Вопрос: нормальные алгоритмы Маркова

А.А. Марков разработал строгую теорию определенного класса алгоритмов, которые называются нормальными алгорифмами Маркова. Для них исходными данными и результатами являются высказывания, записанные в виде слов, принадлежащих некоторому алгоритму А. Если алфавит А входит во множество В, но АВ, то говорят, что В – расширение алфавита А. Пусть RA и существует некоторое PR, в этом случае говорят, что Р – это вхождение подстроки в высказывание R. Марковская подстановка – это замена первого вхождения подслова Р в слове R на слово Q: (P, Q)=PQ.

Если PR, то говорят, что Марковская подстановка не применима к слову R. Частными случаями Марковских подстановок являются пустые вхождения:

( ,Q), (P, ), ( , ). Здесь пустые слова в скобках эквивалентны .

Пример 1:

Если R=192375923A, тогда

(923, 0000)R=1000075923

Пример 2:

R=паровоз

(овоз, _)R=пар_

Пример 3:

R=книга

( , ) R=книга

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

Вопрос: свойства алгоритмов:

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

2. Массовость. Алгоритм должен решать не одну конкретную задачу (ограниченное множество неизменных исходных данных), а серию однотипных задач. Т. е. множество различных исходных данных порождает различные результаты. Массовость алгоритма – это допустимость всех объектов соответствующего класса, а не допустимость какого-либо их количества.

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

4. Потенциальная осуществимость алгоритма. Говорят, что алгоритм применим к допустимому исходному данному, если с его помощью можно получить искомый результат. Иначе, хотя исходное данное и допустимо, но алгоритм к нему не применим. Неприменимость алгоритма к допустимому исходному данному заключается в том, что алгоритмический процесс становится бесконечным, либо безрезультатно обрывается на каком-либо шаге. Отвлекаясь от реальной ограниченности времени и ресурсов, необходимых для выполнения алгоритма, требуют лишь того, чтобы алгоритмический процесс заканчивался после конечного числа шагов, и чтобы на каждом шаге не было препятствий для его выполнения. В этом случае считают, что алгоритм применим к исходному данному и потенциально (а не реально) осуществим.

5. Понятность. Алгоритм понятен для исполнителя, если он знает, как его выполнять (know how). Возникает вопрос: что именно должен знать исполнитель? Свойство понятности можно истолковать как наличие алгоритма, определяющего процесс выполнения заданного алгоритма. В этом случае исполнителями могут быть любые объекты. Тогда исполнителю должен быть известен алгоритм (руководство к действию) для решения всех других алгоритмов, соответствующих исполнителю. Таким образом, возникает рекурсивное определение алгоритма, например, любая операционная система – это алгоритм алгоритмов.

6. Корректность. Алгоритм корректен, если выполняются три условия:

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

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

Результат работы алгоритма устойчив к вычислительной погрешности (свойство обусловленности).

Если хоть одно из этих условий не выполняется, то алгоритм считается некорректным. Вычислительная погрешность (машинная точность) возникает из-за ограниченной разрядной сетки ЭВМ и операций округления. Обусловленность алгоритма показывает чувствительность результата работы алгоритма к малым, но неизбежным ошибкам вычислений. Алгоритм хорошо обусловлен, если малые вычислительные погрешности приводят к малой относительной погрешности результата.

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

Вопрос: истинность и выполнимость формул:

Высказывания с использованием пропозициональных переменных и логических связок представляются формулами. Семантика формул определяется их свойством быть истинными или ложными, то есть принимать значение T(true) - истина, или F(false) – ложь. Формула выполнима, если она допускает хотя бы одну модель, т.е. ее можно интерпретировать со значением T.

Формула невыполнима, если она не имеет ни одной модели, то есть, при всех интерпретациях является ложной. Например, формула (p ) невыполнима.

Вопрос: гипотеза Черча

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

Каков бы ни был алгоритм, перерабатывающий наборы целых неотрицательных чисел в целые неотрицательные числа, существует алгоритм, сопутствующий рекурсивной функции, который ему эквивалентен.

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