44) Нормальные алгорифмы Маркова

Марков А.А– советский математик, занимавшийся математической логикой и конструктивной математикой. Разработал так называемые нормальные алгорифмы основанные на полусистемах Туэ (ассоциативное исчисление, разработанное шведским математиком Акселем Туэ). Задаётся конечный алфавит A и конечное множество подстановок P. Работа алгоритма состоит из выполнения двух операторов: распознавателей и подстановки. Оператор-распознаватель находит вхождение левой части подстановки в слово I, а оператор-подстановка заменяет это вхождение на правую часть подстановки.

Нормальный алгорифм останавливает процесс в случаях:

1. Подходящая подстановка не найдна.

1. Применена последняя подстановка.

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

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

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

45) Универсальная абстрактная машина и проблема самоприменимости в теории алгоритмов

Алгоритмы строятся из команд. А из алгоритмов можно строить более сложные алгоритмы

1. Композиция C алгоритмов А _,В:

C=А _В

С = В (А (Х)), Х – исходные данные.

Таким образом, приписывается программа к программе

2) Ветвление:

А, В, С,D.

Запускается алгоритм А.

Если результат применения А (Х) соответствует заданному условию, то D(Х) = B(Х). Иначе, D(Х) = С (Х).

3. Итерация (повторение):

Повторение алгоритма А, пока алгоритм В не укажет, что пора заканчивать. универсальная машина U выполняет, как и современная ЭВМ любую программу. Машина читает произвольную запись программы Р. и применяет ее к заданному слову. Исходные данные таким образом, это запись программы Р и исходные данные Х., (Р) – запись программы, Х – исходные данные (на ленте)

(Р) * Х, где * - разделитель, символ не используемый в Р.Тогда результат записывается как U((P)*X) = P(X).

Один из способов построения универсальной машины – использование геделевской нумерации алгоритмов

Проблема самоприменимости

заключается в том чтобы по заданной программе Р для абстрактной машины узнать, применима ли она к своей собственной записи Р((Р)), где (Р) – запись программы (О.Б. Лупанов)

Суть: существует ли такая машина, которая по записи любой др. машины и определяет самоприменимость др. машины. Применима -1, не применима – 0. Проблема самоприменимости алгоритмически не разрешима. Не существует универсального алгоритма.

46) Сложность алгоритмов

Сложность алгоритма отражает затраты, требуемые для его работы.

Это функция, которая каждой входной длине n ставит в соответствие минимальное время, затрачиваемое алгоритмом на решение всех однотипных индивидуальных задач этой длины

Сложностью задачи называется сложность наилучшего алгоритма.

Полиномиальным алгоритмом- называется алгоритм, у которого временная сложность равна О (Р(n)), где Р(n) - некоторая полиномиальная функция от входной длины n. Алгоритмы, для временной сложности которых не существует такой оценки, называются экспоненциальными.

Задача считается труднорешаемой, если для нее не существует разрешающего полиномиального алгоритма. Итак, основные классы сложности таковы: а) Полиномиальная сложность. P(n) – полином от n.O(P(n)) – сложность задач класса класса Р.

б) Экспоненциальная сложность.

O(xⁿ) – класс Е – экспоненциальный

в) NP сложные задачи

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