Комбинаторные алгоритмы, Ху Т.Ч., Шинг М.Т., 2004

Комбинаторные алгоритмы, Ху Т.Ч., Шинг М.Т., 2004.
 
   Книга представляет собой перевод второго расширенного и дополненного издания распространенного на Западе учебника американских математиков Т.Ч. Ху и М.Т. Шинга. Первое издание (1982) на русский язык не переводилось. Книга посвящена алгоритмам дискретной математики (кратчайшие пути и потеки в сетях, динамическое программирование, поиск с возвратом, бинарные деревья, эвристические алгоритмы, матричное умножение, NP-полные задачи, локальные алгоритмы, деревья Гомори-Ху) и может использоваться как учебник по курсу «Анализ и разработка алгоритмов» и как справочник. Весь материал изложен в классических традициях учебной литературы. Многие результаты на русском языке излагаются впервые.
Для студентов, аспирантов и научных работников, специализирующихся по дискретной математике и информатике.




Терминология теории графов.
Пытаясь решить какую-нибудь проблему, мы часто рисуем граф. Граф нередко является простейшим и наиболее ясным способом описания системы, структуры или ситуации. Китайская поговорка «рисунок полезнее тысячи слов» вполне оправдывается в математическом моделировании. Именно поэтому теория графов имеет многочисленные применения в физике, биологии и социальных науках. Большое разнообразие приложений приводит и к разнобою в терминологии. Работы по теории графов переполнены определениями, и каждый автор предпочитает свои собственные. Ниже мы вводим минимальный набор интуитивно ясных определений. Применяемые здесь обозначения и терминология близки к используемым Кнутом.

Граф состоит из конечного множества вершин и множества ребер, соединяющих вершины. Мы будем изображать вершины маленькими кружками, а ребра — линиями. Система или структура часто могут быть представлены графом, в котором линии указывают отношения между вершинами (элементами системы). Например, вершины могут представлять города, а ребра — соединяющие их дороги. Мы можем также представлять вершинами людей и соединять ребром две вершины, если соответствующие люди знакомы друг с Другом.

ОГЛАВЛЕНИЕ.
Предисловие к русскому изданию.
Предисловие к первому изданию.
Предисловие ко второму изданию.
Глава 1. Кратчайшие пути в графах.
1.1. Терминология теории графов.
1.2. Кратчайший путь.
1.3. Кратчайшие пути между всеми параши узлов.
1.4. Алгоритм декомпозиции.
1.5. Ациклические сети.
1.6. Кратчайшие пути в общей сети.
1.7. Минимальное остовное дерево.
1.8. Поиск в ширину и поиск в глубину.
Упражнения.
Литература.
Ответы.
Глава 2. Максимальные потоки.
2.1. Максимальные потоки.
2.2. Алгоритмы нахождения максимального потока.
2.2.1. Алгоритм Форда-Фалкерсона.
2.2.2. Алгоритм Карзанова.
2.2.3. МРМ-алгоритм.
2.2.4. Анализ алгоритмов.
2.3. Многотерминальные минимальные потоки.
2.3.1. Реализуемость (Гомори и Ху [12]).
2.3.2. Анализ (Гомори и Ху [12]).
2.3.3. Синтез (Гомори и Ху [12]).
2.3.4. Многопродуктовые потоки.
2.4. Потоки с минимальной стоимостью.
2.5. Приложения.
2.5.1. Множества различных представителей.
2.5.2. PERT-метод.
2.5.3. Оптимальное коммуникационное остовное дерево.
Упражнения.
Литература.
Ответы.
Глава 3. Динамическое программирование.
3.1. Введение.
3.2. Задача о рюкзаке.
3.3. Задача о двумерном рюкзаке.
3.4. Алфавитные деревья минимальной стоимости.
3.5. Резюме.
Упражнения.
Литература.
Ответы.
Глава 4. Поиск с возвращением.
4.1. Введение.
4.2. Оценивание эффективности.
4.3. Ветви и границы.
4.4. Дерево игры.
Упражнения.
Литература.
Глава 5. Бинарные деревья.
5.1. Введение.
5.2. Дерево Хаффмена.
5.3. Алфавитные деревья.
5.4. Алгоритм Ху-Таккера.
5.5. Допустимость и оптимальность.
5.6. Алгоритм Гарсиа и Уочса.
5.7. Регулярные функции стоимости.
5.8. t-арные деревья и другие результаты.
Упражнения.
Литература.
Ответы.
Глава 6. Эвристические алгоритмы.
6.1. Жадные алгоритмы.
6.2. Задача об упаковке.
6.3. Задача о составлении расписания.
6.4. Расписание с древесными ограничениями.
Упражнения.
Литература.
Глава 7. Матричное умножение.
7.1. Алгоритм Штрассена умножения матриц.
7.2. Оптимальный порядок умножения матриц.
7.3. Триангуляция выпуклого многоугольника.
7.4. Эвристический алгоритм.
Упражнения.
Литература.
Ответы.
Глава 8. NР-полнота.
8.1. Введение.
8.2. Полиномиальные алгоритмы.
8.3. Недетерминированные алгоритмы.
8.4. NP-полные задачи.
8.5. Как решать NР-полную задачу?.
Литература.
Глава 9. Алгоритмы локального индексирования.
9.1. Объединение алгоритмов.
9.2. Максимальные потоки и минимальные разрезы.
9.3. Смежность и разделение.
Глава 10. Дерево Гомори-Ху.
10.1. Древесные ребра и древесные звенья.
10.2. Стягивание.
10.3. Доминирование.
10.4. Эквивалентные формулировки.
10.4.1. Оптимальное объединение компаний.
10.4.2. Оптимальное круговое разбиение.
10.5. Крайние звезды и H-допустимые круги.
10.6. Высокоуровневый подход.
10.7. Метод китайских палочек.
10.8. Взаимодействие между фазами.
10.9. Лестничная диаграмма.
10.10. Вопросы сложности.
Приложение А. Замечания к главам 2, 5, 6.
А.1. Деревья предшественников.
А.2. Минимальная поверхность или задача о плато.
А.3. Дополнения к главе 5.
А.3.1. Простое обоснование алгоритма Ху-Таккера.
А.3.2. Бинарные деревья поиска.
А.3.3. Бинарный поиск на ленте.
А.4. Комментарии к разделу 6.2.
Приложение В. Сетевая алгебра.
Литература, добавленная при переводе.
Предметный указатель.



Бесплатно скачать электронную книгу в удобном формате, смотреть и читать:
Скачать книгу Комбинаторные алгоритмы, Ху Т.Ч., Шинг М.Т., 2004 - fileskachat.com, быстрое и бесплатное скачивание.

Скачать pdf
Ниже можно купить эту книгу, если она есть в продаже, и похожие книги по лучшей цене со скидкой с доставкой по всей России.Купить книги


Скачать - pdf - Яндекс.Диск.




Хештеги: #учебник по информатике :: #информатика :: #компьютеры :: #Ху :: #Шинг :: #алгоритм :: #графы :: #дерево Хаффмена