Сообщение о э дейкстра

Обновлено: 02.07.2024

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

В информатике мы все – дети Дейкстры

Эдсгер Вибе Дейкстра родился в Роттердаме (Нидерланды) в мае 1930 года в семье научных работников: отец будущего лауреата Тьюринговской премии был химиком, мать – математиком что, видимо, и предопределило выбор Дейкстры поступить на отделение математики и теоретической физики Лейденского университета. Еще учась в университете Дейкстра познакомился с первыми компьютерами и увлекся их программированием. Этому немало способствовало и то, что будучи еще студентом Дейкстра с 1952 года работал программистом в Математическом центре Амстердама. За год до окончания университета Дейкстра оказался перед дилеммой: продолжить научную карьеру по основной специальности – теоретической физике или все-таки продолжать заниматься программированием. Вот что рассказывал об этом он сам:

По счастью Дейкстра обратился со своими сомнениями к своему научному руководителю Адриану ван Вейнгаардену у которого хватило житейской мудрости и научной проницательности чтобы убедить молодого физика стать профессиональным программистом.

Трудно сказать – много ли потеряла теоретическая физика оставшись без Дейкстры; учитывая его уникальную интеллектуальную мощь, которая очень вскоре проявилась в полную силу, рискну предположить, что физика потеряла немало. Но случилось то, что случилось и начиная с этого времени талант и энергия Э.Дейкстры принадлежали новой дисциплине – информатике.

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

Однако, ближайшие несколько лет показали – ван Вейнгаарден не ошибся, предложив своему талантливому студенту, а в дальнейшем аспиранту, выбрать программирование: с конца 50-х годов корпорация IBM начала производство компьютеров на транзисторах, что позволило существенно снизить их энергоемкость, массу и стоимость одновременно подняв объемы памяти и производительность. Моментально подтянулись другие компании и компьютеры из военных и научных лабораторий стали доступны банкам, производственным предприятиям, учебным заведениям, больницам, коммунальным службам. Компьютерная эра началась.

Алгоритм кратчайшего пути на графе

В 1959 году Дейкстра предложил алгоритм поиска кратчайшего пути от любой вершины ориентированного взвешенного графа (графа, ребрам которого приписаны направления и вес, скажем расстояние или цена) до любой другой. Алгоритм появился в результате поиска решения оптимальной разводки соединений плат компьютера.

Вопросы, касающие трансляции языков программирования, подробно изложены в многочисленной литературе к которой я и отсылаю заинтересованного читателя.

Борьба за ресурсы или взаимодействие процессов

«Эти две последнии операции всегда выполняются над семафорами и представляют единственный способ обращения к семафорам со стороны одновременно действующих процессов.

Эти концепции и их дальнейшее развитие – например, мьютексы – и сегодня применяются при проектировании и реализации операционных систем.

«В давние времена один богатый филантроп пожервовал свой капитал на основание некоего пансиона, чтобы дать пристанище пяти знаменитым философам. У каждого философа была своя комната, где он мог предаваться размышлениям. Была у них и общая столовая с круглым столом, вокруг которого стояли пять стульев, каждый помеченный именем того философа, которому он предназначался. Слева от каждого философа лежала золотая вилка, а в центре стояла большая миска спагетти, содержимое которой постоянно пополнялось.

Видит ли читатель в чем тут проблема?

Проникновение компьютеров во все отрасли промышленности, бизнеса, образования и проч., а также сопутствующий этому проникновению рост объема разрабатываемого программного обеспечения вызывал обеспокоенность ведущих специалистов: программы становились все больше, все сложнее, все разнообразнее. Все это не смогло не сказаться на их качестве – оно стремительно падало.

Досадно, если ошибка была в программе начисления заработной платы, но это, в конце-концов дело поправимое. Страшно, если программная ошибка обнаруживалась в системе управления воздушным транспортом. И совсем уж катастрофической была бы ошибка в программе управления работой атомного реактора.

В чем причины этого? Причин было множество, но я задержусь только на одной из них – как раз той, которой и посвящена цитированная выше статья Дейкстры. Обратимся опять к тексту статьи:

Для обеспечения указанных легкости и гибкости Дейкстра предлагает проектировать и кодировать программы в соответствии с определенной дисциплиной, названной им структурным программированием. Известно (это математический факт известный как теорема Бема-Якопини), что любую программу можно построить с использованием трех конструкций: последовательного выполнения и операторов выбора и цикла. Дейкстра предложил (одновременно, хотя и независимо с Никлаусом Виртом – еще одним лауреатом премии Тьюринга) представлять программу как иерархическую структуру блоков, каждый из которых выполняет небольшую, но завершенную задачу. Это достигается с помощью механизма процедур и функций. Т.о. программы приобретали модульность.

Идеи структурного программирования, поначалу встреченные с недоверием, довольно скоро завоевали признание (особенно, после создания Никлаусом Виртом языка программирования PASCAL). Более того, эта методика остается актуальной и сегодня (достаточно вспомнить такие популярные языки программирования C, PASCAL или BASIC).

Книги по точным наукам, вообще говоря, не балуют своих читателей философскими размышлениями. Книга Дейкстры – счастливое исключение: это одновременно и математический текст, и сборник рецептов, и интеллектуальное откровение пророка.

Формально книга представляет собой описание решений примерно двух десятков задач, начиная от самых простых (алгоритм Евклида нахождения наибольшего общего делителя), до весьма сложных (построение выпуклой оболочки по заданным точкам в 3-х мерном пространстве). Если бы книга ограничивалась только этим, то, безусловно, она была бы интересна, познавательна, но не более.

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

В конце 60-х годов XX века американцем Р.Флойдом и англичанином Ч.Хоаром - оба, кстати, Тьюринговские лауреаты - было начато исследование формальных свойств программ. Нельзя сказать, что до них этими вопросами никто не занимался, но предыдущие исследования (за исключением, пожалуй, передовых статей создателя языка LISP Дж.Мак-Карти) носили довольно фрагментарный характер. Самые проницательные исследователи понимали, что назревал кризис, обусловленный сложностью и объемом программного обеспечения: индустрии грозила опасность захлебнуться в миллионах строк кода. Ч.Хоар, используя идеи Р.Флойда, предложил формализм для обозначения частичной корректности программ. Этот формализм выражался формулой вида:

имевший следующий смысл: если команда S начинается в начальном состоянии, удовлетворяющем предикату (т.е. условию) Q, то имеется гарантия , что выполнение S заканчивается через конечное время в состояниии удовлетворяющему предикату (т.е. условию) R.

Это все, конечно, очень и очень абстрактно; сейчас я, в качестве примера, рассмотрю реализацию на языке программирования Java алгоритма определения наибольшего общего делителя (НОД) пары целых чисел по алгоритму Евклида:

Void gcd (int x, int y)

if (x > y) x = x – y;

Теперь проверим как работает эта реализация при различных значениях аргументов:

Вызов gcd (0, 257), очевидно, работает не так как надо: правильный результат 257. Для пары (0, 0) результат вообще не определен: любое число исключая 0 служит решением. Последние два варианта (когда один или оба аргумента метода отрицательны) не позволяют определить правильный результат (он, кстати, равен по-прежнему 37). Одним словом – либо неполна реализация (в ней не обрабатываются особые случаи), либо я передаю недопустимые значения входных аргументов.

Кто в этом виноват? Конечно, программист – он обязан был это предусмотреть какие значения аргументов допустимы, а какие нет. Причем еще на этапе написания программы. Можно ли предотвратить подобные ситуации? Можно. Как именно? Ответ и его обоснование и находятся в книге Дейкстры.

Цель программирования – написание программ, выполняющих поставленные задачи. Возвращаясь к примеру очевидно, что в нем такой задачей является нахождение НОД пары чисел и легко видеть, что правильный ответ зависит от области значений аргументов. С точки зрения математики алгоритм нахождения НОД отвечает тому, что требуется (сам Евклид тому порукой); но раз есть ошибки выполнения, то их источник кроется в реализации этого алгоритма.

Вспоминая школьную алгебру мы вспомним, что многие изучаемые в ней функции определены не для всех значений аргументов. Скажем, квадратный корень определен только для неотрицательных аргументов (комплексные числа я не рассматриваю); деление определено только в том случае, когда делитель не равен 0. Все это – примеры частичных функций. А вот, к примеру, сложение и умножение определены всегда. Следовательно, приведенная выше реализация алгоритма Евклида определена не для всех значений аргументов, т.е. является примером частичной (не всюду определенной) функции. Иными словами, начальные условия при данной реализации должны удовлетворять некоторым условиям, а именно – это должны быть только положительные целые числа.

Вот что пишет Дейкстра:

В приведенной выше реализации алгоритма Евклида я должен был последовательно сузить всю область целых чисел сначала до натуральных, а потом – до положительных. Вот теперь, когда область начальных значений определена, я могу гарантировать, что такая реализация алгоритма отработает правильно.

Таким образом методика построения программ по Дейкстре носит характер поиска начальных условий при которых программа S будет правильно завершена (т.е. окажется в состоянии, удовлетворяющем R). Очень важно сделать такой поиск систематическим; поиск вслепую, как это продемонстрировано выше, не подходит. Для этого Дейкстра привлекает аппарат исчисления предикатов из математической логики; начальные условия не просто ищутся - они выводятся: убедительны не голословные утверждения и не результаты тестовых прогонов, а исключительно математически доказуемые факты. При этом доказательство программы строится параллельно ее написанию. Выгоды этого очевидны – мы получаем более или менее убедительные (в зависимости от глубины анализа) свидетельства того, что программа делает то, что от нее ожидается.

Для обоснования применяемых им методов книга Дейкстры перемежается – и это, возможно, самое ценное, что есть в книге - главами в которых автор рассуждает и делится своими мыслями по разнообразным вопросам программирования. Как настоящий ученый он не скрывает своих сомнений, ошибок, тупиков. Если возможен ошибочный подход или если сам автор допустил ошибку – читатель об этом непременно узнает.

Список литературы я условно разделил на две части: прежде всего - работы самого Э.В.Дейкстры, а затем - книги других авторов, вплотную примыкающие к темам, затронутым в статье.

Электронный архив трудов и рукописей Эдсгера В.Дейкстры

Более простая книга, нежели работа Д.Гриса. Математики заметно меньше, зато много практических примеров и упражнений. Основной язык программирования - PASCAL

Прекрасное изложение теории взаимодействующих процессов и параллелизма. Детальное обсуждение множества вопросов затронутых в статье Дейкстры. Чтение книги предполагает знакомство читателя с основами математической логики и теории множеств

Пионерская работа Ч.Хоара о построении формального базиса программирования

Среди программистов всегда бытовали байки об ошибках программного обеспечения. Трудно сказать – насколько они правдивы. Почти наверняка, что-то подобное происходило: как у каждого хорошего врача есть свое кладбище, так и у каждого хорошего программиста есть своя подборка ошибок и провалов. Эта статья посвящена описанию нескольких ошибок программного обеспечения имевших катастрофические последствия.

В 1958—1960 годах принимал участие в разработке языка программирования Алгол, в 1960-х — участвовал в создании ОС THE — первой операционной системы, построенной в виде множества параллельно исполняющихся взаимодействующих процессов. Именно в процессе этой работы появились понятия синхронизации процессов, идея семафора, а также была чётко осознана необходимость в структуризации процесса программирования и самих программ.

Длительное время работал в фирме Burroughs Corporation. В 1970-е годы вместе с Чарльзом Хоаром и Никлаусом Виртом разработал основные положения ставшей классикой методологией разработки программ — структурного программирования.

В последние годы жизни преподавал в США, в Техасском университете. Умер 6 августа 2002 года.

Научные достижения

Литературные труды

Дейкстра многократно предостерегал от попыток превратить разработку программ в некий тривиальный процесс; по его мнению, программирование, в сути своей — чрезвычайно сложная научная и инженерная деятельность, и никакие новые методы и инструменты не смогут кардинально изменить это положение — они лишь освобождают программиста от части рутинной работы. Попытки же превратить программирование в простое занятие, доступное каждому, обречены на провал.

Влияние

Дейкстра также приобрёл немалую известность за пределами академических кругов благодаря своим резким и афористичным высказываниям по актуальным проблемам компьютерной индустрии. Вот некоторые из его афоризмов:

Один из тех людей, с именем которых связано превращение программирования из шаманства в науку, — Эдсгер Дейкстра. Он небезуспешно доказывал, что программирование — высокое искусство и интеллектуальное творчество.

Программирование – не набор пассов и заклинаний, не шаманство, не танцы с бубном, а математическая дисциплина. А всякая дисциплина, если она претендует на нечто большее, чем на внешний эффект, должна строиться на прочном фундаменте. Таким фундаментом для Дейкстры является математическая логика, а точнее – исчисление предикатов.

Сейчас это не кажется чем-то необычным, но в 50-е годы это прозвучало как откровение. Дейкстра понял и убедительно показал, как теория может и должна помочь практике.

Для особо одаренных

Эдсгер Вайб Дейкстра родился в Роттердаме (Голландия) в 1930 году. Его родители были хорошо образованными людьми: отец был химиком, а мать — математиком. В 1942 году в возрасте 12 лет Дейкстра поступил в гимназию Эрасминиум — школу для особо одаренных детей, где преподавался ряд разнообразных предметов, в том числе греческий, латынь, французский, немецкий и английский языки, биология, математика и химия.

В 1945 году Дейкстра подумал, что он мог бы изучать право и, возможно, работать в качестве представителя Нидерландов в ООН. Однако, вследствие его успехов в изучении химии, математики и физики, он поступил в университет Лейдена, где решил заняться теоретической физикой. В 1951 году он посещал летнюю школу по программированию в Кембриджском университете.

Дилемма

За год до окончания университета Дейкстра оказался перед дилеммой: продолжить научную карьеру по основной специальности – теоретической физике или все-таки продолжать заниматься программированием:

мне надо было сделать выбор – либо прекратить программировать и стать настоящим респектабельным теоретическим физиком, либо как-то формально завершить мое обучение теоретической физике с минимальными усилиями и стать… кем же? Программистом? Но разве это респектабельная профессия? В конце концов, что такое программирование? В чем должен был состоять тот солидный объем знаний, который позволил бы считать программирование научной дисциплиной?

Однажды Дейкстра постучал в дверь кабинета своего научного руководителя ван Вейнгаардена. Терпеливо выслушав, что беспокоит Дейкстра, ван Вейнгаарден согласился, что в настоящее время есть не так уж много вещей, которые можно было бы отнести к дисциплине программирования, но затем он спокойно продолжал объяснять, что автоматические вычисления машины — не кратковременная мода, за ними будущее, что мы находимся у самых истоков и — как знать? — может быть, именно Дейкстра призван превратить программирование в почетную научную дисциплину. Это был поворотный момент всей жизни Эдсгера Дейкстра, и он как можно быстрее прошел все курсы, требующиеся для получения диплома в области теоретической физики, и начал заниматься программированием.

Туманное будущее

Алгоритм Дейкстры

ALGOL-60

Пример обратной польской записи

Величайшие изобретения прошлого по версии Дейкстры

Одним из величайших изобретений, он считал, является замкнутая подпрограмма, которая воплощает одну из фундаментальных абстракций.

Вторым крупным достижением в области программного обеспечения Дейкстра называл рождение FORTRAN. Это был чрезвычайно смелый проект, который должен оцениваться как успешная методика программирования, но с очень ограниченным числом средств поддержки основной концепции. В наши дни этот язык считают устаревшим. Трагическая судьба FORTRAN — следствие его широкого признания, приковавшего мышление тысяч и тысяч программистов к прошлым ошибкам.

Пять обедающих философов

Разумеется, такая нестабильность и непредсказуемость поведения основной программы – операционной системы – никого не могла устроить.

В давние времена один богатый филантроп пожервовал свой капитал на основание некоего пансиона, чтобы дать пристанище пяти знаменитым философам. У каждого философа была своя комната, где он мог предаваться размышлениям. Была у них и общая столовая с круглым столом, вокруг которого стояли пять стульев, каждый помеченный именем того философа, которому он предназначался… Слева от каждого философа лежала золотая вилка, а в центре стояла большая миска спагетти, содержимое которой постоянно пополнялось.

Предполагалось, что большую часть времени философ проводил в размышлениях, а почувствовав голод, шел в столовую, садился на свой стул, брал вилку слева от себя и приступал к еде. Но такова уж сложная природа спагетти, что их не донести до рта без помощи второй вилки. Поэтому философу приходилось брать вилку и справа от себя… Если вилка требовалась другому философу, ему приходилось ждать, пока она освободится.

Структурное программирование

Проникновение компьютеров во все отрасли промышленности, бизнеса, образования, а также сопутствующий этому проникновению рост объема разрабатываемого программного обеспечения вызывал обеспокоенность ведущих специалистов: программы становились все больше, все сложнее, все разнообразнее. Все это не смогло не сказаться на их качестве – оно стремительно падало.

Дейкстра видел причины ошибок в запутанной структуре программ:

Я считаю, что программа никогда не является самоцелью; программа предназнается для того, чтобы вызвать вычисления, а цель вычислений – получить нужный результат… Я утверждаю (хотя и не могу доказать), что легкость и гибкость таких наших суждений существенно зависит от простоты взаимосвязей между программой и вычислениями… Грубо говоря, можно считать желательным, чтобы структура программы отражалась в структуре вычислений.

Для обеспечения указанных легкости и гибкости Дейкстра предлагает проектировать и кодировать программы в соответствии с определенной дисциплиной, названной им структурным программированием. Известно (это математический факт известный как теорема Бема-Якопини), что любую программу можно построить с использованием трех конструкций: следования, ветвления и цикла.

О пользе и вреде Goto

1. Использование GOTO – плохой тон.
2. Самый плохой тон – возвращение с помощью метки назад.
3. GOTO – избыточный оператор. Его легко можно заменить циклами и условиями.
4. Вирт и Дейкстра говорят, что GOTO это плохо.
5. GOTO аннулирует многие возможности компилятора по оптимизации управляющих структур, из-за чего код становится медленней и объёмней.

1. Группа взаимоисключающих условий.
2. Принцип вселенской причинности – если где-то есть GOTO, значит он там нужен.
3. Выход из множества циклов одновременно.
4. Конечные автоматы (пример кода).

Память

Дейкстра продолжал работу в Математическом Центре до тех пор, пока в начале 70-х годов не перешел на работу исследователем в корпорацию Burroughs в США. В 1972 году АСМ наградила Дейкстра премией Тьюринга (ACM Turing Award).

В 1974 году AFIPS удостоила его памятной наградой Гарри Гуда (AFIPS Harry Goode Memorial Award). В начале 1980-х годов Дейкстра переехал в Остин, штат Техас. В 1984 году он был назначен деканом факультета компьютерных наук в Техасском университете.

Не от мира сего

Когда его коллеги подготовили и издали к 60-летнему юбилею специальный сборник, Дейкстра ответил каждому из них личным благодарственным письмом, написанным от руки (а это, между прочим – 61 адресат). Ученому его уровня и положения полагался секретарь, но Дейкстра отказался от этой привилегии и все предпочитал делать сам.

В августе 2002 года Эдсгер Вибе Дейкстра скончался в своем доме в Нидерландах.

Э́дсгер Ви́бе Де́йкстра (нидерл. Edsger Wybe Dijkstra ; 11 мая 1930, Роттердам (Нидерланды) — 6 августа 2002) — выдающийся нидерландский учёный, идеи которого оказали огромное влияние на развитие компьютерной индустрии.

Содержание

Биография

В 1958—1960 годах принимал участие в разработке языка программирования Алгол, в 1960-х — участвовал в создании операционной системы THE (англ.) — первой операционной системы, построенной в виде множества параллельно исполняющихся взаимодействующих процессов. Именно в процессе этой работы появились понятия синхронизации процессов, идея семафора, а также была чётко осознана необходимость в структуризации процесса программирования и самих программ.

Длительное время работал в фирме Burroughs Corporation. В 1970-е годы вместе с Чарльзом Хоаром и Никлаусом Виртом разработал основные положения ставшей классикой методологии разработки программ — структурного программирования.

В последние годы жизни преподавал в США, в Техасском университете. Умер 6 августа 2002 года.

Научные достижения

Литературные труды

Влияние

Студентов, ранее изучавших Бейсик, практически невозможно обучить хорошему программированию. Как потенциальные программисты они подверглись необратимой умственной деградации (по этому вопросу см. статью про оператор
Проекты, предлагающие программирование на естественном языке, гибельны по своей сути.
Когда советское правительство приняло решение о переходе советской промышленности к копированию модельного ряда IBM/360, Дейкстра (работавший в то время в конкурировавшей с IBM фирме Burroughs) назвал это решение величайшей победой Запада в холодной войне, а выбранную для клонирования модель IBM/360 (прообраз советской ЕС ЭВМ) — величайшей диверсией Запада против СССР.

Литература

Дейкстра Э. Дисциплина программирования = A discipline of programming. — 1-е изд. — М.: Мир, 1978. — С. 275.

Дал У., Дейкстра Э., Хоор К. Структурное программирование = Structured Programming. — 1-е изд. — М.: Мир, 1975. — С. 247.

11 мая 1930 года в городе Роттердам (Голландия) родился Эдсгер Вайб Дейкстра (Edsger Wybe Dijkstra), выдающийся ученый и классик программирования. Разработав множество концепций теории программирования, Дейкстра превратил его в серьезную науку, развивавшуюся до этого преимущественно на интуитивно-любительском уровне.

Эдсгер вырос в семье ученых (его мать была математиком, а отец - химиком) и получил прекрасное образование: с детства его окружали точные науки, их четкая логика позднее и легла в основу знаменитых трудов великого теоретика и критика программирования. Окончив Гимназию Эразма в Роттердаме, он получил степень магистра математики и теоретической физики в Лейденском университете (University of Leyden). Однако уже в 1955 г. Эдсгер, устроившись программистом в Математический Центр Амстердама (Mathematisch Centrum), забыл о своей профессии: , - писал молодой ученый. Позднее он получил степень доктора компьютерных наук в Университете Амстердама (University of Amsterdam).

В 1962 г. Дейкстра становится профессором математики в Технологическом университете Эйндховена (Eindhoven, Нидерланды), отказавшись занять предложенную здесь же должность профессора Computing Science. Спустя семь лет, он вновь утверждал, что эта область знания еще не оформилась как самостоятельная дисциплина: Так, в последующее десятилетие становление фундаментальных основ программирования легло на плечи господина Дейкстры.

Именно поэтому Дейкстра призывал отказаться от привычного и вездесущего Go To: . В качестве альтернативы ученый предложил использовать в теле программы операторы повторения (повторение цикла до момента соблюдения заданного условия - while X repeat Y или repeat Y until X), последовательное выполнение команд, идущих друг за другом, условные операторы (if X then Y) и операторы ветвления. По сути, в своей работе Дейкстра изложил основные идеи структурного программирования, без понимания которых даже самому опытному программисту, по его мнению, не добиться успеха в решении постоянно усложняющихся задач.

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

Еще Эммануил Кант говорил о том, что . Язык программирования - тончайшее средство, позволяющее нам шаг за шагом описывать набор тех действий, совокупность которых в конечном итоге и даст желаемый результат. И здесь не обойтись без аккуратности, строгого синтаксиса и соблюдения всех семантических условностей, иначе ошибок не избежать. Но попробуйте представить весь объем исходных текстов, например, Windows, не содержащих в первичном варианте ни единой ошибки. При всем старании опытнейших программистов это просто невозможно. На тестирование и отладку каждого блока, содержащего тысячи команд, порой уходит во много раз больше времени и сил, чем их потребовалось для написания исходного кода. А если в проекте участвуют сотни человек, каждый из которых создает и отлаживает отдельный модуль, позднее включаемый в единый программный код, им просто необходимо на простом и понятном всем языке. Случись иначе, мы бы никогда не увидели ни единого программного продукта, предаваясь метафоре - всех их постигла бы участь Вавилонской башни.

Признание подхода Дейкстры к программированию пришло не сразу. Есть, к сожалению, в научных кругах традиция отвергать и высмеивать неведомые доселе истины, а уж потом только принимать их как само собой разумеющиеся. Всерьез задумываться о ценности идей Дейкстры стали только после наступления так называемого (в 1968 г. в США эта проблема обсуждалась даже на международной конференции). В начале 1970-х годов принципами структурного программирования (которые, кстати, позднее легли в основу объектно-ориентированного программирования) впервые воспользовалась компания IBM при создании банка данных газеты и, надо сказать, очень удачно - работа была выполнена быстро и практически безошибочно.

Теоретические основы создания программ, предложенные Дейкстрой, отнюдь не исчерпываются рассмотренными выше положениями. Дейкстра является автором алгоритма Shortest Path Algorithm (алгоритм кратчайшего пути, известный как алгоритм Дейкстры), ставшего актуальным для маршрутизаторов Интернета. Идея синхронизации последовательных процессов ( ) в работе многозадачных систем (например, при одновременном выполнении операционной системой нескольких процессов) также принадлежит ему1).

Дейкстра принимал непосредственное участие в создании языка Алгол-60 (Algol 60), который по праву можно назвать первым структурным языком программирования, им же написан и первый компилятор с Алгола-60. Многие идеи Дейкстры затем стали основополагающими при создании языков Паскаль, Бейсик и Си.

В 1973 г. ученый становится исследователем одной из авторитетнейших в то время американских компаний - "Барроуз" (Burroughs Corporation). Даже ради престижной должности Дейкстра не покинул родину, а сотрудничал с Burroughs дистанционно. Интересно, что компания заинтересовалась своеобразным хобби своего нового работника: с 1967 г. Дейкстра писал и рассылал своим корреспондентам и работодателям письма (написанные исключительно авторучкой), в которых подробно излагал основные идеи теории программирования, эти письма по просьбе автора Burroughs распространяла в программистских кругах. Естественно, взгляды Дейкстры принимались с уважением далеко не всегда, однако сейчас эти работы признаны классическими. На протяжении всей жизни Дейкстра отправил около 1300 писем, некоторые из которых вошли в сборник, опубликованный в 1982 г.

, - да, профессору Дейкстре знакомо и то, и другое. Терпя саркастические насмешки над своими идеями в начале карьеры (которой ученый отдал более 40 лет), он, в конце концов, получил всемирное признание научной общественности. Декстра был почетным заведующим кафедрой Computer Science Техасского ун членом Колевской Академии Нидерландов, Британского Компьютерного Общества (British Computer Society), Американской Академии Наук и Искусств. За многочисленные научные заслуги в 1972 г. он удостоился премии Алана Тьюринга, в 1982 г. получил премию Пионера Компьютерного Сообщества IEEE. В 2002 г. фонд C&C (Япония) выразил благодарность Дейкстре . И это далеко не весь список:

Дейкстра обладал незаурядным чувством юмора и едко критиковал неудавшиеся труды программистов. Однажды, к примеру, он назвал Фортран (FORTRAN) с двадцатилетним стажем, а APL - языком будущего для программистской техники прошлого. Эдсгер часто играл Моцарта на фортепиано, путешествовал с женой по национальным паркам в маленьком фургончике, названном и ко всем заслугам был отцом трех детей и дедушкой двух внуков. 6 августа 2002 г. ученый скончался от рака на родине, в Нидерландах. Что ж, нам остается лишь вспомнить слова, прозвучавшие на одной из церемоний в его адрес: [1]. 6 августа в своем доме в Нидерландах умер от рака. Дейкстра был выдающимся учёным, идеи которого оказали огромное влияние на развитие компьютерной индустрии. Ему было 72 года [5].

Научные достижения

Литературные труды

Помимо обсуждения специальных вопросов, в своих статьях и книгах Дейкстра последовательно отстаивал необходимость математического подхода к программированию, который предполагает предварительное точное, всестороннее математическое описание задачи и способа её решения, формальное доказательство правильности выбранного алгоритма и последующую реализацию алгоритма в виде максимально простой, структурированной программы, корректность которой должна быть формально доказана. По мнению Дейкстры, господствующий в компьютерной индустрии подход к программированию как к процессу достижения результата методом проб и ошибок порочен, поскольку стимулирует программистов не думать над задачей, а писать код, при этом совершенно не гарантирует корректность программ, которая не может быть доказана тестированием в принципе.

Влияние

Читайте также: