Цели и задачи теории алгоритма

    1.Цели  и задачи теории алгоритма

    2. Практическое применение результатов  теории алгоритмов

       2.1Формолизацыя  понятия алгоритма

    3. Машины Поста

         3.1 Основные понятия и операции

        3.2 Финитный 1 – процесс

         3.3 Способ задания проблемы и  формулировка 1

    4. Машина Тьюринга

       4.1  Алгоритмически неразрешимые проблемы

       4.2 Проблема соответствий Поста  над алфавитом 

    Список  литературы 
 
 
 

            1.Цели и задачи теории алгоритмов

    Обобщая результаты различных разделов теории алгоритмов можно выделить следующие  цели и соотнесенные с ними задачи, решаемые в теории алгоритмов:

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

    2.Практическое  применение результатов  теории алгоритмов

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

    Теоретический аспект: при исследовании некоторой задачи результаты теории алгоритмов позволяют ответить на вопрос – является ли эта задача в принципе алгоритмически разрешимой – для алгоритмически неразрешимых задач возможно их сведение к задаче останова машины Тьюринга. В случае алгоритмической разрешимости задачи – следующий важный теоретический вопрос – это вопрос о принадлежности этой задачи к классу NP–полных задач, при утвердительном ответе на который, можно говорить о существенных временных затратах для получения точного решения для больших размерностей исходных данных.

    Практический  аспект: методы и методики теории алгоритмов (в основном разделов асимптотического и практического анализа) позволяют осуществить:

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

      2.1Формализация понятия алгоритма

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

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

    Пусть D – область (множество) исходных данных задачи, а R – множество возможных результатов, тогда мы можем говорить, что алгоритм осуществляет отображение D --> R. Поскольку такое отображение может быть не полным, то вводятся следующие понятия:

    Алгоритм  называется частичным алгоритмом, если мы получаем результат только для  некоторых d є D и полным алгоритмом, если алгоритм получает правильный результат  для всех d є D.

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

    Варианты  словесного определения алгоритма  принадлежат российским ученым А.Н. Колмогорову и А.А. Маркову 

    Алгоритм (Колмогоров) – это всякая система вычислений, выполняемых по строго определенным правилам, которая после какого-либо числа шагов заведомо приводит к решению поставленной задачи.

    Алгоритм (Марков)– это точное предписание, определяющее вычислительный процесс, идущий от варьируемых исходных данных к искомому результату.

    Отметим, что различные  определения алгоритма, в явной или  неявной форме, постулируют  следующий ряд  требований:

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

    Другие  формальные определения понятия  алгоритма связаны с введением  специальных математических конструкций (машина Поста, машина Тьюринга, рекурсивно-вычислимые функции Черча) и постулированием  тезиса об эквивалентности такого формализма и понятия «алгоритм».

    3.МАШИНА ПОСТА

    3.1Основные понятия и операции

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

    Например, решение уравнения 3*х+9=0 – это  одна из конкретных проблем, а решение  уравнения a*x+b=0 – это общая проблема, тем самым алгоритм (сам термин «алгоритм» не используется Постом) должен быть универсальным, т.е. должен быть соотнесен  с общей проблемой.

    Основные  понятия алгоритмического формализма Поста – это пространство символов (язык L) в котором задаётся конкретная проблема и получается ответ, и набор  инструкций, т.е. операций в пространстве символов, задающих как сами операции, так и порядок выполнения инструкций.

    Каждый  ящик или ячейка могут быть помечены или не помечены.

    Конкретная  проблема задается «внешней силой» (термин Поста) пометкой конечного количества ячеек, при этом, очевидно, что любая  конфигурация начинается и заканчивается  помеченным ящиком. После применения к конкретной проблеме некоторого набора инструкций решение представляется так же в виде набора помеченных и непомеченных ящиков, распознаваемое той же внешней силой.

    Пост  предложил набор инструкций (элементарных операций), которые выполняет «работник», отметим, что в 1936 году не было еще  ни одной электронной вычислительной машины. Этот набор инструкций является, очевидно, минимальным набором битовых  операций:

1. пометить ящик, если он пуст;
2. стереть метку, если она есть;
3. переместиться влево на 1 ящик;
4. переместиться вправо на 1 ящик;
5. определить помечен ящик или нет, и по результату перейти на одну из двух указанных инструкций;
6. остановиться.

    Отметим, что формулировка инструкций 1 и 2 включает защиту от неправильных ситуаций.

    Программа представляет собой нумерованную последовательность инструкций, причем переходы в инструкции 5 производятся на указанные в ней  номера других инструкций.

    3.2 Финитный 1 – процесс

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

    Далее Пост вводит следующие  понятия:

• набор инструкций применим к общей проблеме, если для каждой конкретной проблемы не возникает коллизий в инструкциях 1 и 2, т.е. никогда программа не стирает метку в пустом ящике и не устанавливает метку в помеченном ящике;
• набор инструкций заканчивается (за конечное количество инструкций), если выполняется инструкция (6);
• набор инструкций задаёт финитный 1 – процесс, если набор применим, и заканчивается для каждой конкретной проблемы;
• финитный 1 – процесс для общей проблемы есть 1 – решение, если ответ для каждой конкретной проблемы правильный (это определяется внешней силой).

    3.3 Способ задания проблемы и формулировка 1

    По  Посту проблема задаётся внешней  силой путем пометки конечного  количества ящиков ленты. В более  поздних работах по машине Поста  принято считать, что машина работает в единичной системе счисления (0=V; 1=VV; 2=VVV; 3=VVVV), т.е. ноль представляется одним помеченным ящиком, а целое  положительное число – помеченными  ящиками в количестве на единицу  больше его значения.

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

    Общая проблема называется по Посту 1-заданой, если существует такой финитный 1 – процесс, что, будучи, применим к n є N в качестве исходной конфигурации ящиков, он задает n-ую конкретную проблему в виде набора помеченных ящиков.

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

    Эмиль Пост завершает свою статью следующей  фразой: «Автор ожидает, что его формулировка окажется логически эквивалентной  рекурсивности в смысле Геделя —  Черча. Цель формулировки, однако, в  том, чтобы предложить систему не только определенной логической силы, но и психологической достоверности. В этом последнем смысле подлежат рассмотрению всё более и более  широкие формулировки. С другой стороны, нашей целью будет показать, что  все они логически сводимы  к формулировке 1. В настоящий  момент мы выдвигаем это умозаключение  в качестве рабочей гипотезы. … Успех вышеизложенной программы заключался бы для нас в превращении этой гипотезы не столько в определение или аксиому, сколько в закон приро-ды».

    Таким образом, гипотеза Поста состоит  в том, что любые более широкие  формулировки в смысле алфавита символов ленты, набора инструкций, представления  и интерпретации конкретных проблем  сводимы к формулировке 1.

    Следовательно, если гипотеза верна, то любые другие формальные определения, задающие некоторый  класс алгоритмов, эквивалентны классу алгоритмов, заданных формулировкой 1 Эмиля Поста.

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

    4. Машина Тьюринга

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

    Формально машина Тьюринга может  быть описана следующим  образом: Пусть заданы:

• конечное множество состояний – Q, в которых может находиться машина Тьюринга;
• конечное множество символов ленты – Г;
• функция (функция переходов или программа), которая задается отображением пары из декартова произведения Q x Г (машина находится в состоянии и обозревает символ ) в тройку декартова произведения Q х Г х {L,R} (машина переходит в состояние , заменяет символ на символ и передвигается влево или вправо на один символ ленты) – Q x Г-->Q х Г х {L,R}
• один символ из Г-->е (пустой);
• подмножество є Г --> определяется как подмножество входных символов ленты, причем е є (Г- );
• одно из состояний – є Q является начальным состоянием машины.

    после чего машина переводится в начальное  состояние и головка устанавливается  у самого левого непустого символа  –  , после чего в соответствии с указанной функцией переходов ( , )-->( , , L или R) машина начинает заменять обозреваемые символы, передвигать головку вправо или влево и переходить в другие состояния, предписанные функций переходов.

    Остановка машины происходит в том случае, если для пары ( , ) функ-ция перехода не определена.

    Алан  Тьюринг высказал предположение, что  любой алгоритм в интуитивном  смысле этого слова может быть представлен эквивалентной машиной  Тьюринга. Это предположение известно как тезис Черча–Тьюринга. Каждый компьютер может моделировать машину Тьюринга (операции перезаписи ячеек, сравнения и перехода к другой соседней ячейке с учетом изменения  состояния машины). Следовательно, он может моделировать алгоритмы в  любом формализме, и из этого тезиса следует, что все компьютеры (независимо от мощности, архитектуры и т.д.) эквивалентны с точки зрения принципиальной возможности  решения алгоритмических задач.

    4.1  Алгоритмически неразрешимые  проблемы

    За  время своего существования человечество придумало множество алгоритмов для решения разнообразных практических и научных проблем. Зададимся  вопросом – а существуют ли какие-нибудь проблемы, для которых невозможно придумать алгоритмы их решения?

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

    Успехи  математики к концу XIX века привели  к формированию мнения, которое выразил  Д. Гильберт – «в математике не может  быть неразрешимых проблем», в связи  с этим формулировка проблем Гильбертом на конгрессе 1900 года в Париже была руководством к действию, констатацией отсутствия решений в данный момент.

    Первой  фундаментальной теоретической  работой, связанной с доказательством  алгоритмической неразрешимости, была работа Курта Гёделя – его известная  теорема о неполноте символических  логик. Это была строго формулированная  математическая проблема, для которой  не существует решающего ее алгоритма. Усилиями различных исследователей список алгоритмически неразрешимых проблем  был значительно расширен. Сегодня  принято при доказательстве алгоритмической  неразрешимости некоторой задачи сводить  ее к ставшей классической задаче – «задаче останова».

    Имеет место быть следующая теорема:

    Теорема 3.1. Не существует алгоритма (машины Тьюринга), позволяющего по описанию произвольного алгоритма и его исходных данных (и алго-ритм и данные заданы символами на ленте машины Тьюринга) определить, останавливается ли этот алгоритм на этих данных или работает бесконечно.

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

    Тем не менее, можно попытаться сформулировать причины, ведущие к алгоритмической  неразрешимости, эти причины достаточно условны, так как все они сводимы  к проблеме останова, однако такой  подход позволяет более глубоко  понять природу алгоритмической  неразрешимости:

    а) Отсутствие общего метода решения задачи

    Проблема 1 : Распределение девяток в записи числа ;

    Определим функцию f(n) = i, где n – количество девяток  подряд в десятичной записи числа  , а i – номер самой левой девятки из n девяток подряд: =3,141592… f(1) = 5.

    Задача  состоит в вычислении функции f(n) для произвольно заданного n.

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

    Проблема 2: Вычисление совершенных чисел;

    Совершенные числа – это числа, которые  равны сумме своих делителей, например: 28 = 1+2+4+7+14.

    Определим функцию S(n) = n-ое по счёту совершенное  число и поставим задачу вычисления S(n) по произвольно заданному n. Нет  общего метода вы-числения совершенных  чисел, мы даже не знаем, множество совершенных  чи-сел конечно или счетно, поэтому  наш алгоритм должен перебирать все  числа подряд, проверяя их на совершенность. Отсутствие общего метода решения не позволяет ответить на вопрос о останове алгоритма. Если мы проверили М чи-сел  при поиске n-ого совершенного числа  – означает ли это, что его вообще не существует?

    Проблема 3: Десятая проблема Гильберта;

    Пусть задан многочлен n-ой степени с  целыми коэффициентами – P, су-ществует ли алгоритм, который определяет, имеет  ли уравнение P=0 решение в целых  числах?

    Ю.В. Матиясевич показал, что такого алгоритма  не существует, т.е. отсутствует общий  метод определения целых корней уравнения P=0 по его целочисленным  коэффициентам.

    б) Информационная неопределенность задачи

    Проблема 4: Позиционирование машины Поста на последний помеченный ящик;

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

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

    в) Логическая неразрешимость (в  смысле теоремы Гёделя о неполноте)

    Проблема 5: Проблема «останова» (см. теорема 3.1);

    Проблема 6: Проблема эквивалентности алгоритмов;

    По  двум произвольным заданным алгоритмам (например, по двум машинам Тьюринга) определить, будут ли они выдавать одинаковые выходные результаты на любых  исходных данных.

    Проблема 7: Проблема тотальности;

    По  произвольному заданному алгоритму  определить, будет ли он останавливаться  на всех возможных наборах исходных данных. Другая формулировка этой задачи – является ли частичный алгоритм Р всюду определённым?

    4.2 Проблема соответствий  Поста над алфавитом 

    В качестве более подробного примера  алгоритмически неразрешимой задачи рассмотрим проблему соответствий Поста (Э. Пост, 1943 г.). Мы выделили эту задачу, поскольку  на первый взгляд она выглядит достаточно «алгоритмизуемой», однако она сводима  к проблеме останова и является алгоритмически неразрешимой.

    Постановка  задачи:

    Пусть дан алфавит  : | | >= 2 (для односимвольного алфавита задача имеет решение) и дано конечное множество пар из х , т.е. пары непустых цепочек произвольного языка над алфавитом : , ……, .

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

    В качестве примера рассмотрим = {a,b}

    1. Входные цепочки: (abbb, b), (a, aab), (ba, b)

    Решающая  последовательность для этой задачи имеет вид:

    (a,aab) (a,aab) (ba,b) (abbb,b), так как : a a ba abbb aab aab b b

    2. Входные цепочки: (ab,aba), (aba,baa), (baa,aa)

    Данная  задача вообще не имеет решения, так  как нельзя начинать с пары (aba,baa) или (baa,aa), поскольку не совпадают начальные символы подцепочек, но если начинать с цепочки (ab,aba), то в последующем не будет совпадать общее количество символов «а», т.к. в других двух парах количество символов «а» одинаково.

    В общем случае мы можем построить  частичный алгоритм, основанный на идее упорядоченной генерации возможных  последовательностей цепочек (отметим, что мы имеем счетное множество  таких последовательностей) с проверкой  выполнения условий задачи. Если последовательность является решающей – то мы получаем результативный ответ за конечное количество шагов. Поскольку общий метод  определения отсутствия решающей последовательности не может быть указан, т.к. задача сводима к проблеме «останова» и, следовательно, является алгоритмически неразрешимой, то при отсутствии решающей последовательности алгоритм порождает бесконечный цикл.

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

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

    Список   литературы:

1. Томас Х. Кормен, Чарльз И. Лейзерсон, Рональд Л. Ривест, Клиффорд Штайн Алгоритмы: построение и анализ = INTRODUCTION TO ALGORITHMS — 2-е изд. — М.:, 2006. — С. 1296.
2. Дональд Кнут Искусство программирования, том 1. Основные алгоритмы = The Art of Computer Programming, vol.1. Fundamental Algorithms — 3-е изд. — М.:, 2006. — С. 720.
3. Колмогоров А. Н. Теория информации и теория алгоритмов. — М.: Наука, 1987. — 304 с.
4. Марков А. А., Нагорный Н. М. Теория алгорифмов, изд. 2. — М.: ФАЗИС, 1996.