Эдсгер В. Дейкстра - Википедия - Edsger W. Dijkstra

Эдсгер В. Дейкстра
Дейкстра в 2002 году
Родившийся	(1930-05-11)11 мая 1930 г. Роттердам, Нидерланды
Умер	6 августа 2002 г.(2002-08-06) (72 года) Nuenen, Нидерланды
Гражданство	Нидерланды
Образование	Лейденский университет (B.S., M.S.) Амстердамский университет (Кандидат наук.)
Известен	Смотри ниже
Награды	Выдающийся вклад SIGCSE (1989) Премия Тьюринга (1972) Член ACM (1994) Премия Дейкстры (2002)
Научная карьера
Поля	Информатика Теоретическая информатика
Учреждения	Mathematisch Centrum Эйндховенский технологический университет Корпорация Берроуз Техасский университет в Остине
Тезис	Связь с автоматическим компьютером (1959)
Докторант	Адриан ван Вейнгаарден
Докторанты	Нико Хаберманн Ян ван де Снепшют
Влияния	Адриан ван Вейнгаарден
Под влиянием	Тони Хоар[1] Никлаус Вирт[2][3] Пер Бринч Хансен[4] Лесли Лэмпорт[5][6] Шломи Долев[7] Александр Степанов[8] Дэвид Грис Давид Парнас

Эдсгер Вайбе Дейкстра (/ˈdаɪksтрə/ ДАЙК-strə; Нидерландский язык:[ˈƐtsxər ˈʋibə ˈdɛikstra] (Слушать); 11 мая 1930 - 6 августа 2002) был голландцем специалист в области информатики, программист, инженер-программист, системный ученый, наука эссеист,^[9][10] и пионер информатики.^[11] А физик-теоретик по образованию работал программист на Mathematisch Centrum (Амстердам) с 1952 по 1962 год. Будучи профессором университета на протяжении большей части своей жизни, Дейкстра занимал столетнюю кафедру компьютерных наук в Университете Шлюмберже. Техасский университет в Остине с 1984 г. до выхода на пенсию в 1999 г. Он был профессором математики в Эйндховенский технологический университет (1962–1984) и научный сотрудник на Корпорация Берроуз (1973–1984). В 1972 году он стал первым неамериканцем, небританцем и континентальный европейский победитель Премия Тьюринга.

Одна из самых влиятельных фигур в поколении основателей компьютерной науки,^{[2][3][5][6][12][13]} Дейкстра помог сформировать новую дисциплину как из инженеров, так и из инженеров. теоретическая перспектива.^[14][15] Его фундаментальный вклад охватывает различные области вычислительной науки, в том числе конструкция компилятора, операционные системы, распределенные системы, последовательное и параллельное программирование, парадигма и методология программирования, исследование языка программирования, дизайн программ, разработка программ, проверка программ, принципы программной инженерии, алгоритмы графов и философские основы компьютерного программирования и информатики. Многие из его работ являются источником новых направлений исследований. Некоторые концепции и проблемы, которые сейчас являются стандартными в компьютерных науках, были впервые определены Дейкстрой и / или носят названия, придуманные им.^[16][17] Будучи ярым противником механизированного взгляда на компьютерную науку, он опроверг использование концепций «информатика» и «программная инженерия» в качестве общих терминов для академические дисциплины.^{[нужна цитата ]}

До середины 1960-х гг. компьютерное программирование считалось скорее искусством (или ремеслом), чем научной дисциплиной. В Харлан Миллс По словам (1986), «программирование [до 1970-х годов] рассматривалось как частное занятие по решению головоломок по написанию компьютерных инструкций для работы как программы». В конце 1960-х годов компьютерное программирование находилось в состояние кризиса. Дейкстра был одним из небольшой группы ученых и промышленных программистов, которые выступали за новый стиль программирования для улучшения качества программы. Дейкстра, имевший образование в области математики и физики, был одной из движущих сил принятия компьютерного программирования в качестве научной дисциплины.^[18][19] Он придумал фразу "структурное программирование "и в течение 1970-х годов это стало новой ортодоксией программирования.^[20][21][22] Его идеи о структурном программировании помогли заложить основы для зарождения и развития профессиональной дисциплины программная инженерия, позволяя программистам организовывать все более сложные программные проекты и управлять ими.^[23][24] В качестве Бертран Мейер (2009) отметил: «Революция во взглядах на программирование, начатая иконоборчеством Дейкстры, привела к движению, известному как структурное программирование, которое отстаивало систематический, рациональный подход к построению программ. Структурированное программирование является основой всего, что было сделано с тех пор, как методология программирования, включая объектно-ориентированного программирования."^[25]

Академическое исследование параллельные вычисления началась в 1960-х годах, когда Дейкстра (1965) считается первой статьей в этой области, выявившей и решающей взаимное исключение проблема.^[5][26] Он также был одним из первых пионеров исследований принципов распределенных вычислений. Его фундаментальная работа по параллелизм, семафоры, взаимное исключение, тупик (смертельные объятия), находя кратчайшие пути в графах, Отказоустойчивость, самостабилизация, среди многих других вкладов включает в себя многие из столпов, на которых построена область распределенных вычислений. Незадолго до своей смерти в 2002 году он получил ACM Премия PODC Influential-Paper в распределенных вычислениях за его работу по самостабилизации программных вычислений. Эта ежегодная премия была переименована в Премия Дейкстры (Премия Эдсжера В. Дейкстры в области распределенных вычислений) в следующем году.^[27] В качестве приза, спонсируемого совместно Ассоциация вычислительной техники (ACM) Симпозиум по принципам распределенных вычислений (PODC) и Европейская ассоциация теоретической информатики (EATCS) Международный симпозиум по распределенным вычислениям (DISC) признает, что «Ни один другой человек не оказал большего влияния на исследования принципов распределенных вычислений».

биография

Ранние годы

Эдсгер В. Дейкстра родился в Роттердам. Его отец был химиком, президентом Голландского химического общества; он преподавал химию в средней школе, а позже был ее заведующим. Его мать была математиком, но никогда не имела формальной работы.^[28][29]

Дейкстра рассматривал карьеру юриста и надеялся представлять Нидерланды в Объединенные Нации. Однако после окончания школы в 1948 году по предложению родителей он изучал математику и физику, а затем теоретическая физика на Лейденский университет.^[14]

В начале 1950-х гг. электронные компьютеры были новинкой. Дейкстра наткнулся на свою карьеру совершенно случайно, и через своего научного руководителя, профессора А. Хантьеса, он познакомился с Адриан ван Вейнгаарден, директор вычислительного отдела Математический центр в Амстердаме, который предложил Дийкстре работу; он официально стал первым «программистом» Нидерландов в марте 1952 года.^[14]

Некоторое время Дейкстра оставался приверженцем физики, работая над ней в Лейден три дня в неделю. Однако по мере того, как все больше и больше приходилось заниматься компьютерами, его внимание начало смещаться. Как он вспоминал:^[30]

После трехлетнего программирования, я поговорил с А. ван Вейнгаарден, который тогда был моим начальником в Математический центр в Амстердаме, обсуждение, за которое я буду благодарен ему до тех пор, пока жив. Дело в том, что я должен был одновременно изучать теоретическую физику в Лейденском университете, и, поскольку мне было все труднее и труднее совмещать эти два занятия, мне пришлось принять решение: либо прекратить программировать, либо стать настоящим уважаемым человеком. физик-теоретик, или довести мое изучение физики только до формального завершения, с минимальными усилиями, и стать ....., да что? А программист ? Но была ли это респектабельная профессия? В конце концов, что было программирование ? Где тот объем знаний, который мог бы поддержать его как интеллектуально уважаемую дисциплину? Я очень хорошо помню, как я завидовал своим коллегам по аппаратному обеспечению, которые, когда их спросили об их профессиональной компетенции, могли хотя бы указать, что они знают все об электронных лампах, усилителях и прочем, тогда как я чувствовал, что, столкнувшись с этим вопросом, я стоял бы с пустыми руками. Полный опасений, я постучал в дверь офиса Ван Вейнгаардена, спрашивая его, могу ли я «поговорить с ним на минутку»; когда несколько часов спустя я вышел из его офиса, я был другим человеком. После того, как он терпеливо выслушал мои проблемы, он согласился, что до этого момента не было особой дисциплины программирования, но затем он продолжил тихо объяснять, что автоматические компьютеры должны остаться, что мы были только в начале и могли Разве я не один из тех, кто призван сделать программирование респектабельной дисциплиной в ближайшие годы? Это был поворотный момент в моей жизни, и я как можно быстрее закончил формальное изучение физики.

— Эдсгер Дейкстра, скромный программист (EWD340), Коммуникации ACM

Когда Дейкстра женился на Марии (Риа) Ч. Дебетс в 1957 году, в рамках брачных обрядов от него требовалось заявить о своей профессии. Он заявил, что является программистом, что неприемлемо для властей, поскольку тогда в Нидерландах такой профессии не было.^[30][31]

В 1959 году он получил докторскую степень в Амстердамский университет за диссертацию «Связь с автоматическим компьютером», посвященную описанию язык ассемблера разработан для первого коммерческого компьютера, разработанного в Нидерландах, X1. Его научным руководителем был Ван Вейнгаарден.^[16]

Mathematisch Centrum, Амстердам

С 1952 по 1962 год Дейкстра работал в Mathematisch Centrum в Амстердаме,^[16] где он работал в тесном сотрудничестве с Брэм Ян Лупстра и Карел С. Шолтен, которого наняли для сборки компьютера. Их способ взаимодействия был дисциплинированным: они сначала выбирали интерфейс между оборудованием и программным обеспечением, написав руководство по программированию. Тогда разработчики оборудования должны будут выполнять свою часть контракта, а программист Дийкстра будет писать программное обеспечение для несуществующей машины. Из этого опыта он извлек два урока: важность четкой документации и то, что отладки программы можно в значительной степени избежать путем тщательного проектирования.^[14]Дейкстра сформулировал и решил проблема кратчайшего пути для демонстрации на официальном открытии компьютера ARMAC в 1956 году. Из-за отсутствия журналов, посвященных автоматическим вычислениям, он не публиковал результаты до 1959 года.

В Математическом центре Дейкстра и его коллега Яап Зонневельд [нл ] разработал первый компилятор для языка программирования АЛГОЛ 60 к августу 1960 года, более чем за год до того, как компилятор был выпущен другой группой.^[14] Это оказало глубокое влияние на его более поздние представления о программировании как о научной деятельности.

Эйндховенский технологический университет

В Эйндховенский технологический университет, находится в Эйндховен на юге Нидерландов, где Дейкстра был профессором математики с 1962 по 1984 год.

В 1962 году Дейкстра переехал в Эйндховен, а позже Nuenen, на юге Нидерландов, где он стал профессором кафедры математики в Эйндховенский технологический университет.^[16] В университете не было отдельного факультета информатики, и культура математического факультета его не особо устраивала. Дейкстра пытался создать группу компьютерных ученых, которые могли бы совместно решать проблемы. Это была необычная модель исследования для математического факультета.^[14] В конце 1960-х он построил Операционная система (назван в честь университета, тогда известного как Technische Hogeschool Эйндховен ), что повлияло на дизайн последующих операционные системы за счет использования программной выгружаемой виртуальной памяти.^[32]

Корпорация Берроуз

Дийкстра присоединился Корпорация Берроуз, компания, известная тогда производством компьютеров на основе инновационной аппаратной архитектуры, поскольку ее научный сотрудник в августе 1973 года. В его обязанности входило посещение некоторых исследовательских центров фирмы несколько раз в год и проведение собственных исследований, которые он проводил в самом маленьком исследовательском центре Берроуза, а именно в своем кабинете на втором этаже своего дома в Нуэнене. . Фактически, Дейкстра был единственным научным сотрудником Берроуза и работал на него из дома, иногда путешествуя по его филиалам в Соединенных Штатах. В результате он сократил время приема в университете до одного дня в неделю. Этот день, вторник, вскоре стал известен как день знаменитого «Дневного клуба вторника», семинара, в ходе которого он обсуждал со своими коллегами научные статьи, рассматривая все аспекты: обозначения, организацию, представление, язык, содержание и т. Д. после переезда в 1984 г. в Техасский университет в Остине (США), в г. Остин, Техас.^[16]

Годы Берроуза были наиболее плодотворными в плане публикации исследовательских статей. Он написал около 500 документов серии EWD (описанных ниже), большинство из которых являются техническими отчетами, для частного распространения внутри избранной группы.^[14]

Техасский университет в Остине

В Техасский университет в Остине, где Дейкстра возглавлял столетнюю кафедру компьютерных наук Schlumberger с 1984 по 1999 год.

Дейкстра принял кафедру столетия Schlumberger на факультете компьютерных наук в Техасский университет в Остине в 1984 г.

В последние годы

Дейкстра работал в Остин до выхода на пенсию в ноябре 1999 года. Чтобы отметить это событие и отметить его сорок с лишним лет плодотворного вклада в вычислительная наука, Департамент компьютерных наук организовал симпозиум, который состоялся в день его 70-летия в мае 2000 года.^[14]

Дийкстра и его жена вернулись из Остина в свой прежний дом в Nuenen (Нидерланды), где он обнаружил, что ему осталось жить всего несколько месяцев. Он сказал, что хочет уйти на пенсию в Остине, Техас, но умереть в Нидерландах. Дейкстра умер 6 августа 2002 года после долгой борьбы с раком.^[33] У него и его жены Марии (Риа) Дебетс остались трое детей: Маркус, Фемке и компьютерный ученый Рутгер М. Дейкстра.

Новаторский вклад и влияние на вычислительную науку

Из физика-теоретика по образованию Дейкстра стал одной из самых влиятельных фигур в поколении основоположников компьютерной науки.^{[2][3][5][6][7][8][12][13]} Как пионер во многих областях компьютерной науки, он помог формировать новую дисциплину от инженеров и академическая перспектива. Многие из его работ являются источником новых направлений исследований. Многие концепции, которые сейчас являются стандартными в компьютерных науках, были впервые определены Дейкстрой и / или носят названия, придуманные им. Он также впервые сформулировал и решил несколько важных задач. В 1994 году был проведен опрос более тысячи профессоров информатики, чтобы получить список из 38 наиболее влиятельных научных работ в этой области, и Дейкстра является автором пяти работ.^[12][34][13] В возрасте 42 лет он стал первым неамериканцем, небританцем и континентальный европейский победитель Премия Тьюринга.

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

Его главный новаторский вклад (включая идеи, изобретения и инновации) включает:

• Алгоритмы: Алгоритм Дейкстры, Алгоритм DJP, Алгоритм Дейкстры-Шолтена, Алгоритм Деккера (обобщение), алгоритм банкира, гладкая сортировка, маневровый алгоритм, алгоритм трехцветной маркировки, параллельные алгоритмы, распределенные алгоритмы, алгоритмы предотвращения тупиковых ситуаций, алгоритмы взаимного исключения, самостабилизирующиеся алгоритмы

• Концепции, методы, принципы и теории: АЛГОЛ 60 выполнение, стек вызовов, параллелизм, параллельное программирование, взаимодействующие последовательные процессы, критическая секция, смертельные объятия (тупик ), проблема обедающих философов, Проблема национального флага Нидерландов, отказоустойчивые системы, программирование без использования goto, охраняемый командный язык (охраняемые команды ), слоистая структура в программная архитектура, уровни абстракции, многопоточное программирование, взаимное исключение (мьютекс или же замок ), проблема производитель – потребитель (проблема ограниченного буфера ), программные семьи, семантика преобразователя предикатов, синхронизация процессов, самостабилизирующиеся распределенные системы (самостабилизация ), семафор, разделение проблем, проблема спящего парикмахера, структурированный анализ, структурное программирование, Мультипрограммная система, неограниченный недетерминизм, исчисление самого слабого предусловия

Алгоритмическая работа

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

Алгоритмическая работа Дейкстры (особенно графовые алгоритмы, параллельные алгоритмы, и распределенные алгоритмы ) играет важную роль во многих областях вычислительной науки. В соответствии с Лесли Лэмпорт (2002), Dijkstra "начал область параллельных и распределенные алгоритмы в своей статье CACM 1965 года «Решение проблемы в управлении параллельным программированием», в которой он впервые сформулировал и решил проблему взаимного исключения. «Как объясняет Лэмпорт,« эта статья, вероятно, объясняет, почему PODC существуют (...). Это по сей день самая влиятельная газета в этой области. Что он не выиграл Премия PODC Influential Paper Award отражает искусственное разделение параллельных и распределенных алгоритмов - разделения, которого никогда не существовало в работе Дейкстры ».^[5]

В 1959 году Дейкстра опубликовал в трехстраничной статье «Заметка о двух проблемах, связанных с графами» алгоритм найти кратчайший путь в графе между любыми двумя заданными узлами, теперь называемый Алгоритм Дейкстры. Его влияние на следующие 40 лет резюмируется в статье Миккель Торуп, «Ненаправленные кратчайшие пути от одного источника с положительными целочисленными весами за линейное время» (1999): «С 1959 года все теоретические разработки в SSSP [Кратчайшие пути от одного источника] для общих ориентированных и неориентированных графов были основаны на алгоритме Дейкстры». В SPF используется алгоритм Дейкстры, Кратчайший путь сначала, который используется в протоколах маршрутизации OSPF и IS-IS. Различные модификации алгоритма Дейкстры были предложены многими авторами с использованием эвристика сократить время работы поиск кратчайшего пути. Одним из наиболее часто используемых эвристических алгоритмов является Алгоритм поиска A * (впервые описано Питер Харт, Нильс Нильссон и Бертрам Рафаэль из Стэнфордский исследовательский институт в 1968 г.),^[35] Основная цель - сократить время выполнения за счет уменьшения пространства поиска. Дейкстра подумал о проблема кратчайшего пути при работе в Математический центр в Амстердаме в 1956 году как программист продемонстрировать возможности нового компьютер названный ARMAC. Его цель состояла в том, чтобы выбрать как проблему, так и ответ (который мог бы выдать компьютер), которые могли бы понять некомпьютерные люди. Он разработал алгоритм кратчайшего пути примерно за 20 минут без помощи бумаги и ручки, а затем реализовал его для ARMAC для немного упрощенной транспортной карты 64 городов в Нидерландах (так что 6 битов было бы достаточно для представления города в алгоритме).^[29] Как он напомнил, в интервью, опубликованном в 2001 году:^[36]

Какой самый короткий способ добраться из Роттердама в Гронинген, в общем: из данного города в данный город? Это алгоритм кратчайшего пути, который я разработал примерно за двадцать минут. Однажды утром я ходил по магазинам в Амстердаме с моей молодой невестой, и, уставшие, мы сели на террасе кафе, чтобы выпить чашку кофе, и я просто думал, смогу ли я это сделать, и затем разработал алгоритм кратчайшего пути. . Как я уже сказал, это было двадцать минутное изобретение. Фактически, он был опубликован в 59-м, с опозданием на три года. Публикация по-прежнему читабельна, на самом деле довольно симпатичная. Одна из причин, по которой он такой красивый, заключалась в том, что я разработал его без карандаша и бумаги. Позже я узнал, что одним из преимуществ проектирования без карандаша и бумаги является то, что вы почти вынуждены избегать всех трудностей, которых можно избежать. В конце концов, этот алгоритм стал, к моему большому изумлению, одним из краеугольных камней моей славы.

— Эдсгер Дейкстра, в интервью Филиппу Л. Франа, Сообщения ACM 53 (8), 2001.

Год спустя он столкнулся с другой проблемой инженеров по аппаратному обеспечению, работающих над следующим компьютером института: минимизировать количество проводов, необходимых для соединения контактов на задней панели машины. В качестве решения он заново открыл алгоритм, известный как Прим алгоритм минимального остовного дерева. В Алгоритм Прима был первоначально разработан в 1930 году Чешский математик Войтех Ярник.^[37] а позже независимо переоткрыл и переиздал Роберт С. Прим в 1957 г.,^[38] и Дейкстра в 1959 году.^[39] Поэтому его также иногда называют Алгоритм DJP.^[40]

В 1961 году Дейкстра впервые описал маневровый алгоритм, метод анализа математических выражений, указанных в инфиксная запись, в Mathematisch Centrum отчет.^[41] Его можно использовать для вывода в Обратная польская запись (РПН) или как абстрактное синтаксическое дерево (АСТ). В алгоритм был назван маневровая площадка алгоритм, потому что его работа похожа на железнодорожная маневровая площадка. Алгоритм маневрового двора обычно используется для реализации парсеры приоритета операторов.

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

В 1974 году Дейкстра представил три самостабилизация алгоритмы взаимного исключения по кольцу. Эта работа считается первой, в которой представлена ​​и продемонстрирована концепция самостабилизации.^[42]

В середине 1970-х Дейкстра (вместе с другими авторами) представил две полезные абстракции (мутатор и сборщик) для изучения вывоз мусора. Мутатор абстрагирует процесс, выполняющий вычисления, включая выделение новой ячейки памяти. Сборщик - это процесс, который автоматически удаляет мусор. Далее в этой статье дается формализация трехцветная маркировка это основа для дополнительной сборки мусора.^[43][44]

В начале 80-х Дейкстра и Карел С. Шолтен предложил Алгоритм Дейкстры – Шолтена для обнаружения завершения в распределенные системы.

В 1981 году Дейкстра разработала гладкая сортировка, а на основе сравнения алгоритм сортировки и вариант heapsort.

Построение компилятора и исследование языков программирования

К августу 1960 года Дейкстра и его коллега Зонневельд завершили реализация первого компилятора ALGOL 60 для Electrologica X1 компьютер.

Дейкстра был известен как поклонник язык программирования АЛГОЛ, и работал над командой, которая реализовала первый компилятор за АЛГОЛ 60, в разработке, реализации и популяризации которого он принимал непосредственное участие. Как обсуждалось Питер Наур в статье «Европейская сторона последней фазы развития АЛГОЛА 60», в Материалы Первой конференции ACM SIGPLAN по истории языков программированияВ январе 1978 г. Дейкстра принял участие в период 1958–1959 гг. В ряде встреч, кульминацией которых стала публикация отчета, определяющего язык АЛГОЛ 60. Имя Дейкстры не фигурирует в списке из 13 авторов заключительного отчета, но он был официальным членом Международная федерация обработки информации (ИФИП) Рабочая группа 2.1 ИФИП по алгоритмическим языкам и исчислениям,^[45] который определяет, поддерживает и поддерживает АЛГОЛ 60 и АЛГОЛ 68.^[46] В конце концов он покинул комитет, по-видимому, потому, что не мог согласиться с мнением большинства. Тем не менее, работая в Mathematisch Centrum (Амстердам), он вместе с Яапом Зонневельдом написал первый компилятор ALGOL 60. Дейкстра и Зонневельд, которые работали над компилятором, согласились не бриться, пока проект не будет завершен. Вскоре после этого Зонневельд побрился, но Дейкстра сохранил бороду до конца своей жизни.^[47]

АЛГОЛ был результатом сотрудничества американского и европейского комитетов. АЛГОЛ 60 (сокращение от ALGOrithmic Language 1960) является членом семейства языков программирования ALGOL. Это последовало из АЛГОЛ 58 и вдохновил многие последующие языки. Он дал начало многим другим языкам, в том числе BCPL, B, Паскаль, Симула, и C.^[48] Алгол 60 был тщательно разработан компьютерный язык и предоставил большое количество ранее неизвестных выполнение проблемы. В качестве Бьярне Страуструп отмечает, что «одна проблема с Algol60 заключалась в том, что никто не знал, как его реализовать».^[49] Большой новый вызов в Реализация Алгола 60 распределение и управление данными во время выполнения. В 1960 году Дейкстра и Зонневельд показали, как рекурсивные процедуры могут выполняться с использованием среды выполнения. куча записей активации и как получить эффективный доступ к идентификаторам из статически охватывающих областей действия, используя так называемые отображать.^[50] Компилятор ALGOL 60 одним из первых поддержал рекурсия^[51] используя для этого новый метод. Краткая книга Дейкстры Учебник по программированию на Algol 60, первоначально опубликованный в 1962 году, в течение нескольких лет был стандартным справочником по языку.

Роль методологии программирования и зарождение движения структурного программирования

В 1965 году Дейкстра написал свой знаменитый Примечания по структурированному программированию и объявил программирование как дисциплина в отличие от ремесло. Также в 1965 году Hoare опубликовал важную статью о структурировании данных. Эти идеи оказали глубокое влияние на новые язык программирования, особенно Паскаль. Языки - это средства выражения этих идей. Структурированное программирование получил поддержку структурированный язык программирования.

— Никлаус Вирт, IEEE Annals of the History of Computing (2008)^[3]

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

— Бертран Мейер, Touch of Class: учимся хорошо программировать с объектами и контрактами (2009)^[25]

Компьютерное программирование в 1950-1960-х годах не признавался Академическая дисциплина и в отличие от зрелых наук не было теоретических концепций или систем кодирования. В те годы программирование как профессиональная деятельность было плохо изучено. В конце 1960-х компьютерное программирование находилось в состоянии кризиса. Программный кризис это термин, использовавшийся в первые дни вычислительная наука за трудность написания полезных и эффективных компьютерные программы в нужное время. Кризис программного обеспечения был вызван быстрым увеличением мощности компьютеров и сложностью проблем, которые можно было решить. По мере увеличения сложности программного обеспечения, многие программные проблемы возникли из-за того, что существующих методов было недостаточно. Термин «программный кризис» был придуман некоторыми участниками на первом из Конференции НАТО по разработке программного обеспечения в 1968 г. Гармиш, Германия.^[52][53][54] Его лекция 1972 года по Премии Тьюринга ACM ссылается на ту же проблему: «Основная причина программного кризиса в том, что машины стали на несколько порядков мощнее! Скажем прямо: пока машин не было, программирование оставалось неизменным. вообще никаких проблем; когда у нас было несколько слабых компьютеров, программирование превратилось в легкую проблему, а теперь у нас есть гигантские компьютеры, программирование стало столь же гигантской проблемой ».^[30]

Хотя Дейкстра в 1950-х годах активно программировал машинный код, он пришел к выводу, что в языках высокого уровня частое использование ИДТИ К Заявление обычно было признаком плохой структуры. В 1968 году он написал частную газету «Дело против заявления GO TO»,^[55] который затем был опубликован в виде письма в CACM.^[56] редактор Никлаус Вирт дал этому письму заголовок "Перейти к заявлению, которое считается вредным ", который ввел фразу"считается вредным "в вычисления.

Дейкстра утверждал, что оператор программирования GOTO, встречающийся во многих языках программирования высокого уровня, является основным источником ошибок и поэтому должен быть устранен. Это письмо вызвало бурную дискуссию в сообществе программистов. Некоторые дошли до того, что приравняли хорошее программирование к исключению ИДТИ К. Дейкстра отказался упомянуть дискуссию или даже заявление GO TO в своей статье «Заметки о структурном программировании». Споры давно утихли; Языки программирования предоставляют альтернативу GO TO, немногие программисты сегодня используют его свободно, а большинство вообще никогда не используют.^[14]

Тезис Дейкстры заключался в том, что отклонения от линейного потока управления были бы более очевидными, если бы допускались только в дисциплинированных структурах более высокого уровня, таких как если-то-еще заявление и пока цикл. Эта методология была разработана в структурное программирование, название его книги 1972 года, написанной в соавторстве с Тони Хоар и Оле-Йохан Даль. Структурированное программирование, которое многие считают первым значительным движением в истории компьютерного программирования, стало новой ортодоксией программирования в 1970-х годах.^[57][58][59]

Структурированное программирование часто рассматривается как "программирование без перехода". Но, как отмечает Бертран Мейер, «как первая книга по этой теме [Структурированное программирование Дейкстры, Даля и Хоара] показывает, что структурное программирование - это гораздо больше, чем структуры управления и идти к. Его основной посыл заключается в том, что программирование следует рассматривать как научную дисциплину, основанную на математической строгости ».^[25] Как парадигма программирования, структурированное программирование - особенно в 1970-х и 1980-х годах - значительно повлияло на рождение многих современных языки программирования Такие как Паскаль,^[2][3][60] C, Модула-2, и Ада.^[61] В Фортран 77 версия, включающая концепции структурного программирования, была выпущена в 1978 году. C ++ язык был значительно расширенной и улучшенной версией популярного структурированный язык программирования C (смотрите также: список языков программирования на основе C ). Поскольку C ++ был разработан на основе более традиционного структурированный язык, это 'гибридный язык ', а не чистый объектно-ориентированного программирования язык.^[62]

В своей статье Структурированное программирование: ретроспектива и перспективы (1986), Харлан Миллс пишет: "Эдсгер В. Дейкстра, 1969 г. Структурированное программирование статья положила начало десятилетию интенсивного внимания методам программирования, которые коренным образом изменили человеческие ожидания и достижения в разработка программного обеспечения. До этого десятилетия интенсивного внимания программирование считалось частной деятельностью по решению головоломок по написанию компьютерных инструкций для работы как программы. После этого десятилетия программирование можно было рассматривать как публичную математическую деятельность по преобразованию спецификаций в программы. Раньше проблема заключалась в том, чтобы заставить программы работать, а затем в их дальнейшей отладке, чтобы они делали правильные вещи. После этого можно было ожидать, что программы будут одновременно работать и делать правильные вещи с минимальной отладкой или без нее. Раньше считалось, что ни одна масштабная программа не может быть безошибочной. После этого многие крупные программы работали год или больше, не обнаруживая ошибок. Эти ожидания и достижения не универсальны из-за инерции производственных практик. Но они достаточно хорошо зарекомендовали себя, чтобы предвещать фундаментальные изменения в разработке программного обеспечения ».

Книга Краткая энциклопедия компьютерных наук (2004), под редакцией Эдвина Д. Рейли, отмечает, что «структурное программирование внесло важный вклад в два аспекта: он поднял технику программирования до уровня не столько искусства, сколько науки, и демонстрация того, что тщательно структурированные программы могут быть творческие произведения, обладающие достаточными литературными достоинствами, чтобы их могли читать люди, а не только компьютер ».^[63]

Исследования в области проектирования и разработки программ на заре программной инженерии

Идеи Дейкстры о методология программирования (особенно движение структурированного программирования) помогло заложить основы для зарождения и развития профессиональной дисциплины программная инженерия (в частности, проектирование и разработка программного обеспечения), позволяя программистам организовывать все более сложные программные проекты и управлять ими.^[64][65] В конце 1960-х Дейкстра обсуждал концепцию программных семейств. В середине 1970-х гг. Давид Парнас и другие разъяснили идею и показали, как применить ее в принципах программной инженерии.

Подъем структурное программирование движение привело ко многим другим структурированный подходы, применяемые к разработка программного обеспечения. Техники структурированный анализ и структурированный дизайн являются продуктом концепций и методов структурированного программирования, а также ранних идей модульного дизайна. Принципы модульности были усилены Ларри Константин концепции связь (должно быть минимизировано между модулями) и сплоченность (для максимизации в модулях), Давид Парнас методы скрытие информации, и по абстрактные типы данных.^[66] Ряд инструментов и методов, использующих структурированные концепции были разработаны, такие как Структурированный дизайн, Структурированное программирование Джексона, Росс ' Структурированный анализ и методика проектирования (SADT), Структурированный метод Юрдона, Структурный системный анализ и метод проектирования (SSADM) и Джеймса Мартина инженерия информационных технологий. Поле показатели программного обеспечения часто рассматривается как прямое влияние движения структурного программирования на программная инженерия в 1970-е гг.

Разделение проблем (SoC), один из основных принципов в программная инженерия, это принцип конструкции для разделения компьютерная программа на отдельные разделы, так что каждый раздел посвящен отдельному беспокойство. Период, термин разделение проблем был придуман Дейкстрой в его статье 1974 г. «О роли научной мысли».^[67]

Исследование операционной системы

В 1960-х Дейкстра и его коллеги в Эйндховен разработан и реализован THE (означает 'Technische Hogeschool Эйндховен ') Операционная система, который был организован в четко обозначенные слои абстракции.^[68] Его статья 1968 года на эту тему заложила основу для последующих разработок операционных систем. Компьютерное общество IEEE Дэвид Алан Грир пишет: «Обычно мы прослеживаем идею построения компьютерных систем по слоям до работы в 1967 году, которую голландский ученый-компьютерщик Эдсгер Дейкстра представил на совместной конференции IEEE Computer Society / ACM. До этой статьи инженеры боролись с проблемой того, как для организации программного обеспечения. Если вы посмотрите на ранние примеры программ, и вы можете найти многие из них в электронной библиотеке Computer Society, вы обнаружите, что большая часть кода той эпохи сложна, трудна для чтения, трудна для изменения и сложна для В своей статье 1967 года Дейкстра описал, как программное обеспечение может быть построено по слоям, и привел пример простой операционной системы, использующей пять уровней. Он признал, что эта система, возможно, не может быть реалистичной проверкой его идей, но он утверждал, что " Чем больше проект, тем важнее структурирование! »Идея использования слоев для управления сложностью стала опорой архитектуры программного обеспечения. Мы видим ее во многих формах и применяем ее для решения многих проблем. Мы видим это в иерархия классов в объектно-ориентированном программировании и в структуре Сервис-Ориентированная Архитектура (SOA). SOA - это относительно недавнее применение многоуровневости в информатике. Он был сформулирован в 2007 году как средство управления сложностью бизнес-систем, особенно распределенных систем, в которых широко используется Интернет. Подобно плану Дейкстры по развитию системы, его многоуровневая система называется стеком решений SOA или S3. Девять уровней S3: 1) операционные системы, 2) сервисные компоненты, 3) сервисы, 4) бизнес-процессы, 5) действия потребителей, 6) системная интеграция, 7) контроль и обеспечение качества, 8) информационная архитектура и 9) система управления и политики ".^[69]

Дейкстра организовал проектирование системы по уровням, чтобы снизить общую сложность программного обеспечения. Хотя термин «архитектура» еще не использовался для описания разработка программного обеспечения, это, безусловно, считалось первым проблеском программная архитектура.^[70] Он ввел ряд принципов проектирования, которые стали частью рабочего словаря каждого профессионального программиста: уровни абстракции, послойное программирование, семафор и взаимодействующие последовательные процессы. Его оригинальный доклад об операционной системе THE был переиздан в выпуске журнала ACM, посвященном 25-летию, в январе 1983 года. В качестве вступительной части главный редактор говорит: «Этот проект положил начало долгому исследованию многоуровневых систем. архитектура - линия, которая продолжается и по сей день, потому что иерархическая модульность - мощный подход к организации больших систем ».^[14]

Параллельные вычисления (параллельное программирование)

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

— Лесли Лэмпорт, Лекция Тьюринга: Компьютерные науки о параллелизме: первые годы (Июнь 2015 г.)^[6]

А семафор (нидерландский язык: Seinpaal), термин, использованный в оригинальной статье Дейкстры.^[71] В начале 1960-х Дейкстра предложил первый механизм синхронизации для параллельных процессов, семафор с его двумя операциями, P и V.

В одностраничной статье 1965 года Дейкстра представил «взаимное исключение проблема »для n процессов и обсудили ее решение. Вероятно, это был первый опубликованный параллельный алгоритм.^[6][16] Стандартное к настоящему времени понятие "критическая секция 'также был представлен в этой статье. Пер Бринч Хансен, пионер в области параллельные вычисления, считает Дейкстры Взаимодействующие последовательные процессы (1965) быть первая классическая бумага в параллельном программировании. Как отмечает Бринч Хансен, «этой статьей Дейкстра закладывает концептуальную основу абстрактного параллельного программирования».^[72]

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

В 1968 году Дейкстра опубликовал свою основополагающую статью «Взаимодействующие последовательные процессы ', 70-страничное эссе, которое положило начало области параллельное программирование. В нем он обсуждал понятие взаимное исключение (мьютекс ) и критериям, которым должно удовлетворять удовлетворительное решение. Он также исправил историческую перспективу, упущенную из его статьи 1965 года, включив первое известное правильное решение проблемы взаимного исключения, для двух процессов из-за Теодорус Деккер. Дейкстра впоследствии обобщил Решение Деккера процессам.^[73][74] Далее он предложил первый механизм синхронизации для параллельных процессов,^[75] то семафор с его двумя операциями, P и V. Он также идентифицировал 'тупик проблема '(называемая там' проблема смертельные объятия ')^[76] и предложил элегантный 'Банковский алгоритм ' который предотвращает тупик. Обнаружение и предотвращение тупиковых ситуаций стало постоянной проблемой исследований в области параллельного программирования.

Иллюстрация проблемы обедающих философов

В проблема обедающих философов это пример проблемы, часто используемой в одновременный разработка алгоритма для иллюстрации синхронизация проблемы и методы их решения. Первоначально он был сформулирован Дейкстрой в 1965 году как упражнение для студенческого экзамена, представленное в терминах компьютеров. соревнуясь за доступ к ленточный накопитель периферийные устройства. Вскоре после, Тони Хоар дал проблеме ее нынешнюю постановку.^[77] В проблема спящего парикмахера также приписывается Дейкстре.

Мишель Рейналь (2012) пишет: «Начиная с ранней работы Э.В. Дейкстры (1965), который представил проблему взаимного исключения, концепцию процесса, семафорный объект, понятие самое слабое предварительное условие, и охраняемые команды (среди многих других вкладов), синхронизация это уже не каталог уловок, а область вычислительной науки со своими собственными концепциями, механизмами и методами, результаты которых можно применять во многих областях. Это означает, что синхронизация процессов должна быть основной темой любой учебной программы по информатике ».^[78]

Джон В. Маккормик и др. (2011) отмечает: «Понятие параллельная программа как средство для письма параллельные программы безотносительно к базовому оборудованию был впервые представлен Эдсгером Дейкстра (1968). Моти Бен-Ари (1982) элегантно резюмировал идею Дейкстры в трех предложениях: «Параллельное программирование - это название, данное обозначениям программирования и методам для выражения потенциального параллелизма и решения возникающих проблем синхронизации и коммуникации. Реализация параллелизма - это тема в компьютерных системах (аппаратных и программных), которая по существу не зависит от параллельного программирования. Параллельное программирование важно, потому что оно обеспечивает абстрактную среду для изучения параллелизма, не увязая в деталях реализации ».^[79]

Распределенные вычисления (распределенное программирование)

Дейкстра был одним из первых пионеров исследований принципов распределенных вычислений.^[27] В Премия Дейкстры Спонсоры признают: «Ни один другой человек не оказал большего влияния на исследования принципов распределенных вычислений».^[27] Некоторые из его работ даже считаются теми, что положили начало этой области. Статья Дейкстры 1965 г., Решение задачи управления параллельным программированием был первым, кто представил правильное решение взаимное исключение проблема. Лесли Лэмпорт пишет, что эта работа "наверное поэтому PODC существует "и он" начал область одновременных и распределенные алгоритмы ".^[5]

В частности, его статья «Самостабилизирующиеся системы, несмотря на распределенное управление» (1974) положила начало подполе самостабилизация. Он также считается первым научным исследованием отказоустойчивые системы.^[6] Статья Дейкстры не была широко известна до выступления Лесли Лэмпорта на ACM. Симпозиум по принципам распределенных вычислений (PODC ) в 1983 г. В своем отчете о работе Дейкстры над самостабилизирующийся распределенные системы, Лампорт считает это «важной вехой в работе над Отказоустойчивость 'и' очень плодородное поле для исследований '.^[80]

Формальная спецификация и проверка

С 1970-х годов главным интересом Дейкстры было формальная проверка. В 1976 году Дейкстра опубликовал основополагающую книгу, Дисциплина программирования, который выдвинул свой метод систематической разработки программ вместе с доказательствами их корректности. В своей экспозиции он использовал свой 'Защищенный командный язык '. Язык, опирающийся на недетерминизм, принятый самое слабое предварительное условие семантика и предлагаемый метод разработки по сей день оказывает значительное влияние на месторождение. В исчисление уточнения, первоначально предложенный Ральф-Йохан Бэк^[81] и разработан Кэрролл Морган,^[82] является расширением Дейкстры исчисление самого слабого предусловия, где операторы программы моделируются как преобразователи предикатов.^[83]

В 1984 году, чтобы добавить дополнительную поддержку этому подходу к программированию, он опубликовал совместно с Вимом Фейеном вводный учебник для студентов первого курса факультета информатики. Книга, впервые опубликованная на голландском языке, называлась Een method van programmeren. Английское издание появилось в 1988 году как Метод программирования.

О природе информатики и компьютерного программирования

Многие из его мнений по информатике и программированию получили широкое распространение. Например, ему иногда приписывают программную фразу «два или более, используйте for» (эмпирическое правило, когда использовать цикл).^[84]

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

Дейкстра был одним из самых известных противников инженерной точки зрения на вычислительную науку. Нравиться Питер Наур и Кристен Найгаард Дийкстра не любил сам термин «информатика». Информатика, как указал Дейкстра, заслуживает лучшего названия. Он предполагает, что это можно назвать «компьютерной наукой». Вместо компьютера или вычислительной техники Дейкстра хотел подчеркнуть абстрактные механизмы, которые компьютерная наука использует для преодоления сложности. При выражении абстрактного характера вычислительная наука, он написал,

Еще более сложная путаница возникла из-за того, что среди неподготовленных были инженеры-электронщики, которые должны были проектировать, строить и обслуживать машины. Работа фактически выходила за рамки электронная техника дня, и, как следствие, вопрос о том, как получить и поддерживать физическое оборудование более или менее в рабочем состоянии, в первые дни стал всеобщей заботой. В результате эта тема стала - в первую очередь в США - преждевременно известной как "Информатика ’- что на самом деле похоже на хирургия как «наука о ножах» - и в умах людей прочно укоренилось, что вычислительная наука о машинах и их периферийном оборудовании. Quod non [латинское: «Что не так»]. Теперь мы знаем, что электронные технологии не могут больше способствовать вычисление чем физическое оборудование. Теперь мы знаем, что программируемый компьютер является не более и не менее, чем чрезвычайно удобное устройство для реализации любого мыслимого механизма без изменения единственного провода, и что основная проблема вычислительной науки, следовательно, является концептуальной, а именно, какие (абстрактные) механизмы мы можем представить, не заблудившись в сложностях нашего собственного изготовления.^[85]

В Скромный программист (1972) Дейкстра писал: «Мы не должны забывать, что это не наша задача [ученых-информатиков] создавать программы, это наша задача - проектировать классы вычислений, которые будут демонстрировать желаемое поведение».

Дейкстра также выступил против включения программная инженерия под эгидой академической информатики. Он писал, что «Поскольку экономика известна как« жалкая наука », программную инженерию следует называть« обреченной дисциплиной », обреченной, потому что она даже не может достичь своей цели, поскольку ее цель противоречива сама себе». И «программная инженерия приняла в качестве своего устава« Как программировать, если не можешь »».^[86]

Личность и стиль работы

Дейкстра у доски во время конференции в ETH Цюрих в 1994 году. Однажды он заметил: "Картинка может стоить тысячи слов, а формула стоит тысячи картинок ".^[87]

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

— Э. В. Дейкстра, "О природе вычислительной науки" (EWD896), август 1984 г.

Вы вряд ли можете винить M.I.T. за то, что не обратил внимания на малоизвестного ученого-компьютерщика в маленьком городке в Нидерландах.

— Дийкстра остроумно описывал себя в Nuenen в середине 1960-х гг.^[88][18]

В мире информатики Дейкстра хорошо известен как «персонаж». В предисловии к его книге Дисциплина программирования (1976) он заявил следующее: «За отсутствие библиографии я не предлагаю ни объяснений, ни извинений». Фактически, большинство его статей и книг вообще не имеют ссылок.^[16] Некоторые исследователи выразили сожаление по поводу такого подхода к ссылкам. Но Дейкстра выбрал этот способ работы, чтобы сохранить уверенность в своих силах.

Будучи профессором университета на протяжении большей части своей жизни, Дейкстра рассматривал преподавание не только как обязательную деятельность, но и как серьезное исследовательское начинание.^[14] Его подход к обучению был нетрадиционным.^[89] Его стиль чтения лекций был описан как идиосинкразический. При чтении лекций длинные паузы между предложениями часто объясняются тем фактом, что английский не является родным языком Дейкстры. Однако паузы также служили для него способом подумать на ногах, и он считался быстрым и глубоким мыслителем, когда он читал лекции. Его курсы для студентов в Остине не имели ничего общего с информатикой, но они касались представления математических доказательств.^[16] В начале каждого семестр он фотографировал каждого из студентов, чтобы запомнить их имена. Он никогда не следил за учебник, за возможным исключением его собственного, пока он готовился. Читая лекцию, он писал корректуры мелом на доске, а не использовал фольгу. Он предлагал студентам предлагать идеи, которые затем исследовал, или отказывался от них, поскольку они нарушали некоторые из его принципов. Он давал сложные домашние задания и тщательно изучал решения своих учеников. Он проводил свои выпускные экзамены устно в течение целой недели. Каждого студента обследовали в офисе Дейкстры или дома, и экзамен длился несколько часов.^[14]

Задача университета - не предлагать то, что просит общество, а давать то, что ему нужно. [То, чего требует общество, обычно понимается, и для этого не нужен университет; университет должен предложить то, что не может предложить никто другой.]

— E.W. Dijkstra, "Ответы на вопросы студентов программной инженерии" (EWD1305), ноябрь 2000 г.

Дийкстра также был весьма оригинален в оценке трудоспособности людей. Когда Владимир Лифшиц приехал в Остин в 1990 году на собеседование, Дейкстра дал ему загадку. Владимир решил ее и с тех пор работает в Остине.^[16]

Несмотря на то, что он изобрел большую часть технологий программного обеспечения, он воздерживался от использования компьютеров в своей работе на протяжении многих десятилетий. Даже после того, как он поддался поддержке своих коллег из UT и приобрел Macintosh компьютер, он использовал это только для электронное письмо и для просмотра Всемирная паутина.^[90] Дийкстра никогда не писал свои статьи с помощью компьютера. Он предпочитал полагаться на свои печатная машинка а позже его Montblanc ручка.^[16] Любимым пишущим инструментом Дейкстры был Montblanc. Meisterstück Перьевая ручка. Он неоднократно пробовал использовать другие ручки, но ни одна из них не заменила Montblanc.

Он не использовал текстовые процессоры, полагая, что можно написать письмо или статью без черновиков, переписывания или какого-либо значительного редактирования. Он все продумал в своей голове, прежде чем положить ручка на бумагу, и однажды упомянул, что когда он был студентом-физиком, он решал свои домашние задания в уме, гуляя по улицам Лейден.^[14]Большинство публикаций Дейкстры были написаны им одним. У него никогда не было секретаря, и он в одиночку вел всю свою переписку.^[16] Когда коллеги подготовили Festschrift к его шестидесятилетию, опубликовано Springer-Verlag, он потрудился поблагодарить каждого из 61 участника отдельно, написав собственное письмо.^[16]

На протяжении всей карьеры Дейкстры его работы отличались элегантностью и экономичностью.^[16] Плодотворный писатель (особенно как эссеист), Дейкстра написал более 1300 статей, многие из которых написаны от руки его точным почерком. Это были очерки и притчи; сказки и предупреждения; исчерпывающее объяснение и педагогический предлог. Большинство из них были посвящены математике и информатике; другие были отчетами о поездках, которые больше рассказывают об их авторе, чем о людях и местах, которые они посетили. Он имел обыкновение копировать каждую статью и распространять ее среди небольшой группы коллег, которые копировали и пересылали статьи другой ограниченной группе ученых.^[91] Его роман с простота пришел в раннем возрасте и под руководством матери. Однажды он сказал, что спросил свою мать, является ли тригонометрия сложной темой. Она ответила, что он должен выучить все формулы и что дальше, если ему требуется больше пяти строк, чтобы что-то доказать, он ошибается.^[92]

Дейкстра был известен своим остроумием, красноречием, грубостью, резкостью и часто жестокостью по отношению к коллегам-профессионалам, а также умением обращаться со словами, например, в его замечании: «Вопрос о том, могут ли машины думать (…), столь же актуален, как и вопрос о том, могут ли машины думать (…) Подводные лодки умеют плавать ».^[93]. Его советом перспективному исследователю, который спросил, как выбрать тему для исследования, были мудрые слова: «Делай только то, что можешь делать только ты».^[14] Дейкстра также был известен своей вокальной критикой и отсутствием социальных навыков при общении с коллегами. Как откровенный и критический визионер, он категорически противился учению БАЗОВЫЙ.^[94]

Во многих своих более остроумных эссе Дейкстра описывал вымышленную компанию, председателем которой он являлся. Компания называлась Mathematics, Inc., и он предполагал, что у нее будет коммерциализированный производство математических теоремы таким же образом, как компании-разработчики программного обеспечения коммерциализировали производство компьютерных программ. Он изобрел ряд занятий и задач Mathematics Inc. и задокументировал их в нескольких статьях серии EWD. Выдуманная компания представила доказательство Гипотеза Римана но потом были большие трудности со сбором роялти от математиков, которые доказали результаты, предполагающие гипотезу Римана. Само доказательство было Коммерческая тайна.^[95] Многие доказательства компании были поспешно выброшены, и тогда пришлось потратить большую часть усилий компании на поддержание.^[96] Более успешной попыткой было Стандартное доказательство для Теорема Пифагора, который заменил более 100 несовместимых существующих доказательств.^[97] Дейкстра описал Mathematics Inc. как «самый захватывающий и самый жалкий бизнес из когда-либо задуманных».^[95] EWD 443 (1974) описывает свою вымышленную компанию как имеющую более 75 процентов доли мирового рынка.^[98][99]

Рукописи EWD

Дейкстра был хорошо известен своей привычкой тщательно составлять рукописи с его Перьевая ручка. Рукописи называются EWD, поскольку Дейкстра пронумеровал их знаком EWD, его инициалы в качестве префикса. По словам самого Дейкстры, EWD начались, когда он переехал из Математического центра в г. Амстердам в Технологический университет Эйндховена (затем Technische Hogeschool Eindhoven). После перехода в Эйндховен, Дейкстра испытал блок писателя больше года. Дийкстра раздал своим коллегам фотокопии нового EWD. Многие получатели сделали фотокопии и отправили свои копии, так что EWD распространились по всему международному компьютерному сообществу. Темами были информатика и математика, включая отчеты о поездках, письма и выступления. Эти короткие статьи охватывают период в 40 лет. Почти все EWD, появившиеся после 1972 года, были написаны от руки. Они редко бывают длиннее 15 страниц и имеют последовательную нумерацию. Последний, № 1318, датирован 14 апреля 2002 года. В информатике они известны как отчеты EWD или просто EWD. Было отсканировано более 1300 EWD, и их число растет, чтобы облегчить поиск, и они доступны в Интернете в архиве Дейкстры Техасского университета.^[100]

Личная жизнь и смерть

Самоуверенность Дейкстры сочеталась с удивительно скромной Стиль жизни, до такой степени, чтобы быть спартанский.^[16] Дом его и его жены в Nuenen был простым, маленьким и непритязательным. У него не было телевизора, видеомагнитофона или мобильного телефона, и он не ходил в кино.^[16] Напротив, он хорошо играл на пианино и, находясь в Остин, любил ходить в концерты. Восторженный слушатель классическая музыка, Любимым композитором Дейкстры был Моцарт.^[14]

Дийкстра умер 6 августа 2002 года. По словам официальных лиц Техасского университета, причиной смерти стал рак.^{[101][102][103]}

Влияние и признание

Разница между программистом и ученым-компьютерщиком заключается в должности. Эдсгер Дейкстра гордо хочет, чтобы его называли «программистом», хотя он уже несколько лет не прикасался к компьютеру. (...) Его великая сила в том, что он бескомпромиссен. При мысли о программировании на C ++ ему было бы физически плохо.

— Дональд Кнут (1996), интервью с Дональдом Кнутом Джека Вера из Журнал доктора Добба.^[104]

В 1972 г. Ассоциация вычислительной техники (ACM) признал основополагающий вклад Дейкстры в эту область, наградив его выдающейся премией Тьюринга. Ссылка на награду гласит:^[105]

Эдсгер Дейкстра внес в конце 1950-х годов основной вклад в развитие АЛГОЛ, язык программирования высокого уровня, который стал образцом ясности и математической строгости. Он является одним из главных представителей науки и искусства языки программирования в целом и во многом помогли нам понять их структуру, представление и реализацию. Его пятнадцать лет публикаций основаны на теоретических статьях по теория графов базовым руководствам, пояснительным текстам и философским размышлениям в области языков программирования.

Вступительное слово на церемонии награждения - дань уважения Дийкстре:^[105]

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

По словам сэра Тони Хоар, ФРС, доставленные им на похоронах Дейкстры:^[14]

Эдсгер широко известен как человек, который глубоко задумался над многими глубокими вопросами; и один из самых глубоких вопросов - это вопрос традиционной моральной философии: как получается, что человек должен жить своей жизнью? Эдсгер нашел ответ на этот вопрос в самом начале своей жизни: он решил, что будет жить как академический ученый, проводя исследования в новой области науки - науке о вычислениях. Он заложит основы, которые сделают вычисления строгой научной дисциплиной; и в своих исследованиях, в своем обучении и в своих трудах он будет стремиться к совершенству, исключая все другие заботы. Он никогда не отклонялся от этих обязательств, и именно так он внес в выбранный им предмет изучения величайший вклад, который любой человек мог бы сделать за одну жизнь.

В марте 2003 г. на адрес распределенных вычислений сообщество:^[106]

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

Бывший ACM Президент Питер Дж. Деннинг писал о Дейкстре:^[107]

Эдсгер Дейкстра, один из гигантов в нашей области и страстный сторонник математического взгляда на программы и программирование (...) За предыдущую четверть века он сформулировал многие из великих интеллектуальных задач в этой области как программирование - оператор goto, структурированное программирование, параллельные процессы, семафоры, взаимоблокировки, рекурсивное программирование на языке Algol и создание правильных программ.

Награды и отличия

Среди наград и наград Дейкстры:^[90]

• Член Королевская Нидерландская академия искусств и наук (1971)^[108]
• Заслуженный член Британское компьютерное общество (1971)
• В Ассоциация вычислительной техники с ЯВЛЯЮСЬ. Премия Тьюринга (1972)^[109]
• Премия памяти Гарри Х. Гуда от IEEE Computer Society (1974).^[110]
• Иностранный почетный член Американская академия искусств и наук (1975)
• Доктор наук Honoris Causa от Королевский университет Белфаста (1976)
• Получатель хартии Computer Pioneer от IEEE Computer Society (1982)
• ACM /SIGCSE Премия за выдающийся вклад в образование в области компьютерных наук (1989)
• Парень из Ассоциация вычислительной техники (1994)^[111]
• Почетный доктор Афинский университет экономики и бизнеса, Греция (2001).

В 1969 г. Британское компьютерное общество (BCS) получил одобрение на награду и стипендию, Заслуженный член Британского компьютерного общества (DFBCS), который будет присужден в соответствии с в соответствии с законом 7 из их королевская хартия. В 1971 году были проведены первые выборы в Дейкстру.^[112]

В 1990 году, по случаю 60-летия Дейкстры, факультет компьютерных наук (UTCS) Техасского университета в Остине организовал двухдневный семинар в его честь. Спикеры приехали со всех концов Соединенных Штатов и Европы, а группа ученых-информатиков написала исследовательские статьи, которые были отредактированы в книгу.^[14][113]

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

Незадолго до своей смерти в 2002 году Дейкстра получил награду ACM. Премия PODC Influential-Paper в распределенных вычислений за работу по самостабилизации программных вычислений. Эта ежегодная премия была переименована в Премия Дейкстры (Премия Эдсгера В. Дейкстры в области распределенных вычислений ) в следующем году в его честь.

Премия Дейкстры за выдающиеся академические достижения в области компьютерных наук (Университет Лойолы Чикаго, Департамент компьютерных наук) назван в честь Эдсгера В. Дейкстры. Начиная с 2005 года, эта награда присуждается за высшую академическую успеваемость по специальности "Информатика". Отбор осуществляется на основе среднего балла по всем основным курсам и выбора преподавателями кафедры.^[114]

12 октября 2010 года факультет компьютерных наук (UTCS) Техасского университета в Остине провел первую лекцию, посвященную памяти Эдсгера В. Дейкстры. Тони Хоар, Почетный профессор Оксфорда и главный научный сотрудник Microsoft Research, выступил на мероприятии. Эта серия лекций стала возможной благодаря щедрому гранту компании Schlumberger в память о Дейкстре.

Смотрите также

• Алгоритм Дейкстры
• Проблема обедающих философов
• Защищенный командный язык
• Семантика преобразователя предикатов
• Исчисление слабейших предусловий
• Семафор
• Smoothsort
• Перейти к заявлению, которое считается вредным
• О жестокости реального преподавания информатики
• Список пионеров информатики
• Список важных публикаций по информатике
• Список важных публикаций по теоретической информатике
• Список важных публикаций по параллельным, параллельным и распределенным вычислениям

Избранные публикации

Книги

Избранные статьи

Рекомендации

дальнейшее чтение

• Альтисен, Карине; Devismes, Стефан; Дюбуа, Свон; Пети, Франк; Рейналь, Мишель (2019). Введение в распределенные самостабилизирующиеся алгоритмы. Сан-Рафаэль, Калифорния: Издательство Morgan & Claypool. ISBN  9781681735375.
• Апт, Кшиштоф Р. (2002). "Эдсгер Вайбе Дейкстра (1930–2002): Портрет гения". Формальные аспекты вычислений. 14 (2): 92–98. arXiv:cs / 0210001. Bibcode:2002cs ....... 10001A. Дои:10.1007 / s001650200029. S2CID  12482128.
• Бринч Хансен, Пер (2002). Истоки параллельного программирования: от семафоров до удаленных вызовов процедур. Springer. ISBN  978-0-387-95401-1.
• Бен-Ари, М. (2006). Принципы параллельного и распределенного программирования (2-е изд.). Эддисон-Уэсли. ISBN  978-0-321-31283-9.
• Broy, M .; Денерт, Эрнст, ред. (2002). Пионеры программного обеспечения: вклад в разработку программного обеспечения. Springer. ISBN  978-3-540-43081-0.
• Чен, Питер П. (2002). «От Goto -less к структурированному программированию: наследие Эдсгера В. Дейкстры». Программное обеспечение IEEE. 19 (5): 21. Дои:10.1109 / MS.2002.1032847. S2CID  29320163.
• Дневной свет, Эдгар Г. (2012). Эра программной инженерии: от Тьюринга до Дейкстры. Одинокий ученый. ISBN  9789491386022.
• Дневной свет, Эдгар Г. (2011). «Призыв Дейкстры к обобщению: появление рекурсивной процедуры, конец 1950-х - начало 1960-х годов». Компьютерный журнал. 54 (11): 1756–72. Дои:10.1093 / comjnl / bxr002.
• Долев, Шломи (2000). Самостабилизация. MIT Press. ISBN  978-0-262-04178-2.
• Feijen, W.H.J .; Грис, Дэвид, ред. (1990). Красота - наше дело: поздравление с днем ​​рождения Эдсгеру В. Дейкстре. Springer. ISBN  978-0-387-97299-2.
• Истраль, Сорин (осень – зима 2008 г.). «Рассказы о маяках: Критика профессора Дейкстры считается безвредной" (PDF). Трубопровод. Vol. 17 нет. 2. Кафедра компьютерных наук Университета Брауна. С. 10–17.
• Истраль, Сорин (весна – лето 2010 г.). «Рассказы о маяках: когда профессор Дейкстра ударил меня в поисках прекрасного кода» (PDF). Трубопровод. Vol. 19 нет. 1. Факультет компьютерных наук Университета Брауна. С. 10–12.
• Джеймс, Майк (2013). "Эдсгер Дейкстра - Поэзия программирования". I-programmer.info.
• Лэмпорт, Лесли (Июнь 2015 г.). «Лекция Тьюринга: Компьютерные науки о параллелизме: первые годы». Comm. ACM. 58 (6): 71–76. Дои:10.1145/2771951. S2CID  19164754.
• Лапланте, Филипп А. (1996). Отличные статьи по информатике. IEEE Press. ISBN  978-0-7803-1112-1.
• Лапланте, Филипп А. (2008). «Великие статьи в области компьютерных наук: ретроспектива» (PDF). Журнал научно-практических вычислений. 2 (1): 31–35. CiteSeerX  10.1.1.559.2457. Архивировано из оригинал (PDF) 5 мая 2018 г.
• Ли, J.A.N. (1991). «Границы вычислений: дань уважения Эдсгеру В. Дейкстре по случаю его 60-летия». Анна. Hist. Comp. 13 (1): 91–96. Дои:10.1109 / MAHC.1991.10000.
• Марков, Джон (2002). "Эдсгер Дейкстра, 72 года, физик, который сформировал компьютерную эру". Нью-Йорк Таймс.
• Милоне, Лоренцо (2009). "E.W. Dijkstra, una vita da informatico [на итальянском языке]" (PDF). Mondo Digitale. 9 (2).
• О’Реган, Джерард (2013). Гиганты вычислительной техники: сборник избранных, основных пионеров. Springer. ISBN  978-1-4471-5340-5.
• Пайетт, Сэнди (2014). «Хоппер и Дейкстра: кризис, революция и будущее программирования». IEEE Annals of the History of Computing. 36 (4): 64–73. Дои:10.1109 / MAHC.2014.54. S2CID  9029390.
• Шаша, Деннис; Лазер, Кэти (2 июля 1998 г.). Не в своем уме: жизни и открытия 15 великих ученых-компьютерщиков. Springer. ISBN  978-0-387-98269-4.

внешняя ссылка

• "Архив Э. В. Дейкстры". Центр американской истории, Техасский университет в Остине.
• «Призыв Дейкстры к обобщению». Сайт, посвященный работам и мыслям Дейкстры, созданный и поддерживаемый историком вычислительной техники Эдгаром Грэмом Дэйлайтом.