Наверх


А.Ахо, Дж.Хопкрофт, Дж.Ульман, 1979 (Rus)
Построение и анализ вычислительных алгоритмов


ОГЛАВЛЕНИЕ

1.  МОДЕЛИ ВЫЧИСЛЕНИЙ
   1.1 Алгоритмы и их сложность
   1.2 Машины с произвольным доступом к памяти
   1.3 Вычислительная сложность РАМ-программ
   1.4 Модель с хранимой программой
   1.5 Модификация РАМ
   1.6 Простейшая модель вычислений: машина Тьюринга
   1.7 Связь машин Тьюринга и РАМ
   1.8 Язык высокого уровня - Упрощенный Алгол
   Упражнения
   Замечания по литературе


2.  РАЗРАБОТКА ЭФФЕКТИВНЫХ АЛГОРИТМОВ
  
2.1 Структуры данных: списки, очереди и стеки
   2.2 Представления множеств
   2.3 Графы
   2.4 Деревья
   2.5 Рекурсия
   2.6 Разделяй и властвуй
   2.7 Балансировка
   2.8 Динамическое программирование
   2.9 Эпилог
   Упражнения
   Замечания по литературе


3.  СОРТИРОВКА И ПОРЯДКОВЫЕ СТАТИСТИКИ
  
3.1 Задача сортировки
   3.2 цифровая сортировка
   3.3 Сортировка с помощью сравнений
   3.4 Сортировка деревом - упорядочение с помощью O(N·LogN) сравнений
   3.5 Быстрая сортировка - упорядочение за среднее время O(N·LogN)
   3.6 Порядковые статистики
   3.7 Среднее время для порядковых статистик
   Упражнения
   Замечания по литературе


4.  СТРУКТУРЫ ДАННЫХ ДЛЯ ЗАДАЧ, КАСАЮЩИХСЯ РАБОТЫ С МНОЖЕСТВАМИ
  
4.1 Основные операции над множествами
   4.2 Метод расстановки
   4.3 Двоичный поиск
   4.4 Деревья двоичного поиска
   4.5 Оптимальное дерево двоичного поиска
   4.6 Простой алгоритм для нахождения объединения непересекающихся множеств
   4.7 Древовидные структуры для задач ОБЪЕДИНИТЬ - НАЙТИ
   4.8 Приложения и обобщения алгоритма ОБЪЕДИНИТЬ - НАЙТИ
 
  4.9 Схемы сбалансированных деревьев
   4.10 Словари и очереди с приоритетами
   4.11 Сливаемые деревья
   4.12 Сцепляемые очереди
   4.13 Разбиение
   4.14 Резюме
   Упражнения
   Замечания по литературе


5.  АЛГОРИТМЫ НА ГРАФАХ
   5.1 Остовное дерево наименьшей стоимости
   5.2 Метод поиска в глубину
   5.3 Двусвязность
   5.4 Поиск в глубину в ориентированном графе
   5.5 Сильная связность
   5.6 Задача нахождения путей
   5.7 Алгоритм транзитивного замыкания
   5.8 Алгоритм нахождения кратчайшего пути
   5.9 Задача о путях и умножение матриц
   5.10 Задача с одним источником
   5.11 Доминаторы в ориентированных ациклических графах: комбинирование понятий
   Упражнения
   Замечания по литературе


6.  УМНОЖЕНИЕ МАТРИЦ И СВЯЗАННЫЕ С НИМ ОПЕРАЦИИ
   6.1 Основные понятия
   6.2 Алгоритм Штрассена для умножения матриц
   6.3 Обращение матриц
   6.4 НВП-разложение матриц
   6.5 Приложения НВП-разложения
   6.6 Умножение булевых матриц
   Умножение
   Замечания по литературе


7.  БЫСТРОЕ ПРЕОБРАЗОВАНИЕ ФУРЬЕ И ЕГО ПРИЛОЖЕНИЯ
   7.1 Дискретное преобразование Фурье и обратное к нему
   7.2 Алгоритм быстрого преобразования Фурье
   7.3 БПФ при использовании битовых операций
   7.4 Произведение полиномов
   7.5 Алгоритм Шёнхаге-Штрассена для умножения целых чисел
   Упражнения
   Замечания по литературе


8.  АРИФМЕТИЧЕСКИЕ ОПЕРАЦИИ НАД ЦЕЛЫМИ ЧИСЛАМИ И ПОЛИНОМАМИ
   8.1 Аналогии между целыми числами и полиномами
   8.2 Умножение и деление целых чисел
   8.3 Умножение и деление полиномов
   8.4 Модульная арифметика
   8.5 Модульная арифметика полиномов т вычисление их значений
   8.6 Применение китайской теоремы об остатках
   8.7 Китайская теорема об остатках и интерполяция полиномов
   8.8 Наибольшие общие делители и алгоритм Евклида
   8.9 Асимптотически быстрый алгоритм нахождения НОД полиномов
   8.10 НОД целых чисел
   8.11 Еще раз о применении китайской теоремы об остатках
   8.12 Разреженные полиномы
   Упражнения
   Замечания по литературе


9.  АЛГОРИТМЫ ИДЕНТИФИКАЦИИ
   9.1 Конечные автоматы и регулярные выражения
   9.2 Распознавание образов, задаваемых регулярными выражениями
   9.3 Распознавание подцепочек
   9.4 Двусторонний детерминированный магазинный автомат
   9.5 Позиционные деревья и идентификаторы позиций
   Упражнения
   Замечания по литературе


10.  NP-ПОЛНЫЕ ЗАДАЧИ
   10.1 Недетерминированные машины Тьюринга
   10.2 Классы Р и NP
   10.3 Языки и задачи
   10.4 NP-полнгота задачи выполнимости
   10.5 Еще несколько NP-полных задач
   10.6 Задача с полиномиально ограниченной памятью
   Упражнения
  Замечания по литературе


11.  НЕКОТОРЫЕ ДОКАЗУЕМЫЕ ТРУДНОРАЗРЕШИМЫЕ ЗАДАЧИ
   11.1 Иерархии по сложности
   11.2 Иерархия по емкостной сложности для детерминированных машин Тьюринга
   11.3 Задача, требующая экспоненциальных времени и памяти
   11.4 Неэлементарная задача
   Упражнения
   Замечания по литературе


12.  НИЖНИЕ ОЦЕНКИ ЧИСЛА АРИФМЕТИЧЕСКИХ ОПЕРАЦИЙ
   12.1 Поля
   12.2 Еще раз о неветвящихся программах
   12.3 Матричная формулировка задачи
   12.4 Нижняя граница для числа умножений, связанная с рангом по строкам
   12.5 Нижняя граница для числа умножений, связанная с рангом по столбцам
   12.6 Граница для числа умножений, связанная с рассмотрением строк и столбцов
   12.7 Предварительная обработка
   Упражнения
   Замечания по литературе

  СПИСОК ЛИТЕРАТУРЫ
  ГЛОССАРИЙ
  ИМЕННОЙ УКАЗАТЕЛЬ
  ПРЕДМЕТНЫЙ УКАЗАТЕЛЬ



Наверх


М.О.Асанов, В.А.Баранский, В.В.Расин, 2001 (Rus)
Дискретная математика: Графы, Матроиды, Алгоритмы 


ОГЛАВЛЕНИЕ
ПРЕДИСЛОВИЕ

1.  ОСНОВНЫЕ ПОНЯТИЯ ТЕОРИИ ГРАФОВ
  
1.1 Основные определения
   1.2 Маршруты, связность, циклы и разрезы
   1.3 Ориентированные графы
   1.4 Матрицы, ассоциированные с графом


2.  ДЕРЕВЬЯ
   2.1 Леса, деревья, остовы
   2.2 Блоки и точки сочленения
   2.3 Число остовов в связном обыкновенном графе


3.  ОБХОДЫ ГРАФОВ
   3.1 Эйлеровы графы
   3.2 Гамильтоновы графы


4.  МАТРОИДЫ
   4.1 Полумодулярные решетки, условие Жордано-Дедекинда
   4.2 Конечномерные геометрические решетки и матроиды
   4.3 Основные понятия теории матроидов
   4.4 Различные аксиоматизации матроидов
   4.5 Двойственный матроид
   4.6 Жадный алгоритм
   4.7 Изоморфизмы матроидов
   4.8 Пространство циклов бинарного матроида
   4.9 Пространство циклов и пространство разрезов графа
   4.10 Монотонные полумодулярные функции. Индуцированный матроид
   4.11 Трансверсальные матроиды.
   4.12 Дизъюнктное объединение и сумма матроидов


5.  ПЛАНАРНОСТЬ
   5.1 Укладка графов, планарные графы
   5.2 Формула Эйлера для плоских графов
   5.3 Критерий планарности графа
   5.4 Двойственные графы


6.  РАСКРАСКИ
   6.1 Хроматические числа
   6.2 Хроматические многочлены
   6.3 Коэффициенты хроматических многочленов


7.  ВВЕДЕНИЯ В АЛГОРИТМЫ
   7.1 Алгоритмы и их сложность
   7.2 Запись алгоритмов
   7.3 Корневые и бинарные деревья
   7.4 Сортировка массивов


8.  ПОИСК В ГРАФЕ
   8.1 Поиск в глубину
   8.2 Алгоритм отыскания блоков и точек сочленения
   8.3 Алгоритм отыскания компонент сильной связности в орграфе
   8.4 Поиск в ширину
   8.5 Алгоритм отыскания эйлеровой цепи в эйлеровом графе


9.  ЗАДАЧА О МИНИМАЛЬНОМ ОСТОВЕ


10.  ПУТИ В СЕТЯХ
   10.1 Постановка задачи
   10.2 Общий случай. Алгоритм Форда-Беллмана
   10.3 Случай неотрицательных весов. Алгоритм Дейкстры
   10.4 Случай бесконтурной сети
   10.5  Задача о максимальном пути и сетевые графики
   10.6 Задача о maxmin-пути
   10.7 Задача о кратчайших путях между всеми парами вершин


11.  ЗАДАЧА О МАКСИМАЛЬНОМ ПОТОКЕ
   11.1 Основные понятия и результаты
   11.2 Алгоритм Флойда-Фалкерсона


12.  ПАРОСОЧЕТАНИЯ В ДВУДОЛЬНОМ ГРАФЕ
   12.1 Основные понятия
   12.2 Задача о наибольшем паросочетании. Алгоритм Хопкрофта-Карпа
   12.3 Задача о полном паросочетании. Алгоритм Куна
   12.4 Задача о назначениях. Венгерский алгоритм


13.  ЗАДАЧА КОММИВОЯЖЕРА
   13.1 Основные понятия
   13.2 Алгоритм отыскания гамильтоновых циклов
   13.3 Алгоритмы решения задачи коммивояжера с гарантированной оценкой точности
   13.4 Решение задачи коммивояжера методом ветвей и границ


ЛИТЕРАТУРА
ПРЕДМЕТНЫЙ УКАЗАТЕЛЬ





Наверх

А.А.Зыков,  1987 (Rus)
Основы  теории графов


ОГЛАВЛЕНИЕ
ВВЕДЕНИЕ

1. ИДЕНТИФИКАЦИЯ
   1.1 Обыкновенные графы
   1.2 Изоморфизм
   1.3 Инварианты
   1.4 Вычисление инвариантов
   1.5 Проблема изоморфизма
   1.6 Некоторые применения плотности и неплотности
   1.7 Алгоритмы для плотности, неплотности и изоморфизма
   1.8 Оценка плотности и неплотности
   1.9 Оптимальные и критические графы
   1.10 Проблемы восстановления


2. СВЯЗНОСТЬ
  
2.1 Маршруты
   2.2 Блоки
   2.3 Деревья
   2.4 Паросочетания и двудольные графы
   2.5 L-связные графы
   2.6 Взвешенные графы и метрики
   2.7 Мультиграфы
   2.8 Эйлеровы цепи и циклы
   2.9 Раскраски ребер


3. ЦИКЛОМАТИКА
   3.1 Каркасы и разрезы
   3.2 Пространство суграфов
   3.3 Матрицы инциденций, разрезов и циклов
   3.4 Графы с заданными разрезами и циклами
   3.5 Топологические графы
   3.6 Планарность
   3.7 Борьба с пересечениями
   3.8 Гипотеза Хадвигера
   3.9 Раскраски плоских триангуляций
   3.10 Совершенные графы


4. ОРИЕНТАЦИЯ
  
4.1 Конечные графы общего вида
   4.2 Достижимость
   4.3 Ядра
   4.4 Ориентируемость
   4.5 Транзитируемость

ДОБАВЛЕНИЕ. БУЛЕВЫ МЕТОДЫ В ТЕОРИИ ГРАФОВ
ЗАКЛЮЧЕНИЕ