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

Алгоритмы задаются в виде орграфов (граф-схемы)

Есть 2 типа вершин.

1 – распознаватель вхождения (рв) (проверяет, принадлежит ли строка s1 некой другой строке s2)

2 – операторы подстановки. Заменяют некую строку s3 строкой s4 (s3 à s4)

ВХОД
|
|
|
PB1 à ОП1
|
|
|
PB2 à ОП2
|
|
..
Выход

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

Если через некоторое число шагов мы попадаем, то говорят, что алгоритм применим к исходным данным. Иначе алгоритм не применим.

Рекурсивные функции

Функция называется вычислимой, если существует алгоритм, который вычисляет значение этой функции.

1. О(х) == 0

2. S(x) = x+1

3. { Iⁿ_m (x1, x2, ….,xn) = xm, m<=n) – семейство функций

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

S_n^{m (}h, g1….gm)=h(g1(x1,x2….xn), g2(x1….x2)….gm(x1….xn))

Подстановка вместо переменной значение функции другой функциии.

Оператор примитивной рекурсии

R_n(g,h)

F(x1,….xn+1)

G – n

H – n+2

При n+1 аргументе = 0

F(x1,…..xn, 0) = g(x1,…xn)

По аналогии с мат. Индукцией

F(x1,x2…..xn, y+1) = h (x1,…xn, y, f(x1,x2…..xn,y))

Лекция 9

Операторы суммирования и произведения – примитивно-рекурсивные операторы (ПРО)

Ограниченный оператор минимизации

F(x1,…xn,z) = μ y P (x1,…xn,y) = min(y<=z: P(x1,..xn,y), если у сущестувет

(y<=z) z, если нет

Мы ищем самый маленький у, при котором предикат выполняется. Если находится, то ставим его в значение функции

Ограниченный он потому, что проверка происходит только до заданного значения z. А все переменные – целые положительные.

Неограниченный оператор минимизации. Не имеет ограничения (z)

F(x1,…xn) = μ y P (x1,…xn,y) = min(y<=z: P(x1,..xn,y), если у сущестувет

(y<=z) не определено

Опр.

Функция называется частично-рекурсивной, если она получена из примитивно-рекурсивной при помощи оператора минимизации (Неограниченного).

Опр.

Обще-рекурсивная функция – это частично-рекурсивная функция, которая всюду определена.

Тотальные фунции – всюду определенные, но не всегда вычислимые функции.

Тезис Чёрча:

Всякая вычислимая функции является частично-рекурсивной

Теорема Чёрча-Тьюринга:

Функция вычислима на машине Тьюринга ó она частично рекурсивна

Проблема разрешимости

Надо распространить вычислимые функции на любые функции (тригоном., комплекс, вещественные, символьные и т.п.)

Применяется операция Гёделизация

А* - мн-во слов из этих символов

Пусть А – мн-во символов

Функция g: A* -à N
Сопоставляет каждому слову некое число.

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

Алгоритмически неразрешимая проблема – проблема самоприменимости. (напр. Алгоритм сам определяет, зацикливается он или нет)

Лекция 10

F(x,y) = [ sqrt(x) ] = y?

M_y<=zP(x,y)

P(x,y) = (y+1)² > x

Большинство проблем алгоритмически неразрешимы.

Множество М называется разрешимым, если существует некий алгоритм А_М, который для любого элемента А определяет, принадлежит этот элемент множеству М или нет.

Теорема Райса

Любое нетривиальное свойство вычислимой функции не является алгоритмически разрешимым.

Пусть С – класс функций, облад. Неким нетривиальным свойством. Есть функции, которые этим св-вом не обладают.

Не существует алгоритма, который бы по номеру х функции Fx определил бы, принадлежит ли F классу C, или нет. Или мн-во номеров функции, таких, что эта функция принадлежит классу С. Значит, что это алгоритмически не разрешимо.

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

Асимптотики

Ассимптотики - Технология оценки, скорости роста функции в зависимости от длины вектора данных

F(n) – отражает время работы алгоритма от параметра сложности n

F(n) может быть очень сложным выражением, что не удобно для практического использования.

Задача: придумать некую функцию g(n), которая как-то оценивала эту функцию f.

1. F(n) = o(g(n)) (о- малое. Lim |f/g| = 0)
nàinf

2. F(n) = O(g(n)) (О-большое. Lim |f/g| = const)

3. F(n) = θ (g(n)) (ограничение с 2 сторон. с1g(n)<=f(n)<=c2g(n))

Сложность решения задачи – это сложность самого простого алгоритма, решающего эту задачу.

Оценка бывает в

1) Лучшем

2) Худшем

3) Среднем

Существует алгоритмы со сложнотью θ, и не существует алгоритмов с меньшей временной сложностью.

Пространственная сложность – количество памяти, требуемое для решения задачи. Пространственная сложность обычно растет гораздо медленнее, чем временная.

Сложностные классы Р и NP

Полиномиальная сложность – задачи класса P (x^const)

Задачи класса NP – остальные. Сложность выше (e^x, 1000^x)

Классы P и NP называются классами сложности

Опр. Сложностный класс алгоритмов определяет алгоритмы, которые имеют некоторую заданную меру сложности.

Опр. Сложностный класс P - это множество всех задач, которые могут быть решены за полиномиальное время.

Опр. Сложностный класс NP – это множество всех задач, которые можно решить за полиномиальное время недетерминированным алгоритмом(напр. Дерево поиска, рекурсия). (которые можно решить >> чем полиномиальное время)

Так же класс NP – это класс задач, если решение известно, но неизвестно, правильно оно или нет, то это решение можно проверить за полиномиальное время.

Обобщение:

Для класса P решение можно получить за полиномиальное время, а в классе NP – только проверить за полиномиальное время.

Можно сказать, что алгоритм записан на некоем языке. Говорят, что язык L1 сводится за полиномиальное время к языку L2, если существует некая функция (вычислимая за полиномиальное время) такая, что если x ͼ L1 ó f(x) ͼ L2

Задачи на языке L2 более сложная, чем задача на языке L1. Это значит, что решение любой задачи на языке L2 мы можем приспособить для решения задачи языке L1.

Опр. Задача из класса NP называется NP-полная (NPC – NPcomplete), если к ней может быть сведена за полиномиальное время любая задача из класса NP

NPC входит в NP – это наиболее сложные задачи в классе NP

Задача называется NP-трудной, если нам ничего неизвестно, чему она принадлежит.

Свойства классов.

1. Если (L1<=_p L2) ^ (L2 ͼ P) => L1 ͼ P

2. Если (L1<=_p L2) ^ (L2 <=_p L3) => L1 <=_p L3 (транзитивность)

3. Если некая задача из класса NPC вдруг разрешима за полиномиальное время, то P = NP.

4. Если для некой задачи L1 из класса NP существует задача L2 из класса NPC такая, что она сводится к задаче из класса NP, то L1 ͼ NPC

Задача, с которой связано начало теории сложностных классов.

Есть какая-то ДНФ или КНФ. Надо определить, если такой набор значений булевых переменных, при котором на выходе - 0 или 1

Чем больше таких задач известно и решено, тем проще на их основе решить другую, новую задачу.

Предположим, что задача имеет такую размерность и специфику, что их невозможно решить.

1 способ: Разобьем исходное множество по какому-либо признаку на m множеств так, чтобы m<<n и работаем с отдельными, меньшими множествами.

2 способ: Ищется не точное решение, а приближенное.

3 способ: Решение находится с некой вероятностью.

Конкретные алгоритмы

Примеры – численные методы, интернет, экономика, алгоритмы машинной графики.

Алгоритмы поиска, сортировки, решение задач на графах.

Алгоритмы поиска

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