24. Предмет изуч-я теор алг-мов. Алг-тм, его св-ва, необходим уточ-я пон-я алг-ма. Универсаль-е алг-ие модели.

Алг-м – фундаментальное понятие. Алг-м – точное и понятное предписание о том, какие действия и в каком порядке н. выполнить, чтобы решить любую задачу из класса однотипных задач (это интуитивное понятие). Св-ва алг-в: 1.Точное предпис-е - (определ-ть или детерминир-ть) последовательность шагов д.б. однозначно осуществима и не д. содержать никаких свободно приним. решений. 2.Понятное предписание (понятность) - предписание д.б.сформулировано на понятном исполнителю языке и исполнитель д. уметь исполнять данное предписание. Система команд исполнителя – набор действий, к-е м. исполн. данный исполнитель. 3.Решить любую задачу (массовость). Предписание д. им. единый метод позволяющ по любым конкретным данным из множества всех возможных исход. знач. получ исход результат. 4. Результативность Решить задачу, т.е за конечное число шагов получ ответ или инфо о том, что реш нет. 5. Дискретность Шаги решения зад-ч д б дискретны, т.е кажд шаг четко ограничен от другого. За кажд шагом после помледнего д. следовать очередной шаг и м/д ними никаких действий.

универс-е. алгор-е модели – алг, к-е позволяют описывать любой алгоритм и простые модели, т.е те кот-е облад минимумом необходимых средств. Поиск таких моделей происходит в 3х направлениях: 1.Теория рекурсивных ф-ий. Строится мат модель, на арифметизации алгор построена теория алгоритм моделей. 2.Абстрактные машины: машины Тьюринга, Поста. Для того, чтобы алгор восприним однозначно, а каждый шаг считать элементар и выполнимым, он д.б. представлен так, что его могла выполнить машина, чем проще машина и струк-ра ее действия, тем убедительнее выглядит утверждение.3. Норм-е алг Маркова близки ко 2-му. Здесь механизм не влияет на построение самой модели.

Понятие вычислимой функции.

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

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

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

Простейшие функции: zero(x)=0 (одноместная нулевая), suc(x)=x+1 (следование), I_iⁿ(x₁..x_n)=x_i (n-местная i-я проекция) I₁¹(x₁)=x₁ (идентичность).

Элементарные операции: - суперпозиция, или композиция; примитивная рекурсия

Машина Тюринга

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

Лента – бесконечна, разделена на ячейки, в каждой из к-х м находиться1 символ или пробел. А={а0,а1,…аn} – внешний алфавит.

_ - этот пробел.

Считывающая, записывающая головка м двиг влево, вправо на 1 ячейку. В какой-то момент времени она обозрев 1 ячейку. Исходное состояние машины Тьюринга включ в себя исходное состояние счит, записыв головки и исходное сост ленты, на кй занесено входное слово. Слово состоит из букв внешнего алфавита и ограничено справа и слева пробелами. Q={q0,q1…qk} – состоояния в которых м находиться считывающая головка внутреннее состояние мамшины, в 1 из них (внутренний алфавит). Состояние машины х-ся парой (a_i,q_i) a_i – обозреваемый символ внеш алф, q_i-внутр сос.в кот-м нах-ся машина Машина м выполнять совокупность действий: 1)М записать в кажд мом времени в зависимости от пары (a_i,q_j) новый символ в обозреваемую ячейку 2)м выполнитьь 1 из 3 команд(сдвиг вправо, влево, на месте) 3) считывающая головка переход в новое внутреннее состояние qp

Богатство возможностей и конструкций проявл в том, что если какие-то алг А и В реализ машиной Тьюринга, то м составить разл композицию этих алгоритмов в виде соответств машин Тьюринга

Определение нормального алгоритма Маркова.

1947-ААМарков предлож свою модель (алгоритмич схему), к-ую. назвали нормальным алгоритмом. Здесь нет понятия ленты. Эта схемам представляет собой преобразование входного слова, отвлеченных от машины механизмов. Норм алг – упорядоченный набор пар слов, соед м/д собой стрелками 2х видов

Любая пара слов представляет формулу подстановки для замены подслов в преобразуемом слове.

А₁ { } В1

А₂ { } В₂

Общий вид:

Аn { } В_n, Где Аn – подслово

в преобраз слове, а Вn – то на что нужно заменить, в {} нарисована 1 из 2х стрелочек.

Схема нормального алгоритма:

В ыполнение алгор состоит из тактов, кажд такт состоит из поиска 1-ой по порядку формулы. 1й такт начин с проверки применимости первой ф-лы и ее выполнения. Если в исходном слове есть подстрока А1, то она б замен, м оказаться, что А1 в исходном слове несколько, то замене б подлежать первое вхождение, те слева. Если фрагмента А1 нет, то осуществл переход на проверку применимости формулы 2, если она тоже не применима, то на 3 и т д. После выполнения любой формулы следующий такт будет начинаться с проверки применимости 1й формулы. Завершение алгор возможно в 2 случаях: неприменима ни 1 из формул или выполнена завершающая формула со стрелкой:

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

Понятие алгоритмической разрешимости и неразрешимости.Примеры

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

Примеры алг-ки неразрешимых проблем:

1)Десятая проблема Гильберта: существует ли целочисленные решения для любой системы. 2) Существует ли алг. К-й доказывает существует ли доказательство теоремы или нет.3) Проблема остановки (завершит ли программа работу на указанном месте). 4) Алгоритм не самоприменим, если подаваясь на входе он зацикливается.