|
Оглавление
 Предисловие Глава I. Элементы комбинаторики § 1. Комбинаторные объекты и комбинаторные числа §2. Формула включения-исключения. Производящие функции и возвратные последовательности Глава П. Графы и сети §1. Элементы графа. Подграфы. Способы задания графов §2. Геометрическая реализация графов. Верхняя оценка числа неизоморфных графов с та рёбрами §3. Деревья. Характеристические свойства деревьев §4. Верхняя оценка числа неизоморфных корневых деревьев с т рёбрами §5. Теорема Кэли о числе деревьев с занумерованными вершинами §6. Двудольные графы. Паросочетания и трансверсали. Теорема Холла §7. Сети. Потоки в сетях. Теорема Форда-Фалкерсона Глава III. Булевы функции и формулы §1. Булевы функции. Элементарные булевы функции §2. Формулы и функции, реализуемые формулами. Простейшие эквивалентности §3. Разложение булевых функций. Дизъюнктивные нормальные формы §4. Полнота систем булевых функций. Представление булевых функций полиномами Жегалкина §5. Функции k-значной логики Глава IV. Предикаты
§1. Высказывания, предикаты, кванторы. Геометрический смысл кванторов
§2. Модель, сигнатура модели, формулы в модели. Свободные и связанные переменные
§3. Истинность формулы в модели, на множестве. Тождественно истинные формулы
§4. Эквивалентность формул. Правила преобразования формул с кванторами
§5. Приведённые формулы
§6. Нормальные формулы
Глава V. Схемы из функциональных элементов. Синтез и оценки сложности схем
§ 1. Схемы из функциональных элементов в базисе {, V,- }
§2. Синтез схем с использованием совершенных д.н.ф
§3. Метод Шеннона
§4. Асимптотически оптимальный метод синтеза схем (метод Лупанова)
§5. Мощностной метод получения нижней оценки для сложности схем
Глава VI. Тесты
§ 1. Полные диагностические тесты для таблиц. Оценки длины тестов
§2. Тесты для схем. Построение минимальных тестов методом
Яблонского
§3. Верхние оценки длины единичных тестов для схем
§4. Синтез легкотестируемых схем
Глава VII. Ограниченно-детерминированные функции и реализация их автоматами
§ 1. Детерминированные и ограниченно-детерминированные функции
§2. Способы задания ограниченно-детерминированных функций
§3. Схемы автоматов из функциональных элементов и элементов задержки
Глава VIII. Алгоритмы
§ 1. Алгоритмы. Машины Тьюринга. Задание машины системой команд
§2. Композиции машин. Тезис Тьюринга
§3. Проблема самоприменимости. Теорема о самоприменимости
Глава IX. Кодирование
§ 1. Алфавитное кодирование. Разделимые коды. Свойство префикса
§2. Неравенство Крафта-Макмиллана
§3. Коды с минимальной избыточностью. Оптимальное кодирование Хаффмена
§4. Самокорректирующиеся коды. Коды Хэмминга
§5. Геометрические свойства самокорректирующихся кодов. Оценки Хэмминга и Гильберта
Глава X. Дискретные экстремальные задачи
§ 1. Задача на покрытие. Точное решение задачи на покрытие
§2. Градиентный алгоритм поиска приближённого решения. Оценка сложности градиентного покрытия
§3. Задача о минимальном остовном дереве
§4. Поиск кратчайшего и надёжного путей в графе
§5. Точное решение задачи на покрытие методом динамического программирования
§6. Приближённое решение задачи об упаковке в контейнеры
§7. Классы Р и NP. Полиномиальная сводимость задач
|