Beispiele für Algorithmen

Dieser Artikel Algorithmusbeispiele ergänzt die Charakterisierung von Algorithmen und Algorithmen. Ein Beispiel: Algorithmusspezifikation der Addition m + n. Wahl des Maschinenmodells: Es gibt kein “bestes” oder “bevorzugtes” Modell. Die Turing-Maschine ist, obwohl sie als Standard betrachtet wird, bekanntermaßen unhandlich. Und für verschiedene Probleme scheinen unterschiedliche Modelle erforderlich, um sie zu untersuchen. Viele Forscher haben diese Probleme zum Beispiel beobachtet: Über allem, worauf man bestehen kann, ist, dass der Algorithmus-Schreiber genau (i) das zu verwendende Maschinenmodell und (ii) seinen Befehlssatz spezifiziert.Zerstäubung des Befehlssatzes:Das Turing-Maschinenmodell ist primitiv, aber nicht so primitiv wie es sein kann. Wie in den obigen Zitaten erwähnt, gibt dies Anlass zur Sorge, wenn Komplexität und Äquivalenz von Algorithmen untersucht werden. Obwohl die unten angeführten Beobachtungen das Random-Access-Maschinenmodell betreffen (ein Turing-Maschinenäquivalent), bleibt das Problem für jedes Turing-Äquivalentmodell bestehen:Beispiel # 1: Die allgemeinste (und originellste) Turing-Maschine – Einzelband mit linkem Ende, Multi-Symbolen, 5-Tupel-Befehlsformat – kann in die Turing-Maschine von Boolos-Burgess-Jeffrey ( 2002) – Single-Tape ohne Ende, zwei “Symbole” {B, | } (wobei B “leeres Quadrat” und “markiertes Quadrat” symbolisiert) und ein 4-Tupel-Befehlsformat. Dieses Modell kann wiederum zu einer Post-Turing-Maschine zerstäubt werden: Einband ohne Enden, zwei Symbole {B, | } und einen Befehlssatz für 0- und 1-Parameter (z. B. {Left, Right, Mark, Erase, Jump-if-markiert zu Befehl xxx, Jump-if-blank zu Befehl xxx, Halt}). Beispiel # 2: Der RASP kann auf einen RAM-Speicher reduziert werden, indem seine Anweisungen vom Band und (möglicherweise mit Übersetzung) in seine Zustandsmaschine “Tabelle” von Anweisungen verschoben werden, wobei der RAM seine indirekte Anweisung entfernt und auf einen Wert reduziert 2- und 3-Operand „Abacus“ -Registrierungsmaschine1}

Leave a Comment