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

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

Эдсгер Wybe Дейкстра ( / d aɪ к s т г ə / Dyke -strə ; голландский:  [ɛtsxər ʋibə dɛikstra] ( слушать ) ; 11 мая 1930 - 6 августа 2002) был голландский ученый , программист , инженер - программист , системы ученый , наука эссеист , ^{[9] [10]} и пионер в компьютерной науки . ^[11] По образованию физик-теоретик , работал программистом.в Математическом центре (Амстердам) с 1952 по 1962 год. Профессор университета на протяжении большей части своей жизни, Дейкстра занимал столетнюю кафедру компьютерных наук Шлюмберже в Техасском университете в Остине с 1984 года до своей пенсии в 1999 году. математик в технологическом университете Эйндховена (1962-1984) и научный сотрудник в Burroughs Corporation (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 Award в области распределенных вычислений за свою работу по самостабилизации программных вычислений. В следующем году эта ежегодная награда была переименована в Премию Дейкстры ( премия Эдсгера В. Дейкстры в области распределенных вычислений). ^[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 года.

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

Технологический университет Эйндховена [ править ]

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

Корпорация Берроуз [ править ]

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

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

Техасский университет в Остине [ править ]

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

Последние годы [ править ]

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

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

Новаторский вклад и влияние на информатику [ править ]

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

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

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

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

Алгоритмическая работа [ править ]

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

В 1959 году Дейкстра опубликовал в трехстраничной статье «Заметка о двух проблемах, связанных с графами» алгоритм поиска кратчайшего пути в графе между любыми двумя заданными узлами, который теперь называется алгоритмом Дейкстры . Его влияние в течение следующих 40 лет резюмируется в статье Миккеля Торупа «Ненаправленные кратчайшие пути из одного источника с положительными целочисленными весами в линейное время» (1999): «С 1959 года все теоретические разработки в SSSP [Single-Source Shortest Paths] для общих ориентированных и неориентированных графов были основаны на алгоритме Дейкстры ». Алгоритм Дейкстры используется в SPF, Shortest Path First , который используется в протоколах маршрутизации 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] Его можно использовать для вывода в обратной польской нотации (RPN) или в виде абстрактного синтаксического дерева (AST). Алгоритм был назван маневровым ярд алгоритм , поскольку его эксплуатация напоминает на железной дороге маневрового двор . Алгоритм маневровой станции обычно используется для реализации синтаксических анализаторов приоритета операторов .

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

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

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

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

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

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

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

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

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

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

-  Никлаус Вирт , 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-х годах активно программировал машинный код, он пришел к выводу, что в языках высокого уровня частое использование оператора GOTO обычно является признаком плохой структуры. В 1968 году он написал частную статью «Дело против заявления GO TO» ^[55], которое затем было опубликовано в виде письма в CACM. ^[56] Редактор Никлаус Вирт назвал это письмо заголовком « Перейти к заявлению, признанному вредным », в котором была введена фраза « считается вредным » для компьютеров.

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

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

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

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

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

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

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

Рост движения структурного программирования привел ко многим другим структурированным подходам, применяемым к разработке программного обеспечения . Методы структурированного анализа и структурированного проектирования являются результатом концепций и методов структурированного программирования, а также ранних идей о модульном дизайне. Принципы модульности были усилены Ларри Константин «ы концепций из соединения (чтобы свести к минимуму между модулями) и когезии (до максимума в пределах модулей), с помощью Дэвид Парнас » ы техники из сокрытия информации , а также абстрактных типов данных . ^[66]Ряд инструментов и методов , использующих структурированные концепции были разработан, такими как Structured Design , Структурированное программирование Джексона , Росс " Структурированный анализ и проектирование Техник (SADT), Йордан структурирован метод , структурированный анализ и проектирование Method (Ssadm) и Джеймс Мартин информации технологическая инженерия . Сфера программных метрик часто рассматривается как прямое влияние движения структурного программирования на программную инженерию 1970-х годов.

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

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

В 1960-х Дейкстра и его коллеги в Эйндховене разработали и внедрили операционную систему THE (расшифровывается как « Technische Hogeschool Eindhoven ») , которая была организована в четко определенные уровни абстракции . ^[68] Его статья 1968 года на эту тему заложила основу для последующих разработок операционных систем. Дэвид Алан Грир из IEEE Computer Societyпишет: «Обычно мы прослеживаем идею построения компьютерных систем по слоям еще в статье 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]

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Личность и стиль работы [ править ]

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

-  EW Dijkstra, "О природе вычислительной науки" (EWD896), август 1984 г.

Вряд ли можно винить Массачусетский технологический институт в том, что он не заметил малоизвестного ученого-информатика в маленьком городке в Нидерландах.

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

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

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

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

-  EW 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 электронных документов, число которых растет для облегчения поиска, и они доступны в Интернете в архиве Дейкстры Техасского университета. ^[100]

Личная жизнь и смерть [ править ]

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

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

Влияние и признание [ править ]

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

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

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

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

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

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

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

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

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

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

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

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

Награды и награды [ править ]

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

• Член Королевской Нидерландской академии искусств и наук (1971) ^[108]
• Заслуженный член Британского компьютерного общества (1971 г.)
• Ассоциация вычислительной техники «S Тьюринга AM (1972) ^[109]
• Мемориальная награда Гарри Х. Гуда от компьютерного общества IEEE (1974). ^[110]
• Иностранный почетный член Американской академии искусств и наук (1975).
• Доктор наук Honoris Causa из Королевского университета в Белфасте (1976)
• Получатель хартии Computer Pioneer от компьютерного общества IEEE (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 Award в области распределенных вычислений за свою работу по самостабилизации программных вычислений. В следующем году эта ежегодная награда была переименована в Премию Дейкстры ( Премия Эдсгера В. Дейкстры в области распределенных вычислений ) в его честь.

Премия Дейкстры за выдающиеся академические достижения в области компьютерных наук ( Университет Лойола, Чикаго , факультет компьютерных наук) присуждается в честь Эдсгера В. Дейкстры. Начиная с 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 . DOI : 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. DOI : 10,1109 / MS.2002.1032847 . S2CID  29320163 .
• Дневной свет, Эдгар Г. (2012). Эра программной инженерии: от Тьюринга до Дейкстры . Одинокий ученый. ISBN 9789491386022.
• Дневной свет, Эдгар Г. (2011). «Призыв Дейкстры к обобщению: появление рекурсивной процедуры, конец 1950-х - начало 1960-х годов». Компьютерный журнал . 54 (11): 1756–72. DOI : 10.1093 / comjnl / bxr002 .
• Долев, Шломи (2000). Самостабилизация . MIT Press. ISBN 978-0-262-04178-2.
• Фейен, WHJ; Грис, Дэвид, ред. (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. DOI : 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 . Архивировано 5 мая 2018 года из оригинального (PDF) .
• Ли, Янв (1991). «Границы вычислений: дань уважения Эдсгеру В. Дейкстре по случаю его 60-летия». Анна. Hist. Комп . 13 (1): 91–96. DOI : 10.1109 / MAHC.1991.10000 .
• Марков, Джон (2002). "Эдсгер Дейкстра, 72 года, физик, который сформировал компьютерную эру" . Нью-Йорк Таймс .
• Милоне, Лоренцо (2009). "EW 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. DOI : 10.1109 / MAHC.2014.54 . S2CID  9029390 .
• Шаша, Деннис; Лазер, Кэти (2 июля 1998 г.). Вне их разума: жизни и открытия 15 великих ученых-компьютерщиков . Springer. ISBN 978-0-387-98269-4.

Внешние ссылки [ править ]

Викискладе есть медиафайлы по теме Эдсгера Вайбе Дейкстры .

В Wikiquote есть цитаты, связанные с: Эдсгер В. Дейкстра

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