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