В чем разница между алгоритмом, языком и проблемой?

40

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

jmite
источник
Алгоритм - это способ решения проблемы.
reinierpost

Ответы:

53

Для простоты я начну только с рассмотрения проблем «решения», на которые есть ответ да / нет. Функциональные проблемы работают примерно так же, за исключением того, что вместо да / нет, есть каждое выходное слово, связанное с каждым входным словом.

Язык : язык - это просто набор строк. Если у вас есть алфавит, такой как , то Σ - это множество всех слов, содержащих только символы в Σ . Например, { 0 , 1 } - это множество всех двоичных последовательностей любой длины. Однако алфавит не обязательно должен быть двоичным. Это может быть одинарный, троичный и т. Д.ΣΣ*Σ{0,1}*

Язык над алфавитом - это любое подмножество Σ .ΣΣ*

Проблема : проблема - это некоторый вопрос о том, какой вклад мы бы хотели получить. В частности, проблема решения - это вопрос, который задает вопрос: «Соответствует ли наш заданный вход свойству ?Икс

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

- кодировка входа y для задачи X , а ответом на вход y для задачи X является "Да" }Lзнак равно{вес|весYИксYИкс}

Определение, является ли ответ для ввода для решения проблемы «да», эквивалентно определению, является ли кодирование этого ввода по алфавиту на соответствующем языке.

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

Машина Тьюринга : Машина Тьюринга является формальным аналогом алгоритма. Машина Тьюринга над данным алфавитом для каждого слова будет или не остановится в состоянии принятия. Таким образом, для каждой машины Тьюринга существует соответствующий язык:M

останавливается в состоянии приема на входе w } .L(M)знак равно{вес|Mвес}

(Существует небольшая разница между машинами Тьюринга, которые останавливаются на всех входах и останавливаются на входах yes, что определяет разницу между классами сложности и R E. )ррЕ

Отношения между языками и машинами Тьюринга таковы

  1. Каждая машина Тьюринга принимает только один язык

  2. Может быть несколько машин Тьюринга, которые принимают данный язык

  3. Может не быть машины Тьюринга, которая принимает данный язык.

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

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

  • Алгоритм имеет временную сложность
  • Проблема относится к классу сложности

Алгоритм может иметь определенную временную сложность. Мы говорим, что алгоритм имеет наихудшую ограниченную сверху сложность если алгоритм останавливается не более чем за f ( n ) шагов при любом входе размера nе(N)е(N)N .

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

и т. Д. - все это классы сложности. Это означает, что они содержат проблемы, а не алгоритмы. Алгоритм не может быть в P , но если есть полиномиальный алгоритм решения данной задачи X , то X в P . Там также может быть куча алгоритмов экспоненциального времени приема X , но поскольку существует единственный полиномиальный алгоритм принимающего X , то в P .п,Nп,пSпAСЕ,ЕИкспTяMЕпИксИкспИксИксп

jmite
источник
1
Пожалуйста, не стесняйтесь редактировать этот ответ по своему усмотрению.
Jmite
Я думаю, что было бы хорошо упомянуть, что существуют другие виды вычислительных проблем (например, проблемы поиска).
Каве
1
Говорит кто? Такое мышление является частью того, почему у людей было так много проблем с формализацией и алгоритмом перед намерением машины Тьюринга. Тезис Черча-Тьюринга говорит, что алгоритм - это машина Тьюринга и наоборот, и не все машины Тьюринга останавливаются.
Jmite
4
Чувак, это самый лучший ответ, который я когда-либо видел. Вы только что суммировали всю информатику на 1 странице.
CaptainCodeman
1
@ gnasher729 есть теорема, которая говорит, что она может быть определена с точки зрения проверки, но ее фактическое определение с точки зрения сложности времени для недетерминированных машин, таким образом, название NP: недетерминированный полином
jmite