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

В 1996 году выходит «Теория алгорифмов» совместно с М. Н. Нагорным в 2002 году под редакцией М.Н. Нагорного опубликованы избранные труды А.А. Маркова.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

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

В середине прошлого века А. А. Марков ввел понятие нормального алгоритма (алгорифма) с целью уточнения понятия «алгоритм», что позволяет решать задачи по определению алгоритмически неразрешимых проблем. В отличие от машин Тьюринга и Поста, нормальные алгоритмы Маркова – это алгоритм, который не связан ни с каким «аппаратным обеспечением» (лентой, кареткой и т.п.). Нормальный алгоритм Маркова преобразует одно слово (цепочку символов некоторого алфавита) в другое и задается алфавитом и системой подстановок. Заметьте, что в жизни мы нередко применяем такие замены. Например, при умножении в столбик мы не вычисляем каждый раз произведение 7 × 8, а просто помним, что оно равно 56. Позже это понятие получило название нормального алгоритма Маркова. Идеи этого алгоритма  положены в основу большой группы языков программирования, получивших название языки логического программирования.

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

  Для формализации понятия алгоритма российский математик А. А. Марков предложил использовать ассоциативные исчисления. Рассмотрим некоторые понятия ассоциативного исчисления.

Пусть имеется алфавит (конечный набор различных символов). Составляющие его символы будем называть буквами. Любая конечная последовательность букв алфавита (линейный их ряд) называется словом в этом алфавите.

  Рассмотрим два слова N и М в некотором алфавите А. Если N является частью М, то говорят, что N входит в М.

Зададим в некотором алфавите конечную систему подстановок N - М, S - Т, ... , где N, М, S, Т, ... - слова в этом алфавите. Любую подстановку N-M можно применить к некоторому слову К следующим способом: если в К имеется одно или несколько вхождений слова N, то любое из них может быть заменено словом М, и, наоборот, если имеется вхождение М, то его можно заменить словом N.

    Например: построим алгоритм Маркова, заменив в алфавите А={a, b, c} все буквы а на с. Используем символ α для расширения алфавита А.

В = α . Схема Z нормального алгоритма будет иметь следующий вид:

 

aacbab → αaacbab → cαacbab →ccαcbab → cccbαbab → cccbαab →cccbcbα →cccbcb  ⁴

Совокупность всех слов в  алфавите вместе с системой допустимых подстановок называют ассоциативным исчислением. Чтобы задать ассоциативное исчисление, достаточно задать алфавит и систему подстановок.

Слова P1 и Р2 в некотором  ассоциативном исчислении называются смежными, если одно из них может  быть преобразовано в другое однократным  применением допустимой подстановки. Последовательность слов Р, P1, Р2,..., М  называется дедуктивной цепочкой, ведущей  от слова Р к слову М, если каждое из двух рядом стоящих слов этой цепочки - смежное.

Слова Р и М называют эквивалентными, если существует цепочка  от Р к М и обратно.

Пример:

Алфавит  Подстановки

{а, b, с, d, е} ас - сa,

ad - da;   eca - ae

bc - cb;   eda - be

bd - db;   edb - be

Слова abcde и acbde - смежные (подстановка bc - cb). Слова abcde - cadbe эквивалентны.

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

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

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

Такой набор предписаний  вместе с алфавитом А и набором  подстановок В определяют нормальный алгоритм. Процесс останавливается  только в двух случаях: 1) когда подходящая подстановка не найдена; 2) когда  применена последняя подстановка из их набора. Различные нормальные алгоритмы отличаются друг от друга алфавитами и системами подстановок.

Приведем пример нормального  алгоритма, описывающего сложение натуральных чисел (представленных наборами единиц):

Алфавит:  Система подстановок В:

А = (+, 1)   1 + → + 1

+ 1 → 1

1 → 1

Слово Р: 11+11+111

Последовательная переработка  слова Р с помощью нормального  алгоритма Маркова проходит через  следующие этапы:

Р = 11 + 11 + 111   Р5 = + 1 + 111111

Р1 = 1 + 111 + 111  Р6 = ++ 1111111

Р2 = + 1111 + 111   Р7 = + 1111111

Р3 = + 111 + 1111   Р8 = 1111111

Р4 = + 11 + 11111   Р9 = 1111111

Нормальный алгоритм Маркова  можно рассматривать как  универсальную  форму задания любого алгоритма. Универсальность нормальных алгоритмов декларируется принципом нормализации:

для любого алгоритма в произвольном конечном алфавите А можно построить эквивалентный ему нормальный алгоритм над алфавитом А.

Разъясним последнее утверждение. В некоторых случаях не удается  построить нормальный алгоритм, эквивалентный  данному в алфавите А, если использовать в подстановках алгоритма только буквы этого алфавита. Однако, можно  построить требуемый нормальный алгоритм, производя расширение алфавита А (добавляя к нему некоторое число  новых букв). В этом случае говорят, что построенный алгоритм является алгоритмом над алфавитом А, хотя он будет применяться лишь к словам в исходном алфавите A.

Если алгоритм N задан  в некотором расширении алфавита А, то говорят, что N есть нормальный алгоритм над алфавитом А.

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

Нормальные алгоритмы  Маркова являются не только средством  теоретических построений, но и основой  специализированного языка программирования, применяемого как язык символьных преобразований при разработке систем искусственного интеллекта. Это один из немногих языков, разработанных в России и получивших известность во всем мире.

Любой нормальный алгоритм эквивалентен некоторой  машине Тьюринга, и наоборот – любая машина Тьюринга эквивалентна некоторому нормальному алгоритму.

Вариант тезиса Чёрча – Тьюринга, сформулированный применительно к нормальным алгоритмам, принято называть «принципом нормализации».

Нормальные алгоритмы  оказались удобным средством  для построения многих разделов конструктивной математики. Кроме того, заложенные в определении нормального алгоритма идеи используются в ряде ориентированных на обработку символьной информации языков программирования — например, в языке Рефал.

 

 

 

 

 

 

 

 

 

 

 

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

В 1950–х годах А. А. Марков выдвинул гипотезу, получившую название «принцип нормализации Маркова».

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

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

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

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

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Заключение

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

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

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

 

 

 

 

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

1. Графы и алгоритмы. Структуры данных. Модели вычислений: учебник /      Алексеев В. Е. , Таланов В. А.  – М: Бином. Лаборатория знаний,2009. –320 с.

2. Гуц А.К., Математическая  логика и теория алгоритмов: Учебное  пособие для студентов – 2003.–107с.

3. Игошин В. И. Математическая логика и теория алгоритмов: Учебное пособие для студ. высш. учеб. заведений – М.: Издательский центр «Академия»,2004. –448с.

4. История отечественной  математики: Энциклопедия, т.3/ Штокало И.З. , Юшкевич А.П., Боголюбов А.П. – М: Академия наук СССР, 1968.– 729с.

5. Судьбы творцов российской  науки: Сборник/ Сурин А. В.  и Панов М. И., М.: Эдиториал УРСС, 2002.– 352 с.

6.  Теория алгоритмов: Учебник / Матрос А. М. , Поднебесова Г. Б.  – М.: Бином. Лаборатория знаний, 2008.–202с.

7.  Биографии Знаменитых Людей : http://biography-peoples.ru/index.php/m 

 

 

 

 

 

 

 

 

 

¹ Биографии Знаменитых Людей: http://biography-peoples.ru

² Судьбы творцов российской науки: Сборник/ Сурин А. В.  и Панов М. И., М.: Эдиториал УРСС, 2002.– 174 с.

³ История отечественной математики: Энциклопедия, т.3/ Штокало И.З. , Юшкевич А.П., Боголюбов А.П. – М: Академия наук СССР, 1968.– 540 с.

⁴ Теория алгоритмов: Учебник / Матрос А. М. , Поднебесова Г. Б.  – М.: Бином. Лаборатория знаний, 2008.–202с.