Способы формализации понятия алгоритма

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

— алгоритм должен быть единым для всех допустимых исходных данных, т.е. удовлетворять требованию универсальности;

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

Источник

Задачи по Python с решениями

Свежие записи

Подходы к формализации понятия «алгоритм»

На этом шаге мы рассмотрим подходы к формализации понятия «алгоритм».

Теперь нужно предложить способ
описания шагов алгоритма. Известно несколько подходов к формализации понятия
«алгоритм»:

• теория конечных и бесконечных автоматов;
• теория вычислимых (рекурсивных) функций;
• лямбда-исчисление Черча.

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

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

На следующем шаге мы рассмотрим принципы работы машины Поста.

Источник

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

Ранее были сформулированы основные требования к алгоритмам. Однако понятия, использованные в этих формулировках (такие, как ясность, четкость, элементарность), сами нуждаются в уточнении. Алгоритмы в интуитивном смысле не являются математическими объектами, к ним неприменимы формальные методы исследования и доказательства. Поэтому в XX веке были предприняты попытки формализации понятия алгоритма. Формализа­ция понятия алгоритма необходима по разным причинам. Например, сравнение двух алгоритмов по эффективности, проверка их эквивалентности и т. д. возможны только на основе их формального представления.

Впервые необходимость формального понятия алгоритма возникла в связи с проблемой алгоритмической неразрешимости некоторых задач. Долгое время математики верили в возможность того, что все строго поставленные математические задачи могут быть алгоритмически решены, нужно только найти алгоритм их решения. Вера в универсальность алгоритмических методов была подорвана работой Курта Геделя (1931 год), в которой было показано, что некоторые математические проблемы не могут быть решены с помощью алгоритмов из некоторого класса. Этот класс алгоритмов определяется некоторой формальной конкретизацией понятия алгоритма. Встал вопрос: являются ли алгоритмически неразрешимыми эти проблемы только в рамках использованной Геделем модели алгоритма или же для решения этих проблем вообще нельзя придумать никакого алгоритма ни в каком смысле? Общность результата Геделя зависит от того, совпадает ли использованный им класс алгоритмов с классом всех алгоритмов в интуитивном смысле. Поэтому поиск и анализ различных уточнений и формализации алгоритма и соотношение этих формализаций с интуитивным понятием алгоритма является практически важным.

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

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

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

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

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

Источник

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

Презентация использовалась на занятиях профессионального модуля в ОПК СТИ НИТУ МИСиС

Содержимое разработки

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

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

• Для каждого алгоритма есть некоторое множество объектов, допустимых в качестве исходных данных.

• Массовость;
• Детерминированность;
• Результативность;
• Определенность.

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

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

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

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

Формы представления алгоритмов.

• Одним из распространенных способов записи алгоритмов является запись на языке блок-схем. Запись представляет собой набор элементов (блоков), соединенных стрелками. Каждый элемент – это «шаг» алгоритма. Элементы блок-схемы делятся на два вида. Элементы, содержащие инструкцию выполнения какого-либо действия, обозначают прямоугольниками, а элементы, содержащие проверку условия – ромбами. Из прямоугольников всегда выходит только одна стрелка (входить может несколько), а из ромбов – две (одна из них помечается словом «да», другая – словом «нет», они показывают, соответственно, выполнено или нет проверяемое условие).

Формализация понятия алгоритма. Теория алгоритмов

• В теории алгоритмов предполагается, что каждый шаг алгоритма таков, что его может выполнить достаточно простое устройство (машина), Желательно, чтобы это устройство было универсальным, т.е. чтобы на нем можно было выполнять любой алгоритм. Механизм работы машины должен быть максимально простым по логической структуре, но настолько точным, чтобы эта структура могла служить предметом математического исследования. Впервые это было сделано американским математиком Эмилем Постом в 1936 (машина Поста) еще до создания современных вычислительных машин и (практически одновременно) английским математиком Аланом Тьюрингом (машина Тьюринга).

Теория алгоритмов (Продолжение)

• История конечных автоматов: машина Поста и машина Тьюринга. Машина Поста – абстрактная вычислительная машина, предложенная Постом (Emil L.Post), которая отличается от машины Тьюринга большей простотой. Обе машины «эквивалентны» и были созданы для уточнения понятия «алгоритм».

• Абстрактная машина Поста представляет собой бесконечную ленту, разделенную на одинаковые клетки, каждая из которых может быть либо пустой, либо заполненной меткой «V». У машины есть головка, которая может перемещаться вдоль ленты на одну клетку вправо или влево, наносить в клетку ленты метку, если этой метки там ранее не было, стирать метку, если она была, либо проверять наличие в клетке метки. Информация о заполненных метками клетках ленты характеризует состояние ленты, которое может меняться в процессе работы машины. В каждый момент времени головка находится над одной из клеток ленты и, как говорят, обозревает ее. Информация о местоположения головки вместе с состоянием ленты характеризует состояние машины Поста.

Машина поста (продолжение)

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

Машина поста (продолжение)

• Машина Тьюринга состоит из счетной ленты (разделенной на ячейки и ограниченной слева, но не справа), читающей и пишущей головки, лентопротяжного механизма и операционного исполнительного устройства, которое может находиться в одном из дискретных состояний q0, q1, …, qs , принадлежащих некоторой конечной совокупности (алфавиту внутренних состояний), при этом q0 называется начальным состоянием. Читающая и пишущая головка может читать буквы рабочего алфавита A = , стирать их и печатать.
• Каждая ячейка ленты в каждый момент времени занята буквой из множества А. Чаще всего встречается буква а0 – «пробел».
• Головка находится в каждый момент времени над некоторой ячейкой ленты – текущей рабочей ячейкой.
• Лентопротяжный механизм может перемещать ленту так, что головка оказывается над соседней ячейкой ленты, при этом возможна ситуация выхода за левый край ленты, которая является аварийной (недопустимой), или машинного останова, когда машина выполняет предписание об остановке

Основные элементы блок-схем

Существует несколько способов записи алгоритмов.

Алгоритм может быть записан на

• естественном языке
• в виде блок-схемы
• на алгоритмическом языке

Перечень основных элементов блок-схем

требования к алгоритму

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

• Наличие ввода исходных данных.
• Наличие вывода результата выполнения.
• Однозначность (компьютер «понимает» только однозначные инструкции).

требования к алгоритму

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

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

Несмотря на многообразие алгоритмов все они строятся из 3-х типов алгоритмических структур.

Линейным алгоритмом называется алгоритмом, в котором все указанные в последствии действия исполняются и притом только один раз.

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

Циклический алгоритм – алгоритм в котором какая-то совокупность действий повторяется несколько раз при изменяющихся значениях параметра.

Принципы разработки алгоритмов

Типы алгоритмических процессов

По структуре выполнения алгоритмы и программы делятся на три вида:

• Линейные
• Ветвящиеся
• Циклические

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

Алгоритмы разветвляющейся структуры

• В разветвляющихся алгоритмах выбор направления продолжения вычисления осуществляется по итогам проверки заданного условия.

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

• Существуют две схемы циклических вычислительных процессов.

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

Алгоритм любой сложности может быть представлен комбинацией трех базовых структур:

• следование;
• ветвление (в полной и сокращенной форме);
• цикл (с предусловием или постусловием).

Характерной особенностью этих структур является наличие у них одного входа и одного выхода.

• Построить алгоритмы к следующим задачам:

• Даны три точки на плоскости, заданные своими координатами. Определить ближайшие из них.
• Дан ряд чисел a, b, c. Найти сумму отрицательных чисел.
• Даны x, y, z. Вычислить a и b, если a=(x-2)*y, b=(z+x)/y.

Источник