Шпаргалка по "Теории Алгоритмов"

1. Предмет изучения теории алгоритмов. Интуитивное понятие алгоритма и необходимость его уточнения. Свойства алгоритмов. Универсальные алгоритмические модели.

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

Цели и задачи теории алгоритмов 
· формализация понятия «алгоритм» и исследование формальных алгоритмических систем; 
· формальное доказательство алгоритмической неразрешимости ряда задач; 
· классификация задач, определение и исследование сложностных классов; 
· асимптотический анализ сложности алгоритмов; 
· исследование и анализ рекурсивных алгоритмов; 
· получение явных функций трудоемкости в целях сравнительного анализа алгоритмов; 
· разработка критериев сравнительной оценки качества алгоритмов.

Алгоритм - одно из основных понятий (категорий) математики, не обладающих формальным определением в терминах более простых понятий, а абстрагируемых непосредственно из опыта. Алгоритмами являются, например, известные из начальной школы правила сложения, вычитания, умножения и деления столбиком. Вообще, под алгоритмом понимается всякое точное предписание, которое задаёт вычислительный процесс (называемый в этом случае алгоритмическим), начинающийся с произвольного исходного данного (из некоторой совокупности возможных для данного алгоритма исходных данных) и направленный на получение полностью определяемого этим исходным данным результата. Не предполагается, что результат будет обязательно получен: процесс применения алгоритма к конкретному возможному исходному данному (т.е. алгоритмический процесс, развёртывающийся начиная с этого данного) может также оборваться безрезультатно или не закончиться вовсе. В случае, если процесс заканчивается (соответственно не заканчивается) получением результата, говорят, что алгоритм применим (соответственно неприменим) к рассматриваемому возможному исходному данному. Алгоритм(интуитивное понятие) –точное и понятное предписание исполнителю совершить определенные действия, направленные на решение задачи или достижение цели.

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

Для доказательства несуществования  алгоритма, интуитивного понятия алгоритма  недостаточно. Оно должно быть уточнено и формализовано. 
Интуитивное понятие алгоритма – одно из основных понятий математики, не допускающее определения в терминах более простых понятий 
Формы представления алгоритмов.  
Словесная форма; Блок-схема; Алгоритмическая запись (или запись на языке программирования). 
Универсальные алгоритмические модели - универсальное средство, которое позволяет описать любой алгоритм решения любой задачи. 
Идея построения УАМ - должна иметь предельно простую структуру, возможность выполнять и их элементарность не должны вызывать сомнений

УАМ – средство формализации понятия алгоритм

 

 

 

 

 

Формы понятия объекта                                                                                              Формы понятия действий над объектом

 

 

Абстр машины                                                         НАМ                                                             Рок Ф

 

2. Определение машины Тьюринга. Определение вычислимой по Тьюрингу функции.

Машина Тьюринга есть математическая (воображаемая) машина, а не машина физическая. Она есть такой же математический объект, как функция, производная,  интеграл, группа и т.д. И также как и другие математические понятия, понятие машины Тьюринга отражает объективную реальность, моделирует некие реальные процессы. Ее удобно представлять в виде автоматически работающего устройства. В каждый дискретный момент времени устройство, находясь в некотором состоянии, обозревает содержимое одной ячейки протягиваемой через устройство ленты и делает шаг, заключающийся в том, что устройство переходит в новое состояние, изменяет (или оставляет без изменения) содержимое обозреваемой ячейки и переходит к обозрению следующей ячейки — справа или слева. Причем шаг осуществляется на основании предписанной команды. Совокупность всех команд представляет собой программу машины Тьюринга. В каждый момент времени машина способна находиться в одном состоянии из конечного числа внутренних состояний, совокупность которых Q = {q0 , q1, .., qm}. Среди состояний выделяются два — начальное q1 и заключительное (или состояние остановки) q0. Находясь в состоянии q1, машина

начинает работать. Попав  в состояние q0, машина останавливается. Функция называется вычислимой по Тьюрингу, если существует машина Тьюринга, вычисляющая ее, т.е. такая машина Тьюринга, которая вычисляет ее значения для тех наборов значений аргументов, для которых функция определена, и работающая вечно, если функция для данного набора значений аргументов не определена. Определение 5.8. Функция f(x₁, x₂, …, x_n) называется вычислимой, если существует алгоритм, позволяющий вычислять ее значения для тех переменных, для которых она определена, и работающий бесконечно, если функция для данного набора переменных не определена.Вычислимы по Тьюрингу только частично рекурсивные функции. 
Определение 5.9. Функция f(x₁, x₂, …, x_n) называется вычислимой по Тьюрингу, если существует машина Тьюринга, вычисляющая эту функцию. Пример 1 Построим машину Тьюринга, вычисляющую функцию f(x) = х/2. Эта функция не всюду определена: областью ее определения

является лишь множество  всех четных чисел. Поэтому, учитываяопределение 1, нужно сконструировать такую машину Тьюринга, которая при подаче на ее вход четного числа давала бы на выходе половину этого числа, а при подаче нечетного — работала бы неограниченно

долго.

3. Композиции машин Тьюринга. Тезис Тьюринга.

Определение 1. Пусть заданы машины Тьюринга O1 и О2, имеющие общий внешний алфавит {а0, а1, ..., а‘m} и алфавиты внутренних состояний {q0 , q1 , …, q’n} и {q0, q’1, q’2 ,…, q’t} соответственно. Композицией (или произведением) машины O1 на машину О2

называется новая машина О с темже внешним алфавитом {а0, а1, ..., а’m}, внутренним алфавитом {q0 , q1 , …, qn, qn+1, qn+2 ,…, qn+t} и программой, получающейся следующим образом. Во всех командах из O1, содержащих символ остановки q0 заменяем последний на qn+1. Все остальные символы в командах из O1 остаются неизменными. Вкомандах из O2 символ q0 оставляем неизменным, а все остальные состояния q’i (i = 1, ..., t) заменяем соответственно на qn+i. Совокупность всех так полученных команд образует программу машины-композиции O. Введенное понятие является удобным инструментом для конструирования машин Тьюринга.

Тезис Тьюринга. Всякую вычислимую функцию (алгоритм) можно реализовать с помощью машины Тьюринга.(для всякого алгоритма может быть построена, соответствующая ему машина тьюринга) 
Таким образом, если мы принимаем этот тезис, то можем смело говорить о вычислимости, не указывая конкретную модель Сразу возникает вопрос: любую ли функцию y = f(x), можно вычислить на МТ? 
Ответ на этот вопрос утвердительный. Существует проблема остановки алгоритма. В общих чертах она сводится к вопросу существует ли алгоритм  , который для произвольного алгоритма ^ A и данных   определял бы приведет ли работа алгоритма A к результату или нет, т.е.  , если  результативен и   в противном случае. Эту задачу можно сформулировать, как задачу о существовании МТ  , которая для произвольной машины Тьюринга T и входного слова   МТ T  , если машина Тьюринга   останавливается (вычислима), и  , если   не останавливается (не вычислима). Теорема 1. Не существует машины Тьюринга  , решающей проблему остановки для произвольной машины Тьюринга T.

4. Определение нормального алгоритма Маркова. Функции вычислимые по Маркову. Принцип нормализации Маркова.

Норма́льный алгори́тм Ма́ркова (НАМ) — один из стандартных способов формального определения понятия алгоритма, так же как и машина Тьюринга. Понятие нормального алгоритма введено А.А. Марковым в конце 1940-х годов. Традиционно, когда говорят об алгоритмах Маркова, используют слово "алгорифм". 
Нормальный алгоритм описывает метод переписывания строк, похожий по способу задания на формальные грамматики.

Нормальный алгоритм – это совокупность марковских подстановок. В основе данной модели лежит алфавитное представление информации, под внешним алфавитом данной модели понимается совокупность символов, из которых может состоять входное слово. При этом для реализации алгоритма могут потребоваться дополнительные символы об алгоритме над алфавитом А. Основная идея: если на преобразованную информацию посмотреть отвлеченно от каких-либо машинных механизмов, то процесс преобразования сводится к замене одного фрагмента текста на другой. Марков предложил этот процесс замены описывать в виде системы подстановок(«марковских подстановок») Pi, Qi – слова в некотором алфавите, --> - обычная замена, │à - завершающая замена. Нормально вычислимой (или вычислимой по Маркову) функцией называется вербальная функция f, для которой существует такое расширение D алфавита å и такой нормальный алгорифм в алфавите D, что каждое слово Р в алфавите å из области определения функции f этот нормальный алгорифм переводит в слово f(Р).

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

I. Суперпозиция алгоритмов. При суперпозиции двух алгоритмов слово первого алгоритма рассматривается как входное слово второго алгоритма B, результат суперпозиции C может быть представлен в виде C(p) и B(A(p)).  

II. Объединение алгоритмов. Объединением алгоритмов А и B в одном и том же алфавите называется алгоритм Св том же алфавите, преобразующий любое слово p содержащееся в пересечении областей определения алгоритмов А иВ, в записаныe рядом слова А(р) и В(р).

III. Разветвление алгоритмов. Разветвление алгоритмов представляет собой композицию D трех алгоритмов A, Ви С, причем область определения алгоритма D является пересечением областей определения всех трех алгоритмов А, Ви С, а для любого слова р из этого пересечения D(p) = А(р), если С(р) = е, D(p) = B(p), если C(p) = е, где е - пустая строка.

IV. Итерация алгоритмов. Итерация (повторение) представляет собой такую суперпозицию С двух алгоритмов А иВ, что для любого входного слова p соответствующее слово С(р) получается в результате последовательного многократного применения алгоритма А до тех пор, пока не получится слово, преобразуемое алгоритмом B.

5. Определение класса частично рекурсивных функций. Определение общерекурсивной и примитивно рекурсивной функции. Тезис Черча.

 

Термин рекурсивная функция в теории вычислимости используется для обозначения трёх классов функций 1)примитивно рекурсивные функции; 2)общерекурсивные функции; 3)частично рекурсивные функции. Множество частично рекурсивных функций включает в себя множество общерекурсивных функций, а общерекурсивные функции включают в себя примитивно рекурсивные функции. Частично рекурсивные функции иногда называют просто рекурсивными функциями.

Частичная функция f называется частично рекурсивной, если существует такая конечная последовательность частичных функций g₀, …, g_k что g_k=f  и каждая g i, i≤k либо базисная, либо получается из некоторых предыдущих регулярной суперпозицией, примитивной рекурсией или      минимизацией. Эта последовательность g₀, …,g_k называется определяющей последовательностью для f. Частично рекурсивная функция определяется примитивно рекурсивной, только к двум операторам суперпозиции и примитивной рекурсии добавляется ещё третий оператор — минимизации аргумента.

Общерекурсивная функция — частично рекурсивная функция, определённая для всех значений аргументов. Задача определения того, является ли частично рекурсивная функция с данным описанием общерекурсивной или нет, алгоритмически неразрешима.

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

К числу базовых примитивно рекурсивных  функций относятся функции следующих  трёх видов:

1)Нулевая функция   — функция без аргументов, всегда возвращающая 0. 2)Функция следования   одного переменного, сопоставляющая любому натуральному числу   непосредственно следующее за ним натуральное число  . 3)Функции  , где  , от n переменных, сопоставляющие любому упорядоченному набору   натуральных чисел число   из этого набора.

Операторы подстановки и примитивной рекурсии определяются следующим образом: Оператор суперпозиции (иногда — оператор подстановки). Пусть   — функция от m переменных, а   — упорядоченный набор функций от   переменных каждая. Тогда результатом суперпозиции функций   в функцию   называется функция   от   переменных, сопоставляющая любому упорядоченному набору   натуральных чисел число

.Оператор примитивной рекурсии. Пусть   — функция от n переменных, а   — функция от   переменных. Тогда результатом применения оператора примитивной рекурсии к паре функций   и   называется функция   от   переменной вида

;

.

6. Вычислимая функция, разрешимое, перечислимое множество.

Определение 1. Функция f(x₁,…,х_n) называется вычислимой, если существует алгоритм, позволяющий вычислять ее значения для тех наборов аргументов, для которых она определена, и работающий вечно, если функция для данного набора значений аргументов не определена. Пусть MÍNⁿ= N×…×N.

Определение 2. Множество М называется разрешимым, если имеется алгоритм для выяснения того, принадлежит или не принадлежит произвольный элемент этому множеству.