Теория графов

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