В. П. Некрасов дискретная математика




Скачать 304.78 Kb.
НазваниеВ. П. Некрасов дискретная математика
страница1/4
Дата публикации09.10.2013
Размер304.78 Kb.
ТипМетодические указания
skachate.ru > Информатика > Методические указания
  1   2   3   4
Федеральное агентство связи

ФГОБУ ВПО «Сибирский государственный университет

телекоммуникаций и информатики»

Уральский технический институт связи и информатики (филиал)


В.П. Некрасов

ДИСКРЕТНАЯ МАТЕМАТИКА
Методические указания по выполнению домашней контрольной работы

для студентов заочной формы обучения (нормативного срока)

на базе среднего (полного) общего образования направления

230100 «Информатика и вычислительная техника»

профили «Программное обеспечение средств

вычислительной техники и автоматизированных систем»,

«Вычислительные машины, комплексы, системы и сети»

в соответствии с требованиями ФГОС ВПО 3 поколения

Квалификация (степень) выпускника «бакалавр»

Екатеринбург

2011




УДК 519.1

ББК 22.17я73
Рецензент: к.т.н., доцент кафедры информатики ГОУ ВПО «УГГУ» Ю.С. Петров
Некрасов В. П.

Дискретная математика: Методические указания по выполнению домашней контрольной работы / В.П. Некрасов. — Екатеринбург: УрТИСИ ФГОБУ ВПО «СибГУТИ», 2011. — 42 с.
Методические указания предназначены для выполнения домашней контрольной работы (ДКР) по дисциплине «Дискретная математика».

Методические указания содержат задания по темам:

  • основы теории множеств;

  • отношения;

  • основы теории алгоритмов;

  • методы сортировки.



Рекомендовано НМС УрТИСИ ФГОБУ ВПО СибГУТИ в качестве методических указаний по выполнению домашней контрольной работы студентами заочной формы обучения на базе среднего (полного) общего образования по направлению 230100 «Информатика и вычислительная техника» профили: «Программное обеспечение средств вычислительной техники и автоматизированных систем», «Вычислительные машины, комплексы, системы и сети»


УДК 519.1

ББК 22.17я73

Кафедра информационных систем и технологий

 УрТИСИ ФГОБУ ВПО «СибГУТИ», 2011
СОДЕРЖАНИЕ


ВВЕДЕНИЕ 4

Содержание дисциплины 5

Задание и методические указания по выполнению ДКР 11

Задание 1 11

Задание 2 19

Задание 3 21

Задание 4 44

ВВЕДЕНИЕ



Методические указания по выполнению домашней контрольной работы составлены в соответствии с рабочей программой по дисциплине «Дискретная математика» для направления 230100 «Информатика и вычислительная техника»

Современной вычислительной, информационной и телекоммуникационной технике присущ дискретный характер процессов, поэтому теоретической основой их описания является дискретная математика. Изучаемые понятия, методы и алгоритмы в той или иной степени встречаются в последующих курсах данной специальности.

Содержание дисциплины включает семь тем. Структура учебной дисциплины характеризуется как комплексным подходом к пониманию общих методов дискретной математики, так и прагматической направленностью курса на освоение его основных понятий. Выполнение домашней контрольной работы позволит студентам закрепить теоретические знания курса и использовать их при последующем изучении как общепрофессиональных, так и специальных дисциплин.

^

Содержание дисциплины



1. Цели и задачи дисциплины:

Целью преподавания дисциплины «Дискретная математика» является подготовка студента к профессиональной деятельности, связанной с формированием его общей технической культуры.

Изучение основных понятий дискретной математики, их взаимосвязей и областей практического применения формирует общий технический уровень студента, позволяющий ему эффективно решать инженерные и научно технические задачи.
^ 2. Место дисциплины в структуре ООП:

Дисциплина «Дискретная математика» относится к числу дисциплин вариативной части ООП и является дисциплиной по выбору студента для подготовки бакалавров по направлению 230100 «Информатика и вычислительная техника».

Дисциплина «Дискретная математика» опирается на такие дисциплины как «Математика» и «Информатика» и имеет непосредственную связь с такими дисциплинами, входящими в учебный план, как «Базы данных», «Теория принятия решений», «Теория автоматов», «Теория сложностей вычислительных процессов и структур».

Знания и умения, полученные в результате освоения материала курса «Дискретная математика», являются базой для формирования единого образовательного пространства при подготовке бакалавра по направлению «Информатика и вычислительная техника».
^ 3. Требования к результатам освоения дисциплины:

    Процесс изучения дисциплины направлен на формирование следующих компетенций:

  • владеет культурой мышления, способен к обобщению, анализу, восприятию информации, постановке цели и выбору путей ее достижения (ОК-1);

  • использует основные законы естественнонаучных дисциплин в профессиональной деятельности, применяет методы математического анализа и моделирования, теоретического и экспериментального исследования (ОК-10);


В результате изучения дисциплины студент должен:

Знать: основные положения теории множеств; отношения на множествах; базовые структуры представления данных; основные положения теории графов; основные виды комбинаторных алгоритмов; элементы теории сложности, методы построения эффективных алгоритмов.

Уметь: применять математические методы для решения практических задач; определить метод и выбрать наиболее приемлемый алгоритм для программной реализации конкретной задачи, оценить его временную сложность; подобрать наиболее подходящую структуру представления данных.

Владеть: методами построения эффективных алгоритмов.


    ^ 4. Объем дисциплины и виды учебной работы:

Общая трудоемкость дисциплины составляет 4 зачетные единицы.


^ Виды учебной работы, формы контроля

Всего, час.

Учебные семестры

144

4

^ Аудиторные занятия

16

16

В том числе







Лекции

8

8

Практические занятия (ПЗ)

8

8

Лабораторные работы (ЛР)







^ Самостоятельная работа (всего)

128

128

В том числе:







Подготовка к аудиторным занятиям (ПАЗ)







Курсовая работа (КР)







Экзамен

0

Экзамен

^ Общая трудоемкость по учебному плану

144

144

Трудоемкость в зачетных единицах

4

4


^ 5. Содержание дисциплины

5.1. Содержание разделов дисциплины

5.1.1. Элементы теории множеств

О понятии множества. Принадлежность элемента множеству. Конечные и бесконечные множества. Универсум. Мощность множества. Пустое множество. Способы задания множеств. Свойства множеств. Равенство двух множеств. Подмножества.

Теоретико - множественные операции. Их интерпретация кругами Эйлера. Свойства операций над множествами. Изоморфизм теоретико-множественных и логических операций.

Вектор (кортеж). Декартово произведение множеств.
5.1.2. Отношения

Отношения на множествах. Бинарное отношение. Определение отношения. Задание отношений. Задание графа через отношение. Свойства отношений. Интерпретация свойств отношений с помощью теории графов.

Отношение эквивалентности. Отношение порядка.

Отношение как базовое понятие в реляционных базах данных. Поле. Запись. Домен. Операции над таблицами.
^ 5.1.3. Основные понятия теории графов

Определение графа. Смежность. Инцидентность. Изоморфизм. Мультиграф. Псевдограф. Подграф. Полный граф. Двудольный граф. Планарный граф. Степень вершины. Теорема Эйлера. Маршрут. Цепь. Простая цепь. Цикл. Простой цикл. Эйлеров и гамильтонов циклы.

Ориентированный граф. Полустепени исхода и захода. Ориентированный маршрут. Путь. Контур. Длина маршрута. Взвешенный граф.

Матрицы графа. Матрица смежностей. Матрица инциденций. Связный граф. Компоненты связности. Дерево. Остовное дерево. Раскраска графа. Хроматическое число.
^ 5.1.4. Структуры данных

Понятие структуры данных в программировании.

Одномерный и двумерный массивы. Стек. Очередь. Дерево. Размещение дерева по уровням.

Представление графа в компьютере. Представление матрицей смежностей, массивами ребер, списками смежностей. Реализация списков смежностей упакованным массивом.
^ 5.1.5. Комбинаторные алгоритмы на графах

Интуитивное понятие алгоритма. Свойства алгоритма. Вычислительные и комбинаторные алгоритмы. Схема поиска решения комбинаторной задачи. Метод полного перебора. Комбинаторный взрыв. Жадные и эвристические алгоритмы.

Временная эффективность алгоритмов. Асимптотические оценки сложности. Полиномиальные и экспоненциальные алгоритмы. Контрольные прогоны.

Нахождение минимального остовного дерева. Жадный алгоритм. Алгоритм Прима.

Алгоритм Дейкстра поиска кратчайшего пути в графе между двумя заданными вершинами. Алгоритм Уоршолла построения транзитивного замыкания.

Эвристические алгоритмы. Основные правила. Последовательный алгоритм раскраски графа. Алгоритм раскраски графа А.П. Ершова.
^ 5.1.6. Методы сортировки

Внутренняя сортировка. Пузырьковые сортировки. Сортировки выбором и вставкой. Быстрая сортировка. Пирамидальная сортировка. Сортировка подсчетом.

Внешняя сортировка. Методы прямого и естественного слияния. Основная теорема сортировки.
5.1.7. Поиск

Бинарный поиск. Поиск на графах в глубину и ширину. Поиск связных компонент графа. Топологическая сортировка.

Поиск в строке текста заданного фрагмента. Последовательный поиск. Метод Боуэра и Мура.
^ 5.2 Разделы дисциплины и междисциплинарные связи

с обеспечиваемыми (последующими) дисциплинами

№ п/п

Наименование обеспечиваемых (последующих) дисциплин

№ разделов данной дисциплины, необходимых для изучения обеспечиваемых (последующих) дисциплин

5.1.1

5.1.2

5.1.3

5.1.4

5.1.5

5.1.6

5.1.7



Базы данных

+

+




+












Теория принятия решений

+

+

+

+

+

+

+



Теория автоматов

+




+




+









Теория сложнос-тей вычислительных процессов и структур

+




+




+

+





^ 5.3. Разделы дисциплин и виды занятий

№ п/п

Наименование раздела дисциплины

Лек-ции

Практ.

зан.

Семин

СРС

Всего

час.

I

Элементы теории множеств

1

1




14

16

II

Отношения

1

1




14

16

III

Основные понятия теории графов

1







20

21

IV

Структуры данных










20

20

V

Комбинаторные алгоритмы на графах

2

4




20

26

VI

Методы сортировки

2

2




20

24

VII

Поиск

1







20

21




Итого по дисциплине

8

8




128

144


^ 6. Практические занятия (семинары)

№ п/п

№ раздела дисциплины

Тематика практических

занятий (семинаров)

Трудомкость

(час.)

1



Теоретико-множественные операции

1

2

II 

Свойства отношений

1

3

VI

Нахождение минимального остовного дерева

2

4

VI

Раскраска графа в минимальное число цветов

2

5

VII

Методы сортировки

2


^ 7. Учебно-методическое и информационное обеспечение дисциплины

а) основная литература

1. Некрасов В.П. Элементы дискретной математики: Учебное пособие. 2-е изд., перераб. и доп. — Екатеринбург: УрТИСИ ФГОБУ ВПО «СибГУТИ», 2006

2. Некрасов В. П. Методы поиска: Учебное пособие. — Екатеринбург: УрТИСИ ФГОБУ ВПО «СибГУТИ», 2008

3. Некрасов В. П. Методы сортировки: Учебное пособие. — Екатеринбург: УрТИСИ ФГОБУ ВПО «СибГУТИ», 2007

4. Некрасов В. П. Структуры данных: Учебное пособие. — Екатеринбург: УрТИСИ ФГОБУ ВПО «СибГУТИ», 2007
б) дополнительная литература

1. Москинова Г.И. Дискретная математика. Математика для менеджера в примерах и упражнениях. М.: Логос, 2002

2. Аляев Ю.А., Тюрин С.Ф. Дискретная математика и математическая логика: учебник. — М.: Финансы и статистика, 2006

3. Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: построение и анализ. М.: МЦНМО, 2000

4. Кузнецов О.П. Дискретная математика для инженера. СПб.: Лань, 2004
^ 8. Материально-техническое обеспечение дисциплины

Компьютерный класс с подключением к сети Интернет.
9. Методические рекомендации по организации изучения дисциплины

Для обеспечения освоения дисциплины используются разработанные преподавателями кафедры методические материалы в форме учебных пособий.


  1   2   3   4

Похожие:

В. П. Некрасов дискретная математика iconВ. П. Некрасов дискретная математика
Методические указания предназначены для выполнения домашней контрольной работы (дкр) по дисциплине «Дискретная математика»
В. П. Некрасов дискретная математика iconДискретная математика
Колесников А. В. Дискретная математика/ Задания и методические указания к курсовой работе для студентов специальностей 230102. 65...
В. П. Некрасов дискретная математика iconУчебно-методический комплекс по дисциплине «Дискретная математика и математическая логика»
Рабочей учебной программы по курсу «Дискретная математика и математическая логика», утверждённой деканом факультета непрерывного...
В. П. Некрасов дискретная математика iconВведение 5 1 введение в теорию множеств 6
Дискретная математика зародилась в глубокой древности и включает в себя многие разделы математики, такие как теория множеств, математическая...
В. П. Некрасов дискретная математика iconАннотация дисциплины «Дискретная математика» Целью дисциплины
Целью дисциплины является ознакомление обучающихся с основами теории графов и теории конечных автоматов. Дисциплина "Дискретная математика"...
В. П. Некрасов дискретная математика iconДискретная математика программа, методические указания и задания для контрольной работы
Методические указания предназначены для студентов второго курса заочной формы обучения по направлению «Телекоммуникации», изучающих...
В. П. Некрасов дискретная математика iconСрс по дисциплине «Дискретная математика»
Множества M, А, В, с – произвольные, множество I – универсальное (универсум),  пустое множество
В. П. Некрасов дискретная математика iconКонтрольная работа №1 По дисциплине «Дискретная математика 2»
В данном графе 4 вершины, следовательно, матрица смежности графа – это матрица A(44)
В. П. Некрасов дискретная математика iconАннотация рабочей программы учебной дисциплины "Дискретная математика"
Дисциплина учебного плана подготовки бакалавра по направлению 230100 Информатика и вычислительная техника (профиль подготовки "Автоматизированные...
В. П. Некрасов дискретная математика iconТемы курса пояснительная записка к методическим указаниям Методические...
Дисциплина «Дискретная математика» относится к вариативной части профессионального цикла основной профессиональной образовательной...

Вы можете разместить ссылку на наш сайт:
Школьные материалы


При копировании материала укажите ссылку © 2014
контакты
skachate.ru
Главная страница