Алгоритм

Edit links
«Алгоритмы» перенаправляется сюда. Информацию об области информатики см. в разделе Анализ алгоритмов . Чтобы узнать о других значениях, см. Алгоритм (значения) .
В цикле вычтите большее число из меньшего. Остановите цикл, когда вычитание сделает число отрицательным. Оцените два числа, равно ли одно из них нулю или нет. Если да, то другое число примите за наибольший общий делитель. Если нет, снова поместите два числа в цикл вычитания.
Блок-схема использования последовательных вычитаний для нахождения наибольшего общего делителя чисел r и s

В математике и информатике алгоритм ​ ( / ˈ æ l ɡ ə r ɪ ð əm / ⓘ ) — это конечная последовательность математически строгих инструкций, обычно используемая для решения класса конкретных задач или выполнения вычислений . [1] Алгоритмы используются в качестве спецификаций для выполнения вычислений и обработки данных . Более продвинутые алгоритмы могут использовать условные выражения, чтобы перенаправить выполнение кода по различным маршрутам (так называемое автоматическое принятие решений ) и сделать правильные выводы (так называемые автоматизированные рассуждения ), в конечном итоге достигнув автоматизации . Использование человеческих характеристик в качестве метафорического описания машин уже практиковалось Аланом Тьюрингом с такими терминами, как «память», «поиск» и «стимул». [2]

Напротив, эвристика — это подход к решению проблем, который может быть не полностью определен или не может гарантировать правильные или оптимальные результаты, особенно в проблемных областях, где нет четко определенного правильного или оптимального результата. [3] Например, рекомендательные системы социальных сетей полагаются на эвристику таким образом, что, хотя в популярных средствах массовой информации 21 века их широко называют «алгоритмами», они не могут дать правильные результаты из-за характера проблемы.

В качестве эффективного метода алгоритм может быть выражен в пределах конечного объема пространства и времени. [4] и на четко определенном формальном языке [5] для вычисления функции . [6] Начиная с начального состояния и начального ввода (возможно, пустого ), [7] инструкции описывают вычисление, которое при выполнении происходит через конечное [8] количество четко определенных последовательных состояний, в конечном итоге производящих «выход» [9] и завершается в конечном конечном состоянии. Переход от одного состояния к другому не обязательно является детерминированным ; некоторые алгоритмы, известные как рандомизированные алгоритмы , включают случайные входные данные. [10]

Этимология [ править ]

Около 825 года нашей эры персидский ученый и эрудит Мухаммад ибн Муса аль-Хорезми написал «Китаб аль-Хисаб аль-хинди » («Книга индийских вычислений») и «Китаб аль-джам' ва'ль-тафрик аль-Хисаб аль-хинди» («Дополнение»). и вычитание в индийской арифметике»). [1] В начале XII века появились латинские переводы упомянутых текстов аль-Хорезми, включающие индуистско-арабскую систему счисления и арифметику , например, Liber Alghoarismi de practica arismetrice , приписываемую Иоанну Севильскому , и Liber Algorismi de numero Indorum , приписываемую Аделарду из Севильи. Ванна . [2] Таким образом, альгоаризми или альгорисми — это латинизация имени Аль-Хорезми; текст начинается с фразы Dixit Algorismi , или «Так говорил Аль-Хорезми». [3] английского слова «алгоризм» Около 1230 года было засвидетельствовано использование , а затем Чосером в 1391 году английский язык принял французский термин. [4] [5] [ нужны разъяснения ] В XV веке под влиянием греческого слова ἀριθμός ( арифмос , «число»; ср. «арифметика») латинское слово было изменено на алгоритмус . [ нужна ссылка ]

Определение [ править ]

Подробное представление различных точек зрения на определение «алгоритма» см. в разделе « Характеристики алгоритмов » .

Одно из неофициальных определений — это «набор правил, который точно определяет последовательность операций». [11] [ нужна цитата для проверки ] который будет включать все компьютерные программы (включая программы, не выполняющие числовые расчеты) и (например) любые предписанные бюрократические процедуры. [12] или из кулинарной книги рецепт . [13] В общем, программа является алгоритмом только в том случае, если она в конце концов останавливается. [14] — даже несмотря на то, что бесконечные циклы иногда могут оказаться желательными. Булос, Джеффри и 1974, 1999 определяют алгоритм как набор инструкций для определения результата, заданных явно в форме, которой может следовать либо вычислительная машина, либо человек, который может выполнять только определенные элементарные операции над символами. . [15]

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

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

История [ править ]

Древние алгоритмы [ править ]

С древности были засвидетельствованы пошаговые процедуры решения математических задач. Это включает в себя вавилонскую математику (около 2500 г. до н.э.), [16] Египетская математика (около 1550 г. до н. э.), [16] Индийская математика (около 800 г. до н.э. и позже), [17] [18] Оракул Ифа (около 500 г. до н. э.), греческая математика (около 240 г. до н. э.), [19] и арабская математика (около 800 г. н.э.). [20]

Самые ранние свидетельства существования алгоритмов можно найти в вавилонской математике древней Месопотамии (современный Ирак). Шумерская глиняная табличка , найденная в Шуруппаке недалеко от Багдада и датированная ок. В 2500 году до нашей эры был описан самый ранний алгоритм деления . [16] Во времена династии Хаммурапи ок. 1800 – ок. 1600 г. до н.э. на вавилонских глиняных табличках описаны алгоритмы вычисления формул. [21] Алгоритмы также использовались в вавилонской астрономии . Вавилонские глиняные таблички описывают и используют алгоритмические процедуры для расчета времени и места важных астрономических событий. [22]

Алгоритмы арифметики также встречаются в древнеегипетской математике , начиная с Математического папируса Ринда ок. 1550 г. до н.э. [16] Позднее алгоритмы использовались в древней эллинистической математике . Два примера — решето Эратосфена , которое было описано во « Введении в арифметику Никомаха » , [23] [19] : Глава 9.2 и алгоритм Евклида , который впервые был описан в «Началах» Евклида ( ок. 300 г. до н. э. ). [19] : Глава 9.1 Примеры древней индийской математики включают « Шулба-сутры» , школу Кералы и «Брахмасфутасиддханту» . [17]

Первый криптографический алгоритм для расшифровки зашифрованного кода был разработан Аль-Кинди , арабским математиком 9-го века, в «Рукописи о расшифровке криптографических сообщений» . Он дал первое описание криптоанализа с помощью частотного анализа , самого раннего алгоритма взлома кода. [20]

Компьютеры [ править ]

Часы с весом [ править ]

Болтер считает изобретение часов с весовым приводом «ключевым изобретением [Европы в Средневековье]». В частности, он отдает должное спускового механизма . механизму [24] это дает нам тиканье механических часов. «Точный автомат» [25] привело немедленно к «механическим автоматам », начиная с 13 века, и, наконец, к «вычислительным машинам» — разностной машине и аналитическим машинам Чарльза Бэббиджа и графини Ады Лавлейс в середине 19 века. [26] Лавлейсу приписывают первое создание алгоритма, предназначенного для обработки на компьютере - аналитической машины Бэббиджа, первого устройства, которое считалось настоящим Тьюринг-полным компьютером, а не просто калькулятором - и в результате его иногда называют «первым программистом в истории». хотя полная реализация второго устройства Бэббиджа будет реализована только спустя десятилетия после ее жизни.

Электромеханическое реле [ править ]

Белл и Ньюэлл (1971) указывают, что жаккардовый ткацкий станок (1801 г.), предшественник карт Холлерита (перфокарты, 1887 г.), и «технологии телефонной коммутации» были корнями дерева, приведшего к разработке первых компьютеров. [27] К середине 19-го века телеграф , предшественник телефона, использовался во всем мире, а его дискретное и различимое кодирование букв в виде «точек и тире» было обычным звуком. К концу 19 века стала использоваться бегущая лента ( около 1870-х годов ), а также карты Холлерита при переписи населения США 1890 года. Затем появился телетайп ( ок. 1910 г. ) с перфолентой, в которой код Бодо был записан на ленте.

Телефонно-коммутационные сети электромеханических реле (изобретены в 1835 г.) легли в основу работ Джорджа Стибитца (1937 г.), изобретателя цифрового суммирующего устройства. Работая в Bell Laboratories, он наблюдал «обременительное» использование механических калькуляторов с шестернями. «Однажды вечером в 1937 году он пошел домой, намереваясь проверить свою идею... Когда работа была окончена, Стибиц сконструировал устройство двоичного сложения». . [28] Математик Мартин Дэвис поддержал особую важность электромеханического реле. [29]

Формализация [ править ]

Ады Лавлейс Диаграмма из « Note G », первого опубликованного компьютерного алгоритма.

В 1928 году началась частичная формализация современной концепции алгоритмов с попыток решить Entscheidungsproblem ( проблему принятия решений), поставленную Дэвидом Гильбертом . Более поздние формализации были оформлены как попытки определить « эффективную вычислимость ». [30] или «эффективный метод». [31] Эти формализации включали рекурсивные функции Гёделя – Эрбрана – Клини 1930, 1934 и 1935 годов, Чёрча Алонзо лямбда-исчисление 1936 года, Эмиля Поста 1936 формулу 1 года и Алана Тьюринга 1936–37 машины Тьюринга и 1939 годов.

Представления [ править ]

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

Машины Тьюринга [ править ]

Существует большое разнообразие возможных представлений, и можно выразить данную программу машины Тьюринга как последовательность машинных таблиц (подробнее см. Конечный автомат , таблица переходов состояний и таблица управления ), как блок-схемы и драконовые диаграммы (см . диаграмму для получения дополнительной информации) или как форму элементарного машинного кода или ассемблерного кода, называемого «наборами четверок» ( см. в разделе « Машина Тьюринга более подробную информацию »). Представления алгоритмов также можно разделить на три общепринятых уровня описания машины Тьюринга: описание высокого уровня, описание реализации и формальное описание. [32] Описание высокого уровня описывает качества самого алгоритма, игнорируя то, как он реализован на машине Тьюринга. [32] Описание реализации описывает общий способ, которым машина перемещает голову и сохраняет данные для выполнения алгоритма, но не дает точных состояний. [32] Наиболее подробно формальное описание дает точную таблицу состояний и список переходов машины Тьюринга. [32]

Представление блок-схемы [ править ]

Графическое средство, называемое блок-схемой, предлагает способ описания и документирования алгоритма (и соответствующей ему компьютерной программы). Подобно потоку программы на машине Мински, блок-схема всегда начинается вверху страницы и продолжается вниз. Его основных символов всего четыре: направленная стрелка, показывающая ход выполнения программы, прямоугольник (SEQUENCE, GOTO), ромб (IF-THEN-ELSE) и точка (ИЛИ-связь). Канонические структуры Бема – Якопини состоят из этих примитивных форм. Подструктуры могут «вкладываться» в прямоугольники, но только в том случае, если из надстройки происходит единственный выход. Символы и их использование для построения канонических структур показаны на схеме. [33]

Алгоритмический анализ [ править ]

Основная статья: Анализ алгоритмов

Часто важно знать, сколько определенного ресурса (например, времени или памяти) теоретически требуется для данного алгоритма. Разработаны методы анализа алгоритмов получения таких количественных ответов (оценок); например, алгоритм, который складывает элементы списка из n чисел, потребует времени , используя большое обозначение O . Алгоритму всегда нужно помнить только два значения: сумму всех элементов на данный момент и его текущую позицию во входном списке. Поэтому говорят, что ему требуется пространство размером , если пространство, необходимое для хранения введенных чисел, не учтено, или если это засчитано.

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

Формальный против эмпирического [ править ]

Основные статьи: Эмпирическая алгоритмика , Профилирование (компьютерное программирование) и Оптимизация программ.

Анализ и изучение алгоритмов — это дисциплина информатики , которая часто практикуется абстрактно, без использования конкретного языка программирования или реализации. В этом смысле анализ алгоритмов похож на другие математические дисциплины, поскольку он фокусируется на основных свойствах алгоритма, а не на особенностях какой-либо конкретной реализации. Обычно для анализа используется псевдокод , поскольку это самое простое и общее представление. Однако в конечном итоге большинство алгоритмов обычно реализуются на определенных аппаратных/программных платформах, и их алгоритмическая эффективность в конечном итоге проверяется с использованием реального кода. Для решения «разовой» проблемы эффективность конкретного алгоритма может не иметь существенных последствий (если только n не чрезвычайно велико), но для алгоритмов, предназначенных для быстрого интерактивного, коммерческого или длительного научного использования, это может иметь решающее значение. Масштабирование от маленького n до большого n часто приводит к появлению неэффективных алгоритмов, которые в остальном безвредны.

Эмпирическое тестирование полезно, поскольку оно может выявить неожиданные взаимодействия, влияющие на производительность. Тесты можно использовать для сравнения возможных улучшений алгоритма до/после после оптимизации программы. Однако эмпирические тесты не могут заменить формальный анализ, и их не так просто выполнить честно. [34]

Эффективность исполнения [ править ]

Основная статья: Алгоритмическая эффективность

Чтобы проиллюстрировать потенциальные улучшения, возможные даже в хорошо зарекомендовавших себя алгоритмах, недавнее важное нововведение, касающееся алгоритмов БПФ (широко используемых в области обработки изображений), может сократить время обработки до 1000 раз для таких приложений, как медицинская визуализация. [35] В общем, повышение скорости зависит от особых свойств задачи, которые очень распространены в практических приложениях. [36] Ускорение такого масштаба позволяет вычислительным устройствам, широко использующим обработку изображений (например, цифровым камерам и медицинскому оборудованию), потреблять меньше энергии.

Дизайн [ править ]

См. также: Алгоритм § По парадигме проектирования.

Разработка алгоритма относится к методу или математическому процессу решения проблем и разработки алгоритмов. Разработка алгоритмов является частью многих теорий решения, таких как «разделяй и властвуй» или динамическое программирование в рамках исследования операций . Методы разработки и реализации алгоритмов также называются шаблонами проектирования алгоритмов. [37] с примерами, включая шаблон метода шаблона и шаблон декоратора. Одним из наиболее важных аспектов разработки алгоритмов является эффективность использования ресурсов (время выполнения, использование памяти); Обозначение «большое О» используется, например, для описания роста алгоритма во время выполнения по мере увеличения размера входных данных. [38]

Структурное программирование [ править ]

Согласно тезису Чёрча-Тьюринга , любой алгоритм может быть вычислен с помощью модели, известной как полная по Тьюрингу . Фактически было продемонстрировано, что для полноты по Тьюрингу требуется только четыре типа инструкций — условный GOTO, безусловный GOTO, присваивание и HALT. Однако Кемени и Курц отмечают, что, хотя «недисциплинированное» использование безусловных GOTO и условных IF-THEN GOTO может привести к « спагетти-коду », программист может писать структурированные программы, используя только эти инструкции; с другой стороны, «также возможно и не слишком сложно писать плохо структурированные программы на структурированном языке». [39] Таусворт дополняет три канонические структуры Бема-Якопини : [40] SEQUENCE, IF-THEN-ELSE и WHILE-DO, а также еще два: DO-WHILE и CASE. [41] Дополнительным преимуществом структурированной программы является то, что ее корректность можно доказать с помощью математической индукции . [42]

Классификация [ править ]

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

По реализации [ править ]

Один из способов классификации алгоритмов — по средствам реализации. 

int gcd(int A, int B) {
    if (B == 0)
        return A;
    else if (A > B)
        return gcd(A-B,B);
    else
        return gcd(A,B-A);
}
Рекурсивная на языке C реализация алгоритма Евклида из приведенной выше блок-схемы
Рекурсия
— Рекурсивный алгоритм это алгоритм, который неоднократно вызывает себя (ссылается на него) до тех пор, пока не будет достигнуто определенное условие (также известное как условие завершения), что является общим методом функционального программирования . Итеративные алгоритмы используют повторяющиеся конструкции, такие как циклы , а иногда и дополнительные структуры данных, такие как стеки, для решения заданных задач. Некоторые задачи естественным образом подходят для той или иной реализации. Например, Ханойские башни хорошо понимаются с помощью рекурсивной реализации. Каждая рекурсивная версия имеет эквивалентную (но, возможно, более или менее сложную) итеративную версию, и наоборот.
Последовательный, параллельный или распределенный
Алгоритмы обычно обсуждаются в предположении, что компьютеры выполняют одну инструкцию алгоритма за раз. Эти компьютеры иногда называют последовательными компьютерами. Алгоритм , разработанный для такой среды, называется последовательным алгоритмом, в отличие от параллельных алгоритмов или распределенных алгоритмов . Параллельные алгоритмы — это алгоритмы, использующие преимущества компьютерной архитектуры, в которой несколько процессоров могут одновременно работать над проблемой. Распределенные алгоритмы — это алгоритмы, в которых используются несколько машин, подключенных к компьютерной сети. Параллельные и распределенные алгоритмы делят проблему на более симметричные или асимметричные подзадачи и собирают результаты обратно. Например, ЦП может быть примером параллельного алгоритма. Потребление ресурсов в таких алгоритмах — это не только циклы работы каждого процессора, но и накладные расходы на связь между процессорами. Некоторые алгоритмы сортировки можно эффективно распараллелить, но их коммуникационные издержки являются дорогостоящими. Итеративные алгоритмы, как правило, поддаются распараллеливанию, но некоторые задачи не имеют параллельных алгоритмов и называются по своей сути последовательными задачами.
Детерминированный или недетерминированный
Детерминированные алгоритмы решают проблему с точным решением на каждом этапе алгоритма, тогда как недетерминированные алгоритмы решают проблемы путем угадывания, хотя типичные предположения становятся более точными за счет использования эвристики .
Точный или приблизительный
Хотя многие алгоритмы достигают точного решения, алгоритмы аппроксимации ищут приближение, которое ближе к истинному решению. Аппроксимация может быть достигнута с использованием детерминированной или случайной стратегии. Такие алгоритмы имеют практическую ценность для решения многих сложных задач. Одним из примеров приближенного алгоритма является задача о рюкзаке , где имеется набор заданных предметов. Его цель – упаковать рюкзак так, чтобы получить максимальную общую ценность. Каждый предмет имеет некоторый вес и некоторую ценность. Общий вес, который можно перевезти, не превышает некоторого фиксированного числа X. Таким образом, решение должно учитывать вес предметов, а также их стоимость. [43]
Квантовый алгоритм
Квантовые алгоритмы работают на реалистичной модели квантовых вычислений . Этот термин обычно используется для тех алгоритмов, которые по своей сути кажутся квантовыми или используют некоторые существенные особенности квантовых вычислений, такие как квантовая суперпозиция или квантовая запутанность .

По парадигме дизайна [ править ]

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

Грубая сила или полный перебор
Грубая сила — это метод решения проблем, который включает в себя систематическое перебор всех возможных вариантов, пока не будет найдено оптимальное решение. Этот подход может занять очень много времени, поскольку требует анализа всех возможных комбинаций переменных. Однако его часто используют, когда другие методы недоступны или слишком сложны. Грубую силу можно использовать для решения множества задач, включая поиск кратчайшего пути между двумя точками и взлом паролей.
Разделяй и властвуй
Алгоритм «разделяй и властвуй» неоднократно сводит экземпляр проблемы к одному или нескольким более мелким экземплярам той же проблемы (обычно рекурсивно ), пока экземпляры не станут достаточно маленькими, чтобы их можно было легко решить. Одним из таких примеров принципа «разделяй и властвуй» является сортировка слиянием . Сортировка может выполняться для каждого сегмента данных после разделения данных на сегменты, а сортировка всех данных может быть получена на этапе завоевания путем объединения сегментов. Более простой вариант «разделяй и властвуй» называется алгоритмом «уменьшай и властвуй» , который решает идентичную подзадачу и использует решение этой подзадачи для решения более крупной проблемы. Метод «разделяй и властвуй» делит проблему на несколько подзадач, поэтому этап завоевания более сложен, чем алгоритмы «уменьшай и властвуй». Примером алгоритма уменьшения и завоевания является алгоритм двоичного поиска .
Поиск и перечисление
Многие задачи (например, игра в шахматы ) можно смоделировать как задачи на графах . Алгоритм исследования графа определяет правила перемещения по графу и полезен для решения таких задач. В эту категорию также входят алгоритмы поиска , перечисление ветвей и границ и возврат .
Рандомизированный алгоритм
Такие алгоритмы делают некоторые выборы случайным (или псевдослучайным) образом. Они могут быть очень полезны при поиске приближенных решений задач, для которых поиск точных решений может быть непрактичным (см. эвристический метод ниже). Известно, что для некоторых из этих задач самые быстрые приближения должны включать в себя некоторую случайность . [44] Могут ли рандомизированные алгоритмы с полиномиальной временной сложностью быть самым быстрым алгоритмом для некоторых задач — открытый вопрос, известный как проблема P и NP . Существует два больших класса таких алгоритмов:
  1. Алгоритмы Монте-Карло возвращают правильный ответ с высокой вероятностью. Например, RP является их подклассом, который работает за полиномиальное время .
  2. Алгоритмы Лас-Вегаса всегда возвращают правильный ответ, но время их работы ограничено только вероятностно, например ZPP .
Уменьшение сложности
Этот метод предполагает решение сложной проблемы путем преобразования ее в более известную задачу, для которой у нас есть (надеюсь) асимптотически оптимальные алгоритмы. Цель состоит в том, чтобы найти сокращающий алгоритм, сложность которого не будет зависеть от результирующего сокращенного алгоритма. Например, один алгоритм выбора для поиска медианы в несортированном списке включает сначала сортировку списка (дорогая часть), а затем извлечение среднего элемента из отсортированного списка (дешевая часть). Эта техника также известна как трансформация и завоевание .
обратное отслеживание
В этом подходе несколько решений создаются постепенно и от них отказываются, когда выясняется, что они не могут привести к действительному полному решению.

Проблемы оптимизации [ править ]

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

Линейное программирование
При поиске оптимальных решений линейной функции, связанной с ограничениями линейного равенства и неравенства, ограничения задачи могут быть использованы непосредственно для получения оптимальных решений. Существуют алгоритмы, способные решить любую задачу этой категории, например популярный симплекс-алгоритм . [45] Проблемы, которые можно решить с помощью линейного программирования, включают задачу максимального потока для ориентированных графов. Если задача дополнительно требует, чтобы одно или несколько неизвестных были целыми числами , тогда это классифицируется как целочисленное программирование . Алгоритм линейного программирования может решить такую ​​задачу, если можно доказать, что все ограничения на целочисленные значения поверхностны, т. е. решения в любом случае удовлетворяют этим ограничениям. В общем случае используется специализированный алгоритм или алгоритм, находящий приближенные решения, в зависимости от сложности задачи.
Динамическое программирование
Когда проблема имеет оптимальные подструктуры (это означает, что оптимальное решение проблемы может быть построено из оптимальных решений подзадач) и перекрывающиеся подзадачи (то есть одни и те же подзадачи используются для решения многих разных экземпляров проблемы), более быстрый подход, называемый динамическим программированием, позволяет избежать повторного вычисления решений, которые уже вычислены. Например, алгоритм Флойда-Уоршалла , кратчайший путь к цели из вершины во взвешенном графе можно найти, используя кратчайший путь к цели из всех соседних вершин. Динамическое программирование и мемоизация идут рука об руку. Основное различие между динамическим программированием и «разделяй и властвуй» заключается в том, что подзадачи в «разделяй и властвуй» более или менее независимы, тогда как в динамическом программировании подзадачи перекрываются. Разница между динамическим программированием и простой рекурсией заключается в кэшировании или мемоизации рекурсивных вызовов. Когда подзадачи независимы и нет повторения, запоминание не помогает; следовательно, динамическое программирование не является решением всех сложных проблем. Используя мемоизацию или поддерживая В таблице уже решенных подзадач динамическое программирование сводит экспоненциальный характер многих задач к полиномиальной сложности.
Жадный метод
похож Жадный алгоритм на алгоритм динамического программирования тем, что он работает, исследуя подструктуры, в данном случае не проблемы, а заданного решения. Такие алгоритмы начинаются с некоторого решения, которое может быть задано или было построено каким-либо образом, и улучшают его путем внесения небольших модификаций. Для некоторых задач они могут найти оптимальное решение, тогда как для других они останавливаются на локальных оптимумах , то есть на решениях, которые не могут быть улучшены алгоритмом, но не являются оптимальными. Наиболее популярное использование жадных алгоритмов — поиск минимального остовного дерева, где с помощью этого метода возможно найти оптимальное решение. Huffman Tree , Kruskal , Prim , Sollin — жадные алгоритмы, способные решить эту задачу оптимизации.
Эвристический метод
В задачах оптимизации эвристические алгоритмы могут использоваться для поиска решения, близкого к оптимальному, в тех случаях, когда поиск оптимального решения нецелесообразен. Эти алгоритмы работают, все ближе и ближе приближаясь к оптимальному решению по мере своего развития. В принципе, если бежать бесконечное количество времени, они найдут оптимальное решение. Их заслуга в том, что они могут за относительно короткое время найти решение, очень близкое к оптимальному. К таким алгоритмам относятся локальный поиск , поиск с запретами , имитация отжига и генетические алгоритмы . Некоторые из них, например имитация отжига, являются недетерминированными алгоритмами, тогда как другие, например поиск с запретами, являются детерминированными. Когда известна граница ошибки неоптимального решения, алгоритм далее классифицируется как алгоритм аппроксимации .

Юридический статус [ править ]

См. Также: Патент на программное обеспечение.

Сами по себе алгоритмы обычно не патентоспособны. В Соединенных Штатах заявка, состоящая исключительно из простых манипуляций с абстрактными понятиями, числами или сигналами, не представляет собой «процессы» (USPTO 2006), поэтому алгоритмы не подлежат патентованию (как в деле Готшалк против Бенсона ). Однако практическое применение алгоритмов иногда патентоспособно. Например, в деле Даймонд против Дира применение простого алгоритма обратной связи для отверждения синтетического каучука было признано патентоспособным. Патентование программного обеспечения является спорным вопросом. [46] Есть критикуемые патенты, связанные с алгоритмами, особенно алгоритмами сжатия данных такие как Unisys , патент LZW . Кроме того, некоторые криптографические алгоритмы имеют ограничения на экспорт (см. Экспорт криптографии ).

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

Дополнительная информация: Список алгоритмов.

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

Описание высокого уровня:

  1. Если в наборе нет чисел, то нет и старшего числа.
  2. Предположим, что первое число в наборе является самым большим числом в наборе.
  3. Для каждого оставшегося числа в наборе: если это число больше текущего самого большого числа, считайте это число самым большим числом в наборе.
  4. Если в наборе не осталось чисел для перебора, считайте, что текущее наибольшее число является самым большим числом в наборе.

(Квази-)формальное описание: Ниже приводится более формальное кодирование алгоритма в псевдокоде или пиджин-коде , написанное прозой, но гораздо ближе к языку высокого уровня компьютерной программы : 

Algorithm LargestNumber
Input: A list of numbers L.
Output: The largest number in the list L.

if L.size = 0 return null
largest ← L[0]
for each item in L, do
    if item > largest, then
        largest ← item
return largest
  • « ←» означает присвоение . Например, « самый большой ← элемент » означает, что значение самого большого изменяется на значение элемента .
  • « return » завершает алгоритм и выводит следующее значение.

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

Примечания [ править ]

  1. ↑ Перейти обратно: Перейти обратно: а б «Определение АЛГОРИТМА» . Интернет-словарь Мерриам-Вебстера . Архивировано из оригинала 14 февраля 2020 года . Проверено 14 ноября 2019 г.
  2. ↑ Перейти обратно: Перейти обратно: а б Блер, Энн, Дугид, Пол, Гоинг, Аня-Сильвия и Графтон, Энтони. Информация: Исторический спутник, Принстон: Princeton University Press, 2021. с. 247
  3. ↑ Перейти обратно: Перейти обратно: а б Дэвид А. Гроссман, Офир Фридер, Информационный поиск: алгоритмы и эвристика , 2-е издание, 2004 г., ISBN   1402030045
  4. ↑ Перейти обратно: Перейти обратно: а б «Например, любой классический математический алгоритм можно описать конечным числом английских слов» (Rogers 1987:2).
  5. ↑ Перейти обратно: Перейти обратно: а б Четко определено в отношении агента, выполняющего алгоритм: «Существует вычислительный агент, обычно человек, который может реагировать на инструкции и выполнять вычисления» (Rogers 1987:2).
  6. ^ «Алгоритм - это процедура вычисления функции (относительно некоторых выбранных обозначений целых чисел) ... это ограничение (числовых функций) не приводит к потере общности» (Rogers 1987: 1).
  7. ^ «Алгоритм имеет ноль или более входных данных, то есть величин , которые ему задаются изначально до начала работы алгоритма» (Кнут 1973:5).
  8. ^ «Процедура, которая обладает всеми характеристиками алгоритма, за исключением того, что ей, возможно, не хватает конечности, может быть названа« вычислительным методом » » (Кнут 1973:5).
  9. ^ «Алгоритм имеет один или несколько выходных данных, то есть величин, которые имеют определенное отношение к входным данным» (Кнут 1973:5).
  10. ^ Является ли процесс со случайными внутренними процессами (не включая входные) алгоритмом, является дискуссионным. Роджерс полагает, что: «вычисления выполняются дискретно, поэтапно, без использования непрерывных методов или аналоговых устройств... осуществляются детерминированно, без обращения к случайным методам или устройствам, например, играм в кости» (Rogers 1987:2) .
  11. ^ Стоун 1973: 4
  12. ^ Симановский, Роберто (2018). Алгоритм смерти и другие цифровые дилеммы . Несвоевременные размышления. Том. 14. Перевод Чейза, Джефферсона. Кембридж, Массачусетс: MIT Press. п. 147. ИСБН  9780262536370 . Архивировано из оригинала 22 декабря 2019 года . Проверено 27 мая 2019 г. [...] следующий уровень абстракции центральной бюрократии: глобально действующие алгоритмы.
  13. ^ Дитрих, Эрик (1999). "Алгоритм". В Уилсоне, Роберт Эндрю; Кейл, Фрэнк С. (ред.). Энциклопедия когнитивных наук Массачусетского технологического института . Библиотека MIT Cognet. Кембридж, Массачусетс: MIT Press (опубликовано в 2001 г.). п. 11. ISBN  9780262731447 . Проверено 22 июля 2020 г. Алгоритм — это рецепт, метод или техника выполнения чего-либо.
  14. ^ Стоун требует, чтобы «он заканчивался за конечное число шагов» (Stone 1973:7–8).
  15. ^ Булос и Джеффри 1974,1999:19
  16. ↑ Перейти обратно: Перейти обратно: а б с д Шабер, Жан-Люк (2012). История алгоритмов: от камешка до микрочипа . Springer Science & Business Media. стр. 7–8. ISBN  9783642181924 .
  17. ↑ Перейти обратно: Перейти обратно: а б Шрирам, М.С. (2005). «Алгоритмы в индийской математике» . В Эмче, Джерард Г.; Шридхаран, Р.; Шринивас, доктор медицины (ред.). Вклад в историю индийской математики . Спрингер. п. 153. ИСБН  978-93-86279-25-5 .
  18. ^ Хаяши, Т. (1 января 2023 г.). Брахмагупта . Британская энциклопедия.
  19. ↑ Перейти обратно: Перейти обратно: а б с Кук, Роджер Л. (2005). История математики: Краткий курс . Джон Уайли и сыновья. ISBN  978-1-118-46029-0 .
  20. ↑ Перейти обратно: Перейти обратно: а б Дули, Джон Ф. (2013). Краткая история криптологии и криптографических алгоритмов . Springer Science & Business Media. стр. 12–3. ISBN  9783319016283 .
  21. ^ Кнут, Дональд Э. (1972). «Древние вавилонские алгоритмы» (PDF) . Коммун. АКМ . 15 (7): 671–677. дои : 10.1145/361454.361514 . ISSN   0001-0782 . S2CID   7829945 . Архивировано из оригинала (PDF) 24 декабря 2012 г.
  22. ^ Аабо, Асгер (2001). Эпизоды из ранней истории астрономии . Нью-Йорк: Спрингер. стр. 40–62. ISBN  978-0-387-95136-2 .
  23. ^ Аст, Кортни. «Эратосфен» . Государственный университет Уичито: факультет математики и статистики. Архивировано из оригинала 27 февраля 2015 года . Проверено 27 февраля 2015 г.
  24. ^ Болтер 1984:24
  25. ^ Болтер 1984:26
  26. ^ Болтер 1984: 33–34, 204–206.
  27. ^ Диаграмма Белла и Ньюэлла 1971:39, ср. Дэвис 2000
  28. ^ * Мелина Хилл, корреспондент Valley News, Мастер получает место в истории , Valley News Западный Ливан, Нью-Хэмпшир, четверг, 31 марта 1983 г., стр. 13.
  29. ^ Дэвис 2000:14
  30. ^ Клини 1943 в Дэвисе 1965: 274
  31. ^ Россер 1939 в Дэвисе 1965: 225
  32. ↑ Перейти обратно: Перейти обратно: а б с д Сипсер 2006:157
  33. ^ см. Таусворт, 1977 г.
  34. ^ Кригель, Ханс-Петер ; Шуберт, Эрих; Зимек, Артур (2016). «(Черное) искусство оценки во время выполнения: сравниваем ли мы алгоритмы или реализации?». Знания и информационные системы . 52 (2): 341–378. дои : 10.1007/s10115-016-1004-2 . ISSN   0219-1377 . S2CID   40772241 .
  35. ^ Джиллиан Конахан (январь 2013 г.). «Лучшая математика делает сети передачи данных быстрее» . Discovermagazine.com. Архивировано из оригинала 13 мая 2014 года . Проверено 13 мая 2014 г.
  36. ^ Хайтам Хассание, Петр Индик , Дина Катаби и Эрик Прайс, « Симпозиум ACM-SIAM по дискретным алгоритмам (SODA). Архивировано 4 июля 2013 г., в Wayback Machine , Киото, январь 2012 г. См. Также веб-страницу sFFT, архивированную 21 февраля. , 2012 год, в Wayback Machine .
  37. ^ Гудрич, Майкл Т .; Тамассия, Роберто (2002). Разработка алгоритмов: основы, анализ и примеры из Интернета . Джон Уайли и сыновья, Inc. ISBN  978-0-471-38365-9 . Архивировано из оригинала 28 апреля 2015 года . Проверено 14 июня 2018 г.
  38. ^ «Нотация Big-O (статья) | Алгоритмы» . Ханская академия . Проверено 3 июня 2024 г.
  39. ^ Джон Г. Кемени и Томас Э. Курц, 1985 г. «Возвращение к основам: история, коррупция и будущее языка» , Addison-Wesley Publishing Company, Inc. Ридинг, Массачусетс, ISBN   0-201-13433-0 .
  40. ^ Таусворт 1977: 101
  41. ^ Таусворт 1977: 142
  42. ^ Кнут 1973, раздел 1.2.1, расширен Таусвортом 1977 на стр. 100 и далее и в главе 9.1.
  43. ^ Келлерер, Ганс; Пферши, Ульрих; Пизингер, Дэвид (2004). Проблемы с рюкзаком | Ганс Келлерер | Спрингер . Спрингер. дои : 10.1007/978-3-540-24777-7 . ISBN  978-3-540-40286-2 . S2CID   28836720 . Архивировано из оригинала 18 октября 2017 года . Проверено 19 сентября 2017 г.
  44. ^ Например, объем ( выпуклого многогранника описанного с помощью оракула членства) можно аппроксимировать с высокой точностью с помощью алгоритма рандомизированного полиномиального времени, но не детерминированного: см. Дайер, Мартин; Фриз, Алан; Каннан, Рави (январь 1991 г.). «Случайный полиномиальный алгоритм аппроксимации объема выпуклых тел». Дж. АКМ . 38 (1): 1–17. CiteSeerX   10.1.1.145.4600 . дои : 10.1145/102782.102783 . S2CID   13268711 .
  45. ^ Джордж Б. Данциг и Мукунд Н. Тапа. 2003. Линейное программирование 2: теория и расширения . Спрингер-Верлаг.
  46. ^ «Эксперты: стимулирует ли патентная система инновации?» . Уолл Стрит Джорнал . 16 мая 2013 г. ISSN   0099-9660 . Проверено 29 марта 2017 г.

Библиография [ править ]

  • Заславский, К. (1970). Математика народа йоруба и их соседей в Южной Нигерии. Двухлетний математический журнал колледжа, 1 (2), 76–99. https://doi.org/10.2307/3027363

Дальнейшее чтение [ править ]

Внешние ссылки [ править ]

Найдите алгоритм в Викисловаре, бесплатном словаре.
В Wikibooks есть книга на тему: Алгоритмы.
В Викиверситете вы можете узнать больше и рассказать другим об алгоритмах на кафедре алгоритмов.
Викискладе есть медиафайлы, связанные с алгоритмами .
Хранилища алгоритмов
Retrieved from "https://en.wikipedia.org/w/index.php?title=Algorithm&oldid=1227499794"