«В. П. Одинец Зарисовки по истории компьютерных наук Учебное пособие Сыктывкар 2013 УДК 004:93 ББК 32.975 О 42 Печатается по решению редакционно-издательского совета Коми государственного педагогического института от ...»

В 1943 г. тогда же, когда появилась указанная выше работа Норберта Винера, Артуро Розенблата и Джулиана Бигелов, вышла статья нейрофизиолога Уоррена Маккалока и логика Уолтера Питса (Warren McCulloch: 1898–1969; Walter Pitts: 1923–1969) [113], давшая на языке математической логики модель нейронной сети.

Через 14 лет (1957) Фрэнк Розенблатт2 издал работу, посвященную самоорганизующемуся автомату, названному «Персептроном» [112] и являвшемуся моделью сетчатки глаза. (Мы уже знаем, что М. Мински и С. Пейперт в 1969 г. показали ограниченность данной модели. И это на 20 лет затормозило исследование нейронных сетей.) Телеология – онтологическое учение о целесообразности бытия. Появилось в космологии Платона как «душа мира»; у Аристотеля – это теория «бессознательной» целесообразности, сообщаемой миру «творцом» (= перводвигателем).

Фрэнк Розенблатт (Frank C. Rosenblatt: 1928–1971) – американский компьютерный специалист, а Артуро Розенблат (Arturo Rosenblueth) – мексиканский психолог и исследователь.

В том же 1957 г. исследователи ИИ обратились к идее эвристического поиска. Пионерами были Аллен Ньюэлл (Allen Newell:

1927–1992) и Джон Клиффорд Шоу (John Clifford Show: 1922– 1991), работавшие в RAND Corporation (в Калифорнии), а также присоединившийся к ним Герберт Саймон (Herbert Simon: 1916– 2001) из Технологического Института Карнеги (в Питтсбурге).

Вместе они образовали команду, называвшуюся в среде американских «компьютерщиков» NSS (по первым буквам фамилий).

Именно команда NSS подготовила почву для широкого развития ИИ: языки программирования, компьютерная симуляция, проблемы принятия человеком (или ИИ) решения1, коммуникация человека и машины.

В 1954 г. А. Ньюэлл покинул RAND, чтобы завершить работу над диссертацией под руководством Г. Саймона. Тем не менее команда NSS продолжила работу над тремя проектами: (C.I.P.) (= Complex Information Processing) – базой компьютерных программ, развивающих шахматные программы, (LT) (= Logic Theorist) – создание языка программирования для поддержки программ (Information Processing Language), и, наконец, GPS (= General Problem Solver) – проблема эвристического поиска.

Язык IPL был создан уже к концу 1954 г., проблема эвристического поиска закончена к 1957 г., а вот проект (C.I.P.) хотя и был формально завершен, но не дал ожидаемого результата – игру на уровне гроссмейстера. (Напомним, что первую шахматную программу составил еще А. Тьюринг в 1949 г.2) Несколько отвлекаясь, заметим, что в 1949–1950 гг. Клод Шеннон (Claude Elwood Shаnnon: 1916–2001) сделал несколько докладов о шахматных программах и опубликовал статью о проHuman Problem Solving – проблема принятия решения при движении из одного состояния человека или ИИ в другое, являющееся целью.

Демонстрировать этот алгоритм А. Тьюринг стал публично в 1951 г., выполняя роль «исполнителя» команд машины.

граммировании компьютера для игры в шахматы (см. [114]), а в 1951 г. им создана и машина, игравшая в шахматы. (Более того, в 1952 г. К. Шеннон создает обучаемую машину по поиску выхода из лабиринта.) В 1957 г. американский программист Александр Бернштейн (Alex Bernstein) усовершенствовал программу К. Шеннона (см. [116]).

В 1958 г. шестой чемпион мира по шахматам доктор технических наук Михаил Моисеевич Ботвинник (1911–1995) открыто заявляет о возможности создания «компьютерного гроссмейстера». Более того, в Лаборатории, которую он возглавляет в ВНИИЭ Минэнерго СССР, начинается работа по проекту «Пионер» – создания «шахматного мастера» [115]. При этом сразу же идет отказ от простого перебора позиций, и делается упор на эвристические методы поиска.

Работа была фактически завершена только через 20 лет, но тогдашняя власть в СССР не дала возможности проверить ее на достаточно мощных ЭВМ, которые были на Западе.

В 1960–1961 гг. М. М. Ботвинник был руководителем дипломной работы выпускника механико-математического факультета Новосибирского университета Владимира Ивановича Бутенко (р. 1939), который до 1970 г.

принимал участие в проекте «Пионер». Позже В. И. Бутенко сам создал первую Сибирскую шахматную программу «Эврика»1.

С 1957 г. проблемами искусственного интеллекта занимался и Ге- М. М. Ботвинник Бутенко В. И. Первая Сибирская шахматная программа «Эврика» и ее особенности. – Новосибирск: Ротапринт ВЦ СО АН СССР, 1985.

оргий Максимович Адельсон-Вельский (р. 1922). В 1965 г. в Институте теоретической и экспериментальной физики АН СССР он возглавил работу по разработке компьютерной шахматной программы. Эта программа победила в 1965–1966 гг. в матче по телеграфной переписке программу Коток-Маккарти. (Алан Коток (Alan Kotok: 1941–2006) усовершенствовал программу Маккарти 1959 г., под чьим руководством он получил степени бакалавра и магистра)2. Позже на основе программы Г. М. Адельсона-Вельского будет создана программа «Каисса», выигравшая первый официальный шахматный чемпионат мира по шахматным программам в Стокгольме в 1974 г.

Вернемся снова в 1958 г. Именно в том году команда NSS разработала алгоритм уменьшения дерева поиска Альфа-бета отсечения, на основе которого построены были функции поиска всех сильных шахматных западных программ3.

К сожалению, система GPS не могла решать реальные задачи, что стало очевидно к концу 60-х гг. XX в. И тогда же в Стэнфордском университете группа ученых во главе с Эдвардом Фейгенбаумом (Edward Albert Feigenbaum: 1936) выдвинула совершенно другую стратегию решения проблемы ИИ: вместо поиска универсального решения для любой задачи ИИ они обратились к опыту человека. Для решения той или иной проблемы в той или иной области человек, прежде всего, обращается к опыту специалиста по данной проблематике и овладевает необходимыми разнообразными умениями и набором специфических правил.

Mc Carthy’s IBM 704 chess-playing program (1959).

В западной литературе до сих пор можно встретить утверждения, что победа была достигнута за счет «консультаций шестого чемпиона мира по шахматам Михаила М. Ботвинника».

Первой машиной, спроектированной только для игры в шахматы и игравшей на уровне мастера, была «Belle», законченная в 1983 г. Ее создатели Кен Томпсон (Kenneth Thompson: 1943) и Джо Кондон (Joseph Condon). Кен Томпсон является также одним из создателей операционной системы UNIX.

В 1971 г. Э. Фейгенбаум, защитивший степень Ph. D. под руководством Саймона в CIT1, публикует работу [117] об интерпретаторе для масс-спектрограммы DENDRAL, ставшей прототипом всех экспертных систем. Видимо поэтому в американской литературе Э. Фейгенбаума нередко называют «отцом» экспертных систем.

В 1976 г. появилась вариация системы DENDRAL для медицинских целей под названием MYCIN, позволившей ставить диагноз и выбирать лечение при заболеваниях, вызванных бактериальной инфекцией, и заболеваниях свертываемости крови. Автор Эдвард (Тэд) Шортлифф (Edward H. Schortliffe: 1947) ввел вместо вероятностей так называемые «коэффициенты уверенности», позволявшие прийти к правдоподобным заключениям на основе даже не вполне достоверных данных. Отметим, что как DENDRAL, так и MYCIN были логическими моделями.

В 1980 г. в Польше под руководством В. П. Одинца и Ю. А. Хрощицкого (Juliusz Antoni Chrocicki: 1943) была начата работа по созданию экспертной системы по атрибуции и датировке предметов живописи (AiD). Эта система должна была стать первой в мире сетевой моделью ЭС. Была создана база знаний [118], и начато создание базы данных. К сожалению, события 1980–1981 гг. не позволили закончить тогда работу [119]. В качестве метрики в модели AiD была выбрана «сила связи», определяемая по специальному правилу, предложенному экспертом.

Любопытно, что сделанный прогноз 10 параметров того, как должно было выглядеть одно из уничтоженных творений Рубенса (1577–1640) (триумфальная арка), в связи с найденными через три года после публикации статьи в «Artibus» [118] документами, описывающими это произведение, подтвердился полностью по параметрам и наполовину по одному параметру.

Carnegie Institute of Technology (теперь Carnegy Mellon University).

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

С другой стороны, появление в 1982 г. [138] машинной обучающей системы EURISKO (ее автор Дуг Ленат (Douglas Lenat:

1950), ученик профессора Э. Фейгенбаума) позволяет надеяться на неограниченные возможности применения роботов и их коммерческий успех.

Приведем краткие биографии некоторых из упомянутых выше и причастных к созданию экспертных систем ученых.

Норберт Винер родился в университетском городке штата Миссури Коламбия (Columbia) в 1894 г. в семье выходца из Российской Империи (город Белосток – теперь в Польше) Лео Винера. Отец, известный полиглот и историк, позже основал в Гарварде первую в Америке кафедру славянской культуры и стал первым в Америке профессором славянской лет Н. Винер получает степень бакалавра по математике. Затем год изучает – философию в Корнельском университете. Вновь вернувшись в Гарвард, Н.

Норберт Винер Л. Винер перевел на английский язык 24-томное собрание сочинений Льва Толстого.

по математике под руководством логика Карла Шмидта (Karl Schmidt: 1874–1961). В диссертации, в частности, Н. Винер вводит понятие упорядоченной пары1. В первой половине 1914 г.

Н. Винер путешествует по Европе, встречаясь с Б. Расселом и Г. Харди в Кембридже, а с Д. Гильбертом и Эд. Ландау – в Геттингене. Во время Первой мировой войны Н. Винер, будучи преподавателем в Гарварде, проходит путь от пацифиста до патриота, несколько раз пытаясь вступить в армию, но неудачно (из-за плохого зрения). В 1918 г. Освальд Веблен (Oswald Veblen: 1880– 1960)2 инициирует сотрудничество Н. Винера с Абердинской баллистической лабораторией, основанной в Мэриленде. Из-за антисемитизма, воцарившегося после Первой мировой войны в Гарварде (и в частности, из-за постоянных придирок со стороны влиятельнейшего математика Георга Биркгофа (Birkhoff George David: 1884–1944)3, Н. Винер перешел в MIT. В 1926 г. Н. Винер по стипендии Гуггенхайма едет в Геттинген и Кембридж, изучая броуновское движение и другие стохастические процессы (названные позже Винеровскими), интеграл Фурье, проблему Дирихле и гармонический анализ. Во время Второй мировой войны Н. Винер занимался усовершенствованием орудий противовоздушной обороны средствами оповещения, связи и т. д.

Все вместе это послужило почвой для создания кибернетики и когнитивной науки, способствовало исследованиям MIT в области нейропсихологии, биофизики нейронных систем и вовлечению в эти исследования Уоррена Маккалока и Уолтера Питтса.

Фактически речь идет о свойствах дуг графа, хотя термин «граф» не упоминается.

О. Веблен был, кстати, научным руководителем А. Черча.

В 1925–1926 гг. Г. Биркгоф был Президентом Американского Математического общества. Заметим, что А. Энштейн отмечал антисемитизм Георга Биркгофа.

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

Артуро Розенблат затем – в Берлине и Париже, где получил диплом врача. Вернувшись в психологии. В 1930 г., получив Гуггенхеймовскую стипендию, едет в Гарвард Автономном Национальном университете г. Мехико. В 1947–1949 гг. и ром. Умер А. Розенблат в 1970 г. в Мексике; в том же году вышла его знаменитая книга: «Память и ЭВМ: философия науки» [120].

В 1916 г. в г. Милуоки (штат Висконсин) в еврейской семье инженера, выходца из Германии родился Герман Саймон (1916– 2001). По своему влиянию на науку он очень похож на Леонида Витальевича Канторовича (1912–1986)1. Под влиянием младшего брата своей матери (экономиста) Г. Саймон изучает социальные науки в Чикагском университете, получает там степень бакалавра (1936) и Ph. D. (1943) по политическим наукам. Одновременно (с 1933 г.) Г. Саймон много внимания уделяет математике. Основным учителем Г. Саймона становится специалист по эконометрии и математической экономике Генри Шульц (Henry Schulz: 1893– 1938), эмигрант из Российской Империи, родившийся на территории современной Белоруссии, один из создателей эконометрии2.

С 1939 по 1942 г. Г. Саймон был директором исследовательской группы Университета Беркли (Калифорния), с 1942 по 1949 г.

– деканом факультета политических наук при Иллинойском технологическом институте. С 1949 г. (и до своей кончины в 2001 г.) Г. Саймон был связан с Карнеги Тех (переименованном позже в Карнеги-Меллон университет). Там он читал различные курсы, включая психологию и компьютерные науки. С 1949 по 1955 г.

Г. Саймон основное внимание уделяет математической экономике, при этом вместе с Дэвидом Хокинсом (David Hawkins: 1913– 2002)3 в 1949 г. получает необходимые и достаточные условия Нобелевский лауреат по экономике (1975) и выдающийся советский математик (см. также выше, начало § 6).

Г. Шульц трагически погиб в возрасте 45 лет вместе со своей семьей в автокатастрофе около Сан-Диего.

Д. Хокинс родился в Эл-Пасо. Получив степени бакалавра (1934) и магистра (1937) в Стенфордском университете по философии науки и Ph. D. (1940) в Калифорнийском университете (по теории вероятностей), он становится помощником Р. Оппенгеймера в Манхеттенском проекте (создания атомной бомбы). В 1938–1943 гг. был членом Компартии США. В 1949 г. сотрудничает с Г. Саймоном по изучению макроэкономики. Из-за начавшейся в 1949 г. в существования положительного вектора для решения системы с матрицей «вход-выход» Василия Васильевича Леонтьева (1905– 1999) [121], будущего Нобелевского лауреата по экономике (1973). Кстати, с другим Нобелевским лауреатом Т. Купмансом (Tjalling Koopmans: 1910–1985) Г. Саймон работает в 40-е гг. в Комиссии по аренде (Cowles Commission). О работе команды NSS говорилось выше. Со своим учеником Эдвардом Фейгенбаумом он развивает EPAM-теорию (Elementary Perceiver and Memorizer).

В 1975 г. Г. Саймон получает премию Тьюринга «за работу по ИИ», а в 1978 г. становится лауреатом Нобелевской премии1 по экономике за исследования в области принятия решения в процессах без экономической организации [122].

Как и Г. Саймон, Клод Элвуд Шеннон родился в 1916 г. (и умер в 2001 г.). Мать Клода была учительницей иностранных университет, став (в 1936 г.) бакалавром по электротехнике и математике.

США антикоммунистической истерии Д. Хокинсу было разрешено заниматься лишь подготовкой учителей математики для школ.

Правильнее эту премию называть «премией памяти А. Нобеля».

говый компьютер Веннивера Буша (Vannevar Buch: 1890–1974), позволявший решать дифференциальные уравнения до шестого порядка включительно. Его начальником был сам В. Буш, профессор, глава инженерной части MIT, ставший в 1938 г. Президентом Института Карнеги в Вашингтоне1. Он посоветовал К. Шеннону заняться генетикой (генетика входила в тематику исследований Института Карнеги), придав ей алгебраический аппарат.

Параллельно К. Шеннон занимается зависимостями в пропускных способностях систем связи с шумами и искажениями в этих системах. В 1940 г. К. Шеннон защищает диссертацию на степень Ph. D. «Алгебра в теоретической генетике». (Руководителем со стороны MIT был алгебраист, профессор Фрэнк Л. Хичкок (Frank Lauren Hitchcock: 1875–1957), эксперт в области математической химии и кватернионов.) Одновременно К. Шеннон защищает магистерскую диссертацию по электротехнике. Академический 1940/41 год К. Шеннон проводит на стажировке в Принстоне, где под руководством Германа Вейля (Hermann Weyl: 1885–1955) оформляет свои идеи относительно теории информации.

Когда США начали принимать участие во Второй мировой войне, К. Шеннон в Лабораториях Белла разрабатывает радиотехнические устройства по обнаружению самолетов (а позже и ракет) противника.

В 1948 г. выходит знаменитая статья К. Шеннона «Математическая теория связи» [127], ставшая одним из краеугольных камней в развитии информатики, или, как теперь модно говорить, инфоноосферы [141]. Разумеется, эта работа важна и для ИИ.

Задачи, связанные с передачей информации по «защищенному» каналу, привели еще в 1943 г. К. Шеннона к идее связи проС 1940 г. В. Буш становится советником Президента США по науке (в то время это был Франклин Делано Рузвельт (Franklin Delano Roosevelt: 1882– 1945)).

блем передачи информации с криптологией [128]. По этому поводу К. Шеннон вступает тогда же в контакт с А. Тьюрингом.

Напомним также, что еще в 1937 г. К. Шеннон представил работу (магистерская диссертация) о представлении булевских функций с помощью релейно-контактных схем. (Работа была опубликована год спустя [126]). Этот результат был получен в СССР раньше (1934–1935), но публикация Виктора Ивановича Шестакова (1907–1987) задержалась до 1941 г. [124; 125]. О работах К. Шеннона по программированию шахматной игры уже говорилось выше.

Эдвард Альберт Фейгенбаум – «отец» экспертных систем.

Родился в 1936 г. в г. Уихокен (Weehawken, штат Нью-Джерси).

Он окончил в Питтсбурге Технологический Институт Карнеги (ныне Carnegie Mellon University) и получил звание инженера (1956).

Диссертацию на степень Ph. D. Э. Фейгенбаум писал под руководством Г. Саймона (защитил в 1960 г.), а к концу 60-х гг. им и была создана система DENDRAL [130]. Позже Э. Фейгенбаум стал создателем энциклопедии «Карманная книга Искусственного Интеллекта». В течение многих лет профессор Э. Фейгенбаум был деканом факультета компьютерных наук и директором Вычислительного центра Стэнфордского университета. Он был также Президентом Американской Ассоциации Искусственного Интеллекта. В 1994–1997 гг. был главным научным специалистом Военно-воздушных сил США [102].

В заключение этого параграфа остановимся на двух принципиальных моментах – 1) машине вывода и 2) автоматизированном процессе извлечения знаний.

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

Они разнятся цепочкой рассуждений: либо «прямой» – когда идут от данных к гипотезам, либо «обратной» – когда ищут данные для доказательства или опровержения гипотезы. В 1983 г.

Крис Нейлор (Chris Naylor) в работе «Как построить собственную экспертную систему» [131] попытался соединить оба подхода.

Что касается автоматизированного процесса извлечения знаний, то здесь еще остается широкое поле деятельности.

В работе 1984 г. [132] Ричард Форсайт (Richard Forsyth) попробовал применить дарвиновскую систему естественного отбора для создания и усиления правил классификации (кратко BEAGLE)1, т. е. создал биологический эволюционный алгоритм, порождающий логические выражения.

В этой связи напомним, что Сергей Юрьевич Маслов дал метод построения машинных алгоритмов поиска логического вывода (для любых!) логических исчислений (а не только предикатов) еще в 1967 г. (ДАН СССР, т. 172, № 1), а подробно – год спустя [133].

Biological Evolutionary Algorithm Generating Logical Expressions.

Заключение Читатель, «добравшийся» до заключения, может резонно спросить: почему автор, говоря об искусственном интеллекте, не коснулся пяти изобретений Семена Николаевича Корсакова (1787–1853) по ИИ в России. Не вступая в полемику, приведу фрагмент решения Академии Наук от 24 октября 1832 г., подписанного академиками Остроградским, Купфером, Брандтом и профессором Парретом1: «...Показав, таким образом, что это новое изобретение отнюдь не применимо к наукам, члены Комиссии все же отдают должное остроумию, сообразительности и изобретательности автора…»

Можно сделать вывод, что С. Н. Корсаков фактически своими изобретениями констатировал потребность в базе знаний, а члены Комиссии резонно указали, что для каждой науки (а значит, и задачи, решаемой этой наукой), нужен свой эксперт (см.

[22]).

Добавим также, что обширная литература по проблеме искусственного интеллекта (до 1987 г.) содержится в книге Ж.-Л.

Лорьера [89].

Остроградский Михаил Васильевич (1801–1867), академик-математик; Купфер Адольф Яковлевич (1799–1865), академик по минералогии; Брандт Федор Федорович (1802–1879), экстраординарный академик зоологии; Паррет Иван Егорович (1791–1841), врач и естествоиспытатель, заведующий кафедрой физики Дерптского университета (по состоянию на 24.10.1832 г.).

Упражнения 1. Дана таблица по 100 умершим людям:

Пользуясь формулами Байеса, найти апостериорные шансы курящего мужчины прожить долгую жизнь (> 75 лет), если 2. Дайте определение нечеткого множества и приведите примеры.

3. Дайте определение многозначной1 логики (n := 3, 4, 5) и приведите примеры.

4. Напомним, что коэффициент уверенности (КУ) = разности между двумя мерами:

КУ[h:e] = MD[h:e] – MHD[h:e], где КУ[h:e] – уверенность в гипотезе h с учетом свидетельств е;

MD[h:e] – мера доверия h при заданном е;

MHD[h:e] – мера недоверия гипотезе h при свидетельствах е.

Перед заключением к главе III отметим, что обширная КУ [h:e] может изменяться от (– 1) = абсолютная ложь, до (+ 1) = абсолютная истина, а MD [h:e] [0, 1], MHD [h:e] [0, 1]. Приведите примеры коэффициентов уверенности, включая крайние значения.

Напомним, что творцом многозначной логики был польский логик Ян Лукашевич (ukazewicz Jan: 1878–1956).

Список литературы Основной [1] The Oxford English Dictionary / edited by John Simpson and Edmund Weiner. – Second Edition. – Oxford : Oxford University Press, 1989. – Vol’s 1–20.

[2] Большой Англо-Русский словарь / под рук. И. Р. Гaльперина и Э. М. Медниковой : в 2-х т. – М. : Русский язык, 1988.

[3] Одинец В. П. Зарисовки по истории математики. – Сыктывкар : Изд-во КГПИ, 2005. – 232 с.

[4] Депман И. Я. История арифметики. – М. : Гос. уч.-пед. издво, 1959. – 432 с.

[5] Price Derek J. de Solla. An Ancient Greek computer // Scientific American. – June 1959. – P. 60–67.

[6] Pastore G. Atikythera EI Regoli Calcolatori. – Rome, 2006. – 73 p.

[7] Апокин И. А., Майстров Л. Е. Развитие вычислительных машин. – М. : Наука, 1974. – 309 с.

[8] Апокин И. А., Майстров Л. Е. История вычислительной техники. – М. : Наука, 1990. – 263 с.

[9] Ланина Э. П. История развития вычислительной техники. – Иркутск : Изд-во ИрГТУ, 2001. – 167 с.

[10] Исаков В. Н. Элементы численных методов. – М. : Академия, 2003. – 189 с.

[11] Таненбаум Э. Архитектура компьютера. – 5-е изд. – СПб. :

Питер, 2010. – 843 с.

[12] Апокин И. А., Майстров Л. Е., Эдлин И. С. Чарльз Бэббидж.

– М. : Наука, 1981.

[13] Фихтенгольц Г. М. Курс дифференциального и интегрального исчисления. – М. : Физматлит, 1962. – Т. 2. – 807 с.

[14] Большая Советская энциклопедия / гл. ред. Б. А. Введенский. – М. : Большая Советская Энциклопедия, 1957. – Т. 48. – 701 с.

[15] Старцев П. А. Очерки истории астрономии в Китае. – М. :

Госизд. физ-мат. лит-ры, 1961. – 156 с.

[16] Jackson A. S. Analog Computation. – London & NewYork : Mc Graw-Hill, 1960.

[17] Marguin J. Histoire des instruments et machines calculer – Trois sicles de mcanique pensante, 1642–1942. – Paris : Hermann, 1994.

[18] Залгаллер В. А. Выпуклые многогранники с правильными гранями / Записки научных семинаров ЛОМИ. – Ленинград : Наука, 1967. – Т. 2. – 220 с.

[19] Mollenhoff C. R. Atanasoff: Forgotten Father of the Computer. – Ames (Iowa) : Iowa State University Press, 1988.

[20] Дашевский Л. Н., Шкабара Е. А. Как это начиналось. – М. :

Знание, 1981. – 64 с.

[21] Detlefsen M. Polnische Rechenmaschinenerfinder des 19 Jahrhunderts. Ein wenigbekanntes Kapitel polnischer Wissenschaftsgeschichte // Wissenschaft und Fortschritt. – T. 26. – № 2 (1976). – S. 86–91.

[22] Кольман Э., Радовский М. И. Из истории вычислительных устройств (по материалам Архива АН СССР) // Историко-математические исследования. – М. : Наука, 1961. – Т. 14. – С. 550–586.

[23] Одинец В. П. К 200-летию со дня рождения создателей вычислительных машин, представленных к Демидовской премии, Х. З.

Слонимского и Г. Куммера // Вестник Сыктывкарского университета.

– Сер. 1. – Вып. 13 (2011). – С. 137–144.

[24] Ананьева О. А. Счислитель Куммера // Памятники науки и техники в музеях России. – М. : Наука, 2005. – Вып. 4. – С. 14–17.

[25] Малиновский Б. Н. История вычислительной техники в лицах. – К. : КИТ, ПТОО «А.С.К», 1995. – 384 с.

[26] Владимиров В. С. Математика и создание первых образцов атомного оружия : интервью от 17 октября 2008 г. – М. : Агентство PRoAtom. – 14 c.

[27] Пройдаков Э., Ливеровский А. Дальше так нельзя : интервью с академиком В. С. Бурцевым // PC WEEK. – 2003. – 14 мая.

[28] Одинец В. П. О некоторых стереотипах при изложении истории информатики // Некоторые актуальные проблемы современной математики и математического образования. Герценовские чтения – 2011. – СПб. : БАН, 2011. – T. LXIV. – С. 193–198.

[29] Очерки истории информатики в России // Сб. научн. трудов.

– Новосибирск : Научно-изд. Центр ОИГГ РАН, 1998.

[30] Post E. L. Finite combinatore processes-formulation 1 // The Jour. of Symbolic Logic. – T. 1. – № 3 (1936). – Р. 103–105. (В русском переводе: Эмиль Л. Пост. Финитные комбинаторные процессы, формулировка 1. – в книге [31, с. 83–88]) [31] Успенский В. А. Машина Поста. – М. : Знание, 1988. – 96 с.

[32] Chups A. An unsolvable problem of elementary number theory // Amer. J. Math. – 1936. – V. 58. – № 2. – Р. 345–363.

[33] Gdel K. ber formal unentscheidbare Stze der Principia Mathematica und vervandter Systeme I // Monatsheft Math. Phys. – Bd.

38, H. 1 (1931). – S. 173–198.

[34] Turing A. On computable numbers, with an application to the Entscheidungsproblem // Proc. London Math. Soc. – Ser. 2. – V. 42. – № 3–4 (1936). – Р. 230–265.

[35] Turing A. A correction // Proc. London Math. Soc. – Ser. 2. – V.

43. – № 7 (1937). – Р. 544–546.

[36] Исаков В. Н., Исакова В. В. Алгоритмизация и программирование: методические аспекты // Информатика и образование. – № (1995). – С. 44–48.

[37] Драгалин А. Г. Математический интуиционизм. Введение в теорию доказательств. – М. : Наука, 1979.

[38] Von Neumann J. Zur Theorie der Gesellschaftsspiele // Math.

Ann. – 100 (1928). – S. 295–320. (В русском переводе: Дж. фон Нейман. К теории стратегических игр / Матричные игры. – М. : Физматлит, 1961.) [39] Banach S., Tarski A. Sur la decomposition des ensembles de points en parties respectivement congruentes // Fundamenta Mathematicae.

– № 6 (1924). – S. 244–277.

[40] Ященко И. В. Парадоксы теории множеств // Математическое просвещение. – 2002. – Вып. 20. – 40 с.

[41] Hausdorff F. Bemerkungen ber den Inhalt von Punktmengen // Mathem. Annalen. – Vol. 75 (1914). – S. 428–434.

[42] von Neumann J. The Mathematical Foundations of Quantum Mechanics. – Princeton : Princeton Univ. Press, 1932.

[43] von Neumann J., Morgenstern O. Theory of Games and Economic Behavior. – Princeton : Princeton Univ. Press, 1944.

[44] Марков А. А. Теория алгорифмов // Труды МИАН СССР. – Т.

38 (1951). – С. 176–179. (См. также: Марков А. А. Избранные труды. – М. : Изд-во МЦНМО, 2003. – Т. II. – С. 32–43).

[45] Одинец В. П., Поспелов М. В. Введение в теорию алгоритмов : учебное пособие. – Сыктывкар : Изд-во КГПИ, 2006. – 140 с.

[46] Марков А. А. Теория алгорифмов // Труды МИАН СССР. – Т.

42 (1954). – С. 3–375.

[47] Вейль Г. О философии математики / пер. с нем. А. П. Юшкевича. – М.; Л. : ГТТИ, 1934. – 128 с..

[48] Гейтинг А. Интуиционизм. – М. : Мир, 1965. (Пер. с англ.:

Heyting A. Intuitionism. An Introduction. – Amsterdam : North-Holland Publishing Co., 1965.) [49] Ловягин Ю. Н. Исчисление бесконечно малых Г. В. Лейбница в современном изложении, или Введение в нестандартный анализ А.

Робинсона. – Сыктывкар : Изд-во Сыкт. лесн. ин-та, 2001. – 163 с.

[50] Davis M. Emil L. Post: His Life and Work // Solvability, Provability, Definability. The Collected Works of Emil Post (Ed. Davis M.) – Birkhuser, 1994. – P. xi–xxviii.

[51] Dawson J. Logical dilemmas: The life and work of Kurt Gdel. – Wellesley MA : AK Peters, 1997.

[52] Britton J. L., Ince D. C. and Sanuders P. T. (eds). Collected works of A. M. Turing. – Amsterdam : North-Holland, 1992. – Vol. 1–3.

[53] Turing S. Alan M. Turing. – Cambridge : Cambridge Univ. Press, 1959.

[54] Aspray W. John von Neumann and the Origins of Modern Computing. – Cambridge (Mass.) : MIT Press, 1990.

[55] Нагорный Н. М. Андрей Андреевич Марков и его конструктивное направление в математике // А. А. Марков. Избранные труды / сост. Н. М. Нагорный. – М. : Изд-во МЦНМО, 2002. – Т. 1. – С. V– XLVIII.

[56] Kleene S. K. General recursive function of natural numbers // Math. Ann. – Bd. 2. 112 (1936). – P. 727–742.

[57] Клини С. Введение в метаматематику. – М. : ИЛ, 1957.

(Пер. с англ.: Kleene S. K. Introduction to Metamathematics.– Amsterdam : D. Van Nostrand, 1952).

[58] O’Connor J. J., Robertson E. F. Stephen Cole Kleene. MacTutor History of Mathematics archive. – St. Andrews (Scottland) : University of St. Andrews, 1997.

[59] Ackermann W. Philosophische Bemerkungen zur mathematischen Logik und zur mathematischen Grundlagenforschung. – Ratio, Band 1, 1957.

[60] Pter R. Rekursive Funktionen in der Computer Theorie. – Budapest, 1976.

[61] Володин И. А., Кузнецов В. Е., Фоменко А. Т. О проблеме алгоритмического распознавания стандартной трехмерной сферы // УМН. – Т. 29. – № 5 (1974). – С. 71–168.

[62] Марков А. А. О конструктивной математике // Труды МИАН СССР. – Т. 67 (1962). – С. 8–14. (или Марков А. А. Избранные труды. – М. : Изд-во МЦНМО, 2008. – Т. 2. – С. 194–200).

[63] Цейтин Г. С. Алгорифмические операторы в конструктивных метрических пространствах // Труды МИАН СССР. – Т. (1962). – С. 295–361.

[64] Новиков П. С. Об алгоритмической неразрешимости проблемы тождества // Доклады АН СССР. – Т. 85. – № 4 (1952). – С. 709–712.

[65] Новиков П. С., Адян С. И. О бесконечных периодических группах. I, II, III // Изв. АН СССР. – Сер. матем. – 32:1 (1968). – С. 212–244; 32:2 (1968). – С. 251–524; 32:3 (1968). – С. 709–731.

[66] Маслов С. Ю. Представление перечислимых множеств локальными исчислениями // Труды МИАН СССР. – 93 (1967). – С. 43–49.

[67] Tarski A. A decision method for elementary algebra and geometry. – Santa Monika (CA) : RAND Corp., 1948.

[68] Davis M. Arithmetical problems and recursively enumerable predicates // Journal of Symbolic Logic. – 18 №1 (1953). – Р. 33–41.

[69] Davis M., Putnam H., Robinson J. The decision problem for exponential Diophantine equations // Annals of Mathem. – Vol. 74. – № (1961). – Р. 425–436. (Русск. перев.: сб. «Математика». – Т. 8. – № (1964). – С. 69–79).

[70] Матиясевич Ю. В. Диофантовость перечислимых множеств // Доклады АН СССР. – Т. 191. – № 2. – 1970. – С. 279–282.

[71] Матиясевич Ю. В. Десятая проблема Гильберта. – М. : Наука: Физматлит, 1993. – 223 с.

[72] de Gaynesford M. Hilary Putnam. – Kingston (Ontario) : Mc Gill – Queens Univ. Press., 2006.

[73] Feferman S. Julia Bowman Robinson, 1919–1985. – Biographical Memoirs, 63 – Washington, DC : National Academy of Sciences, 1994. – P. 425–479.

[74] Мальцев А. И. Алгебраические системы. – М. : Наука, 1970.

– 391 с.

[75] Одинец В. П., Шлензак В. А. Избранные главы теории графов / пер. с польск. В. П. Одинца при участии М. В. Поспелова. – М.;

Ижевск : Регулярная и хаотическая динамика, 2009. – 504 с.

[76] Курош А. Г. Анатолий Иванович Мальцев (к пятидесятилетию со дня рождения) // УМН. – Т. 14. – № 6 (1959). – С. 203–211.

[77] Mints G. An exception from a foreword to the English edition of the book: «Voprosy Kibernetiki». – No 131. (1987) // Amer. Math. Soc.

Transl. – Ser. 2. – Vol. 178. – Providence (RI) : AMS, 1997.

[78] Вершик А. М. Потайной дайджест времен застоя // Звезда.

1991. – № 1. – С. 165–170.

[79] Морозова Е. А., Петраков И. С. Международные математические олимпиады. – М. : Просвещение, 1971. – 254 с.

[80] Tarski A. Sur les ensembles dfinissables de number reels. I // Fundamenta Mathematical. – T. 17 (1931). – A. 210–239.

[81] Tarski A. Der Wahrheitsbegriff in den formalisierten Sprachen // Studia Philosophia. – 1 (1936). – S. 261–405.

[82] Givant S. Bibliography of Alfred Tarski // Journal of Symbolic Logic. – 51 (1986). – S. 913–941.

[83] Хопкрофт Дж., Мотвани Р., Ульман Д. Введение в теорию автоматов. – М. : Вильямс, 2002. – 528 с. (Пер. с англ.: Introdaction to Automate Theory, Languages and Computation.) [84] Николенко С. P = SN ? // Компьютерра. – 2006. – № 6. – февраля.

[85] Dennis Sh., Lazer C. Out of Their Minds: The Lives and Discoveries of 15 Great Computer Scientists. – Berlin–New York : Springer, 1995.

[86] Hilts P. J. Scientific Temperaments: Three Lives in Contemporary Science. Legenthy profiles of John Mc Carthy, physicist Robert R. Wilson and geneticist Mark Ptashne. – Simon and Schuster, 1982.

[87] Mc Carthy J., Hayes P. J. Some philosophical problem from the standpoint of artifical intelligence // Machine Intelligence. – 4 (1969). – Edinburg : Edinburg University Press. – P. 463 – 502.

[88] Griffiths P., Spencer D., Whitehead G. Solomon Lefschetz. A Biographical Memoir. – Washigton D.C. : National Academy of Scieces, 1992. – P. 271–313.

[89] Лорьер Ж.-Л. Системы искусственного интеллекта / пер. с франц. – М. : Мир, 1991. – 568 с.

[90] Peano G. Arithmetices principia nova methoda exposita. – Turin :

Bocca, 1889.

[91] Grassman H. Lehrbuch der Arithmetik. – Berlin : Enslin, 1861.

[92] Tarski A. The concept of truth in formal languages // Stud.

Philos. (Warsaw). – 1 (1935). – P. 261–405.

[93] Church A. A note on the Entscheiedigungsproblem // J. Symb.

Logic. – № 1 (1936). – Р. 40–41.

[94] Маслов С. Ю. Обратный метод установления выводимости в классическом исчислении предикатов // Доклады АН СССР. – Т. 159.

– № 1 (1964). – С. 17–20.

[95] Братко И. Алгоритмы искусственного интеллекта на языке PROLOG. – М. : Вильямс, 2004. – 640 с.

[96] Horn A. On sentences which are true of direct unions of algebras // Journal of Symbolic Logic. – 16 (1951). – P. 14–21.

[97] Уинстон П. Искусственный интеллект. Artifical Intelligence.

– М. : Мир, 1980. – 520 с.

[98] Смолин Д. В. Введение в искусственный интеллект : конспект лекций. – М. : Физматлит, 2004. – 208 с.

[99] Minskiy M., Papert S. Perceptrons. – Cambridge, MA : MIT Press, 1969.

[100] Minskiy M., Papert S. Artifical Intelligence. – Eugen: Univ. of Oregon Press, 1972.

[101] Розенблатт Ф. Принципы нейродинамики. Перцептроны и теория механизмов мозга / пер. с англ. – М. : Мир, 1965. – 480 с.

[102] Henderson H. A to Z of Computer Scientists. – New York :

Facts on File, 2003. – 208 p.

[103] Гаврилова Т. А., Хорошевский В. Ф. Базы знаний интеллектуальных систем : учебник. – СПб. : Питер, 2000.

[104] Экспертные системы. Принципы работы и примеры / под ред. Р. Форсайта; пер. с англ. – М. : Радио и связь, 1987. – 223 с.

[105] Wiener N., Rosenblueth A., Bigelow J. Behavior, purpose and teleology // Philos. Sci. – 10 (1943). – P. 18–24.

[106] Wiener N. Cybernetics, or Control and Communication in the Animal and the Machine. (Actuelits Sci. Ind. No 1053). – Paris : Hermann and Cie, 1948. (Переизд.: Cambridge (Mass) : The MIT Press; New York:

Wiley).

[107] Gentzen G. Die Widerspruchenfreiheit der reinen Zahlentheorie // Mathem. Annalen. – Bd. 12 (1936). – S. 493–565.

[108] Menzler-Trott E. Gentzens Problem: Mathematische Logik in nationalsozialistischen Deutschland. – Berlin : Birkhauser Verlag, 2001.

[109] Urquhart A. Emil Post // Handbook of the History of Logic. – Vol. 5. (Logic from Russell to Church.) – P. 429–478.

[110] Post E. L. Introduction to a general theory of elementary propositions // American Journal of Math. – 43 (1921). – P. 163–185.

[111] Горлицкая С. И., Кузнецова И. Н., Литвин Ф. Д. Образовательные среды LOGO и LEGO // Компьютерные инструменты в образовании. – СПб. : Изд-во ЦПО «Информатизация образования». – 1999. – № 5. – С. 65–70.

[112] Rosenblatt F. The PERCEPTRON: a Percejving and Recognizing Automaten. – New York : Cornell Aeronautical Lab, 1957.

[113] Mc Culloch W., Pitts W. A logical calculus of ideas imminent in nervous activity // Bull. of Mathematical Biophysics. – 5 (1943). – P. 115–133.

[114] Shannon C. Programming a Computer for Playng Chess // Philosophical Magazin. – Ser. 7. – Vol. 41. – № 314 (1950).

[115] Ботвинник М. М. Алгоритм игры в шахматы. – М. : Наука, 1968.

[116] Bernstein A., Roberts M. Computer vs Chess-Player // Scientific American. – Vol. 198 (1958). – P. 96–105.

[117] Feigenbaum E. On generality and problem solving. – Machine Intelligence. – 1971. – 6.

[118] Chrocicki J. A., Odinec V. P. (= Odyniec W. P.). On Direct Graph Models of Influences in Art Theory // Artibus et Historiаe. – Venezia – Wien : IRSA-LICOSA. – 1980. – № 3. – Р. 113–130.

[119] Odyniec W. P. The first expert system for painting ascription and dating: to the history of creation // L’Europe moderne-nouveau monde, nouvelle civilization. – Warszawa : Arx Regia, 2009. – P. 216–217.

[120] Rosenblueth A. Mind and Brain: A Philosophy of Science. – Cambridge, MA : MIT Press, 1970.

[121] Hawkins D., Simon H. A. Some Conditions of Macroeconomic Stability // Econometrica. – 1949. – XVII. – P. 245–248.

[122] Simon H. A. Models of My Life. – New York : Basic Books, Sloan Foundation Series, 1991. – 415 p.

[123] Шеннон К. Работы по теории информации и кибернетике.

– М. : Изд-во иностр. лит., 1963. – 830 с.

[124] Шестаков В. И. Алгебра двухполюсных схем, построенных исключительно из двухполюсников (алгебра А-схем) // Автоматика и телемеханика. – 1941. – № 2. – С. 15–24.

[125] Шестаков В. И. Алгебра двухполюсных схем, построенных исключительно из двухполюсников (алгебра А-схем) // Журнал технической физики. – 1941. – Т. 11. – № 6. – С. 532–549.

[126] Shannon C. E. A Symbolic Analysis of Relay and Switching Circuits (MSThesis) // Massachusetts Institute of Technology, Dept of Electrical Engineering (Aug. 10, 1937). Published in Transaction of the Amer. Inst. of Electrical Engineers. – Vol. 57 (1938). – P. 713–723.

[127] Shannon C. E. A Mathematical Theory of Communication // Bell System Technical Journal. – Vol. 27 (1948). – P. 379–423; 623–656.

[128] Shannon C. E. Communication Theory of Secrecy Systems – Bell System Technical Journal. – 1949. – Vol. 28. – P. 657–724.

[129] Bowker R. R. Papert Seymour A. // American Men and Women of Science. – 1998/99. – P. 1056.

[130] Feigenbaum E. A., Buchanan B. G. and Lederberg J. On generality and problem solving: a case using the DENDRAL program in Machine Intelligence, 6. – Edinburg : Edinburg University Press, 1971. – P. 165–190.

[131] Naylor C. Build Your Own Expert System. – Chichester : Sigma Technical Press (John Wiley), 1983.

[132] Forsyth R. BEAGLE: a Darwinian approach to pattern recognition // Kybernetes. – 10. – Nr. 3 (1981). – P. 159–166.

[133] Маслов С. Ю. Обратный метод установления выводимости для логических исчислений // Труды МИАН СССР. – Т. 98 (1968).

– С. 26–87.

[134] Кнут Д. Э. Искусство программирования. – М. : Вильямс, 2000. – Т. 1. Основные алгоритмы. – 692 с.

[135] Кнут Д. Э. Искусство программирования. – М. : Вильямс, 2003. – Т. 2. Получисленные алгоритмы.

[136] Кнут Д. Э. Искусство программирования. – М. : Вильямс, 2007. – Т. 3. Сортировка и поиск. – 824 с.

[137] Кнут Д. Э. Искусство программирования. – М. : Вильямс, 2008. – Т. 4. Вып. 2. Генерация всех кортежей и перестановок. – 570 c.

[138] Lenat D. Eurisko: a program that learns new heuristics and domain concepts // Artificial Intelligence. – 21 (1983). – P. 61–98.

[139] Романовский И. В. Дискретный анализ. – 3-е изд. – СПб. :

Невский Диалект : БХВ–Петербург, 2004. – 320 с.

[140] Старобогатов Р. О., Румянцева Е. И. Квантовые компьютеры // Информационные системы и технологии. – № 1 (2). – СПб. :

Парк Ком, 2010. – С. 110–115.

[141] Юсупов Р. М. Информатизация как мощный фактор интеграции науки и образования // Мировые модели взаимодействия науки и высшего образования / Материалы Межд. научн. конф. 1– июля 1996 г. – СПб. : Изд-во СПбГТУ, 1997. – С. 91–98.

[142] Малиновский Б. Н. Цифровые управляющие машины и автоматизация производства. – М. : Машгиз, 1963. – 288 с.

[143] Одинец В. П. Возвращаясь к Куммеру // Вестник Сыктывкарского ун-та. – 2012. – Сер. 1. – Вып. 15. – С. 147–149.

ЧАСТЬ II

Глава IV. История языков программирования § 15. Алгоритмические языки. Первые два поколения языков программирования Начнем этот параграф с утверждения, что естественные языки, включая русский и английский, неоднозначны и противоречивы (см. [5]). Для доказательства достаточно напомнить, так называемый, парадокс французского математика Жюля Ришара2 в форме Д. Берри3, содержащийся в фразе: «[Указать] наименьшее В главе IV не рассматриваются языки:

Бейсик (от англ. BASIC – Beginner’s All-purpose Symbolic Instruction Code) – высокоуровневый язык, созданный в 1963 г. Томасом Курцем для обучения начинающих (Tomas Eugene Kurtz: 1928) и Джоном Кемени (John Georg Kemeny: 1926–1992) (см. [2, гл. II]);

PL/1 – первоначально (1964) названный сотрудниками фирмы IBM и ассоциацией пользователей машин фирмы IBM, как NPL (New Programming Laguage), но учитывая, что в Великобритании эта аббревиатура означает National Physics Laboratory, переименованный на PL/1 (см. [2, гл. IV]);

LOGO – язык высокого уровня, созданный в 1967 г. Сеймуром Пейпертом и Идит Харель Капертон (Idit Harel Caperton: 1958) для обучения детей дошкольного и младшего школьного возраста (см. [3]).

Не будет рассматриваться история языков, которые находятся «между» компилируемыми и интерпретируемыми, а также история ряда классов языков программирования (стековых, аспектно-ориентированных, прототипных, скриптовых, эзотерических и учебных). В то же время в Части III будет описана история ряда языков, в частности РЕФАЛ (его создателем является советский и американский физик и кибернетик Валентин Фёдорович Турчин (1931–2010) (см. [4]), родившийся в Подольске и умерший в Нью-Йорке, выпускник физического факультета МГУ им. М. В. Ломоносова (1953), доктор физ.-мат. наук (подробнее см. § 27)). В конце Главы IX будет дана подробная история языка PostScript.

Ж. Ришар (Jules Antuan Richard: 1862–1956) описал свой парадокс в 1905 г. в работе: Les principes des mathmatiques et le problem des ensembles // Revue gnrale des sciences pures et appliqus. – Vol. 16. – P. 541–543.

Д. Берри (G. G. Berry: 1867–1928) – библиотекарь Оксфордского университета.

из натуральных чисел, которое нельзя назвать на русском языке с помощью менее 20 слов»1, приведенной в переводе на русский язык в 1957 г. классической работы «Введение в метаматематику» Стивена Клини (1909–1994) [6, с. 41]. Тем не менее естественные языки содержат подъязыки, фразы которых однозначны и не зависят ни от каких внешних для данного языка условий. Например, такими подъязыками (их называют формальными) служат системы счисления.

Для описания формального языка нужен другой язык. Его называют языком-объектом. Язык, применяемый для описания языка-объекта, называют метаязыком. Напомним, структуру предложений (т. е. завершенных конструкций естественного Эта фраза, задающая объект на русском языке, содержит 16 слов (т. е.

меньше 20). Впервые же фраза: «the smallest possible integer not definable by a given number of words» была описана Бертраном Расселом (Bertrand Arthur Russell: 1872–1970), и именно он приписал ее Д. Берри [5].

Современные теории, посвященные проблемам синтаксиса формальных языков, восходят к двум классическим работам Ноама Хомского (Noam Chomsky: 1928): «Syntactic Structures», 1957 г. [7], и «Aspects of the Theory of Syntax», 1965 г. [8], в которых изучаются иерархия формальных языков и порождающие грамматики (см. также: «Метаязык науки»: материалы Международной научной конференции; гл. ред. С. В. Лесников. Сыктывкар: СыктГУ, 2012. 900 с.).

Второй способ построения метасинтаксического языка, основанный на двухуровневой грамматике, был предложен голландским математиком А. ван предложенный американским информатиком Джоном Бэкусом (John Warner Backus: 1924–2007), названный нормальной нотацией Бэкуса и восходящий к работе индийского ученого VI в.

Панини (Pini) по созданию грамматики санскрита.

Множество конструкций языкаобъекта, находящихся в правых частях формул (Бекуса), называют базой языка-объекта, а сами эти конструкции – Джон Кемени морфемами данного языка.

Напомним также, что если t – некоторый алгоритм (подробнее см. [9], гл. II) над языком L, то все его результаты принадлежат некоторому языку. При этом существует такой язык, содержащий результаты алгоритма t, который, кроме этих результатов, не содержит никаких других конструкций, т. е. является t-алгоритмически минимальным подъязыком в. Язык будет формальным языком. Примером такого языка является, в частности, совокупность всевозможных программ, которые мыслимы для данной вычислительной машины.

Вийнгаарденом (Adriaan van Wijngaarden: 1916–1987) при работе над созданием языков ALGOL и ALGOL 68. Он получил название W-грамматики.

При этом построении метасинтаксический язык состоит из конечного числа предложений, называемых формулами (Бэкуса). В этих формулах используются два универсальных метасимвола: и, при этом первый символ читают: по определению есть, а второй – или.

Напомним, что, если алгоритм задан на языке L1 над языком L2, то язык L называют алгоритмическим языком, а L2 – языком исходных данных [9].

Как известно (cм., например, [9, с. 134]), языками программирования называют знаковые системы, используемые для описания процессов решения задач на ЭВМ. Традиционно языки программирования делятся на три группы: 1) формальные алгоритмические языки; 2) формальные неалгоритмические языки1 и 3) неформализованные (полностью) знаковые системы, применяемые при программировании (например, блок-схемы).

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

В 1842 г. Ада Лавлейс (Ada Lovelace (Byron): 1815–1852), работая над переводом на английский (Luigi Menabrea: 1809–1896) об аналитической машине Чарльза Бэббиджа передней панели аналитической машины ключевых переключателей2.

К этой группе относятся языки, в которых дается метод решения задачи без точного указания последовательности действий, которые должны при этом выполняться. Примером является язык параметрически заданных схем. Этот язык является частным случаем языка логических схем (ЯЛС), созданных в 50-е гг. XX в. в СССР для описания дискретных процессов различной природы. В 1953 г. Алексей Андреевич Ляпунов (1911–1973) ввел понятия оператора схемы счета и схемы программы (публикация 1956 г. [10]). Через 2 года Ю. И. Янов, при изучении схем алгоритмов, формализовал понятие ЯЛС (публикация 1958 г. [11]). Семантику этого языка получил в 1959 г. Николай Андреевич Криницкий (подробнее см. [12]). В 1962 г. завершение изучения ЯЛС было дано в работе А. А. Ляпунова [13].

Подробнее о задачах, решавшихся на машине Ч. Бэббиджа с помощью программ А. Лавлейс, см.: [1, c. 22].

В аналитической машине считывание переменных и операций осуществлялось с помощью перфокарт [1, c. 21–22]. Через 100 лет перфокарты были дополнены перфолентами, и появился машинный язык, с помощью которого можно было задавать команды, обращаясь к ячейкам памяти. Напомним, что машинный язык представляет собой свод правил кодирования действий, определенных в числовом виде (в основном арифметических действий)1.

Основной морфемой машинного алгоритмического языка является:

Кроме того, бывают морфемы, и другие.

Из этих морфем, которые будут словами в двухбуквенном алфавите, при их расположении в определенном порядке образуется слово, называемое.

Машинный язык или машинный код традиционно относят к первому поколению языков программирования.

Составление программы на машинном языке было сложной комбинаторной задачей, так как одновременно с составлением команд программист распределял и память. Эти трудности достаточно наглядно проиллюстрированы на примере программирования на вычислительной машине «ALWAC III-E» в книге М. Клейна, Г. Моргана и М. Аронсона, вышедшей в США в 1958 г. (русский перевод 1960 г.) [14].

Кодами называются формальные языки, для которых метаязык, являющийся тоже формальным, состоит из двух подъязыков, первый из которых состоит из множества осмысленных предложений той области, которая нас интересует, а второй содержит описания двух правил, называемых, соответственно, правилом кодирования и правилом декодирования [9].

Примерно в это же время удалось разделить распределение памяти и составление команд за счет введения символических адресов.

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

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

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

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

Каждое семейство процессоров имеет свою систему команд и соответствующий ей язык ассемблера. При этом язык ассемблера В настоящее время автокодом называют язык программирования, предложения которого по своей структуре, как правило, подобны командам и обрабатываемым данным конкретного машинного языка.

позволяет писать самый эффективный (т. е. самый быстрый и компактный) код, который возможен для данного процессора [15–17].

В 1954 г. в отделе ИМ АН СССР, которым руководил А. А. Ляпунов, на основе разработанного им операторного метода в программировании, была создана программа ПП-1, являющаяся первым в мире транслятором с некоторого универсального алгоритмиче- А. А. Ляпунов ского языка на язык машины.

В настоящее время наиболее распространенными синтаксисами языков ассемблера являются Intel-синтаксис и AT&T-синтаксис.

На языке ассемблера до сих пор производится создание операционных систем, драйверов, антивирусов и других защитных программ (подробнее см. [16; 17]). Неслучайно поэтому язык ассемблера относят ко второму поколению языков программирования1.

Джон Бэкус родился в Филадельфии (США) в 1924 г. Первоначально, по окончании средней школы в Пенсильвании, Джон собирался изучать химию в университете в Вирджинии. Однако, вскоре после поступления, он был призван в армию (шла II Мировая война) и направлен на учебу в Хаверфордский медицинский колледж. Там у него диагносцировали опухоль черепной кости и после удачной операции в череп ему была вставлена Существуют компьютеры, у которых в качестве машинного языка используется язык программирования высокого уровня (например, Лисп, Форт). Тем самым эти языки в компьютере выполняют роль языков ассемблера.

заниматься математикой. Поступив в Колумбийский университет, он уже в 1949 г.

составе группы участвует в создании языка Fortran для IBM704 [18]. Позже Д. Бэкус в составе интернационального комитета работает над созданием языков Алгол-58 и Алгол-60, для которых создает нотацию, названную нотацией Бэкуса (Backus-Naur Form,сокращенно BNF). За этот результат он был награжден (1977) премией им. Тьюринга. В последующие годы (до 1991 г.) занимается уровневыми функциями программирования (function-level programming). Д. Бэкус был также включен в список 32 выдающихся ученых, которые заслужили высшую награду компьютерного сообщества1, но поскольку уже имели другие награды этого сообщества, то удостоены грамоты «Computer Pioneer Charter Recepiens» [19].

Адриаан ван Вийнгаарден родился в 1916 г. в Роттердаме. В 1939 г., по окончании учебы в Технологическом Университете в Дельфте, получает звание инженера-механика. Он собирается работать над докторской диссертацией по гидродинамике, но в эти планы вторгается война. После войны А. ван Вийнгаардена привлекает идея автоматизации расчетов, и с начала 1947 г. он Медаль «Computer Pioneer» (см. след. сноску на с. 15).

становится во главе Вычислительного отдела только что созданного Математического Центра (MC) в Амстердаме.

В 50-е гг. XX столетия он занимается языками программирования, входя в число создателей языков ALGOL и ALGOL-68, для которых он разрабатывает двухуровневый тип грамматики, названной W-грамматикой [20].

В 1961 г. он становится во главе Адриаан Вийнгаарден MC и работает на этом посту до 1981 г.

Не случайно А. ван Вийнгаардена называют «отцом» голландской информатики. Умер А. ван Вийнгаарден в 1987 г. в Амстердаме [21].

Алексей Андреевич Ляпунов родился в 1911 г. в Москве (академик-математик Александр Михайлович Ляпунов (1867– 1918) был двоюродным братом деда А. А. Ляпунова – Николая Васильевича Ляпунова). Формально высшего образования А. А. Ляпунов не получил – на физико-математическом факультете МГУ им. М. И. Ломоносова он проучился только один год, а затем, в 1929 г., ушел из университета, как он сам говорил впоследствии, «из-за удушающей коммунистической атмосферы».

Сблизившись в 1931 г. с академиком Н. Н. Лузиным (1883–1950), травля которого началась уже тогда, он под его руководством не только получает прекрасное математическое образование, но и новые результаты в дескриптивной теории множеств.

С 1934 г. до начала 50-х гг. (с перерывами) А. А. Ляпунов работает в Математическом институте им. В. А. Стеклова (МИ). Во время Великой Отечественной войны А. А. Ляпунов служит артиллеристом. Среди наград, полученных им на фронте, есть и орден Красной Звезды.

С 1953 г., по инициативе М. В. Келдыша, А. А. Ляпунов возглавил в Отделении прикладной математики МИ работы по программированию.

11 октября 1955 г. в Президиум ЦК КПСС поступило письмо большой группы советских ученых1, содержавшее оценку состояния биологии в СССР и критику взглядов и действий Т. Д.

Лысенко, организовавшего при И. Сталине разгром генетики.

В числе подписавших это письмо (или, как тогда говорили, «подписантов») был и А. А. Ляпунов [22].

Противостояние интеллигенции и власти, конечно, отражалось на творчестве А. А. Ляпунова, но именно в эти годы им получены ценнейшие результаты в кибернетике, программировании (в частности, построена теория ЯЛС [13]) и в теории функций вещественного переменного. Воспользовавшись созданием Сибирского отделения (СО) АН СССР, он в 1961 г. переезжает в Новосибирск, и фактически создает в Институте математики СО отделение кибернетики.

В 1964 г. А. А. Ляпунов был избран членом-корреспондентом Академии Наук СССР по отделению математики. Умер А. А. Ляпунов в 1973 г. В 1996 г. (посмертно) он был награжден самой престижной наградой Компьютерного сообщества (IEEE Computer Society) – медалью «Computer Pioneer»2 за «разработку теории операторных методов для абстрактного программирования, творцу советской кибернетики и программирования».

Письмо «трехсот».

Медаль была учреждена в 1981 г. Вручается за выдающиеся достижения в компьютерных науках, полученные более 15 лет назад от даты вручения. На аверсе медали выполнен барельеф Ч. Бэббиджа, а на реверсе – формула награждения.

§ 16. Языки высокого уровня и языки структурного программирования В период с 1954 по 1957 г. в США в корпорации IBM под руководством Джона Бэкуса был создан язык высокого уровня (с транслятором) ФОРТРАН (сокр. от англ. FORmula TRANslator = FORTRAN), имитирующий естественный язык, который был задуман для использования в научных и инженерных целях1. Многие десятилетия считалось, что это был первый язык высокого уровня, позволявший достаточно легко писать большие программы и решать задачи с разветвленной логикой [2].

Однако оказалось, что еще в 1945 г. для своей еще незаконченной машины Z4 немецкий ученый и инженер Конрад Цузе (Konrad Ernst Otto Zuse: 1910–1995) успел разработать первый в мире высокоуровневый язык программирования Plankalkl [1, c. 31]. Этот язык поддерживал не только операции назначения и вызов подпрограмм, но и итерационные циклы, условные операторы, массивы, обработку исключений. Представление чисел было с плавающей запятой. Частично результаты работы над этим языком были опубликованы К. Цузе2 в 1948–1949 гг. [23]. Но тогда мало кто обратил внимание на эту работу. Полностью описание языка и его возможностей было дано в брошюре 1972 г.

[24], когда пути развития программмиКонрад Цузе рования уже определились.

Напомним, что алгоритмический язык ФОРТРАН относится к числу операторных языков. Алгоритмы задаются с помощью операторов. Первичными структурами в Фортране являются числа, идентификаторы и строки.

О биографии К. Цузе см. [1, c. 30–32].

При жизни самого К. Цузе не было создано реализации для языка Plankalkl. Но в 2000 г. во Freie Universitt (Берлин) был создан первый компилятор языка Plankalkl для современных компьютеров.

Возвращаясь к Фортрану, заметим, что этот язык эволюционировал, но новые стандарты языка (FORTRAN 95, FORTRAN 2003) cохраняют преемственность c более старыми, что дает возможность использовать коды ранее написанных программ. В то же время стандартом языка FORTRAN 2008 уже достигается поддержка средствами языка параллельных вычислений.

Первый советский компилятор с Фортрана был создан к 1967 г.

для модификации машины Минск-21.

В 1968 г. для машины БЭСМ-6 в Объединенном институте ядерных исследований в Дубне был создан компилятор ФОРТРАН-ДУБНА. В 1970 г. в Институте Прикладной Математики (ИПМ) АН СССР была разработана графическая библиотека ГРАФОР (ГРАфическое расширение ФОРтрана = ГРАФОР). С 1972 г. вся линейка единой системы ЭВМ (ЕС ЭВМ), выпускавшихся в СССР, имела транслятор Фортрана.

В 1965 г. фирма IBM выпустила компьютер IBM 1130. Этот компьютер попал и в Национальную радиоастрономическую лабораторию (National Radio Astronomy Observatory (NRAO)), в которой уже с конца 50-х гг. работал Чарльз Мур (Charles H. Moore:

1938). Именно он, занимаясь разработкой программ сбора и обработки данных, получаемых радиотелескопом, уже в 1968 г.

создал первую версию языка FORTH2.

Машина «Минск 23». Главный конструктор – Виктор Владимирович Пржиялковский (р. 1930).

Сам Ч. Мур назвал свой язык FOURTH, полагая, что это будет язык для машин 4-го поколения, к которым относилась и IBM 1130. Однако IBM допускала имена, составленные не более чем из 5 прописных букв, и поэтому название языка было преобразовано в FORTH.

В этом языке программы записываются в виде последовательности лексем (по терминологии этого языка их называют «словами»). Для формул и математических выражений используется постфиксная запись1. Синтаксис базового уровня состоит из одного правила – «все определения разде- Чарльз Мур ляются пробелами».

Язык Форт – уникальный язык: с одной стороны, по многим свойствам он близок к языкам ассемблера, а с другой – его синтаксис и семантику можно расширить до любого другого языка программирования во время компиляции форт-программы.

Окончательная версия языка Форт появилась в 1971 г. и была принята в качестве основного языка Американским астрономическим обществом. Доктор Элизабет Ратер (Elizabeth Rather) из Университета штата Аризона в процессе сотрудничества с NRAO занялась (c 1971 г.) проблемой переписки программ, написанных на языке Форт, на наиболее распространенный язык FORTRAN.

В ходе этой работы ей, в кооперации с Чарльзом Муром, удалось существенно улучшить язык Форт.

В 1973 г. Ч. Мур и Э. Ратер основали компанию FORTH, Inc. Работа этой компании способствовала тому, что язык Форт был портирован на множество платформ. В частности, он был первым «resident software» на чипе Intel 8086 c 1978 г.

В 1977 г. в рамках Международного Астрономического сообщества был выработан глоссарий языка Форт, обозначаемый как AST.01 [25; 26].

Эту нотацию часто называют «обратной польской нотацией» (revers Polish notation (RPN)).

Э. Ратер была Президентом компании FORTH, Inc. с 1980 по 2006 г.

К 1994 г. при участии многих стран1 и фирм был принят ANSI стандарт языка FORTH.

К моменту появления первой версии языка Форт (1968) уже десять лет шло создание языков структурного программирования.

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

Первым языком структурного программирования был Алгол (ALGOrithmic Language = ALGOL). Причиной его появления было осознание потребности создания универсального языка, который, с одной стороны, служил бы для описания алгоритмов в научных публикациях, а с другой – был бы средством реального программирования.

В 1958 г. съехавшиеся на конференцию, проводившуюся на базе Европейского технического университета (Цюрих, Швейцария), ученые разных стран предприняли в течение недели попытку создания такого языка, назвав его Алгол-58. Этот язык был доработан Комитетом под эгидой Международной федерации по обработке информации (IFIP).

Его новый стандарт Алгол-60 обычно именуют просто Алгол.

В усовершенствовании этого языка2 (и создании стандарта АлC 1988 г. в рамках Ассоциации вычислительной техники (= Association for Computing Machinery (ACM)) была организована группа SIGFORTH для согласования окончательного стандарта языка FORTH. Eе российский аналог возглавлял С. Н. Баранов, опубликовавший (вместе с Н. Р. Ноздруновым) в 1988 г.

(тогда еще в Ленинграде) книгу «Язык Форт и его реализация» [25]. В 1990 г. в Москве вышел перевод книги Л. Броуди «Начальный курс программирования на Форте» c предисловием И. В. Романовского [26]. Эти две книги, выпущенные большими тиражами, способствовали знакомству российских математиков, а также всех интересующихся информатикой с языком Форт.

Подробнее см.: Роберт У. Себеста. Первый шаг к совершенствованию: язык ALGOL 60 // Основные концепции языков программирования / пер. с англ. – 5-е изд. – М.: Вильямс, 2001. – 672 с.

гол-68) от СССР активное участие принимал Григорий Самуилович Цейтин (р. 1936)1. Отметим, что наиболее новой и весьма полезной идеей всех стандартов Алгола являлось понятие процедуры. В Вычислительных центрах в СССР создавались библиотеки процедур, разумеется, тех, в которых не использовались глобальные переменные и операторы перехода, выхоГ. С. Цейтин дящие за пределы тела процедуры.

В работе Комитета по разработке стандарта языка Алгол- участвовал швейцарский ученый Никлаус Вирт (Niklaus Emil Wirth: 1934). В 1968–1969 гг. он руководил созданием языка структурного программирования, который мог бы использоваться как в промышленном программировании, так и при обучении программированию в высшей школе. Этот язык был назван Паскаль, в честь французского математика Блеза Паскаля (1623– 1662), создателя одной из первых механических вычислительных машин (см. [1, с. 11; 27]).

Язык Паскаль не был первым языком, созданным на основе Алгола. Так, еще в 1966 г. Н. Вирт вместе с Хельмутом Вебером (Helmut Weber: 1947) создали язык Эйлер [28; 29], являвшийся расширением и обобщением языка Алгол-60. Язык Эйлер был более простым и более гибким, чем Алгол-60. Он использовался для микропрограммного обеспечения IBM 360/302.

Позже (в 1978 г.) Н. Виртом на основе языка Паскаль и стандартов Алгол был разработан язык программирования общего наБиографию Г. С. Цейтина см. на стр. 100.

Helmut Weber. A microprogrammed implementation of EULER on IBM system/360 model 30 // Communications of the ACM. – V. 10. – Issue 9. – Sept. 1967.

значения Модула-21. Особенностью этого языка, в частности, была возможность создавать на нем такие системные программы, как обработчики прерываний и драйверы устройств, а также поддерживать программирование параллельно взаимодействующих процессов [30]. В свою очередь, язык Модула-2 повлиял на создание языков Modula-3, Oberon, Ada, Fortran-90, Lua, Zonnon и Modula-GM2.

В 1966 г. (когда Н. Вирт и Х. Вебер завершили создание языка Эйлер), в Кембриджском университете (Великобритания) Мартин Ричардс (Martin Richards) разработал язык программирования, предназначавшийся для написания компиляторов для других языков [31].

Этот язык, названный BCPL (Basic Combined Programming Language), заинтересовал двух сотрудников лаборатории фирмы AT&T Bell Telephone Кена Томпсона (Kenneth Thompson: 1943) Ritchie: 1941–2011). На основе этого языка Кен Томпсон (при содействии Д. Ритчи) создает 1969 г. язык «В» = Би. Предполагалось, что этот язык будет использоваться в операционной системе UNIX, К. Томпсона) к 1973 г. разработал станМартин Ричардс дартизированный процедурный язык Язык Модула-2 испытал также влияние языка Simula-67 (подробнее см. [30]).

Популярности языка Паскаль во многом способствовала деятельность публичной компании Borland International, образованной в 1983 г. со штабквартирой в г. Остин (штат Техас). В 1992 г. этой фирмой был выпущен пакет программирования, использующий язык Паскаль, Turbo Pascal 7.0. (Позже эта фирма была преобразована в фирму Borland Software Corporation, а в 2009 г.

поглощена британской фирмой Micro Focus.) программирования «С» = Си [32], который и используется с тех пор в операционной системе UNIX1. Позже язык Си был перенесен на многие другие операционные системы [33]. Этот язык широко применяется для создания как прикладных программ, так и системного программного обеспечения.

Никлаус Вирт родился в 1934 г. в предместье Цюриха (Швейцария) в семье школьного учителя. С детства Н. Вирт увлекался электроникой и конструированием. В 1954 г. поступил на факультет электроники Технического института (ETH)2 в Цюрихе. По получении степени бакалавра электротехники (1958) продолжил обучение в Лавальском университете (Universit Laval) штата Квебек в Канаде.

По результатам магистерской диссертации (1960) Н. Вирт был приглашен в университет в Беркли (Калифорния) к одному из пионеров компьютерных наук профессору Гарри Хаски (Harry Huskey: 1916), начинавшему работать над ENIAC еще в 1945 г. в Пенсильванском университете. Под руководством Г. Хаски Никлаус Вирт начал работу над созданием языка Эйлер на основе Алгола-60 средствами языка Лисп. После успешной защиты диссертации (1963) Н. Вирт был приглашен в Комитет по стандартизации Алгола и разработке стандарта Алгол-68. Одновременно, став (1963) ассистентом Стенфордского университета, Н. Вирт разработал (вместе с Д. Уэльсом3) в 1963–1967 гг. для программирования на платформе IBM/360 язык PL/360.

Возвратившись в ETH в Цюрих (1967), Н. Вирт работает там вплоть до выхода на пенсию в 1999 г.

Подробнее об этой системе см.: [34].

ETH = Eidgenssische Technische Hochschule in Zrich.

Не путать с Джимми Уэйлсом (Jimmy Donald Wales: 1966) – основателем Википедии.

Никлаус Вирт программирования встроенных систем, К 1980 г. под руководством Н. Вирта была разработана система Lilith для персонального 16-ти разрядного компьютера, которая на десятилетие обогнала одну из основных тенденций компьютерной индустрии [33].

В 1988 г. вместе с Ю. Гуткнехтом (Jrg Gutknecht: 1949), тогда еще Assistant Professor компьютерных наук в ETH, Н. Вирт разработал язык Оберон – упрощенную версию Модулы-2, но дополненную новыми возможностями [34].

В 1996 г. Н. Вирт разработал оригинальный язык Lola, для обучения и симуляции цифровых электрических схем [35].

За свои достижения Н. Вирт получил много премий и наград.

Выделим только премию ACM 1984 (премию им. Тьюринга) и присуждение ему в 2007 г. Российской Академией Наук ученой степени доктора honoris causa.

Кен Томпсон родился в 1943 г. в г. Новый Орлеан (США).

Учился в Калифорнийском университете в Беркли, специализируясь в области электротехники и информатики. В 1965 г. он получил в этой области степень бакалавра, а год спустя – магистра наук.

В лаборатории фирмы AT&T Bell (сокращенно Bell Labs) начинается многолетнее творческое сотрудничество Кена Томпсона с пришедшим в эту лабораторию в 1967 г. Деннисом Ритчи. В 1969 г. они оба стали творцами операционной системы UNIX [36]. Тогда же для этой системы К.

Томпсон создает язык программирования Би1, явившийся предшественником языка Си Денниса Ритчи.

Позже К. Томпсон вместе с Джозефом Кондоном (Joseph Condon) создали аппаратное и программное обеспечение для шахматного компьютера Bell ([38], см. также [1, с. 148–150]).

В 2000 г. К. Томпсон ушел из Bell Labs и до 2006 г. работал в корпорации Entrisphere, Inc. Последние годы К. Томпсон работает в корпорации Google над созданием языка Go.

За свои научные результаты К. Томпсон получил немало наград. Так, в 1983 г. Томпсон и Ритчи получили премию им. Тьюринга «за разработку общей теории операционных систем и, в частности, за создание UNIX».

Деннис Ритчи родился в 1941 г. в районе Бронксвилл (НьюЙорк) в семье научного сотрудника Bell Labs A. Ритчи (Alistair E.

Ritchie). После окончания средней школы в городке Саммит штата Нью Джерси поступил в Гарвард, получив по окончании учебы степень магистра физики. Далее, с 1967 г. до выхода на пенсию, Несколько ранее К. Томпсон создает язык Bon для операционной системы Multics, которая оказалась неудачной, но опыт работы над ней послужил созданию UNIX [37].

этой пробы (система получилась чрезмерно усложненная) обогатила опытом, и к Деннис Ритчи Позже, в 1978 г., Д. Ритчи вместе с канадским ученым Брианом Керниганом (Brian Wilson Kernighan: 1942), работавшим в то время в Bell Labs, издает книгу «Язык программирования Си»

[32], которая была переведена на многие языки и сделала Д. Ритчи знаменитым.

Деннису Ритчи принадлежит также расширение ALTRAN для языка FORTRAN. За свои научные результаты Д. Ритчи был неоднократно награжден: в 1983 г. – премией им. Тьюринга (совместно с К. Томпсоном) – за разработку общей теории операционных систем, в частности, за создание UNIX; в 2005 г. – премией Исследовательского Института Промышленности2 – за вклад в науку и технологии.

Деннис Ритчи умер 12 октября 2011 г. от рака, через неделю после смерти Стива Джобса – основателя компании Apple.

Название диссертации было «Program Structure and Computational Complexity».

Находится в городке Арлингтон (штат Вирджиния) – фактически пригороде Вашингтона.

§ 17. Языки конкретных классов задач В те же годы, когда появлялись языки структурного программирования (т. е. в 1958–1975 гг.), для решения конкретных классов задач создавались свои языки программирования.

В 1958 г. был создан первый аппликативный1 (функциональный) язык Lisp (от англ. LISt Processing), автор – Джон Маккарти (John McCarthy: 1927–2011)) (см. [40], а также [1, c. 141–142]).

Язык Lisp создавался Д. Маккарти с 1955 г. в процессе работы над системами искусственного интеллекта2 в Массачусеттском Технологическом Институте (MIT). У языка Lisp появилось немало диалектов: Lisp 1.5, MacLisp, ZetaLisp, NIL, InterLisp, Common Lisp, Scheme, ISLISP (последние три из них используются и в настоящее время).

В 1960 г. Д. Маккарти публикует работу3, в которой не только описываются цели создания функциональных языков программирования (в частности, Lisp), и при этом демонстрируется возможность участия объекта, как в роли функции, так и в роли аргумента, но и утверждается возможность автоматизации проверки математических утверждений.

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

По своему синтаксису Lisp схож c создававшимся в 60-е гг.

также для применения в исследованиях, связанных с искусственАппликативные языки программирования базируются на последовательном применении функциональных преобразований к данным (подробнее см. [39]).

Сам термин «искусственный интеллект» появился на рубеже 1955–56 гг.

(см. [1, с. 127]).

McCarthy D. Recursive Functions of Symbolic Expressions and Their Computation by Machine // Communications of the ACM. – 1960. – No. 3 (4). – P. 184–195.

мысли автора, должно было стать создание систем планирования действий роботов.

В СССР язык Planner был реализован примерно через 10 лет в системе ПЛЭНЕР-БЭСМ для БЭСМ-6.

В 1965 г., т. е. через пять лет после выхода упоминавшейся выше работы Д. Маккарти, вышла работа Джона Робинсона (John Биографии С. Пейперта (Seymour Papert) и М. Мински (Marvin Minski) см. в I части книги. M. Петерсон защитил докторскую диссертацию в 1967 г. в Кембридже. После трех лет работы в MIT вернулся в Великобританию в Университет Варвика, где стал (и оставался до 2007 г.) директором Центра дискретной математики и ее приложений.

Alan Robinson: 1930)1, являющаяся базовой в автоматизации правила резолюции в логике2. Реализовал метод автоматического доказательства теорем (предложенный Д. А. Робинсоном) в 1973 г. Робин Милнер (Arthur John Robin Gorell Milner: 1934–2010), положив начало создания семейства ML (Meta Language) – строгих языков функционального программирования [43].

Язык Planner был первым языком того направления в программировании, которое получило название логического программирования, и опирается на автоматическое доказательство теорем [45–46]. Самым известным языком логического программирования является язык Prolog (от фр.

PROgrammation en LOGique).

Prolog – это язык и система логического программирования, основанная на некотором подмножестве3 формальной системы – John Alan Robinson. A Machine-Oriented Logic Based on the Resolution Principle // Communications of the ACM. – 1965. – No. 5. – P. 23–41.

В СССР метод построения машинных алгоритмов поиска логического вывода для любых логических исчислений (а не только для исчисления предикатов первого порядка, как у Д. Робинсона) был дан С. Ю. Масловым (1939– 1982) в 1967 г. в работе [42] (см. также [1]).

Это подмножество состоит из предикатов логики дизъюнктов Хорна. Дизъюнкт Хорна – это дизъюнкция литералов с не более чем одним положительным литералом. Напомним, что литерал – это запись в исходном коде программы, представляющая собой фиксированное значение. Константы отличаются от литералов тем, что к ним обращение осуществляется посредством ссылок. К элементарным литералам относятся, в частности, литералы для записи чисел (числовые литералы), строки символов, заключенные в кавычки или скобки (строковые литералы), два литерала true и false или их аналоги (логические литералы). Дизъюнкт Хорна ровно с одним положительным литералом называется определенным дизъюнктом. Дизъюнкт Хорна без положительных литералов в логическом программировании называется целью (или запросом). Поскольку резолюция двух дизъюнктов Хорна является дизъюнклогики исчисления предикатов первого порядка (см. [1, c. 132– 133]). Основными понятиями в Prolog являются факты, правила логического вывода и запросы. Эти понятия позволяют описывать базы знаний, процедуры логического вывода и принятия решений.

Тем самым появление языка Prolog завершило создание аппарата для создания экспертных систем – и они немедленно появились [1, § 14].

Язык Prolog был описан в 1972 г. французским информатиком Аленом Кольмерауером (Alain Colmerauer: 1941) при поддержке Филиппа Руссела (Philippe Roussel) [47].

К основным реализациям языка Prolog относятся: GNU Prolog, Quintus, SICStus, YAP.

В 1967 г. появился язык Simula-67, инспирированный Алголом-60 [48]. Создателями этого языка были двое норвежцев:

совершенно нового класса языков – объектно ориентированных языков (ООП) [49], Кристен Нюгорд базирующиеся на понятиях инкапсуляции1, том Хорна, а резолюция цели и определенного дизъюнкта также является дизъюнктом Хорна, то в автоматическом доказательстве теорем это дает результат, если теорема представлена в виде цели. Добавим, что дизъюнкты (Хорна) были впервые описаны американским математиком Альфредом Хорном (Alfred Horn: 1918–2001) в работе [44] в 1951 г.

Инкапсуляция – это свойство системы, позволяющее объединить данные и методы, работающие с ними в класс, избавив пользователя от деталей реализации [49].

наследовании1, полиморфизма2, дающих возможность, разбивая задачу на составные части, работать над каждой частью по отдельности, применяя ставшие уже классическими принципы структурного программирования [49; 50].

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

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

Добавим, что каждый объект является представителем класса, который выражает общие свойства объектов. Классы организованы в ориентированное граф-дерево с единственным корнем. Возвращаясь к языку Simula-67, отметим, что фактически этот язык есть объектное расширение языка Algol-60.

Через два года после появления языка Simula-67 была начата разработка следующего объектно ориентированного языка, названного Smalltalk (доступен для пользователей с 1980 г.). В окончательную версию Smalltalk-80 были добавлены метаклассы.

Наследование – это свойство системы, позволяющее описать новый класс, на основе существующего, с частично или полностью заимствующимися признаками, или, как говорят программисты, функциональностью [49].

Полиморфизм – это свойство системы использовать объекты с одинаковым интерфейсом без информации о типе и внутренней структуре объекта [49].

высокопроизводительных серверов. Уже из названия языка следует, что он является развитием языка Си. Являясь весьма популярным языком общего назначения, он, в отличие от языка Си, поддерживает объектно ориентированное и обобщенное программирование [33].

В мае 1995 г. был выпущен императивный, кроссплатформенный объектно ориентированный язык Джава = Java1. Основное его достоинство – наличие программы, обрабатывающей байтовый код и передающей инструкции оборудованию как интерпретатор, и, тем самым, независимость байтового кода от операционной системы и оборудования. Язык Java соединил в себе достоинства многих языков, прежде всего Ada-83 и Object Pascal, появившихся в промежутке 1983–1994 гг., но повлиял также на многие языки, появившиеся позже. Впрочем, и сам язык Java претерпел ряд модификаций: Java 2, Java 5.0, Java 6, Java7.

Отметим также, что внутри Java существует уже несколько семейств технологий, обеспечивающих, в частности, возможность использования в устройствах с ограниченной вычислительной мощностью, например в мобильных телефонах, или с ограниченной памятью, например в смарт-картах (подробнее см., например, [52–55]).

Язык Java был разработан компанией Sun Microsystems, позже поглощенной компанией Oracle Corporation.

Упражнения 1. Требуется составить таблицу значений функции y = f (x) для x1,…,xn, если x*= 2, x1 = -1, xk = (x1)k, k: = 2,3,…,20, n = 20.

[9, с. 139, пример 3.2] Напишите программы для вычисления таблицы на языках:

FORTRAN, ALGOL-68, C, Pascal, Java.

2. Какие средства существуют в разных языках, обеспечивающие прерывание нормального хода программы при определенных условиях (ситуации прерывания)? Приведите примеры.

3. Какие операторы ввода (вывода) применяются в разных языках? Опишите их, приводя примеры.

4. Дайте определение простой переменной и переменной с индексами в выбранном вами языке. Что такое описание массива?

5. Как выглядит оператор процедуры в языках, которые вы знаете? Приведите пример рекурсивной процедуры в произвольных, по вашему выбору, языках.

6. Дайте определение гипертекста1. Приведите пример. Что такое гиперссылка?

7. Что такое метаязык?2 Приведите пример. Дайте определение формы Бэкуса-Наура.

Изобретателем понятия «гипертекст» (1965) и создателем гипертекстовой системы Xanadu является американский философ и социолог Тэд Нельсон (Theodor Holm Nelson: 1937).

Напомним, что понятие «метаязык» было введено польским математиком Альфредом Тарски (Alfred Tarski (Tajtelbaum): 1902–1983) (подробнее см.:

Тарски А. Введение в логику и методологию дедуктивных наук. – М.: Госиздат ИЛ, 1948. – 325 с.; а также [1]).

Глава V. История баз данных и информационно-поисковых систем § 18. Система управления базами данных в интерактивном режиме Напомним, что базой данных (БД)2 называется совокупность данных, организованных в соответствии с определенными правилами и поддерживаемых в памяти компьютера [56; 57]. При этом обычно добавляется, что эта совокупность данных характеризует актуальное состояние некоторой предметной области и служит для удовлетворения информационных потребностей пользователей.

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

Более того, неправомерно называть базами данных сведения из определенного вида деятельности человека, которые хранят, например, бухгалтерские книги (что имело место в средневековой Италии, начиная с XV в.), сведения о страховых случаях с морскими судами (с XVI в.) в Англии, сведения об уплате податей в Киевской Руси после административной реформы княгини Ольги (945) и т. д. Тем не менее нередко период до 1900 г.

В данной главе не приводится история языка SQL, позволяющего определять и динамически изменять схему базы данных, история оператора SELECT, агрегатных функций, средств формулировки аналитических и рекурсивных запросов, средств манипулирования данными, объектных расширений языка баз данных SQL.

Термин база данных (Data Base) появился только в начале 60-х гг. До этого употреблялся термин банк данных.

называют нулевым периодом в истории баз данных, а период 1900–1950 гг. – первым периодом истории баз данных.

Фактически, история баз данных начинается только с 1955 г., когда появилось программируемое оборудование обработки записей на основе файлов1. В тот период данные (во внешней памяти) хранились на перфокартах [56], хотя уже в феврале 1954 г. бывшему школьному учителю Рейнольду Джонсону (Reynold B. Johnson: 1906–1998), с 30-х гг.2 связанному с фирмой IBM, впервые удалось переписать данные с перфокарт на диск3. В г. уже был выпущен серийный дисковый накопитель, который фирма IBM выпустила для своей системы IBM 305 RAMAC4.

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

Первый шаг в создании системы управления базами данных (СУБД) был сделан Чарльзом Бахманом (Charles William Bachman: 1924) в 1960 г., когда он перешел в корпорацию General Electric (GE) из химической компании Dow Chemical. В GE он Напомним, что файл (в этой главе) – это именованная область внешней памяти, в которую можно записывать и из которой можно считывать данные [56, с. 19].

В 1971 г. Р. Джонсон покинул фирму IBM, в рамках которой им было получено свыше 90 патентов, в том числе и на «электрографию» – прародительницу ксерокопирования. В 1986 г. Р. Джонсон за свои изобретения получил из рук Президента США Р. Рейгана Национальную медаль Технологий, а в г. – Computer Pioneer Award [58].

Появление устройств внешней памяти со съемными пакетами магнитных дисков и подвижными головками чтения/записи вызвано было к жизни, в первую очередь, требованиями со стороны бизнес-приложений. Впрочем, сама идея наличия головки считывания/записи восходит к ленточным автоматам Э. Поста и А. Тьюринга (см., например, [1, гл. II]).

RAMAC = Random Access Method of Accounting and Control. Систему IBM 305 RAMAC иногда называют первым суперкомпьютером.

Ч. Бахман был и руководителем рабочей группы Date Base Task Group, созданной в 1965 г. и разработавшей концепцию схем баз данных и концепцию независимости данных, сформулировавшей понятие подсхемы (первая Чарльз Бахман 1971, 1973 и 1978 гг. (см. [56; 59]).

Следующий шаг в развитии БД был сделан специалистами из IBM в середине 60-х гг. для серии компьютеров IBM/360, когда ими была создана операционная система OS/360 и в рамках этой ОС – первая развитая система управления файлами1. Реализация этой системы стала возможной благодаря появлению контроллеров управления дисковыми устройствами.

Чарльз Бахман родился в городке Манхэттен штата Канзас в семье футбольного тренера из колледжа (Kansas State College) в 1924 г. Среднюю школу он окончил в городке Восток Лансинг (East Lansing, штат Мичиган), где находится университет штата Мичиган. С марта 1944 г. Ч. Бахман служит в армии США (в противовоздушной артиллерии) на театре военных действий против Японии. После демобилизации в 1946 г. поступает в колледж Напомним, что английский термин file system и соответствующий русский термин файловая система имеет два значения: 1) архив файлов, хранящихся во внешней памяти и 2) программная система, управляющая файлами [56]. Файлы, которые представляют собой наборы блоков, нумеруемых в адресном пространстве файла и отображаемых на физические блоки диска, называют базовыми. Первоначально в файловых системах пользователи представляли файл как последовательность записей, однако с появлением ОС UNIX все чаще любой файл представляется как непрерывная последовательность байтов.

штата Мичиган (при Мичиганском университете) и в 1948 г. получает степень бакалавра по инженерной механике. Через два года он получает степень магистра по этой же специальности в университете штата Пенсильвания. Далее – десятилетняя (до 1960 г.) работа в химической компании Dow Chemical (Мидленд, штат Мичиган), где он дослужился до должности менеджера по обработке информации1.

Перейдя в 1960 г. в фирму General Electric (GE), Ч. Бахман разрабатывает одну из первых в мире СУБД, названную им Integrated Data Store (IDS).

К IDS он, при поддержке крупнейшей целлюлозо-бумажной компании Вейерхойзер Ламбер (Weyerhaeuser Lumber), создает первое в мире мультипрограммное устройство2 по выборке информации. Покинув GE в 1970 г., Ч. Бахман переходит в маленькую компанию Cullinane Information Systems, переименованную позже в Cullinet., создававшую программное обеспечение для фирмы IBM.

В 1973 г. за выдающийся вклад в развитие технологий баз данных был награжден Премией Тьюринга. Позже под руководством Ч. Бахмана был, в частности, разработан стандартный язык определения данных и манипулирования данными; он же был одним из первых создателей сетевой3 модели баз данных.

Работы Ч. Бахмана за период с 1951 по 2007 г. хранятся в Институте им. Ч. Бэббиджа Университета Миннесоты.

Data Processing menager.

Multiprogramming access.

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

[56]).

§ 19. Реляционная модель данных В 1969 г. в Сан-Хосе (Калифорния) в фирме IBM математик Эдгар («Тед») Кодд (Edgar Frank Codd: 1923–2003) закончил работу над первой реляционной1 моделью данных (опубликована год спустя [60]). Однако более десятилетия все результаты Э. Кодда подвергались критике за якобы невозможность эффективной реализации такой модели. Были и другие причины, мешавшие принятию этой модели. С одной стороны, это была критика Ч. Бахмана, с другой – сложившееся мнение о Э. Кодде как о «леваке», он был вынужден даже на 10 лет (1953–1963) покинуть США из-за преследований маккартистов2.

Вместе с Э. Коддом он разрабатывает (первую) нормальную форму (названа позже формой Бойса-Кодда), и вместе они формулируют основные понятия баз данных: тип данных, домен, атрибут, отношение, заголовок (= схема) отношения, кортеж, тело отноЭдгар Кодд Термин «реляционный» произошло от relation (= отношение).

Сенатор-республиканец Джозеф Маккарти (Joseph McCarthy: 1908–1957) был олицетворением сил, боровшихся в период 1947–1956 гг. не только против левых идей, но и против гомосексуалистов. И это последнее, было, повидимому, единственным, что ему нравилось в политике СССР.

Напомним, что понятие типа данных взято в точности из языков программирования. В реляционных базах данных обычно хранятся символьные, числовые, специализированные числовые, специальные временные и собственные данные.

Реляционная модель данных с момента ее создания, согласно наиболее распространенной трактовке, состоит из трех частей:

структурной части, манипуляционной части и целостной части1.

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

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

Заголовком отношения называется конечное множество (H) атрибутов, т.

е. упорядоченных пар вида, где А – имя атрибута, а Т – имя некоторого базового элемента или домена.

Кортежем t, соответствующим заголовку H, называется множество упорядоченных триплетов вида, где является допустимым значением типа данных или домена Т.

Телом В отношения называют произвольное множество кортежей t.

Первичным ключом (переменной) отношения является такое подмножество S – множества атрибутов ее заголовка, что в любое время значение первичного ключа в любом кортеже тела отношения отличается от значения первичного ключа в любом другом кортеже тела этого отношения, а никакое собственное подмножество множества S этим свойством не обладает [56].

n-арным отношением называют подмножество декартова произведения множеств D1, D2,…,Dn, не обязательно различных. Множества D1,…,Dn называют доменами. Интерпретация отношения – это таблица с n столбцами, в которой нет двух одинаковых строк, а столбцы соответствуют атрибутам отношения. При этом каждый атрибут в отношении имеет уникальное имя (подробнее см. [56; 57; 60]).

Структурная часть модели определяет, что единственной структурой данных является нормализованное n-арное отношение.

Манипуляционная часть модели определяет два основных способа манипулирования данными: с помощью реляционной алгебры и с помощью реляционного исчисления.

Целостная часть реляционной модели определяет два базовых требования целостности: 1) требование целостности сущности (entity integrity), выражающееся в том, что любая переменная отношения должна обладать первичным ключом и никакое значение первичного ключа в кортежах значения/отношения переменной отношения не должно содержать неопределенных значений; 2) требование целостности по ссылкам (referential integrity), выражающееся в том, что для каждого значения внешнего ключа, появляющегося в ссылающемся отношении, на которое ведет ссылка, либо должен найтись кортеж с таким же значением первичного ключа, либо значение внешнего ключа должно быть неопределенным (т. е. ни на что не указывать) [56; 57]).

торой был предложен Кристофером Дейтом (Christopher J. Date:

1941) и назван реляционной алгеброй Кодда1.

Раймонд Бойс до своей смерти (1974) успевает вместе с Дональдом Чемберленом (Donald D. Chamberlen: 1944) разработать и язык SQL (= Structure Query Language) – первый коммерчески удачный язык для реляционных моделей данных [61]. Первой реализацией SQL стала реляционная СУБД System R2, созданная в 70-х гг. [62].

System R претерпел развитие, но сохранил большинство традиционных средств языка SQL. Именно в это время к развитию СУБД System R в рамках компании IBM подключился Вон Ким (Won Дональд Чемберлен Kim). Чаще всего из этого периода циВ алгебре Кодда определяются два класса операций: теоретико-множественные (объединение, пересечение, взятие разности и взятие декартова произведения отношений) и специальные реляционные операции (ограничение отношения, проекцию отношения, соединение отношений и деление отношений).

Кроме того, в алгебру включают две операции: операцию присваивания и операцию переименования атрибутов [56, с. 56].