Алгоритм
Алгоритм (от «аль-Хорезми»[1]), в информатике — строго определённый порядок[2] вычислений, выполнением которого обеспечивается[3] заданное математическое отношение между исходными и итоговыми данными.
Уровни и способы абстракции алгоритмов[править]
Строго различаются понятия алгоритм и компьютерная программа. Алгоритм это лишь абстрактная теоретическая сущность, тогда как программа — это некоторое подготовленное или текущее состояние конкретного программируемого вычислительного устройства, либо же конкретный код-прообраз такого рода состояний. Программа может направлять произвольные шаги вычислений, допускать сбои, выходить из-под контроля, а вот алгоритм, даже будучи реализован в конкретной программе, — по определению работает исправно при любом из вариантов исходного состояния вычислений. Такая бесперебойная исправность подлежит математическому доказательству, и, помимо этого, алгоритмы подвергаются анализу в области информатики, так и называемой: анализ алгоритмов. В литературе традиционно указывают тривиальное: исправная работа алгоритма должна всякий раз завершаться, то есть, не занимать всю вечность.
Алгоритм может быть представлен:
- в риторическом изложении, то есть, в форме словесных утверждений, однозначных и точных, а также понятных в качестве технической инструкции;
- в готовой к работе материальной форме вычислительного устройства;
- как объект формальной системы, то есть, грамматики формального языка: в простейшем случае — через рекурсивное применение «применения»: оператора «апплицировать»;
- начертанием блок-схемы,
- как компьютерный код любого уровня абстракции: от лямда-выражений и машинного кода до псевдокода и запросов к генератору.
Анализ алгоритмов даёт оценку их эффективности: степени бережности к вычислительным ресурсам. Через функцию от объёма вводных данных алгоритмы оцениваются по временной и пространственной вычислительной сложности: время можно измерять числом атомарных операций или машинных циклов, а пространство — число ячеек памяти. Все эти понятия и их конкретный характер — зависят от задействуемой вычислительной среды: либо конкретной технологии, либо теоретической сущности, — такой, как абстрактная машина, автомат, нейросеть, вентильная матрица.
Примеры[править]
Multiplication à la russe[править]
Если дана пара чисел, то как найти их произведение? Ответов (алгоритмов) множество, наиболее древний можно найти в двух знаменитых египетских папирусах — ахмесовом и московском. Алгоритм «египетского умножения»: при данных a и b и ответ=0: Если a нечетное, добавить b к ответу. Поделить a на два. Удвоить b. Если a>1, повтор. В данном виде алгоритм сам не вовлекает операции умножения: на двоичном компьютере деление и умножение на два можно выполнить через сдвиги.
Но в школах преподаётся метод умножения столбиком.
Наибольший общий делитель[править]
Наибольший общий делитель двух чисел можно найти, последовательно деля с остатком: алгоритм Эвклида.
- Находим остаток от деления:
r←(a modulo b) - Если это нуль, ответ b:
if r=0 return b - Рекурсия с b и r:
a←b, b←r, goto 1
См. также[править]
Источники[править]
- ↑ Слово «алгоритм»: происхождение и развитие в журнале «Потенциал»
- ↑ Порядок в математическом смысле: обобщение понятия «последовательность».
- ↑ Вероятностные алгоритмы обеспечивают не абсолютную гарантию результата, а достаточную вероятность, которая, в свою очередь, доказана.
| ||||||||||||||||||||||||||||||||||||||||||||