Презентация по информатике на тему "Нормальный алгоритм Маркова " (10-11 кл)

Нормальный алгоритм Маркова

меню  Андрей Андреевич Марков Биография Научный вклад и награды  Нормальный алгоритм Описание Пример 1 Возможности нормальных  алгоритмов Пример 2

Марков, Андрей Андреевич  (младший) Дата рождения :9 (22) сентября 1903 Место рождения : Санкт­Петербург Дата смерти :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. В  этом случае почти всегда необходимо увеличить последнюю цифру на 1, а  последняя цифра отличается тем, что после нее идет символ "@". Поэтому  первыми подстановками должны быть подстановки типа Но если это цифра 9, то ее нужно заменить 0 и увеличение на 1 перенести в  предыдущий разряд. Этому отвечает подстановка Наконец, если число начинается с 9 и перед этой цифрой нужно  поставить 1, то этому будет отвечать подстановка а если это не так, то в конце работы алгоритма символы @ надо стереть,  что выполнит подстановка С           М

Таким образом, мы получаем следующий НАМ увеличения десятичного  числа на 1: Приведем работу построенного алгоритма для чисел 79 и 99: Аналогичным образом разрабатывается нормальный алгоритм Маркова  для уменьшения числа на 1 Н         М