Лекция 7 Биографии основных теоретиков компьютерных наук

План лекции Алан Тьюринг Джон Фон Нейман Эдсгер Вайб Дейкстра Дональд Эрвин Кнут Языки программирования и их создатели

Алан Тьюринг (1912 – 1954)

Основные результаты Тезис Чёрча-Тьюринга Машина Тьюринга Криптография Тест Тьюринга Колоссус

Тезис Чёрча-Тьюринга Любая функция, которая может быть вычислена физическим устройством, может быть вычислена машиной Тьюринга

Машина Тьюринга

Криптография Тьюринг помогал взломать код Энигмы Построен первый программируемый компьютер Колоссус Базировался: – на его концепции универсальной машины 1936 – потенциальной скорости и надёжности электронных технологий – неэффективность разностных машин для различных логических процессов Шифр-код был расшифрован в 1943 Все компьютеры были разрушены по приказу Черчилля

Colossus Под руководством выдающегося математика Алана Тьюринга была построена специализированная электронная вычислительная машина Colossus. Она насчитывала 2000 радиоламп и обрабатывала симв./с

Enigma В местечке Блечли-Парк (Bletchley Park) под Лондоном была организована сверхсекретная криптоаналитическая лаборатория для расшифровки немецких военных шифров, используемых в шифровальной машине Enigma.

Тест Тьюринга Опубликован в 1950 году Человек обменивается сообщениями на естественном языке с двумя собеседниками (человек и компьютер) Если человек не может определить кто есть кто, то считается что компьютер прошёл тест Переписка должна производиться через контролируемые промежутки времнени Тьюринг оценил что программы в 2000 году пройдут тест Пока не подошли даже близко

Джон фон Нейман

Архитектура фон Неймана В современных машинах эти блоки сочетаются в одной микросхеме, называемой центральным процессором (ЦП).

Другие значимые достижения Квантовая физика Функциональный анализ Теория множеств Создатель теории игр Создатель теории клеточных автоматов

Клеточные автоматы

Эдсгер Вайб Дейкстра (1930 – 2002)

Основные результаты Математическая логика Algol-60 Концепция семафоров Алгоритм Дейкстры Борьба с оператором GOTO

Афоризмы (1) Студентов, ранее изучавших Бейсик, практически невозможно обучить хорошему программированию. Как потенциальные программисты они подверглись необратимой умственной деградации Вопрос «умеет ли компьютер думать» имеет не больше смысла, чем вопрос «умеет ли подводная лодка плавать» Проекты, предлагающие программирование на естественном языке, гибельны по своей сути

Афоризмы (2) Дейкстра назвал модель IBM/360 (прообраз советской ЕС ЭВМ) величайшей диверсией Запада против СССР На пустом диске можно искать вечно Если отладка процесс удаления ошибок, то программирование должно быть процессом их внесения

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

Языки и системы программирования Михаил Романович Шура-Бура и А.П. Ершов – создатели первых отечественных систем автоматизации программирования для ЭВМ «БЭСМ» и «Стрела» ( годы)

Наиболее активный период разработки языков и систем программирования приходится на 1960-е годы. За это десятилетие в мире родилось более тысячи разнообразных языков, как универсальных, так и специализированных, но выжили и доросли до XXI века дожили немногие, в том числе бессмертные Fortran, Basic, Algol, Cobol, Simula, Lisp и их потомки. На рисунке: «вавилонская башня» языков программирования, созданных в 1960-е годы Язык и системы программирования

Языки и системы программирования Родословная основных высокоуровневых языков программирования

Fortran Fortran = FORmula TRANslator Первый высокоуровневый язык программирования Fortran был разработан в фирме IBM под руководством Джона Бэкуса (Backus, John; р. 1924). Работа над языком началась в 1954 г., первая реализация для IBM 704 в выполнена в 1957 г.

Fortran CMAIN PROGRAM 101FORMAT(208) 102FORMAT(//N=,15, 5X, R=, 15 1//6X, M, 5X, PROB) 103 FORMAT(18, F14.10) 201READ(1,101) N, IR WRITE(3,102) N, IR IF(N) 202, 202, STOP 203IF(IR) 202, 202, M=O P=COMBF(N,M)*COMBF(IR-1,N-M-1) 1/COMBF(N+IR-1,IR)...

Basic BASIC = Beginners All-purpuse Symbolic Instruction Code Язык Basic был разработан в 1964 г. в Дармутском колледже в г. Хановере (Darmouth College, Hanover), штат Нью-Хемпшир

Авторы языка Basic. Стоит Джон Кемени (Kemeny, John G.; ), сидит Томас Курц (Kurtz, Thomas E.; р. 1928) Basic 10 dim A(5) 20 for i=1 to 5 30 input A(i) 40 next i 50 if i=5 then goto if A(i)

Basic Будущие создатели Microsoft Пол Аллен (Allen, Paul; р. 1954) и Билл Гейтс (Gates, William; р. 1955) познакомились с Бэйсиком, работая в компьютерном классе школы в Сиэтле (снимок 1968 г.)

Basic Начав с Бэйсика, компания Microsoft превратилась в крупнейшую софтверную империю, а Билл Гейтс – стал самым богатым человеком на планете Штаб - квартира корпорации Microsoft в Редмонде (пригород Сиэтла)

Cobol COBOL = COmmon Business- Oriented Language На фото: разработчики языка Cobol у шуточного обелиска, присланного в их адрес в качестве намека на безнадежно медленную работу, способную похоронить саму идею. Справа внизу – Грейс Хоппер

Cobol Основные свойства языка Cobol: независимость программ от оборудования; независимость программ от данных; сложные структуры данных; синтаксис, приближенный к естественному английскому языку.

Cobol 1010 IDENTIFICATION DIVISION PROGRAM-ID EXAMPLE ENVIROMENT DIVISION INPUT-OUTPUT SECTION FILE-CONTROL SELECT CD ASSIGN TO SYS010 UNIT-RECORD 2540R SELECT TT ASSIGN TO SYS009 UTILITY DATA DIVISION FILE SECTION FDCDDATA RECORD IS C 1110LABEL RECORDS ARE OMITTED C C1 PICTURE 9(4) C2 PICTURE C3 PICTURE X(70).

Cobol 1290 PROCEDURE DIVISION P1.OPEN INPUT CD, OUTPUT TT P2.READ CD, AT END GO TO P MOVE C1 TO D MOVE C2 TO D MOVE C3 TO D ADD C1, C2, GIVING D WRITE T FROM D. 1370GO TO P P3.CLOSE SD, TT. 1390STOP RUN.

Algol ALGOL = ALGOrithmic Language В 1958 году в Цюрихе (Швейцария) состоялась международная конференция, предложившая проект нового универсального международного языка программирования Algol-58. В 1960 году на парижской конференции была принята окончательная версия под названием Algol-60. На снимке: участники парижской конференции голосуют за Алгол-60.

Algol Основные свойства языка Algol-60 машинная независимость; формальный синтаксис; описание переменных и блочная структура; рекурсия Нормальная форма Бэкуса-Наура (БНФ) ::= 1|2|3|4|5|6|7|8|9|0 ::= |

Algol Простейшая программа на Алголе-60, вычисляющая среднее арифметическое n чисел. Синтаксис Алгола-60 сформировал стандарт для всех последующих языков программирования begin integer i, n; real s; real array x[1:n]; s:=0; for i:=1 step 1 to n do s:=s+x[i]; s:=s/n end

Pascal Член комитета по Алголу-68 Никлаус Вирт (Wirth, Niklaus; р. 1934) был против принятия переусложненного стандарта. В знак доказательства своей правоты он разработал в 1971 г. простой и ясный алголоподобный язык, предназначенный прежде всего для обучения студентов в Федеральном техническом университете в Швейцарии. В честь изобретателя первой вычислительной машины Вирт назвал язык Паскалем.

Turbo Pascal Новую жизнь языку Pascal дал Филипп Кан (Kahn, Philippe; р. 1938) – создатель компилятора Turbo Pascal для IBM PC и основатель компании Borland (1984 г.)

PL/1 PL/1 = Programming Language One Язык PL/1 был частью амбициозного проекта IBM S/360, он создавался в спешке и представлял собой механическую смесь идей из многих языков. Критики сравнивали его с елкой со множеством украшений. EXAMPLE: PROCEDURE OPTIONS (MAIN); ON ENDFILE (SYSIN) GO TO ENDING; P1:GET LIST (A, B, C); D = B*B 4*A*C; E = B/(A+A); IF D

Simula и Smalltalk Simula = SIMULAlation За разрабртку языка Simula Кристен Нигорд (Nygaard, Kristen; ), на снимке слева, и Оле-Йохан Дал (Dahl, Ole-Johan; ) были удостоены высшей награды компьютерного сообщества – медали Тьюринга

Simula и Smalltalk Простейшая программа на Smalltalk, вычисляющая среднее арифметическое пяти чисел |a| a := Array new: 5. 1 to: 5 do: [:i | a at: i put: (Prompter prompt: Введите элемент массива) asNumber]. a := a asSortedCollection. a do: [:i | Transcript putAll: i printString].

C Язык Си (С) был создан Деннисом Ричи (Ritchie, Dennis M.; р. 1941) в 1973 году в Bell Labs в ходе разработки операционной системы UNIX. Он развивал язык Би (B), который основывался на созданном в Кембриджском университете языке BCPL (от Basic Combined Programming Language), который в свою очередь был потомком Алгола-60

C float A[5]; for(int i=0;i

C++ Бьярн Страуструп (Stroustrup, Bjarne; р. 1950) ввел в язык С объекты и превратил его в С++

Java В 1995 г. фирма Sun Microsystems представила язык Java для программирования в интернете. Он возник в ходе реализации проекта Oak («Дуб»), целью которого было создание системы программирования бытовых микропроцессорных устройств. Джеймс Гослинг (Gosling, James) – автор Java.

Java в Web

C# class test { int i, n; float s; float x[n]; public static void main( String args[] ) { n = 10; s = 0; for( i=1; i

LISP Lisp = LISt Processing Язык LISP создан в 1960 году Джоном Маккарти (McCarthy, John; р ) в Массачусетском технологическом институте на теоретическом фундаменте лямбда-исчисления, предложенного еще в 1930 году известным американским логиком Алонзо Черчем. Дж. Маккарти и А.П. Ершов Снимок 1975 г.

LISP (setq L `( )) (defun sum (L) (cond ((null L) '0) (t (add (car L) (sum (cdr L)))) ) (div (sum L) '5) Примитивы : cond условная функция, проверяющая с помощью функции null пустоту списка; add суммирование аргументов; car извлечение первого элемента из списка; cdr извлечение остатка списка (без первого элемента).