Дискретная математика

1. Теория множеств

1.1. Множества и отношения. Множества и элементы множеств

1.2. Сравнение множеств

1.3. Операции над множествами

1.4. Диаграммы Эйлера-Венна

1.5. Табличный способ задания множеств

1.6. Свойства операций над множествами

1.7. Отношения

1.8. Специальные бинарные отношения

2. Математическая логика

2.1. Высказывания

2.2. Логические связки (операции) над высказываниями

2.3. Пропозициональные формулы

2.4. Булевы функции. Таблицы истинности

2.5. Булевы функции одной переменной

2.6. Булевы функции двух переменных

2.7. Существенные и несущественные переменные

2.8. Равносильные формулы. Основные равносильности

2.9. Основные тавтологии

2.10. Основные равносильности

2.11. Понятие двойственной функции

2.12. Некоторые двойственные функции

2.13. Элементарные канонические формы

2.14. Нормальные формы формул

2.15. Приведение формул к нормальным формам

2.16. Минимизация д.н.ф.

2.17. Полные системы функций. Полином Жегалкина

2.18. Функционально замкнутые классы функций

2.19. Понятие алгоритма. Описание машины Тьюринга

3. Теория графов

3.1. Основные понятия и определения

3.2. Смежность, инцидентность, степени

3.3. Способы задания графов

3.4. Подграфы. Операции на графах

3.5. Связность. Компоненты связности. Маршруты и пути

3.6. Эйлеровы и гамильтоновы графы

3.7. Деревья и леса

3.8. Цикломатическое число графа. Построение остовного дерева связного графа

4. Конечные автоматы

4.1. Понятие конечного детерминированного автомата

4.2. Способы задания автоматов

4.3. Эквивалентные состояния. Минимизация к.д.а

4.4. Алгоритм минимизации конечного автомата

4.5. Каноническая таблица. Канонические уравнения

4.6. Функциональные и логические элементы. Проектирование дискретных устройств

 

Рекомендуемая учебная литература для изучения теории:

  1. Ерусалимский Я.М. Дискретная математика, теория, задачи.—М.: Вуз. кн., 1998.
  2. Кузнецов О.П., Адельсон-Вельский Г.М. Дискретная математика для инженеров.—М.: Энергоатомиздат, 1988.
  3. Логинов Б.М. Лекции и упражнения по курсу "Введение в дискретную математику".—Калуга, 1998.
  4. Мангушева И.П. и др. Ограниченно детерминированные функции и конечные автоматы.—Саратов: Изд–во СГУ, 1997.
  5. Нефедов В.Н., Осипова В.А. Курс дискретной математики: Учебное пособие.—М.: Изд–во МАИ, 1992.
  6. Оре О. Теория графов.—М.: Наука, 1980.
  7. Яблонский С.В. Введение в дискретную математику.—М.: Наука, 1986.

Рекомендуемые пособия для практических занятий:

  1. Гаврилов Г.П., Сапоженко А.А. Сборник задач по дискретной математике.—М.: Наука, 1977.
  2. Лавров И.А., Максимова Л.Л. Задачи по теории множеств, математической логике и теории алгоритмов.—М.: Наука, 1975.
  3. Макаров Р. Н. Практические занятия по дискретной математике. Учебное пособие.—Новосибирск: СибГУТИ, 2001.—56 с.: ил.
  4. Насыров З.Х. Дискретная математика. Учебное пособие.—Обнинск: ИАТЭ, 1999.

*****

© 2009-2017 Банк лекций siblec.ru
Лекции для преподавателей и студентов. Формальные, технические, естественные, общественные, гуманитарные, и другие науки.