Новосибирский государственный университет Факультет информационных технологий Современные проблемы информатики и вычислительной техники

А.М.Федотов

Публикации и документы в коллекции "Современные проблемы информатики"

Книга (A discipline of programming) написана одним из крупнейших зарубежных специалистов в области программирования. Она посвящена фундаментальным вопросам конструирования корректных и изящных программ для ЭВМ. В ней предлагается методика формального вывода программы из математической постановки задачи. При этом прослеживается развитие алгоритмов вплоть до создания программ. Материал излагается в форме остроумных и поучительных задач по программированию. Книга представляет значительный интерес для широкого круга программистов.

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

В коллекции представлено 8 первых глав из книги.

Ссылки на авторов публикации:
Дейкстра Эдсгер Вибе

Ключевые термины:  программирование;

Контекстный поиск: Задайте образец для поиска:

Федотов Анатолий Михайлович

НГУ ФИТ НГУ ИВТ СО РАН