Войти
Блок-схема алгоритма (алгоритм Евклида ) для вычислений наибольшего общего делителя (НОД) двух чисел a и b в точках с именами A и B. Алгоритм продолжает последовательное вычитание в двух циклах: ЕСЛИ тест B ≥ A дает «да» или «истина» (подробнее точно, число b в позиции B больше или равно числовое число в позиции A) ЗАТЕМ алгоритм определяет B ← B - A (что означает, что число b - a заменяет старое число b). Аналогично, ЕСЛИ A>B, ТО A ← A - B. Процесс завершается, когда (содержимое) B равно 0, в результате чего получается g.c.d. в А. (Алгоритм взят из Scott 2009: 13; символы и стиль рисования из Tausworthe 1977). 
Диаграмма Ады Лавлейс из «примечания G», первого компьютерного алгоритма в математика и информатика, ((
слушайте )) - это конечная последовательность четко определенных, компьютерно реализуемые инструкции, обычно решения класса проблем или для выполнения вычислений. Алгоритмы всегда однозначны и используются в качестве спецификаций для выполнения вычислений, обработки данных, автоматических рассуждений и других задач.
В качестве эффективного метода алгоритм может быть выражен в ограниченном пространстве времени и на четко определенном формальном языке для вычислений функции . Начало с начального состояния и начального ввода (возможно, пустой ), инструкции выполняют вычисление, которое, когда выполняется, выполняется через конечное количество четко определенные последовательные состояния, в конечном итоге производящие «выход» и заканчивающиеся конечным конечным состоянием. Переход из одного состояния в другое не обязательно детерминированный ; некоторые алгоритмы, известные как рандомизированные алгоритмы, включая случайный ввод.
Концепция алгоритма существует с древних времен. Арифметические алгоритмы, такие как алгоритм деления, использовались древними вавилонскими математиками c. 2500 г. до н.э. и египетские математики ок. 1550 г. до н. Э. греческие математики позже использовали алгоритмы из решета Эратосфена для поиска простых чисел и алгоритм Евклида для поиска наибольшего общего делителя двух чисел. Арабские математики, такие как аль-Кинди, в 9 веке использовали криптографические алгоритмы для взлома кода, на основе на частотный анализ.
Само слово «алгоритм» происходит от имени математика 9 века Мухаммада ибн Муса аль-Хваризми, чей нисба (идентифицируя его как из Хорезм ) латинизирован как Алгоритми. Частичная формализация того, что может стать современной концепцией алгоритма, началась попытка решить Entscheidungsproblem (проблема решения), поставленную Дэвидом Гильбертом в 1928 году. Более поздние формы разработки были сформулированы как определить «эффективная вычислимость » или «эффективный метод». Эти формы формирования включали Гедель –Гербранд –Клин рекурсивные функции 1930, 1934 и 1935 годов, Алонзо Черч лямбда-исчисление 1936 года, Формулировка 1 Эмиляа 1936 года и Алан Тьюринг машины Тьюринга 1936–37 и 1939 гг.
Слово «алгоритм» имеет свои корни в латинизации нисбы, что указывает на его географическое происхождение. имя персидского математика Мухаммада ибн Муса аль-Хорезми к алгоритму. Аль-Хваризми (арабизированный персидский الخوارزمی ок. 780–850) был математиком, астрономом, географом и ученым в Дом Мудрости в Багдаде, имя которого означает «уроженец Хорезма », региона, который был частью Великого Ирана и ныне в Узбекистане.
Около 825 г. аль-Хорезми написал арабский язык трактат по индуистско-арабской системе счисления, который был переведен на латынь в 12 веке. Рукопись начинается с фразы «Диксит Алгоризми» («Так говорил Аль-Хорезми»), где «Алгоризми» было латинизацией имени аль-Хорезми переводчиком. Аль-Хорезми был самым читаемым математиком в Европе в период позднего средневековья, главным образом благодаря его книге, Алгебре. Внесредневековой латыни, алгоритм, английское «алгоритм », искажение его имени, означало просто «десятичная система счисления». В области 15 области греческого слова ἀριθμός (арифмос), «число» (ср. «Арифметика») латинское слово было изменено на алгоритм, а соответствующий английский термин «алгоритм» впервые засвидетельствован в 17 веке. век; современный смысл введен в 19 веке.
На английском языке он был впервые использован примерно в 1230 году, а затем Чосером в 1391 году. Английский принял французский термин, но это не так. до конца 19 века этот «алгоритм» приобрел значение, которое он имеет в современном английском языке.
Другое раннее использование этого слова относится к 1240 году в начале под названием Carmen de Algorismo, составленном Александром де Вильдье. Он начинается с:
Haec algorismus ars praesens dicitur, in qua / Talibus Indorum fruimur bis quinque figuris.
что переводится как:
Алгоризм - это искусство, с помощью которого в настоящее время мы используем индейские фигуры, число которых два умножить на пять.
Поэма состоит из нескольких сотен строк и резюмирует искусство вычислений с использованием индийских игральных костей (Tali Indorum) или индусских цифр.
неформальным определением может быть «набор правил, определяющих последовательность операций», который будет запускать все компьютерные программы (включая программы, не выполняющие числовые вычисления) и (например) любую предписанную бюрократическую компьютерную или кулинарную книгу рецепт.
В общем, программа является алгоритмом только в том случае, если она в конечном итоге останавливается - даже если бесконечные циклы иногда могут оказаться желательными.
Прототипным примером алгоритма является алгоритм Евклида, который используется для определения максимального делителя двух целых чисел; пример (есть и другие) описывается блок-схемой выше и в следующем качестве в разделе.
Boolos, Jeffrey 1974, 1999 предоставляет неформальное значение слова «алгоритм» в следующей цитате:
Ни один человек не может писать достаточно быстро, или достаточно долго, или достаточно мало † († "все меньше и меньше без ограничений… вы бы пытались писать на молекулах, атомах, электронах »), чтобы перечислить все члены бесчисленно бесконечного множества, записывая их имена за другие в некоторой нотации. множеств: они могут дать явные инструкции для определения n -го множества для произвольного конечного n. Эти инструкции должны дать совершенно явно в форме, в которой они могли бы быть вычислительной машиной или человеком, который способен выполнять только очень элементарные операции с символами.
"бесчисленное совокупное множество" - это элемент, элементы которого можно поставить во взаимно однозначное соответствие с целыми числами. образом, Булос и Джеффри говорят, что подразумевает инструкции для процесса, который «» создает выходные целые числа из произвольных «входных» целых или целых чисел, которые, теоретически, могут быть сколь угодно большими. Например, алгоритм может представлять собой алгебраическое уравнение, такое как y = m + n (т. Е. Две произвольные «входные переменные» m и n, которые производят выходной y), но попытки определить это понятие указать на то, что слово подразумевает больше, чем это, что-то вроде (для примера сложения):
Алгоритмы необходимы для компьютеров, как обрабатывают данные. Многие компьютерные программы содержат алгоритмы, которые подробно выполняют инструкции, которые компьютер должен выполнять - в определенном порядке, как расчетные зарплаты сотрудников или печать табелей успеваемости студентов. Таким образом, алгоритм можно рассматривать как любую последовательность операций, может моделироваться системой полной по Тьюрингу. Среди авторов, которые отстаивают этот тезис, - Мински (1967), Сэвидж (1987) и Гуревич (2000):
Мински: «Но мы также будем утверждать, с Тьюрингом... что любая процедура, которую« естественно »можно назвать эффективной, может: на самом деле, может быть реализована (простой) машиной. Хотя это может показаться крайним, аргументы… в ее пользу трудно опровергнуть ».
Гуревич: «… Неформальный аргумент Тьюринга в пользу его тезиса оправдывает более сильный тезис: каждый алгоритм может быть смоделирован машиной Тьюринга... согласно Сэвиджу [1987], алгоритм - это вычислительный процесс, определяемый машиной Тьюринга".
Машины Неформальные определения алгоритмов в целом требуют, чтобы алгоритм всегда завершал работу, чтобы вычислить, вычислить, могут быть выполнены алгоритмы, чтобы алгоритм всегда завершал работу. Это требование невозможного выполнения, является ли формальная процедура алгоритмом в общем случае - из-за основной теоремы теории теории, известная как проблема остановки.
Обычно, когда алгоритм hm связан с обработкой информации, данные могут быть прочитаны из источника ввода, записаны в устройстве вывода и сохранены для дальнейшей обработки. На практике состояние хранится в одной или нескольких структурах данных.
. Для некоторых из этих вычислительных процессов алгоритм должен быть строго определен: указан так, как он применен во всех обстоятельствах, которые могут возникнуть. Это любые условные шаги должны работать систематически, в каждом конкретном случае; критериями для каждого случая должны быть ясными (и вычислимыми).
Форма представляет собой точный список точных шагов, порядок вычислений всегда имеет решающее значение для функционирования алгоритма. Обычно, что описано в явном виде и описываются как начинающиеся «сверху» и «спускающиеся вниз» - идея, которая более формально описывается в поток управления.
Пока что обсуждение при формализации алгоритма принимает предпосылки императивного программирования. Это наиболее распространенная концепция - попытка описать задачу дискретными, «механическими» средствами. Уникальная для этой концепции формализованных алгоритмов операция присваивания , которая устанавливает значение переменной. Это происходит из интуитивного представления о «памяти » как о блокноте. Пример такого задания можно найти ниже.
Для альтернативных концепций того, что алгоритм, см. функциональное программирование и логическое программирование.
Алгоритмы могут быть выражены во многих наиболее нотациях, включая естественные языки, псевдокод, блок-схемы, дракон-диаграммы, языков программирования или управляющие таблицы (обрабатываются интерпретаторами ). Выражения алгоритмов на естественном языке тенденций быть многословными и неоднозначными и редко используются для сложных алгоритмов. Псевдокод, блок-схемы, дракон-схемы и управляющие таблицы - это структурированные способы выражения алгоритмов, позволяющие избежать многих двусмысленностей, характерных для операторов, основанных на естественном языке. Языки программирования в первую очередь предназначены для выражения алгоритмов в форме, которая может использовать как способ определения или документирования алгоритмов.
существует представлений, и можно выразить программу машины Тьюринга как последовательность машинных таблиц (см. конечный автомат, таблица переходов состояний и таблица управления для стабильной информации), в виде блок-схем и drakon-charts (см. диаграмму состояний для получения дополнительной информации) или в виде формы рудиментарного машинного кода или ассемблерного кода, называемых «наборами четверок» (см. машина Тьюринга ).
Представления алгоритмов можно разделить на три допустимых уровня описания машины Тьюринга, а именно:
Пример простого алгоритма «Добавить m + n», описанного на всех трех уровнях, см. в разделе Примеры # алгоритмов.
Дизайн алгоритма см. к методу или математическому процессу для решения проблем и инженерных алгоритмов. Разработка алгоритмов является частью многих теорий решений исследования операций, таких как динамическое программирование и разделяй и властвуй. Методы разработки и реализации схем разработки алгоритмов также называются шаблонами разработки алгоритмов, с примерами, включая шаблон и шаблон декоратора.
Один из наиболее важных алгоритмов разработки алгоритмов заключается в создании алгоритма, который имеет эффективное время выполнения, также известный как его Big O.
Типичные шаги в разработке алгоритмов:
Алгоритм Logical NAND, реализованный в электронном виде в 7400 микросхеме Большинство алгоритмов предназначены для реализации в виде компьютерных программ. Однако алгоритмы также реализуются другими средствами, такими как биологическая нейронная сеть (например, человеческий мозг, реализующий арифметические операции или насекомое, ищущее еду), в электрической цепи или в механическом устройстве.
Примеры блок-схем канонических структур Бема-Якопини : ПОСЛЕДОВАТЕЛЬНОСТЬ (прямоугольники, спускающиеся по странице), WHILE-DO и IF-THEN-ELSE. Эти три структуры состоят из примитивного условного GOTO (IF test THEN GOTO step xxx, показан ромбиком), безусловного GOTO (прямоугольник), различных операторов присваивания (прямоугольник) и HALT (прямоугольник). Вложение этих структур в блоки присваивания приводит к получению сложных диаграмм (см. Tausworthe 1977: 100, 114). В компьютерных системах алгоритм в основном является экземпляром логики написано в программном обеспечении разработчиками программного обеспечения, чтобы быть эффективным для предполагаемого "целевого" компьютера (ов) для создания вывода из заданного (возможно, нулевого) ввода. Оптимальный алгоритм, даже работающий на старом оборудовании, даст более быстрые результаты, чем неоптимальный (более высокая временная сложность ) алгоритм для той же цели, работающий на более эффективном оборудовании; вот почему алгоритмы, как и компьютерное оборудование, считаются технологиями.
«Элегантные» (компактные) программы, «хорошие» (быстрые) программы: понятие «простота и элегантность» неформально встречается в Knuth и именно в Chaitin :
Чейтин предваряет свое определение: «Я покажу, что вы не можете доказать, что программа «элегантна» »- такое доказательство решило бы проблему остановки (там же).
Алгоритм против функции, вычисляемой алгоритмом: для данной функции может существовать несколько алгоритмов. Это верно даже без расширения доступного для программиста набора инструкций. Роджерс отмечает, что «... важно различать понятие алгоритма, то есть процедуры, и понятие функции, вычисляемой алгоритмом, то есть отображение, полученное процедурой. Одна и та же функция может иметь несколько разных алгоритмов».
К сожалению, возможен компромисс между добротой (скоростью) и элегантностью (компактностью) - элегантная программа может предпринять больше шагов для завершения вычисления, чем менее элегантная. Пример, в котором используется алгоритм Евклида, показан ниже.
Компьютеры (и компьютеры), модели вычислений: Компьютер (или человеческий «вычислитель») - это ограниченный тип машины, «дискретное детерминированное механическое устройство», которое слепо следует своим инструкциям. Примитивные модели Мелзака и Ламбека свели это понятие к четырем элементам: (i) дискретные, различимые местоположения, (ii) дискретные, неразличимые счетчики, (iii) агент, и (iv) список инструкций, которые эффективны относительно возможностей
Мински описывает более подходящую вариацию модели «счеты» Ламбека в своих «Очень простых основах для вычислимости ». Машина Мински последовательно проходит через свои пять ( или шесть (в зависимости от того, как считается) инструкций, если только условное IF – THEN GOTO или безусловное GOTO не изменяет последовательность выполнения программы. Помимо HALT, машина Мински включает три операции присваивания (замены, подстановки): ZERO (например, содержимое ячейки заменяется на 0: L ← 0), SUCCESSOR (например, L ← L + 1) и DECREMENT (например, L ← L - 1).). Программисту редко приходится писать «код» с таким ограниченным набором инструкций. Но Мински показывает (как это делают Мелзак и Ламбек), что его машина полная по Тьюрингу только с четырьмя общими типами инструкций: условный GOTO, безусловный GOTO, присваивание / замена / подстановка и HALT. Однако несколько разных инструкций присваивания (например, DECREMENT, INCREMENT и ZERO / CLEAR / EMPTY для машины Мински) также требуются для полноты по Тьюрингу; их точная спецификация в некоторой степени зависит от дизайнера. Безусловный GOTO - это удобство; он может быть построен путем инициализации выделенного местоположения нулем, например. инструкция «Z ← 0»; после этого инструкция IF Z = 0 THEN GOTO xxx является безусловной.
Моделирование алгоритма: компьютерный (вычислительный) язык: Кнут советует читателю, что «лучший способ изучить алгоритм - это попробовать его... немедленно взять ручку и бумагу и проработать пример». Но как насчет симуляции или исполнения реальной вещи? Программист должен перевести алгоритм на язык, который симулятор / компьютер / вычислитель может эффективно выполнять. Стоун приводит пример этого: вычисляя корни квадратного уравнения, компьютер должен знать, как извлечь квадратный корень. В противном случае алгоритм, чтобы быть эффективным, должен обеспечивать набор правил для извлечения квадратного корня.
Это означает, что программист должен знать «язык», который эффективен по отношению к цели. вычислительный агент (компьютер / вычислитель).
Но какую модель следует использовать для моделирования? Ван Эмде Боас замечает, что даже если мы будем основывать теорию сложности на абстрактных, а не на конкретную машинух, произвол в выборе модели остается. Именно здесь возникает понятие моделирования ». Когда измеряется скорость, имеет значение набор команд. Например, подпрограмма в алгоритме Евклида для вычисления остатка будет намного быстрее, если бы программист имел доступную инструкцию «модуль », а не просто вычитание (или, что еще хуже: просто «декремент» Мински).
Структурированное программирование, канонические структуры: Согласно тезису Черча - Тьюринга, любой алгоритм может быть вычислен с помощью модели, известной как полная по Тьюрингу, и, согласно демонстрациям Мински, Для полноты по Тьюрингу требуется только четыре типа инструкций - условный GOTO, безусловный GOTO, присваивание, HALT. Кемени и Курц замечают, что, хотя «недисциплинированное» использование безусловных GOTO и условных IF-THEN GOTO может привести к «спагетти-код », программист может писать структурированные программы, используя только эти инструкции; с другой стороны, «также возможно и не слишком сложно писать плохо структурированные программы на структурированном языке». Таусворте дополняет три канонических структур Бема-Якопини : SEQUENCE, IF-THEN-ELSE и WHILE-DO, еще две: DO-WHILE и CASE. Дополнительным преимуществом структурированной программы является то, что она обеспечивает доказательства правильности с использованием математической индукции.
Канонические символы блок-схемы: графический помощник, называемый блок-схемой, предлагает способ описать и задокументировать алгоритм (и компьютерную программу одного). Подобно программному потоку машины Мински, блок-схема всегда начинается в верхней части страницы и продолжается вниз. Его основных символов всего четыре: направленная стрелка, показывающая выполнение программы, прямоугольник (SEQUENCE, GOTO), ромб (IF-THEN-ELSE) и точка (OR-). Канонические структуры Бема - Якопини состоят из этих примитивных форм. Подконструкции могут «вкладываться» в прямоугольники, но только если один выход происходит из надстройки. Символы и для построения канонических использование их показано на схеме.
Один из простейших алгоритмов - найти наибольшее число в списке чисел в случайном порядке. Чтобы найти решение, нужно просмотреть все числа в списке. Из этого следует алгоритм, который может быть изложен в высокоуровневом английской прозой, как:
Высокоуровневое описание:
(Квази) формальное описание: Написано прозой, но намного ближе к высокоуровневому языку компьютерной программы, следующее представляет собой более формальное кодирование алгоритма в псевдокоде или пиджин-коде :
Алгоритм LargestNumber Ввод: список чисел L. Вывод: наибольшее число в списке L.
ifL.size = 0 возврат наибольшее значение null ← L [0] для каждого позиция в L, doifэлемент>наибольший, затем наибольший ← элемент возврат наибольший
Диаграмма-пример алгоритма Евклида из TL Heath (1908), с добавлением более подробной информации. Числовых примеров. Никомах приводит пример 49 и 21: «Я вычитаю меньшее из большего; 28 осталось; затем снова вычитаю из этого то же 21 (поскольку это возможно); 7 осталось; Я вычитаю это из 21, остается 14; снова вычитаю 7 (это возможно); Осталось 7, но 7 нельзя вычесть из 7. "Хит комментирует, что" Последнее фраза любопытна, но ее значение достаточно очевидно, как и значение фразы об окончании "на одно и то же число". (Хит 1908: 300). Алгоритм Евклида для вычислений наибольшего общего делителя (НОД) двух представленных как Предложение II в Книге VII («Элементарная теория чисел») из его Элементов. Евклид ставит задачу следующим образом: «Даны два числа, не простые друг другу, найти их наибольшую общую меру». Он определяет «Число [быть] множеством, состоящим из единиц»: счетное число, положительное целое число, не включая ноль. «Измерять» означает последовательно (q раз) link более короткую длину измерения s вдоль большей длины l, пока оставшаяся часть r не станет меньше длины s. r = l - q × s, q - частное, или остаток r - это «модуль», целочисленная дробная часть, оставшаяся после деления.
Для достижения успеха, начальные удовлетворять двум требованиям: (i) не должны быть равны нулю, И (ii) вычитание быть «правильным»; т.е. тест должен соответствовать, что меньшее из двух чисел вычитается из большего (или два могут быть равны, так что их вычитание дает ноль).
Первоначальное доказательство Евклида третье требование: две не должны быть простыми друг другу. Евклид сформулировал это так, чтобы он мог построить сокращение до абсурда доказательство того, что общее мера двух чисел на самом деле является величайшей. Хотя алгоритм Никомаха такой же, как и у Евклида, когда число просты по отношению друг к другу, он дает число «1» для их общей меры. Итак, если быть точным, следующий алгоритм Никомаха на самом деле.
Графическое выражение алгоритма Евклида для наибольшего общего делителя для 1599 и 650. 1599 = 650 × 2 + 299 650 = 299 × 2 + 52 299 = 52 × 5 + 39 52 = 39 × 1 + 13 39 = 13 × 3 + 0
Для выполнения алгоритма Евклида требуется всего несколько типов инструкций - некоторые логические тесты (условный GOTO), безусловный GOTO, присваивание (замена) и вычитание.
"Неэлегантная" - это перевод версии алгоритма Кнута с остаточным циклом на основе вычитания, заменяющим его использование деления (или инструкции "модуля")). По материалам Кнут 1973: 2–4. В зависимости от двух чисел «Неэлегантный» может вычислить g.c.d. с меньшим шагов, чем "Elegant". Следующий алгоритм как четырехэтапная версия алгоритма, используемого Евклида и Никомаха, но вместо того, чтобы использовать деление для нахождения остатка, он использует последовательные вычитания более короткой длины s из оставшаяся длина r, пока r не станет меньше s. Описание высокого, выделенное жирным шрифтом, адаптировано из Knuth 1973: 2–4:
INPUT :
1 [В двух местах L и S поместите числа l и s, которые соответствуют две длины]: INPUT L, S 2 [ Инициализировать R: сделать оставшуюся длину равной начальной / начальной / входной длине l]: R ← L
E0: [Убедитесь, что r ≥ s.]
3 [Убедитесь, что меньшее из двух чисел указано в S, большее в R]: ЕСЛИ R>S, ТО содержимое L является большим числом, поэтому пропустите этапы обмена 4, 5и 6 : GOTO step 6 ИНАЧЕ поменять местами содержимое R и S. 4 L ← R (этот первый шаг избыточен, но полезен для дальнейшего обсуждения). 5 R ← S 6 S ← L
E1: [Найти остаток] : до тех пор, пока оставшаяся длина r в R не станет меньше, чем более короткая длина s в S, многократно вычтите значение измерения s в S из длины r в R.
7 IF S>R ТО выполнено измерение, поэтому GOTO 10 ELSE измерьте снова, 8 R ← R - S 9 [Остаточный цикл]: GOTO 7.
E2: [Остаток равен нулю?] : ЛИБО (i) последняя мера была точной, остаток в R равен нулю, и программа может остановиться, ИЛИ (ii) алгоритм должен продолжаться: последняя мера оставила остаток в R меньше, чем измеренное число в S.
10 ЕСЛИ R = 0, ТО сделано это ПЕРЕЙДИТЕ к шагу 15 ИНАЧЕ ПРОДОЛЖИТЕ К шагу 11,
E3: [поменять местами s и r] : Гайка алгоритма Евклида. Используйте остаток r, чтобы измерить то, что раньше было меньшим числом s; L служит временным местом.
11 L ← R 12 R ← S 13 S ← L 14 [Повторить процесс измерения]: GOTO 7
ВЫХОД :
15 [Готово. S содержит наибольший общий делитель ]: PRINT S
DONE :
16 HALT, END, STOP.
Следующая версия алгоритма Евклида требует только шесть основных инструкций, чтобы сделать то, что тринадцать требуется для «Неэлегантности»; хуже того, «Неэлегантный» требует большего количества инструкций. Блок-схему «Элегант» можно найти в верхней части этой статьи. В (неструктурированном) базовом языке шаги пронумерованы, а инструкция LET =является инструкцией присваивания, обозначенной ←.
5 REM Алгоритм Евклида для наибольшего общего делителя 6 PRINT "Введите два целых числа больше 0" 10 INPUT A, B 20 IF B = 0 THEN GOTO 80 30 IF A>B THEN GOTO 60 40 LET B = BA 50 GOTO 20 60 LET A = AB 70 GOTO 20 80 PRINT A 90 END
Как работает «Elegant»: вместо внешней «петли Евклида» «Elegant» перемещается вперед и назад между двумя «параллельными петлями», A>Цикл B, который вычисляет A ← A - B, и цикл B ≤ A, который вычисляет B ← B - A. Это работает, потому что, когда, наконец, уменьшенное значение M меньше или равно вычитаемому S (Difference = Minuend - Subtrahend), уменьшенное значение может стать s (новая длина измерения), а вычитаемое значение может стать новым r (длина, которую необходимо измерить); другими словами, «смысл» вычитания меняется на противоположный.
Следующая версия может использоваться с языками программирования из семейства C :
// алгоритм Евклида для наибольшего общего делителя int euclidAlgorithm (int A, int B) {A = abs (A) ; В = абс (В); while (B! = 0) {если (A>B) A = A-B; иначе B = B-A; } return A; }Делает ли алгоритм то, что хочет его автор? Несколько тестовых примеров обычно дают некоторую уверенность в основной функциональности. Но тестов мало. Для тестовых случаев один источник использует 3009 и 884. Кнут предложил 40902, 24140. Другой интересный случай - два относительно простых числа 14157 и 5950.
Но "исключительные случаи" должны быть идентифицированы и проверено. Будет ли "Неэлегантность" работать правильно, когда R>S, S>R, R = S? То же для "Элегант": B>A, A>B, A = B? (Да для всех). Что происходит, когда одно число равно нулю, а оба числа равны нулю? («Неэлегантный» вычисляет вечно во всех случаях; «Элегантный» вычисляет вечно, когда A = 0.) Что произойдет, если введены отрицательные числа? Дробные числа? Если входные числа, то есть область функции, вычисленной алгоритмом / программой, должны включать только положительные целые числа, включая ноль, то сбои в нуле указывают, что алгоритм (и программа, которая создает экземпляр it) является частичной функцией, а не полной функцией. Заметным отказом из-за исключений является отказ ракеты Ariane 5 Flight 501 (4 июня 1996 г.).
Доказательство правильности программы с помощью математической индукции: Кнут демонстрирует применение математической индукции к «расширенной» версии алгоритма Евклида, и он предлагает «общий метод, применимый для доказательства валидность любого алгоритма ». Таусворте предлагает, чтобы мерой сложности программы была длина доказательства ее правильности.
Элегантность (компактность) против качества (скорости): всего шесть Основные инструкции, "Elegant" явный победитель по сравнению с "Inelegant" с тринадцатью инструкциями. Однако «Неэлегантный» быстрее (он достигает HALT за меньшее количество шагов). Анализ алгоритма показывает, почему это так: «Elegant» выполняет две условные проверки в каждом цикле вычитания, тогда как «Inelegant» только один. Поскольку алгоритм (обычно) требует большого количества циклов, в среднем много времени тратится впустую, делая "B = 0?" тест, который требуется только после вычисления остатка.
Можно ли улучшить алгоритмы ?: Как только программист оценивает программу «подходящей» и «эффективной», то есть вычисляет функцию, задуманную ее автором, возникает вопрос: можно ли ее улучшить?
Компактность «Неэлегантности» может быть улучшена за счет исключения пяти шагов. Но Чайтин доказал, что сжатие алгоритма не может быть автоматизировано с помощью обобщенного алгоритма; скорее, это можно сделать только эвристически ; т. е. путем исчерпывающего поиска (примеры можно найти в Занятый бобер ), проб и ошибок, сообразительности, проницательности, применения индуктивного мышления и т. д. Обратите внимание, что шаги 4, 5 и 6 повторяются на шагах 11, 12 и 13. Сравнение с «Elegant» подсказывает, что эти шаги вместе с шагами 2 и 3 можно исключить. Это уменьшает количество инструкций с тринадцати до восьми, что делает его «более элегантным», чем «Elegant», при девяти шагах.
Скорость «Elegant» можно повысить, переместив «B = 0?» тест вне двух циклов вычитания. Это изменение требует добавления трех инструкций (B = 0?, A = 0?, GOTO). Теперь "Elegant" быстрее вычисляет числа-примеры; Всегда ли это так для любых заданных A, B и R, S потребует подробного анализа.
Часто важно знать, какая часть определенного ресурса (например, времени или памяти) теоретически требуется для данного алгоритма. Разработаны методы алгоритмов анализа для получения количественных ответов (оценок); например, для приведенного выше алгоритма сортировки требуется время O (n) с использованием нотации большой O с n в предписании длины. Всегда алгоритму нужно запоминать только два значения: наибольшее число, найденное на момент, и его текущую последнюю в списке ввода. Следовательно, считается, что для него требуется пространство O (1), если пространство, необходимое для хранения входных чисел, не учитывается, или O (n), если оно считается.
Различные алгоритмы могут выполнить одну и ту же задачу с другими набором инструкций за меньшее или большее количество времени, пространства или «усилий », чем другие. Например, алгоритм двоичного поиска (со стоимостью O (log n)) превосходит последовательный поиск (стоимость O (n)) при использовании для поиска в таблице в отсортированных списках или массивх.
анализ и изучение алгоритмов является дисциплиной информатики, и часто практикуется абстрактно без использования конкретный язык программирования или его реализация. В этом смысле анализ алгоритмов напоминает другие математические дисциплины, поскольку он фокусируется на основных свойствах алгоритма, а не на специфике какой-либо алгоритм реализации. Обычно для анализа используется псевдокод , как это наиболее простое и общее представление. Однако в конечном итоге большинство алгоритмов реализуются на определенных аппаратных / программных платформах, и их алгоритмическая эффективность в конечном итоге подвергается проверке с использованием реального кода. Для решения «одноразовой» проблемы эффективного алгоритма может быть не имеет значительных последствий (если не является большим большим), но для алгоритмов, разработанных для быстрого интерактивного, коммерческого или длительного научного использования, это может быть критичным. Масштабирование от маленького n к большому n часто обнаруживает неэффективные алгоритмы, которые в остальном безобидны.
Эмпирическое тестирование эффективно, поскольку оно может выявить неожиданные реакции, влияющие на показатели. Тесты другая установка для сравнения до / после улучшений алгоритма после оптимизации программы. Однако эмпирические тесты не могут заменить формальный анализ, и их нетривиально выполнять честно.
Чтобы проиллюстрировать потенциальные улучшения, возможно даже в хорошо зарекомендовавших себя алгоритмах, недавно Нововведение, связанное с алгоритмами алгоритмов БПФ (широко используемыми в области обработки изображений), может сократить время обработки до 1000 раз для таких приложений, как получение медицинских изображений. Как правило, повышение скорости зависит от особых свойств задачи, которые очень часто встречаются в практических приложениях. Такое ускорение позволяет вычислительным устройствам, которые используют использование изображений (например, цифровые камеры и медицинское оборудование), потреблять меньше энергии.
Существуют различные способы классификации алгоритмов, каждый из которых имеет свои достоинства.
Один из способов классификации алгоритмов - это средства реализации.
int gcd (int A, int B) {если (B == 0) вернуть A; иначе, если (A>B) вернуть gcd (A-B, B); иначе вернуть gcd (A, B-A); } |
| Рекурсивная C реализация алгоритма Евклида из выше блок-схемы |
Другой способ классификации алгоритмов - по методологии их разработки или парадигме. Существует определенное количество парадигм, каждая из которых отличается от другой. Кроме того, каждая из этих категорий включает множество различных типов алгоритмов. Вот некоторые общие парадигмы:
Для задач оптимизации существует более конкретная классификация алгоритмов; алгоритм для таких проблем может попадать в одну или несколько общих категорий, описанных выше, а также в одну из следующих:
Каждая область науки имеет свои проблемы и потребности. эффективные алгоритмы. Связанные проблемы в одной области часто изучаются вместе. Некоторыми примерами классов являются алгоритмы поиска, алгоритмы сортировки, алгоритмы слияния, числовые алгоритмы, алгоритмы графа, строковые алгоритмы, вычислительные геометрические алгоритмы, комбинаторные алгоритмы, медицинские алгоритмы, машинное обучение, криптография, сжатие данных, алгоритмы и методы синтаксического анализа..
Поля имеют тенденцию перекрываться друг с другом, и усовершенствования алгоритмов в одном поле могут улучшить таковые в других, иногда совершенно не связанных, полях. Например, динамическое программирование было изобретено для оптимизации потребления ресурсов в промышленности, но теперь оно используется для решения широкого круга задач во многих областях.
Алгоритмы можно классифицировать по количеству времени, которое им необходимо для выполнения, по сравнению с их размером входных данных:
Некоторые задачи могут иметь несколько алгоритмов разной сложности, в то время как другие задачи могут не иметь алгоритмов или не иметь известных эффективных алгоритмов. Также есть сопоставления одних проблем с другими проблемами. В связи с этим было обнаружено, что более целесообразно классифицировать сами проблемы, а не алгоритмы, в классы эквивалентности на основе сложности наилучших возможных алгоритмов для них.
Прилагательное «непрерывный» в применении к слову «алгоритм» может означать:
Алгоритмы, сами по себе, как правило, не патентоспособны. В Соединенных Штатах утверждение, состоящее исключительно из простых манипуляций с абстрактными понятиями, числами или сигналами, не является «процессами» (USPTO 2006), и, следовательно, алгоритмы не являются патентоспособными (как в Gottschalk v. Benson ). Однако практическое применение алгоритмов иногда может быть запатентовано. Например, в деле Diamond v. Diehr применение простого алгоритма обратной связи для помощи в отверждении синтетического каучука было признано патентоспособным. Патентование программного обеспечения вызывает большие споры, и существуют сильно критикуемые патенты, касающиеся алгоритмов, особенно алгоритмов сжатия данных, таких как Unisys 'патент LZW.
Кроме того, некоторые криптографические алгоритмы имеют ограничения экспорта (см. экспорт криптографии ).
Самые ранние свидетельства использования алгоритмов находятся в вавилонской математике древних времен. Месопотамия (современный Ирак). Шумерская глиняная табличка, найденная в Шуруппак около Багдада и датированная примерно 2500 г. до н.э., описывала самый ранний алгоритм деления. Во время династии Хаммурапи около 1800-1600 гг. До н.э. вавилонские глиняные таблички описывали алгоритмы вычисления формул. Алгоритмы также использовались в вавилонской астрономии. Вавилонские глиняные таблички описывают и используют алгоритмические процедуры для вычисления времени и места значительных астрономических событий.
Алгоритмы для арифметики также встречаются в древней египетской математике, восходящей к Ринду. Математический папирус около 1550 г. до н.э. Позднее алгоритмы использовались в древней эллинистической математике. Двумя примерами являются Сито Эратосфена, которое было описано в Введение в арифметику Никомах, и алгоритм Евклида, который был впервые описан в Элементах Евклида (ок. 300 г. до н.э.).
Счетные метки: для отслеживания их стада, их мешков с зерном и свои деньги древние использовали для подсчета: накапливая камни или отметины, нацарапанные на палках, или лепили отдельные символы из глины. Благодаря вавилонскому и египетскому использованию знаков и символов в конечном итоге появились римские цифры и счеты (Дилсон, стр. 16–41). Счетные метки заметно выделяются в арифметике с унарной системой счисления, используемой в вычислениях машины Тьюринга и машины Пост-Тьюринга.
Мухаммад ибн Муса аль-Хваризми, персидский математик, написал Аль-Джабр в 9 веке. Термины «алгоритм » и «алгоритм» происходят от имени аль-Хваризми, а термин «алгебра » происходит из книги «Аль-Джабр». В Европе слово «алгоритм» первоначально использовалось для обозначения наборов правил и методов, используемых Аль-Хорезми для решения алгебраических уравнений, а затем было обобщено для обозначения любого набора правил или методов. В конечном итоге это привело к появлению у Лейбница концепции логического вычислителя (около 1680 г.):
За полтора века до своего времени Лейбниц предложил алгебру логики, алгебра, которая определяла бы правила для манипулирования логическими понятиями таким же образом, как обычная алгебра определяет правила для манипулирования числами.
Первый криптографический алгоритм для дешифрования зашифрованного кода был разработана Аль-Кинди, арабским математиком 9-го века , в «Рукописи о расшифровке криптографических сообщений». Он дал первое описание криптоанализа посредством частотного анализа, самого раннего алгоритма взлома кода.
Часы: Болтер считает изобретение приводимых под грузом часов «ключевым изобретением [Европы в средние века]», в частности, спусковым механизмом с краем, который дает нам с тиканьями механических часов. «Точная автоматическая машина» сразу же привела к «механическим автоматам », начиная с 13 века, и, наконец, к «вычислительным машинам» - разностной машине и аналитическим машинам Чарльз Бэббидж и графиня Ада Лавлейс, середина XIX века. Лавлейсу приписывают первое создание алгоритма, предназначенного для обработки на компьютере - аналитическую машину Бэббиджа, первое устройство, которое считалось реальным полным по Тьюрингу компьютером, а не просто калькулятором - и в результате ее иногда называют «первым программистом в истории», хотя полная реализация второго устройства Бэббиджа будет реализована только через десятилетия после ее жизни.
Логические машины 1870 - Стэнли Джевонс «логические счеты» и «логическая машина»: Техническая проблема заключалась в сокращении булевых уравнений, когда они представлены в форме, аналогичной то, что сейчас известно как Карты Карно. Джевонс (1880) сначала описывает простые «счеты», состоящие из «деревянных брусков, снабженных булавками, придуманных так, чтобы любую часть или класс [логических] комбинаций можно было выделить механически... Однако позднее я уменьшил систему до полностью механической формы и, таким образом, воплотили весь косвенный процесс вывода в том, что можно назвать логической машиной ». Его машина была оснащена« определенными подвижными деревянными стержнями », а« у подножия 21 клавиша, как у пианино [и т. д.]... ". С помощью этой машины он мог проанализировать «силлогизм или любой другой простой логический аргумент».
Эту машину он показал в 1870 году перед членами Королевского общества. Другой логик Джон Венн, однако, в своей «Символической логике 1881 года» обратил на это стремление предвзято: «Я сам не высоко оцениваю интерес или важность того, что иногда называют логическими машинами... мне не кажется, что какие-либо устройства, известные в настоящее время или которые могут быть обнаружены, действительно заслуживают названия логических машин "; подробнее см. Характеристики алгоритмов. Но чтобы не отставать, он также представил «план, в чем-то аналогичный, как я понимаю, со счетами профессора Джевона... [И] [а] выигрыш, соответствующий логической машине профессора Джевонса, может быть описан следующим образом. Я предпочитаю называть это просто машиной логических диаграмм... но я полагаю, что она могла бы очень полно делать все, что можно рационально ожидать от любой логической машины ".
Жаккардовый ткацкий станок, перфокарты Холлерита, телеграфия и телефония... электромеханическое реле: Белл и Ньюэлл (1971) указывают, что жаккардовый ткацкий станок (1801), предшественник карт Холлерита (перфокарты, 1887), и «технологии телефонной коммутации» были корни дерева, ведущие к созданию первых компьютеров. К середине 19 века телеграф, предшественник телефона, использовался во всем мире, его дискретное и различимое кодирование букв в виде «точек и тире» было обычным звуком. К концу 19 века использовалась тикерная лента (примерно 1870-е гг.), Как и карточки Холлерита при переписи населения США 1890 года. Затем появился телетайп (ок. 1910 г.) с использованием перфолентной бумаги кода Бодо на ленте.
Телефонные коммутационные сети с электромеханическими реле (изобретены в 1835 году) лежали в основе работы Джорджа Стибица (1937), изобретателя цифрового суммирующего устройства. Работая в Bell Laboratories, он наблюдал «обременительное» использование механических калькуляторов с шестеренками. Однажды вечером 1937 года он вернулся домой, намереваясь проверить свою идею... Когда работа была закончена, Стибиц сконструировал двоичное суммирующее устройство »..
Дэвис (2000) отмечает особую важность электромеханического реле (с его двумя «двоичными состояниями» - открытым и закрытым):
Символы и правила: быстро сменяющие друг друга математики Джордж Буль (1847, 1854), Готтлоб Фреге (1879) и Джузеппе Пеано (1888–1889) свели арифметику к последовательности символов, управляемых правилами. Принципы арифметики Пеано, представленные новым методом (1888 г.), были «первой попыткой аксиоматизации математики на символическом языке ".
. Но Хейенорт дает Фреге (1879 г.) такую похвалу:« Возможно, наиболее важное отдельное произведение, когда-либо написанное в логике.... в котором мы видим "язык формул", то есть lingua characterica, язык, написанный особыми символами, "для чистой мысли", то есть свободный от риторических украшений... построенный из определенных символов, которыми манипулируют по определенным правилам ». Работа Фреге была дополнительно упрощена и дополнена Альфредом Норт Уайтхедом и Бертраном Расселом в их Principia Mathematica (1910–1913).
Парадоксы: В то же время в литературе появился ряд тревожных парадоксов, в частности, парадокс Бурали-Форти (1897), парадокс Рассела (1902–03) и Ричард Парадокс. Полученные в результате соображения привели к статье Курта Гёделя (1931) - он конкретно цитирует парадокс лжеца - которая полностью сводит правила рекурсии к числам.
Эффективная вычислимость: в попытке решить Entscheidungsproblem, точно определенную Гильбертом в 1928 году, математики сначала приступили к определению того, что подразумевается под "эффективным методом" или "эффективным вычислением" или «эффективная вычислимость» (то есть расчет, который будет успешным). В быстрой последовательности появились следующие: Алонсо Черч, Стивен Клини и Дж. λ-исчисление Россера - тонко отточенное определение «общей рекурсии» из работы Гёделя, действующего по предложениям Жака Эрбрана (ср. Принстонские лекции Гёделя в 1934 г.) и последующие упрощения Клини. Доказательство Чёрча, что проблема Entscheidungspro неразрешима, определение Эмиля Поста эффективной вычислимости, когда рабочий бездумно следует списку инструкций, чтобы перемещаться влево или вправо через последовательность комнат и, находясь там, либо помечает, либо стирает бумагу. или посмотрите на бумагу и примите решение о следующей инструкции. Доказательство Алана Тьюринга того, что проблема Entscheidungspro неразрешима с помощью его «автоматической машины» - по сути, почти идентична «формулировке» Поста, J. Определение Баркли Россера «эффективного метода» в терминах «машины». Предложение предшественника «тезиса Чёрча », которое он назвал «Тезисом I», и несколько лет спустя позднее Клини переименовал свою диссертацию в «Тезис Чёрча» и предложил «Тезис Тьюринга».
Эмиль Пост (1936) описали действия «компьютера» (человека) следующим образом:
Его символьное пространство было бы
Статуя Алана Тьюринга в Блетчли-Парк Работа Алана Тьюринга предшествовала работе Стибица (1937); неизвестно, знал ли Стибиц о работе Тьюринга. Биограф Тьюринга полагал, что использование Тьюрингом модели, похожей на пишущую машинку, проистекает из юношеского интереса: «Алан мечтал изобрести пишущие машинки в детстве; у миссис Тьюринг была пишущая машинка, и он вполне мог начать с того, что спросил себя, что имелось в виду, когда говорил: a typewriter 'mechanical'". Given theпреобладание азбуки Морзе и телеграфии, тикерных лент и телетайпов, мы можем предположить, что все это было влиянием.
Тьюринг - его модель вычислений теперь называется машиной Тьюринга - начинается, как и Пост, с анализа человеческого компьютера, который он сокращает до простого набора основных движений и «душевные состояния». Но он делает еще один шаг и создает машину как модель вычисления чисел.
Редукция Тьюринга дает следующее:
« Возможно, некоторые из этих изменений обязательно вызовут изменение состояния ума. Поэтому наиболее общей единственной операцией следует считать одну из следующих:
Несколько лет спустя, Тьюринг расширил свой анализ (тезис, определение) этим убедительным выражением:
Дж. Баркли Россер определил «эффективный [математический] метод» следующим образом (курсив добавлен):
Сноска № 5 Россера указанныйе тся на работу (1) Черча и Клини и их определение λ-определимости, в частности, использование его Черчем в его «Неразрешимой проблеме элементарной теории чисел» (1936); (2) Хербранд и Гёдель и их использование рекурсии, в частности использование Гёделя в его знаменитой статье «О формально неразрешимых предложениях принципов» «Математика и родственные системы» I (1931 г.); и (3) Пост (1936 г.) и Тьюринг (1936–37) в их механических моделях вычислений.
Стивен К. Клини определил как его теперь известный «Тезис» Я "известен как тезис Черча-Тьюринга. Но он сделал это в следующем (жирным шрифтом в оригинале):
Персональные усилия были направлены на дальнейшее развитие уточнение определения« алгоритма », и работа продолжается из-за проблем, связанных, в частности, с основами математики (особенно тезис Черча - Тьюринга ) и философия разума (особенно аргументы о искусственном интеллекте ). Подробнее см. Характеристики алгоритмов.
 | Посмотрите вверх алгоритм в Викисловарь, словарь бесплатный. |
 | В Викиучебнике есть книга по теме: Алгоритмы |
 | на Викиверситет, вы можете узнать больше и научить других о алгоритме в Департаменте алгоритмов |
 | На Викискладе есть материалы, связанные с алгоритмами. |
