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

Федеральное агентство по образованию

Государственное образовательное учреждение

высшего профессионального образования

«Оренбургский государственный университет»

Кафедра программного обеспечения вычислительной техники

и автоматизированных систем

УТВЕРЖДАЮ

Декан факультета информационных технологий _ А.М. Пищухин « _ » 2007 г.

Рабочая программа дисциплины «Дискретная математика»

Направление подготовки: 654600 «Информатика и вычислительная техника»

Специальность: 230105.65 «Программное обеспечение вычислительной техники и автоматизированных систем»

Факультет информационных технологий Форма обучения: очная Оренбург Рецензент:

кандидат технических наук, доцент Боровский А.С.

Рабочая программа дисциплины «Дискретная математика» /сост.

А.В. Каменев. – Оренбург: ГОУ ОГУ, 2007. - с.

Рабочая программа предназначена для преподавания дисциплины общепрофессионального цикла студентам очной формы обучения специальности 230105.65 – «Программное обеспечение вычислительной техники и автоматизированных систем» в 3 семестре.

Рабочая программа составлена с учетом Государственного образовательного стандарта высшего профессионального образования по направлению подготовки дипломированных специалистов 654600 – ИНФОРМАТИКА И ВЫЧИСЛИТЕЛЬНАЯ ТЕХНИКА, утвержденного 27.03.2000 Министерством Образования Российской Федерации.

Составитель: А.В. Каменев 20.05.2007 г.

©Каменев А.В., © ГОУ ОГУ, Содержание с.

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

2 Место дисциплины в учебном процессе…………………………………… 3 Организационно-методические данные дисциплины……………………...

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

4.1 Выписка из ГОС ВПО «Требования к обязательному минимуму содержания основной образовательной программы» по дисциплине 4.2 Разделы дисциплины, их содержание и виды занятий ……..……………..

5 Тематический план изучения дисциплины ………………..……………….

5.1 Лабораторные работы………………………………………………………..

5.2 Практические (семинарские) занятия……………………………………….

5.3 Самостоятельное изучение разделов дисциплины…………….…………..

6 Учебно-методическое обеспечение дисциплины………………………….

6.1 Рекомендуемая литература………………………………………….……… 6.1.1 Основная литература………………………………………………………… 6.1.2 Дополнительная литература………………………………………………… 6.2 Средства обеспечения освоения дисциплины……………………..……….

6.2.1 Методические указания и материалы по видам занятий……….………….

6.2.2 Программное обеспечение использования современных информационно-коммуникационных технологий (по видам занятий) ……………………………………………………………….……… 6.2.3 Контрольные вопросы для самоподготовки…………………….………….

6.2.4 Критерии оценки знаний, умений и навыков……………………………… 7 Материально-техническое обеспечение дисциплины……………………..

7.1 Учебно-лабораторное оборудование ……….……………………………… Лист согласования рабочей программы …………………………………… Дополнения и изменения в рабочей программе…………………………… 1 Цели и задачи курса Целью дисциплины является изучение и освоение методов дискретной математики, наиболее применяемых при проектировании вычислительной техники и автоматизированных систем. Формирование практических навыков разработки и анализа алгоритмов над объектами дискретной математики В результате изучения дисциплины студент должен:

- способы задания, свойства множеств, отношений, функций и отображений;

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

- методы осуществления операций над графами и выполнения количественных оценок их характеристик;

- стандартные и рекурсивные схемы алгоритмов, структуры и потоки данных;

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

- использования символики дискретной математики для выражения количественных и качественных отношений объектов;

иметь представление:

- о перспективах использования методов дискретной математики при разработке моделей систем автоматики и вычислительной техники.

2 Место дисциплины в учебном процессе Дисциплина относится к циклу общепрофессиональных дисциплин и федеральному компоненту ООП.

Изучение данной дисциплины базируется на следующих дисциплинах:

- математический анализ;

- вычислительная математика;

- программирование.

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

- математическая статистика и случайные процессы;

- программирование на языках высокого уровня;

- методы и средства защиты компьютерной информации.

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

3 Организационно-методические данные дисциплины разделов, проработка и повторение лекционного материала и материала учебников и учебных пособий, подготовка к лабораторным и практическим занятиям, коллоквиумам и т.д.), (СР) 4 Содержание дисциплины 4.1 Выписка из ГОС ВПО «Требования к обязательному минимуму содержания основной образовательной программы» по дисциплине «Дискретная математика»:

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

алгебры с двумя операциями; решетки; матроиды; графы; операции над графами;

независимость и покрытия; циклы и разрезы; деревья; алгебра логики; Булевы функции; Булева алгебра; нормальные формы представления; функциональная полнота и замкнутость; минимизация булевых функций; стандартные и рекурсивные схемы; эквивалентность схем алгоритмов; структуры и потоки данных; применение методов дискретной математики при проектировании и моделировании.

4.2 Содержание дисциплины Таблица 3 – Разделы дисциплины, изучаемые в 3 семестре Роль дискретной математики при разработке и эксплуатации технических Задание множеств и осуществление операций над ними. Минимизация представлений множеств. Отношения и их свойства. Функции.

Задание и характеристики графов.

Операции над графами. Связность графов.

Независимость и покрытия. Циклы и разрезы. Деревья.

Булевы функции. Булева алгебра.

Нормальные формы представления функций. Функциональная полнота и замкнутость. Минимизация булевых Операции и алгебры. Алгебры с одной операцией. Алгебры с двумя операциями.

Решетки. Матроиды.

Стандартные и рекурсивные схемы.

Эквивалентность схем алгоритмов.

Структуры и потоки данных.

Применение методов дискретной математики при проектировании 5 Тематический план изучения дисциплины п/п 1. Роль дискретной математики при разработке и эксплуатации 4. Упорядоченность. Дополнение. Кольцо множеств 3 2 Функции. Множества бесконечные, счетные.

1. Связность в неориентированных графах и орграфах.

1. Формулы булевой алгебры. Основные законы булевой 2. Эквивалентность формул. Принцип двойственности.

Нормальные формы представления 1. Совершенные дизъюктивные (СДНФ) и совершенные 3. Геометрическое представление булевых функций.

15 5 Функциональная полнота и замкнутость 1. Системы элементарных булевых функций. Определение функционально полной системы элементарных булевых 2. Примеры функционально полных базисов. Важнейшие замкнутые классы. Теорема о функциональной полноте.

3. Понятие о реализации булевых функций. Условная цена Минимизация булевых функций 1. Сокращенная, тупиковая и минимальная формы;

2. Операции элементарного и неполного склеивания; операция поглощения. Метод Квайна – Мак-Клоски. Метод карт 3. Минимизация не полностью определенных функций.

4 3 Алгебраические структуры 1. Алгебраические структуры;

3. Алгебра термов; изоморфные алгебры;

4. Алгебры с одной операцией; алгебры с двумя операциями.

1. Решетки. Ограниченные решетки. Решетки с дополнением.

2. Матроиды. Максимальные независимые подмножества.

17 6 Стандартные и рекурсивные схемы 18 6, 7 Эквивалентность схем алгоритмов 1. Функциональная эквивалентность схем алгоритмов.

3. Применение методов дискретной математики при 5.2 Лабораторные работы Представление и выполнение операций над множествами 5.3 Практические занятия Представление и выполнение операций над множествами 5.4 Самостоятельное изучение разделов дисциплины № Вопросы, выносимые на самостоятельное изучение раздела Жадный алгоритм. Эквивалентные преобразования. Пороговая логика. Биномиальные коэффициенты. Модулярная арифметика.

Алгоритм нахождения максимального потока.

6 Учебно-методическое обеспечение дисциплины 6.1 Рекомендуемая литература 6.1.1 Основная литература Акимов, О.Е. Дискретная математика: логика, группы, графы / О.Е.

Акимов.- 2-е изд., доп. - М. : ЛБЗ, 2001. – 376 с.

Белоусов, А.И. Дискретная математика: Учеб. для вузов / А.И.

Белоусов, С.Б. Ткачев.- 2-е изд., стереотип.. - М. : Изд-во МГТУ им. Н.Э.

Баумана, 2002. - 744 с. - (Математика в техническом ун-те. Вып. ХIХ).

Ф.А.Новиков. Дискретная математика для программистов. –С-Пб.: Питер, 2002.

6.1.2 Дополнительная литература Асанов, М.О. Дискретная математика: графы, матроиды, алгоритмы: Учеб.

Расин. - Ижевск : Регулярная и хаот. динамика, 2001. - 288 с.

Иванов, Б.Н. Дискретная математика. Алгоритмы и программы: Учеб.

пособие / Б.Н. Иванов. - М. : Лаборатория Базовых Знаний, 2001. - 288 с.

Кузнецов, О.П. Дискретная математика для инженера: учебник / 4-е изд., CПб. : Лань, 2005. - 400 с.

6.2 Средства обеспечения освоения дисциплины 6.2.1 Методические указания и материалы по видам занятий 6.2.1.1 Методические указания к лабораторным занятиям Методические указания к проведению лабораторных работ. Разработка кафедры.

6.2.1.2 Методические указания к практическим занятиям Методические указания к проведению практических занятий. Разработка кафедры.

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

6.2.3 Контрольные вопросы для самопроверки 1. Понятия и аксиомы теории множеств.

2. Объединение. Равенство множеств.

3. Пересечение. Симметрическая разность.

4. Упорядоченность. Дополнение. Кольцо множеств.

5. Представление множеств и операций с ними в ЭВМ.

6. Декартовы произведения. Отношения.

7. Отношения эквивалентности.

8. Представление в ЭВМ отношений. Поле отношений.

9. Образ, прообраз множества.

10.Область определения.

11.Отображения множества.

12.Биективность. Аксиома выделения.

13.Аксиома степени.

14.Аксиома бесконечности.

15. Представление функций в ЭВМ.

16.Счетные множества.

17.Несчетные множества.

18.Свойства счетных и несчетных множеств.

19.Континуум. Континуальные множества.

20.Кардинальное число. Мощность.

21.Ординалы и трансфиниты.

22.Аксиома выбора. Вполне упорядоченные множества.

23.Аксиоматика теории множеств.

24.Алгебра Кантора.

25.Минимизация представления множеств.

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

27.Замыкания и подалгебры.

28.Алгебра термов.

29.Свойства операций.

30.Изоморфные алгебры.

31.Полугруппы.

32.Моноиды. Группы.

33.Свойства алгебр с одной операцией.

34.Алгебры с двумя операциями 35.Кольца. Области целостности. Поля.

36.Свойства алгебр с двумя операциями.

37.Ограниченные решетки.

38.Решетки с дополнением.

39.Частичный порядок в решетке.

40.Максимальные независимые подмножества.

41.Базисы. Ранг.

42.Жадный алгоритм.

43.Виды графов.

44.Подграфы.

45.Матрицы ассоциированные с графами.

46.Степени вершин.

47.Маршруты, цепи и циклы.

48.Расстояние между вершинами.

49.Диаметр и радиус графа.

50.Унарные и бинарные операции над графами.

51.Дополнение графа.

52.Удаление и добавление вершин.

53.Удаление и добавление ребер.

54.Отождествление вершин.

55.Расщепление вершин.

56.Объединение графов.

57.Пересечение графов. Кольцевая сумма.

58.Компоненты связности графов.

59.Точки сочленения. Мосты.

60.Вершинная и реберная связность.

61.Связность ориентированных графов.

62.Алгоритмы вычисления связности.

63.Внутренняя устойчивость. Вершинное число независимости.

64.Реберное число независимости.

65.Вершинное и реберное покрытие графа.

66.Внешняя устойчивость.

67.Вершинное и реберное число внешней устойчивости.

68.Циклы и разрезы 69.Матрицы циклов и разрезов.

70.Независимые множества циклов и разрезов (коциклов).

71.Эйлеровы циклы.

72.Ориентированные деревья.

73.Упорядоченные деревья.

74.Бинарные деревья.

75.Дереья сортировки.

76.Алгоритм поиска в дереве сортировки.

77.Алгебра логики 78.Булевы функции. Способы задания.

79.Булевы функции одной и двух переменных и их свойства.

80.Формулы булевой алгебры.

81.Основные законы булевой алгебры.

82.Эквивалентность формул. Принцип двойственности.

83.Конституенты единицы и нуля.

84.Разложение булевых функций по переменным.

85.Совершенные дизъюктивные (СДНФ) и совершенные конъюктивные нормальные формы (СКНФ).

86.Переход от СДНФ к СКНФ и наоборот.

87.Геометрическое представление булевых функций.

88.Системы элементарных булевых функций.

89.Определение функционально полной системы элементарных булевых функций.

90.Примеры функционально полных базисов.

91.Важнейшие замкнутые классы.

92.Теорема о функциональной полноте.

93.Понятие о реализации булевых функций.

94.Условная цена реализации по Квайну.

95.Основные понятия и определения: каноническая задача минимизации;

96.импликанта и простая импликанта;

97.сокращенная, тупиковая и минимальная формы;

98.операции элементарного и неполного склеивания; операция поглощения.

99.Метод Квайна – Мак-Клоски.

100.Метод карт Карнау или диаграмм Вейча.

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

102.Минимизация конъюктивных нормальных форм.

103.Проблема факторизации при упрощении функций.

104.Совместная минимизация систем функций. Минимизация функций в других базисах.

105.Схемы алгоритмов и потоков данных 106.Основные элементы схем алгоритмов.

107.Стандартные схемы алгоритмов.

108.Рекурсивные схемы алгоритмов.

109.Структурирование схем алгоритмов.

110.Функциональная эквивалентность схем алгоритмов.

111.Структуры и потоки данных.

112.Графовые представления.

113.Рекурсивное определение структур данных.

114.Обзор приложений дискретной математики 6.2.4 Критерии оценки знаний, умений и навыков Итоговыми формами контроля знаний, умений и навыков по дисциплине являются зачет и экзамен. Зачет выставляется при условии, если студент не имеет задолжностей по лабораторным работам и выполнил отчет по РГЗ. Экзамен проводится по билетам, которые включают два теоретических вопроса.

Оценка знаний студентов производится по следующим критериям:

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

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

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

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

7 Материально-техническое обеспечение дисциплины 7.1 Учебно-лабораторное оборудование Лабораторные работы проводятся в компьютерных классах кафедры ПОВТАС – ауд. №№ 14406 (а, б), 14422, 14423 или 14424.

техника»

Специальность: 230105.65 «Программное обеспечение вычислительной техники и автоматизированных систем»

Дисциплина: Дискретная математика Форма обучения: очная Учебный год 2006 / Рекомендована заседанием кафедры программного обеспечения вычислительной техники и автоматизированных систем протокол от « _ » _ 2006 г.

Ответственный исполнитель, заведующий кафедрой ПОВТАС Н.Соловьев « _ » _ 2006 г.

Исполнитель доцент кафедры ПОВТАС

СОГЛАСОВАНО:

Заведующий кафедрой ПОВТАС _ Н.Соловьев « » _ 200 г.

Председатель методической комиссии по специальности 230105.65 «Программное обеспечение вычислительной техники и автоматизированных систем»

Заведующий отделом комплектования научной библиотеки Начальник УСИТО