Реферат Дейкстра. Эдскгер Вибе Дейкстра. Эдскгер Вибе Дейкстра. Родился в 1930м году, 11 мая в Роттердаме, Нидерланды
 Скачать 15.74 Kb.
|
|
Эдскгер Вибе Дейкстра. Родился в 1930м году, 11 мая в Роттердаме, Нидерланды. Семья ученых: Отец – химик, мать – Математик. По окончанию школы поступил на факультет теоретической физики Лейденского университета. Его увлечение программированием началось в 1951м году, поступив на трёхнедельные компьютерные курсы в Кембридже. С 1952 года работал программистом в Математическом центре Амстердама во главе с профессором Ван Вейнгаардена (Кстати, в последующем являющийся автором спобова формального описания грамматики формальных языков – Метод двухуровневой грамматики Ван Вейнгаардена). Для ясности, Формальный язык - это математическая модель реального языка. Под реальным языком здесь понимается некий способ общения субъектов друг с другом. После 1952 года он окончательно принял курс на программирование, пусть и закончив до конца курс физики. В 1956 году принял участие в разработке ЭВМ X1, где и был применен его алгоритм, для разводки плат ЭВМ. В последствии он стал предметом диссертации Дейкстры. Работал данный компьютер на транзисторах и ферромагнетиках, тем самым сыскав большой успех. Память, к слову, являлась не перезаписываемой, с объёмом 108кб, в которой каждое слово кодировалось 27 битами. Суть алгоритма Дейкстры заключался в Кратчайшем пути. Появился данный алгоритм в результате оценки мощности компьютера ARCMAC. Суть крылась в поиске наикратчайшего пути, для преодоления расстояния между точками. Как он работает? Инициализация: Метка самой вершины 1 полагается равной 0, метки остальных вершин – недостижимо большое число (в идеале — бесконечность). Это отражает то, что расстояния от вершины 1 до других вершин пока неизвестны. Все вершины графа помечаются как не посещённые. Первый шаг Минимальную метку имеет вершина 1. Её соседями являются вершины 2, 3 и 6. Обходим соседей вершины по очереди. Первый сосед вершины 1 – вершина 2, потому что длина пути до неё минимальна. Длина пути в неё через вершину 1 равна сумме кратчайшего расстояния до вершины 1 (значению её метки) и длины ребра, идущего из 1-й во 2-ю, то есть 0 + 7 = 7. Это меньше текущей метки вершины 2 (10000), поэтому новая метка 2-й вершины равна 7. Аналогично находим длины пути для всех других соседей (вершины 3 и 6). Все соседи вершины 1 проверены. Текущее минимальное расстояние до вершины 1 считается окончательным и пересмотру не подлежит. Вершина 1 отмечается как посещенная. Второй шагШаг 1 алгоритма повторяется. Снова находим «ближайшую» из не посещенных вершин. Это вершина 2 с меткой 7. Снова пытаемся уменьшить метки соседей выбранной вершины, пытаясь пройти в них через 2-ю вершину. Соседями вершины 2 являются вершины 1, 3 и 4. Вершина 1 уже посещена. Следующий сосед вершины 2 — вершина 3, так как имеет минимальную метку из вершин, отмеченных как не посещённые. Если идти в неё через 2, то длина такого пути будет равна 17 (7 + 10 = 17). Но текущая метка третьей вершины равна 9, а 9 < 17, поэтому метка не меняется. Структурное программирование. Поскольку компьютеры сыскали большой спрос, они начали проникать во все сферы жизни человека: Образование, промышленность, бизнес и прочее. Так, программы становились объемнее, разнообразнее и соответственно – сложнее. А это, в свою очередь, сильно снизило их качество. Поэтому программированию требовалось внести легкость и гибкость, чего так не хватало в то время. Для обеспечения указанных легкости и гибкости Дейкстра предлагает проектировать и кодировать программы в соответствии с определенной дисциплиной, названной им структурным программированием. Так мы и получили три основных типа кода: Следование (Операции выполняются линейно, операция за операцией), Цикл (Возможность повтора операции при наличии определенных условиях) и Ветвление (Образование веток в коде, благодаря наличия определенного условия.) По сей день данные конструкции используются в современном программировании. Идея самого структурного программирования сразу сыскала свою популярность в языке Pascal, и по сей день является актуальной (Языки С, Pascal или Basic) В августе 2002 Дейкстра скончался у себя дома. |