- •Курс лекций
- •По дискретной математике
- •(2 Семестр)
- •(Для студентов специальности «Прикладная математика», «Компьютерные системы и сети»)
- •Комбинаторика.
- •§1. Правила комбинаторики. Основные комбинаторные формулы.
- •Размещения.
- •Перестановки.
- •Сочетания.
- •§2. Свойства сочетаний. Бином Ньютона.
- •§3. Числа Фибоначчи. Рекуррентные соотношения.
- •§3. Производящие функции.
- •Теория графов. Введение
- •§1. Основные понятия и определения теории графов.
- •§2. Задачи, послужившие основой теории графов.
- •1. Задача о кенигсбергских мостах.
- •2. Задача о четырех красках.
- •§3. Алгоритмические задачи.
- •1. Задачи о кратчайших путях.
- •Алгоритм решения.
- •Обоснование алгоритма.
- •2. Алгоритм построения Эйлерова цикла.
- •Обоснование алгоритма.
- •3. Потоки на транспортных сетях.
- •Алгоритм Форда - Фалкерсона для нахождения потока наибольшей величины.
- •Обоснование алгоритма.
- •§4. Цикломатическое число графа. Деревья.
- •§5. Эйлерова характеристика. Плоские графы.
- •§6. Теорема о пяти красках.
- •Оценка хроматического числа плоского графа.
- •§7. Графы правильных многогранников.
- •Теория конечных автоматов Введение.
- •§1. Определение автомата Мили. Автомат Мура.
- •§2. Покрытие и эквивалентность. Морфизмы.
- •§3. Эквивалентные состояния автоматов.
- •§4. Процедура минимизации конечных автоматов.
- •§5. Машина Тьюринга.
- •§6. Не полностью описанные автоматы.
- •Алгоритмы и рекурсивные функции. Введение.
- •§1. Основные понятия и определения.
- •§2. Примитивно рекурсивные функции.
- •§3. Частично рекурсивные функции.
- •§4. Машины Тьюринга.
- •Список литературы.
- •2 Семестр
Список литературы.
1) Н. Я. Виленкин, Комбинаторика, «Наука», М., 1969.
2) М. Холл, Комбінаторика (пер. с англ.).
3) В. В. Белов, Е. М. Воробьев, В. Е. Шаталов, Теория графов, «Высшая школа», М., 1976.
4) О. Оре, Графы и их приложения, «Мир», 1965.
5) О. Оре, Теория графов (пер. с англ.), «Наука», 1968.
6) А. Гилл, Введение в теорию конечных автоматов, М., «Наука», 1966.
Учебное издание
курс лекций
по дискретной математике
2 Семестр
(для студентов, специальности «Прикладная математика», «Компьютерные системы и сети»)
Составители:
Вячеслав Викторович БАРАБАШ
Елена Юрьевна ЧАЛАЯ
Авторский оригинал-макет
Издательство Восточноукраинского национального университета имени Владимира Даля
Адрес издательства : 91034, г. Луганск, кв. Молодежный, 20а
Телефон: 8 (0642) 41-34-12, факс. 8 (0642) 41-31-60
E-mail: uni@snu.edu.ua http: www.snu.edu.ua