stringtranslate.com

Алгоритм

В цикле вычтите большее число из меньшего. Остановите цикл, когда вычитание сделает число отрицательным. Оцените два числа, равно ли одно из них нулю или нет. Если да, возьмите другое число как наибольший общий делитель. Если нет, снова поместите два числа в цикл вычитания.
Блок-схема использования последовательных вычитаний для нахождения наибольшего общего делителя чисел r и s

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

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

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

Этимология

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

Определение

Одно неформальное определение — «набор правил, который точно определяет последовательность операций», [11] [ нужна цитата для проверки ], которое включает все компьютерные программы (включая программы, которые не выполняют числовые вычисления), а также любые предписанные бюрократические процедуры [12] или рецепты из кулинарной книги . [13] В общем, программа является алгоритмом только в том случае, если она в конечном итоге останавливается [14] — даже несмотря на то, что бесконечные циклы иногда могут оказаться желательными. Булос, Джеффри и 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). Подструктуры могут «вкладываться» в прямоугольники, но только если из надстройки есть единственный выход.

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

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

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

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

Анализ и изучение алгоритмов — это дисциплина компьютерной науки . Алгоритмы часто изучаются абстрактно, без ссылок на какой-либо конкретный язык программирования или реализацию. Анализ алгоритмов напоминает другие математические дисциплины, поскольку он фокусируется на свойствах алгоритма, а не на реализации. Псевдокод типичен для анализа, поскольку является простым и общим представлением. Большинство алгоритмов реализованы на определенных аппаратных/программных платформах, и их алгоритмическая эффективность проверяется с использованием реального кода. Эффективность конкретного алгоритма может быть незначительной для многих «разовых» задач, но она может быть критической для алгоритмов, разработанных для быстрого интерактивного, коммерческого или долгосрочного научного использования. Масштабирование от малого 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]

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

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

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

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

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

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

Другой способ классификации алгоритмов — по их методологии проектирования или парадигме . Некоторые общие парадигмы:

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

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

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

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

Примеры

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

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

  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. ^ Дэвид А. Гроссман, Офир Фридер, Информационный поиск: алгоритмы и эвристики , 2-е издание, 2004, ISBN 1402030045 
  3. ^ ab «Любой классический математический алгоритм, например, можно описать конечным числом английских слов» (Роджерс 1987:2).
  4. ^ ab Хорошо определено относительно агента, который выполняет алгоритм: «Существует вычислительный агент, обычно человек, который может реагировать на инструкции и выполнять вычисления» (Роджерс 1987:2).
  5. ^ «алгоритм — это процедура вычисления функции (относительно некоторой выбранной нотации для целых чисел)... это ограничение (числовыми функциями) не приводит к потере общности» (Роджерс 1987:1).
  6. ^ «Алгоритм имеет ноль или более входных данных, т. е. величин , которые даны ему изначально, до начала работы алгоритма» (Кнут 1973:5).
  7. ^ «Процедура, которая обладает всеми характеристиками алгоритма, за исключением того, что она, возможно, лишена конечности, может быть названа «вычислительным методом » » (Кнут 1973:5).
  8. ^ «Алгоритм имеет один или несколько выходов, т. е. величин, которые имеют указанное отношение к входным данным» (Кнут 1973:5).
  9. ^ Является ли процесс со случайными внутренними процессами (не включая входные данные) алгоритмом или нет, является спорным. Роджерс полагает, что: «вычисление выполняется дискретным пошаговым образом, без использования непрерывных методов или аналоговых устройств... продолжается детерминированно, без обращения к случайным методам или устройствам, например, игральным костям» (Rogers 1987:2).
  10. ^ Блэр, Энн, Дугид, Пол, Гоинг, Аня-Сильвия и Графтон, Энтони. Информация: Исторический компаньон, Принстон: Princeton University Press, 2021. стр. 247
  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. ^ Кригель, Ханс-Петер ; Шуберт, Эрих; Зимек, Артур (2016). «(Черное) искусство оценки времени выполнения: сравниваем ли мы алгоритмы или реализации?». Knowledge and Information Systems . 52 (2): 341–378. doi :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). Разработка алгоритмов: основы, анализ и примеры Интернета. John Wiley & Sons, Inc. ISBN 978-0-471-38365-9. Архивировано из оригинала 28 апреля 2015 г. . Получено 14 июня 2018 г. .
  38. ^ "Нотация Big-O (статья) | Алгоритмы". Khan Academy . Получено 3 июня 2024 г. .
  39. ^ Джон Г. Кемени и Томас Э. Курц 1985 Назад к основам: история, коррупция и будущее языка , Addison-Wesley Publishing Company, Inc. Рединг, Массачусетс, ISBN 0-201-13433-0 . 
  40. ^ Таусворте 1977:101
  41. ^ Таусворте 1977:142
  42. ↑ Knuth 1973, раздел 1.2.1, расширенный Tausworthe 1977 на страницах 100ff и в главе 9.1
  43. ^ «Эксперты: поощряет ли патентная система инновации?». The Wall Street Journal . 16 мая 2013 г. ISSN  0099-9660 . Получено 29 марта 2017 г.
  44. ^ Келлерер, Ганс; Пферши, Ульрих; Пизингер, Дэвид (2004). Проблемы с рюкзаком | Ганс Келлерер | Спрингер. Спрингер. дои : 10.1007/978-3-540-24777-7. ISBN 978-3-540-40286-2. S2CID  28836720. Архивировано из оригинала 18 октября 2017 г. . Получено 19 сентября 2017 г. .
  45. ^ Например, объем выпуклого многогранника ( описанный с помощью оракула членства) может быть аппроксимирован с высокой точностью с помощью рандомизированного полиномиального алгоритма времени, но не детерминированного: см. 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. 
  46. ^ Джордж Б. Данциг и Мукунд Н. Тапа. 2003. Линейное программирование 2: Теория и расширения . Springer-Verlag.

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

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

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

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