stringtranslate.com

Алгоритм

В цикле вычтите большее число из меньшего. Остановите цикл, когда вычитание сделает число отрицательным. Оцените два числа, равно ли одно из них нулю или нет. Если да, возьмите другое число как наибольший общий делитель. Если нет, снова поместите два числа в цикл вычитания.
Блок-схема использования последовательных вычитаний для нахождения наибольшего общего делителя чисел 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] Таким образом, alghoarismi или algorismi является латинизацией имени Аль-Хорезми; текст начинается с фразы Dixit Algorismi , или «Так говорил Аль-Хорезми». [3] Около 1230 года засвидетельствовано английское слово algorism , а затем Чосером в 1391 году английский язык принял французский термин. [4] [5] [ необходимо разъяснение ] В 15 веке под влиянием греческого слова ἀριθμός ( arithmos , «число»; ср. «арифметика») латинское слово было изменено на algorithmus . [ необходима цитата ]

Определение

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

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

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

История

Древние алгоритмы

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

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

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

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

Компьютеры

Часы с гиревым приводом

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

Электромеханическое реле

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

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

Формализация

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

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

Представления

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

Машины Тьюринга

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

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

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

Алгоритмический анализ

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

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

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

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

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

Эффективность исполнения

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

Дизайн

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

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

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

Правовой статус

Алгоритмы сами по себе обычно не патентуются. В Соединенных Штатах иск, состоящий исключительно из простых манипуляций абстрактными понятиями, числами или сигналами, не является «процессами» (USPTO 2006), поэтому алгоритмы не патентуются (как в деле Gottschalk v. Benson ). Однако практическое применение алгоритмов иногда патентуется. Например, в деле Diamond v. Diehr применение простого алгоритма обратной связи для помощи в вулканизации синтетического каучука было признано патентоспособным. Патентование программного обеспечения является спорным [44], и существуют критикуемые патенты, включающие алгоритмы, особенно алгоритмы сжатия данных , такие как патент LZW компании Unisys . Кроме того, некоторые криптографические алгоритмы имеют экспортные ограничения (см. экспорт криптографии ).

Классификация

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

По реализации

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

Рекурсия
Рекурсивный алгоритм — это алгоритм, который многократно вызывает (ссылается на) себя, пока не совпадет определенное условие (также известное как условие завершения), что является методом, общим для функционального программирования . Итеративные алгоритмы используют повторяющиеся конструкции, такие как циклы , а иногда и дополнительные структуры данных, такие как стеки, для решения заданных задач. Некоторые задачи естественным образом подходят для одной или другой реализации. Например, ханойские башни хорошо понятны с использованием рекурсивной реализации. Каждая рекурсивная версия имеет эквивалентную (но, возможно, более или менее сложную) итеративную версию, и наоборот.
Последовательный, параллельный или распределенный
Алгоритмы обычно обсуждаются с предположением, что компьютеры выполняют одну инструкцию алгоритма за раз. Такие компьютеры иногда называют последовательными компьютерами. Алгоритм, разработанный для такой среды, называется последовательным алгоритмом, в отличие от параллельных алгоритмов или распределенных алгоритмов . Параллельные алгоритмы — это алгоритмы, которые используют преимущества компьютерных архитектур, где несколько процессоров могут работать над проблемой одновременно. Распределенные алгоритмы — это алгоритмы, которые используют несколько машин, подключенных к компьютерной сети. Параллельные и распределенные алгоритмы разделяют задачу на более симметричные или асимметричные подзадачи и собирают результаты обратно вместе. Например, ЦП может быть примером параллельного алгоритма. Потребление ресурсов в таких алгоритмах — это не только циклы процессора на каждом процессоре, но и накладные расходы на связь между процессорами. Некоторые алгоритмы сортировки можно эффективно распараллелить, но их накладные расходы на связь обходятся дорого. Итеративные алгоритмы, как правило, поддаются распараллеливанию, но некоторые задачи не имеют параллельных алгоритмов и называются по своей сути последовательными задачами.
Детерминированный или недетерминированный
Детерминированные алгоритмы решают проблему, принимая точное решение на каждом шаге алгоритма, тогда как недетерминированные алгоритмы решают проблемы с помощью догадок, хотя типичные догадки становятся более точными за счет использования эвристик .
Точные или приблизительные
В то время как многие алгоритмы достигают точного решения, алгоритмы приближения ищут приближение, которое ближе к истинному решению. Приближение может быть достигнуто либо с помощью детерминированной, либо случайной стратегии. Такие алгоритмы имеют практическую ценность для многих сложных задач. Одним из примеров приближенного алгоритма является задача о рюкзаке , где есть набор заданных предметов. Его цель — упаковать рюкзак, чтобы получить максимальную общую стоимость. Каждый предмет имеет некоторый вес и некоторую стоимость. Общий вес, который можно нести, не превышает некоторого фиксированного числа X. Таким образом, решение должно учитывать вес предметов, а также их стоимость. [45]
Квантовый алгоритм
Квантовые алгоритмы работают на реалистичной модели квантовых вычислений . Этот термин обычно используется для тех алгоритмов, которые кажутся по своей сути квантовыми или используют некоторые существенные особенности квантовых вычислений, такие как квантовая суперпозиция или квантовая запутанность .

По парадигме дизайна

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

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

Проблемы оптимизации

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

Линейное программирование
При поиске оптимальных решений для линейной функции, связанной с линейными ограничениями равенства и неравенства, ограничения задачи могут быть использованы непосредственно при получении оптимальных решений. Существуют алгоритмы, которые могут решить любую задачу в этой категории, например, популярный симплексный алгоритм . [47] Задачи, которые можно решить с помощью линейного программирования, включают задачу максимального потока для ориентированных графов. Если задача дополнительно требует, чтобы одно или несколько неизвестных были целыми числами, то она классифицируется в целочисленном программировании . Алгоритм линейного программирования может решить такую ​​задачу, если можно доказать, что все ограничения для целочисленных значений являются поверхностными, т. е. решения в любом случае удовлетворяют этим ограничениям. В общем случае используется специализированный алгоритм или алгоритм, который находит приближенные решения, в зависимости от сложности задачи.
Динамическое программирование
Когда проблема показывает оптимальные подструктуры — то есть оптимальное решение проблемы может быть построено из оптимальных решений подзадач — и перекрывающиеся подзадачи , то есть те же подзадачи используются для решения множества различных экземпляров задач, более быстрый подход, называемый динамическим программированием, позволяет избежать повторного вычисления решений, которые уже были вычислены. Например, алгоритм Флойда–Уоршелла , кратчайший путь к цели от вершины во взвешенном графе может быть найден путем использования кратчайшего пути к цели от всех смежных вершин. Динамическое программирование и мемоизация идут рука об руку. Главное различие между динамическим программированием и разделяй и властвуй заключается в том, что подзадачи более или менее независимы в разделяй и властвуй, тогда как подзадачи перекрываются в динамическом программировании. Разница между динамическим программированием и прямой рекурсией заключается в кэшировании или мемоизации рекурсивных вызовов. Когда подзадачи независимы и нет повторений, мемоизация не помогает; следовательно, динамическое программирование не является решением для всех сложных проблем. Используя мемоизацию или ведение таблицы уже решенных подзадач, динамическое программирование сводит экспоненциальную природу многих задач к полиномиальной сложности.
Жадный метод
Жадный алгоритм похож на алгоритм динамического программирования в том, что он работает, исследуя подструктуры, в данном случае не проблемы, а заданного решения. Такие алгоритмы начинаются с некоторого решения, которое может быть задано или было построено каким-то образом, и улучшают его, внося небольшие изменения. Для некоторых задач они могут найти оптимальное решение, в то время как для других они останавливаются на локальных оптимумах , то есть на решениях, которые не могут быть улучшены алгоритмом, но не являются оптимальными. Наиболее популярное использование жадных алгоритмов — поиск минимального остовного дерева, где нахождение оптимального решения возможно с помощью этого метода. Дерево Хаффмана , Крускал , Прим , Соллин — это жадные алгоритмы, которые могут решить эту задачу оптимизации.
Эвристический метод
В задачах оптимизации эвристические алгоритмы могут использоваться для поиска решения, близкого к оптимальному, в случаях, когда поиск оптимального решения нецелесообразен. Эти алгоритмы работают, приближаясь все ближе и ближе к оптимальному решению по мере продвижения. В принципе, если они выполняются в течение бесконечного времени, они найдут оптимальное решение. Их достоинство в том, что они могут найти решение, очень близкое к оптимальному, за относительно короткое время. Такие алгоритмы включают локальный поиск , поиск с запретами , имитацию отжига и генетические алгоритмы . Некоторые из них, такие как имитация отжига, являются недетерминированными алгоритмами, в то время как другие, такие как поиск с запретами, являются детерминированными. Когда известна граница ошибки неоптимального решения, алгоритм далее классифицируется как алгоритм приближения .

Примеры

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

Общее описание:

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

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

Алгоритм НаибольшееЧислоВходные данные
: список чисел L.Вывод :
наибольшее число в списке L.
если  L.size = 0 вернуть null largest ← L [0] для каждого  элемента  в  L , сделать  if  item > largest , then  largest ← item вернуть  largest

Смотрите также

Примечания

  1. ^ ab "Определение АЛГОРИТМА". Онлайн-словарь Merriam-Webster . Архивировано из оригинала 14 февраля 2020 г. Получено 14 ноября 2019 г.
  2. ^ ab Блэр, Энн, Дугид, Пол, Гоинг, Аня-Сильвия и Графтон, Энтони. Информация: Исторический компаньон, Принстон: Princeton University Press, 2021. стр. 247
  3. ^ Дэвид А. Гроссман, Офир Фридер, Информационный поиск: алгоритмы и эвристики , 2-е издание, 2004, ISBN 1402030045 
  4. ^ ab «Любой классический математический алгоритм, например, можно описать конечным числом английских слов» (Роджерс 1987:2).
  5. ^ ab Хорошо определено относительно агента, который выполняет алгоритм: «Существует вычислительный агент, обычно человек, который может реагировать на инструкции и выполнять вычисления» (Роджерс 1987:2).
  6. ^ «алгоритм — это процедура вычисления функции (относительно некоторой выбранной нотации для целых чисел)... это ограничение (числовыми функциями) не приводит к потере общности» (Роджерс 1987:1).
  7. ^ «Алгоритм имеет ноль или более входных данных, т. е. величин , которые даны ему изначально, до начала работы алгоритма» (Кнут 1973:5).
  8. ^ «Процедура, которая обладает всеми характеристиками алгоритма, за исключением того, что она, возможно, лишена конечности, может быть названа «вычислительным методом » » (Кнут 1973:5).
  9. ^ «Алгоритм имеет один или несколько выходов, т. е. величин, которые имеют указанное отношение к входным данным» (Кнут 1973:5).
  10. ^ Является ли процесс со случайными внутренними процессами (не включая входные данные) алгоритмом или нет, является спорным вопросом. Роджерс полагает, что: «вычисление выполняется дискретным пошаговым образом, без использования непрерывных методов или аналоговых устройств... осуществляется детерминированно, без обращения к случайным методам или устройствам, например, игральным костям» (Rogers 1987:2).
  11. ^ Стоун 1973:4
  12. ^ Симановски, Роберто (2018). Алгоритм смерти и другие цифровые дилеммы. Несвоевременные размышления. Том 14. Перевод Чейза, Джефферсона. Кембридж, Массачусетс: MIT Press. стр. 147. ISBN 9780262536370. Архивировано из оригинала 22 декабря 2019 г. . Получено 27 мая 2019 г. . [...] следующий уровень абстракции центральной бюрократии: глобально работающие алгоритмы.
  13. ^ Дитрих, Эрик (1999). «Алгоритм». В Wilson, Роберт Эндрю; Keil, Фрэнк К. (ред.). Энциклопедия когнитивных наук Массачусетского технологического института. Библиотека Cognet Массачусетского технологического института. Кембридж, Массачусетс: MIT Press (опубликовано в 2001 г.). стр. 11. ISBN 9780262731447. Получено 22 июля 2020 г. . Алгоритм — это рецепт, метод или техника выполнения чего-либо.
  14. ^ Стоун требует, чтобы «это завершилось конечным числом шагов» (Stone 1973:7–8).
  15. ^ Булос и Джеффри 1974,1999:19
  16. ^ abcd Шабер, Жан-Люк (2012). История алгоритмов: от Pebble до Microchip . Springer Science & Business Media. стр. 7–8. ISBN 9783642181924.
  17. ^ ab Sriram, MS (2005). "Алгоритмы в индийской математике". В Emch, Gerard G.; Sridharan, R.; Srinivas, MD (ред.). Вклад в историю индийской математики . Springer. стр. 153. ISBN 978-93-86279-25-5.
  18. ^ Хаяши, Т. (2023, 1 января). Брахмагупта. Энциклопедия Британника.
  19. ^ Заславский, Клаудия (1970). «Математика народа йоруба и их соседей в Южной Нигерии». Двухгодичный колледж математики. Журнал . 1 (2): 76–99. doi :10.2307/3027363. ISSN  0049-4925. JSTOR  3027363.
  20. ^ abc Кук, Роджер Л. (2005). История математики: краткий курс . John Wiley & Sons. ISBN 978-1-118-46029-0.
  21. ^ ab Dooley, John F. (2013). Краткая история криптологии и криптографических алгоритмов . Springer Science & Business Media. стр. 12–3. ISBN 9783319016283.
  22. ^ Кнут, Дональд Э. (1972). «Древние вавилонские алгоритмы» (PDF) . Commun. ACM . 15 (7): 671–677. doi :10.1145/361454.361514. ISSN  0001-0782. S2CID  7829945. Архивировано из оригинала (PDF) 24 декабря 2012 г.
  23. ^ Aaboe, Asger (2001). Эпизоды из ранней истории астрономии . Нью-Йорк: Springer. С. 40–62. ISBN 978-0-387-95136-2.
  24. ^ Аст, Кортни. «Эратосфен». Университет штата Уичито: Кафедра математики и статистики. Архивировано из оригинала 27 февраля 2015 г. Получено 27 февраля 2015 г.
  25. ↑ Болтер 1984:24
  26. ↑ Болтер 1984:26
  27. ^ Болтер 1984: 33–34, 204–206.
  28. ^ Диаграмма Белла и Ньюэлла 1971:39, см. Дэвис 2000
  29. ↑ Мелина Хилл, корреспондент Valley News, Мастер на все руки вошел в историю , Valley News West Lebanon NH, четверг, 31 марта 1983 г., стр. 13.
  30. ^ Дэвис 2000:14
  31. ↑ Клини 1943 в Дэвис 1965:274
  32. ^ Россер 1939 в Дэвисе 1965: 225
  33. ^ abcd Сипсер 2006:157
  34. ^ см. Таусворте 1977
  35. ^ Кригель, Ханс-Петер ; Шуберт, Эрих; Зимек, Артур (2016). «(Черное) искусство оценки времени выполнения: сравниваем ли мы алгоритмы или реализации?». Knowledge and Information Systems . 52 (2): 341–378. doi :10.1007/s10115-016-1004-2. ISSN  0219-1377. S2CID  40772241.
  36. ^ Джиллиан Конахан (январь 2013 г.). «Лучшая математика делает сети передачи данных более быстрыми». discovermagazine.com. Архивировано из оригинала 13 мая 2014 г. Получено 13 мая 2014 г.
  37. ^ Хайтам Хассание, Петр Индик , Дина Катаби и Эрик Прайс, «Симпозиум ACM-SIAM по дискретным алгоритмам (SODA)», архивировано 4 июля 2013 г. на Wayback Machine , Киото, январь 2012 г. См. также веб-страницу sFFT, архивировано 21 февраля 2012 г. на Wayback Machine .
  38. ^ Гудрич, Майкл Т.; Тамассиа , Роберто (2002). Разработка алгоритмов: основы, анализ и примеры Интернета. John Wiley & Sons, Inc. ISBN 978-0-471-38365-9. Архивировано из оригинала 28 апреля 2015 г. . Получено 14 июня 2018 г. .
  39. ^ "Нотация Big-O (статья) | Алгоритмы". Khan Academy . Получено 3 июня 2024 г. .
  40. ^ Джон Г. Кемени и Томас Э. Курц 1985 Назад к основам: история, коррупция и будущее языка , Addison-Wesley Publishing Company, Inc. Рединг, Массачусетс, ISBN 0-201-13433-0 . 
  41. ^ Таусворте 1977:101
  42. ^ Таусворте 1977:142
  43. ↑ Knuth 1973, раздел 1.2.1, расширенный Tausworthe 1977 на страницах 100ff и в главе 9.1
  44. ^ «Эксперты: поощряет ли патентная система инновации?». The Wall Street Journal . 16 мая 2013 г. ISSN  0099-9660 . Получено 29 марта 2017 г.
  45. ^ Келлерер, Ганс; Пферши, Ульрих; Пизингер, Дэвид (2004). Проблемы с рюкзаком | Ганс Келлерер | Спрингер. Спрингер. дои : 10.1007/978-3-540-24777-7. ISBN 978-3-540-40286-2. S2CID  28836720. Архивировано из оригинала 18 октября 2017 г. . Получено 19 сентября 2017 г. .
  46. ^ Например, объем выпуклого многогранника ( описанный с помощью оракула членства) может быть аппроксимирован с высокой точностью с помощью рандомизированного полиномиального алгоритма времени, но не детерминированного: см. Dyer, Martin; Frieze, Alan; Kannan, Ravi (январь 1991 г.). "A Random Polynomial-time Algorithm for Approximating the Volume of Convex Bodies". J. ACM . 38 (1): 1–17. CiteSeerX 10.1.1.145.4600 . doi :10.1145/102782.102783. S2CID  13268711. 
  47. ^ Джордж Б. Данциг и Мукунд Н. Тапа. 2003. Линейное программирование 2: Теория и расширения . Springer-Verlag.

Библиография

Дальнейшее чтение

Внешние ссылки

Найдите алгоритм в Викисловаре, бесплатном словаре.
В Wikibooks есть книга по теме: Алгоритмы
В Викиверситете вы можете узнать больше и научить других алгоритмам на кафедре алгоритмики.
На Викискладе есть медиафайлы по теме «Алгоритмы» .
Репозитории алгоритмов