IT-Персоны - Программист, который писал притчи и не любил бейсик

Новости it-компаний

Корпорация Dell объявила о выходе на рынок двух новых моделе

News image

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

IBM и Novell завершили сертификацию SUSE LINUX по новому, бо

News image

Компании IBM и Novell объявили о том, что система SUSE LINUX Enterprise Server 9 успешно пр...

Авторизация



Развитие технологий:

Процессор Pentium 4

В 2000 г. корпорация Intel анонсировала следующее поколение 32-разрядных процессоров, которое получило название Pentium 4, в корпусе под Socket 423, а ...

Второе поколение процессоров Pentium

О втором поколении процессоров Pentium было объявлено в марте 1994 г. Тактовая частота для них составляла 90 МГц (149,8 млн. оп...


Программист, который писал притчи и не любил бейсик
Это интересно - Персоны

программист, который писал притчи и не любил бейсик

В прикладной науке имена людей, внесших огромный вклад в развите техники и технологии, как правило, скрыты за названиями компаний и стандартов, но несмотря на это, имя Эдсгера Дейкстра навеки будет вписано золотыми буквами в историю компьютерной индустрии, и все это благодаря огромному количеству концепций, ставших привычными и общепринятыми. Более сорока лет Дейкстра отдал этой отрасли науки. С его именем неразравно связаны такие идеи как структурированное (структурное) программирование (ставшее фундаментом объектно-ориентированного подхода) или алгоритм Shortest Path Algorithm (первоначального открытия кратчайшего пути для маршрутизаторов Интернета). Этот алгоритм я продемонстрирую вам в конце этой статьи.

6 августа на 72 году жизни в своем доме в Нидерландах, после долгой борьбы с недугом скончался от рака один из пионеров вычислительных наук профессор Эдсгер Вайб Дейкстра (Edsger Wybe Dijkstra), выдающийся теоретик компьютерного программирования. Также Дейкстра являлся одним из создателей языка программирования Алгол и автором термина структурное программирование .

Эдсгер Вайб Дейкстра родился в 1930 году в голландском городе Роттердам в семье ученых, его отец был химиком, мать - математиком. Окончил гимназию Эразма Роттердамского, после чего получил степень магистра математики и теоретической физики в Университете Лейдена, а также звание доктора компьютерных наук в Университете Амстердама. Позже Дейкстра работал программистом в амстердамской организации Mathematisch Centrum, а затем профессором в Техническом университете Эйндховена, где преподавал математику. Параллельно он занимался исследованиями для корпорации Барроуз.

Еще в 1955 году он решил сменить профессию физика-теоретика на программиста (как пишет сам Дейкстра, в то время профессии программиста еще не было в официальном справочнике ), а в 1968 году его имя стало широко известным, что являлось следствием публикации его знаменитой статьи в Communications of the ACM о недопустимости использования оператора GOTO. Это заложило основы структурированного программирования. Впоследствии были другие не менее значимые работы (хотя в последние годы Дейкстра весьма критически отзывался о техническом прогрессе в области ИТ: Электронная индустрия не решает проблемы, а только создает новые ).

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

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

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

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

Рабочая группа была создана при IFIP (International Federation on Information Processing) - тогда эта общественная организация играла роль создателя стандартов. В 1968 году IFIP приняла новый вариант языка, названный Алгол 68. За время создания этой версии идеология программирования изменилась, и его праотцы, среди которых был и Дейкстра, уже отрицательно отнеслись к новой реализации. Однако во время разработки языка Алгол были фактически сформулированы общие принципы языкостроения . Например, участник рабочей группы, знаменитый Никлаус Вирт, позже создал один из самых популярных языков Паскаль. Стоит отметить, что в работе международной группы принимал участие (по почте) и советский ученый Григорий Цейтлин.

Ситуация, возникшая вокруг языка Алгол, фактически определила стиль дальнейшего развития программирования. Почти в каждую программистскую эпоху наблюдалось противостояние двух языков программирования, что означало попытку реализовать две разные идеологии. Началось все с борьбы языков Алгол-60 и Фортран. В 80-е годы свысока смотрели друг на друга сторонники языков Паскаль и Си. По этому поводу даже существует анекдот: Приехал Никлаус Вирт в Италию и спрашивает у местных программистов: Вам нравится язык Паскаль? Си! - отвечают они. Вирт был очень расстроен . Конец 90-х годов был отмечен противостоянием идеологий Си++ и Java.

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

Он предложил использовать при создании программы всего три логические структуры: sequence (следование), selection (ветвление) и iteration (цикл). Получалось, что такой оператор, как goto (от go to - дословно иди к ), становился лишним. Оператор goto позволяет переключить выполнение программы на другой оператор, который может находиться практически в любом месте ее текста. Непосвященный человек может представить этот оператор в виде указания в тексте романа: читай на странице 100 . Таких переходов может быть множество, и логика романа или программы становится запутанной.

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

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

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

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

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

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

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

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

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

Более тысячи трехсот работ, составляющих около восьми тысяч страниц, покойного профессора в электронной форме благодаря усилиям его коллег доступны сегодня на сайте кафедры информатики Университета Техаса (www.cs.utexas.edu/users/EWD). По-русски публиковалась самая известная монография Дейкстры Дисциплина программирования (М.: Мир , 1976), их совместная с У. Далом и К. Хоором книга Структурное программирование (М.: Мир , 1975) и ряд статей. В том же издательстве Мир в 1984 году вышел перевод учебника Наука программирования , написанного одним из самых горячих приверженцев подхода Дейкстры Д. Грисом.

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

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

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

Впоследствии, с 1973 по 1999 гг., он возглавлял кафедру информатики, созданную компаниями Schlumberger и Centennial, Университета Техаса в Остине, был почетным профессором Техасского университета, членом Голландской королевской академии наук и искусств, иностранным почетным членом Американской академии наук и искусств, почетным членом Британского компьютерного общества, почетным доктором наук Королевского университета Белфаста.

АЛГОРИТМ

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

Задача:

В ориентированной, неориентированной или смешанной (т. е. такой, где часть дорог имеет одностороннее движение) сети V найти кратчайший путь из заданной вершины i во все остальные вершины.

Решение (Дейкстpа, 1959 г.)

Алгоритм использует три массива из N (= числу вершин сети) чисел каждый. Первый массив A содержит метки с двумя значениями:

0 (вершина еще не рассмотрена) и 1 (вершина уже рассмотрена);

второй массив B содержит расстояния - текущие кратчайшие расстояния (от-до) соответствующей вершины; третий массив С содержит номера вершин - k-й элемент С[k] есть номер предпоследней вершины на текущем кратчайшем пути из Vi в Vk. Матрица расстояний D[i,k] задает длины дуге D[i,k]; если такой дуги нет, то D[i,k] присваивается большое число, равное машинной бесконечности .

Теперь можно описать Алгоритм Дейкстры

1 (инициализация). В цикле от 1 до N заполнить нулями массив A; заполнить числом i массив C; перенести i-ю строку матрицы D в массив B,

A[i]:=1; C[i]:=0 (i - номер стартовой вершины)

2 (общий шаг). Hайти минимум среди неотмеченных (т. е. тех k, для которых A[k]=0); пусть минимум достигается на индексе j, т. е. B[j]<=B[k]

Затем выполняются следующие операции:

A[j]:=1;

если B[k]>B[j]+D[j,k], то (B[k]:=B[j]+D[j,k]; C[k]:=j)

(Условие означает, что путь Vi ... Vk длиннее, чем путь Vi...Vj Vk).

(Если все A[k] отмечены, то длина пути от Vi до Vk равна B[k]. Теперь надо перечислить вершины, входящие в кратчайший путь).

3 (выдача ответа). (Путь от Vi до Vk выдается в обратном порядке следующей процедурой:)

3.1. z:=C[k];

3.2. Выдать z;

3.3. z:=C[z]. Если z = О, то конец,

иначе перейти к 3.2.

Для выполнения алгоритма нужно N раз просмотреть массив B из N элементов, т. е. алгоритм Дейкстры имеет квадратичную сложность: O(n2).

Притча

В незапамятные времена была организована железнодорожная компания. Один из её руководителей (вероятно, коммерческий директор) обнаружил, что можно сэкономить ну просто огромные деньги, если снабжать туалетом не каждый вагон, а лишь половину из них. На том и порешили.

Однако вскоре после начала перевозок пассажиров начались неприятности. Причина их крайне проста: о распоряжении ничего не знали на сортировке и считали все вагоны одинаковыми. В результате в некоторых поездах туалеты практически отсутствовали.

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

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

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

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

Технически это было уже невозможно. И вот тут кто-то заметил: если мы сцепим вагон с туалетом и вагон без туалета в пару так, чтобы туалет находился посередине, и никогда их не будем расцеплять, то сортировка будет иметь дело вместо N ориентированных объектов с N/2 симметричных объектов. Но это решение требовало и двух уступок: во-первых, поезда теперь могли состоять только из чётного количества вагонов (кого волнует, что кому-то может не хватить мест); во-вторых, туалеты были расположены на несколько неравном расстоянии (и тем более, кому интересен лишний метр).

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

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

 


Читайте:


Добавить комментарий


Защитный код
Обновить

Творцы улыбок

News image

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

КОНРАД ЦУЗЕ. ПИОНЕР КОМПЬЮТЕРОСТРОЕНИЯ

News image

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

Жесткие диски для ноутбуков становятся тоньше

News image

На данный момент жесткие диски для ноутбуков могут быть толщиной 9,5 мм и 12,5 мм. Первые получили наибольшее распространение, а об...

Financial Times обещает iTablet уже в следующем месяце

News image

Конец декабря редакция Financial Times решила скрасить очередной порцией слухов о планшетнике Apple. По данным издания, это устройство, покорившее заголовки СМ...

MacBU подытоживает две тысячи девятый год

News image

Как прошел 2009 год в компании, которую традиционно принято считать вторым крупнейшим разработчиков ПО для платформы Apple Macintosh? В Microsoft Ma...

Планшетный Мак покажут 26 января?

News image

За несколько дней до начала нового 2010 года онлайн-пресса разразилась новым потоком слухов на тему планшетного компьютера Apple: сначала хорошо ос...

VESA официально утвердила стандарт mini DisplayPort

News image

Презентованный Apple осенью 2008-го новый видеоинтерфейс mini DisplayPort (сокращенно mDP) вызвал неоднозначную реакцию, отголоски которой оставались различимыми вплоть до вчерашнего дн...

Внедрение 6-ядерных процессоров Intel Xeon может потребовать

News image

Изданию Fudzilla стали известны подробности по первому 6-ядерному процессору Intel Xeon. Он получит обозначение Core i7 980X, а его несущая тактовая ча...