Введение

Последовательность операций для задачи

В математике и информатике алгоритм (/audio=en us алгоритм. ogg/'/æ//l//ɡ//ə//r//ɪ//ð//əm/) — это конечная последовательность математически строгих инструкций, обычно используемых для решения класса конкретных задач или для выполнения вычислений. Алгоритмы используются как спецификации для выполнения вычислений и обработки данных. Более продвинутые алгоритмы могут использовать условные операторы для направления выполнения кода по различным путям (известному как автоматическое принятие решений) и для получения обоснованных выводов (известному как автоматическое рассуждение), в конечном итоге достигая автоматизации. Алан Тьюринг уже использовал человеческие характеристики для метафорического описания машин, такие как "память", "поиск" и "стимул". В отличие от этого, эвристика — это подход к решению проблем, который может быть не полностью определен или не гарантировать правильных или оптимальных результатов, особенно в областях, где не существует четко определенного правильного или оптимального решения. Например, системы рекомендаций в социальных сетях полагаются на эвристики, и хотя в современных СМИ их часто называют "алгоритмами", они не могут обеспечить корректные результаты из-за специфики решаемой задачи. Как эффективный метод, алгоритм может быть выражен в конечном объеме пространства и времени и на формальном языке, четко определяющем функцию. Начиная с начального состояния и входных данных (возможно, пустых), инструкции описывают вычисление, которое при выполнении проходит через конечное число четко определенных последовательных состояний, в конечном итоге выдавая "выход" и завершаясь в конечном состоянии. Переход от одного состояния к другому не обязательно является детерминированным; некоторые алгоритмы, известные как рандомизированные алгоритмы, включают случайные входные данные.

Этимология

Около 825 года н.э. персидский ученый и полимат Мухаммад ибн Муса аль-Хваризми написал "Китаб аль-хисаб аль-хинди" ("Книга индийских вычислений") и "Китаб аль-жам' ва'ль тафрик аль-хисаб аль-хинди" ("Сложение и вычитание в индийской арифметике"). Оба этих текста на оригинальном арабском языке в настоящее время утеряны. Однако его другая книга по алгебре сохранилась. Она охватывает все компьютерные программы (включая те, которые не выполняют числовые вычисления), и, например, любую предписанную бюрократическую процедуру или рецепт из кулинарной книги. В общем смысле, программа является алгоритмом только в том случае, если она в конечном итоге завершается, хотя бесконечные циклы иногда могут быть полезны. Алгоритм можно определить как набор инструкций для определения результата, представленных явно в форме, которую может выполнить либо вычислительная машина, либо человек, способный осуществлять только определенные элементарные операции с символами. Понятие алгоритма также используется для определения понятия разрешимости – ключевого для объяснения того, как возникают формальные системы, исходя из небольшого набора аксиом и правил. В логике время, необходимое для выполнения алгоритма, не поддается измерению, поскольку, по-видимому, не связано с общепринятыми физическими величинами. От этой неопределенности, характерной для текущих исследований, проистекает отсутствие определения алгоритма, которое было бы применимо как к конкретным (в определенном смысле), так и к абстрактным областям его использования. Большинство алгоритмов предназначены для реализации в виде компьютерных программ. Однако алгоритмы могут быть реализованы и другими способами, например, в биологической нейронной сети (например, человеческий мозг, выполняющий арифметические операции, или насекомое, ищущее пищу), в электрической схеме или в механическом устройстве.

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

С древности засвидетельствованы пошаговые процедуры решения математических задач. Это включает в себя вавилонскую математику (около 2500 г. до н.э.), Оракул Ифы (около 500 г. до н.э.), греческую математику (около 240 г. до н.э., например, решето Эратосфена и алгоритм Евклида) и арабскую математику (IX век, например, криптографические алгоритмы для взлома шифров на основе частотного анализа). Первый криптографический алгоритм для расшифровки зашифрованных сообщений был разработан Аль-Кинди, арабским математиком IX века, в трактате «Рукопись о методах расшифровки криптографических сообщений». Он дал первое описание криптоанализа с использованием частотного анализа, самый ранний алгоритм взлома шифров. Во времена династии Хаммурапи, примерно в 1800–1600 гг. до н.э., на вавилонских глиняных табличках описывались алгоритмы для вычисления формул. Алгоритмы также использовались в вавилонской астрономии. Вавилонские глиняные таблички описывают и применяют алгоритмические процедуры для вычисления времени и места важных астрономических событий. Алгоритмы для арифметики также встречаются в древнеегипетской математике, восходящей к папирусу Ринда, датированному примерно 1550 г. до н.э., который можно рассматривать как механизм, отсчитывающий время, подобно механическим часам. «Точная автоматическая машина» сразу привела к созданию «механических автоматов», начиная с XIII века, и, наконец, к «вычислительным машинам» — дифференциальной и аналитической машинам Чарльза Бэббиджа и Ады Лавлейс, в середине XIX века. Лавлейс приписывают создание первого алгоритма, предназначенного для обработки на компьютере — аналитической машине Бэббиджа, первом устройстве, которое считается полноценным компьютером Тьюринга, а не просто вычислителем, — и поэтому её иногда называют «первым программистом в истории», хотя полная реализация второго устройства Бэббиджа была осуществлена лишь десятилетия спустя после её смерти.

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

Белл и Ньюэлл (1971) отмечают, что ткацкий станок Жаккарда (1801), предшественник карт Холлерита (перфокарт, 1887), и "технологии телефонной коммутации" стали истоками, от которых произошли первые компьютеры. К середине XIX века телеграф, предшественник телефона, широко использовался по всему миру, а его дискретное и различимое кодирование букв в виде "точек и тире" стало привычным звуком. К концу XIX века в ходу была биржевая лента (ок. 1870-х годов), а также карты Холлерита, применённые при переписи населения США в 1890 году. Затем появился телеграфный аппарат (ок. 1910 года) с использованием перфорированной бумаги и кода Бодо. Электромеханические реле (изобретённые в 1835 году) лежали в основе работы Джорджа Стибица (1937), изобретателя цифрового сумматора. Работая в Bell Laboratories, он заметил "обременительное" использование механических калькуляторов с шестерёнками. "Однажды вечером в 1937 году он вернулся домой, чтобы испытать свою идею. После завершения экспериментов Стибиц сконструировал двоичное устройство для сложения". Математик Мартин Дэвис подчеркнул особую важность электромеханического реле.

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

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

Представительства

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