Алгоритм

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

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

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

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

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

Содержание

[править] Умножение

Если дана пара чисел, то как найти их произведение? Ответов (алгоритмов) множество, наиболее древний можно найти в двух знаменитых египетских папирусах — ахмесовом и московском.

[править] 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

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

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


Персональные инструменты
Пространства имён

Варианты
Действия
Навигация
Инструменты