Дискретная математика УМК

Контрольные вопросы

1.Основные принципы и теоремы комбинаторики.

2.Размещения, перестановки и сочетания (без повторений).

3.Размещения, перестановки и сочетания (с повторениями).

4.Биномиальные и полиномиальные коэффициенты.

Тема 3. Элементы теории графов

Графы, их вершины и ребра. Графы и бинарные отношения. Изображение графов. Матрица инцидентности графа. Матрица смежности графа. Подграфы. Степени вершин графа. Маршруты, цепи и циклы. Планарные графы. Теоремы Эйлера и Куратовского. Эйлеровы графы. Условия, при которых граф является эйлеровым. Раскраска графов. Структуры данных для представления графа. Представление графа списком смежности. Обход графа. Обход графа по глубине. Обход графа по ширине. Ориентированные графы. Определение орграфа. Маршруты и связность в орграфах. Упорядоченные орграфы и обходы. Сети. Потоковые модели. Сетевые графики.

Основные термины

Граф, ориентированный неориентированный граф, граф Эйлера, граф Гамильтона, связность графа, раскраска графа, сети, потоковые модели.

Контрольныевопросы

1.Понятие графа. Ориентированные и неориентированные графы.

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

3.Степени вершин графа. Маршруты, цепи и циклы.

4.Планарные графы.

5.Теоремы Эйлера и Куратовского. Эйлеровы графы.

6.Условия, при которых граф является эйлеровым. Раскраска графов.

7.Обход графа. Обход графа по глубине. Обход графа по ширине.

8.Ориентированные графы. Определение орграфа. Маршруты и связность в орграфах. Упорядоченные орграфы и обходы.

10

9.Сети. Потоковые модели.

10.Сетевые графики.

Тема 4. Основные положения математической логики и исчисления

Высказывания и логические связки. Булевы функции (БФ). Способы задания БФ. Функциональный базис, композиция функций. Формулы, эквивалентные преобразования формул. Элементы булевой алгебры. Специальные разложения БФ. СДНФ и СКНФ. Минимизация булевых функций. Схемы из логических элементов. Связь сложности схем и сложности формул. Минимизация БФ аналитическим способом. Нормальные формы БФ. Минимизация БФ методом Квайна – Мак-Класки. Табличный способ минимизации на картах Карно. Функциональная полнота систем булевых функций. Замечательные классы БФ. Теорема о функциональной полноте. Примеры функцио- нально-полных базисов. Построение схем в универсальных базисах. Релейноконтактные схемы. Полиномы Жегалкина. Функции k-значной логики. Предикаты, операции над ними. Формулы логики предикатов. Исчисление предикатов. Кванторы существования и всеобщности. Правила вывода. Правила резолюции. Теоремы Геделя.

Основные термины

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

Контрольные вопросы

1.Логические функции.

2.Функционально полный набор функций.

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

4.Минимизация логических функций.

5.Исчисление высказываний.

11

6.Исчисление предикатов первого порядка.

7.Правила логического вывода.

8.Теоремы Геделя.

Тема 5. Алгоритмы и их сложность

Основные понятия теории алгоритмов. Машины Тьюринга. Понятие об алгоритмической разрешимости и неразрешимости задач. Функции сложности алгоритмов. Методы построения эффективных алгоритмов. Метод разбиения и рекурсии. Сложность рекурсивных алгоритмов.

Основные термины

Алгоритм, машина Тьюринга, алгоритмическая разрешимость, рекурсивные функции, временная сложность алгоритмов.

Контрольные вопросы

1.Определение алгоритма.

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

3.Алгоритмическая разрешимость и неразрешимость задач.

4.Рекурсивные (частично рекурсивные) функции.

5.Сложность алгоритмов и программ.

Тема 6. Конечные автоматы и регулярные языки

Основные понятия. Автомат Мили. Автомат Мура. Способы задания автоматов. Языки и грамматика. Контекстно-свободные языки. Деревья вывода. Эквивалентность состояний. Алгоритм разбиения состояний. Анализ автоматов. Сети автоматов. Сети Петри и их расширения.

Основные термины:

Конечный автомат, автомат Мили, автомат Мура, формальные языки и формальные грамматики, деревья вывода, сети автоматов, сети Петри.

12

Контрольные вопросы

1.Понятие конечного автомата.

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

3.Формальные языки. Классификация языков.

4.Контекстно-свободные языки.

5.Формальные грамматики.

6.Сети автоматов.

7.Сети Петри.

8.Расширения сетей Петри.

13

6. СПИСОК РЕКОМЕНДУЕМОЙ ЛИТЕРАТУРЫ

Основная литература

1.Данилов В.Г., Дубнов В.Л., Лакерник А.Р., Райцин А.М. Дискретная математика. – М.: Телеком, 2008.

2.Кузнецов О.П. Дискретная математика для инженера. – М.: Лань, 2007.

3.Новиков Ф.А. Дискретная математика. – СПб: Питер, 2008.

4.Тишин В.В. Дискретная математика в примерах и задачах. – СПб.: БХВ-Петербург, 2008.

5.Эвнин А.Ю. Задачник по дискретной математике. – СПб.: Питер, 2012.

Дополнительная литература

1.Аляев Ю.А. Тюрин С.Ф. Дискретная математика и математическая логика. – М.: Финансы и статистика, 2006.

2.Андерсон Дж. Дискретная математика и комбинаторика. – М.: Виль-

ямс, 2004.

3.Белоусов А.И., Ткачев С.Б. Дискретная математика. – М.: МГТУ им. Н.Э. Баумана, 2004.

4.Гаврилов Г.П. Сапоженко А.А. Задачи и упражнения по курсу дискретной математики. – М.: Физматлит, 2005.

5.Горбатов В.А. Фундаментальные основы дискретной математики. Информационная математика. – М.: Наука; Физматлит, 2000.

6.Кормен Т.Х. [и др.]. Алгоритмы: построение и анализ. – М.: Вильямс, 2005.

7.Кузнецов О.П., Адельсон-Вельский Г.М. Дискретная математика для инженера. – М., 1988.

8.Лавров И.А., Максимова Л.Л. Задачи по теории множеств, математической логике и теории алгоритмов: учеб. пособие. – М.: Наука, 1984.

14

9.Maкоха А.Н., Сахнюк П.А., Червяков Н.И. Дискретная математика: учеб. пособие. – М.: Физматлит, 2005.

10.Оре О. Теория графов. – М.: Наука, 1980.

11.Питерсон Дж. Теория сетей Петри и моделирование систем. – М.:

Мир, 1984.

12.Сачков В.Н. Введение в комбинаторные методы дискретной математики. – М.: Изд-во МЦНМО, 2004.

13.Судоплатов С.В., Овчинникова Е.В. Элементы дискретной математики: учебник. – М.: ИНФРА-М, Новосибирск: Изд-во НГТУ, 2002.

14.Форд Л, Фалкерсон Д. Потоки в сетях. – М.: Мир, 1966.

15.Яблонский С.В. Введение в дискретную математику: учеб. пособие. – М.: Высшая школа, 2006.

15

7. ПЛАНЫ СЕМИНАРСКИХ ЗАНЯТИЙ

Тема 1. Введение. Множества, отношения, функции

Занятие 1. Определение множества. Основные операции над множеством

Вопросыдляобсуждения

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

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

Основнаялитература

1.Новиков Ф.А. Дискретная математика. – СПб: Питер, 2008.

2.Кузнецов О.П. Дискретная математика для инженера. – М.: Лань, 2007.

3.Тишин В.В. Дискретная математика в примерах и задачах. – СПб.: БХВПетербург, 2008.

Дополнительная литература

1.Андерсон Дж. Дискретная математика и комбинаторика. – М.: Вильямс, 2004.

2.Лавров И.А., Максимова Л.Л. Задачи по теории множеств, математической логике и теории алгоритмов: учеб. пособие. – М.: Наука, 1984.

Занятие 2. Отношения над множествами

Вопросыдляобсуждения

1.Отношения. Свойства отношений.

2.Способы задания отношений.

3.Классификация отношений.

4.Отношения на базах данных.

Основнаялитература

1.Новиков Ф.А. Дискретная математика. – СПб: Питер, 2008.

2.Кузнецов О.П. Дискретная математика для инженера. – М.: Лань, 2007.

16

3.Тишин В.В. Дискретная математика в примерах и задачах. – СПб.: БХВПетербург, 2008.

Дополнительнаялитература

1.Андерсон Дж. Дискретная математика и комбинаторика. – М.: Вильямс, 2004.

2.Лавров И.А., Максимова Л.Л. Задачи по теории множеств, математической логике и теории алгоритмов: учеб. пособие. – М.: Наука, 1984.

Тема 2. Комбинаторика

Занятие 3. Основные операции комбинаторики

Вопросыдляобсуждения

1.Перестановки.

2.Число сочетаний, число размещений и число перестановок.

3.Основные теоремы комбинаторики.

Основнаялитература

1.Новиков Ф.А. Дискретная математика. – СПб: Питер, 2008.

2.Данилов В.Г., Дубнов В.Л., Лакерник А.Р., Райцин А.М. Дискретная математика. – М.: Телеком, 2008.

3.Тишин В.В. Дискретная математика в примерах и задачах. – СПб.: БХВПетербург, 2008.

Дополнительнаялитература

1.Андерсон Дж. Дискретная математика и комбинаторика. – М.: Вильямс, 2004.

2.Галкина В.А. Дискретная математика: комбинаторные методы оптимизации. – М.: Гелиос АРВ, 2003.

3.Лавров И.А., Максимова Л.Л. Задачи по теории множеств, математической логике и теории алгоритмов: учеб. пособие. – М.: Наука, 1984.

17

Занятие 4. Множества и элементы комбинаторики

Вопросыдляобсуждения

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

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

3.Отношения и операции.

4.Способы задания отношений.

5.Основные операции комбинаторики.

6.Теоремы комбинаторики.

Основнаялитература

1.Данилов В.Г., Дубнов В.Л., Лакерник А.Р., Райцин А.М. Дискретная математика. – М.: Телеком, 2008.

2.Кузнецов О.П. Дискретная математика для инженера. – М.: Лань, 2007.

3.Новиков Ф.А. Дискретная математика. – СПб: Питер, 2008.

4.Тишин В.В. Дискретная математика в примерах и задачах. – СПб.: БХВПетербург, 2008.

5.Эвнин А.Ю. Задачник по дискретной математике. – СПб.: Питер, 2012.

Дополнительнаялитература

1.Андерсон Дж. Дискретная математика и комбинаторика. – М.: Вильямс, 2004.

2.Галкина В.А. Дискретная математика: комбинаторные методы оптимизации. – М.: Гелиос АРВ, 2003.

3.Лавров И.А., Максимова Л.Л. Задачи по теории множеств, математической логике и теории алгоритмов: учеб. пособие. – М.: Наука, 1984.

Тема 3. Элементы теории графов

Занятие 5. Способы задания графов

Вопросы для обсуждения

1. Неориентированные графы. Матрицы смежности и инцидентности.

18

2.Ориентированные графы. Матрицы смежности и инцидентности.

3.Степени вершин графа.

4.Частичные графы, подграфы.

Основная литература

1.Данилов В.Г., Дубнов В.Л., Лакерник А.Р., Райцин А.М. Дискретная математика. – М.: Телеком, 2008.

2.Кузнецов О.П. Дискретная математика для инженера. – М.: Лань, 2007.

3.Новиков Ф.А. Дискретная математика. – СПб: Питер, 2008.

4.Тишин В.В. Дискретная математика в примерах и задачах. – СПб.: БХВПетербург, 2008.

5.Эвнин А.Ю. Задачник по дискретной математике. – СПб.: Питер, 2012.

Дополнительная литература

1.Горбатов В.А. Фундаментальные основы дискретной математики. Информационная математика. – М.: Наука; Физматлит, 2000.

2.Оре О. Теория графов. – М.: Наука, 1980.

3.Форд Л, Фалкерсон Д. Потоки в сетях. – М.: Мир, 1966.

Занятие 6. Пути на графах. Потоковые модели

Вопросы для обсуждения

1.Графы Эйлера, Гамильтона.

2.Обход по графу.

3.Общие сведения о потоковых моделях.

4.Задачи теории потоков.

Основная литература

1.Данилов В.Г., Дубнов В.Л., Лакерник А.Р., Райцин А.М. Дискретная математика. – М.: Телеком, 2008.

2.Кузнецов О.П. Дискретная математика для инженера. – М.: Лань, 2007.

3.Новиков Ф.А. Дискретная математика. – СПб: Питер, 2008.

19