6. Теория алгоритмов - pismo.netnado.ru o_O
Главная
Поиск по ключевым словам:
Похожие работы
6. Теория алгоритмов - страница №1/5

6. Теория алгоритмов




6.1. Понятие алгоритма



Алгоритм - это строгое предписание по выполнению последовательности шагов, приводящее к решению задачи данного типа. Понятие алгоритма относится к понятиям фундаментальным и неопределяемым.
Свойства алгоритмов:

1. Массовость.

2. Пошаговость.

3. Элементарность отдельных шагов (что такое «элементарно» каждый Ватсон понимает по-своему).

4. Детерминированность (точно известно, что нужно делать после каждого шага).

5. Эффективность (алгоритм должен привести к решению за конечное число шагов).


Главное разочарование программистов относительно теории алгоритмов состоит в том, что классическая теория алгоритмов не занимается «правилами построения алгоритмов». На законный вопрос, чем же она тогда занимается, можно достойно ответить: она занимается более важной проблемой – проблемой алгоритмической разрешимости. То есть занимается определением того, возможно ли вообще построить алгоритм для решения задач данного типа.

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

невозможно построить функцию
F(х) = 1, если в числе  есть последовательность из х подряд цифр 5

 0, иначе.


Любопытна в связи с этим теорема:

Теорема: Алгоритмически неразрешимых задач больше, чем алгоритмически разрешимых.

Доказательство: Мощность множества функций (если угодно – задач) даже заведомо ограничено:

f

NN


не менее, чем континуум- 1

Количество же вычислимых функций (если угодно – алгоритмов) счетно, т.е. 0.

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

Таким образом, 1 - 0 = 1



6.2. Конкретизация понятия алгоритма

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

1. -нотация.

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

3. Машины Тьюринга.

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


В связи с этим задача переформулируется следующим образом:

Задача алгоритмически разрешима, если для нее можно построить -нотацию (рекурсивную функцию, машину Тьюринга, нормальный алгорифм Маркова). И наоборот, если невозможно построить -нотацию и т.п., то задача алгоритмически неразрешима. Важно, что все конкретизации алгоритма равнообъемны, то есть одновременно могут или не могут быть построены для исследуемых задач.



6.3. Сложность вычислений

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

алгоритмическая разрешимость еще не означает, что задача может быть реально решена.

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

И здесь вступает в силу «математика практической осуществимости»…Такого рода проблемами занимается теория сложности вычислений.

Рассмотрим для иллюстрации таблицу, в которой четыре столбца, соответствующие «абстрактному» объему исходных данных (n)

Три строки соответствуют различным «функциям сложности вычислений». В таблице приведены времена вычислений в зависимости от объема данных и сложности вычислений (F).




n

F


10

30

50

60

n

10-5 cек

3010-6 cек.

3010-6 cек.

3010-6 cек.

n5

0.1 cек.

24.3 cек.

5.2 мин.

13 мин.

2n

10-3 cек.

17.9 мин.

35.7 лет

366 столетий

Бросается в глаза быстрый рост сложности вычислений в последней строке.

Действительно, с точки зрения теории сложности вычислений, между последним и двумя первыми типами задач пропасть. Первые две задачи относятся к классу задач с полиномиальной сложностью. А последняя – к задачам с экспоненциальной сложностью. Такие задачи называются трудноразрешимыми. Класс этих задач формируется эмпирически и носит название класса NP - полных задач.

Есть какая-то аналогия между проблемами алгоритмической разрешимости и трудноразрешимости. Как из-за невозможности определить понятие алгоритма проблема алгоритмической разрешимости сводится к возможности построения конкретизации, так и трудноразрешимость устанавливается сведением исследуемой задачи к одной из «эталонных» NP - полных задач.



6.4. Машины Тьюринга

Известны случаи построения школьниками железных машин Тьюринга с колесами.

Но машина Тьюринга – это все-таки прежде всего метод математического моделирования.

Машина Тьюринга включает:

1. Потенциально бесконечную (вправо) ленту, разделенную на ячейки.

2. Считывающе-записывающую головку с устройством управления (УУ).

3. Алфавит внутренних состояний {q0, q1...qn}.

4. Входной-выходной алфавит.






Определяется начальная конфигурация. Головка смотрит на какую-то ячейку и устройство управления находится в начальном состоянии q1.

Устройство управления на основании считанного из ячейки символа и внутреннего состояния пишет в ячейку символ (возможно, тот же самый), совершает действие D и переходит в новое внутреннее состояние (возможно прежнее). Это и есть команда Машины Тьюринга, которую можно записать так:

aiqi  ajDjqj.

D = {Л, П, С} - множество действий.

Л – влево, П – вправо, С - стоять.

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

Машина заканчивает работу, когда переходит в состояние q0.

 - пустой символ.


Пример: Построим машину Т, которая в сплошной последовательности 1 стирает первую и две последние. ( - пустой символ).





q1

q2

q3

q4

1

Пq2

1Пq2

Лq4

Сq0



-

Лq3

-

-



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

Автор - А.А. Марков, отдавал предпочтение транскрипции алгорифм. Нормальные алгорифмы Маркова представляются нормальной схемой подстановок, которая состоит из совокупности подстановок, расположенных в определенном порядке. Подстановки имеют вид: P ()Q (P Q(простая) подстановка, P Qзаключительная подстановка).

Говорят, что строка R входит в строку L, если L имеет вид L1RL2.

Говорят, что подстановка применима к слову, если строка, соответствующая левой части подстановки, входит в слово. Применение заключается в замене в преобразуемом слове левой строки подстановки правой.

Две особые подстановки:

P - аннулирующая.

Q - порождающая.


Механизм работы нормальных алгорифмов:

0) Дано (преобразуемое) слово – цепочка символов фиксированного алфавита и нормальная схема подстановок, содержащая фиксированную последовательность простых и заключительных подстановок.

1) Слово всегда просматривается слева направо.

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

2) Работа алгоритма заканчивается тогда, когда ни одна из подстановок не применима, либо.использована заключительная подстановка.
Примеры.

нормальная схема преобразуемое

подстановок слово




xx  y xxxyyyzzz

xy  x yxyyyzzz

yzy  x yxyyzzz

zz . z yxyzzz

yy  x yxzzz

yxzz
МУХА

Х  К МУКА

М  Р РУКА

КА  ЛОН РУЛОН

РУ . СЛ СЛОН


Примеры алгорифмов, использующие специальные символы, аннулирующие и порождающие подстановки:

Удвоение исходной строки

х  хх

у  уу

хх  хх

ху  ух

ух  ху

уу  уу

 


 .

 


Обращение исходной строки

  


  

х  х


у  у

  .


ху ух

ух  ху

 

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

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

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

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

Рекурсивные функции строятся на основе трех примитивных (заведомо однозначно понимаемых и реализуемых) функций.

1. Нуль-функция: Z(x) = 0.

Например, Z(1) = 0, Z(5) = 0., но Z(-5) - не определено.


  1. Функция следования: S(x) = x + 1.

Тонкость заключается в том, что операции сложения (+) мы здесь пока не определили и запись " + 1" понимается как взятие следующего элемента естественно упорядоченного множества N.

То есть в множестве N. всегда можно найти следующий аргумент, например: S(5) = 6.

3.Функция проектирования (выбора аргумента). Ii( n) (x1, x2,...,xi,...,xn) = xi.

Или частный случай - тождественная функция: I (x) = x.


С примитивными функциями можно производить различные манипуляции, используя три оператора: суперпозиции, примитивной рекурсии и наименьшего корня.
1.Оператор суперпозиции: Позволяет из функции f (у1, …, уm) и функций

h1(x1,...,xn), h2(x1,...,xn), ... ,hm(x1,...,xn) сконструировать функцию

f(h1(x1,...,xn), ... , hm(x1,...,xn)).

Например, с помощью оператора суперпозиции можно получить любую константу

S(S( …(Z(x)) …)) = n, где число вложенных функций следования равно n.

Или сдвига числа на константу n, также равную числу вложенных функций следования.

S(S( …(S(x)) …)) = x + n,


  1. Оператор примитивной рекурсии. Этот оператор позволяет получит

n + 1-местную функцию из n-местной и n + 2 - местной функций.

Оператор задается двумя равенствами:



f(x1,...,xn, 0) = g(x1,...,xn)

f(x1,...,xn, y) = h(x1,...,xn, y-1, f(x1,...,xn, y-1))

Позволяет по n+1-местной функции получить n-местную.

Частный случай - функция одного аргумента:



f(0) = const

f(y) = h(y - 1, f(y - 1))


Функции, которые могут быть построены из примитивных с помощью операторов суперпозиции и примитивной рекурсии называются примитивно-рекурсивными.
Пример: функция суммирования.

f(x, 0) = g(x) = I(x) = x

f(x, 1) = h(x, 0, f(x, 0)) = h(x, 0, x) = h`(I3(3)((x, 0, x)) = S(x) = x + 1

f(x, 2) = h(x, 1, f(x,1)) = h(x, 1, x+1) = S(x + 1) = x + 2

. . .

f(x, y) = h(x, 1, f(x, y - 1)) = S(f (x, y - 1)) = x + y



то есть в традиционной записи определение сложения, как примитивно-рекурсивной функции, будет:

x + y = x + (y - 1) + 1


Функция умножения.

fp(x, 0) = y(x) = z(0) = 0

fp(x, 1) = h(x, 0, fp(x, 0)) = h(x, 0, 0) = h`(I1,3(3)((x, 0, 0)) = f(x, 0) = x

fp(x,2) = h`(x, fp(x, 1)) = f(x, x) = 2x

fp(x,y) = f(x, fp(x, y - 1))

то есть в традиционной записи определение умножения, как примитивно-рекурсивной функции, будет

x*y = x*(y - 1) + x

3. -оператор.

y[g(x1, ... , xn, y) = 0]

где y - выделенная переменная.

Работу -оператора можно описать следующим образом.

Выделяется переменная (здесь – у). Затем фиксируется значение остальных переменных (x1, ... , xn). Значение y последовательно увеличивается, начиная с нуля. Значением -оператора будет значение y, при котором функция впервые обратилась в ноль. Значение -оператора считается неопределенным, если функция вообще не принимает значения ноль, либо она принимает отрицательое значение до того как примет значение ноль.

Пример.

Пусть функция g(х, y) = х – у + 3. Зафиксируем х = 1



y[g(1, y) = 0] = 4

так как 1 – 4 + 3 = 0.

Класс (множество, которое может быть получено из примитивных функций с помощью операторов суперпозиции, примитивной. рекурсии и -оператора, называется. множеством частично-рекурсивных функций.

Множество частично-рекурсивных функций совпадает с множеством вычислимых функций - алгоритмически разрешимых задач.




следующая страница >>