Какие темы самые важные для олимпиадного программировании в книге Кормена «Алгоритмы. Построение и анализ»?

Question

[kvellou]

Вот содержание книги Кормена:

Часть I. Основы
Глава 1. Роль алгоритмов в вычислениях
Глава 2. Приступаем к изучению
Глава 3. Рост функций
Глава 4. Рекуррентные соотношения
Глава 5. Вероятностный анализ и рандомизированные алгоритмы

Часть II. Сортировка и порядковая статистика
Глава 6. Пирамидальная сортировка
Глава 7. Быстрая сортировка
Глава 8. Сортировка за линейное время
Глава 9. Медианы и порядковые статистики

Часть III. Структуры данных
Глава 10. Элементарные структуры данных
Глава 11. Хеш-таблицы
Глава 12. Бинарные деревья поиска
Глава 13. Красно-черные деревья
Глава 14. Расширение структур данных

Часть IV. Усовершенствованные методы разработки и анализа
Глава 15. Динамическое программирование
Глава 16. Жадные алгоритмы
Глава 17. Амортизационный анализ

Часть V. Сложные структуры данных
Глава 18. B-деревья
Глава 19. Биномиальные пирамиды
Глава 20. Фибоначчиевы пирамиды
Глава 21. Структуры данных для непересекающихся множеств

Часть VI. Алгоритмы для работы с графами
Глава 22. Элементарные алгоритмы для работы с графами
Глава 23. Минимальные остовные деревья
Глава 24. Кратчайшие пути из одной вершины
Глава 25. Кратчайшие пути между всеми парами вершин
Глава 26. Задача о максимальном потоке

Часть VII. Избранные темы
Глава 27. Сортирующие сети
Глава 28. Работа с матрицами
Глава 29. Линейное программирование
Глава 30. Полиномы и быстрое преобразование Фурье
Глава 31. Теоретико-числовые алгоритмы
Глава 32. Поиск подстрок
Глава 33. Вычислительная геометрия
Глава 34. NP-полнота
Глава 35. Приближенные алгоритмы

Часть VIII. Приложения: математические основы
Приложение А. Ряды
Приложение Б. Множества и прочие художества
Приложение В. Комбинаторика и теория вероятности

Какие темы нужно прям изучать, а по каким можно просто поверхностно пройти?

Answer 1

[Alexandroppolus]

к ответу выше ещё можно добавить Часть IV.
этих штук (особенно ДП) будет завались.

Comments

[kvellou]

а как насчёт Часть II ?

[Alexandroppolus]

kvellou, то же всё есть готовое. Если ты пишешь на плюсах, то все эти базовые вещи уже реализованы.

[Wataru]

kvellou, Сортировки писать вот точно не придется. Их дают только что-бы объяснить всякие приемы построения алгоритмов.

А динамическое программирование - одна из самых важных тем. Я эту строчку просто тупо не заметил в списке.

Answer 2

[Wataru]

Часть III. Структуры данных
Часть VI. Алгоритмы для работы с графами

Менее важные, но встречающиеся темы:
Глава 30. Полиномы и быстрое преобразование Фурье
Глава 31. Теоретико-числовые алгоритмы
Глава 32. Поиск подстрок
Глава 33. Вычислительная геометрия

Но лучше прочитать, таки, всю книгу. Вправляет мозги, учит строить математические модели задач, что в олимпиадах очень важно.

Comments

[kvellou]

А важны ли темы как рекуррентные соотношения, асимптотические функции? Просто я их вообще не понимаю

[Wataru]

kvellou, Надо примерно понимать, что такое ассимптотическая сложность, почему сортировка слиянием или quicksort работают за O(n log n), почему бинарный поиск за O(log n). Никакие формальные математические доказательства и свойства не нужны. Главное уметь оценить сложность алгоритма.

[Alexandroppolus]

Часть III. Структуры данных

в стандартных библиотеках всё там перечисленное есть из коробки. Можно же пользоваться? (знать что это и для чего, конечно, надо)

[kvellou]

Wataru, но всё таки стоит прочесть всю книгу, но делать особый акцент на важные темы а по остальным просто пройтись?

[Wataru]

Alexandroppolus, Можно, но это слабо помогает. Там есть только самое примитивное сбалансированное дерево. Если надо считать какую-нибудь сумму в поддереве, то надо писать с нуля что-то (например, декартово дерево). Деревьев отрезков в стандартных библиотеках вообще, по-моему, нет нигде. Их, конечно, можно заменить и балансированным деревом поиска, но только с дополнительными данными по поддеревьям. Но легче писать дерево отрезков, чем декартово дерево, поэтому эту структуру тоже знать надо.

[Wataru]

kvellou, Да, всю книгу прочесть определенно стоит. Но не страшно, если в неважных темах вам что-то непонятно.