Специальные формы описания алгоритмов




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

Алгоритмически неразрешимые проблемы (определение алгоритмически разрешимых и неразрешимых задач, понятия записи алгоритма и самоприменимости, теорема об алгоритмической неразрешимости проблемы самоприменимости)

Алгоритмы обрабатывают определённые объекты („входные") и выдают объекты („выходные") в качестве результатов. Объекты могу быть конкретными, как, например, десятичное число в случае A. Объекты могут быть абстрактными, как, скажем, натуральные числа (для которых могут использоваться разнообразные эквивалентные системы представления) в случае B — для описанного там алгоритма совершенно несущественно, записываются числа в десятичной или двоичной системе счисления или даже римскими цифрами, свойства делимости от этого не меняются. В теоретических исследованиях предпочитают опираться на алгоритмы, которые работают, например, только с натуральными числами (Гёдель), либо только с цепочками знаков (Марков). С практической точки зрения нет никакой пользы или нужды в таких ограничениях, допустимы какие угодно множества объектов, если только можно аккуратно определить их свойства. Разве лишь, поскольку приходится привлекать разбор отдельных случаев, необходимо включить в множество объектов по крайней мере значения истинности «истина» и «ложь».

В зависимости от того, какие допускаются классы объектов (соответствующие операции), приходят к различным классам алгоритмов.

Алгоритмы Маркова

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

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

Операция замены: «Если а является подсловом заданного слова х, то заменить это подслово на Ь. В случае, если подслово а встречается в слове х несколько раз, словом Ь заменяется то из них, которое стоит в самой левой позиции». (*)

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

Такого рода алгоритмы называют алгоритмами Маркова по имени советского математика А. А. Маркова, который впервые описал их (в 1951 г.); сам Марков называл их „нормальными алгорифмами". Алгоритмы Маркова считают уточнением понятия алгоритма, достигаемым за счёт использования специальной формы описания.

В качестве примера приведем алгоритм Маркова, который по заданному двоичному слову строит производное двоичное слово. Этот алгоритм использует вспомогательные знаки ‑ „челноки" и содержит следующие продукции:

Останавливающие продукции отмечены точкой. На рисунке ниже показано применение алгоритма к слову 001101110101.

α001101110101

0α01101110101

00α1101110101

001β101110101

0010β01110101

00101α1110101

001011β110101

0010110β10101

00101100β0101

001011001α101

0010110011β01

00101100111α1

001011001111β

Благодаря компактным правилам замены алгоритмы Маркова представляют собой мощное средство описания: на сегодня нет таких алгоритмов над последовательностями знаков, для которых не существовало бы алгоритма Маркова, выполняющего ту же самую обработку сообщений. Описания, сформулированные в виде алгоритмов Маркова, часто оказываются весьма короткими по сравнению с другими, менее „рафинированными" формами описания. Заметим, что элементарную для алгоритмов Маркова операцию замены (*) можно также рассматривать как сложную, рекурсивно определяемую операцию над последовательностями знаков. Поэтому понятие элементарности всегда относительно.

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

Собственно действия с числами в цифровой записи относятся, таким образом, к классу алгоритмов над цепочками знаков. Здесь в арифметике мы обнаруживаем исторические корни слова algorismo; еще Лейбниц говорил об „алгоритме умножения".

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

Тренажеры (эмуляторы) здесь:

https://kpolyakov.spb.ru/prog/nma.htm

https://cmcmsu.no-ip.info/1course/alg.schema.nam.htm



Поделиться:




Поиск по сайту

©2015-2024 poisk-ru.ru
Все права принадлежать их авторам. Данный сайт не претендует на авторства, а предоставляет бесплатное использование.
Дата создания страницы: 2017-06-30 Нарушение авторских прав и Нарушение персональных данных


Поиск по сайту: