  МИНОБРНАУКИ РОССИИ
АЛАТЫРСКИЙ ФИЛИАЛ
Федерального государственного бюджетного образовательного учреждения высшего профессионального образования
«Чувашский государственный университет имени И.Н.Ульянова»
Факультет управления и экономики
Кафедра Высшей математики и информационных технологий
ДИСКРЕТНАЯ МАТЕМАТИКА
группа ЗАФТ – 03 – 13
1 курс (1 семестр)
Преподаватель: асс. Турайкина Е.В.
Алатырь 2013
ДИСКРЕТНАЯ МАТЕМАТИКА
Методические указания по выполнению контрольной работы
Введение
Изучение дисциплины «Дискретная математика» предусмотрено Государственным образовательным стандартом высшего профессионального образования, регламентирующими процесс подготовки бакалавров по специальности 010500 «Математическое обеспечение и администрирование информационных систем». В соответствии с этими же стандартами данная дисциплина должна быть обеспечена практикумом.
Контрольная работа по дисциплине «Дискретная математика» нацелена на ознакомление студентов с основами дискретной математики. В процессе обучения прививаются навыки свободного обращения с основными понятиями комбинаторики, бинарными отношениями, булевыми функциями, функциями k-значной логики, графами и вырабатывается представление о проблематике теории кодирования.
Изучение данной дисциплины способствует более глубокому пониманию проблематики теории алгоритмов, ее возможностей и трудностей, помогает строить алгоритмы для решения дискретных задач.
Общие методические указания
Задания носят теоретический и практический характер и заключаются в решении задач и ответах на вопросы. Задания выполняются в строгой последовательности: сначала указывается условие, затем ответ. Контрольная работа выполняется в письменном виде в виде распечаток результата выполненного задания. Объем контрольной работы не должен превышать 20 печатных страниц. Работа должна быть грамотно написана, правильно оформлена. Страницы нумеруются, ставится номер варианта. В конце работы указывается список используемой литературы. Номер варианта соответствует порядковому номеру студента в списке группы.
Контрольную работу необходимо представить в сроки, указанные в учебном графике. Работы, не отвечающие требованиям методических указаний, не засчитываются.
Перечень дисциплин, усвоение которых необходимо студентам для изучения данной дисциплины:
математика;
математическая логика;
программирование.
Контрольная работа оформляется в следующем виде:
титульный лист;
содержание;
затем приводятся:
для теоретических заданий – вариант ответа;
для практических заданий – распечатки результатов выполненной работы на компьютере и описание проделанных действий.
список использованной литературы.
Задание №1. Теоретический вопрос
При выполнении данного задания необходимо более полно раскрыть поставленную тему приведением всех необходимых ссылок
на использованные источники литературы.
-
№ варианта
|
Индивидуальная тема
|
1
|
Элементы теории нечетких множеств.
|
2
|
Циклы. Фундаментальные множества циклов.
|
3
|
Жадный алгоритм построения минимального остовного дерева
|
4
|
Эйлеровы графы.
|
5
|
Свойства гамильтоновых графов. Задача коммивояжера.
|
6
|
Представление графов в ЭВМ
|
7
|
Алгоритм ближайшего соседа построения остовного дерева.
|
8
|
Кратчайшие пути на графе.
|
9
|
Кодирование. Виды кодирования.
|
10
|
Группы. Приложения групп.
|
11
|
Полиномиальная формула. Бином Ньютона.
|
12
|
Раскраски графов.
|
13
|
Деревья.
|
14
|
Парадоксы теории множеств.
|
15
|
Сортировка всплытием Флойда.
|
Задание №2. Практические задания
А) Дано: А {1,2,3,5,7} и В {3,4,5}. Найти А∩В, В\А. Решить аналитически и с помощью кругов Эйлера-Венна.
Б) Дано А={пароход}, В= {водоворот}, C= {флот}. Найти А∩В, А+В, A\B, B\С, C∩A.
В) Отношение R на множестве А {a, b, c, d} задано матрицей:
Л И Л И
И И Л И
Л Л И Л
Л И И И
Назовите упорядоченные пары, принадлежащие R. Постройте орграф.
Г) Перечислите упорядоченные пары, принадлежащие отношениям, заданным на множестве {x: x Z b 1≤x≤12}.
R= {(x,y) : xy=9}
Д) Определите какие из следующих отношений между множествами
А= {a,b,c,d} и В={1,2,3,4} являются функциями из множества А в В.
1) h = {(a,2), (c,1), (b,4), (d,2)};
2) s = {(a,2), (c,1), (d,2)};
3) m = {(a,2), (d,1), (b,4), (d,3)}.
Е) Найти матрицы смежности, инциденции и расстояний для графа G=(V,E):
Ж) Выясните, является ли граф, заданный следующей матрицей смежности, деревом:
З) Решите задачу с помощью графа.
В шахматном турнире принимали уча стие 6 партнеров разных профессий: токарь, слесарь, инженер, учитель, врач и шофер.
Известно:
1. в первом туре Андреев играл с врачом, учитель с Борисовым, а Григорьев с Евдокимовым;
2. во втором туре Дмитриев играл с токарем, а врач с Борисовым;
3. в третьем туре Евдокимов играл с инженером;
4. по окончании турнира места распределились так — Борисов I место, Григорьев и инженер поделили II и III места, Дмитриев занял IV Место, а Золотарев и слесарь поделили пятое и шестое места.
Какие профессии имели Григорьев, Дмитриев и Евдо кимов?
И) В таблице дано расстояние в милях между пятью деревнями A, B, C, D, E. Найдите минимальное остовное дерево. Изобразите его.
|
A
|
B
|
C
|
D
|
E
|
A
|
-
|
13
|
3
|
9
|
9
|
B
|
13
|
-
|
11
|
11
|
13
|
C
|
3
|
11
|
-
|
9
|
7
|
D
|
9
|
11
|
9
|
-
|
2
|
E
|
9
|
13
|
7
|
2
|
-
|
К) Каждый ученик класса либо девочка, либо блондин, либо любит математику. В классе 20 девочек, из них 12 блондинок, и одна блондинка любит математику. Всего в классе 24 ученика – блондина, математику из них любят 12, а всего учеников (мальчиков и девочек), которые любят математику – 17, из них 6 девочек. Сколько учеников в данном классе?
Л) Закодировать по Фано сообщения, имеющие следующие вероятности с использованием кодового дерева.
сообщение
|
1
|
2
|
3
|
4
|
5
|
6
|
7
|
вероятность
|
0,4
|
0,2
|
0,1
|
0,1
|
0,1
|
0,05
|
0,05
|
Примерный перечень вопросов к экзамену
Множества: основные определения.
Операции над множествами.
Понятие универсального множества.
Основные свойства операций над множествами.
Диаграммы Эйлера-Венна.
Декартово произведение множеств.
Отношения: основные понятия.
Бинарные отношения.
Способы задания бинарных отношений.
Свойства бинарных отношений.
Соответствия. Основные определения.
Функции. Отображения.
Инъективные, сюръективные и биективные функции.
Операции над соответствиями.
Мощность множества.
Конечные множества.
Бесконечные множества.
Матрица бинарного отношения.
Основные свойства матриц бинарных отношений.
Специальные бинарные отношения
Отношения эквивалентности.
Фактор-множества.
Отношения порядка.
Отношения эквивалентности.
Аксиомы теории множеств
Виды графов.
Способы задания графов.
Матрица смежности графа.
Матрица инцидентности графа.
Матрица весов графа.
Подграфы и части графа.
Операции над графами.
Маршруты в графах, понятие цепи.
Понятие цикла и контура в графе.
Достижимость.
Связность графа.
Матрица связности графа.
Нахождение кратчайших маршрутов.
Степени вершин.
Понятие эйлерова графа.
Понятие гамильтонова графа.
Понятия дерева и леса.
Остовы графов.
Понятие упорядоченного дерева.
Понятие бинарного дерева.
Решение задачи коммивояжера.
Планарные графы.
Понятие раскраски графа.
Понятие алгебраической структуры.
Виды алгебраических структур. Примеры.
Алгебраическая структура: решетка.
Булева алгебра.
Законы булевой алгебры.
Понятие рекуррентных соотношений.
Примеры рекуррентных соотношений.
Понятие корня многочлена.
Каноническое разложение многочлена.
Деление многочленов друг на друга.
Понятие информационной избыточности.
Проверочные (корректирующие) символы.
Понятие циклического кода.
Понятие кода Хэмминга.
Корректирующие коды.
Кодовое расстояние.
Учебно-методическое и информационное обеспечение учебной дисциплины
Рекомендуемая основная литература
№
| Название |
Количество единиц в библиотеке
|
|
Судоплатов С.В., Овчинникова Е.В. Элементы дискретной математики: Учеб. – М.: ИНФРА-М, 2002. – 280 с.
|
30
|
|
Акимов О.Е. Дискретная математика: логика, группы, графы: Учеб. Пособие. – 2-е изд., доп. – М.: Лаборатория базовых знаний, 2001. – 376 с.
|
2
|
|
Новиков Ф.А. Дискретная математика для программистов: Учеб. для вузов / Ф.А. Новиков. – СПб. и др.: Питер, 2002. – 301 с.
|
22
|
Рекомендуемая дополнительная литература
№
| Название |
Количество единиц в библиотеке
|
|
Акимов О.Е. Дискретная математика: логика, группы, графы: Учеб. Пособие. – 2-е изд., доп. – М.: Лаборатория базовых знаний, 2001. – 376 с.
|
2
|
|
Лыскова В.Ю. Логика в информатике: Метод. Пособие / В.Ю. Лыскова, Е.А. Ракитина. – М.: Лаборатория базовых знаний, 2001. – 158 с.
|
1
|
|
Иванов Б.Н. Дискретная математика. Алгоритмы и программы: Учеб. – М.: Лаборатория базовых знаний, 2002. – 288 с.
|
2
|
|
Лавров И.А., Максимова Л.Л. Задачи по теории множеств, математической логике и теории алгоритмов. – 4-е изд. – М.: Физматлит, 2001. – 255 с.
|
3
|
|
Непейвода Н.Н. Прикладная логика: Учеб. пособие. – 2-е изд., испр. и доп. – Новосибирск: Издательство Новосибирского университета, 2000. – 490 с.
|
1
|
|
Яблонский С.В. Введение в дискретную математику: Учеб. пособие. – 3-е изд., стерео. – М.: Высшая школа, 2002. – 384 с.
|
1
|
|
Желтов В. П. Дискретная математика: Крат. конспект лекций / Желтов В. П., Сидоров Н. Н., отв. ред. Желтов В. П. ; Чуваш. гос. ун-т им. И. Н. Ульянова - Чебоксары: Изд-во Чуваш. ун-та, 2000. - 115с.
|
68
|
|
Дистель Рейнгард Теория графов: Изд-во Ин-та математики / Дистель Рейнгард, пер. с англ. Бородина О.В. - Новосибирск: Изд-во Ин-та математики, 2002. - 335с.
|
2
|
|
Асеев Г. Г. Дискретная математика: учебное пособие / Асеев Г. Г., Абрамов О. М., Ситников Д. Э. - Ростов н/Д, Харьков: Феникс, Торсинг, 2003. - 143с.
|
5
|
|
Кожухов С. Ф. Дискретная математика: булевы алгебры: учебное пособие / Кожухов С. Ф., Сургут. гос. ун-т Ханты-Мансийского автоном. округа - Сургут: Изд-во СурГУ, 2008. - 47с.
|
1
|
|
Шевелев Ю. П. Дискретная математика: учебное пособие для вузов по специальности "Прикладная математика и информатика" / Шевелев Ю. П. - СПб. и др.: Лань, 2008. - 591с.
|
2
|
Программное обеспечение и Интернет-ресурсы
http://eqworld.ipmnet.ru – сайт о математике;
http://dic.academic.ru – словари и энциклопедии;
http://mechmath.ipmnet.ru – тематический сайт о математике;
http://free-math.ru – задачи и олимпиады по математике;
www.allmath.ru – учебники по математике;
www.exponenta.ru – образовательный математический сайт.
Программное обеспечение: MS Office, Pascal, Delphi 7.0.
|
