Алгоритм что это такое


АЛГОРИТМ

Содержание статьи

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

Слово «алгоритм» происходит от имени великого среднеазиатского ученого 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 – «пробел». Головка находится в каждый момент времени над некоторой ячейкой ленты – текущей рабочей ячейкой. Лентопротяжный механизм может перемещать ленту так, что головка оказывается над соседней ячейкой ленты, при этом возможна ситуация выхода за левый край ленты, которая является аварийной (недопустимой), или машинного останова, когда машина выполняет предписание об остановке.

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

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

Анна Чугайнова

www.krugosvet.ru

Что такое Алгоритм простыми словами

Хотим мы этого или не хотим, но уже сегодня человечество живет наполовину в цифровом мире. Математика – Богиня нашего цифрового мира и Алгоритм – пророк ее.

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

Однако, инстинкт тоже в своем роде является алгоритмом, а в чем же тогда преимущество человека?

  • Инстинкты властвуют над животными.
  • Человек же создает алгоритмы сам.

Именно способность самостоятельно создавать подобные действия и является кардинальным отличием мыслящего человека от подвластного природным инстинктам животного.

Что называется алгоритмом

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

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

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

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

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

Думаю вам такой порядок действий хорошо знаком.

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

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

Виды

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

В зависимости от практической задачи структура алгоритма может изменяться.

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

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

Говоря простыми словами, разветвляющийся «algorithm» еще можно описать словами из американского боевика: «Что-то пошло не так. Переходим к плану «Б». Планы А и Б – это и есть ветви решения поведения боевой группы на задании, в условиях непредсказуемо меняющейся обстановки.

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

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

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

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

  • Карма – это глобальный алгоритм жизни обычного человека, еще не достигшего «просветления».

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

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

В каких сферах их применяют

Алгоритмы буквально пронизывают всю Вселенную. Сам термин «algorithm», как принято считать, происходит от имени средневекового арабского математика Аль-Хорезми.

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

Это интересно: Что такое Апгрейд, Стрим, Мемы, Франшиза

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

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

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

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

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

По каким алгоритмам работает поиск от Google и Яндекс

Яркий пример – работа поисковых сервисов. Как же Яндекс и Google могут так быстро находить на миллионах сайтов в интернете ответы практически на любой вопрос пользователя?

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

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

  • Индексация – сбор данных, опубликованных на всех сайтах в интернете.
  • Определение релевантности. Информация на веб-страницах сортируется по тематикам поисковых запросов.
  • Ранжирование. По каждой теме производится оценка качества и полезности ответов. Затем на странице результатов поиска ответы размещаются «по ранжиру», в порядке убывания качества и соответствия.

Многие пользователи полагают, что после запуска поиска по фразе Google со всех ног мечется по всему интернету и там ищет относящуюся к делу (релевантную) информацию.

Прочитай это: Что такое ранжирование сайта и какие факторы на это влияют

Ничего подобного. Весь контент со всех веб-страниц заранее собирается специальными программами (которые тоже есть алгоритмы) – так называемыми поисковыми роботами.

Собранная информация хранится в Индексе поисковой машины – базе данных. Слово Index по-английски означает «каталог». Это примерно, как в обычной библиотеке все книги разделены по полкам, а в Каталоге лежат карточки с краткими описаниями. Индекс Яндекса – это и есть такой цифровой каталог всего интернет-контента.

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

Фразы в тексте, соответствующие поисковому запросу принято называть «ключевыми словами» или «ключевиками».

Чтобы поисковой машине было легче найти контент на сайте, веб-мастера специально добавляют в текстовый контент соответствующие ключевые слова. Это называется «поисковая оптимизация».

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

  • Оценка уникальности.
  • Проверка достоверности и актуальности сведений.
  • Объем и профессиональный уровень контента (информационная ценность).
  • Авторитетность автора, репутация публикатора.
  • Цитируемость – кто и как ссылается на данный контент на сторонних сайтах.
  • И еще проверка контента и сайта в целом по нескольким сотням разных алгоритмов.

Некоторые алгоритмы поисковых систем известны и имеют названия.

  • Алгоритм Яндекса ИКС определяет качество контента на сайте.
  • Алгоритм Google «Колибри» предназначен для улучшенного поиска и ранжирования контента, написанного естественным разговорным языком.

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

  • Фильтр Яндекса «Минусинск» выявляет и понижает в выдаче сайты, использующие покупные SEO-ссылки.
  • Фильтр Гугл «Пингвин» предназначен для определения неестественных, искусственных ссылок.

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

Так то, всё, что известно относительно алгоритмов Яндекса и Google веб-мастерам и специалистам по поисковому продвижению, найдено и выявлено чисто эмпирическим путем или относится к области гипотетических предположений.

seoslim.ru

Алгоритм

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

gtmarket.ru

алгоритм - это... Что такое алгоритм?

  • Алгоритм Ли — Алгоритм Ли  волновой алгоритм поиска пути на карте, алгоритм трассировки. С его помощью можно построить путь, или трассу, между двумя любыми элементами в лабиринте. Из начального элемента распространяется в четырёх направлениях волна. Тот… …   Википедия

  • АЛГОРИТМ —         [от algorithm!; algorismus, первоначально лат. транслитерация имени ср. азиат. учёного 9 в. Хорезми (Мухаммед бен Муса аль Хорезми)], программа, определяющая способ поведения (вычисления); система правил (предписаний) для эффективного… …   Философская энциклопедия

  • алгоритм — Конечный набор предписаний для получения решения задачи посредством конечного количества операций. [ГОСТ 34.003 90] алгоритм Конечное упорядоченное множество точно определенных правил для решения конкретной задачи. [ИСО/МЭК 2382 1] [ГОСТ Р 52292… …   Справочник технического переводчика

  • АЛГОРИТМ — [лат. algorithmus < арабск. Algorithmi имя собств.] 1) мат. однозначно определенная процедура для схематического решения класса задач; 2) инф. понятное и точное предписание исполнителю совершить последовательность действий, направленных на… …   Словарь иностранных слов русского языка

  • алгоритм — алгорифм Словарь русских синонимов. алгоритм сущ., кол во синонимов: 3 • алгорифм (1) • …   Словарь синонимов

  • алгоритм — а, м. algorithme m. 1230 algorisme. Лексис.1. В математике общепонятное предписание, определяющее детерминированный вычислительный процесс, ведущий от исходных данных к искомому результату. БАС 2. Алгебра логика математики; алгоритм ее… …   Исторический словарь галлицизмов русского языка

  • Алгоритм — (algorithm) Последовательность четко определенных действий для решения проблемы, выраженная в конечном числе шагов. Алгоритмы широко применяются в компьютерной области. Шаги алгоритма переводятся в последовательность команд, понимаемых… …   Словарь бизнес-терминов

  • АЛГОРИТМ — (алгорифм) (от algorithmi, algorismus, первоначально латинская транслитерация имени математика аль Хорезми), способ (программа) решения вычислительных и других задач, точно предписывающий, как и в какой последовательности получить результат,… …   Современная энциклопедия

  • АЛГОРИТМ — (алгорифм) (от algorithmi algorismus, первоначально лат. транслитерация имени математика аль Хорезми), способ (программа) решения вычислительных и др. задач, точно предписывающий, как и в какой последовательности получить результат, однозначно… …   Большой Энциклопедический словарь

  • АЛГОРИТМ — (от лат. формы имени среднеазиатского математика аль Хорезми) правило действий, последовательность проведения вычислительных операций, способ нахождения искомого результата. В экономических задачах, решаемых с использованием математических… …   Экономический словарь

psychology.academic.ru

АЛГОРИТМ - это... Что такое АЛГОРИТМ?

  • Алгоритм Ли — Алгоритм Ли  волновой алгоритм поиска пути на карте, алгоритм трассировки. С его помощью можно построить путь, или трассу, между двумя любыми элементами в лабиринте. Из начального элемента распространяется в четырёх направлениях волна. Тот… …   Википедия

  • АЛГОРИТМ —         [от algorithm!; algorismus, первоначально лат. транслитерация имени ср. азиат. учёного 9 в. Хорезми (Мухаммед бен Муса аль Хорезми)], программа, определяющая способ поведения (вычисления); система правил (предписаний) для эффективного… …   Философская энциклопедия

  • алгоритм — Конечный набор предписаний для получения решения задачи посредством конечного количества операций. [ГОСТ 34.003 90] алгоритм Конечное упорядоченное множество точно определенных правил для решения конкретной задачи. [ИСО/МЭК 2382 1] [ГОСТ Р 52292… …   Справочник технического переводчика

  • алгоритм — предписание, задающее на базе системы правил последовательность операций, точное выполнение коих позволяет решать задачи определенного класса. Понятие, ключевое для математики и логики математической. В психологии применяется не в строгом… …   Большая психологическая энциклопедия

  • алгоритм — алгорифм Словарь русских синонимов. алгоритм сущ., кол во синонимов: 3 • алгорифм (1) • …   Словарь синонимов

  • алгоритм — а, м. algorithme m. 1230 algorisme. Лексис.1. В математике общепонятное предписание, определяющее детерминированный вычислительный процесс, ведущий от исходных данных к искомому результату. БАС 2. Алгебра логика математики; алгоритм ее… …   Исторический словарь галлицизмов русского языка

  • Алгоритм — (algorithm) Последовательность четко определенных действий для решения проблемы, выраженная в конечном числе шагов. Алгоритмы широко применяются в компьютерной области. Шаги алгоритма переводятся в последовательность команд, понимаемых… …   Словарь бизнес-терминов

  • АЛГОРИТМ — (алгорифм) (от algorithmi, algorismus, первоначально латинская транслитерация имени математика аль Хорезми), способ (программа) решения вычислительных и других задач, точно предписывающий, как и в какой последовательности получить результат,… …   Современная энциклопедия

  • АЛГОРИТМ — (алгорифм) (от algorithmi algorismus, первоначально лат. транслитерация имени математика аль Хорезми), способ (программа) решения вычислительных и др. задач, точно предписывающий, как и в какой последовательности получить результат, однозначно… …   Большой Энциклопедический словарь

  • АЛГОРИТМ — (от лат. формы имени среднеазиатского математика аль Хорезми) правило действий, последовательность проведения вычислительных операций, способ нахождения искомого результата. В экономических задачах, решаемых с использованием математических… …   Экономический словарь

dic.academic.ru

алгоритм - это... Что такое алгоритм?

  • Алгоритм Ли — Алгоритм Ли  волновой алгоритм поиска пути на карте, алгоритм трассировки. С его помощью можно построить путь, или трассу, между двумя любыми элементами в лабиринте. Из начального элемента распространяется в четырёх направлениях волна. Тот… …   Википедия

  • АЛГОРИТМ —         [от algorithm!; algorismus, первоначально лат. транслитерация имени ср. азиат. учёного 9 в. Хорезми (Мухаммед бен Муса аль Хорезми)], программа, определяющая способ поведения (вычисления); система правил (предписаний) для эффективного… …   Философская энциклопедия

  • алгоритм — Конечный набор предписаний для получения решения задачи посредством конечного количества операций. [ГОСТ 34.003 90] алгоритм Конечное упорядоченное множество точно определенных правил для решения конкретной задачи. [ИСО/МЭК 2382 1] [ГОСТ Р 52292… …   Справочник технического переводчика

  • алгоритм — предписание, задающее на базе системы правил последовательность операций, точное выполнение коих позволяет решать задачи определенного класса. Понятие, ключевое для математики и логики математической. В психологии применяется не в строгом… …   Большая психологическая энциклопедия

  • АЛГОРИТМ — [лат. algorithmus < арабск. Algorithmi имя собств.] 1) мат. однозначно определенная процедура для схематического решения класса задач; 2) инф. понятное и точное предписание исполнителю совершить последовательность действий, направленных на… …   Словарь иностранных слов русского языка

  • алгоритм — алгорифм Словарь русских синонимов. алгоритм сущ., кол во синонимов: 3 • алгорифм (1) • …   Словарь синонимов

  • алгоритм — а, м. algorithme m. 1230 algorisme. Лексис.1. В математике общепонятное предписание, определяющее детерминированный вычислительный процесс, ведущий от исходных данных к искомому результату. БАС 2. Алгебра логика математики; алгоритм ее… …   Исторический словарь галлицизмов русского языка

  • Алгоритм — (algorithm) Последовательность четко определенных действий для решения проблемы, выраженная в конечном числе шагов. Алгоритмы широко применяются в компьютерной области. Шаги алгоритма переводятся в последовательность команд, понимаемых… …   Словарь бизнес-терминов

  • АЛГОРИТМ — (алгорифм) (от algorithmi, algorismus, первоначально латинская транслитерация имени математика аль Хорезми), способ (программа) решения вычислительных и других задач, точно предписывающий, как и в какой последовательности получить результат,… …   Современная энциклопедия

  • АЛГОРИТМ — (алгорифм) (от algorithmi algorismus, первоначально лат. транслитерация имени математика аль Хорезми), способ (программа) решения вычислительных и др. задач, точно предписывающий, как и в какой последовательности получить результат, однозначно… …   Большой Энциклопедический словарь

  • АЛГОРИТМ — (от лат. формы имени среднеазиатского математика аль Хорезми) правило действий, последовательность проведения вычислительных операций, способ нахождения искомого результата. В экономических задачах, решаемых с использованием математических… …   Экономический словарь

dic.academic.ru


Смотрите также