ЭС: А.А.Марков

МАРКОВ АНДРЕЙ АНДРЕЕВИЧ (9(22).09.1903, Санкт-Петербург – 13.10.1979, Москва), математик.
 
Окончил Ленинградский государственный университет (1924). Доктор физико-математических наук (1935, без защиты диссертации). Профессор (1936).
Член-корреспондент отделения физико-математических наук (секция математики) АН СССР (1953).
 
Заведующий кафедрой математической логики механико-математического факультета (1959–1979).
 
Научная и педагогическая деятельность. В сфере научных интересов топология, топологическая алгебра, теория динамических систем, теория алгорифмов/алгоритмов, математическая логика и конструктивная математика.
Основоположник отечественной школы конструктивной математики. Его первые работы в этом направлении были посвящены построению примера ассоциативной системы с неразрешимой проблемой тождества и примера ассоциативной системы с неразрешимой проблемой односторонней делимости (1947).
В области математической логики решил две знаменитые математические проблемы – проблему тождества для конечнопорождённых и конечноопределённых полугрупп (1947, проблема Туэ/Thue) и проблему гомеоморфии в топологии (1958). Создал рабочий аппарат, опирающийся на удачно выбранное им понятие нормальных алгоритмов (алгоритм Маркова), которое широко используется в общей теории алгоритмов и в теоретической кибернетике. Методика, разработанная А.А. Марковым при построении теории нормальных алгоритмов, в значительной степени предвосхитила приёмы структурного программирования и технику верификации программ.
Решил задачу об инверсионной сложности булевых функций и нашёл минимальные контактно-вентильные схемы, реализующие симметрические булевы функции. Заложил основы теории сложности алгоритмов. Развил специальную конструктивную логику, учитывающую специфику конструктивных объектов.
Занимался применением математической логики в теории вычислительных машин. Разработал терминологию для описания работы вычислительных машин. Выполнил важные работы в области криптографии. Наиболее известна «теорема Маркова», которая классифицирует шифры, не распространяющие искажения.
 
С 1943 г. руководил в МГУ научным семинаром по математической логике, а в 1959 г. основал кафедру математической логики, членами которой стали О.Б. Лупанов, П.С. Новиков, В.А. Успенский, С.В. Яблонский, С.А. Яновская.
 
Государственные награды: ордена – Ленина (1954), Трудового Красного Знамени (1963, 1975), «Знак Почёта» (1945), медали – «За доблестный труд в Великой Отечественной войне 1941–1945 гг.» (1945), «За оборону Ленинграда» (1946).
 
Основные труды: «Теория алгорифмов» (1951, 1954; соавт., 1984), «О конструктивной математике» (1962), «О логике конструктивной математики» (1972), «О теории вероятностей и математической статистике. Переписка А.А.Маркова и А.А.Чупрова» (соавт., 1977), учебные пособия «Лекции по математической логике» (соавт., 1973), «Элементы математической логики» (1984).
 
Литература: Нагорный Н.М., Шанин Н.А. А.А.Марков: к 60-летию со дня рождения. Успехи математических наук. 1964, май – июнь. Т. 19. Вып. 3. С. 207–223; А.А.Марков. МИАН имени В.А.Стеклова.