🗊Презентация Уточнение понятия алгоритм и его формализации

Уточнение понятия алгоритм и его формализации

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

Каждый алгоритм служит для решения некоторого класса задач. Каждый алгоритм служит для решения некоторого класса задач. Задачи должны быть записаны на некотором языке. Результат применения алгоритма– решение задачи– также должен быть записан на вполне определенном языке. Таким образом, в процессе выполнения алгоритма текст задачи преобразуется в текст ее решения.

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

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

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

Массовость алгоритма. Начальное выражение может выбираться из некоторого потенциально бесконечного множества. Иначе говоря, алгоритм должен обеспечивать решение некоторому множеству (классу) задач с различными параметрами (коэффициентами).

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

Основная задача теории алгоритмов – это решение проблемы алгоритмической разрешимости, а не поиск правила (способа/метода) ее решения. Основная задача теории алгоритмов – это решение проблемы алгоритмической разрешимости, а не поиск правила (способа/метода) ее решения. Теория алгоритмов дает ответ на вопрос «Данная задача имеет решение?», и не отвечает на вопрос «Как решается данная задача?»

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

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

Третье направление связано с понятием нормальных алгоритмов, введенным и разработанным российским математиком А. А. Марковым. Это направление получило название нормальные алгоритмы Маркова.

Третье направление связано с понятием нормальных алгоритмов, введенным и разработанным российским математиком А. А. Марковым. Это направление получило название нормальные алгоритмы Маркова.

Частично рекурсивные функции

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

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

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

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

Если функция определена на собственном подмножестве множества Если функция определена на собственном подмножестве множества то будем называть ее частично рекурсивной.

Определим простейшие функции и элементарные операции над функциями.

Элементарные операции над частичными функциями. 1. Суперпозиция(или композиция). Пусть даны частичная функция и частичные функции

В противном случае функция считается неопределенной. Для функции полученной суперпозицией функций В противном случае функция считается неопределенной. Для функции полученной суперпозицией функций будем использовать обозначение

Примеры.

2.Рекурсия Начнем с частных случаев. Пусть заданы функция и число a. Уравнения: однозначно определяют функцию

Последовательно вычисляя, находим: Последовательно вычисляя, находим:

3. Минимизация.

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

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

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

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

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

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

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

Подмножество множества натуральных чисел называется разрешимым, если его характеристическая функция рекурсивна.

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

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

Утверждение: Всякое непустое разрешимое множество M является перечислимым. Доказательство. Определим перечисляющую функцию f. Пусть m– произвольный элемент множества M. Определяем по рекурсии:

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

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

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

Это определение дает алгоритм вычисления значений функции . В соответствии с тезисом Черча, функция частично рекурсивна, и, значит, общерекурсивна, поскольку функция определена для любого . Значит, функция должна получить свой номер при перечислении с помощью . Это определение дает алгоритм вычисления значений функции . В соответствии с тезисом Черча, функция частично рекурсивна, и, значит, общерекурсивна, поскольку функция определена для любого . Значит, функция должна получить свой номер при перечислении с помощью .

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

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

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

Теорема Райса утверждает, что по номеру алгоритма нельзя узнать, периодична ли, например, функция, вычисляемая в соответствии с этим алгоритмом.

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

Идею такой машины предложил в 1937 году английский математик А. Тьюринг.

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

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

Операторы перемещения Т={Л, П, Н}. Л, П, Н – это символы сдвига «влево», «вправо» и «на месте». Операторы перемещения Т={Л, П, Н}. Л, П, Н – это символы сдвига «влево», «вправо» и «на месте». Бесконечная лента Бесконечная лента характеризует память машины. Она разбита на клеточки. В каждую клеточку может быть записан только один символ из внешнего алфавита.

Управляющая головка. Управляющая головка (УГ) передвигается вдоль ленты и может останавливаться напротив какой-либо клетки, т. е. считывать символ

Логическое устройство. В зависимости от текущего внутреннего состояния, и считанного с ленты символа, переходит в новое внутренне состояние, и «премещает» управляющую головку.

Программа машины Тьюринга (Р) - совокупность всех команд, Программа представляется в виде таблицы и называется Тьюринговой функциональной схемой. Программа машины Тьюринга (Р) - совокупность всех команд, Программа представляется в виде таблицы и называется Тьюринговой функциональной схемой. Например:

Таким образом, машина Тьюринга может быть представлена в виде четверки:

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

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

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

ПРИМЕР Построим машину Тьюринга, которая будет стирать последнюю единицу в последовательности единиц.

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

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

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

Проверим работоспособность машины Тьюринга: Проверим работоспособность машины Тьюринга:

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

Нормальные алгоритмы Маркова Нормальный алгоритм Маркова представляет собой систему подстановок

Слово z считается включенным в слово у, если у может быть представлено как:

Работа нормального алгоритма Маркова: Исходное слово просматривается слева направо с целью выявления вхождения первого правила подстановки. Как только находится первое вхождение первого правила подстановки, оно заменяется по этому правилу и исходное слово снова просматривается с первого символа по первому правилу подстановки.

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

ПРИМЕР ПРИМЕР Построить нормальный алгоритм Маркова, стирающий последовательность единиц. Нормальный алгоритм Маркова для данной задачи представляет собой две подстановки :

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

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

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