Was ist der Unterschied zwischen einem Algorithmus, einer Sprache und einem Problem?

40

Es scheint, dass die Leute auf dieser Seite oft andere wegen verwirrender "Algorithmen" und "Probleme" korrigieren. Was ist der Unterschied zwischen diesen? Woher weiß ich, wann ich Algorithmen und Probleme in Betracht ziehen sollte? Und in welcher Beziehung stehen diese zum Sprachbegriff in der formalen Sprachtheorie?

jmite
quelle
Ein Algorithmus ist ein Weg, um ein Problem zu lösen.
Reinierpost

Antworten:

53

Der Einfachheit halber werde ich zunächst nur auf "Entscheidungs" -Probleme eingehen, bei denen eine Ja / Nein-Antwort vorliegt. Funktionsprobleme funktionieren in etwa auf die gleiche Weise, außer dass jedem Eingangswort anstelle von Ja / Nein ein bestimmtes Ausgangswort zugeordnet ist.

Sprache : Eine Sprache ist einfach eine Reihe von Zeichenfolgen. Wenn Sie ein Alphabet haben, wie , dann Σ * ist die Menge aller Wörter nur die Symbole in enthalten Σ . Zum Beispiel ist { 0 , 1 } die Menge aller Binärsequenzen beliebiger Länge. Ein Alphabet muss jedoch nicht binär sein. Es kann unär, ternär usw. sein.ΣΣΣ{0,1}

Eine Sprache über einem Alphabet ist eine beliebige Teilmenge von Σ * .ΣΣ

Problem : Ein Problem ist eine Frage zu einer Eingabe, die wir gerne beantwortet hätten. Insbesondere ist ein Entscheidungsproblem eine Frage, die sich stellt: "Erfüllt unsere gegebene Eingabe die Eigenschaft ?X

X

L={wwyXyX}

Das Bestimmen, ob die Antwort für eine Eingabe zu einem Entscheidungsproblem "Ja" ist, entspricht dem Bestimmen, ob eine Codierung dieser Eingabe über ein Alphabet in der entsprechenden Sprache vorliegt.

Algorithmus : Ein Algorithmus ist eine schrittweise Methode zur Lösung eines Problems. Beachten Sie, dass ein Algorithmus auf viele Arten und in vielen Sprachen ausgedrückt werden kann und dass es viele verschiedene Algorithmen gibt, die ein bestimmtes Problem lösen.

M

L(M)={wMw}

RRE

Die Beziehung zwischen Sprachen und Turing-Maschinen ist wie folgt

  1. Jede Turingmaschine akzeptiert genau eine Sprache

  2. Es kann mehr als eine Turing-Maschine geben, die eine bestimmte Sprache akzeptiert

  3. Möglicherweise gibt es keine Turing-Maschine, die eine bestimmte Sprache akzeptiert.

Wir können ungefähr dasselbe über Algorithmen und Probleme sagen: Jeder Algorithmus löst ein einzelnes Problem, aber es kann 0 oder viele Algorithmen geben, die ein bestimmtes Problem lösen.

Zeitkomplexität : Eine der häufigsten Ursachen für Verwechslungen zwischen Algorithmen und Problemen sind Komplexitätsklassen. Die korrekte Zuordnung lässt sich wie folgt zusammenfassen:

  • Ein Algorithmus hat eine zeitliche Komplexität
  • Ein Problem gehört zu einer Komplexitätsklasse

f(n)f(n)n

Probleme haben keine Laufzeit, da ein Problem nicht an einen bestimmten Algorithmus gebunden ist, der tatsächlich ausgeführt wird. Stattdessen sagen wir, dass ein Problem zu einer Komplexitätsklasse gehört, wenn es einen Algorithmus gibt, der dieses Problem mit einer bestimmten zeitlichen Komplexität löst.

P,NP,PSPACE,EXPTIMEPXXPXXP

jmite
quelle
1
Sie können diese Antwort nach Belieben bearbeiten.
8.
Ich denke, es wäre gut zu erwähnen, dass es andere Arten von Rechenproblemen gibt (z. B. Suchprobleme).
Kaveh
1
Sagt wer? Diese Art des Denkens ist Teil dessen, warum die Leute vor der Absicht der Turing-Maschine so viele Probleme mit der Formalisierung und dem Algorithmus hatten. Die Church-Turing-These besagt, dass ein Algorithmus eine Turing-Maschine ist und umgekehrt, und nicht alle Turing-Maschinen anhalten.
Mittwoch,
4
Alter, das ist die beste Antwort, die ich je gesehen habe. Sie haben gerade die gesamte Informatik auf einer Seite zusammengefasst.
CaptainCodeman
1
@ gnasher729 Es gibt einen Satz, der besagt, dass er in Bezug auf die Überprüfung definiert werden kann, aber seine tatsächliche Definition ist in Bezug auf die Zeitkomplexität für nicht deterministische Maschinen, daher der Name NP: nicht deterministisches Polynom
jmite