Что именно представляет собой алгоритм?

Я знаю, что это может звучать немного нестандартно, на самом деле я всегда думал внутри коробки, но в последнее время я думал, возможно, потому, что информатика предоставляет высокую степень свободы, о способах разработки других программ, кроме те, которые преподавали в университете.

Рассмотрим факториальную функцию. Обычно мы определяем эту функцию как

 int fact(int n) 
 { 
 int r = 1; 
 for(int i=2;i<=n;i++) 
 r = r*i; 
 return r; 
 } 

Я бы назвал это алгоритмом и не сомневаюсь, что это правильный способ сделать это. Затем я подумал: «Могу ли я сделать это в постоянное время?», Что привело к следующей идее: что если бы у меня был массив целых чисел, где массив [n] содержит факториал n? Как только этот массив заполнен, я могу просто определить факт как:

 int fact(int n) 
 { 
 return array[n]; 
 } 

Тем не менее, я не могу назвать этот алгоритм, хотя он обеспечивает правильный результат и работает в постоянном времени O (1). Можно ли это назвать алгоритмом? Иначе почему бы и нет? Я мог бы утверждать, что заполнение массива потребовало бы, чтобы алгоритм работал в какое-то время, даже если бы он был в нашем мозгу, чтобы мы могли заполнить массив, но может ли это быть критерием? Как эти аспекты обрабатываются формально?

Обратите внимание, что эту концепцию можно распространить на любую функцию, работающую над целыми числами, независимо от количества аргументов, мне просто нужно использовать матрицу, если функция имеет 2 аргумента, или 3, если функция имеет 3 аргумента и так далее. Кроме того, не используются ли эти решения просто из-за потребления памяти?

Кроме того, эти функции не могут также охватывать любую программу с выводом, поскольку я мог бы найти способ индексировать каждый возможный вывод, который может предоставить программа.

В качестве другого примера рассмотрим обычное использование массива: я выделяю массив изначально размером N, затем добавляю элементы в массив, сохраняя значение по индексу n и увеличивая n на одну единицу. Затем, если я хочу найти элемент, я не могу помочь, но выполнить линейный поиск по массиву. Если бы вместо этого я создал массив размером, например, Integer.MAXVALUE, для хранения целых чисел, инициализированных нулями, я мог бы сохранить целое число, поместив 1 в его индекс. Тогда я мог бы искать его существование в массиве за время O (1). Что если бы я хотел иметь возможность разместить несколько единиц одного и того же номера? Нет проблем, я бы просто увеличил значение, хранящееся в целочисленном индексе.

Сортировка будет немного сложнее, но, тем не менее, поиск и сложение могут быть выполнены за O (1) раз.

Неформальное определение алгоритма в популярном учебнике выглядит примерно так:

Алгоритм - это (1) хорошо определенная вычислительная процедура (2), которая требует некоторого ввода, а (3) производит некоторый вывод (4) для хорошо определенной вычислительной задачи.

В первом случае вы написали алгоритм, в котором: Проблема состоит в том, чтобы найти факториал (часть 4 определения), заданный в качестве входного значения int n (часть 2 определения), код описывает вычисление, которое должно быть выполнено (часть 1 определения) ), результат является факториалом (часть 3 определения).

Во втором случае: проблема состоит в том, чтобы найти элемент массива в позиции n (часть 4 определения), заданной в качестве входного значения n (часть 3 определения), код описывает вычисление, которое должно быть выполнено (часть 2 определения), output - это элемент в позиции n (часть 1 определения).

Вы хранили там факториалы, так что это дает вам факториалы. Если бы вы хранили там квадраты или кубы, вы бы получили квадраты или кубы, поэтому нельзя сказать, что второй фрагмент сам по себе является алгоритмом для вычисления факториалов.

И если вы говорите, что поиск массива вместе с массивом, имеющим f (n) в позиции n, является алгоритмом для вычисления f (n), то вы продвинулись настолько глубоко, что больше нет вычислений ниже. Четко определенная вычислительная процедура должна быть конечной информацией. Если бесконечный массив факториалов является частью вычислительной процедуры, это не имеет места. Так что это не будет алгоритм для вычисления факториалов.

В широком смысле алгоритм - это последовательность шагов для решения проблемы .

В CS следующие термины обычно понимаются / предполагаются при использовании термина алгоритм:

• Алгоритм имеет конечное описание и четко определенную процедуру для выполнения его шагов для любого случая проблемы. (Подробнее ниже.)
• Экземпляр задачи, заданный в виде конечной строки (последовательность входных символов), и выходные данные алгоритма могут быть закодированы в виде конечной строки.
• Проблема - это совокупность проблемных примеров вместе с возможными «правильными» выходными данными для каждого экземпляра. «Решение» означает получение правильного результата.
• (Обычно) экземпляры задачи могут быть сколь угодно большими (существует бесконечное число возможных примеров, которые должен решать ваш конечный алгоритм).

До основания CS математики сталкивались с теми же проблемами, что и вы, и вводили формальные определения вычислений для решения этих проблем. Таким образом, в настоящее время мы можем формализовать все вышеперечисленные предположения, просто сказав: «алгоритм - это процедура, которая может быть реализована на машине Тьюринга» . Это, вероятно, лучший официальный ответ на ваш вопрос.

Обратите внимание, что тезис Черча-Тьюринга говорит, что мы думаем, что нет «более мощной» формализации алгоритмов, чем машина Тьюринга.

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

Теперь мы могли бы вместо этого рассматривать вычисления следующим образом: для каждого входного размера существует ТМ (или какое-либо другое вычислительное устройство), которое решает проблему. Это совсем другой вопрос. Обратите внимание, что один TM не может хранить факториал каждого отдельного целого числа, поскольку TM имеет конечное описание. Однако мы можем создать TM (или программу на C), которая хранит факториалы всех чисел ниже 1000. Затем мы можем создать программу, которая хранит факториалы всех чисел от 1000 до 10000. И так далее.

Эти неоднородные типы вычислений обычно моделируются в теоретических CS схемами. Вы рассматриваете различную конструкцию схемы для каждого возможного размера входа.

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

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

$n!$$n!$) может быть вычислено в нем гораздо более эффективно, по сравнению с C.

Когда мы беспокоимся о фактическом времени работы на реальном компьютере, мы должны быть еще более осторожными, но, к сожалению, это обычно выходит за рамки теоретической информатики.

$n$$n!$

Какое понятие алгоритма мы должны использовать? Одно предложение, изложенное выше, заключается в использовании программ на Си. Мы можем назвать это понятие C-вычислением. Вычисление по Тьюрингу - это то, что вы получаете, когда используете машины Тьюринга. Оказывается, что функция является C-вычислимой тогда и только тогда, когда она вычислима по Тьюрингу. В этом смысле обе эти модели вычислений эквивалентны. Действительно, многие другие модели эквивалентны, например, все языки программирования общего пользования (с учетом бесконечной памяти и неограниченных переменных).

Мы говорим, что язык программирования P является тьюрингово-полным, функция является P-вычислимой тогда и только тогда, когда она тьюрингово-вычислима. Гипотеза Черча-Тьюринга является неформальным утверждением о том, что все разумные модели вычислений, имеющие конечное описание и занимающие конечное время, являются полными по Тьюрингу. Ваша модель имеет конечное описание, но не занимает конечного времени.

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

Память может быть произвольно большой, как и входные данные, но чтобы быть полезным определением алгоритма, кодовое пространство должно быть конечным. В противном случае вы получите проблему, которую вы только что определили.

$O(\log A)$$A$$O(\log n)$$O(\log n!)$$O(n (\log n)^2)$$s$$n = O(2^s)$$O(2^s~s^2)$$O(1)$

Несколько замечаний, которые могут быть полезны:

Проблемы - это заявления о допустимых входах и соответствующих выходах. Это то, что мы хотим решить. Алгоритмы являются вычислительными процедурами. Мы можем сказать, что алгоритм корректен по отношению к проблеме, если он принимает входные данные, которые допустимы по отношению к проблеме, и выдает выходные данные в соответствии с описанием проблемы.

Оба ваших примера являются алгоритмами, так как они оба являются явно вычислительными процедурами. То ли алгоритмы правильно или нет , зависит от того, как вы определили проблему и как интерпретировать представление алгоритма. Некоторые постановки проблемы:

1. $n$$n!$
2. $n > 0$$n! <$ INT_MAX$n!$

Некоторые интерпретации вашего первого фрагмента кода:

1. Это псевдокод, который похож на C / C ++, за исключением деталей. intна самом деле означает «любое целое число», например.
2. Это следует интерпретировать так, как если бы это была настоящая программа на C / C ++.

Интерпретация 1 верна для постановки задачи 1, если факториал принимает значение 1 для отрицательных чисел (в противном случае мы можем изменить постановку задачи, чтобы ограничить область или алгоритм для учета желаемого поведения). Интерпретация 2 верна для постановки задачи 2 с той же оговоркой.

arrayarray$n$$n > 0$$n! <$ INT_MAX$n!$$n < 0$

$n$$n! \geq 2^{32}$$n! \geq 2^{64}$

$k$$k$$n$$kn$$k+n$

Алгоритм является программа , написанная на Тьюрингу языке , который доказуемо останавливается на всех допустимых входных сигналов. Все стандартные языки программирования являются тьюрингово-полными. Слово происходит от европейского перевода имени al-Khwārizmī, персидского математика, астронома и географа, чьи работы основаны на работах индийского математика 7-го века Брахмагупты, который ввел индийскую систему счисления в западном мире.

Похоже, в основном вопрос заключается в том, являются ли таблицы поиска частями алгоритмов. Абсолютно! В машинах Тьюринга (ТМ) таблицы могут быть закодированы в таблице состояний ТМ. TM может инициализировать ленту на основе конечного объема данных, хранящихся в таблице переходов. Однако «алгоритмы», которые не работают на бесконечных входах, только на конечных входах, являются «тривиально» машинами с конечным числом состояний (FSM) .

В двух словах : алгоритм является конструктивной частью конструктивного доказательства того, что данная проблема имеет решение. Мотивация для этого определения - изоморфизм Карри-Ховарда между программами и доказательством, учитывая, что программа имеет интерес только в том случае, если она решает проблему, но доказуемо так. Это определение допускает дополнительную абстракцию и оставляет некоторые двери открытыми в отношении типа областей, которые могут быть затронуты, например, в отношении свойств конечности.

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

Выявление некоторых проблем

Стандартный способ рассмотрения алгоритма состоит в том, чтобы утверждать, что алгоритм - это произвольная конечно определенная программа для некоторого вычислительного устройства , включая те, которые не имеют ограничений в памяти. Язык также может быть языком машинного компьютера. На самом деле достаточно рассмотреть все программы для полного вычислительного устройства Тьюринга (что подразумевает отсутствие ограничений памяти). Это может не дать вам представление всех алгоритмов, в том смысле, что алгоритмы должны быть выражены в форме, которая в своих деталях зависит от контекста интерпретации, даже теоретического, поскольку все определяется до некоторой кодировки. Но, поскольку он будет вычислять все, что нужно вычислить, он будет каким-то образом включать все алгоритмы, вплоть до кодирования.

$\pi$

$\pi$Возможно, в математическом смысле почти все. Но это потребовало бы большей точности в определениях.

Таким образом, реальный вопрос состоит в том, чтобы знать, каковы значимые алгоритмы. Ответ заключается в том, что значимые алгоритмы - это те, которые решают проблему, шаг за шагом вычисляя «решение», «ответ» этой проблемы. Алгоритм интересен, если он связан с проблемой, которую он решает.

Итак, учитывая формальную проблему, как мы получаем алгоритм, который решает проблему. Явно или неявно, алгоритмы связаны с идеей, что существует решение проблемы, которое может быть доказано правильным. То, насколько точны наши методы доказательства, - это другой вопрос, но мы стараемся, по крайней мере, убедить себя. Если вы ограничиваете себя конструктивной математикой, которая на самом деле является тем, что мы должны делать (и это является очень приемлемым аксиоматическим ограничением для большей части математики), способ доказать существование решения состоит в том, чтобы пройти этапы доказательства, которые фактически демонстрируют конструкт это представляет решение, включая, возможно, другие шаги, которые устанавливают его правильность.

Все программисты думают примерно так: если я так и так поиграюсь с данными, то получу этот виджет, который обладает только правильными свойствами из-за теоремы Сезама, и, запустив это преобразование, сохраняющее foo, получу желаемый ответ . Но доказательства обычно неформальны, и мы не прорабатываем все детали, что объясняет, почему спутник пытался вывести на орбиту Марс (среди прочего). Мы делаем большую часть рассуждений, но на самом деле мы оставляем только конструктивную часть, которая строит решение, и мы описываем его на компьютерном языке как алгоритм, который решает проблему.

Интересные алгоритмы (или программы)

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

Интересный алгоритм - это конструктивная часть конструктивного доказательства того, что данная задача имеет решение . Это означает, что доказательство должно на самом деле демонстрировать решение, а не просто доказывать его существование, например, путем противоречия. Для более подробной информации см. Интуиционистская логика и конструктивизм в математике.

Это, конечно, очень ограничительное определение, которое учитывает только то, что я назвал интересными алгоритмами. Так что игнорирует почти все из них. Но так же поступают все наши учебники по алгоритму. Они пытаются преподавать только некоторые из интересных.

Учитывая все параметры задачи (входные данные), он говорит вам, как получить указанный результат шаг за шагом. Типичным примером является разрешение уравнений ( алгоритм имени на самом деле происходит от имени персидского математика Мухаммада ибн Муса аль-Хваризми , который изучал разрешение некоторых уравнений). Части доказательства используются, чтобы установить, что некоторые значения, вычисленные в алгоритме, действительно имеют некоторые свойства, но эти части не нужно хранить в самом алгоритме.

Разумеется, это должно происходить в формализованной логической структуре, которая устанавливает, с какими данными рассчитываются, какие допускаются элементарные вычислительные шаги и какие используются аксиомы.

Возвращаясь к вашему факториальному примеру, он может быть истолкован как алгоритм, хотя и тривиальный. Нормальная факториальная функция соответствует доказательству того, что с учетом некоторой арифметической структуры и целого числа n существует число, являющееся произведением первых n целых чисел. Это довольно просто, как и факторные вычисления. Это может быть более сложным для других функций.

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

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

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

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

$2^{1000}$

Какие программы интересны

Это обсуждение должно быть более правильно связано с такими результатами, как изоморфизм Карри-Ховарда между программами и доказательство. Если какая-либо программа на самом деле является доказательством чего-либо, любая программа может быть истолкована как интересная программа в смысле определения выше.

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

Это, вероятно, исключает большинство «случайно сгенерированных» программ.

Это также несколько открытое определение того, что является «интересным алгоритмом». Любая программа, которая может показаться интересной, определенно такова, поскольку существует определенная система типов, которая делает ее интересной. Но программа, которая до сих пор не была типизированной, могла стать типизируемой с более продвинутой системой типов и, таким образом, стать интересной. Точнее, это всегда было интересно, но из-за недостатка знаний о правильной системе типов мы не могли этого знать.

Однако известно, что не все программы являются типизируемыми, поскольку известно, что некоторые лямбда-выражения, такие как реализация Y-комбинатора , не могут быть набраны в системе звукового типа .

Это представление относится только к программным формализмам, которые могут быть непосредственно связаны с некоторой аксиоматической системой доказательств. Я не знаю, как его можно распространить на вычислительные формализмы низкого уровня, такие как машина Тьюринга. Однако, поскольку алгоритмика и вычислимость часто являются игрой кодирования проблем и решений (представьте себе арифметику, закодированную в лямбда-исчислении ), можно считать, что любое формально определенное вычисление, которое может быть показано как кодирование алгоритма, также является алгоритмом. Такие кодировки, вероятно, используют только очень небольшую часть того, что может быть выражено в формализме низкого уровня, таком как машины Тьюринга.

Один интерес этого подхода состоит в том, что он дает понятие алгоритма, которое является более абстрактным и независимым от вопросов фактического кодирования, «физической представимости» вычислительной области. Таким образом, можно, например, рассматривать области с бесконечными объектами, пока существует вычислительный способ их использования.

На момент написания статьи не существует хорошего формального определения «алгоритм». Тем не менее, есть умные люди, работающие над этим.

Мы знаем, что каким бы ни был «алгоритм», он находится где-то между «математической функцией» и «компьютерной программой».

Математическая функция - это формальное понятие отображения между входами и выходами. Так, например, «сортировка» - это отображение между последовательностью упорядочиваемых элементов и последовательностью упорядочиваемых элементов одного и того же типа, которое отображает каждую последовательность в ее упорядоченную последовательность. Эта функция может быть реализована с использованием различных алгоритмов (например, сортировка слиянием, сортировка кучи). Каждый алгоритм, в свою очередь, может быть реализован с использованием разных программ (даже с учетом одного и того же языка программирования).

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

Точно так же существует класс эквивалентности между алгоритмами, где два алгоритма эквивалентны, если они вычисляют одну и ту же математическую функцию.

Самое сложное во всем этом - попытаться уловить то, что мы подразумеваем под «по сути тем же».

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

Какое бы отношение эквивалентности мы ни выбрали, это дает нам некоторую структуру. Алгоритмы образуют категорию в силу того, что они являются частной категорией программ. Известно, что некоторые интересные эквивалентные отношения порождают интересные категориальные структуры; например, категория примитивно-рекурсивных алгоритмов является универсальным объектом в категории категорий. Всякий раз, когда вы видите такую ​​интересную структуру, вы знаете, что эта линия исследования, вероятно, будет полезна.

Ваш вопрос и описание не имеют такого отношения. Алгоритм является теоретическим и не относится ни к какому языку программирования. Алгоритм представляет собой набор правил или этапов (процедур) для решения проблемы. Ваша проблема может быть решена многими способами или многими алгоритмами.

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