Алгоритм

Материал из Циклопедии
Перейти к навигации Перейти к поиску
Алгоритмы. Виды и свойства алгоритмов // IT Hobbies [7:16]

Алгоритм (от «аль-Хорезми»[1]) в информатике — это строго определённый порядок[2] вычислений, выполнением которого обеспечивается[3] заданное математическое отношение между исходными и итоговыми данными.

Уровни и способы абстракции алгоритмов[править]

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

Алгоритм может быть представлен:

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

Примеры[править]

Multiplication à la russe[править]

Если дана пара чисел, то как найти их произведение? Ответов (алгоритмов) множество, наиболее древний можно найти в двух знаменитых египетских папирусах — ахмесовом и московском. Алгоритм «египетского умножения»: при данных a и b и ответ=0: Если a нечетное, добавить b к ответу. Поделить a на два. Удвоить b. Если a>1, повтор. В данном виде алгоритм сам не вовлекает операции умножения: на двоичном компьютере деление и умножение на два можно выполнить через сдвиги.

Но в школах преподаётся метод умножения столбиком.

Наибольший общий делитель[править]

Наибольший общий делитель двух чисел можно найти, последовательно деля с остатком: алгоритм Эвклида.

  1. Находим остаток от деления: r←(a modulo b)
  2. Если это нуль, ответ b: if r=0 return b
  3. Рекурсия с b и r: a←b, b←r, goto 1

См. также[править]

Источники[править]

  1. Слово «алгоритм»: происхождение и развитие в журнале «Потенциал»
  2. Порядок в математическом смысле: обобщение понятия «последовательность».
  3. Вероятностные алгоритмы обеспечивают не абсолютную гарантию результата, а достаточную вероятность, которая, в свою очередь, доказана.
 
Библиотека

Стандартная библиотекаПространство имёнФреймворкИнтерфейсAPI

Основные
термины

АлгоритмПсевдокодПерегрузка операторовВыражениеИнструкцияОперацияОтступКоличество строк кода

Подпрограмма

Соглашение об именованииМультиметодCallbackФункция высшего порядкаРекурсивная функцияОбобщённое программированиеОперандПараметрПолиморфизмПерегрузка процедур и функций

ООП

КлассКонструкторДеструкторИнкапсуляцияНаследованиеМножественное наследованиеМетодСборка мусораСсылка

Структуры
и типы данных

ДеревоСимвольный типЗаписьМножествоОчередьСписокСвязный списокСтекСвойствоСемафорМассивКучаАбстрактный тип данныхДинамический массив

Исходный
код

Категория Категория