МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ

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

Новокузнецкий институт (филиал)

Факультет информационных технологий

РАБОЧАЯ ПРОГРАММА ДИСЦИПЛИНЫ

(ОПД.Ф.2) «Дискретная математика»

для специальности

010501.65 Прикладная математика и информатика

Специализаций 010211 «Системное программирование», 010202 «Математическое моделирование»

Новокузнецк 2013 Сведения о разработке и утверждении рабочей программы дисциплины Рабочая программа дисциплины (ОПД.Ф.2) «Дискретная математика» федерального компонента цикла ОПД составлена в соответствии с Государственным образовательным стандартом высшего профессионального образования второго поколения по специальности 010200 – Прикладная математика и информатика, утвержденному 23 марта 2000 г., номер государственной регистрации 199 ЕН / СП для специализаций «Системное программирование» и «Математическое моделирование»

Автор к.т.н., доцент Решетникова Е.В.

Рецензент (ы) Рабочая программа обсуждена на заседании кафедры математики и математического моделирования « 10 » декабря Протокол № 2012г.

Заведующий кафедрой Е. В. Решетникова (подпись) Рабочая программа одобрена методической комиссией факультета информационных технологий « 15 » января 2013г. Протокол № Председатель методической комиссии Н.Б. Ермак (подпись) Пояснительная записка Дисциплина «Дискретная математика» для студентов специальности 010501. «Прикладная математика и информатика» входит в состав Государственного Образовательного стандарта Высшего Профессионального Образования (ГОС ВПО). Ее место – в ряду общепрофессиональных дисциплин федерального компонента учебного плана.

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

Выписка из ГОС ВПО специальности «Прикладная математика и информатика»

Дискретная математика ОПД.Ф.02 Функциональные системы с операциями; дискретные структуры (графы, сети, коды); дизъюнктивные нормальные формы и схемы из функциональных элементов.

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

Что является составной частью общей цели ООП – подготовить высококвалифицированных специалистов – математиков, системных программистов для работы в отраслях народного хозяйства, научных и учебных заведениях соответствующего профиля.

Основными задачами дисциплины являются:

* выработка навыков использования теоретико-множественных, логических и графических методов представления данных;

* освоение студентами средств дискретной математики для изучения различных моделей, в том числе и непрерывных.

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

Курс «Дискретная математика» для студентов специальности 010501 структурно разделен (по семестрам) на 2 части: функциональные системы с операциями, дизъюнктивные нормальные формы и схемы из функциональных элементов – 1-й семестр;

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

Формы обучения включают в себя:

- лекции, на которых закладываются теоретическая база знаний по дисциплине «Дискретная математика»;

- практические занятия, где студенты приобретают навыки в решении задач по отдельным разделам дисциплины;

- самостоятельная работа студентов, которая осуществляется в двух формах:

индивидуального выполнения заданий по вариантам и индивидуально-аудиторного – с консультацией у преподавателя, а также составлении студентами тестов и задач по блокам тем;

- разбор сложных задач на плановых консультациях.

По дисциплине осуществляется текущий, промежуточный контроль и итоговый контроль в форме экзамена (1,2 семестры) и зачета (1 семестр).

при обучении по сокращенным программам (дисциплина в целом, разделы и темы) Тесты (3, 6, 12 недели первого семестра) Контрольные работы (18 неделя первого семестра, 17 неделя второго семестра), индивидуальное домашнее задание (13 неделя первого семестра, 10 неделя второго семестра) Содержание частей, разделов и тем курса 1 семестр РАЗДЕЛ 1. Функциональные системы с операциями.

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

Алгебраические системы.

Алгебра логики. K-значная логика.

РАЗДЕЛ 2. Дизъюнктивные нормальные формы и схемы из функциональных элементов.

Дизъюнктивные нормальные формы Синтез схем из функциональных элементов РАЗДЕЛ 3. Комбинаторный анализ.

Комбинаторные объекты и комбинаторные числа.

Рекуррентные соотношения.

Производящие функции.

2 семестр РАЗДЕЛ 4. Дискретные структуры (графы, сети, коды).

Основные понятия теории графов. Алгоритмы на графах.

Сети. Двухполюсные сети из двухобъектных наборов. -сети.

Теория кодирования.

РАЗДЕЛ 5. Функциональные системы с операциями.

Ограниченно-детерминированные функции с операциями.

Машина Тьюринга.

Вычислимые функции.

Содержание практических занятий РАЗДЕЛ 1. Функциональные системы с операциями.

Практическое занятие №1. Множества. Подмножества. Операции над множествами и их свойства. Мощность множеств. Равносильность множеств. Метод взаимного включения. Характеристические предикаты.

План работы:

1. Опрос (письменный или устный). 2. Решение задач.

Примерные задания 2. Построить диаграмму Эйлера, иллюстрирующую множество задания 1.

3. Максимально упростите выражение, пользуясь основными эквивалентностями 4. Докажите тождество двумя способами при помощи характеристических предикатов и методом взаимного включения ( A B) A B.

Практическое занятие №2. Тест по теме множества, подмножества и операции над ними.

Практическое занятие №3. Прямое произведение множеств. Отношения. Операции над отношениями.

План работы:

1. Опрос (письменный или устный). 2. Решение задач.

Примерные задания 2. Задать характеристическим предикатом отношение R M M («быть делителем»), где М={1,2,3,4,5,6}. Составить матрицу отношения. Составить отношения R 1, R, R и их матрицы.

Практическое занятие №4. Соответствия и их свойства. Классы соответствий.

Функции. Типы функций.

План работы:

1. Опрос (письменный или устный). 2. Решение задач.

Примерные задания 1. Определить какими свойствами обладают отношения из 2 задания практического занятия №4. Какие из них являются эквивалентностью, толерантностью, порядком (строгим или нестрогим), предпорядком (строгим или нестрогим)?

2. Определить свойства отношения R ( x, y) | x, y Z, x y 1 на множестве целых чисел Z.

Практическое занятие №5. Тест по теме отношения, свойства отношений, операции над отношениями.

Практическое занятие №6 Алгебраические системы.

План работы:

1. Опрос (письменный или устный). 2. Решение задач.

Примерные задания 1. Установить образуют ли алгебры следующие системы,,, Z, :, 2. Построить подсистему (X ), порожденную множеством X {2}. R, 3.

Практическое занятие №7 Булевы функции, таблицы истинности, эквивалентные преобразования.

План работы:

1. Опрос (письменный или устный). 2. Решение задач.

Примерные задания 1. Построить таблицы соответствующих функций, выяснить, эквивалентны ли формулы и. Для эквивалентных формул докажите эквивалентность, выполнив преобразования одной формулы в другую.

Практическое занятие №8 Существенные переменные. Двойственность булевых функций.

План работы:

1. Опрос (письменный или устный). 2. Решение задач.

Примерные задания 1. Указать все фиктивные переменные у функции f ( x, y, z) (10101010);

2. Используя непосредственно определение двойственности булевых функций, а также основные эквивалентности, выясните, является ли функция g двойственной к функции f:

3. Используя принцип двойственности, постройте формулу, реализующую функцию, двойственную к функции f, и убедитесь в том, что полученная формула эквивалентна Практическое занятие №9 Классы Поста. Полнота систем булевых функций План работы:

1. Опрос (письменный или устный). 2. Решение задач.

Примерные задания 1. Проверить, является ли функция f монотонной: f ( x1 x2 ) & ( x1 ~ x2 );

2. Выяснить, является ли линейной функция f, заданная векторно (методом неопределенных коэффициентов): a f (10010110 );

3. Представив функцию f полиномом, выяснить, является ли она линейной:

4. Выяснить, полна ли система функций: A {xy, x y, x y, xy yz zx};

РАЗДЕЛ 2. Дизъюнктивные нормальные формы и схемы из функциональных элементов.

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

Совершенные нормальные формы.

План работы:

1. Опрос (письменный или устный). 2. Решение задач.

Примерные задания 1. С помощью эквивалентных преобразований построить ДНФ функции:

2. Используя эквивалентные преобразования, построить КНФ функции:

3. Используя дистрибутивный закон, перейти от заданной КНФ функции к ДНФ:

4. Используя дистрибутивный закон, перейти от заданной ДНФ функции к ее КНФ:

6. Представить в СКНФ f ( x1, x2 ) ( x1 x2 );

Практическое занятие №11 Минимизация нормальных форм.

План работы:

1. Опрос (письменный или устный). 2. Решение задач.

Примерные задания 1. С помощью алгоритма Квайна построить МДНФ для функции f, заданной вектором своих значений: f = (01110110);

2. Найти МДНФ функции f с помощью карты Карно: f = (01010111);

Практическое занятие №12. Тест по теме булевы функции.

Практическое занятие №13 Схемы из функциональных элементов.

План работы:

1. Опрос (письменный или устный). 2. Решение задач.

Примерные задания 1. Постройте схему из функциональных элементов по данной функции проводимости:

2. Постройте наиболее простую схему из функциональных элементов по заданным условиям работы: f (0,0,0) f (0,1,0) f (1,0,0) f (0,1,1) 3. Спроектируйте схему из функциональных элементов, позволяющую включать и выключать одну электрическую лампочку с помощью трех независимых переключателей.

Сколькими способами можно сконструировать схему?

4. Комитет состоит из пяти человек. Решение выносится большинством голосов. Если председатель «против», то решение не принимается. Построить такую схему, чтобы, голосуя «за», каждый из пяти человек нажимал бы кнопку, и в случае принятия решения зажигалась бы сигнальная лампочка.

РАЗДЕЛ 3. Комбинаторный анализ.

Практическое занятие №14 Конечные множества и комбинаторика.

План работы: 1. Опрос (письменный или устный). 2. Решение задач.

Примерные задания 1. Сколько существует способов задать код, состоящий из 4 букв английского алфавита?

2. Найдите номер члена разложения ( x x 2 )12, не содержащего x.

Практическое занятие №15 Метод рекуррентных соотношений.

План работы: 1. Опрос (письменный или устный). 2. Решение задач.

Примерные задания 1. Найти общее решение f (n 2) 7 f (n 1) 12 f (n) 0, Практическое занятие №16 Счетные множества и производящие функции.

План работы: 1. Опрос (письменный или устный). 2. Решение задач.

Примерные задания 1. Какую последовательность производит функция f ( x) 1, ее производная f (x), ее первообразная F (x) ?

Практическое занятие №17 Контрольная работа по комбинаторике.

2 семестр РАЗДЕЛ 4. Дискретные структуры (графы, сети, коды).

Практическое занятие №1 Способы задания графов. Операции над графами. Обходы графов. Поиск остова.

План работы: 1. Опрос (письменный или устный). 2. Решение задач Примерные задания 1. Придумайте 6 графов: орграф, неорграф, мультиграф, псевдограф, несвязный граф, граф с изолированными вершинами. Опишите известными вам способами данные графы:

матрицей смежности; матрицей инцидентности; структурой смежности; списком ребер.

2. Используя поиск в глубину или ширину, определить количество компонент связности произвольного графа.

3. Разработать алгоритм поиска эйлерова цикла для ориентированного графа.

Практическое занятие №2 Задача оптимального расписания. Раскраска вершин графа.

План работы: 1. Опрос (письменный или устный). 2. Решение задач Примерные задания 1. Разработать алгоритм нахождения паросочетания максимального веса в двудольном графе.

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

Практическое занятие №3 Поиск минимального маршрута.

План работы: 1. Опрос (письменный или устный). 2. Решение задач Примерные задания 1. Применить алгоритм Форда-Беллмана для определения кратчайшего маршрута в графе (от 1 до 12 вершины) Практическое занятие №4 Задача коммивояжера. Поиск максимального потока в сети.

План работы: 1. Опрос (письменный или устный). 2. Решение задач Примерные задания 1. Применить алгоритм решения задачи коммивояжера.

2. Найти максимальный поток в сети.

Практическое занятие №5 Теория кодирования План работы: 1. Опрос (письменный или устный). 2. Решение задач Примерные задания 1. Кодировать слово 0110 с помощью кода с проверкой четности, кода с тройным повторением.

2. Определить расстояние Хемминга между словами 1010 и 1110.

3. Построить код Хаффмана по частотам:

РАЗДЕЛ 5. Функциональные системы с операциями.

Практическое занятие №6 Машина Тьюринга.

План работы: 1. Опрос (письменный или устный). 2. Решение задач Примерные задания 1. Построить машину Тьюринга, реализующую умножение двух чисел в унарном коде.

Практическое занятие №7 Вычислимые функции План работы: 1. Опрос (письменный или устный). 2. Решение задач Примерные задания 1. Доказать, что умножение примитивно-рекурсивная функция.

Практическое занятие №8 Контрольная работа по темам Машина Тьюринга.

Вычислимые функции.

Примерная тематика тестов, индивидуальных заданий и контрольных работ.

1 семестр 1. Множества, подмножества и операции над ними (Тест - практическое занятие №3)..

2. Отношения, свойства отношений, операции над отношениями (Тест - практическое занятие №6).

3. Булевы функции (Тест - практическое занятие №12).

4. Булевы функции (Индивидуальное домашнее задание) 5. Комбинаторика (Контрольная работа - практическое занятие №17) 2 семестр 1. Теория графов (Индивидуальное домашнее задание).

2. Машина Тьюринга. Вычислимые функции. (Контрольная работа - практическое занятие №8) Основная литература 1. Соболева, Т. С. Дискретная математика [Текст] : учебное пособие для вузов / под ред. А. В. Чечкина. - М.: Академия, 2006. - 256 с. - (Университетский учебник). - Гриф МО "Допущено" 2. Кузнецов, О. П. Дискретная математика для инженера [Текст]: учебник. - Издание 6е, стереотипное. - СПб. [и др.] : Лань, 2009. - 400 с. - (Учебники для вузов. Специальная литература).

3. Редькин, Н.П. Дискретная математика [Текст]: учебник. – М.: Физматлит, 2009. – с. – Гриф «Рекомендовано» УМО по классическому университетскому образованию в качестве учебника для студентов высших учебных заведений, обучающихся по направлениям подготовки 010100 «Математика», 010200 «Математика. Прикладная математика», 011000 «Механика. Прикладная математика». – Режим доступа:

http://e.lanbook.com/view/book/2293/ Дополнительная литература 1. Асанов, М. О. Дискретная математика : графы, матроиды, алгоритмы [Текст] : учебное пособие. - Издание 2-е, исправленное и дополненное. - Санкт-Петербург [и др.] : Лань, 2010. - с. - (Учебники для вузов. Специальная литература).

2. Горбатов, В. А. Фундаментальные основы дискретной математики. Информационная математика [Текст] : учебник для вузов. - М. : Наука [и др.], 2000. - 544 с.

3. Новиков, Ф. А. Дискретная математика для программистов [Текст] : учебное пособие. - 2-е издание. - СПб. [и др.] : Питер, 2004. - 364 с. - (Учебник для вузов). - Гриф МО "Допущено" 4. Акимов, О. Е. Дискретная математика: Логика, группы, графы [Текст] : учебник. - Издание 2-е, дополненное. - М. : Лаборатория Базовых Знаний, 2003. - 376с. - (Технический университет).

5. Яблонский, С.В. Введение в дискретную математику [Текст]: Учебное пособие для вузов. е изд., стереот. - М. : Высшая школа, 2001. - 384с. - Гриф МО "Допущено".

6. Иванов, Б.Н. Дискретная математика: Алгоритмы и программы [Текст]: Учебное пособие. М. : Лаборатория Базовых Знаний, 2002. - 288с. - (Технический университет).

7. Судоплатов, С. В. Элементы дискретной математики [Текст] : учебник для втузов. - М.Новосибирск : ИНФРА-М; НГТУ, 2002. - 280 с. - (Высшее образование). - Гриф МО "Рекомендовано".

8. Гаврилов, Г.П., Сапоженко, А.А. Задачи и упражнения по дискретной математике [Электронный ресурс] – 3-е издание, перераб. - Москва: Физматлит, 2009. – 416 с. Режим доступа:

http://e.lanbook.com/view/book/2157/ 9. Копылов, В.И. Курс дискретной математики [Электронный ресурс] – 1-е изд. – СанктПетербург [и др.] : Лань, 2011. – 208 с. - Режим доступа: http://e.lanbook.com/view/book/1798/ 10. Куликов В.В. Дискретная математика [Электронный ресурс]: Учебное пособие / В.В.

Куликов. - М.: РИОР, 2007. - 174 с. Режим доступа: http://znanium.com/bookread.php?book= 11. Аляев, Ю. А. Дискретная математика и математическая логика [Текст] : учебник. - М. :

Финансы и статистика, 2006. - 368 с.

4. Формы текущего, промежуточного и рубежного контроля Формы и порядок проведения контроля.

Текущий Устные опросы в начале каждого Устные опросы в начале Критерии оценки знаний студентов.

Знания и умения студентов проверяются при текущем, промежуточном и итоговом контроле оцениваются на «отлично», «хорошо», «удовлетворительно», «неудовлетворительно» в соответствии с указаниями ГОС (по всем дисциплинам и практикам, включенным в учебный план высшего учебного заведения, должна выставляться итоговая оценка по шкале - отлично, хорошо, удовлетворительно, неудовлетворительно или зачтено, не зачтено).

Критерии оценки знаний студентов в целом по дисциплине:

«отлично» выставляется студенту, показавшему всесторонние, систематизированные, глубокие знания учебной программы дисциплины и умение уверенно применять их на практике при решении конкретных задач, свободное и правильное обоснование принятых решений;

«хорошо» - выставляется студенту, если он твердо знает материал, грамотно и по существу излагает его, умеет применять полученные знания на практике, но допускает в ответе или в решении задач некоторые неточности;

«удовлетворительно» - выставляется студенту, показавшему фрагментарный, разрозненный характер знаний, недостаточно правильные формулировки базовых понятий, нарушения логической последовательности в изложении программного материала, но при этом он владеет основными разделами учебной программы, необходимыми для дальнейшего обучения и может применять полученные знания по образцу в стандартной ситуации;

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

– оценки «зачтено» заслуживает студент, обнаруживший всестороннее, систематическое и глубокое знание учебно-программного материала, умение свободно выполнять задания, предусмотренные программой, усвоивший основную и знакомый с дополнительной литературой, рекомендованной программой. Как правило, оценка «зачтено» выставляется студентам, усвоившим взаимосвязь основных понятий дисциплины в их значении для приобретаемой специальности.