<center>
<h3>
Т.Ч. Ху,
М.Т. Шинг<br>
<br>
КОМБИНАТОРНЫЕ АЛГОРИТМЫ
</h3>
<p>
<i>перевод с английского</i>:
В.Е.Алексеева, Н.Ю.Золотых,
С.В.Сорочана,  В.А.Таланова,
В.Н.Шевченко,  А.А.Яценко

</center>



<p>
Книга представляет собой перевод второго расширенного и дополненного
издания распространенного на Западе учебника американских математиков
Т.Ч.Ху и М.Т.Шинга. Первое издание (1982) на русский
язык не переводилось. 
<p>
Первый автор хорошо известен отечественному читателю по переводу его
замечательной книги <i>Целочисленное программирование и потоки в сетях</i>, 
сыгравшей большую роль в знакомстве отечественного читателя с
новыми разделами дискретной математики.
<p>
Книга посвящена алгоритмам дискретной математики
(кратчайшие пути и потоки в сетях, динамическое программирование, поиск с
возвратом, бинарные деревья, эвристические алгоритмы, матричное умножение,
NP-полные задачи, локальные алгоритмы, деревья Гомори-Ху) и может
использоваться как учебник по курсу <i>Анализ и разработка алгоритмов</i> и
как справочник. Весь материал изложен в классических традициях учебной
литературы. Многие результаты на русском языке излагаются впервые.
<p>
Для студентов, аспирантов и научных работников, специализирующихся по
дискретной математике и информатике.

<p>
330 с., обложка, 268 илл.

<p>
Чтобы оценить дух книги, вы можете скачать <a href="contents.pdf">Оглавление и предисловие</a>

<p>
По вопросам приобретения книги обращайтесь на кафедру МЛиВА ф-та ВМК
Нижегородского госуниверситета им. Н.И. Лобачевского (Нижний Новгород,
пр. Гагарина, 23, корп. 2, ауд. 219, 223) или по e-mail zny@uic.nnov.ru


<h1>
Оглавление
</h1>

<ul>
<li> Предисловие к русскому изданию
<li> Предисловие к первому изданию
<li> Предисловие ко второму изданию
<p>
<li> Глава 1. Кратчайшие пути в графах
<ul>
<li> 1.1. Терминология теории графов
<li> 1.2. Кратчайший путь
<li> 1.3. Кратчайшие пути между всеми парами узлов
<li> 1.4. Алгоритм декомпозиции
<li> 1.5. Ациклические сети
<li> 1.6. Кратчайшие пути в общей сети
<li> 1.7. Минимальное остовное дерево
<li> 1.8. Поиск в ширину и поиск в глубину
<li> Упражнения
<li> Литература
<li> Ответы
</ul>
<p>
<li> Глава 2. Максимальные потоки
<ul>
<li> 2.1. Максимальные потоки
<li> 2.2. Алгоритмы нахождения максимального потока
<ul>
<li> 2.2.1. Алгоритм Форда-Фалкерсона
<li> 2.2.2. Алгоритм Карзанова
<li> 2.2.3. MPM-алгоритм
<li> 2.2.4. Анализ алгоритмов
</ul>
<li> 2.3. Многотерминальные минимальные потоки
<ul>
<li> 2.3.1. Реализуемость (Гомори и Ху [12])
<li> 2.3.2. Анализ (Гомори и Ху [12])
<li> 2.3.3. Синтез (Гомори и Ху [12])
<li> 2.3.4. Многопродуктовые потоки
</ul>
<li> 2.4. Потоки с минимальной стоимостью
<li> 2.5. Приложения
<ul>
<li> 2.5.1. Множества различных представителей
<li> 2.5.2. PERT-метод
<li> 2.5.3. Оптимальное коммуникационное остовное дерево
</ul>
<li> Упражнения
<li> Литература
<li> Ответы
</ul>
<p>
<li> Глава 3. Динамическое программирование 
<ul>
<li> 3.1. Введение
<li> 3.2. Задача о рюкзаке
<li> 3.3. Задача о двумерном рюкзаке
<li> 3.4. Алфавитные деревья минимальной стоимости
<li> 3.5. Резюме
<li> Упражнения
<li> Литература
<li> Ответы
</ul>
<p>
<li> Глава 4. Поиск с возвращением
<ul>
<li> 4.1. Введение
<li> 4.2. Оценивание эффективности
<li> 4.3. Ветви и границы
<li> 4.4. Дерево игры
<li> Упражнения
<li> Литература
</ul>
<p>
<li> Глава 5. Бинарные деревья
<ul>
<li> 5.1. Введение
<li> 5.2. Дерево Хаффмена
<li> 5.3. Алфавитные деревья
<li> 5.4. Алгоритм Ху-Таккера
<li> 5.5. Допустимость и оптимальность
<li> 5.6. Алгоритм Гарсиа и Уочса 
<li> 5.7. Регулярные функции стоимости 
<li> 5.8. t-арные деревья и другие результаты 
<li> Упражнения 
<li> Литература 
<li> Ответы 
</ul>
<p>
<li> Глава 6. Эвристические алгоритмы 
<ul>
<li> 6.1. Жадные алгоритмы 
<li> 6.2. Задача об упаковке 
<li> 6.3. Задача о составлении расписания 
<li> 6.4. Расписание с древесными ограничениями 
<li> Упражнения 
<li> Литература 
</ul>
<p>
<li> Глава 7. Матричное умножение 
<ul>
<li> 7.1. Алгоритм Штрассена умножения матриц 
<li> 7.2. Оптимальный порядок умножения матриц 
<li> 7.3. Триангуляция выпуклого многоугольника 
<li> 7.4. Эвристический алгоритм 
<li> Упражнения 
<li> Литература 
<li> Ответы 
</ul>
<p>
<li> Глава 8. NP-полнота 
<ul>
<li> 8.1. Введение 
<li> 8.2. Полиномиальные алгоритмы 
<li> 8.3. Недетерминированные алгоритмы 
<li> 8.4. NP-полные задачи 
<li> 8.5. Как решать NP-полную задачу? 
<li> Литература 
</ul>
<p>
<li> Глава 9. Алгоритмы локального индексирования 
<ul>
<li> 9.1. Объединение алгоритмов 
<li> 9.2. Максимальные потоки и минимальные разрезы 
<li> 9.3. Смежность и разделение 
</ul>
<p>
<li> Глава 10. Дерево Гомори-Ху 
<ul>
<li> 10.1. Древесные ребра и древесные звенья 
<li> 10.2. Стягивание 
<li> 10.3. Доминирование 
<li> 10.4. Эквивалентные формулировки 
<ul>
<li> 10.4.1. Оптимальное объединение компаний 
<li> 10.4.2. Оптимальное круговое разбиение 
</ul>
<li> 10.5. Крайние звезды и Hедопустимые круги 
<li> 10.6. Высокоуровневый подход 
<li> 10.7. Метод китайских палочек 
<li> 10.8. Взаимодействие между фазами 
<li> 10.9. Лестничная диаграмма 
<li> 10.10.Вопросы сложности 
</ul>
<p>
<li> Приложение А. Замечания к главам 2, 5, 6 
<ul>
<li> А.1. Деревья предшественников 
<li> А.2. Минимальная поверхность или задача о плато 
<li> А.3. Дополнения к главе 5 
<ul>
<li> А.3.1. Простое обоснование алгоритма Ху-Таккера 
<li> А.3.2. Бинарные деревья поиска 
<li> А.3.3. Бинарный поиск на ленте 
</ul>
<li> А.4. Комментарии к разделу 6.2 
</ul>
<p>
<li> Приложение Б. Сетевая алгебра 
<p>
<li> Литература, добавленная при переводе 
<p>
<li> Предметный указатель 
</ul>

<h1>
Детали
</h1>

<i>T.C. Hu, M.T. Shing</i> Combinatorial Algorithms. - Dover Publications, 2002.

<p>

<i>Ху Т.Ч., Шинг М.Т.</i> Комбинаторные алгоритмы / Пер. с англ. -
Нижний Новгород: Изд-во Нижегородского госуниверситета им.Н.И.Лобачевского, 2004. -
330 с.