Рабочая программа дисциплины «Алгоритмы и анализ сложности»
Скачать 0.5 Mb.
|
| Тема 1.Математическая логика и теория алгоритмов - 2 часа лекций, 2 часа практических зантий, 3 часа самостоятельной работы. Виды алгоритмов: машины Тьюринга: многоленточные, многоголовочные машины, многомерные ленты, квазибесконечномерность лент*), ленты с неевклидовой топологией*), древовидные ленты, эластичные ленты - К-алгоритмы*). *) - дополнительные вопросы Структура одноленточной одноголовочной (классической) машины Тьюринга (МТ): 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.Виды алгоритмов- 2 часа лекций, 2 часа практических занятий, 3 часа самостоятельной работы. Алгоритмы Колмогорова-Успенского. К-алгоритм - частный случай КУ-алгоритма. Многомагазинный автомат. Алгоритм как математическая конструкция. 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. Магазинные автоматы. Нормальные алгоритмы. Регистровые машины - 2 часа лекций, 2 часа практических занятий, 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. Равнодоступные адресные машины (РАМ) - 2 часа лекций, 2 часа практических занятий, 3 ЧАСА САМОСТОЯТЕЛЬНОЙ РАБОТЫ. Структура РАМ: Входной поток: 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 = ar[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. Примитивно рекурсивные, частично рекурсивные и общерекурсивные функции - 2 часа лекций, 2 часа практических занятий, 3 ЧАСА САМОСТОЯТЕЛЬНОЙ РАБОТЫ. Базисные функции (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)-местной hf=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 Остаток от деления: rm(x,0) = 0 rm(x,y+1) = if x-.S(rm(x,y))=0 then 0 else S(rm(x,y)) x mod y = rm(y,x) mod=R(Z,if0(Z(I33),S(I33),-.(I31,S(I33))))(I22,I21), при этом определении x mod 0 = 0. Целая часть частного: dr(x,0) = 0 dr(x,y+1) = if rm(x,S(y))=0 then S(dr(x,y)) else dr(x,y) x div y = dr(y,x) div=R(Z,if0(S(I33)),I33,rm(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.Примитивно рекурсивные предикаты, множества и отношения. Замкнутость этих классов относительно логических операций и навешивания ограниченных кванторов, 2 ЧАСА ЛЕКЦИЙ, 2 ЧАСА ПРАКТИЧЕСКИХ ЗАНЯТИЙ, 3 ЧАСА САМОСТОЯТЕЛЬНОЙ РАБОТЫ. Частичная рекурсивность вычислимых функций Теорема о частичной рекурсивности функций, вычислимых - многомагазинными автоматами - (К-алгоритмами, машинами Тьюринга) - нормальными алгоритмами Маркова. Части доказательства: Взаимно однозначное соответствие между словами алфавита Би натуральными числами (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) |
Похожие:
 | Радиофизический факультет Дисциплина «Алгоритмы и анализ сложности» относится к дисциплинам базовой части профессионального цикла основной образовательной... |  | Рабочая программа дисциплины «Алгоритмы и процессоры цифровой обработки сигналов» ... |
| Рабочая программа дисциплины «экономический анализ» Рабочая программа предназначена для преподавания общепрофессиональной дисциплины федерального компонента опд. Ф. 06 «Экономический... | | Рабочая программа дисциплины «финансовый анализ» Рабочая программа предназначена для преподавания специальной дисциплины вузовского компонента студентам заочной формы обучения (сокращенный... |
| Рабочая программа Наименование дисциплины Охватывают основные сведения по данной дисциплине. Варианты сбалансированы по сложности и равноценны по трудоемкости | | Рабочая программа дисциплины «инвестиционный анализ» Рабочая программа предназначена для преподавания специальной дисциплины вузовского компонента студентам очной и заочной форм обучения... |
| Реферат по информатике и икт по теме: «Алгоритмы» Я выбрал тему учебно-методического комплекса «Алгоритмы», так как она является одной из главной тем в информатике | | Реферат по информатике и икт по теме: “ Разветвляющиеся алгоритмы” Я выбрал тему: «Разветвляющиеся алгоритмы», потому что они очень часто применяются в алгоритмизации и программировании. Без знания... |
| Программа по формированию навыков безопасного поведения на дорогах... Иметь представление об алгоритмах, свойствах алгоритмов и записи алгоритмов. Приводить примеры алгоритмов из жизни. Применять готовые... | | Урока Тема урока Количество часов «Зарождение и предмет кибернетики», «Компьютер и управление», «Управление и алгоритмы», «Линейные алгоритмы управления без обратной... |
| Рабочая программа дисциплины «Иностранный язык» Рабочая программа предназначена для преподавания дисциплины специальности 080109. 65 "Бухгалтерский учет, анализ и аудит" в 1- 4... | | Рабочая программа дисциплины «Иностранный язык» Рабочая программа предназначена для преподавания дисциплины специальности 080109. 65 "Бухгалтерский учет, анализ и аудит" в 1- 4... |
| Рабочая программа дисциплины «Иностранный язык» Рабочая программа предназначена для преподавания дисциплины специальности 080109. 65 "Бухгалтерский учет, анализ и аудит" в 1- 4... | | Рабочая программа дисциплины «информатика» Рабочая программа предназначена для преподавания общематематической и естественнонаучной дисциплины студентам очной формы обучения... |
| Рабочая программа по дисциплине В. В экономический анализ Целью освоения дисциплины «Экономический анализ» является изучение теоретических основ и приобретение студентами практических навыков... | | Еще с девятого класса мы изучаем алгоритмы. И вот перейдя из десятого... Целью нашей работы является раскрыть, что такое алгоритмы, их виды и назначения, в чем заключается смысл работы с алгоритмом |
