Теория алгоритмов в лицах: А. А. Марков

 

 

Федеральное государственное  бюджетное образовательное учреждение

высшего профессионального образования

 «Алтайская государственная  педагогическая академия»

 

Институт физико-математического  образования

 

Кафедра теоретических основ  информатики

 

 

 

Теория алгоритмов в лицах: А. А. Марков

Курсовая работа

 

 

Выполнила

студентка 394 группы

Сулоева Е. К.

___________________________

        (подпись)

Научный руководитель

к.п.н., доцент кафедры теоретических  основ информатики  Афонина М. В. ___________________________

          (подпись)

Оценка _____________________

Барнаул 2012

Оглавление

Введение ………………………………………………………………………..3

§1 Биография А. А. Маркова  ………………………………………………….4

1.1 Детство и юность……………………………………………………….......5

1.2 Карьера…………………………………………………………...…………6

1.3 Научные труды……………………………………………………………..9

§2 Нормальные алгоритмы Маркова………………………………………...11

§3 Принцип нормализации Маркова………………………………………...16

Заключение……………………………………………………………………18

Библиографический список используемой литературы……………………21

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Введение

В нашей жизни мы очень  часто используем термин «алгоритм», определение которого является интуитивным. Изучением уточнения этого понятия  занимались многие ученые: Алан Матисон  Тьюринг, Эмиль Леон Пост, Андрей Андреевич  Марков и многие другие. Нормальный алгоритм Маркова (НАМ, также марковский алгоритм) – один из способов формального определения понятия алгоритма. Теория нормальных алгоритмов (или алгорифмов, как называл их создатель теории) была разработана советским математиком Андреем Андреевичем Марковым (1903 – 1979) в конце 1940–х – начале 1950 годов двадцатого века. Эти алгоритмы представляют собой некоторые правила по переработке  слов, в каком – либо алфавите, так что исходные данные и искомые результаты для алгоритмов являются словами в некотором алфавите. Нормальные алгорифмы оказались удобным средством для построения многих разделов конструктивной математики. Кроме того, заложенные в определении нормального алгорифма идеи, используются в ряде ориентированных на обработку символьной информации языков программирования — например, в языке Рефал.

Данная тема «Теория алгоритмов в лицах: А. А. Марков» является актуальной, так как сама наука «Теория алгоритмов» важна в современном мире, она лежит в основе большинства компьютерных процессов, без которых мы не мыслим свою жизнь, а А. А. Марков внес большой вклад в ее развитие. 

Алгоритм А.А. Маркова (который  является алгоритмической моделью) оказал существенное влияние на развитие ЭВМ и практику программирования и является очень важной конструкцией в разработке алгоритмов.

Целью данной работы является изучение биографии А.А.Маркова, в частности событий и фактов, повлиявших на его становление как ученого и его вклад в «Теорию алгоритмов».

Задачи, решенные в процессе выполнения данной работы:

1. Изучить биографию А.А. Маркова: семья, образование, карьера.
2. Проанализировать вклад А. А. Маркова  в развитии «Теории алгоритмов».
3. Раскрыть сущность нормального алгоритма Маркова и роль данной модели в развитии.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

§1  Биография  А. А. Маркова

Андрей Андреевич Марков - один из крупнейших математиков и  логиков современности. Справедливости ради следует сразу же отметить, что в творческом пути А.А. Маркова  не было периода, на протяжении которого он не занимался бы математической наукой. Связь его с этой наукой несомненна, интерес к ней был  велик и неслучаен. Им был выполнен ряд исследований по конкретным проблемам  математики и теории алгоритмов, написаны статьи, подготовлено немало важных докладов.

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

1.1 Детство и юность

А.А. Марков- младший был  сыном знаменитого российского  математика, академика Андрея Андреевича (старшего). Он был первым и долгожданным ребенком в семье. У Андрея Андреевича и Марии Ивановны долго не было своих детей. Рождение сына перевернуло всю их жизнь, теперь главной целью стало воспитание маленького Андрюши. Мальчик много болел, и семья Марковых в 1910-1912 годах часто выезжала за границу, чтобы выходить малыша. Летом они отдыхали на курорте в Баден-Бадене, в Германии, осень проводили в Италии или в Швейцарии. ¹

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

Юноша Марков получил блестящее  образование и в 1919 году поступил на химический факультет Петербургского университета. С третьего курса он переходит на физическое отделение физико - математического факультета и заканчивает его в 1924 году уже после смерти отца.

С 1924 года А.А. Марков – аспирант, а затем (с 1928 по 1935 год)- сотрудник  Астрономического института. В 1927 году начал исследования по теории дифференцированных уравнений, а затем по топологии. В это время им выполнен ряд  замечательных работ по небесной механике, сохраняющих свое значение и в настоящее время. Занятия  небесной механикой естественным путем  подвели А. А. Маркова  к исследованию чисто математических проблем. «К 1935 я сложился как математик» - писал  он впоследствии в своей автобиографии. В этом году ему без защиты присуждается ученая степень доктора физико-математических наук, а в 1936 году он становится профессором  Ленинградского университета. В 1939—1972 работал в Математическом институте им. Стеклова АН СССР. До июля 1942 года находился в блокадном Ленинграде. Учёная степень доктора физико-математических наук присвоена без защиты диссертации в 1935 году. Таким образом, можно сделать вывод, что Марков стал математиком не по образованию, как это чаще всего случается с математиками- профессионалами, а по полученному опыту работы.

1.2 Карьера 

Диапазон математических дисциплин, затронутых А. А. Марковым на его творческом пути, был чрезвычайно  широк. Чуткий ко всему новому в современной  науке, А. А. Марков с пристальным  вниманием следил за первыми шагами становления общей теории алгоритмов, опиравшейся на произведенное в  середине 30 – х годов уточнение  общего понятия алгоритма. Он был  первым, кому в полной мере удалось  осознать фундаментальный характер этого события и те богатые  общелогические и общематематические возможности, которые оно открывало. Опираясь на точное понятие алгоритма, А. А. Марков продолжил и на современной  основе развил идеи Брауэля и Вейля, сформировав собственную концепцию  построения математики.

В 1950-х годах создал в Вычислительном Центре АН СССР лабораторию математической логики и структуры машин, которой руководил около двадцати лет.

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

Им был получен весьма неожиданный ответ на вопрос об инверсированной  сложности булевых функций и  их систем в 1957-1963 годах.

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

А. А. Марковым были заложены основы теории сложности алгоритмов, в рамках которой сложность конкретного  алгоритма трактуется как объем  памяти, потребный для запоминания  его программы. (В случае нормальных алгоритмов речь идет о длине их изображений или записей.) Предложенный им подход в 1964 году пролил свет на причины, по которым массовые алгоритмические  проблемы бывают неразрешимыми, и породил  обширную проблематику, впоследствии разрабатывавшуюся большим числом исследований.

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

Вопросами общего характера  посвящены его статьи «Математическая  логика и вычислительная математика»  и «Что такое кибернетика?». Вторая из этих статей представляет собой  резюме доклада, неоднократно читанного  в Москве в начале 60- х годов. В  этом докладе кибернетика определялась А. А. Марковым как общая теория причинных  сетей, не апеллирующая к понятиям «управления», «информация» и тому подобное, часто  употребляющимися в не очень определенном смысле. Доклад этот вызвал оживленную дискуссию, и , в частности, ответом  на него послужил известный доклад Андрея Николаевича Колмогорова (1903- 1987) «Что такое информация», прочитанный на заседании Московского математического общества.

Остро складывалась ситуация с конструктивным направлением в  математике. Уже первые антитеоретико- множественные выступления А. А. Маркова (конец 40- х – начало 50 –  х годов) были встречены «в штыки  » не только профессионалами –  идеологами, но и придерживавшимися  традиционных взглядов коллегами. А. А. Марков был обвинен в идеализме  и формализме, что граничило в  ту пору с политическим обвинением. Борьба, которую ему пришлось вести, была «войной одного против всех», и  то, что в этой войне ему удалось  отстоять свою точку зрения и даже просто уцелеть, объясняется не только его научным авторитетом или бойцовским темпераментом, но, в какой- то мере, и благосклонностью судьбы. Тем не менее, он не был избран действительным членом Академии наук, а членом- корреспондентом стал лишь в 1953 году уже будучи знаменитым ученым, он не был удостоен премий, обычно присуждавшихся ученым его ранга, его университетская кафедра подверглась притеснениям, а его ученики – по сравнению со своими сверстниками, равными по таланту, - имели гораздо меньшие шансы на продвижение. Одни из них были вынуждены поменять специальность, а другие – вообще покинуть страну. Не впадая в слишком большое преувеличение, можно сказать, что у себя на родине созданная А. А. Марковым направление оказалось – как и кибернетика - в числе репрессированных наук.²

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

Скончался А. А. Марков 11 октября 1979 года в Москве и похоронен на Новокузнецком кладбище.

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

Научные труды

Марков открыл достаточно много математических законов, установил очень много важных фактов, принимал участие во многих математических конференциях, хочется рассказать о некоторых очень немногих из них. Итак, классификация соударений в общей задаче трех тел впервые опубликована в журнале «Ленинградского физико-математического общества» в 1929 году (т.2 с.81-97).

В 1930 году опубликован закон  об интегрируемом случае ограниченной задачи трех тел в книге «Труды ІІ, ІІІ  и І ІV Астрономических съездов».

1934 - Закон об изотопии  компактных множеств в эквивалентных  пространствах.

В 1936 году было написано и  опубликовано довольно большое количество работ Маркова. Вот некоторые  из них:

1. О векторных пространствах конечной размерности в книге «Труды ІІ Всесоюзного математического съезда», Ленинград.

2. Арифметическая характеристика тригонометрических полиномов.

3. О теории стационарных колебательных процессов.

        1947 год – невозможность алгоритмов тождества и делимости в теории ассоциативных систем.

Конец 1940-х - начало 1950-х годов - нормальные алгоритмы Маркова.

1952 - О неразрешимых алгоритмических  проблемах.

1953 - Непрерывность конструктивных  функций.

1958 - Неразрешимость проблемы гомеоморфии, доклады о проблеме представимости матриц, о конструктивных функциях.³

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