Отзыв о книге Э. Дейкстры "Дисциплина программирования"
12 марта 2013, 20:46
Автор: rgbeast
В книге представлен систематический подход к созданию программ, о которых точно известно, что они правильные. Автор начинает с математического построения доказательства работы алгоритма и демонстрирует строгий формальный подход в приложении к нескольким алгоритмам.
Из первых глав становится понятно, что дать математическое доказательство правильности для произвольного алгоритма - почти неразрешимая задача. Поэтому Дейкстра предлагает строить алгоритм так, чтобы упростить процесс доказательства. Для этого предложен ряд оригинальных методов, в числе которых инвариант цикла и цикл Дейкстры. При этом алгоритм, структура данных и программа разрабатываются параллельно методом пошаговой детализации. Автор обсуждает вопросы оптимизации алгоритма на этапе разработки и после разработки - многие методы сегодня стали стандартом (например, избыточность данных для повышение производительности). Увлекательность чтения дополняется тем, что в одной из глав Дейкстра разрабатывает новый алгоритм, одновременно описывая процесс со всеми пробами и ошибками. Несмотря на то, что книга вышла в 1978 году, ничего из описанного в ней не потеряло актуальности, а некоторые темы, напротив, стали востребованными значительно позже выхода книги (например, обсуждение многопоточности).
Рекомендую книгу всем, кто заинтересован в создании алгоритмов.
См. также обсуждения на webew:
Дейкстра о тестировании
Рекомендация Дейкстры в отношении условий цикла
Из первых глав становится понятно, что дать математическое доказательство правильности для произвольного алгоритма - почти неразрешимая задача. Поэтому Дейкстра предлагает строить алгоритм так, чтобы упростить процесс доказательства. Для этого предложен ряд оригинальных методов, в числе которых инвариант цикла и цикл Дейкстры. При этом алгоритм, структура данных и программа разрабатываются параллельно методом пошаговой детализации. Автор обсуждает вопросы оптимизации алгоритма на этапе разработки и после разработки - многие методы сегодня стали стандартом (например, избыточность данных для повышение производительности). Увлекательность чтения дополняется тем, что в одной из глав Дейкстра разрабатывает новый алгоритм, одновременно описывая процесс со всеми пробами и ошибками. Несмотря на то, что книга вышла в 1978 году, ничего из описанного в ней не потеряло актуальности, а некоторые темы, напротив, стали востребованными значительно позже выхода книги (например, обсуждение многопоточности).
Рекомендую книгу всем, кто заинтересован в создании алгоритмов.
См. также обсуждения на webew:
Дейкстра о тестировании
Рекомендация Дейкстры в отношении условий цикла