Меню

Проблема определения понятия алгоритм

Алгоритм. Его виды и свойства

Презентация к уроку

Цель урока: Формирования у учащихся правильного понимания алгоритмов, их свойств, видов и практических навыков составления алгоритмов.

Дидактические: Обеспечить условия:

  • для изучения и закрепления основных понятия по теме;
  • для усвоения, закрепления темы.

Воспитательные: Обеспечить условия:

  • для воспитания чувства коллективизма и взаимопомощи, культуры общения;
  • для критического отношения к своему труду, умение оценивать его.

Развивающие: Обеспечить условия:

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

Демонстрационный материал к уроку:

  1. Мультимедийная презентация
  2. Портрет Мухаммеда Бен Муссы аль-Хорезми.

Ход урока

  1. Организационный момент. (2 мин.)
  2. Актуализация знаний. Постановка учебной задачи. (3 мин.)
  3. Изложение нового материала. (30 мин.)
  4. Закрепление нового материала (10 мин.)

Понятие алгоритма

Появление алгоритмов связывают с зарождением математики.

Более 1000 лет назад (825 г.)ученый из города Хорезма Абдулла (или Абу Ждафар) Мухаммед бен Мусса аль-Хорезми создал книгу по математике, в тором описал способы выполнения арифметических действий над многозначными числами.

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

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

Свойства алгоритма

  1. Дискретность
  2. Детерминированность
  3. Массовость
  4. Результативность
  5. Конечность
  6. Дискретность (от лат. Discretus–разделенный , прерывистый) – это свойство предполагает, что любой алгоритм должен состоять из последовательности шагов, следующих друг за другом.
  7. Детерминированность (от лат. Determinate – определенность, точность) — это свойство указывает, что любое действие в алгоритме должно быть строго и недвусмысленно определенно и описано для каждого случая.
  8. Массовость – это свойство подразумевает, что один и тот же алгоритм может применяться для решения целого класса задач, отличающихся исходными данными.
  9. Результативность (конечность) алгоритма — исполнение алгоритма должно закончиться за конечное число шагов.

Словесный способ записи алгоритмов представляет собой описание последовательных этапов обработки данных. Алгоритм задается в произвольном изложении на естественном языке.

Пример: Алгоритм «Зарядка»

  1. Потянитесь, лежа в постели.
  2. Сядьте на кровати, поставив ноги на пол.
  3. Нагнитесь вперед, пытаясь достать руками пальцы ног.
  4. Выгните спину дугой.
  5. Сосчитайте до 10.
  6. Вернитесь в исходное положение.

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

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

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

  1. Ввести значения а и х.
  2. Сложить х и 6.
  3. Умножить а на 2.
  4. Вычесть из 2а сумму (х+6).
  5. Вывести у как результат вычисления выражения.

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

Виды алгоритма

Линейный алгоритм – это такой, в котором все операции выполняются

последовательно одна за другой.

Пример: Алгоритм посадки дерева.

  1. Выкопать в земле ямку;
  2. Опустить в ямку саженец;
  3. Засыпать ямку с саженцем землей;
  4. Полить саженец водой.

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

Если , то , иначе

Пример: Если на улице дождь, то останемся дома, а если нет то идем гулять.

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

Цикл с известным числом повторений

Цикл с известным числом повторений часто называют «циклом ДЛЯ»

Пример: Алгоритм «Упражнение для глаз»

  1. Возьмите карандаш.
  2. Установите его в исходное положение у кончика носа
  3. Повторите 10 раз, следя за движение карандаша:
    • Переместите карандаш на расстояние вытянутой руки;
    • Верните карандаш в исходное положение
  4. Положите карандаш
  5. Конец алгоритма

Цикл с постусловием

Цикл с неизвестным числом повторений, в тором выход из цикла осуществляется при выполнении условия, принято называть «циклом с постусловием» или «циклом ПРИ»

  1. Удобно положите левую руку ладонью вверх.
  2. Два пальца правой руки положите на запястье левой руки.
  3. Заметьте положение секундной стрелки
  4. Сосчитайте очередной удар
  5. Посмотрите на часы
  6. Если секундная стрелка прошла полный круг, то закончите действия, иначе перейдите к п.4

Цикл с предусловием

Цикл с известным числом повторений, в котором цикл продолжается, пока выполняется условие, принято называть «циклом с предусловием» или «циклом ПОКА»

  1. Подойдите к бочке
  2. Если бочка неполна (есть место для воды) , то перейдите к п.3, иначе конец алгоритма.
  3. Наберите ведро воды
  4. Вылейте ведро в бочку
  5. Перейдите к п.2.

Источник



АЛГОРИТМ

АЛГОРИТМ – система правил, сформулированная на понятном исполнителю языке, которая определяет процесс перехода от допустимых исходных данных к некоторому результату и обладает свойствами массовости, конечности, определенности, детерминированности.

Слово «алгоритм» происходит от имени великого среднеазиатского ученого 8–9 вв. Аль-Хорезми (Хорезм – историческая область на территории современного Узбекистана). Из математических работ Аль-Хорезми до нас дошли только две – алгебраическая (от названия этой книги родилось слово алгебра) и арифметическая. Вторая книга долгое время считалась потерянной, но в 1857 в библиотеке Кембриджского университета был найден ее перевод на латинский язык. В ней описаны четыре правила арифметических действий, практически те же, что используются и сейчас. Первые строки этой книги были переведены так: «Сказал Алгоритми. Воздадим должную хвалу Богу, нашему вождю и защитнику». Так имя Аль-Хорезми перешло в Алгоритми, откуда и появилось слово алгоритм. Термин алгоритм употреблялся для обозначения четырех арифметических операций, именно в таком значении он и вошел в некоторые европейские языки. Например, в авторитетном словаре английского языка Webster’s New World Dictionary, изданном в 1957, слово алгоритм снабжено пометкой «устаревшее» и объясняется как выполнение арифметических действий с помощью арабских цифр.

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

Проблема определения понятия «алгоритм».

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

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

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

Идея о существовании алгоритмически неразрешимых проблем оказалась верной, но для того, чтобы ее обосновать, необходимо было дать точное определение алгоритма. Попытки выработать такое определение привели к возникновению теории алгоритмов, в которую вошли труды многих известных математиков – К.Гедель, К.Черч, С.Клини, А.Тьюринг, Э.Пост, А.Марков, А.Колмогоров и многие другие.

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

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

Понятие «алгоритма».

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

Читайте также:  Смена председателя правления ТСЖ

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

Наличие исходных данных и некоторого результата.

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

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

Детерминированность.

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

Результативность.

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

Определенность.

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

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

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

Например, описание алгоритма Евклида нахождения НОД (наибольшего общего делителя) двух целых положительных чисел может быть представлено в виде трех шагов. Шаг 1: Разделить m на n. Пусть p – остаток от деления.

Шаг 2: Если p равно нулю, то n и есть исходный НОД.

Шаг 3: Если p не равно нулю, то сделаем m равным n, а n равным p. Вернуться к шагу 1.

Приведенная здесь запись алгоритма нахождения НОД очень упрощенная. Запись, данная Евклидом, представляет собой страницу текста, причем последовательность действий существенно сложней.

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

На рисунке представлена блок-схема алгоритма нахождения НОД:

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

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

Приведенное определение алгоритма нельзя считать представленным в привычном математическом смысле. Математические определения фигур, чисел, уравнений, неравенств и многих других объектов очень четки. Каждый математически определенный объект можно сравнить с другим объектом, соответствующим тому же определению. Например, прямоугольник можно сравнить с другим прямоугольником по площади или по длине периметра. Возможность сравнения математически определенных объектов – важный момент математического изучения этих объектов. Данное определение алгоритма не позволяет сравнивать какие-либо две таким образом определенные инструкции. Можно, например, сравнить два алгоритма решения системы уравнений и выбрать более подходящий в данном случае, но невозможно сравнить алгоритм перехода через улицу с алгоритмом извлечения квадратного корня. С этой целью нужно формализовать понятие алгоритма, т.е. отвлечься от существа решаемой данным алгоритмом задачи, и выделить свойства различных алгоритмов, привлекая к рассмотрению только его форму записи. Задача нахождения единообразной формы записи алгоритмов, решающих различные задачи, является одной из основных задач теории алгоритмов. В теории алгоритмов предполагается, что каждый шаг алгоритма таков, что его может выполнить достаточно простое устройство (машина), Желательно, чтобы это устройство было универсальным, т.е. чтобы на нем можно было выполнять любой алгоритм. Механизм работы машины должен быть максимально простым по логической структуре, но настолько точным, чтобы эта структура могла служить предметом математического исследования. Впервые это было сделано американским математиком Эмилем Постом в 1936 (машина Поста) еще до создания современных вычислительных машин и (практически одновременно) английским математиком Аланом Тьюрингом (машина Тьюринга).

История конечных автоматов: машина Поста и машина Тьюринга.

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

В 1935 американский математик Пост опубликовал в «Журнале символической логики» статью Финитные комбинаторные процессы, формулировка 1. В этой статье и появившейся одновременно в Трудах Лондонского математического общества статье английского математика Тьюринга О вычислимых числах с приложением к проблеме решения были даны первые уточнения понятия «алгоритм». Важность идей Поста состоит в том, что был предложен простейший способ преобразования информации, именно он построил алгоритмическую систему (алгоритмическая система Поста). Пост доказал, что его система обладает алгоритмической полнотой. В 1967 профессор В.Успенский пересказал эти статьи с новых позиций. Он ввел термин «машина Поста». Машина Поста – абстрактная машина, которая работает по алгоритмам, разработанным человеком, она решает следующую проблему: если для решения задачи можно построить машину Поста, то она алгоритмически разрешима. В 1970 машина Поста была разработана в металле в Симферопольском университете. Машина Тьюринга была построена в металле в 1973 в Малой Крымской Академии Наук.

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

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

Читайте также:  Должностная инструкция чем регламентирована ее наличие

Современный взгляд на алгоритмизацию.

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

Источник

АЛГОРИТМ

АЛГОРИТМ — предписание (система правил), определяющее содержание и последовательность операций, обеспечивающих решение задач определенного класса.

Термин «алгоритм» происходит от имени средневекового узбекского математика Аль-Хорезми, который еще в 9 веке сформулировал правила выполнения четырех арифметических действий.

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

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

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

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

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

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

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

Разработка Алгоритма представляется целесообразной там, где возникает необходимость стандартизации действия: напр., при обработке историй болезни, каких-либо объективно снятых кривых (температурных графиков, энцефалограмм, ЭКГ и так далее) или при попытках формализовать (в данном случае описать) процесс постановки диагноза (см. Диагноз, диагностика).

Библиография: Айзерман М. А. и др. Логика, Автоматы, Алгоритмы, М., 1963; Ляпунов А. А. и Шестопал Г. А. Об алгоритмическом описании процессов управления, в кн.: Математ. просвещение, под ред. Я. С. Дубнова и др., в. 2, с. 81, М., 1957; Трахтенброт Б. А. Алгоритмы и машинное решение задач, М., 1957.

Источник

Алгоритм

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

Формальные свойства алгоритмов [в явной или неявной форме] включают следующий ряд общих требований:

  1. Дискретность (разделённость на части) и упорядоченность. Алгоритм должен состоять из отдельных действий, которые выполняются последовательно друг за другом.
  2. Детерминированность (однозначная определённость). Многократное применение одного алгоритма к одному и тому же набору исходных данных всегда даёт один и тот же результат.
  3. Формальность. Алгоритм не должен допускать неоднозначности толкования действий для исполнителя.
  4. Результативность и конечность. Работа алгоритма должна завершаться за определённое число шагов, при этом задача должна быть решена.
  5. Массовость. Определённый алгоритм должен быть применим ко всем однотипным задачам.

Предписание алгоритма, как правило, фиксируется (записывается) в виде текста некотором формализованном языке (см. Язык формализованный), называемого программой. Понятие программы формулируется в чисто структурных терминах синтаксиса этого языка, без какого-либо обращения к смысловым категориям. Точно такой же характер носит и описание процедуры выполнения программы. Поэтому в роли исполнителя алгоритмов, записанных на формализованных [алгоритмических] языках, может выступать не только человек, но и наделённое соответствующими [вычислительными] возможностями автоматическое устройство, машина. Универсальным исполнителем алгоритмов является компьютер. С его помощью возможно выполнять все основные виды алгоритмов. Возможность машинного осуществления алгоритмических процедур, и, соответственно, машинного решения задач, стимулировала развитие вычислительной техники и создание математической теории алгоритмов. В современной науке теория алгоритмов является основой конструктивного направления в математике и логике, а также выступает одной из базисных дисциплин в области вычислительной техники и программирования, машинного решения разнообразных задач, моделирования различных процессов и других областях.

Слово «алгоритм» происходит от имени арабского учёного IX века Мухамеда бен Мусы аль-Хорезми, который впервые описал правила выполнения арифметических действий в десятичной системе счисления, придуманной в Индии. Впоследствии термином «алгоритм» стали обозначать эти правила вычислений. Однако с течением времени понятие алгоритма постепенно расширялось, наряду с его экспансией из чистой математики в другие сферы, и в XX веке под ним стали понимать точную последовательность действий, приводящую к решению поставленной задачи, при условии, что эта задача является заведомо решаемой.

Алгоритм — одно из основных понятий математической логики (см. Логика математическая) и математики. Хотя неформально математики всё время занимались поиском алгоритмов, данное понятие было уточнено лишь в годах XX века. Первыми такими уточнениями были абстрактные определения частично-рекурсивных и представимых функций в формальной теории чисел, появившиеся в связи с задачами теории доказательств. В 1936 году Э. Пост и А. Тьюринг независимо друг от друга предложили понятия абстрактных вычислительных машин и указали, что любой алгоритм в интуитивном смысле слова может быть реализован на данных машинах, несмотря на кажущуюся примитивность их элементарных действий.

В машине Тьюринга памятью является потенциально бесконечная лента, в каждой клетке которой записан символ из заранее заданного конечного алфавита. Более того, достаточно рассматривать ленту, каждая клетка которой содержит один бит информации, то есть либо пуста, либо содержит символ |. Процессор машины Тьюринга состоит из головки (каретки), которая в любой момент обозревает одну клетку, и программы, состоящей из конечного числа команд, обычно нумеруемых натуральными числами. Каждая команда представляет собой условное действие, зависящее от символа, записанного в клетке. Это действие имеет вид совокупности элементарных инструкций формы ab (L, R, S) i, в которой присутствует лишь одна из букв L, R, S. Буква L означает приказ сдвинуться на следующем такте на одну клетку влево, R — вправо, S — остаться на месте. Элементарная инструкция означает следующее: если машина видит a, записать в клетку b, передвинуться в соответствии с командой и перейти к исполнению команды i. Такая элементарность действий машины стала результатом проведённого Тьюрингом методологического анализа элементарных действий человека по исполнению алгоритмов.

Читайте также:  Vacmaster VQ1220PF Operator s Manual

Машина Поста представляет собой универсальный исполнитель, позволяющий вводить начальные данные и читать результат выполнения программы. В машине имеются регистры, содержащие натуральные числа, элементарные операции увеличения и уменьшения числа на 1 и условный переход, если число в регистре равно . Машина Поста состоит из: а) бесконечной ленты, поделённой на одинаковые ячейки-секции (ячейка может быть пустой [ или пустота] или содержать метку [1 или любой другой знак]; б) головки (каретки), способной передвигаться по ленте на одну ячейку в ту или иную сторону, а также способной проверять наличие метки, стирать и записывать метку. Состояние машины Поста описывается состоянием ленты и положением каретки. Состояние ленты — это информация о том, какие секции пусты, а какие отмечены. Шаг — это движение каретки на одну ячейку влево или вправо. Состояние ленты может изменяться в процессе выполнения программы. Элементарные действия (команды) машина Поста проще команд машины Тьюринга, поэтому программы для машины Поста имеют большее число команд, чем аналогичные программы для машины Тьюринга. Команды машины Поста предвосхитили систему команд современных вычислительных машин.

Одновременно А. Чёрч и X. Б. Карри создали одно из самых абстрактных уточнений алгоритма: λ-определимость, выразимость с помощью терма комбинаторной логики (см. Логика комбинаторная). Выяснилось, что и ранее созданные теоретические понятия, и самые элементарные, и самые абстрактные, из вновь появившихся уточнений алгоритма оказались эквивалентны. Этот факт, подтверждённый в дальнейшем для всех вновь появлявшихся точных определений алгоритма, послужил основой утверждения, скромно называемого в математике тезисом Чёрча, хотя степень его подтверждённости ныне выше, чем у любого физического «закона». Содержательное понятие алгоритма эквивалентно по объёму любому из имеющихся в данный момент математических уточнений этого понятия, в частности вычислимости на машине Тьюринга.

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

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

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

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

Множество, характеристическое свойство которого является всюду определённым вычислимым предикатом, называется разрешимым. Множество, принадлежность элемента которому можно установить за конечное число шагов применением некоторого алгоритма, называется перечислимым. Например, множество тавтологий классической логики высказываний (см. Логика высказываний) разрешимо, а множество тавтологий классической логики предикатов (см. Логика предикатов) перечислимо. Следует отметить, что в случае перечислимого множества алгоритмически установить можно лишь истинность, а не ложность. В классической математике имеет место следующий критерий разрешимости: множество разрешимо, если и оно, и его дополнение перечислимы. В конструктивной математике этот критерий эквивалентен принципу Маркова. Другая характеризация перечислимого множества — множество объектов, выводимых в некотором исчислении.

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

Например, определение алгоритма может быть записано как слово в некотором алфавите, а если взять определение алгоритма, в котором рассматриваются лишь натуральные числа, такое слово может быть естественно представлено как число в системе счисления, основанием которой является количество букв в алфавите. Тогда имеется универсальный алгоритм U, перерабатывающий любую пару (ϕ, P), где ϕ — конструктивный объект, называемый записью или программой (относительно U) алгоритма ϕ, в результат применения ϕ к P. Универсальный алгоритм не может быть всюду определён. Если рассматривать лишь конструктивные объекты, то алгоритм естественно отождествить с его программой относительно некоторого U. То, что такое отождествление является ограниченным, показывают проблемы современной теории и практики программирования. Одной из самых трудных возникающих в этом случае проблем является восстановление алгоритма по реализующей его конкретной программе. Если понятие алгоритма, перерабатывающего реальные конструктивные объекты, можно считать однозначно определённым, то его обобщение на объекты высших типов допускает многочисленные варианты, неэквивалентные друг другу.

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

На основе теории сложности А. Н. Колмогоров, Л. А. Левин, П. Мартин-Лёф и другие развили алгоритмическую теорию вероятностей. Основой данной теории явилось содержательное определение случайной последовательности по Р. Мизесу. Двоичная последовательность случайна, если из неё нельзя выбрать никакую последовательность с другой частотой нулей и единиц. Например, последовательность , 1, , 1… неслучайна, поскольку последовательность её чётных членов состоит из одних единиц. В классической математике такое определение пусто. А. Н. Колмогоров уточнил его, предложив рассматривать лишь алгоритмические перестановки подмножеств членов данной последовательности. Оказалось, что случайность связана со сложностью определения. Сложность фрагментов случайной последовательности пропорциональна длине их записи. Итак, содержательно случайные объекты являются приближениями к случайным последовательностям. Для любой совокупности программ, имеющих ограниченную сложность, можно построить ограниченный универсальный алгоритм, исполняющий все их без ошибок, но его сложность будет неизмеримо выше, чем сложность исполняемых программ. Далее, возможно построить алгоритмический процесс, расширяющий ограниченный универсальный алгоритм с тем, чтобы включить любую предъявленную программу, не входящую в данный класс, но при этом сложность универсального метода станет ещё выше. Уже один шаг данного процесса диагонализации далеко выводит за рамки класса функций, считающихся реально вычислимыми.

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

Источник