Понятие алгоритма — Информатика: конспект лекций

Входом алгоритма является конечный набор элементарных объектов. В данном примере дерево рекурсивных вызовов обрывается на F1{\displaystyle F_{1}} и F2{\displaystyle F_{2}}, для вычисления которых не используются рекурсивные вызовы. Таким образом, алгоритм выдаёт один и тот же результат (ответ) для одних и тех же исходных данных.

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

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

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

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

А в популярной средневековой поэме «Роман о Розе» (1275—1280) Жана де Мена «греческий философ Алгус» ставится в один ряд с Платоном, Аристотелем, Евклидом и Птолемеем! Многие века абак был фактически единственным средством для практичных вычислений, им пользовались и купцы, и менялы, и учёные. Итак, сочинения по искусству счёта назывались Алгоритмами. Позднее и оно, в свою очередь, подверглось искажению, скорее всего, связанному со словом arithmetic.

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

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

А программа — это конкретная реализация алгоритма, которая может быть скомпилирована и выполнена на компьютере

За сорок лет алгоритм превратился в одно из ключевых понятий математики, и признанием этого стало включение слова уже не в энциклопедии, а в словари. Например, оно присутствует в академическом «Словаре русского языка» (1981 г.) именно как термин из области математики. Соответственно и алгоритмы ни разу не упоминаются на её страницах. Но уже в начале 70-х гг. прошлого столетия, когда компьютеры перестали быть экзотической диковинкой, слово «алгоритм» стремительно входит в обиход.

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

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

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

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

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

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

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

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

Алгоритм, в свою очередь, является реализацией идеи решения

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

Особенно полезна нумерация в исследовании алгоритмов, работающих с другими алгоритмами

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

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

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