
Третий том «Совершенного алгоритма» подходит разработчику, который умеет писать программы, но хочет увереннее выбирать способ решения задачи. Книгу о жадных алгоритмах и динамическом программировании написал Тим Рафгарден; Андрей Логунов указан как переводчик. Эти роли подтверждает карточка Литрес.
Ниже разбор открытого отрывка издательства и самостоятельные упражнения к его теме. Оценка всей книги здесь не даётся.
Сначала проверьте уровень подготовки
Если вы понимаете цикл и рекурсию, можете отсортировать массив и объяснить, от чего зависит время работы программы, попробуйте отрывок «Разработка жадного алгоритма» в блоге издательства «Питер». В нём разбирается порядок выполнения работ: каждой назначены длительность и вес, а цель выражена через взвешенные сроки завершения, поэтому автору приходится сопоставить разные правила выбора и объяснить, какое из них действительно решает поставленную задачу.
Это удобная проверка перед покупкой. Закройте текст после постановки задачи и своими словами объясните, что именно надо минимизировать. Если значение слова «вес» осталось неясным, вернитесь к модели задачи. Без модели код легко решает другую задачу.
Практика: найти ошибку в правдоподобном правиле
Предложение «сначала делать наиболее ценную работу» звучит убедительно. Но одна важная работа может занять столько времени, что задержит все остальные, поэтому её приоритет зависит и от длительности, и от того, как сформулирована общая цель.
Для учебной модели выпишите несколько работ и придумайте два правила их сортировки. Одно может учитывать разность веса и длительности, другое их отношение. Затем вручную вычислите целевую функцию для каждого полученного порядка, а при малом числе работ переберите все перестановки, чтобы увидеть, есть ли вариант лучше и где именно предложенное правило отклоняется от него.
Нашли более выгодный порядок? Контрпример опровергает универсальность выбранного правила. Совпадение с перебором на нескольких наборах лишь поддерживает гипотезу: следующий шаг состоит в доказательстве, а не в накоплении удачных запусков.
Как перейти к динамическому программированию
В этом томе заявлены также задача о рюкзаке и выравнивание последовательностей; если при чтении их объяснений остаётся неясным отдельный шаг, можно обратиться к тематическим видеоматериалам третьей части на сайте автора. Для самостоятельной работы выберите одну задачу и заведите короткую запись решения:
- Определите, какие данные входят в задачу и что считается ответом. Отдельно выпишите ограничения.
- Назовите состояние подзадачи так, чтобы по его параметрам можно было восстановить смысл результата.
- Объясните переход из меньших подзадач. Укажите, почему рассмотренные варианты исчерпывают допустимые решения.
- Запишите базовый случай и порядок заполнения. Попробуйте восстановить выбранные элементы, если нужен сам набор, а не только его стоимость.
- Сравните реализацию с полным перебором на маленьком входе. После этого оцените расход памяти и время работы при росте входных данных.
Где заканчивается применимость примера
При переносе учебного алгоритма в продукт сверяйте условия заново. В реальном расписании могут появиться зависимости между работами или несколько исполнителей, поэтому доказательство для исходной модели само по себе ничего не обещает такой системе, даже если порядок работ выглядит разумным.
Книгу разумно выбирать для изучения способов рассуждать об алгоритмах. Если нужна готовая реализация под конкретную библиотеку, сначала проверьте её документацию и контракт входных данных. Открытый отрывок помогает оценить ход объяснения, но не подтверждает отсутствие ошибок во всём переводе.
Источники
- Литрес: третий том «Совершенного алгоритма»
- Издательство «Питер»: открытый отрывок о жадном алгоритме
- Algorithms Illuminated: официальный сайт Тима Рафгардена
Материал обновлён 10 октября 2026 года. Границы проверки указаны в тексте.
