Презентация, доклад по информатике Нормальный алгоритм Маркова

алгоритмов

Пример 2

Санкт-Петербург

Дата смерти :11 октября 1979 (76 лет)

Научная сфера :математика

Место работы :ЛГУ; МГУ; ВЦ АН СССР;
Математический институт им. В. А. Стеклова АН СССР

Учёная степень : доктор физико-математических наук

Известен как : основоположник советской школы конструктивной математики

М

А. Маркова, основоположник советской школы конструктивной математики.

Окончил Восьмую Петроградскую гимназию в 1919 году; Ленинградский государственный университет в 1924 году; аспирантуру в Астрономическом институте в Ленинграде в 1928 году.
Учёная степень доктора физико-математических наук присвоена без защиты диссертации в 1935 году. Член-корреспондент АН СССР с 1953 года, в том же году вступил в КПСС.
В 1933—1955 годах работал в Ленинградском университете (с 1936 г. — профессор): с 1936 по 1942 год и с 1943 по 1953 год — заведующий кафедрой геометрии. До июля 1942 года находился в блокадном Ленинграде.
С 1959 по 1979 год — заведующий кафедрой математической логики Московского государственного университета.
Одновременно в 1939—1972 работал в Математическом институте имени Стеклова АН СССР.
В 1950-х годах создал в Вычислительном Центре АН СССР лабораторию математической логики и структуры машин, которой руководил около двадцати лет.

М

теории алгоритмов и конструктивной математике.
Доказал неразрешимость проблемы равенства в ассоциативных системах (1947), проблемы гомеоморфии в топологии (1958), создал школу конструктивной математики и логики в СССР, автор понятия нормального алгоритма.

Награды

Орден «Знак Почёта» (1945)
Орден Ленина (1954)
Орден Трудового Красного Знамени (1963)
Медаль «За доблестный труд в Великой Отечественной войне 1941—1945 гг.» (1945)
Медаль «За оборону Ленинграда» (1946)
Премия имени П. Л. Чебышёва АН СССР (1969)

М

алгоритма (другой известный способ — машина Тьюринга). Понятие нормального алгоритма введено А. А. Марковым (младшим) в конце 1940-х годов в работах по неразрешимости некоторых проблем теории ассоциативных вычислений. Традиционное написание и произношение слова «алгорифм» в этом термине также восходит к его автору, многие годы читавшему курс математической логики на механико-математическом факультете МГУ.
Нормальный алгоритм описывает метод переписывания строк, похожий по способу задания на формальные грамматики. НАМ является Тьюринг-полным языком, что делает его по выразительной силе эквивалентным машине Тьюринга и, следовательно, современным языкам программирования. На основе НАМ был создан функциональный язык программирования Рефал.

М

нормальных алгоритмов Маркова. Сначала обратим внимание на одно обстоятельство, связанное с работой любого НАМ: нужно либо вводить дополнительное правило остановки работы нормального алгоритма (иначе в примере увеличения числа на 1 алгоритм продолжит работу и снова будет увеличивать полученный результат еще на 1 и т.д. неограниченное число раз), либо перед началом работы нормального алгоритма добавлять к входной строке специальные символы, отличные от других символов строки, которые учитываются подстановками алгоритма в начале его работы и которые удаляются в конце работы алгоритма. Мы будем придерживаться второго способа, как и одна из наиболее успешных реализаций нормальных алгоритмов Маркова в виде языка программирования Рефал. В качестве добавляемого символа возьмем символ "@".

М

почти всегда необходимо увеличить последнюю цифру на 1, а последняя цифра отличается тем, что после нее идет символ "@". Поэтому первыми подстановками должны быть подстановки типа

пример

Но если это цифра 9, то ее нужно заменить 0 и увеличение на 1 перенести в предыдущий разряд. Этому отвечает подстановка

Наконец, если число начинается с 9 и перед этой цифрой нужно поставить 1, то этому будет отвечать подстановка

а если это не так, то в конце работы алгоритма символы @ надо стереть, что выполнит подстановка

С М

работу построенного алгоритма для чисел 79 и 99:

Аналогичным образом разрабатывается нормальный алгоритм Маркова для уменьшения числа на 1

Н М