Эдсгер Дейкстра: в поисках «кратчайшего пути» к осознанному программированию

Алгоритм Дейкстры нахождения кратчайшего пути

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

Для решения указанной задачи можно использовать алгоритм Дейкстры — алгоритм на графах, изобретённый нидерландским ученым Э. Дейкстрой в 1959 году. Находит кратчайшее расстояние от одной из вершин графа до всех остальных. Работает только для графов без рёбер отрицательного веса.

Пусть требуется найти кратчайшие расстояния от 1-й вершины до всех остальных.

Кружками обозначены вершины, линиями – пути между ними (ребра графа). В кружках обозначены номера вершин, над ребрами обозначен их вес – длина пути. Рядом с каждой вершиной красным обозначена метка – длина кратчайшего пути в эту вершину из вершины 1.

Инициализация

Метка самой вершины 1 полагается равной 0, метки остальных вершин – недостижимо большое число (в идеале — бесконечность). Это отражает то, что расстояния от вершины 1 до других вершин пока неизвестны. Все вершины графа помечаются как непосещенные.

Первый шаг

Минимальную метку имеет вершина 1. Её соседями являются вершины 2, 3 и 6. Обходим соседей вершины по очереди.

Первый сосед вершины 1 – вершина 2, потому что длина пути до неё минимальна. Длина пути в неё через вершину 1 равна сумме кратчайшего расстояния до вершины 1 (значению её метки) и длины ребра, идущего из 1-й во 2-ю, то есть 0 + 7 = 7. Это меньше текущей метки вершины 2 (10000), поэтому новая метка 2-й вершины равна 7.

Аналогично находим длины пути для всех других соседей (вершины 3 и 6).

Все соседи вершины 1 проверены. Текущее минимальное расстояние до вершины 1 считается окончательным и пересмотру не подлежит. Вершина 1 отмечается как посещенная.

Второй шаг

Шаг 1 алгоритма повторяется. Снова находим «ближайшую» из непосещенных вершин. Это вершина 2 с меткой 7.

Снова пытаемся уменьшить метки соседей выбранной вершины, пытаясь пройти в них через 2-ю вершину. Соседями вершины 2 являются вершины 1, 3 и 4.

Вершина 1 уже посещена. Следующий сосед вершины 2 — вершина 3, так как имеет минимальную метку из вершин, отмеченных как не посещённые. Если идти в неё через 2, то длина такого пути будет равна 17 (7 + 10 = 17). Но текущая метка третьей вершины равна 9, а 9

Эдсгер Дейкстра: в поисках «кратчайшего пути» к осознанному программированию

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

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

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

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

Известность Дейкстре принесли его работы в области применения математической логики при разработке компьютерных программ. Он активно участвовал в разработке языка программирования Алгол и написал первый компилятор Aлгол-60. Будучи одним из авторов концепции структурного программирования, он проповедовал отказ от использования инструкции GOTO. Также ему принадлежит идея применения «семафоров» для синхронизации процессов в многозадачных системах и алгоритм нахождения кратчайшего пути на ориентированном графе с неотрицательными весами рёбер, известный как Алгоритм Дейкстры. В 1972 году Дейкстра стал лауреатом премии Тьюринга.

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

Дейкстра был активным писателем, его перу (он предпочитал авторучку клавиатуре) принадлежит множество книг и статей, самыми известными из которых являются книги «Дисциплина программирования» и «Заметки по структурному программированию», и статья «О вреде опе ратора GOTO» (GOTO considered harmful) — классические книги по теории структурного программирования.

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

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

Влияние

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

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

Дейкстра Эдсгер Вайб, специалист в области теоретического программирования

Эдсгер Вибе Дейкстра родился 11 мая 1930 года. Известен как нидерландский учёный, исследователь распределённых вычислений и формальной верификации, один из разработчиков концепции структурного программирования, его работы оказали влияние на развитие информационных технологий и информатики.

Биография

Эдсгер родился в г. Роттердам (Нидерланды).

Обучался в Лейденском университете на факультете теоретической физики. Программированием начал заниматься с 1951 года, закончил в Кембридже трёхнедельные компьютерные курсы. В 1952 году Дейкстра стал работать программистом в Математическом центре в Амстердаме. Его руководителем стал профессор Адриан ван Вейнгаарден, который впоследствии является автором двухуровневых грамматик ван Вейнгаардена – одного из способов формального описания грамматики формальных языков.

С этого же года Эдсгер Вайб уже принял решение окончательно связать свою деятельность с программированием, но заканчивает курс теоретической физики.

Дейкстра при поиске путей оптимизации разводки плат, во второй половине 1950-х годов разрабатывает алгоритм отыскания кратчайшего пути на графе, который стал известен под названием «алгоритм Дейкстры».

Готовые работы на аналогичную тему

С 1958 по 1960 год Дейкстра принимал активное участие в разработке языка программирования Алгол, работая в группе создания компилятора языка. Группа соревновалась с датской командой Петера Наура. Дейкстра дал клятву до завершения проекта не бриться и победил, так как написал компилятор за полтора месяца, при этом он изобрел «вызов по имени» – новое правило компиляции.

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

Долгое время Дейкстра работает в компании Burroughs.

В 1970-х годах совместно Никлаусом Виртом и Тони Хоаром Дейкстра разрабатывает основные положения структурного программирования.

Дейкстра преподает в Техасском университете до конца своих дней. Умер Эдсгер Дейкстра в возрасте 72 лет 6 августа 2002 года в г. Нюэнен (Нидерланды) от рака.

Задай вопрос специалистам и получи
ответ уже через 15 минут!

Научная деятельность

Дейкстра стал известен своими работами по применению математической логики в ходе разработки компьютерных программ. Являлся активным участником при разработке языка программирования Алгол и создателем первого компилятора Алгол-60.

Дейкстра, являясь одним из авторов концепции структурного программирования, продвигал идею отказа от использования инструкции GOTO. Является автором идеи применения «семафоров» с целью синхронизации процессов в многозадачных системах и алгоритма нахождения самого короткого пути на ориентированном графе, который стал известен как алгоритм Дейкстры.

Награды

Лауреат премии Тьюринга (1972 год).

Ежегодная премия за публикацию, которая оказала наибольшее влияние на область распределённых вычислений от Симпозиума по принципам распределённых вычислений Ассоциации вычислительной техники (2002 год). Начиная с 2003 года данная премия стала носить название премии Дейкстры в знак признания его заслуг.

Научные публикации

В своих трудах настаивал на необходимости математического подхода к программированию. Является автором нескольких книг и многих статей, среди которых:

«Заметки по структурному программированию»,
«Дисциплина программирования»,
«О вреде оператора GOTO».

Так и не нашли ответ
на свой вопрос?

Просто напиши с чем тебе
нужна помощь

Эдсгер Вайб Дейкстра

Поделитесь в соцсетях:

Эдсгер В. Дейкстра, родившийся 11 мая 1930 г., — третий ребенок в большой по
сегодняшним меркам семье (четверо детей). Его отец, по словам самого Эдсгера,
“был великолепным химиком”. Не надо пытаться объяснять столь сильный
эпитет, употребленный Э. В. Дейкстрой, сыновьими чувствами — Дав Вайб Дейкстра
(Дейкстра-старший) успешно совмещал работу преподавателя химии в средней школе
с изобретательской и научной деятельностью и… с должностью Президента Датского
Химического Сообщества. В воспоминаниях Э. В. Дейкстры подчеркивалось, что глубокие
знания его отца в области химии и физики сочетались с блестящими преподавательскими
способностями, на которые повысился спрос в условиях “идеализма после Второй
мировой войны” (здесь и далее по тексту в кавычках приводятся цитаты из разных
работ и воспоминаний Дейкстры). Учитывая, что и мать Эдсгера была математиком
и обладала “не столь энциклопедическими знаниями, как отец, но исключительно
быстрым умом… и любовью к элегантным решениям”, будущее Дейкстры-сына оказалось
предрешенным. И он сам собирался продлить семейную династию — стать школьным
учителем.

Читать еще: Пример работы с JAXB. Сохраняем Java объект в XML, восстанавливаем объект из XML

Но амбиции, свойственные юношескому возрасту, “загнали” Эдсгера в Роттердамский
университет — на факультет права. Будущий автор таких “компьютерно-народных”
слов и фраз, как “структурное программирование” и “тестирование
программ может выявить наличие ошибок, но не может служить доказательством их
отсутствия”, по окончании школы лелеял мечту… представлять Данию в Организации
Объединенных Наций. Правда, Провидение с юношеской мечтой поступило достаточно
жестко — вступительные экзамены были успешно провалены, и Эдсгеру ничего другого
не оставалось, кроме поступления в Лейденский университет на факультет теоретической
физики. Сам Дейкстра-младший об этом выборе говорил так: “Более старшие и
мудрые советовали мне, что куда безопаснее основывать свой выбор на способностях,
чем на идеализме”.

Университетские годы для Дейкстры, как и для всех жителей послевоенной Европы, были очень трудными — “мы были крайне бедны, очень тяжело работали, никогда не высыпались и часто не ели вдоволь”. Впрочем, такие трудности тогда людей уже не пугали. Постоянный подписчик журнала “Nature”, Дейкстра-старший, “высмотрел” в нем рекламу трехнедельных курсов программирования в Кембридже (на которых изучалась ЭВМ EDSAC) и предложил Эдсгеру поучиться дополнительно. “Я счел это хорошей идеей, потому что собирался стать лучшим физиком-теоретиком, и чувствовал, что умение использовать электронные вычислители в достижении такой цели будет полезным”, — так об этом вспоминал Э. Дейкстра. Но еще до сентября 1951 г. (в первые три недели именно этого сентября должны были проводиться курсы) будущая не менее знаменитая в компьютинге личность — ван Вингаарден (van Wijngaarden), прослышав о планах студента, пригласил его на работу в Математический Центр в Амстердаме. И с 1952 г. неудавшийся юрист и пока несостоявшийся физик-теоретик Дейкстра стал первым датчанином, получающим заработную плату по ведомости, в графе “профессия” которой стояло слово “программист”.

Совершенно новая по тем временам область деятельности оказалась настолько интересной, что Э. Дейкстра был поставлен перед выбором между изучением теоретической физики или программирования. “Я выбрал последнее, и физика стала формальностью. После получения степени в 1956 г. я немедленно переехал из Лейдена в Амстердам и с этого момента работал только в Математическом Центре”.

В воспоминаниях Дейкстры проскальзывает бесценная информация о том, как реально
развивалась европейская академическая наука в те нелегкие послевоенные годы. Оказывается,
тогда совершенно нормальным явлением была работа двух студентов-физиков Муниципального
университета Амстердама над созданием… компьютера для Математического Центра.
Именно в команду из двух “конструкторов” и попадает Дейкстра. В момент
прихода Эдсгера в Центр новый компьютер был неработоспособным, но “они много
учились, в том числе и тому, что когда в ходе проектирования совершено слишком
много ошибок, лучше всего начинать все с начала”. И первый датский программист
включается в проект создания “очередного компьютера”. Скупые строчки
воспоминаний Дейкстры об этом этапе могли бы стать образцом для подражания многим
“последователям-самодельщикам” (будь то программисты или разработчики
аппаратных средств): “Без всяких обсуждений дисциплины проектирования, что
могло бы показаться ужасным сегодня, мы начали с того, что написали руководство
программиста будущего компьютера, включающее полное функциональное описание машины
(по ряду причин, этим занимался я один). Данный документ использовался как контрактное
соглашение между мной и командой: они знали, что они должны проектировать, я знал,
что должен писать”. А теперь давайте удивимся — группе из трех молодых людей,
работающих в совершенно новой области, меньше чем за год удалось создать действующую
вычислительную машину во времена, когда в помине не было никаких микропроцессоров,
микросхем и систем автоматизированного проектирования!

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

Итак, самодельный компьютер заработал, получил название, и настало время продемонстрировать
его вычислительную мощь, для чего Дейкстра создает, по его словам, “свой
первый нетривиальный алгоритм”. Сегодня его знает любой человек, изучающий
курс программирования, — это знаменитый алгоритм поиска кратчайшего пути в графе.
Здесь сразу уместно будет привести несколько фрагментов из воспоминаний Дейкстры.
Во-первых, алгоритм этот создавался не из простого любопытства, а для решения
вполне конкретной задачи, а именно, — минимизации длины проводников на аналоге
“материнской платы” нового разрабатываемого командой компьютера X1,
так что лавровый венок создателя первой “утилиты всех времен и народов”
класса CAD-CAE Дейкстре можно присваивать смело. А вот “во-вторых” лучше
сказать словами самого Дейкстры: “На много лет и в широких кругах алгоритм
поиска кратчайшего пути был основным источником моей славы, что мне всегда казалось
странным — ведь он был создан даже без карандаша и бумаги, за чашкой кофе на
солнечной террасе кафе в Амстердаме, в качестве демонстрации решения проблемы
с X1 для моей жены …”.

Очередному компьютеру-самоделке X1 мы косвенно обязаны не только самым известным алгоритмом Дейкстры. “Департамент проектирования аппаратных средств” в лице двух авторов за тяжелых три месяца добился от Главного Разработчика Архитектуры (в лице Э. Дейкстры) согласия на реализацию системы прерываний реального времени. Ведущий архитектор боялся ухода из-под ног детерминизма в поведении будущей машины, конструкторы же настаивали: “Мы понимаем, что это сделает решение ваших задач невообразимо трудным, но кто-то вроде вас должен справляться и с такими трудностями”. В конце концов Дейкстра идет на уступку, которая оборачивается для него докторской степенью. Именно вопросу построения такой сегодня обыденной (но и такой далекой от простоты) программной подсистемы — обработчику прерываний реального времени — и была посвящена докторская диссертация Дейкстры. Защита диссертации по времени почти совпала с первой публикацией знаменитого алгоритма в первом выпуске первого датского “компьютерного” журнала “Numerische Mathematik” в 1959 г.

программирование — одна из наиболее трудных областей прикладной математики;
чистым математикам в ней делать нечего — пусть лучше занимаются чистой математикой;

простейший вид приложений — это технические и научные вычислительные задачи;

инструменты, которые мы используем, определяют наши мыслительные возможности
и, таким образом, мыслительные способности;

об использовании языка программирования можно сказать так: невозможно остро
отточить карандаш тупым топором и уж совершенно тщетно пытаться выполнить
эту задачу десятью тупыми топорами;

простота — это необходимое условие надежности;

использование антропоморфной терминологии в отношении компьютеров — симптом
профессиональной незрелости.

Период “компьютерных самоделок” буквально осязаем в самом “фривольном”
эпистолярном наследии Дейкстры. Его резкие высказывания (в том числе и в адрес
общепринятых грандов компьютерной индустрии) стали классикой нового жанра — “компьютерного
юмора”: “Проект IBM 360 был намного эффективнее Манхеттенского проекта
(в рамках которого создавались первые атомные бомбы. — Прим. автора статьи)
— при равных затратах он обладал большей поражающей способностью”, “Ожидание
— это самый забавный вид деятельности, потому что вы не можете ожидать в два
раза быстрее”, “Computer Science имеет такое же отношение к изучению
компьютеров, как астрономия к изучению телескопов”. Что тут можно сказать…
Когда три человека проходят фактически самостоятельно по еще нехоженому пути и
добиваются впечатляющих результатов, им многое простительно. Тем более, когда
это “многое” базируется на энциклопедических знаниях и огромном опыте.

С лета 1959 г. Дейкстра начинает работать над еще одним проектом, плоды которого неразрывно ассоциируются с его именем. Конечно же, речь идет о языке Algol 60 — прародителе подавляющего большинства современных массово-распространенных языков программирования (которые в честь этого пусть не всегда явного родства называют “алголоподобными”). “По ходу дела” (именно так он относится к этим фактам в своих воспоминаниях) Дейкстра создает способы реализации рекурсивных программ, самостоятельно разрабатывает основу процесса трансляции — использование механизма стека для преобразования выражений в тогда еще безымянную “обратную польскую запись” (это название появилось значительно позже). Сегодня эти маленькие открытия никого не удивляют, но тогда, в 1959 г., они были далеко не такими маленькими, и с публикацией в 1960 г. статьи “Рекурсивное программирование” лексикон программистов пополнился двумя новыми словами: “стек” и “рекурсия”, изобретенными Дейкстрой…

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

Работа над первым компилятором Algol 60 для компьютера X1 велась в такой атмосфере,
что каждый участник проекта каждый день забирал с собой домой все материалы по
проекту… на случай пожара в лаборатории. Пожар, естественно, не случился. А
вот результатам работы на Algol мы прямо или косвенно обязаны фундаментальным
понятиям мультипрограммирования, усовершенствованным фактически до современного
уровня в рамках следующего проекта с активнейшим участием Дейкстры — операционной
системы THE. “Создавая THE, мы знали, что творим историю, потому что это
была первая в мире ОС, основанная на независимых синхронизируемых взаимодействующих
процессах с защитой от тупиковых ситуаций (дедлоков)”. Дейкстра в этой фразе
умолчал о главном — по-настоящему исторический характер THE проявился тогда,
когда стало слишком очевидным несоответствие между крохотной командой разработчиков
и масштабами задачи.

Почти полгода Дейкстра пребывал в “задумчивой депрессии” и, наконец, в качестве терапии… написал “Заметки о структурном программировании”. Разосланные друзьям всего лишь 20 копий “Заметок…” сделали то, что мы называем Историей. Они начали эпоху Структурного Программирования.

Читать еще: Amcpromote что это за программа?

Впоследствии, уже работая в знаменитых своими условиями для академических ученых лабораториях компании Burroughs, Дейкстра издал одну из лучших (а может быть и вообще лучшую) книг по программированию, ставшую настольной для нескольких поколений программистов. Порядок, который внесла методология структурного программирования в наш беспорядочный мир, трудно переоценить — слава Богу и Дейкстре, но баллистические ракеты непроизвольно не стартуют из своих шахт, бортовая электроника автомобилей не “взбрыкивает” при движении, грубые ошибки систем управления воздушным движением по вине программ — редкость. И все это длится десятилетиями…

Пик популярности работ Эдсгера Вайб Дейкстры, пришедшийся на середину 70-х годов,
сегодня прошел. Модой и умами правят совсем другие имена. И все-таки… автору
статьи кажется, что изучение “Дисциплины программирования” — как минимум
необходимое условие для того, чтобы записанная в ведомости на получение зарплаты
должность “программист” выглядела достойной имени первого датского программиста.

Научные дисциплины имеют некоторый “размер”, определяемый человеческими
константами: необходимая сумма знаний должна умещаться в человеческой голове,
число необходимых умений должно быть не больше того, чему человек может научиться
и в дальнейшем не терять полученных навыков. С другой стороны, научная дисциплина
не должна быть слишком маленькой или слишком узкой, чтобы она не исчерпалась в
течение по крайней мере одного поколения. Но не любой набор отрывочных фактов
или небывалых умений, даже достаточного размера, составляет живую научную дисциплину!
Есть еще два требования. Внутреннее требование соответствия: умение должно позволять
накапливать знания, а знания — совершенствовать умения. И наконец, есть внешнее
требование (мы назовем его “узким интерфейсом”) — сущность дисциплины
допустимо изучать в достаточно высокой степени изолированности, чтобы она не зависела
в каждый момент критически от развития других областей науки.

ЭДСГЕР ДЕЙКСТРА “Смиренный” программист

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

Один из тех людей, с именем которых связано превращение программирования из шаманства в науку, — Эдсгер Дейкстра. Профессиональный словарь программиста полон слов, введенных или предложенных Э. В. Дейкстрой, — “дисплей”, “мертвая хватка”, “семафор”, “программирование с минимумом операторов go to”, “структурное программирование”. Однако его влияние на программирование является более всепроникающим. Ценнейший вклад Дейкстры — его стиль: подход к программированию как к высокому искусству и интеллектуальному творчеству, настойчивые требования и практическая демонстрация того, что программы должны быть с самого начала правильно составлены, а не просто отлаживаться до тех пор, пока не станут правильными; ясное понимание того, какие проблемы лежат в основе программирования. Во всех своих исследованиях Дейкстра придает большое значение простоте и изяществу математических рассуждений. При написании своих работ он создал новый стиль научных и технических сообщений, который можно описать как нечто среднее между журнальными публикациями и дружеской перепиской.

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

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

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

Однако одной из проблем, с которой он столкнулся, было то, что к тому времени программирование еще не было официально признано профессией. (Когда он подавал документы для регистрации брака в 1957 году, ему пришлось написать в качестве своей профессии “физик-теоретик”.) Все первые автоматические электронные компьютеры были уникальными, построенными в единственном экземпляре машинами, очень громоздкими и действительно фантастическими. Поэтому несчастных программистов едва замечали. По мере того как мощность машин возросла более чем в тысячу раз, честолюбивые замыслы общества, связанные с применением этих машин, росли в той же пропорции, и именно несчастный программист обнаружил, что его работа оказалась в поле зрения между целями и средствами. Тогда, в середине 60-х годов, случилось нечто ужасное: появились компьютеры так называемого третьего поколения. Когда о таких ЭВМ было объявлено и стали известны их функциональные спецификации, многим из программистов стало не по себе; по крайней мере, такое чувство возникло у Эдсгера Дейкстра. Было естественно ожидать, что такие вычислительные машины хлынут потоком на компьютерный рынок, и следовало ожидать, что их организация будет более разумной. Но проект содержал такие серьезные ошибки, что Дейкстра почувствовал, что одним ударом прогресс в информатике был заторможен по меньшей мере лет на десять. Это была самая черная неделя во всей его профессиональной карьере. Вот, что говорил он по этому поводу: “Быть может, печальнее всего то, что после всех этих лет разочаровывающего опыта многие все еще честно верят в то, что в силу некоторого закона природы машины должны быть именно такими”.

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

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

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

Третьим проектом, о котором упоминает Дейкстра, является LISP. На использовании LISP основаны многие в некотором смысле наиболее изощренные программные продукты. В шутку LISP описывался как “наиболее интеллигентный способ злоупотребления компьютером”. Дейкстра считал, что подобная характеристика является большим комплиментом, поскольку она передает всю полноту освобождения: LISP помогает многим из наиболее одаренных программистов мыслить о вещах, ранее считавшихся немыслимыми.

Четвертым проектом был ALGOL-60. В то время как определение LISP до сих пор остается причудливой мешаниной из того, что язык означает, и того, как он работает, знаменитое “Сообщение об алгоритмическом языке ALGOL-60” является плодом подлинных усилий перейти на следующий уровень абстрактности и определить язык программирования способом, не зависящим от его реализации.

Это все было в прошлом. Однажды Дейкстра набросал один из вариантов будущего развития программного обеспечения. “Картина такова, что еще до завершения семидесятых мы сможем изобрести и реализовать системы такого рода, которые сейчас находятся на пределе наших возможностей программировать, и затратить на них лишь несколько процентов тех усилий, которых они требуют ныне, и, кроме того, эти системы будут практически свободными от ошибок. Такая решительная перемена за такой короткий период времени была бы революцией. Но на сколько вероятно, что эта революция произойдет? По-видимому, надо, чтобы выполнились три основных условия. Весь мир должен признать необходимость перемены; во- вторых, экономическая необходимость этой перемены должна быть достаточно сильной; и, в-третьих, эта перемена должна быть технически выполнимой”. Поворотной точкой была Конференция по технике программного обеспечения в Гармише в октябре 1968 года. Эта конференция стала сенсационной, когда на ней впервые был открыто признан кризис программного обеспечения. Поэтому первое условие Дейкстра считал выполненным.

Читать еще: Как выключить iphone 5 без кнопки power?

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

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

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

Третий довод основан на конструктивном подходе к проблеме правильности программы. Единственный эффективный способ значительно повысить доверие к программе — это дать убедительное доказательство правильности. Программист должен доказывать правильность программы одновременно с ее написанием.

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

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

И последним доводом в пользу технической реализуемости революции он привел широкую применимость хорошо разложимых на компоненты решений.

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

Проф. М. Гуда и проф. Э. Дейкстра в Техническом университете Эйндховена

Многим программистам Дейкстра известен как создатель алгоритма “кратчайшего пути”, предложенного им еще в 1952 году, который появился в результате его работы над задачей по оценке производительности компьютера ARCMAC, установленного в Математическом Центре. Этот алгоритм позволяет находить наилучший путь для перемещения между двумя точками. Ученый также использовал этот алгоритм для решения задачи “О нахождении оптимального пути передачи электрического тока всем существенным элементам цепи, минимизируя при этом расход меди”, с которой столкнулись инженеры, разрабатывавшие ARCMAC. Он назвал этот способ “алгоритмом дерева с кратчайшими ветвями”. В начале 60-х годов Дейкстра применил идею взаимного исключения к технологии связи между компьютером и его клавиатурой. Он использовал символы Р и V для представления двух операций, производимых в задаче взаимного исключения. Эта идея стала частью практически всех современных процессоров и модулей памяти, начиная с 1964 года, когда IBM впервые использовала ее в своей архитектуре IBM/360. Он помог программной индустрии стать намного более дисциплинированной, выдвинув тезис, что оператор “go to является вредным”. Это означало, что чем больше в программе операторов go to, тем труднее разобраться в исходном коде программы. Эдсгер Дейкстра стоял у истоков структурного программирования. В 1972 году он вместе с Оле Далом и Тони Хоаром опубликовал основополагающую монографию “Структурное программирование”.

Дейкстра продолжал работу в Математическом Центре до тех пор, пока в начале 70-х годов не перешел на работу исследователем в корпорацию Burroughs в США. В 1972 году ACM наградила Дейкстра премией Тьюринга (ACM Turing Award). В 1974 году AFIPS удостоила его памятной наградой Гарри Гуда (AFIPS Налу Goode Memorial Award). В начале 1980-х годов Дейкстра переехал в Остин, штат Техас. В 1984 году он был назначен деканом факультета компьютерных наук в Техасском университете.

Эдсгер Вайб Дейкстра является Почетным Иностранным членом Американской Академии гуманитарных, естественных и технических наук. Он также является членом Голландской королевской Академии наук, действительным членом Британского Компьютерного Общества и, наконец, доктором наук Королевского университета в Белфасте.

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

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

Дейкстра, Эдсгер Вибе

Национальный исследовательский институт математики и информатики
Технический Университет Эйндховена
Техасский университет в Остине

создатель алгоритма Дейкстры и семафоров
один из основателей структурного программирования
один из создателей операционной системы THE

Э́дсгер Ви́бе Де́йкстра (нидерл. Edsger Wybe Dijkstra [ˈɛtsxər ˈwibə ˈdɛɪkstra] прослушать) (11 мая 1930, Роттердам Нидерланды — 6 августа 2002, Нуенен, Нидерланды) — нидерландский учёный, идеи которого оказали влияние на развитие компьютерной индустрии.

Содержание

Биография

Родился 11 мая 1930 года в Роттердаме, в семье учёных (отец — химик, мать — математик). По окончании школы поступил на факультет теоретической физики Лейденского университета. В 1951 году увлёкся программированием, поступил на трёхнедельные компьютерные курсы в Кембридже, с 1952 года работал программистом в Математическом центре Амстердама под руководством профессора Адриана ван Вейнгаардена, впоследствии — автора одного из способов формального описания грамматики формальных языков — так называемых двухуровневых грамматик Ван Вейнгаардена. Уже в 1952 году принял решение окончательно специализироваться на программировании, но курс теоретической физики закончил. В 1956 году принял участие в разработке ЭВМ X1. [источник не указан 535 дней] Эта машина была создана тремя энтузиастами за год. Именно для оптимизации разводки плат для X1 был придуман алгоритм поиска кратчайшего пути на графе, известный как «алгоритм Дейкстры».

В 1957 году Дейкстра женился. Как вспоминал он сам, в графе «профессия» анкеты, которую положено заполнять при бракосочетании, он написал «программист» — и его заставили переписывать документы, заявив, что такой профессии не существует. В результате, как писал Дейкстра: «Хотите — верьте, хотите — нет, но в графе „профессия“ моего свидетельства о браке значится забавная запись „физик-теоретик“!» [1] .

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

Длительное время работал в компании Burroughs (англ. Burroughs Corporation ). В 1970-е годы вместе с Тони Хоаром и Никлаусом Виртом разработал основные положения структурного программирования.

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

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

Известность Дейкстре принесли его работы в области применения математической логики при разработке компьютерных программ. Он активно участвовал в разработке языка программирования Алгол и написал первый компилятор Алгол-60. Будучи одним из авторов концепции структурного программирования, он «проповедовал» отказ от использования инструкции GOTO. Также ему принадлежит идея применения «семафоров» для синхронизации процессов в многозадачных системах и алгоритм нахождения кратчайшего пути на ориентированном графе с неотрицательными весами рёбер, известный как Алгоритм Дейкстры. В 1972 году Дейкстра стал лауреатом премии Тьюринга.

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

Дейкстра был активным писателем, его перу (он предпочитал авторучку клавиатуре) принадлежит множество книг и статей, самыми известными из которых являются книги «Дисциплина программирования» и «Заметки по структурному программированию», и статья «О вреде оператора GOTO» (GOTO considered harmful) — классические книги по теории структурного программирования.

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

Влияние

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

голоса

Рейтинг статьи