Лекции Русакова (1021002)
Текст из файла
МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТПРИБОРОСТРОЕНИЯ И ИНФОРМАТИКИРусаков Алексей Михайлович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. Теоретические сведения. .............................................................
Характеристики
Тип файла PDF
PDF-формат наиболее широко используется для просмотра любого типа файлов на любом устройстве. В него можно сохранить документ, таблицы, презентацию, текст, чертежи, вычисления, графики и всё остальное, что можно показать на экране любого устройства. Именно его лучше всего использовать для печати.
Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
