Maкоха А. Н., Сахнюк П. А., Червяков Н. И. Дискретная математика: Учеб. пособие. - М., 2005. - 368 с.
Учебное пособие содержит как традиционные разделы дискретной математики (введение в теорию графов, нормальные формы логических функций и синтез комбинационных схем, конечные автоматы), так и нетрадиционный раздел — алгебраические и теоретико-числовые основы модулярного кодирования. Книга носит скорее практический, нежели теоретический характер. Во всех главах имеется достаточное количество примеров, иллюстраций, схем и таблиц, позволяющих неформально усвоить соответствующий материал. К каждой главе приводится список вопросов и задач, направленных на осознанное закрепление основных понятий и алгоритмов. Пособие создано на основе лекций, практических и лабораторных занятий, проведенных авторами в Ставропольском военном институте связи ракетных войск и в СГУ на различных специальностях. Для студентов и преподавателей вузов, а также инженеров и специалистов, работающих в области прикладной математики и телекоммуникаций.
ОГЛАВЛЕНИЕ
Предисловие................................................................................5
Глава 1. Введение в теорию графов..................................9
1.1. Основные понятия теории графов. Изоморфизм графов ... 10
1.2. Связность графов................................................................16
1.3. Способы машинного представления графов..........................19
1.4. Деревья и их основные свойства..........................................24
1.5. Обходы графа и алгоритмы оптимизации путей на графе . . 31
1.6. Задача о кратчайшем остовном дереве................................45
1.7. Циклические графы и их свойства......................................53
1.8. Потоки в сетях....................................................................64
Вопросы и упражнения к главе 1..............................................83
Глава 2. Нормальные формы логических функций и
синтез комбинационных схем................................................95
2.1. Логические операции над высказываниями и их свойства . ....................96
2.2. Формулы и функции алгебры логики. Закон двойственности............. 101
2.3. Совершенные дизъюнктивные и конъюнктивные нормальные формы булевых функций..............................................107
2.4. Полнота и замкнутость системы булевых функций. Представление о классах Поста..................................................110
2.5. Минимизация булевых функций..........................................114
2.6. Синтез комбинационных схем..............................................128
2.7. Приложения алгебры логики к синтезу и анализу функциональных устройств комбинационного типа..........................143
Вопросы и упражнения к главе 2..............................................177
Глава 3. Конечные автоматы..............................................184
3.1. Основные понятия теории автоматов..................................185
3.2. Автоматы Мили и Мура. Частичные автоматы....................192
3.3. Классы эквивалентных состояний автомата и алгоритмы их нахождения........................................................................197
3.4. Эквивалентность автоматов и теорема о минимальном автомате Мили..........................................................................205
3.5. Минимизация частичных автоматов....................................211
3.6. Основные этапы проектирования автоматов........................215
3.7. Применение теории автоматов к анализу и синтезу типовых функциональных узлов цифровой техники..........................230
3.8. Сети из автоматов..............................................................260
3.9. Сети Петри и искусственные нейронные сети......................268
Вопросы и упражнения к главе 3..............................................292
Глава 4. Алгебраические и теоретико-числовые основы
модулярного кодирования ....................................................312
4.1. Кодирование данных в системе остаточных классов............312
4.2. Степенные вычеты и вычисления в конечных полях............337
4.3. Связь между нейронными сетями и модулярными кодами. . 353
Вопросы и упражнения к главе 4..............................................357
Список литературы....................................................................366
