Алгоритмы, Аха, Аха Лей, 2024

Алгоритмы, Аха, Аха Лей, 2024.

   Зачем читать скучные описания алгоритмов и продираться через нагромождение формул? Практические примеры и забавные объяснения позволят моментально разобраться с самыми сложными задачами, а юмор и прекрасные иллюстрации не дадут вам «заснуть» над книгой. Вы словно читаете короткие истории или пытаетесь справиться с головоломкой, постигая при этом суть алгоритмов и ощущая их красоту.
В число алгоритмов, рассмотренных в книге, вошли различные методы сортировки, перебор, поиск в глубину и ширину, обход графов, четыре алгоритма поиска кратчайшего пути, два алгоритма минимального остовного дерева, алгоритмы определения вершин и ребер разреза, а также поиск наибольшего паросочетания в двудольных графах и многое другое.




Сеня покупает книги.
Существует множество других алгоритмов, например сортировка кучи — упорядочивание на основе двоичного дерева, о котором я расскажу в следующей главе. А сейчас давайте повторим три уже изученных алгоритма сортировки при решении задачи «Сеня покупает книги» (основана на первом задании олимпиады по информатике NOIP 2006).

В школе, где учится Сеня, собираются организовать библиотеку, и учительница поручает мальчику провести опрос среди одноклассников, чтобы узнать, какие книги они любят читать. Сеня попросил каждого ученика написать ISBN книги, которую он хотел бы прочитать (вы знали, что каждая книга имеет уникальный идентификатор? Если не верите, возьмите какую-нибудь книгу и посмотрите ее выходные данные). Конечно, окажется, что несколько книг интересны многим школьникам, поэтому некоторые номера ISBN будут повторяться. Сене нужно удалить повторяющиеся номера ISBN, чтобы каждая книга была куплена только в одном экземпляре (школьное руководство скуповато). Затем нужно отсортировать номера ISBN в порядке возрастания, после чего Сеня отправится в книжный магазин. Мы должны помочь Сене удалить повторяющиеся номера и получить упорядоченный список.

ОГЛАВЛЕНИЕ.
От автора.
Благодарности.
О научном редакторе русского издания.
От издательства.
Глава 1. На старт, внимание, сортировка!.
1.1. Быстро и просто — блочная сортировка.
1.2. Рассказ о добрых соседях — сортировка пузырьком.
1.3. Самая популярная — быстрая сортировка.
1.4. Сеня покупает книги.
Глава 2. Стеки, очереди, связные списки.
2.1. Расшифровка номера — очереди.
2.2. Проверка палиндромов — стеки.
2.3. Карточная игра «пьяница» по-восточному.
2.4. Добавление элемента в последовательность — связные списки.
2.5. Аналоговые связные списки.
Глава 3. Перебор! Это жестко.
3.1. Полный перебор.
3.2. Бомбермен.
3.3. Уравнения из спичек.
3.4. Перестановки чисел.
Глава 4. Всемогущий поиск.
4.1. Только вперед, пока не упретесь в стену, — поиск в глубину.
4.2. Спасти малышку Сашу.
4.3. Шаг за шагом — поиск в ширину.
4.4. Продвинутый бомбермен.
4.5. Первый герой.
4.6. Игра в сантехника.
Глава 5. Обход графа.
5.1. Что на самом деле означают «глубина» и «ширина».
5.2. Карты и маршруты — обход графа в глубину.
5.3. Минимум пересадок — обход графа в ширину.
Глава 6. Кратчайший путь.
6.1. Всего пять строк кода — алгоритм Флойда — Уоршелла.
6.2. Алгоритм Дейкстры — кратчайшие пути из одного источника.
6.3. Алгоритм Беллмана — Форда: решение проблемы отрицательных весов ребер.
6.4. Оптимизированный алгоритм Беллмана — Форда.
6.5. Сравнение алгоритмов нахождения кратчайшего пути.
Глава 7. Волшебное дерево.
7.1. Начинаем путешествие по деревьям.
7.2. Бинарные деревья.
7.3. Куча — волшебная очередь приоритетов.
7.4. Борьба с преступностью.
Глава 8. Более сложные алгоритмы.
8.1. Торговые пути — поиск минимального остовного дерева.
8.2. И снова задача о минимальном остовном дереве.
8.3. Выбираем цель — вершина разреза графа.
8.4. Ключевые связи — нахождение ребра разреза с помощью алгоритма Тарьяна.
8.5. Американские горки — поиск наибольшего паросочетания в двудольном графе.
Глава 9. Попробуйте улучшить решение. Интервью в Microsoft Research Asia.

Купить .





Теги: учебник по программированию :: программирование :: Аха Лей :: алгоритм