Что такое определенность алгоритма
АЛГОРИТМ
АЛГОРИТМ – система правил, сформулированная на понятном исполнителю языке, которая определяет процесс перехода от допустимых исходных данных к некоторому результату и обладает свойствами массовости, конечности, определенности, детерминированности.
Слово «алгоритм» происходит от имени великого среднеазиатского ученого 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». У машины есть головка, которая может перемещаться вдоль ленты на одну клетку вправо или влево, наносить в клетку ленты метку, если этой метки там ранее не было, стирать метку, если она была, либо проверять наличие в клетке метки. Информация о заполненных метками клетках ленты характеризует состояние ленты, которое может меняться в процессе работы машины. В каждый момент времени головка находится над одной из клеток ленты и, как говорят, обозревает ее. Информация о местоположения головки вместе с состоянием ленты характеризует состояние машины Поста. Работа машины Поста заключается в том, что головка передвигается вдоль ленты (на одну клетку за один шаг) влево или вправо, наносит или стирает метки, а также распознает, есть ли метка в клетке в соответствии с заданной программой, состоящей из отдельных команд.
Современный взгляд на алгоритмизацию.
Теория алгоритмов строит и изучает конкретные модели алгоритмов. С развитием вычислительной техники и теории программирования возрастает необходимость построения новых экономичных алгоритмов, изменяются способы их построения, способы записи алгоритмов на языке, понятном исполнителю. Особый тип исполнителя алгоритмов – компьютер, поэтому необходимо создавать специальные средства, позволяющие, с одной стороны, разработчику в удобном виде записывать алгоритмы, а с другой – дающие компьютеру возможность понимать написанное. Такими средствами являются языки программирования или алгоритмические языки.
Алгоритм. Свойства алгоритма
Существует множество определений понятия «алгоритм»:
Из определений вытекают свойства алгоритма [5]:
Теперь покажем, что конкретный алгоритм обладает этими свойствами. В качестве примера, возьмем алгоритм, изображенный на рис. 1 в виде блок-схемы [6].
Рис 1 Блок-схема алгоритма проверки правильности расстановки скобок
Приведенный алгоритм проверяет правильность расстановки скобок, если скобки расставлены правильно – то каждой закрывающей скобке предшествует соответствующая открывающая, а каждой открывающей соответствует закрывающая.
Суть алгоритма заключается в подсчете глубины вложенности скобок друг в друга. Если в какой-то момент глубина получает значение меньше нуля – то скобки расставлены неправильно. Если просмотрены все символы строки, но счетчик не равен нулю – то в строке есть не закрытые скобки (расставлены неправильно). В противном случае скобки расставлены правильно.
Можно сказать, что алгоритм обладает свойством дискретности, так как весь алгоритм разбит на отдельные части (на блок-схеме это хорошо видно).
Доказать детерминированность алгоритма, достаточно сложно, например, когда алгоритм содержит части, которые выполняются параллельно, но не будем сейчас на этом останавливаться. Скажем, что в данном случае программа является детерминированной, т.к. не содержит фрагментов, зависящих от времени выполнения, т.е. сколько бы мы не тестировали алгоритм на одной и той же строке результат не изменится.
Чтобы показать результативность алгоритма, в данном случае достаточно заметить, что любой путь из начальной вершины в конечную содержит блок вывода результата. Перед блоком «конец» алгоритм содержит лишь 2 альтернативные ветви, каждая из которых выводит некоторый результат.
Алгоритм обладает свойством массовости, т.к. исходными данными для него может быть любая конечная последовательность символов. Алгоритм не обладал бы этим свойством, если бы работал лишь ограниченном наборе исходных данных, например на строках «()» и «())», но на остальных наборах не работал или работал не правильно.
Проверить свойство правильности алгоритма достаточно просто, для этого можно взять несколько примеров исходных данных, для которых результат очевиден и протестировать алгоритм на них, но доказать правильность алгоритма достаточно сложно. Доказательство правильности называется верификацией и явно выходит за рамки этой статьи.
В этой статье мы разобрались с тем, что такое алгоритм и какими основными свойствами он должен обладать. К теме алгоритмов я обязательно вернусь в будущих статьях.
Свойства алгоритмов
Центральным понятием информатики является алгоритм. Алгоритм – это метод (способ) решения задачи, записанный по определенным правилам, обеспечивающим однозначность его понимания и механического исполнения при всех значениях исходных данных.
Описание метода следует выполнять в соответствии с определенными правилами:
– выделить величины, являющиеся исходными для задачи;
– разбить процесс решения задачи на этапы, известные исполнителю, которые он может выполнить однозначно без всяких пояснений;
– указать порядок выполнения этапов;
– указать признак окончания процесса решения задачи;
– указать результат решения задачи.
Составить такое описание обычно нелегко, но, следуя ему и механически выполняя все указанные в нем этапы в требуемом порядке, исполнитель может всегда правильно решить задачу.
Основные свойства алгоритма, вытекающие из его определения:
– дискретность алгоритма – свойство алгоритма, означающее, что процесс решения задачи, определяемый алгоритмом, разделен на отдельные элементарные действия (шаги). Алгоритм представляет последовательность указаний и команд, определяющих порядок выполнения шагов процесса;
– определенность алгоритма – свойство алгоритма, когда каждая его команда понятна исполнителю, не оставляя при этом места для ее неоднозначного толкования и неопределенного исполнения. Описание алгоритма должно быть таким, чтобы его мог выполнить пользователь;
– результативность алгоритма – свойство алгоритма, означающее, что решение задачи происходит за конечное число шагов и за конечное время. В алгоритме всегда должно быть указано условие его выполнения;
– массовость алгоритма – свойство алгоритма, означающее, что каждый алгоритм, разработанный для решения некоторой задачи, должен быть применим для решения задач этого типа при всех допустимых значениях исходных данных.
Процесс решения задачи с помощью ЭВМ не отличается от процесса решения этой же задачи человеком-исполнителем. Так же следует выбирать и изучать метод решения задачи, так же составлять алгоритм и решать задачу строго в соответствии с ним, только решать должна ЭВМ, а не человек. Программный принцип работы – способность действовать по алгоритму, реализованному в виде программы.
Возможность использования ЭВМ вместо человека объясняется соответствием свойств алгоритма и ЭВМ: алгоритм допускает механическое выполнение его для решения задачи, а ЭВМ может механически, не вникая, выполнять операции в заданном порядке. Отличие указанного процесса при использовании ЭВМ в том, что при составлении алгоритма происходит разбиение процесса решения задачи на операции, которые в состоянии выполнить ЭВМ.
Другое отличие в том, что составленный алгоритм решения задачи следует перевести на язык, понятный ЭВМ.
Презентация к уроку
Цель урока: Формирования у учащихся правильного понимания алгоритмов, их свойств, видов и практических навыков составления алгоритмов.
Задачи урока:
Дидактические: Обеспечить условия:
Воспитательные: Обеспечить условия:
Развивающие: Обеспечить условия:
Демонстрационный материал к уроку:
Ход урока
Понятие алгоритма
Появление алгоритмов связывают с зарождением математики.
Более 1000 лет назад (825 г.)ученый из города Хорезма Абдулла (или Абу Ждафар) Мухаммед бен Мусса аль-Хорезми создал книгу по математике, в тором описал способы выполнения арифметических действий над многозначными числами.
Алгоритм – описание последовательности действий, исполнение которых приводит к решению поставленной задачи за конечное число шагов.
Алгоритм — понятное и точное предписание исполнителю выполнить конечную последовательность команд, приводящих от исходных данных к искомому результату.
Свойства алгоритма
Словесный способ записи алгоритмов представляет собой описание последовательных этапов обработки данных. Алгоритм задается в произвольном изложении на естественном языке.
Пример: Алгоритм «Зарядка»
При словесно-формульном способе алгоритм записывается в виде текста с формулами по пунктам, определяющим последовательность действий.
Пусть, например, необходимо найти значение следующего выражения:
Словесно-формульным способом алгоритм решения этой задачи может быть записан в следующем виде:
При графическом представлении алгоритм изображается в виде последовательности связанных между собой функциональных блоков, каждый из которых соответствует выполнению одного или нескольких действий.
Виды алгоритма
Линейный алгоритм – это такой, в котором все операции выполняются
последовательно одна за другой.
Пример: Алгоритм посадки дерева.
Разветвляющийся алгоритм – это алгоритм в котором выполняется либо одна, либо другая группа действий в зависимости от истинности или ложности условия.
Полная форма
Неполная форма
Пример: Если на улице дождь, то останемся дома, а если нет то идем гулять.
Циклический алгоритм – действия повторяются до тех пор, пока выполняется заданное условие.
Цикл с известным числом повторений
Цикл с известным числом повторений часто называют «циклом ДЛЯ»
Пример: Алгоритм «Упражнение для глаз»
Цикл с постусловием
Цикл с неизвестным числом повторений, в тором выход из цикла осуществляется при выполнении условия, принято называть «циклом с постусловием» или «циклом ПРИ»
Цикл с предусловием
Цикл с известным числом повторений, в котором цикл продолжается, пока выполняется условие, принято называть «циклом с предусловием» или «циклом ПОКА»
Свойства алгоритма
Свойства алгоритма
К алгоритму предъявляется ряд требований:
Определенность, т.е. он должен быть точен, общепонятен, исключать возможность произвольного толкования.
Массовость, т.е. чтобы его можно было применить к однотипным задачам.
Результативность, т.е. через определенное число шагов алгоритм должен закончиться.
Дискретность, т.е. возможность деления задачи на шаги, элементарные операции.
Понятность, т.е. ориентация на те команды, которые знает исполнитель.
Дискретность – одно из первоначальных требований. Процесс должен быть разделен на отдельные элементарные действия, возможность выполнения которых не вызывает сомнения. В результате получается совокупность предписаний, обозначающих структуру алгоритма. Это свойство особенно наглядно прослеживается на примерах бытовых алгоритмов (например, в кулинарных, при приготовлении блюда). Оно характерно для последовательных алгоритмов и не является обязательным для алгоритмов с параллельным исполнением.
Понятность отмечает еще одну особенность алгоритма. Предполагается, что исполнитель всегда знает, как сделать действие. Исполнитель – это автомат, человек, механизм и т.п., который умеет выполнять некоторый набор действий. Т.е. у каждого исполнителя есть перечень команд, и составляя алгоритм, надо иметь в виду исполнителя.
Следующее свойство – детерминированность, или определенность – тесно связано с предыдущим. Алгоритм должен быть сформирован так, чтобы действия были точно определены, однозначны и давали один и тот же результат от одних и тех же данных. Кроме того, исполнителю должно быть ясно, какие действия.
Массовость, или общность, означает, что алгоритм может быть применен не только к единственным исходным данным или набору данных, но и к целому классу похожих задач.
Результативность, или выполнимость, означает, что при любых допустимых исходных данных и точном выполнении всех предписаний Вы закончите проект за конечное число шагов. Но это требование может не учитывать реальных условий, поэтому говорят о “потенциальной” выполнимости.
Под правильностью понимают способность алгоритма обеспечить получение именно того результата, который требуется. Неправильность может объясняться неполнотой наших представлений о свойствах объекта или упущением в решении. Доказательство правильности алгоритма – один из самых трудных этапов тестирования. Задача часто делится на блоки и правильность доказывается для каждого блока, хотя такая проверка не является полной.
Эффективность подразумевает тот факт, что для решения задачи могут быть предложены разные алгоритмы. Выбор того, который будет выполнен за минимальное время, с минимальными затратами ресурсов, – задача непростая. Хотя чаще под эффективностью понимают длительность счета. Для отслеживания таких затрат достаточно предусмотреть в алгоритме счетчики времени.