webew
Войти » Регистрация
 
Алгоритмы

Отзыв о книге Э. Дейкстры "Дисциплина программирования"

12 марта 2013, 20:46
Автор: rgbeast
В книге представлен систематический подход к созданию программ, о которых точно известно, что они правильные. Автор начинает с математического построения доказательства работы алгоритма и демонстрирует строгий формальный подход в приложении к нескольким алгоритмам.

Из первых глав становится понятно, что дать математическое доказательство правильности для произвольного алгоритма - почти неразрешимая задача. Поэтому Дейкстра предлагает строить алгоритм так, чтобы упростить процесс доказательства. Для этого предложен ряд оригинальных методов, в числе которых инвариант цикла и цикл Дейкстры. При этом алгоритм, структура данных и программа разрабатываются параллельно методом пошаговой детализации. Автор обсуждает вопросы оптимизации алгоритма на этапе разработки и после разработки - многие методы сегодня стали стандартом (например, избыточность данных для повышение производительности). Увлекательность чтения дополняется тем, что в одной из глав Дейкстра разрабатывает новый алгоритм, одновременно описывая процесс со всеми пробами и ошибками. Несмотря на то, что книга вышла в 1978 году, ничего из описанного в ней не потеряло актуальности, а некоторые темы, напротив, стали востребованными значительно позже выхода книги (например, обсуждение многопоточности).

Рекомендую книгу всем, кто заинтересован в создании алгоритмов.

См. также обсуждения на webew:
Дейкстра о тестировании
Рекомендация Дейкстры в отношении условий цикла
Добавить комментарий

1234ru

Цитата:
В книге представлен систематический подход к созданию программ, о которых точно известно, что они правильные

А когда бывает не точно известно?
Можно пример того и другого?

Вообще интересно, что по столь динамично развивающейся области имеется литература, не теряющая своей актуальности на протяжении нескольких десятков лет.
То, что не убивает нас, делает нас инвалидами.
13.03.2013, 03:32
Ответить
NO USERPIC

rgbeast

1234ru
А когда бывает не точно известно?
Можно пример того и другого?

Примеры доказанно правильных программ при заранее известных условиях их работоспособности есть в книге. Примеры обратного долго искать не нужно. Это любые программы, которые в принципе могут содержать баги (или их содержат). Для многих программ даже неизвестно точно, что именно они делают. В том смысле, что поведение при различных входных параметрах может быть неожиданным и недокументированным. При разработке программист часто руководствуется своими представлениями о том, каким будет поток исполнения программы. Отсюда необходимость отладки, которая, опять же, не гарантирует отсутствия багов. Дейкстра предлагает ряд методов для того, чтобы "компенсировать ограниченность объема черепной коробки" и создавать корректные программы, не перебирая в голове все варианты их исполнения.

1234ru
Вообще интересно, что по столь динамично развивающейся области имеется литература, не теряющая своей актуальности на протяжении нескольких десятков лет.

Если заложить правильный фундамент, он останется надолго.
13.03.2013, 19:55
Ответить
© 2008—2024 webew.ru, связаться: x собака webew.ru
Сайт использует Flede и соответствует стандартам WAI-WCAG 1.0 на уровне A.
Rambler's Top100

Реклама: