Рабочая программа по дисциплине «теория алгоритмов и сложности» для специальности 351400 Прикладная информатика (по областям) Форма обучения: очная

Вид материала

Содержание

Содержание лекционных занятий
Лекция 2. Виды алгоритмов
Лекция 3. Магазинные автоматы. Нормальные алгоритмы. Регистровые машины
Лекция 4. Равнодоступные адресные машины (РАМ)
Write * 2
5. Примитивно рекурсивные, частично рекурсивные и общерекурсивные функции
Лекция 6. Примитивно рекурсивные предикаты, множества и отношения. Замкнутость этих классов относительно логических операций и н
Лекция 7. Универсальный Нормальный Алгоритм Маркова на Упрощенном Рефале.

Подобный материал:

1 2 3 4

Содержание лекционных занятий

Лекция 1. Математическая логика и теория алгоритмов

Виды алгоритмов:

машины Тьюринга: многоленточные, многоголовочные машины,

многомерные ленты, квазибесконечномерность лент*),

ленты с неевклидовой топологией*), древовидные ленты,

эластичные ленты - К-алгоритмы*).

*) - дополнительные вопросы

Структура одноленточной одноголовочной (классической)

машины Тьюринга (МТ):

1) ленточный алфавит: конечное множество "букв" Б=

{б[0],б[1],...,б[d]}, нумерация букв ленточного алфавита

(буквы как натуральные числа): б[i]=i;

2) пробел: элемент ленточного алфавита - пустая буква " "=б[0];

3) алфавит (множество) состояний: конечное множество Q=

{q[0],q[1],...,q[n]}, состояния как натуральные числа q[i]=i;

4) начальное состояние: элемент множества состояний q[1]=1;

5) заключительное состояние: элемент множества состояний q[0]=0;

6) алфавит сдвигов Д={l,s,r};

7) "сдвиг на одну ячейку влево": l;

8) "сдвиг на одну ячейку вправо": r;

9) "отсутствие сдвига": s;

10) функция перехода ф, отображающая Б*(Q\q[0]) в Б*Q*Д,

таблица функции перехода.

Работа одноленточной двусторонней одноголовочной МТ:

1) входние слово: w[1]w[2]...w[n], w - отображение 1..n в Б;

2) моменты времени: N={0,1,2,...} - натуральные числа;

3) номера ячеек Z={...,-2,-1,0,1,2,...} - целые числа;

4) содержимое ленты: л - отображение N*Z в Б;

5) начальное содержимое ленты: л[0,i]=б[0] при i=0,-1,-2,... и i=n+1,n+1,...

л[i]=w[i] при i=1,2,...n.

6) результат: слово, записанное справа от головки до первого пробела

в конце работы.

Пример программы (таблицы функции перехода) сложения в "палочковой"

(монадической) системе счисления:

----------------

| | | + | |

---|---|---|---|

1 | 2r| 0r| 0s|

---|---|---|---|

2 ||2r||3l| 3l|

---|---|---|---|

3 ||3l|+3l| 0r|

----------------

Протокол работы этой МТ на входном слове "||+|||":

||+|||

1

|+|||

2

|+|||

2

|||||

2

|||||

2

|||||

0

Контрольный вопрос

Что делает следующая машина Тьюринга:

----------------

| a | b | |

---|---|---|---|

1 | 2r| 0r| 0s|

---|---|---|---|

2 |a2r|b2r| 3l|

---|---|---|---|

3 | 4l|a5l| 0s|

---|---|---|---|

4 |a4l|b4l| 1r|

---|---|---|---|

5 |a5l|b5l| 0r|

----------------

Протокол aaba ?

Результат abaa , aba ?

Лекция 2. Виды алгоритмов

Алгоритмы Колмогорова-Успенского.

К-алгоритм - частный случай КУ-алгоритма.

Многомагазинный автомат.

Алгоритм как математическая конструкция.

U - множество конструктивных объектов.

T - конечное множество их локальных преобразований

T - подмножество отображений из U в U.

C - множество признаков C - подмножество отображений из U в {0,1}.

Пусть i,f,o:T, c:C, x:I.

Тогда (i,f,c,o)(x)=(y:=i(x);while(c(y))y:=f(y);o(y))

т.е.

(i,f,c,o)(x)=o(f*(min({j=1,..,N-1|c(f*j(i(x))=1})))

Рассмотрим случай, когда конструктивные объекты - деревья/

скобочные структуры.

Локальные преобразования скобочных структур.

Контрольные вопросы

Пусть К-алгоритм f=

(

qa - aaq

qb - bq

q. - qq.

aqq - qqa

bqq - qqbb

.qq - .

).

Чему равно f(abba)?

Что делает этот алгоритм в общем случае?

Напишите алгоритм, удваивающий число в монадической системе

счисления.

Лекция 3. Магазинные автоматы. Нормальные алгоритмы. Регистровые машины

Правила (подстановки) магазинных автоматов:

a1,a2,...,an - w1,w2,...,wn

(ai - не более, чем однобуквенные слова).

Нормальные алгоритмы (НА) Маркова.

Нормальны алгоритм - последовательности (подстановок) вида

f=(u[1] - e[1] v[1];

u[2] - e[2] v[2];

...

u[n] - e[n] v[n])

где v[i], u[i] принадлежат Б* - слова в алфавите Б, e[i]=. или

пустое слово

(".", "-", ";" не принадлежит Б). Применение алгоритма f к

слову w состоит в замене w на слово xv[i]y, при наименьшем i,

для которого слово w представимо в виде xu[i]y. При этом для

данного i длина слова x также берется наименьшей. Если e[i]

пусто, то процесс на этом заканчивается, иначе - продолжается

снова по этому же правилу (находится наименьшее i, а для него -

наименьшее x, при которых уже вновь полученное слово представимо

в виде xu[i]y, и производится соответствующая замена u[i] на

v[i] и т.д.).

Пример. Алгоритм вычисления модуля разности в монадической системе

счисления (заменяет слово x*y, где слова x и y состоят из m и n

палочек соответственно, на слово, содержащее из |m-n| палочек,

то есть слово вида xy*y - на x, а слово вида x*xy - на y, где

x,y:{|}* ):

absdiff=(|*| - *; * -.).

Протокол работы алгоритма absdiff на слове ||||*||:

||||*|| - |||*| - ||* - ||.

Протокол работы алгоритма absdiff на слове ||*||||:

||*|||| - |*||| - *|| - ||.

Регистровые машины. Определение. Примеры.

Контрольный вопрос:

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

Лекция 4. Равнодоступные адресные машины (РАМ)

Структура РАМ:

Входной поток: x[1],x[2],... (входные данные)

Указатель входного потока: i

(Возможное видоизменение: размер входного потока: n: x[1],...,x[n].)

Начальное значение указателя входного потока: 1

Текущее значение входного потока (входное значение): x[i]

Выходной поток: y[1],y[2],... (ячейки для выхоых данных)

Указатель выходного потока: j

Начальное значение указателя выходного потока: 1

Текущее значение выходного потока (выводимое значение): y[j]

Оперативная память: r[0],r[1],r[2],... (регистры)

Аккумулятор (сумматор): r[0]

Программа: 1: I[1];

2: I[2];

...

(команды)

Начальное содержимое памяти: нули

Структура команды: код_операции модификатор операнд

Коды операций:

LOAD - загрузка сумматора,

STORE - запоминание сумматора,

ADD - сложение,

SUBT - вычитание,

JGTZ - переход по положительному значению,

READ - чтение,

WRITE - запись,

HALT - остановка.

Коды дополнительных операций:

JUMP - переход,

JZERO - переход по нулю,

MULT - умножение,

DIV - деление.

Машины с умножением: MRAM

Модификаторы: =, пробел, *

Операнд: числовая константа

(Основной) Тип данных: натуральные числа

(Вариант - работа с целыми числами и др.)

Система команд РАМ:

Команда Комментарий

LOAD = a r[0]:=a

LOAD a r[0]:=r[a]

LOAD * a r[0]:=r[r[a]]

STORE a r[a]:=r[0]

STORE * a r[r[a]]:=r[0]

ADD = a r[0]:=r[0]+a

ADD a r[0]:=r[0]+r[a]

ADD * a r[0]:=r[0]+r[r[a]]

SUBT = a r[0]:=r[0]-.a

где x-.y = max{0,x-y}, если работаем с натуральными числами

SUBT a r[0]:=r[0]-.r[a]

SUBT * a r[0]:=r[0]-.r[r[a]]

(MULT = a r[0]:=r[0]*a

MULT a r[0]:=r[0]*r[a]

MULT * a r[0]:=r[0]*r[r[a]]

DIV = a r[0]:=r[0]/.a

где x/.y - целая часть частного от деления x на y и 0, если y=0

DIV a r[0]:=r[0]/.r[a]

DIV * a r[0]:=r[0]/.r[r[a]]

JUMP m go to m

JZERO m if r[0]=0 then go to m

)

JGTZ m if r[0] > 0 then go to m

READ a r[a]:=x[i];i:=i+1

READ * a r[r[a]]:=x[i];i:=i+1

(возможное видоизменение команды READ:

READ m if i > n then go to m; r[0]:=x[i]; i:=i+1)

WRITE = a y[j]:=a;j:=j+1

WRITE a y[j]:=r[a];j:=j+1

WRITE * a y[j]:=r[r[a]];j:=j+1

HALT остановка, используется при работе в режиме offline,

операнд отсутствует, в режиме online остановка происходит при исчерпании

данных во время выполнения операции READ - при i, большем n.

Примеры РАМ-программ

1. Сложение 2-х чисел: y[1]=x[1]+x[2]:

1: READ 1

2: READ 0

3: ADD 1

4: WRITE 0

5: HALT

2. Сложение n=x[1] чисел: y[1]=x[2]+x[3]+...+x[1+x[1]]:

READ 1

loop: JZERO out

READ 0

ADD 2

STORE 2

JUMP loop

out: WRITE 2

HALT

3. Инверсия (выдача в обратном порядке) n чисел:

y[1]=x[1+x[1]],

y[2]=x[x[1]],

...,

y[i]=x[2+x[1]-i]

...,

y[x[1]]=x[2]:

LOAD = 3

STORE 2

READ 1

LOAD 1

loop: JZERO out

READ * 2

LOAD 2

ADD = 1

STORE 2

LOAD 1

SUBT = 1

STORE 1

JUMP loop

out: LOAD 2

SUBT = 1

STORE 2

SUBT = 2

JZERO end

WRITE * 2

JUMP out

end: HALT

Контрольный вопрос

Пусть f=

(

READ 0

STORE 1

READ 0

ADD 1

MULT 1

WRITE 0

HALT

).

Чему равно f(2,2), f(5,8), f(x,y) (написать выражение)?

РАМ с хранимой программой.

5. Примитивно рекурсивные, частично рекурсивные и общерекурсивные функции

Базисные функции (B):

I[n,k](x[1],...,x[n])=x[k] при k=1,...,n (другая запись Ink);

Z(x)=0 (другая запись Z=O или Z=0);

S(x)=x+1;

Операторы над (частичными натуральнозначными) функциями

(натуральных аргументов):

суперпозиция o: при любых m-местной f, n-местных g,

натуральных векторах X

fo(g[1],...,g[m])(X)=f(g[1](X),...,g[m](X)), где (X)=(x[1],...,x[n])

(n-мерный натуральный вектор),

если правая часть равенства неопределена, то левая также неопределена,

другая запись: fo(G)=f(G);

(примитивная) рекурсия R: при любых n-местной g, n+2-местной h

f=gRh - n+1-местная функция, это равенство означает, что при

любых n-мерных натуральных векторах X и при любом натуральном y

выполнены два следующих равенства:

f(X,0)=g(X)

f(X,y+1)=h(X,y,f(X,y))

(если правая часть неопределена, то левая также неопределена);

другая запись: f=R(g,h);

операция нахождения наименьшего корня (операция минимизации) mu:

для любой n+1-местной функции M(f) -

Mf(X)=min{y|f(X,y)=0}

(если правая часть неопределена, то левая также неопределена)

Примитивно рекурсивные функции (ПРФ) как замыкание множества B

относительно операций о и R.

Примеры ПРФ:

+: x+0=x

x+(y+1)=S(x+y)

+=R(I11,S(I33))

*: x0=0

x(y+1)=xy+x

*=R(Z,+(I33,I31))

**: x**0=1

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

**=R(S(Z),*(I33,I11))

***: x***0=1

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

***=R(S(Z),**(I31,I33))

Пример не ПРФ:

обозначения:

S(x)=A(0,x,y),

x+y=A(1,x,y),

xy=A(2,x,y),

x**y=A(3,x,y),

x***y=A(4,x,y) (операция "тетрация"),

При n, большем 1

A(n+1,x,0)=1;

A(n+1,x,y+1)=A(n,x,A(n+1,x,y))

A - пример не ПРФ.

Примеры ПРФ:

Pd2(x,0)=0

Pd2(x,y+1)=y

Pd(x)=Pd2(x,x)

Pd=R(Z,I32)(I11)

Pd(x)=max{0,x-1}

x-.0=x

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

-.=R(I11,Pd(I33))

if0(x1,x2,0)=x1

if0(x1,x2,y+1)=x2

if0=R(I21,I42)

if0(x,y,z)=if z=0 then x else y

Остаток от деления:

dom(x,0) = 0

dom(x,y+1) = if x-.S(dom(x,y))=0 then 0 else S(dom(x,y))

x mod y = dom(y,x)

mod=R(Z,if0(Z(I33),S(I33),-.(I31,S(I33))))(I22,I21),

при этом определении x mod 0 = 0.

Целая часть частного:

vid(x,0) = 0

vid(x,y+1) = if dom(x,S(y))=0 then S(vid(x,y)) else vid(x,y)

x div y = vid(y,x)

div=R(Z,if0(S(I33)),I33,dom(I31,S(I32)))))(I22,I21),

при этом определении x div 0 = x.

Целая часть корня (степени x):

root(x,0) = 0

root(x,y+1) = if S(root(x,y))**x-.y=0 then root(x,y) else S(root(x,y))

root=R(Z,if0(I33,S(I33),-.(**(S(I33),I31),I32)))

Целая часть квадратного корня:

sqrt(x) = root(2,x)

sqrt=root(S(S(Z)),I11)

Частично-рекурсивные функции (ЧРФ) как замыкание множества B

относительно операций o, R и M.

Общерекурсивные функции (ОРФ) как множество всех всюду определенных

ЧРФ. Функция A - пример ОРФ, не являющейся ПРФ.

Контрольный вопрос

f1(x,0)=0

f1(x,y+1)=y

f1=R(Z,I32)

f2(x,0)=x

f2(x,y+1)=f1(x,f2(x,y))

f2=R(I11,f1(I31,I33))

f2(2,1)=?, f2(1,2)=?

f3=R(I11,R(Z,I32)(I31,I33))

f3(3,2)=?, f3(3,3)=?

Вычислить

f=M(I21-'I22) (M=mu=minroot)

f(0),f(1),f(100),f(x) (выражение)

Лекция 6. Примитивно рекурсивные предикаты, множества и отношения. Замкнутость этих классов относительно логических операций и навешивания ограниченных кванторов

Частичная рекурсивность вычислимых функций

Теорема о частичной рекурсивности функций,

вычислимых

- многомагазинными автоматами

- (К-алгоритмами, машинами Тьюринга)

- нормальными алгоритмами Маркова.

Части доказательства:

Взаимно однозначное соответствие между словами алфавита Б

и натуральными числами (d-адическая система счисления)

Примитивная рекурсивность функции конкатенации чисел в

d-адической системе счисления.

Примитивная рекурсивность функции выполнения подстановки НА.

Примитивная рекурсивность функции выполнения y подстановок.

Частичная рекурсивность функции подсчета числа шагов НА.

Примитивная рекурсивность функции кодирования и декодирования

чисел в алфавите.

Одновременная рекурсия. **)

Функция, нумерующая пары **)

C(x,y)=(x+y+1)(x+y)/2+x+1

(l,r) - обратная вектор-функция.

Двухмагазинный автомат **)

(n,r,d)

n:N, (1..n-1)=S - символы магазинного алфавита

r:N, (0..r-1)=Q - состояния, 0 - заключительное, 1 - начальное.

d - функция перехода

d отображает n*n*(1..r) в n*n*r

yields(x)=(x,,1)

step(w,v,q)=(w.a',v.b',q')

где d(last(w), last(v),q)=(a',b',q'),

last()=0, last(wa)=a, wa.0=w, w.a=wa, (a:S,w:S*),

end(w,v,q)=(q=0)

.

c3(x,y,z)=c(c(x,y),z)

l3[1](u)=l(l(u))

l3[2](u)=r(l(u))

l3[3](u)=r(u)

.

f - функция протокола автомата (n,r,d):

f(x,0)=c3(x,0,1)

f(x,i+1)=c3(w.a',v.b',q')

=c3(.(l3[1](x),d[1](last(l3[1](x)),last(l3[2](x)),l3[3](x))),

.(l3[2](x),d[2](last(l3[1](x)),last(l3[2](x)),l3[3](x))),

d[3](last(l3[1](x)),last(l3[2](x)),l3[3](x)))

.

g - функция выхода автомата (n,r,d)

g(x)=f(x,min{i|l33(f(x,i))=0})

.

.(x,y)=if(y,trunc(x),dx+y)

trunc(x)=if(x mod d, [x/d]-1, [x/d])

d[i](x,y,z)=d(x,y,z)[i]

last(x)=if(x,0,if(x mod d, d, x mod d))

.

Если d - параметр, то d[i](a,b,q) заменить на

appl[i](d,a,b,q)=l[3,i](proj(proj(proj(d,a),b),q))

proj(D,i)=(l(D)/r(D)**i)mod r(D)

Лекция 7. Универсальный Нормальный Алгоритм Маркова на Упрощенном Рефале. Машины Джонса. Универсальная машина Джонса.

Запись на предельно упрощенном рефале

запись УА для НА. Программа НА вида

x[1] - e[1] y[1]

...

x[n] - e[n] y[n]

кодируется выражением

(((x[1])(e[1])y[1])...((x[n])(e[n])y[n]),

где x[i], y[i] - слова в рабочем алфавите алгоритма,

e[i]=. или e[i] пусто.

Например, алгоритм

|*| - *

* -.

кодируется выражением

((('|*|')()'*')(('*')('.')))

Программа на упрощенном рефале:

U((p((u)(e)v)q)x u y)=V((e)(p((u)(e)v)q)x v y);

U((p)x)=x;

V(()z)=U(z);

V(('.')(p)x)=x.

Машины Джонса (дополнительный вопрос).

Универсальная машина Джонса.

Команды

x:=E [v:=E]

if E1=E2 then S1 else S2

while E1#E2 do S

Выражения (E1.E2), nil, x, lE, rE.

Лекция 8. Программа машины Джонса как структура данных

Элементы программы машины Джонса как структуры данных:

(':='.E), ('.'.(E1.E2)), ('l'.E), ('r'.E),

('if'.((E1.E2).(S1.S2))), ('nil'.nil)

('while'.((E1.E2).S)).

Контрольный вопрос:

Напишите программу, выполняющую преобразование

(nil.(nil. ... (nil.(E1.E2))...)) в (E1.E2)

Лекция 9. Разрешимые и неразрешимые множества.

Перечислимые и неперечислимые множества

Определение класса разрешимых множеств

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

характеристическая функция вычислима. X - характеристическая

функция множества M элементов пространства U, если X отображает

U в {0,1} и для любого x из U равенство X(x)=1 эквивалентно

принадлежности элемента x множеству M. (Примечание: в качестве

пространства U можно брать, например, множество натуральных

чисел, множество слов в конечном алфавите, множество конечных

последовательностей натуральных чисел, множество бинарных

конечных деревьев (или n-арных конечных деревьев или конечных

упорядовеннных деревьев), термов в конечном функциональном

базисе и т.д.).

Свойства разрешимых множеств

- Пустое множество разрешимо.

- Пространство U разрешимо.

- Любое конечное множество разрешимо.

- Пересечение любого конечного числа разрешимых множеств

разрешимо.

- Объединение любого конечного числа разрешимых множеств

разрешимо.

- Разность двух разрешимых множеств разрешима.

- Пример неразрешимого множества - область определения

универсального алгоритма.

Определение класса перечислимых множеств

Перечислимыми множествами называются области определения

вычислимых функций.

Свойства класса перечислимых множеств

- Класс перечислимых множеств совпадает с классом множеств

значений вычислимых функций.

- Все разрешимые множества перечислимы.

- Пересечение любого конечного числа перечислимых множеств

перечислимо.

- Объединение любого конечного числа перечислимых множеств

перечислимо.

- Если дополнение перечислимого множества перечислимо, то это

множество разрешимо.

- Следствие: дополнение области определения универсального

алгоритма не перечислимо.

Контрольный вопрос:

выделите перечислимые и разрешимые множества среди следующих

множеств:

1) множество программ, не применимых к пустому слову,

2) - -, применимых ...,

3) множество (p,n,x), для которых p не останавливается за n

шагов на x,

4) - -, - - - останавливается - - - - пустом слове,

5) - (p,n), - - - не останавливается ...,

6) - -, - - - останавливается ...,

7) - программ, не останавливающихся за 1000000 шагов на пустом слове,

8) - -, останавливающихся ...,

9) можно ли определить, выполняется ли когда-либо некоторая команда

в программе.

Иерархия Клини-Мостовского

Blog

Рабочая программа по дисциплине «теория алгоритмов и сложности» для специальности 351400 Прикладная информатика (по областям) Форма обучения: очная

Содержание