Андрей андреевич марков реферат
Обновлено: 05.07.2024
Содержание
Вложенные файлы: 1 файл
ку.docx
Федеральное государственное бюджетное образовательное учреждение
высшего профессионального образования
Институт физико- математического образования
Кафедра теоретических основ информатики
Теория алгоритмов в лицах: А. А. Марков
студентка 394 группы
к.п.н., доцент кафедры теоретических основ информатики Афонина М. В. ___________________________
§1 Биография А. А. Маркова ………………………………………………….4
§2 Нормальные алгоритмы Маркова………………………………………. 11
§3 Принцип нормализации Маркова………………………………………. 16
Библиографический список используемой литературы……………………21
Введение
Алгоритм А.А. Маркова (который является алгоритмической моделью) оказал существенное влияние на развитие ЭВМ и практику программирования и является очень важной конструкцией в разработке алгоритмов.
Задачи, решенные в процессе выполнения данной работы:
§1 Биография А. А. Маркова
Андрей Андреевич Марков - один из крупнейших математиков и логиков современности. Справедливости ради следует сразу же отметить, что в творческом пути А.А. Маркова не было периода, на протяжении которого он не занимался бы математической наукой. Связь его с этой наукой несомненна, интерес к ней был велик и неслучаен. Им был выполнен ряд исследований по конкретным проблемам математики и теории алгоритмов, написаны статьи, подготовлено немало важных докладов.
Давайте проследим жизненный путь Андрея Андреевича, чтобы лучше понять, как ему удалось внести такой большой вклад в науку.
1.1 Детство и юность
А.А. Марков- младший был сыном знаменитого российского математика, академика Андрея Андреевича (старшего). Он был первым и долгожданным ребенком в семье. У Андрея Андреевича и Марии Ивановны долго не было своих детей. Рождение сына перевернуло всю их жизнь, теперь главной целью стало воспитание маленького Андрюши. Мальчик много болел, и семья Марковых в 1910-1912 годах часто выезжала за границу, чтобы выходить малыша. Летом они отдыхали на курорте в Баден-Бадене, в Германии, осень проводили в Италии или в Швейцарии. 1
В семье царила атмосфера, характерная для высшего слоя российской интеллигенции той поры: высокая мораль, строгая иерархия жизненных ценностей, вера в высокую миссию культуры. Отец своей самоотверженной любовью к науке, ответственным отношением к общей ситуации в ней, острым интересом к ее новейшим достижениям подавал благотворный пример сыну, относясь с полной серьезностью к его воспитанию. Некоторое время он даже преподавал математику в классе, в котором учился его сын.
Юноша Марков получил блестящее образование и в 1919 году поступил на химический факультет Петербургского университета. С третьего курса он переходит на физическое отделение физико - математического факультета и заканчивает его в 1924 году уже после смерти отца.
1.2 Карьера
Диапазон математических дисциплин, затронутых А. А. Марковым на его творческом пути, был чрезвычайно широк. Чуткий ко всему новому в современной науке, А. А. Марков с пристальным вниманием следил за первыми шагами становления общей теории алгоритмов, опиравшейся на произведенное в середине 30 – х годов уточнение общего понятия алгоритма. Он был первым, кому в полной мере удалось осознать фундаментальный характер этого события и те богатые общелогические и общематематические возможности, которые оно открывало. Опираясь на точное понятие алгоритма, А. А. Марков продолжил и на современной основе развил идеи Брауэля и Вейля, сформировав собственную концепцию построения математики.
В 1950-х годах создал в Вычислительном Центре АН СССР лабораторию математической логики и структуры машин, которой руководил около двадцати лет.
При построении теории нормальных алгоритмов А. А. Марковым была разработана развитая методика, в значительной степени предвосхищающая приемы структурного программирования и технику верификации программ.
Им был получен весьма неожиданный ответ на вопрос об инверсированной сложности булевых функций и их систем в 1957-1963 годах.
Им были найдены минимальные контактно-вентильные схемы, реализующие симметрические булевы функции в 1962 году.
А. А. Марковым были заложены основы теории сложности алгоритмов, в рамках которой сложность конкретного алгоритма трактуется как объем памяти, потребный для запоминания его программы. (В случае нормальных алгоритмов речь идет о длине их изображений или записей.) Предложенный им подход в 1964 году пролил свет на причины, по которым массовые алгоритмические проблемы бывают неразрешимыми, и породил обширную проблематику, впоследствии разрабатывавшуюся большим числом исследований.
Им был предложен и опробован в действии представляющий как теоретический, так и практический интерес точный язык для описания работы вычислительных машин в 1967 году.
Нельзя не упомянуть и том высоком этическом примере, который А. А. Марков подавал ученикам своим ежедневным поведением. Известно бесстрашие, с которым он выступал в защиту подвергавшихся преследованиям коллег и учеников. Эта роль Маркова- воспитателя – воспитателя, в основном, собственным примером, - безусловно, заслуживает отдельного рассмотрения. Но уже и сейчас мы можем с полной уверенностью утверждать, что научный вклад окружавших его учеников и сотрудников был неделим от их культурных, этических и гражданских качеств, сформировавшихся под его прямым и косвенным влиянием.
Скончался А. А. Марков 11 октября 1979 года в Москве и похоронен на Новокузнецком кладбище.
Из выше сказанного можно сделать вывод, что Андрей Андреевич был очень талантливым математиком. Безусловно, большой вклад на становлении его личности внес Андрей Андреевич (старший), давший ему хорошее образование и воспитание.
Научные труды
1934 - Закон об изотопии компактных множеств в эквивалентных пространствах.
В 1936 году было написано и опубликовано довольно большое количество работ Маркова. Вот некоторые из них:
2. Арифметическая характеристика тригонометрических полиномов.
3. О теории стационарных колебательных процессов.
1947 год – невозможность алгоритмов тождества и делимости в теории ассоциативных систем.
Конец 1940-х - начало 1950-х годов - нормальные алгоритмы Маркова.
1952 - О неразрешимых алгоритмических проблемах.
1953 - Непрерывность конструктивных функций.
1958 - Неразрешимость проблемы гомеоморфии, доклады о проблеме представимости матриц, о конструктивных функциях. 3
Доклад о некоторых алгорифмах связанных с системами слов, был представлен 1963 году, а уже в следующем году о нормальных алгорифмах, вычисляющих булевы функции.
Формировать интерес к математике.Учить пользоваться энциклопедическими словарями. Активизировать работу учащихся.Развивать эрудицию, математическую речь.
| Вложение | Размер |
|---|---|
| grigoreva_mariya.docx | 21.61 КБ |
Предварительный просмотр:
МКОУ Специальная ( коррекционная) школа-интернат VIII вида
УЧЕНИЦА 8 КЛАССА
АНДРЕЙ АНДРЕЕВИЧ МАРКОВ 1856- 1922.
А. А. Марков-русский математик, представитель петербургской математической школы. Он родился в Рязани. В 1874г. поступил на физико- математический факультет Петербургского университета, где под влиянием П. Л. Чебышева занялся теорией непрерывных дробей и теорией чисел.
В 1884г Марков защитил докторскую диссертацию. Посвященную непрерывным дробям, в которой доказал и обобщил некоторое неравенства Чебышева, опубликованные раньше без доказательств. Маркову принадлежат также многочисленные работы по различным разделам математического анализа. В 1890г. за глубокие научные исследования Марков был избран академиком петербургской академии наук.
С конца 90- гг. ХIХ в. главным предметом исследований ученого стала теория вероятностей. Здесь он продолжил работу своего учителя П. Л. Чебышева и ввел новый объект исследования- последовательности зависимых случайных величин, получившие в дальнейшем названия Марковских цепей. Так называют последовательности случайных величин, для которых вероятность появления того или иного значения на (к+1)- м шагу зависит лишь от того, какое значения эта величина приняла на k- м шагу, и не зависит от значений величины на 1м,2-м, ..(к- 1)-м шагах.
Марковские цепи сразу после их открытия не нашли практических приложений, и ученому пришлось применять свои результаты к распределению гласных и согласных букв в поэме А.С. Пушкина « Евгений Онегин. Ведь за согласной чаще идёт гласная, а за гласной- согласная, и в первом приближении можно считать, что вероятность появления гласной на (к+1)-м месте зависит лишь от того, гласной или согласной является буква, стоящая на к-м месте. Но, как всегда бывает с глубокими научными результатами, в дальнейшем были обнаружены гораздо более важные для практики области приложения марковских цепей (например, теория массового обслуживания). Из теории Марковских цепей возникла общая теория случайных процессов, которая применяется при изучении лавинных процессов и других проблем.
Андрей Андреевич Марков - известный отечественный математик, академик, который внес большой вклад в науку, изучая теорию вероятности. Также в сфере его интересов находились теория чисел и математический анализ. Примечательно, что при этом Андрей Андреевич воспитал сына, который тоже стал ученым. Он считается основоположником советской школы по изучению конструктивной математики.
Биография ученого
Андрей Андреевич Марков родился в 1856 году. Он появился на свет в Рязани. Его отец по имени Андрей Григорьевич был чиновником, служивший коллежским советником в Лесном департаменте. После того, как он вышел в отставку с этого поста, перебрался в Санкт-Петербург, где стал поверенным и главным управляющим в имении Екатерины Александровны Вальватьевой.
Дедушка героя нашей статьи Григорий Маркович был сельским дьяконом. Биография Андрея Андреевича Маркова сегодня хорошо известна всем, кто интересуется математикой. Он был дважды женат. Его первой супругой стала Надежда Петровна Федорова, дочь чиновника. Они родили шестерых детей. Мальчик Павел умер в детстве. Остальных детей звали Петр, Евгения, Мария, Михаил и Андрей.
Во второй раз он заключил брак с Анной Иосифовной, от которой у него родилось еще трое детей - Лидия, Владимир и Екатерина. Владимир Андреевич был талантливым ученым, который подавал большие надежды в математике. Но он умер в возрасте 26 лет от туберкулеза.
Хорошо известна и сестра его отца, которую звали Евгения Андреевна. В русскую историю она вошла как одна из первых отечественных женщин-врачей.
Сам Андрей Андреевич Марков страдал от туберкулеза коленного сустава с самого детства. Из-за этого ему пришлось до десяти лет передвигаться на костылях. Только когда известный хирург Кадэ провел операцию, он получил возможность нормально передвигаться.
Образование
В 1866 году Андрей Андреевич Марков поступил в пятую гимназию в Санкт-Петербурге. В то время это учебное заведение считалось классическим, в нем преподавались греческий и латинский языки. Гуманитарные науки пришлись не по вкусу герою нашей статьи, поэтому по большинству предметов он не успевал, прикладывая практически все усилия только для изучения математики.
Окончить гимназию ему удалось в 1874 году. После этого Андрей Андреевич Марков-старший стал студентом Санкт-Петербургского университета. В вузе он занимался у известных профессоров Золотарева, Коркина, а также у легендарного Пафнутия Чебышева (на фото выше), который сыграл значительную роль в судьбе героя нашей статьи.
Выпускником университета он стал в 1878 году. В Петербургском университете окончил физико-математический факультет по математическому разряду, получив степень кандидата наук. Отличился, став обладателем золотой медали за сочинение, посвященное интегрированию дифференциальных уравнений с помощью непрерывных дробей. Ему предложили остаться при университете, чтобы начать готовиться к получению профессорского звания.
Магистерская диссертация
В 1880 году Андрей Андреевич Марков-старший защитил свою знаменитую работу, посвященную бинарным квадратичным формам положительного определителя. Эта диссертация сразу сделала его одним из самых влиятельных ученых в этой области.
Вскоре после этого он успешно защищает докторскую диссертацию по приложениям алгебраических непрерывных дробей. Начиная с 1880 года, преподает в Петербургском университете на должности приват-доцента. Через три года успешной трудовой деятельности получает курс под названием "Введение в анализ", который до этого читали Поссе и Сохоцкий. Так совпало, что параллельно университет покинул знаменитый Чебышев, поэтому математик Андрей Андреевич Марков начал обучать студентов основам теории вероятностей.
В 1886 году героя нашей статьи выбрали адъюнктом на физико-математическом отделении, с тех пор он начал заниматься исключительно чистой математикой. С 1896 года становится ординарным академиком при императорской академии наук в Санкт-Петербурге.
По возрастающей развивалась его карьера и на физико-математическом факультете. В 1886 году он получил пост профессора, а в 1898 - действительного статского советника.
В 1922 году Марков умер в Петрограде. Ему было 66 лет. Ученого похоронили на Митрофаниевском кладбище. В 1954-м был перезахоронен на Литераторских мостках на Волковском кладбище.
Научная работа
Говоря о математике Андрее Андреевиче Маркове и его достижениях, нужно отметить, что наибольший вклад он внес в изучение теории вероятностей. Марков стал первооткрывателем большого класса стохастических процессов, которые сопровождались непрерывной временной и дискретной компонентой. В будущем они были названы в его честь.
Его процессы можно описать таким образом. Состояние самого процесса напрямую зависит исключительно от текущего состояния. Сама теория вероятности в те годы была построена таким образом, что она считалась исключительно абстрактной, но в настоящее время она находит применение на практике.
Марков вывел теорию цепей, которая сразу стала важной областью научных исследований. Так называемая теория марковских процессов представляла собой базис для более глобальной теории, посвященной стохастическим процессам. Это также известно, как неравенство Маркова. Математик сыграл большую роль в продвижении классических исследований своих предшественников, которые относились к большим числам и центральной теореме теории вероятностей, занимался проблемой распространения их на так называемые цепи Маркова.
Отдельно стоит отметить, что знаковым открытием Маркова стала работа, связанная с теорией случайных процессов, а также с теорией вероятности в целом. Похожих успехов в будущем добился Колмогоров, который предложил строгую и четкую теоретико-вероятностную формулировку, выдвинув ее на основе теории меры.
Успехи в математическом анализе
Большой вклад ученый, которому посвящена эта статья, внес в математический анализ. В исчерпывающем списке трудов, над которыми трудился Марков, работы по математическому анализу занимают около трети. В первую очередь он усердно изучал теорию непрерывных дробей, вычисление конечных разностей, экстремальные задачи, которые предстоит решать в так называемых функциональных пространствах, а также занимался изучением теории интерполирования функций, проблемой моментов, квадратурными формулами, теорией ортогональных многочленов, дифференциальными уравнениями, теорией функций, которая менее всего уклоняется от нуля. По большинству из этих перечисленных разделов Марков сумел добиться важнейших результатов.
Мысли своего непосредственного учителя Чебышева Марков в основном перенял, начав заниматься решение проблем, обозначенных в его трудах. Ключевые и классические работы Маркова и Чебышева были посвящены предельным величинам интегралов, составляли ключевые основы теорий моментов и экстремальных задач в области функциональных пространств.
Ученый также работал над теорией чисел. При этом конкретных публикаций у него всего около пятнадцати. Но каждая из них имеет определяющее значение для этой теории в целом. К ним в первую очередь необходимо отнести магистерскую диссертацию, посвященную бинарным квадратичным формам положительного определителя, которая увидела свет в 1880 году.
Эта теория примыкала к исследованиям Золотарева и Коркина, ее высоко ценил Чебышев, многим настоятельно советуя ее изучить. Эта диссертация была посвящена проблемам арифметических минимумов, которые применяются в неопределенных бинарных квадратичных формах. В большинстве своих последующих статей Марков рассматривал эту проблему как неопределенные тернарные и кватернарные квадратичные формы. Результаты работы и идеи самого Маркова оказали огромное влияние на развитие теории чисел в целом.
Конфликт с церковью
В самом начале XX столетия у Маркова возник конфликт с Русской православной церковью. В 1901 году ученый-математик выступал с резкой критикой решения Синода, который отлучил Льва Толстого от церкви.
В 1912 году Марков отправил письмо в Святейший синод при Русской православной церкви, в котором самостоятельно попросил отлучить его от церкви. Академик, в частности, писал, что не видит никакой существенной разницы между мощами и иконами, а также идолами и богами, с одной стороны, а с другой стороны, не сочувствует ни одной мировой религии, каждая из которых, также как и православие, поддерживается исключительно огнем и мечом.
В феврале синод рассмотрел обращение Маркова, поручив петербургскому митрополиту вразумить академика. Но герой нашей статьи отказался даже от встречи со священником. Он официально заявил, что считает это пустой тратой своего времени.
Тогда митрополит Антоний подписал резолюцию, в которой призвал всех официально считать Маркова отпавшим от православия и подлежащим незамедлительному исключению из списков православных лиц.
В сентябре 1912 года духовная консистория Санкт-Петербурга официально утвердила это решение. В очередной раз дело было рассмотрено синодом в октябре. Служители православной церкви постановили известить об этом случае его непосредственных руководителей, чиновников в министерстве народного просвещения. После этого они затребовали подробные сведения о его родителях, дате и месте крещения. В ответ на это Марков отказался предоставлять эти сведения, из-за чего было решено обратиться за ними в Академию наук. Однако в ней ответили, что не располагают подобной информацией. Такой же ответ пришел из Петербургского университета и полиции.
Если перечислять основные работы Маркова, то необходимо упомянуть такие труды, как "Исчисление вероятностей", "Избранные труды по теории непрерывных дробей и теории функций, наименее уклоняющиеся от нуля", "Избранные труды. Теория чисел. Теория вероятностей".
Марков был весьма разносторонним и образованным человеком, у него было много увлечений, о которых знали многие его друзья, знакомые и коллеги. В первую очередь, Андрей Андреевич был заядлым шахматистом. Он участвовал в большом количестве турниров по переписке. В основном, это были турниры и отдельные матчи, которые организовывались под эгидой всевозможных печатных изданий. Марков занимался шахматной композицией, близко дружил с Чигориным, они даже были спарринг-партнерами. Между прочим, к удовольствию для будущего академика, их встреча завершилась со счетом 1,5:2,5. Марков сумел выиграть одну партию, следующую свел вничью, только после этого Чигорин одержал две победы подряд, играя белыми фигурами. Если оценивать его успехи в шахматах по современным меркам, то становится очевидным, что Марков играл в шахматы на уровне современного мастера спорта.
Всего в шахматном архиве ученого-математика содержится около полутора тысяч писем. Особенную ценность представляет архив его переписки с сыном. Частично материалы из этого архива публиковались при непосредственном содействии Романова и Гродзенского.
Марков-младший
Андрей Андреевич Марков-младший родился в 1903 году. Он появился на свет в Санкт-Петербурге. Андрей Андреевич, которому посвящена первая часть этой статьи, был его отцом. Сын пошел по его стопам, но уже не в царской России, а в Советском Союзе, став одним из самых известных советских математиков. Считается, что именно он стал основоположников отечественной школы конструктивной математики. В биографии Андрея Андреевич Маркова-младшего, детство которого прошло в Санкт-Петербурге, большую роль сыграло воспитание, которое дал ему отец, и образование, которое избрал сам юноша. Все это оказало непосредственное влияние на будущее Маркова-младшего.
Андрей Андреевич Марков-младший стал выпускником Восьмой Петроградской гимназии в 1919 году. В 1924 году стал выпускником Ленинградского государственного университета, отправившись учиться в аспирантуру при Астрономическом институте Ленинграда.
Рассказывая кратко биографию А. А. Маркова-младшего, нужно обязательно упомянуть, что ученую степень доктора физико-математических наук была ему присвоена в 1935 году без официальной защиты диссертации, настолько уже в то время ценились его труды и достижения. В 1953 году произошло важное событие в биографии Андрея Андреевича Маркова-младшего. Кратко этот факт обязательно стоит упомянуть. Он стал членом Академии наук Советского Союза. Параллельно в том же году стал членом КПСС.
Научная карьера
Внес большой вклад в информатику Андрей Андреевич Марков. Его же трудовая и научная карьера развивалась так. В 1933 году он начал работать в Ленинградском университете, в 1936 году получил там должность профессора. Затем до 1942 года, а также с 1943-го по 1953 годы заведовал кафедрой геометрии. При этом чуть меньше года провел в блокадном Ленинграде, который оккупировали фашисты во время Великой Отечественной войны.
С 1959 по 1979 годы Марков заведовал кафедрой математической логики в Московском государственном университете. Параллельно начал работать в институте математики имени Стеклова Академии наук Советского Союза. В этом заведении он прослужил вплоть до 1972 года.
Успехи в информатике
После войны открывается новая страница в биографии Андрея Андреевича Маркова-младшего. На базе вычислительного центра, который работает при Академии наук Советского Союза, он создает настоящую лабораторию логики и структуры машин, которой лично руководит более двух десятилетий.
Рассказывая кратко о самом важном в биографии А. А. Маркова-младшего, нужно отметить, что работа именно в этой лаборатории оказала влияние на всю его дальнейшую карьеру.
Хорошо известна общественная и политическая позиция Маркова по так называемому "Письму 99". Это коллективное обращение, которое в 1968 году подписали ряд знаменитых советских математиков, стремясь защитить своего коллегу Александра Есенина-Вольпина. Последнего принудительно отправили в психиатрическую лечебницу из-за того, что он вел диссидентскую деятельность. Письмо стало важным событием не только в жизни видных деятелей советской математики, но и в отечественной истории правозащитного движения. Марков это письмо подписал вместе с другими знаменитыми деятелями науки.
Примечательно, что это письмо стало важной вехой во взаимоотношении между властью и советским математическим сообществом. Многие из тех, кто его решился подписать, были подвергнуты репрессиям. Как минимум, подписанты лишались работы или завидных привилегий. Из-за этого письма произошла смена руководителей советского образования и математической науки. И все же на Маркове его подпись, поставленная под письмом, сильно не отразилась, в отличие от многих других.
Сам Есенин-Вольпин, который, кстати, был сыном Сергея Есенина, в 1972 году эмигрировал в США, на чем настояли и советские власти. Он умер в Бостоне только в 2016 году.
Исследовательская работа
Наибольший вклад в советскую информатику внес Андрей Андреевич Марков. При этом основные его труды посвящены топологии, теории алгоритмов, теории динамических систем, конструктивной математике и теории алгоритмов.
В частности, Андрею Андреевичу Маркову удалось доказать неразрешимость проблемы равенства в ассоциативных системах, к такому выводу он пришел в 1947 году. В 1958 вывел ключевые проблемы гомеоморфии и топологии, а также стал основателем и создателем школы конструктивной логики и математики в Советском Союзе. Именно его авторству принадлежит термин нормального алгоритма.
Выдающимся математиком был ученик Чебышева Андрей Андреевич Марков (1856—1922).
Продолжая дело своего учителя, Марков установил наиболее общие условия, при которых выполняется закон больших чисел. Дав ответ на вопрос, когда и где можно применять этот закон, Марков широко распахнул дверь перед теорией вероятностей в естествознание и технику.
Андрей Андреевич Марков.
Огромным достижением математической мысли была работа Маркова, посвященная центральной, предельной теореме теории вероятностей. Эта теорема была сформулирована Чебышевым. Великий математик начал работать над доказательством теоремы, но довести свою работу до конца не успел.
Центральная теорема теории вероятностей, намеченная Чебышевым и доказанная Марковым, применяется, например, для составления таблиц артиллерийской стрельбы.
Блестяще завершив исследования, начатые Чебышевым, Марков дал великолепное в своей ясности и безупречности доказательство этой теоремы, решающей вопрос о том, как часто какая-либо случайная величина принимает некоторое определенное значение. Он установил, что вероятность значений, принимаемых этой величиной, подчиняется строгому закону.
Центральная теорема, как и закон больших чисел, имеет фундаментальное значение в теории вероятностей.
Пользуясь результатами Маркова, физики с безукоризненной точностью могут вычислить, какая часть бесчисленного роя молекул обладает той или иной скоростью. Эта теорема лежит в основе расчетов таблиц для артиллерийской стрельбы. Выведенный из этой теоремы закон рассеивания снарядов дает возможность уверенно вести стрельбу, невзирая на множество случайных причин, отклоняющих снаряд от цели.
Развивая теорию вероятностей, Марков приступил к математическому истолкованию и значительно более сложных явлений.
В некоторых процессах последующие состояния определенной системы не могут считаться независимыми от ее предыдущих состояний. Такая взаимосвязь сплошь и рядом наблюдается в технике и естествознании. Нельзя, например, численность колонии бактерий в какой-нибудь момент считать независимой от ее численности в предшествующее время. Марков дал математическую теорию, способную описать такие сложные явления.
Теория Маркова исключительно широко применяется в физике, — она служит могучим средством расчета атомных и молекулярных процессов.
Труды русских математиков явились прочным фундаментом, на котором стала развиваться теория вероятностей.
Успехи теории вероятностей оказались столь разительны, что ученые принялись разрабатывать ее самым широким образом.
Читайте также: