Понятие алгоритма. Его свойства.

Понятие алгоритма. Его свойства.

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

Такими свойствами являются:

• Дискретность (прерывность, раздельность) – алгоритм должен представлять процесс решения задачи как последовательное выполнение простых (или ранее определенных) шагов. Каждое действие, предусмотренное алгоритмом, исполняется только после того, как закончилось исполнение предыдущего.

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

• Результативность (конечность) – алгоритм должен приводить к решению задачи за конечное число шагов.

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

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

Маши́на Тью́ринга (МТ) — абстрактный исполнитель (абстрактная вычислительная машина). Была предложена Аланом Тьюрингом в 1936 годудля формализации понятия алгоритма.

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

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

Что собой представляет машина Тьюринга?

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

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

Вычислимые по Тьюрингу функции

Будем рассматривать функции f от одной или нескольких переменных, заданных на множестве N = {0, 1, 2, …, n, …} натуральных чисел или его подмножествах (частичные функции) и принимающие значения на множестве N. Определение 5.8. Функция f(x1, x2, …, xn) называется вычислимой, если существует алгоритм, позволяющий вычислять ее значения для тех переменных, для которых она определена, и работающий бесконечно, если функция для данного набора переменных не определена.

Определение 5.9. Функция f(x1, x2, …, xn) называется вычислимой по Тьюрингу, если существует машина Тьюринга, вычисляющая эту функцию.

Тезис Тьюринга (Основная гипотеза теории алгоритмов).

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

Правильная вычислимость функций на машине Тьюринга.

Определение 1. Будем говорить, что машина Тьюринга пра­вильно вычисляет функцию f(x1, x2,..., хп),, если начальное слово она переводит в слово и при этом в процессе работы не пристраивает к начальному слову но­вых ячеек на ленте ни слева, ни справа. Если же функция f не определена на данном наборе значений аргументов, то, начав работать из указанного положения, она никогда в процессе рабо­ты не будет надстраивать ленту слева.

Пример 1. Приведем программы машин Тьюринга, пра­вильно вычисляющих функции S(x) = х+ 1 и 0(х) = 0. Функция S(x) =х+ 1 осуществляет перевод: q101x0 => q001x+1. Ее программа:q10→ q2 П; q21→ q21 П; q20→ q31; q31→ q31 Л; q30→ q00. Функция O(x) = 0 осуществляет перевод: q101x0 => q000x+1. Ее программа: q10→ q2 0П; q21→ q21 П; q20→ q30Л; q31→ q40; q40→ q30Л, q30→ q00. Соответствующую машину Тьюринга обозна­чили О.

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

С математической точки зрения машина Тьюринга — просто определенный алгоритм для переработки слов. Операции композиции, выполняемые над алгоритмами, позволяют образовы-вать новые, более сложные алгоритмы из ранее известных простых алгоритмов. Поскольку машина Тьюринга—алгоритм, то операции композиции применимы и к машинам Тьюринга. Рассмотрим основные из них, а именно: произведение, возве-дение в степень, итерацию. Пусть заданы машины Тьюринга Т1 и Т2, имеющие какой-то общий внешний алфавит А = {а0, а1,..., аm} и внутренние алфавиты Q1 = {q0, q1,..., qn} и cоответственно Q2 = {q0,q1,…,qt}. Композитом, или произведением, машины Т1 на машину T2 будем называть машину Т с тем же внешним алфавитом А= {а0, а1,..., аm}, внутренним алфавитом Q = {q0, q1,...,qn, qn+1,...,qn+t} и программой, получающейся следующим образом. Во всех командах Т1 содержащих заключитель-ный символ q0, заменяем его на символ qn+1. Все остальные символы в командах T1 оставляем неизменными. В командах Т2, напротив, символ q0 оставляем неизменным, но зато каждый из остальных символов заменяем символом qn+j. Совокупность всех команд Т1 и Т2, измененных указанным способом, и будет программой композита или произведения машин T1 и T2.Произведение машины T1 на машину Т2 обозначается через Т = T1 • T2, или Т = T1 * Т2. Таким образом, машина Т есть произведение машин Т1 и T2, если последовательная работа этих двух машин эквивалентна работе одной машины Т.

Рекурсивные функции.

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

Функция Аккермана.

Функция Аккермана определяется рекурсивно для неотрицательных целых чисел и следующим образом:

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

Оператор минимизации.

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

Тезис Чёрча.

физический тезис Чёрча — Тьюринга: любая функция, которая может быть вычислена физическим устройством, может быть вычислена машиной Тьюринга;

Сильный тезис Чёрча — Тьюринга (тезис Чёрча — Тьюринга — Дойча): любой конечный физический процесс, не использующий аппарат, связанный с непрерывностью и бесконечностью, может быть вычислен физическим устройством.

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

Разрешимым называется множество целых чисел для которого существует алгоритм определения принадлежности ему некоторого элемента. Для разрешимого множества задаётсявычислимая и всюду определённая функция :

Естественно, наличие внутри символа принадлежности не означает, что мы пользуемся кем то заданным предикатом (получился бы порочный круг). Вместо " " стоит конечная последовательность символов некоторой программы, которая должна выдать не нулевое значение, тогда . Если же эта программа, или другая " " выдаёт ноль, то . Функция называется характеристической.

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

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

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

т.е. её значение равно -тому элементу множества.

Понятие алгоритма. Его свойства.

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

Такими свойствами являются:

• Дискретность (прерывность, раздельность) – алгоритм должен представлять процесс решения задачи как последовательное выполнение простых (или ранее определенных) шагов. Каждое действие, предусмотренное алгоритмом, исполняется только после того, как закончилось исполнение предыдущего.

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

• Результативность (конечность) – алгоритм должен приводить к решению задачи за конечное число шагов.

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

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

Маши́на Тью́ринга (МТ) — абстрактный исполнитель (абстрактная вычислительная машина). Была предложена Аланом Тьюрингом в 1936 годудля формализации понятия алгоритма.

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

Что способствует осуществлению желаний? Стопроцентная, непоколебимая уверенность в своем...

ЧТО ПРОИСХОДИТ, КОГДА МЫ ССОРИМСЯ Не понимая различий, существующих между мужчинами и женщинами, очень легко довести дело до ссоры...

Живите по правилу: МАЛО ЛИ ЧТО НА СВЕТЕ СУЩЕСТВУЕТ? Я неслучайно подчеркиваю, что место в голове ограничено, а информации вокруг много, и что ваше право...

ЧТО И КАК ПИСАЛИ О МОДЕ В ЖУРНАЛАХ НАЧАЛА XX ВЕКА Первый номер журнала «Аполлон» за 1909 г. начинался, по сути, с программного заявления редакции журнала...

Не нашли то, что искали? Воспользуйтесь поиском гугл на сайте: