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

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

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

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

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

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

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

Занятие 7. Основы теории графов

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

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

2.Основные характеристики графов.

3.Графовые модели.

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

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

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

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

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

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

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

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

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

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

20

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

Занятия 8, 9. Элементы алгебры логики

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

1.Способы задания функций. Таблицы истинности.

2.Функционально полные системы.

3.Конъюнктивно и дизъюнктивно-нормальные формы.

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

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

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

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

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

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

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

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

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

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

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

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

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

21

Занятие 10. Элементы исчисления высказываний и исчисления предикатов

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

1.Формальные теории. Исчисление высказываний.

2.Предикаты первого порядка. Исчисление предикатов. Кванторы общности и существования.

3.Метод резолюции.

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

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

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

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

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

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

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

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

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

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

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

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

22

Занятие 11. Минимизация функция алгебры логики. Релейно-контактные схемы

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

1.Минимизация функций алгебры логики.

2.Минимизация БФ аналитическим способом.

3.Минимизация БФ методом Квайна – Мак-Класки.

4.Табличный способ минимизации на картах Карно.

5.Релейно-контактные схемы.

6.Полиномы Жегалкина.

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

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

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

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

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

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

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

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

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

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

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

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

23

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

Занятие 12. Понятие алгоритма, определение сложности алгоритма

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

1.Рекурсивные функции.

2.Формальные системы.

3.Временная и емкостная сложность алгоритма.

4.Сложность алгоритмов и программ. Структурная сложность алгоритма.

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

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

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

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

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

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

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

Занятие 13. Элементы математической логики, исчислений

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

1.Логические функции. Способы задания.

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

3.Формулы исчислений высказываний. Правила вывода.

4.Вычислительная сложность алгоритмов.

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

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

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

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

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

24

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

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

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

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

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

Тема 6. Конечные автоматы

Занятие 14. Способы задания конечны автоматов

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

1.Автомат Мили.

2.Автомат Мура.

3.Минимизация автоматов.

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

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

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

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

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

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

Занятие 15. Языки и грамматики

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

1.Классы формальных грамматик.

2.Сети Петри и их расширения.

25

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

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

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

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

1.Аляев Ю.А. Тюрин С.Ф. Дискретная математика и математическая ло

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

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

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

26

8.СЛОВАРЬ ТЕРМИНОВ

1.Множеством М называется объединение в единое целое определенных различимых объектов а, которые называются элементами множества. Множество можно описать, указав какое-нибудь свойство, присущее всем элементам этого множества. Определение Н. Бурбаки: Множество образуется из элементов, обладающих некоторыми свойствами и находящихся в некоторых отношениях между собой или с элементами других множеств. Указание, что множество состоит из различимых элементов a1,...,an и только из них условно записывается A ={a1,a2 ,...,an}. При-

надлежность элементов множеству (отношение принадлежности) задается с использованием символа . а А. Если элемент не принадлежит множеству, то пишут b A .

2.Объединением множеств А и В называется множество С, элементы которого принадлежат хотя бы одному из множеств А и В. Обозначается С = А В.

3.Пересечением множеств А и В называется множество С, элементы которого принадлежат каждому из множеств А и В. Обозначение С = А ∩ В.

4.Разностью множеств А и В называется множество, состоящее из элементов множества А, не принадлежащих множеству В. Обозначается С = А \ В.

5.Декартовым (прямым) произведением множеств А и В называется мно-

жество всех упорядоченных пар (a, b), где а А, b B.

A×B ={(a,b) a A; b B}.

6.Булеан – множество, элементами которого являются все подмножества, называется множеством подмножеств A или булеаном A (также степенью множества, показательным множеством или множеством частей).

7.Мощность множества – это обобщение понятия количества (числа элементов множества), которое имеет смысл для всех множеств, включая бесконечные. Мощность множества называется кардинальным числом, и

27

обозначается мощность такого множества A через |A|. Существуют большие, есть меньшие бесконечные множества, среди них счётное множество является самым маленьким.

8. Отношение – математическая структура, которая формально определяет свойства объектов и их взаимосвязи. Отношение A X ×Y называется функциональным, если все его элементы (упорядоченные пары) имеют разные первые координаты. Т.е. каждому элементу x X соответствует один и только один элемент y Y. Если функциональное отношение

A X ×Y всюду определено на множестве X , т.е. его область определения Do ( A) полностью совпадает с множеством X , то его называют функциональным отображением X в Y и обозначают X A→Y .

9.Комбинаторика – это раздел математики, посвященный задаче выбора и расположения элементов некоторого конечного множества в соответствии с заданными правилами.

10.Размещением без повторений из n элементов по k элементов k ≤ n называются k-элементные подмножества множества A, отличающиеся один от другого или самими элементами или их порядком.

11.Перестановками из n элементов называются множества из n элементов, отличающиеся один от другого порядком элементов.

12.Сочетаниями без повторений, содержащими k элементов, выбранных из n элементов заданного множества, называются всевозможные множества из k элементов, отличающиеся хоть одним элементов (порядок не учитывается), при этом все элементы различны

13.Граф – непустое множество Х и множество отношений R называется графом и обозначается G(X , R) .

14.Матрицей смежности орграфа D называется квадратная матрица A(D) = [aij] порядка n, у которой

a = 1,если (vi , v j ) X ; ij 0, если (vi , v j ) X .

28

15. Матрицей инцидентности орграфа D называется (n×m)-матрица B(D) =

16.Маршрутом в данном графе G называется конечная последовательность ребер вида {v0, v1}, {v1, v2}, …, {vm–1, vm–1} (обозначаемая также v0 → v1 → v2 → … → vm). Маршрут называется цепью, если все его ребра различны, и простой цепью, если все вершины тоже различны (кроме, может быть, начальной и конечной вершин). Цепь или простая цепь замкнуты, если начальная и конечная вершины совпадают. Замкнутая простая цепь, содержащая по крайней мере одно ребро, называется циклом.

17.Обхватом графа называется длина его кратчайшего цикла.

18.Путем в графе называют последовательность дуг (u1, u2, ...), в которой начало каждой очередной дуги совпадает с концом предыдущей. Длина пути – это число составляющих его дуг (ни о какой метрике в теории графов речи нет). Если в пути никакая дуга не встречается дважды, его называют простым. Такой путь называется путем Эйлера. В противном случае путь называется составным. Путь также называется простым, если он не проходит через одну вершину более одного раза. Такой путь, проходящий через все вершины графа, называется гамильтоновым.

19.Подграфом графа (Х, Г) называется граф (А, ГА), который получается выбором части вершин исходного графа с сохранением присутствующих связей между этими вершинами.

20.Частичным графом (Х, Г) называется граф, который получается выбором всех вершин исходного графа с потерей некоторых связей между ними.

21.Частичным подграфом (Х, Г) называется граф, который получается выбором части вершин исходного графа с сохранением лишь части присутствующих связей между этими вершинами.

29