Дискретные структуры (осенний семестр, 2003)

Вопросы к экзамену

1. Логика высказываний (высказывание, связки, истинность, тавтология и противоречие, эквивалентность пропозициональных форм, законы Де Моргана, полные системы связок). Понятие исчисления высказываний (понятие формальной аксиоматической теории; логический вывод, аксиомы и правила вывода).
2. Булевы функции (функция, порождаемая пропозициональной формой; построение формы, порождающей заданную функцию). Цифровые логические схемы (типы вентилей, синтез схем по таблицам истинности, дизъюнктивные нормальные формы).
3. Логика предикатов (высказывания с кванторами, истинность, отрицание высказываний с кванторами). Понятие исчисления предикатов (понятие формальной аксиоматической теории; логический вывод, аксиомы и правила вывода).
4. Методы доказательств. Структура формальных доказательств.  Прямое доказательство.  Доказательство с помощью контрпримеров.  Доказательство от противного.  Доказательство посредством контрапозиции.
5. Математическая индукция. Использование принципа математической индукции (провести доказательство какого-нибудь утверждения с использованием индукции).
6. Теория множеств (принадлежность, включение, операции над множествами, тождества, законы Де Моргана). Понятие булевой алгебры, примеры.
7. Отношения, бинарные отношения. Отношение эквивалентности на множестве. Порождаемое им разбиение на смежные классы, их свойства. Отношение порядка.
8. Формальные языки. Понятие конечного автомата, распознающего язык.
9. Комбинаторика (размещения, перестановки, сочетания, сочетания с повторениями). Бином Ньютона.
10. Графы (ориентированные/неориентированные, подграфы, степень вершины, теоремы о сумме степеней и о кол-ве нечетных вершин в графе).
11. Пути, цепи и контуры (определения, эйлеровы и гамильтоновы контуры - теоремы и следствия существования в ориентированных и неориентированных графах). Связность графов. Представление графов с помощью матриц инцидентности. Теорема о степени матрицы инцидентности.
12. Деревья и их свойства, каркасы (остовные деревья). Графы с весами. Алгоритм построения каркаса минимального веса (алгоритм Kruskal'а).
13. Бинарные деревья, полные бинарные деревья и их свойства. Организация хранения упорядоченных данных в виде бинарного дерева. Алгоритмы поиска, вставки и удаления узлов в деревьях.
14. Сбалансированные деревья (определение, преимущества организации хранения упорядоченных данных в виде бинарного сбалансированного дерева). Алгоритм балансировки.

Литература

1. Susana S. Epp. Discrete Mathematics. - 2nd ed. Brooks/Cole Publishing Company. 1995. - 802 p.
2. И.В. Романовский. Дискретный Анализ: Учебное пособие по прикладной математике и информатике. Физматлит. Невский диалект. Лаборатория базовых знаний. СПб и М. 2000 - 240 с.
3. Ф.А. Новиков. Дискретная математика для программистов: Учебник. - СПб; Питер, 2000. - 304 с.
4. В.Н. Нефедов, В.А. Осипов. Курс дискретной математики: Учебное пособие. -М.; Изд-во МАИ, 1992, - 264.
5. В.А. Горбатов. Фундаментальные основы дискретной математики. Информационная математика. - М. Наука. Физматлит, 2000.-544 с.
6. Д. Кук, Г. Бейз. Компьютерная математика: Пер. с англ.-М.: Наука, Гл. ред. физ.-мат. лит., 1990.-384 с.
7. С.В. Яблонский. Введение в дискретную математику: Учеб. пособие для вузов. 2-е изд, перераб. и доп.- М.: Наука, Гл. ред. физ.-мат. лит., 1986.-384 с.
8. С. Лавров. программирование. Математические основы, средства, теория. - СПб.: БХВ-Петербург, 2001.- 320 с.
9. С.В. Судоплатов, Е.В. Овчинникова. Элементы дискретной математики: Учебник. М.: ИНФРА-М, Новосибирск: Изд-во НГТУ, 2002. - 280 с. (Серия "Высшее образование").
10. М.О Асанов, В.А. Баранский, В.В. Расин. Дискретная математика: графы, матройды, алгоритмы. - Ижевск: НИЦ "Регулярная и хаотическая динамика", 2001, 288 с.
11. Я.М. Ерусалимский. Дискретная математика: теория, задачи, приложения. 4-е издание. - М.: Вузовская книга, 2001. - 280 с.
12. Б.Н. Иванов. Дискретная математика. Алгоритмы и программы: Учеб. пособие.- М.: Лаборатория Базовых Знаний, 2002 - 288 с.
13. О.Е. Акимов. Дискретная математика: логика, группы, графы. 2-е издание, доп.- М.: Лаборатория Базовых Знаний, 2003.
14. А. Шень. Программирование: теоремы и задачи.- М.: МЦНМО, 1995.
15. Н.К. Верещагин, А. Шень. Начала теории множеств. 2-е издание, испр.- М.: МЦНМО, 2002.
16. Э. Мендельсон. Введение в математическую логику.- М.: Наука, 1976.
17. О. Оре, Теория графов.- М.: Наука, 1980. - 336 с.