Лекции Русакова
Описание файла
PDF-файл из архива "Лекции Русакова", который расположен в категории "". Всё это находится в предмете "дискретная математика" из 3 семестр, которые можно найти в файловом архиве РТУ МИРЭА. Не смотря на прямую связь этого архива с РТУ МИРЭА, его также можно найти и в других разделах. Архив можно найти в разделе "лекции и семинары", в предмете "дискретная математика" в общих файлах.
Просмотр PDF-файла онлайн
Текст из PDF
МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТПРИБОРОСТРОЕНИЯ И ИНФОРМАТИКИРусаков Алексей МихайловичRusakovAM.ruЛекции по дисциплине «Дискретнаяматематика»Москва 2011Оглавление.Введение......................................................................................................... 6Глава 1. Теория множеств. ........................................................................... 71.01. Понятие множества.
Операции над множествами. ...................... 71.02. Свойства операций сложения и пересечения множеств. ............. 91.03. Принцип двойственности в теории множеств. ........................... 111.04. Отображения множеств. ................................................................
121.05. Разбиение на классы. Отношения эквивалентности. ................. 161.06. Упорядоченные множества. Изоморфизм теории множеств. ... 201.07. Счётные множества. Теорема Кантора. ....................................... 241.08. Аксиома выбора. Теорема Цермело. ............................................
321.09. Примеры задач и упражнений. ..................................................... 341.10. Задачи для самостоятельного решения. ...................................... 41Глава 2. Теория графов. .............................................................................. 482.01. Основные определения теории графов. ....................................... 482.02. Планарные графы. .......................................................................... 512.03. Локальные степени графа. Части и подграфы. ...........................
522.04. Бинарные отношения в теории графов. ....................................... 532.05. Матрицы смежности и инцидентности........................................ 542.06. Маршруты, цепи и простые цепи. ................................................ 572.07. Транспортные сети......................................................................... 592.08. Связность. Компоненты связности ..............................................
602.09. Матрицы достижимости и связности........................................... 622.10. Расстояние и протяжённость в графе........................................... 682.11. Деревья. ...........................................................................................
702.12. Помеченные графы. Перечисление помеченных деревьев. ...... 742.13. Задача поиска маршрутов в графе................................................ 772.14. Поиск оптимального пути (маршрута) ........................................ 782.15. Минимальные пути, маршруты в нагруженных графах. ........... 8122.16. Специальные пути в орграфах (маршруты в графах). ............... 852.17. Эйлеровы цепи и цепи.
.................................................................. 882.18. Гамильтовы циклы. ........................................................................ 902.19. Примеры задач и упражнений. ..................................................... 922.20. Задачи для самостоятельного решения. ...................................... 96Глава 3. Основы теории формальных грамматик. .................................
1023.01. Основные определения формальных грамматик. ..................... 1023.02. Основные операции формальных грамматик. .......................... 1053.03. Определение и способы описания формальных грамматик.... 1103.04. Классификация формальных языков по Хомскому. ................ 116Глава 4. Теория автоматов. ...................................................................... 1194.01. Основные понятия теории автоматов. ....................................... 1194.02. Способы задания автоматов. Таблица переходов. ...................
1224.03. Способы задания автоматов. Граф автомата. ........................... 1244.04. Способы задания автоматов. Матрица переходов и выходов. 1264.05. Машины Тьюринга и конечные автоматы. ............................... 1264.06. Машины Тьюринга с двумя выходами. ..................................... 1314.07.
Машины Тьюринга и линейно-ограниченные автоматы. ........ 1354.08. Автоматы с магазинной памятью и бесконтекстные языки. ... 1374.09. Бесконтекстные (контекстно-свободные) языки. ..................... 1414.10. Модель дискретного преобразователя Глушкова В. М. .......... 1434.11. Понятие об абстрактном автомате и индуцируемом имотображении. ...................................................................................................
1454.12. Автоматные отображения и события. ........................................ 1494.13. Представление событий в автоматах. ........................................ 1544.14. Регулярные языки и конечные автоматы. ................................. 1554.15. Основной алгоритм синтеза конечных автоматов.................... 1574.16. Правила подчинения мест в регулярных выражениях............. 16034.17. Правила построения основного алгоритма синтеза конечныхавтоматов.......................................................................................................... 1624.18.
Автомат Мили. ............................................................................. 1674.19. Автомат Мура. .............................................................................. 169Глава 5. Теория булевых функций. ......................................................... 1705.01. Связь булевых функций и схем из функциональных элементови контактных схем. ......................................................................................... 1705.02.
Основные понятия булевых функций. ....................................... 1745.03. Законы двойственности. .............................................................. 1815.04. Основные свойства булевых функций. ...................................... 186Глава 6. Элементы теории доказательств. .............................................. 1896.01. Естественная дедукция. ...............................................................
1906.02. Метод математической индукции. ............................................. 1946.03. Доказательство неравенств методом математической индукции.Неравенство Коши-Буняковского. ................................................................ 1956.04. Примеры задач и упражнений. ................................................... 1986.05. Задачи для самостоятельного решения. .................................... 201Глава 7. Элементы комбинаторики. ........................................................
2047.01. Основные понятия комбинаторики. ........................................... 2047.02. Декартово произведение множеств............................................ 2087.03. Задачи для самостоятельного решения. .................................... 212Глава 8. Основная часть: практическая работа студентов.................... 213Практическое занятие №1. Разработка синтаксических анализаторовдля регулярных языков. ...................................................................................... 2138.01. Общие указания к выполнению практической работы. ........... 2138.02.
Цель работы .................................................................................. 2148.03. Постановка задачи ....................................................................... 2148.04. Последовательность выполнения. .............................................. 2178.05. Методический пример. ................................................................
21848.06. Контрольная распечатка. ............................................................. 2208.07. Замечания. ..................................................................................... 2218.08. Отчет по практической работе. .................................................. 2248.09. Контрольные вопросы ................................................................. 2248.10.
Варианты заданий. ....................................................................... 225Домашняя работа №1. По всей теории ................................................... 228Домашняя работа №2. Способы задания графов ................................... 229Глава 9. Дополнительная часть: практическая работа студентов ........
275Практическое занятие №1. Работа с регулярными выражениями наоснове PERL ........................................................................................................ 2759.01. Общие указания к выполнению практической работы. ........... 2759.02. Цель работы .................................................................................. 2759.03. Теоретические сведения. .............................................................
