Edsger Wybe Dijkstra ( / ˈ d aɪ k s t r ə / DYKE -strə ; голландский: [ˈɛtsxər ˈʋibə ˈdɛikstraː] ; 11 мая 1930 — 6 августа 2002) — голландскийучёный-компьютерщик,программист,инженер-программист, математик и научныйэссеист.[1][2]
Родившийся в Роттердаме , Нидерланды , Дейкстра изучал математику и физику, а затем теоретическую физику в Лейденском университете . Адриан ван Вейнгаарден предложил ему работу в качестве первого программиста в Нидерландах в Математическом центре в Амстердаме , где он работал с 1952 по 1962 год. Он сформулировал и решил задачу о кратчайшем пути в 1956 году, а в 1960 году разработал первый компилятор для языка программирования ALGOL 60 совместно с коллегой Яапом А. Зонневельдом . В 1962 году он переехал в Эйндховен , а затем в Нюэнен , где стал профессором кафедры математики в Высшей технической школе Эйндховена . В конце 1960-х годов он построил систему мультипрограммирования THE , которая повлияла на конструкции последующих систем благодаря использованию программно-ориентированной страничной виртуальной памяти. Дейкстра присоединился к Burroughs Corporation в качестве единственного научного сотрудника в августе 1973 года. Годы работы в Burroughs стали для него временем наибольшей продуктивности в плане научных статей. Он написал около 500 документов в серии "EWD", большинство из которых были техническими отчетами, для частного распространения в рамках избранной группы.
В 1984 году Дейкстра занял кафедру Schlumberger Centennial Chair на кафедре компьютерных наук Техасского университета в Остине и работал в Остине, штат Техас , до выхода на пенсию в ноябре 1999 года. Он и его жена вернулись из Остина в свой родной дом в Нюэнене, где он умер 6 августа 2002 года после продолжительной борьбы с раком. [3]
Он получил премию Тьюринга 1972 года за фундаментальный вклад в разработку структурных языков программирования. Незадолго до своей смерти он получил премию ACM PODC Influential Paper Award в области распределенных вычислений за работу по самостабилизации вычислений программ. Эта ежегодная награда была переименована в премию Дейкстры в следующем году в его честь.
Эдсгер В. Дейкстра родился в Роттердаме . Его отец был химиком, президентом Голландского химического общества ; он преподавал химию в средней школе, а позже стал ее суперинтендантом. Его мать была математиком, но никогда не имела официальной работы. [4] [5]
Дейкстра рассматривал карьеру юриста и надеялся представлять Нидерланды в Организации Объединенных Наций . Однако после окончания школы в 1948 году по предложению родителей он изучал математику и физику, а затем теоретическую физику в Лейденском университете . [6]
В начале 1950-х годов электронные компьютеры были новинкой. Дейкстра наткнулся на свою карьеру случайно, и через своего руководителя, профессора Йоханнеса Хаантьеса , он познакомился с Адрианом ван Вейнгаарденом , директором отдела вычислений в Математическом центре в Амстердаме , который предложил Дейкстре работу; он официально стал первым «программистом» Нидерландов в марте 1952 года. [6]
Дейкстра некоторое время оставался преданным физике, работая над ней в Лейдене три дня в неделю. Однако с ростом интереса к вычислениям его фокус начал смещаться. Как он вспоминал: [7]
После трех лет программирования у меня состоялся разговор с А. ван Вейнгаарденом, который тогда был моим начальником в Математическом центре в Амстердаме, разговор, за который я буду благодарен ему до конца жизни. Дело в том, что я должен был одновременно изучать теоретическую физику в Лейденском университете, и поскольку мне становилось все труднее совмещать эти два занятия, мне нужно было решить: либо прекратить программирование и стать настоящим, уважаемым физиком-теоретиком, либо довести свое изучение физики до формального завершения, с минимальными усилиями, и стать... да чем? Программистом? Но была ли это уважаемая профессия? Ведь, в конце концов, что такое программирование? Где был солидный объем знаний, который мог бы поддержать его как интеллектуально уважаемую дисциплину? Я очень хорошо помню, как я завидовал своим коллегам по аппаратному обеспечению, которые, когда их спрашивали об их профессиональной компетентности, могли, по крайней мере, указать, что они знают все о электронных лампах, усилителях и всем остальном, в то время как я чувствовал, что, столкнувшись с этим вопросом, я останусь с пустыми руками. Полный опасений, я постучал в дверь кабинета Ван Вейнгаардена, спрашивая его, могу ли я «поговорить с ним минутку»; когда я вышел из его кабинета несколько часов спустя, я был другим человеком. Ибо, терпеливо выслушав мои проблемы, он согласился, что до этого момента не было особой дисциплины программирования, но затем он продолжил спокойно объяснять, что автоматические компьютеры были здесь, чтобы остаться, что мы были только в начале, и не могу ли я быть одним из тех, кто призван сделать программирование уважаемой дисциплиной в грядущие годы? Это был поворотный момент в моей жизни, и я завершил свое формальное изучение физики так быстро, как только мог.
— Эдсгер Дейкстра, «Скромный программист» (EWD340), «Коммуникации ACM»
Когда Дейкстра женился на Марии "Рии" К. Дебетс в 1957 году, в рамках брачного обряда он должен был указать свою профессию. Он заявил, что он программист, что было неприемлемо для властей, поскольку в то время в Нидерландах такой профессии не было. [7] [8]
В 1959 году он получил докторскую степень в Амстердамском университете за диссертацию под названием «Связь с автоматическим компьютером» [9], посвященную описанию языка ассемблера, разработанного для первого коммерческого компьютера, разработанного в Нидерландах, Electrologica X1 . Руководителем его диссертации был Ван Вейнгаарден. [10]
С 1952 по 1962 год Дейкстра работал в Математическом центре в Амстердаме [10] , где он тесно сотрудничал с Брэмом Яном Лоопстрой и Карелом С. Шолтеном , которых наняли для создания компьютера. Их режим взаимодействия был дисциплинированным: сначала они принимали решение об интерфейсе между оборудованием и программным обеспечением, написав руководство по программированию. Затем разработчики оборудования должны были быть верны своей части контракта, в то время как Дейкстра, программист, писал программное обеспечение для несуществующей машины. Два урока, которые он извлек из этого опыта, заключались в важности четкой документации и в том, что отладки программы можно в значительной степени избежать с помощью тщательного проектирования. [6] Дейкстра сформулировал и решил задачу о кратчайшем пути для демонстрации на официальном открытии компьютера ARMAC в 1956 году. Из-за отсутствия журналов, посвященных автоматическим вычислениям, он не публиковал результат до 1959 года.
В Математическом центре Дейкстра и его коллега Яап Зонневельд разработали первый компилятор для языка программирования ALGOL 60 к августу 1960 года, более чем за год до того, как компилятор был создан другой группой. [6] ALGOL 60 известен как ключевой шаг вперед в развитии структурного программирования.
В 1962 году Дейкстра переехал в Эйндховен , а затем в Нюэнен , на юге Нидерландов, где он стал профессором кафедры математики в Технологическом университете Эйндховена . [10] В университете не было отдельного факультета компьютерных наук, и культура математического факультета не особенно его устраивала. Дейкстра попытался создать группу компьютерных учёных, которые могли бы сотрудничать при решении проблем. Это была необычная модель исследований для математического факультета. [6] В конце 1960-х годов он создал операционную систему THE (названную в честь университета, тогда известного как Technische Hogeschool Eindhoven ), которая повлияла на дизайн последующих операционных систем благодаря использованию программно-ориентированной страничной виртуальной памяти. [11]
Дейкстра присоединился к Burroughs Corporation — компании, известной тогда производством компьютеров на основе инновационной аппаратной архитектуры — в качестве научного сотрудника в августе 1973 года. Его обязанности состояли в посещении некоторых исследовательских центров фирмы несколько раз в год и проведении собственных исследований, которые он проводил в самом маленьком исследовательском учреждении Burroughs, а именно в своем кабинете на втором этаже своего дома в Нюэнене. Фактически, Дейкстра был единственным научным сотрудником Burroughs и работал на него из дома, время от времени выезжая в его филиалы в Соединенных Штатах. В результате он сократил свое назначение в университете до одного дня в неделю. Тот день, вторник, вскоре стал известен как день знаменитого «Вторничного полуденного клуба», семинара, в ходе которого он обсуждал со своими коллегами научные статьи, рассматривая все аспекты: нотацию, организацию, представление, язык, содержание и т. д. Вскоре после того, как в 1984 году он переехал в Техасский университет в Остине (США), в Остине, штат Техас , появился новый «филиал» Вторничного полуденного клуба . [10]
Годы Берроуза были для него наиболее плодовитыми в плане исследовательских статей. Он написал около 500 документов в серии EWD (описанной ниже), большинство из которых были техническими отчетами, для частного распространения в пределах избранной группы. [6]
В 1984 году Дейкстра занял кафедру Schlumberger Centennial на кафедре компьютерных наук Техасского университета в Остине.
Дейкстра работал в Остине до своей отставки в ноябре 1999 года. Чтобы отметить это событие и почтить его сорок с лишним лет плодотворного вклада в вычислительную науку , Департамент компьютерных наук организовал симпозиум, который состоялся в его 70-й день рождения в мае 2000 года. [6]
Дейкстра и его жена вернулись из Остина в его родной дом в Нюэнене, Нидерланды, где он обнаружил, что ему осталось жить всего несколько месяцев. Он сказал, что хочет выйти на пенсию в Остине, штат Техас , но умереть в Нидерландах. Дейкстра умер 6 августа 2002 года после долгой борьбы с раком. [3] [12] [13] [14] У него и его жены остались трое детей: Маркус, Фемке и компьютерный ученый Рутгер М. Дейкстра. [15]
Вряд ли можно винить Массачусетский технологический институт за то, что он не обратил внимания на малоизвестного ученого-компьютерщика из маленького городка в Нидерландах.
— Дейкстра, сказал о себе в Нюэнене в середине 1960-х годов. [17]
В мире компьютерной науки Дейкстра хорошо известен как «персонаж». В предисловии к своей книге «Дисциплина программирования» (1976) он заявил следующее: «За отсутствие библиографии я не даю ни объяснений, ни извинений». Фактически, большинство его статей и книг вообще не имеют ссылок. [10] Дейкстра выбрал такой способ работы, чтобы сохранить свою самостоятельность. [18]
Будучи университетским профессором большую часть своей жизни, Дейкстра рассматривал преподавание не просто как обязательную деятельность, но и как серьезное исследовательское начинание. [6] Его подход к преподаванию был нетрадиционным. [19] Его стиль чтения лекций описывался как своеобразный. Во время чтения лекций длинные паузы между предложениями часто приписывались тому факту, что английский не был родным языком Дейкстры. Однако паузы также служили для него способом думать на ходу, и он считался быстрым и глубоким мыслителем во время чтения лекций. Его курсы для студентов в Остине имели мало общего с компьютерной наукой, но они касались представления математических доказательств. [10] В начале каждого семестра он фотографировал каждого из своих студентов, чтобы запомнить их имена. Он никогда не следовал учебнику , за возможным исключением своего собственного, пока он находился в стадии подготовки. Во время чтения лекций он писал доказательства мелом на доске, а не использовал проекционную фольгу. Он предлагал студентам предлагать идеи, которые он затем исследовал или отказывался исследовать, потому что они нарушали некоторые из его принципов. Он давал сложные домашние задания и тщательно изучал решения своих студентов. Он проводил свои выпускные экзамены устно, в течение целой недели. Каждый студент был обследован в офисе или дома у Дейкстры, и экзамен длился несколько часов. [6]
Дейкстра также был весьма оригинален в своем способе оценки способностей людей к работе. Когда Владимир Лифшиц приехал в Остин в 1990 году на собеседование, Дейкстра дал ему головоломку. Лифшиц решил ее и с тех пор работает в Остине. [10]
Он избегал использования компьютеров в своей работе в течение многих десятилетий. Даже после того, как он поддался на уговоры коллег из Техасского университета и приобрел компьютер Macintosh , он использовал его только для электронной почты и просмотра Всемирной паутины. [20] Дейкстра никогда не писал свои статьи с помощью компьютера. Он предпочитал полагаться на свою пишущую машинку , а позже на ручку Montblanc . [10] Любимым пишущим инструментом Дейкстры была перьевая ручка Montblanc Meisterstück .
Он не пользовался текстовыми процессорами , полагая, что человек должен уметь писать письмо или статью без черновиков, переписывания или какого-либо существенного редактирования. Он все продумывал в голове, прежде чем положить перо на бумагу, и однажды упомянул, что когда он был студентом-физиком, он решал домашние задания в уме, гуляя по улицам Лейдена . [ 6] Большинство публикаций Дейкстры были написаны им в одиночку. У него никогда не было секретаря, и он сам занимался всей своей корреспонденцией. [10] Когда коллеги подготовили юбилейный сборник к его шестидесятилетию, опубликованный Springer-Verlag , он потрудился поблагодарить каждого из 61 автора отдельно, в рукописном письме. [10]
В книге «Скромный программист» (1972) Дейкстра писал: «Мы не должны забывать, что это не наше [специалистов по вычислительной технике] дело — создавать программы, это наше дело — проектировать классы вычислений, которые будут демонстрировать желаемое поведение».
Дейкстра также выступал против включения программной инженерии в академическую компьютерную науку. Он писал, что «так же, как экономика известна как «жалкая наука», программная инженерия должна быть известна как «обреченная дисциплина», обреченная, потому что она не может даже приблизиться к своей цели, поскольку ее цель внутренне противоречива». И «программная инженерия приняла в качестве своего устава «Как программировать, если вы не можете». [21]
Дийкстра вел скромный образ жизни, вплоть до спартанского. [10] Его дом и дом его жены в Нюэнене были простыми, маленькими и непритязательными. У него не было телевизора, видеоплеера или мобильного телефона, и он не ходил в кино. [10] Он играл на пианино и, находясь в Остине, любил ходить на концерты. Дийкстра был энтузиастом классической музыки , его любимым композитором был Моцарт . [6]
На протяжении всей карьеры Дейкстры его работа характеризовалась элегантностью и экономией. [10] Плодовитый писатель (особенно как эссеист), Дейкстра написал более 1300 статей, многие из которых были написаны от руки его точным почерком. Это были эссе и притчи; сказки и предостережения; всеобъемлющие объяснения и педагогические предлоги. Большинство из них были посвящены математике и информатике; другие представляли собой отчеты о поездках, которые больше раскрывали их автора, чем людей и посещенные места. У него была привычка копировать каждую статью и распространять ее среди небольшой группы коллег, которые копировали и пересылали статьи другой ограниченной группе ученых. [22]
Дейкстра был хорошо известен своей привычкой тщательно составлять рукописи своей авторучкой . Рукописи называются EWD, поскольку Дейкстра нумеровал их, добавляя к ним EWD , свои инициалы. По словам самого Дейкстры, EWD начались, когда он переехал из Математического центра в Амстердаме в Эйндховенский технологический университет (тогда Technische Hogeschool Eindhoven). После переезда в Эйндховен Дейкстра более года испытывал творческий кризис . Он распространял фотокопии нового EWD среди своих коллег. Многие получатели фотокопировали и пересылали свои копии, поэтому EWD распространились по всему международному сообществу компьютерных наук. Темами были компьютерная наука и математика, и они включали отчеты о поездках, письма и речи. Эти короткие статьи охватывают период в 40 лет. Почти все EWD, появившиеся после 1972 года, были написаны от руки. Они редко бывают длиннее 15 страниц и последовательно пронумерованы. Последний, № 1318, датирован 14 апреля 2002 года. В компьютерной науке они известны как отчеты EWD или просто EWD. Было отсканировано более 1300 EWD, и все большее число из них было расшифровано для облегчения поиска, и они доступны онлайн в архиве Дейкстры Техасского университета. [23]
Его интерес к простоте появился в раннем возрасте и под руководством матери. Однажды он сказал, что спросил свою мать, является ли тригонометрия сложной темой. Она ответила, что он должен выучить все формулы и что, кроме того, если ему требуется больше пяти строк, чтобы что-то доказать, он на неправильном пути. [24]
Дейкстра был известен своим остроумием, красноречием, грубостью, резкостью и часто жестокостью по отношению к коллегам-профессионалам, а также манерой обращения со словами, например, в его замечании: «Вопрос о том, могут ли машины думать (…), примерно так же актуален, как вопрос о том, могут ли подводные лодки плавать». [25] Его советом перспективному исследователю, который спросил, как выбрать тему для исследования, была фраза: «Делай только то, что можешь делать только ты». [6] Дейкстра также был известен своей громкой критикой и отсутствием социальных навыков при взаимодействии с коллегами. Как откровенный и критически настроенный визионер, он решительно выступал против преподавания BASIC . [26]
Во многих своих остроумных эссе Дейкстра описывал вымышленную компанию, председателем которой он был. Компания называлась Mathematics, Inc., компания, которая, как он представлял, коммерциализировала производство математических теорем таким же образом, как компании-разработчики программного обеспечения коммерциализировали производство компьютерных программ. Он придумал ряд видов деятельности и проблем Mathematics Inc. и задокументировал их в нескольких статьях серии EWD. Воображаемая компания представила доказательство гипотезы Римана , но затем столкнулась с большими трудностями при сборе гонораров от математиков, которые доказали результаты, предполагая гипотезу Римана. Само доказательство было коммерческой тайной . [27] Многие из доказательств компании были спешно выброшены за дверь, и затем большую часть усилий компании пришлось потратить на поддержание . [28] Более успешной попыткой было Стандартное доказательство теоремы Пифагора , которое заменило более 100 несовместимых существующих доказательств. [29] Дейкстра описал Mathematics Inc. как «самый захватывающий и самый несчастный бизнес, когда-либо задуманный». [27] EWD 443 (1974) описывает его вымышленную компанию как имеющую более 75% доли мирового рынка. [30] [31]
Дейкстра получил премию Тьюринга в 1972 году за пропаганду структурного программирования, парадигмы программирования, которая использует структурированный поток управления в противовес неструктурированным переходам к различным разделам программы с помощью операторов Goto . Его письмо 1968 года редактору Communications of ACM « Оператор Go To считается вредным » вызвало серьезные дебаты. Современные программисты в целом придерживаются парадигмы структурного программирования. [32]
Среди его самых известных вкладов в информатику — алгоритм кратчайшего пути , известный как алгоритм Дейкстры , широко преподаваемый в современных курсах бакалавриата по информатике. Среди его других вкладов — алгоритм сортировочной станции ; система мультипрограммирования THE , важный ранний пример структурирования системы как набора слоев; алгоритм банкира ; и конструкция семафора для координации нескольких процессоров и программ. Еще одна концепция, сформулированная Дейкстрой в области распределенных вычислений, — это самостабилизация — альтернативный способ обеспечения надежности системы. Алгоритм Дейкстры используется в SPF, Shortest Path First , который используется в протоколах маршрутизации OSPF и IS-IS . [33] [34]
Среди наград и почестей Дейкстры: [20]
В 1969 году Британское компьютерное общество (BCS) получило одобрение на премию и стипендию, Выдающийся член Британского компьютерного общества (DFBCS), которая должна была быть присуждена в соответствии с постановлением 7 их королевской хартии . В 1971 году были проведены первые выборы, на этот раз Дейкстры. [39]
В 1990 году по случаю 60-летия Дейкстры Департамент компьютерных наук (UTCS) Техасского университета в Остине организовал двухдневный семинар в его честь. Докладчики приехали со всех уголков Соединенных Штатов и Европы, а группа компьютерных ученых внесла вклад в исследовательские статьи, которые были отредактированы в книгу. [40]
В 2002 году японский фонд C&C Foundation наградил Дейкстру «за его новаторский вклад в создание научной основы компьютерного программного обеспечения посредством творческих исследований в области базовой теории программного обеспечения, теории алгоритмов, структурного программирования и семафоров». Дейкстра был жив, чтобы получить уведомление о награде, но ее приняла его семья на церемонии награждения после его смерти.
Незадолго до своей смерти в 2002 году Дейкстра получил премию ACM PODC Influential-Paper Award в области распределенных вычислений за работу по самостабилизации вычислений программ. Эта ежегодная премия была переименована в премию Дейкстры ( Edsger W. Dijkstra Prize in Distributed Computing ) в следующем году в его честь.
Премия Дейкстры за выдающиеся академические достижения в области компьютерных наук ( Университет Лойолы, Чикаго , кафедра компьютерных наук) названа в честь Эдсгера В. Дейкстры. Начиная с 2005 года, эта награда отмечает высшую академическую успеваемость выпускников факультета компьютерных наук. Отбор осуществляется на основе среднего балла по всем основным курсам и выборов преподавателей факультета. [41]
Факультет компьютерных наук (UTCS) Техасского университета в Остине провел первую лекцию памяти Эдсгера В. Дейкстры 12 октября 2010 года. Тони Хоар , почетный профессор Оксфорда и главный научный сотрудник Microsoft Research, выступил на мероприятии. Эта серия лекций стала возможной благодаря щедрому гранту Schlumberger в память о Дейкстре.
Алан М. Тьюринг размышлял о критериях для решения вопроса о том, могут ли машины мыслить, вопроса, о котором мы теперь знаем, что он примерно так же актуален, как вопрос о том, могут ли подводные лодки плавать.(транскрипция), 1984
