Книги серии: Высшее образование: Бакалавриат (1)

Аннотация

Учебное пособие написано на основе семестрового курса лекций по дискретной математике,читаемого студентам факультета ВМК МГУ им.М.В.Ломоносова.Оно включает в себя введение в такие разделы дискретной математики,как булевы функции,графы,коды,автоматы,реализация булевых функций схемами.Ряд вопросов,представленных в пособии,отсутствует в известном учебнике С.В.Яблонского"Введение в дискретную математику"или изложен по-другому.Пособие может использоваться для чтения курса"Дискретная математика",а также для самостоятельного изучения основ дискретной математики.
Оглавление
Введение
Глава I. Функции алгебры логики
§ 1. Функции алгебры логики. Равенство функций. Тождества для элементарных функций
§ 2. Теорема о разложении функции алгебры логики по переменным. Теорема о совершенной дизъюнктивной нормальной форме
§ 3. Полные системы.
§ 4. Теорема Жегалкина о представимости функции алгебры логики полиномом
§ 5. Понятие замкнутого класса.
§ 6. Двойственность. Класс самодвойственных функций, его замкнутость
§ 7. Класс монотонных функций, его замкнутость
§ 8. Лемма о несамодвойственной функции
§ 9. Лемма о немонотонной функции
§ 10. Лемма о нелинейной функции
§ 11. Теорема Поста о полноте системы функций алгебры логики
§ 12. Теорема о максимальном числе функций в базисе алгебры логики
§ 13. Теорема о предполных классах
§ 14. k-значные функции.
Глава II. Основы теории графов
§ 15. Основные понятия теории графов. Изоморфизм графов. Связность
§ 16. Деревья. Свойства деревьев
§ 17. Корневые деревья. Верхняя оценка их числа
§ 18. Геометрическая реализация графов.
§ 19. Планарные графы. Формула Эйлера
§ 20. Доказательство непланарности графов К5 и К3,3. Теорема Понтрягина - Куратовского
§ 21. Теорема о раскраске планарных графов в пять цветов
Глава III. Основы теории кодирования
§ 22. Алфавитное кодирование. Алгоритм распознавания взаимной однозначности алфавитного кодирования. Теорема Маркова
§ 23. Неравенство Макмиллана
§ 24. Существование префиксного кода с заданными длинами кодовых слов
§ 25. Оптимальные коды, их свойства
§ 26. Теорема редукции
§ 27. Коды с исправлением r ошибок.
§28. Коды Хэмминга.
Глава IV. Основы теории управляющих систем
§ 29. Схемы из функциональных элементов. Реализация функций алгебры логики схемами
§ 30. Сумматор. Верхняя оценка сложности сумматора. Вычитатель §31. Метод Карацубы построения схемы для умножения, верхняя оценка ее сложности
§ 32. Дешифратор. Асимптотика сложности дешифратора. Верхняя оценка сложности реализации произвольной функции алгебры логики
§ 33. Мультиплексор и универсальный многополюсник. Оценки их сложности. Метод Шеннона
Глава V. Основы теории конечных автоматов
§ 34. Автоматы и способы их задания. Единичная задержка
§ 35. Схемы из функциональных элементов и элементов задержки. Автоматность осуществляемых ими отображений
§ 36. Моделирование автоматной функции схемой из функциональных элементов и элементов задержки
§ 37. Теорема Мура. Теорема об отличимости состоян