Beste Antwort
Darauf gibt es keine Antwort.
Lassen Sie uns die Antwort auf diese Problemstellung finden:
Q. Wie finde ich, dass ein Algorithmus eine bessere Leistung erbringt?
A. Häufigste Methoden zum Vergleichen von Algorithmen:
1) Zeitkomplexität
2) Raumkomplexität
3) Qualität der Lösung (möglicherweise nicht) anwendbar sein, wenn es vorschlägt, ein Problem genau zu lösen). Dies kann ein großer Faktor sein, wenn es sich um Approximationsalgorithmen handelt.
4) Einfache Implementierung / Anpassung des Algorithmus. Einige Algorithmen können viel Aufwand für die korrekte Implementierung haben. Manchmal gibt es geeignetere Algorithmen Zum Beispiel finden die meisten Bellman-Ford beim parallelen Rechnen aufgrund der Funktionsweise von Bellman-Ford nützlicher als den Dijkstra-Algorithmus.
Zeit und Komplexität sind jedoch nicht * immer * die gewünschte Funktion zum Maximieren; Ich werde zwei Beispiele nennen.
Eines ist „numerische Stabilität“ , ein Merkmal von Algorithmen sowohl in der linearen Algebra als auch in Differentialgleichungen. Wir werden sowohl mehr algorithmische Zeit als auch mehr algorithmische Komplexität für Algorithmen aufwenden, die numerisch stabiler sind. In der linearen Algebra wird Instabilität im Allgemeinen verursacht, wenn ein Algorithmus auf Zahlen trifft, die zu nahe an Null oder unendlich oder an beiden liegen, da die endliche Darstellung der Zahlenauflösung verloren gehen kann. Im Allgemeinen führt dies dazu, dass sehr geringfügig unterschiedliche Zahlen, nur wenige Epsilon voneinander verschieden (wobei Epsilon die kleinste Zahl ist, die zu einer auf einer Maschine hinzugefügt werden kann und ein Ergebnis ergibt! = 1), große Unterschiede in erzeugen die Antwort. So verbringen wir zum Beispiel viel Zeit- und Raumkomplexität, indem wir die LU-Faktorisierung „schwenken“, um einen stabilen Algorithmus zu erhalten. ohne schwenkbar ist LU nicht stabil. Ebenso haben wir Algorithmen, die nichts anderes als „Bedingungs“ -Matrizen ausführen, um Instabilität zu vermeiden.
Ein zweites Beispiel ist „Robustheit“ in seinen technischen statistischen Sinn. Robustheit bedeutet ein Maß oder einen Algorithmus, der * nicht * für Ausreißer empfindlich ist. Wenn ich zum Beispiel eine Linie der kleinsten Quadrate an eine Reihe von Punkten anpasse, kann die Linie durch einen einzelnen extrem großen Wert stark verzerrt werden. Selbst wenn ich 99 Zahlenpaare habe, die eine perfekte 45-Grad-Linie bilden, wird die angepasste Linie stark sein, wenn ich ein einzelnes Ausreißerpaar hinzufüge, für das der Y-Wert hundertmal so hoch ist, wie es „sein sollte“, auf dieselbe Linie zu fallen schief von der 45-Grad-Linie. Der Algorithmus „gibt“ die perfekte Anpassung für 99 Punkte auf, um den einen Ausreißerpunkt besser darzustellen. Das ist * nicht * robust.
Ein robuster Ansatz für kleinste Quadrate besteht darin, anstatt die Linie zu finden, die die Summe der durch die Verwendung dieser Linie erzeugten quadratischen Fehler minimiert, die Linie zu finden, die den * Median * von minimiert die quadratischen Fehler, die durch die Verwendung dieser Linie erzeugt wurden. In diesem Beispiel ist diese Linie die 45-Grad-Linie, und der Median der quadratischen Fehler ist Null, und der Ausreißerpunkt (und tatsächlich bis zu 98 weitere verrückte Ausreißer) würde vollständig ignoriert. Die 45-Grad-Linie würde gefunden werden.
Ähnliche robuste Algorithmen existieren zum Anpassen statistischer Kurven, zum Finden von Formen usw. Sie sind jedoch zeitaufwändig, manchmal sehr kostspielig. Die Zeitkosten sind es jedoch wert, da robuste Statistiken effektiv gegen „Rauschen“ in Signalen immun sind, wo dies bei Ansätzen mit kleinsten quadratischen Fehlern nicht der Fall ist. Die reale Welt ist voll von Rauschen und Ausreißern, von denen einige durch menschliche oder maschinelle Fehler verursacht werden, insbesondere bei pixeligen Bildern oder gesampeltem Ton. Unter solchen Umständen kann ein zeitaufwändigerer robuster Algorithmus Signale in einer verrauschten Umgebung finden, in der schnellere Algorithmen Antworten erzeugen, die durch Rauschen so verfälscht sind, dass sie nutzlos oder sogar gefährlich sind, wenn sie akzeptiert werden.
In einigen Fällen Zeit und Raumkomplexität sind bei weitem nicht so wichtig wie das Finden einer Antwort, die das tatsächliche Signal trotz Rauschen und Verschlechterung des Signals am wahrscheinlichsten modelliert.
Antwort
Algorithmen, die aus der Mathematik stammen, sind „Rezepte“. zur Durchführung funktionsbasierter Berechnungen, die mechanisch verfolgt werden können. In der funktionsbasierten mathematischen Weltanschauung müssen alle Eingaben zu Beginn der Berechnung angegeben werden, die in geschlossener Box abläuft. Der Begriff eines Algorithmus ist von Natur aus informell, da eine algorithmische Beschreibung nicht auf eine einzelne Sprache oder einen Formalismus beschränkt ist.
Das vielleicht älteste Beispiel ist der Euklid-Algorithmus zum Auffinden gemeinsamer Teiler. Algorithmen erfassen, was es bedeutet, dass eine Berechnung „effektiv“ ist. Wie mathematische Formeln sagen uns Algorithmen, wie man einen Wert berechnet; Im Gegensatz zu ihnen können Algorithmen das beinhalten, was wir jetzt Schleifen oder Verzweigungen nennen.
Rolle des Algorithmus: Bei einem endlichen Eingabewert x beschreibt ein Algorithmus die Schritte, um ihn effektiv in einen Ausgabewert y umzuwandeln, wobei y ist f (x) für eine rekursive Funktion f.
Algorithmen wurden in den 1950er Jahren von den frühen Informatikern übernommen, die die Verbindung zwischen Algorithmen und Turing-Maschinen (TMs, ein formales Berechnungsmodell aus dem Jahr 1936) herstellten und deren Ausdruckskraft gleichsetzten.
Knuths berühmtes und einflussreiches Lehrbuch „The Art of Computer Programming, Vol. 1“ in den späten 1960er Jahren hat die Zentralität von Algorithmen in der Informatik populär gemacht. In seiner Definition von Algorithmen stimmte Knuth mit den mathematischen funktionsbasierten Grundlagen der Berechnungstheorie überein. „Es gibt viele andere im Wesentlichen gleichwertige Möglichkeiten, das Konzept einer effektiven Berechnungsmethode zu formulieren (z. B. unter Verwendung von TMs).“
Knuth hat ausdrücklich angegeben, dass Algorithmen geschlossen sind. Sobald die Berechnung begonnen hat, wird keine neue Eingabe akzeptiert: „Ein Algorithmus hat null oder mehr Eingaben, d. h. Größen, die ihm anfänglich gegeben werden, bevor der Algorithmus beginnt.“ Er unterschied Algorithmen von willkürlichen Berechnungen, die E / A beinhalten können. Ein Beispiel für ein Problem, das nicht algorithmisch ist, ist die folgende Anweisung aus einem Rezept: „Leicht werfen, bis die Mischung bröckelig ist.“ Dieses Problem ist nicht algorithmisch, da ein Computer nicht wissen kann, wie lange er mischen muss. Dies kann von externen, sich dynamisch ändernden Bedingungen wie der Luftfeuchtigkeit abhängen, die nicht mit Sicherheit im Voraus vorhergesagt werden können.
Obwohl keine Einigung über den genauen Begriff der Algorithmen besteht, bleibt Knuths Diskussion der Algorithmen endgültig.
Die erste Programmiersprache auf hoher Ebene, die ausdrücklich zur Spezifizierung von Algorithmen entwickelt wurde, war ALGOL (ALGOrithmic Language). Es wurde Ende der 50er Jahre eingeführt und in den 1960er Jahren weiterentwickelt und diente als Standard für die Veröffentlichung von Algorithmen. Getreu der funktionsbasierten Konzeptualisierung von Algorithmen stellte ALGOL keine Konstrukte für die Eingabe und Ausgabe bereit, da diese Operationen außerhalb des Bereichs der Algorithmen liegen. (Es überrascht nicht, dass diese Abwesenheit die Einführung von ALGOL durch die Industrie für kommerzielle Anwendungen behinderte.)
In den 1960er Jahren gab es eine Zunahme von Programmen für Bachelor-Informatik (CS). Nach Angaben der Association for Computing Machinery (ACM) stieg die Anzahl der CS-Programme in den USA von 11 im Jahr 1964 auf 92 im Jahr 1968. Dieser Anstieg ging mit intensiven Aktivitäten zur Feststellung der Legitimität dieser neuen Disziplin in den Augen der Akademiker einher Gemeinschaft. ACM spielte bei dieser Aktivität eine zentrale Rolle. 1965 sprach sie die Rechtfertigung und Beschreibung von CS als Disziplin aus, die als Grundlage für ihre Empfehlungen von 1968 für CS-Programme für Studenten diente.
In der Beschreibung von CS durch ACM wurde eine wirksame Transformation von Informationen als zentrales Anliegen identifiziert: „ Die Informatik befasst sich mit Informationen im gleichen Sinne wie die Physik mit Energie … Der Informatiker ist daran interessiert, die pragmatischen Mittel zu entdecken, mit denen Informationen transformiert werden können. “ Diese Beschreibung stellt Algorithmen in den Mittelpunkt der Informatik, da sie die „Rezepte“ für die Durchführung dieser effektiven Transformationen von Eingaben zu Ausgaben sind. Tatsächlich hat ACM diesen Fokus auf Algorithmen im nächsten Satz ihres Berichts explizit gemacht:
„Dieses Interesse führt zu einer Untersuchung effektiver Arten der Darstellung von Informationen, effektiver Algorithmen zur Transformation von Informationen und effektiver Sprachen, mit denen ausgedrückt werden kann Algorithmen … und effektive Wege, um dies zu angemessenen Kosten zu erreichen. “
Ein zentrales algorithmisches Anliegen, analog zum Anliegen der Energie in der Physik, trug dazu bei, CS als legitime akademische Disziplin auf Augenhöhe zu etablieren Physik. Algorithmen sind bis heute ein zentraler Bestandteil der Informatik.
Die Koexistenz der informellen (algorithmischen) und formalen (TM-basierten) Ansätze zur Definition lösbarer Probleme besteht bis heute fort und ist in zu finden alle modernen Lehrbücher über Algorithmen oder Berechenbarkeit. Dies hat sich für Informatiker als sehr praktisch erwiesen, da wir die algorithmische Berechnung informell unter Verwendung von „Pseudocode“ beschreiben können, mit dem Wissen, dass eine äquivalente Turing-Maschine konstruiert werden kann.
– Ein Problem ist lösbar, wenn es möglich ist durch einen Algorithmus angegeben. – Ein Problem ist lösbar, wenn es eine Turing-Maschine dafür gibt.
Die Entscheidung von Theoretikern und Pädagogen aus den 1960er Jahren, Algorithmen in den Mittelpunkt der CS zu stellen, spiegelte sich deutlich in Lehrbüchern für Studienanfänger wider. Es gab jedoch keine explizite Standarddefinition eines Algorithmus und verschiedene Lehrbücher entschieden sich dafür, diesen Begriff unterschiedlich zu definieren. Während einige Lehrbücher wie das von Knuth darauf bedacht waren, Algorithmen explizit auf diejenigen zu beschränken, die Funktionen berechnen und daher Turing-Maschinen entsprechen, ließen die meisten Theoriebücher diese Einschränkung implizit, aber nicht angegeben.
Ein frühes Beispiel ist a Lehrbuch von Hopcroft und Ullman aus dem Jahr 1969, dessen spätere Ausgaben bis heute verwendet werden: „Ein Verfahren ist eine endliche Folge von Anweisungen, die mechanisch ausgeführt werden können, wie z. B. ein Computerprogramm …Eine Prozedur, die immer beendet wird, wird als Algorithmus bezeichnet. “
Diese Beschreibung eines Algorithmus schließt nichtfunktionale Berechnungen wie das Zubereiten von Speisen nicht explizit aus. Ihre Beispiele für verschiedene Probleme machen jedoch deutlich, dass sie nur funktionsbasierte Berechnungen in Betracht zogen. Tatsächlich verwendeten sie ALGOL für ihre Beispiele, die nicht einmal Konstrukte für Eingabe und Ausgabe boten.
Seit Ende der 60er Jahre waren die in der Praxis verwendeten und in CS-Programmen gelehrten Programmiersprachen auf hoher Ebene nicht mehr vorhanden gebunden an die algorithmischen Beschränkungen des frühen ALGOL. Sie können Programme schreiben, die während der gesamten Berechnung kontinuierlich mit ihrer Umgebung interagieren, z. B. Betriebssysteme, grafische Benutzeroberflächen oder automatische Fahrzeuge und andere Roboter.
Als Reaktion darauf können moderne Programmierlehrbücher wie Rice und Rice (1969) erweiterte den Begriff der Algorithmen explizit um nichtfunktionale Probleme. Dieser Ansatz, der die Zentralität von Algorithmen widerspiegelt, ohne sie auf die Berechnung von Funktionen zu beschränken, wurde typisch für nicht-theoretische Lehrbücher. Das Thema dieser Lehrbücher ist eher die Programmiermethodik als die Berechnungstheorie, und die mathematischen Prinzipien, die unseren Berechnungsmodellen zugrunde liegen, wurden aus praktischen Gründen beiseite geworfen.
Oberflächlich betrachtet wurde die Definition eines Algorithmus in Rice and Rice und anderen solchen Lehrbüchern unterscheidet sich nicht von Hopcroft und Ullman: „Ein Algorithmus ist ein Rezept, eine Reihe von Anweisungen oder die Spezifikationen eines Prozesses, um etwas zu tun. Dass etwas normalerweise ein Problem löst. “ Ihre Beispiele für berechenbare Probleme sind jedoch nicht mehr funktionsbasiert und lassen nur die Art von Berechnung zu, die Knuth abgelehnt hatte. Zwei solche Beispiele, die angeblich durch einen Algorithmus gelöst werden können, sind die Herstellung von Kartoffelwodka und das Füllen eines Grabens mit Sand; Knuth hätte beide abgelehnt.
Diese Lehrbücher erheben keinen Anspruch auf TM-Äquivalenz für ihre „Algorithmen“. Den Studenten wurde jedoch nicht bewusst gemacht, dass sich dieser Begriff von Algorithmen von dem von Knuth unterscheidet und dass die als berechenbar angesehenen Probleme dadurch erweitert wurden. Durch die Kombination einer breiteren, praktischeren Konzeptualisierung von Algorithmen (und damit von berechenbaren Problemen) mit Theorien, die behaupten, dass sehr berechenbare Probleme von TMs berechnet werden können, hinterließ der algorithmisch fokussierte CS-Lehrplan den falschen Eindruck, dass diese breitere Reihe von Problemen auftreten könnte auch durch TMs gelöst werden.
Während die praktischen Informatiker längst dem Beispiel von Rice and Rice gefolgt sind und das Konzept der Algorithmen über die Berechnung von Funktionen hinaus erweitert haben, hat die theoretische Informatik die mathematische Weltanschauung beibehalten, die Rahmen bildet Berechnung als funktionsbasiert und begrenzt unsere Vorstellung von einem Rechenproblem entsprechend. Dies gilt zumindest für Studenten. Das Ergebnis ist eine Dichotomie, bei der die Informatiker Algorithmen als Synonym für den allgemeinen Begriff der Berechnung („was Computer tun“) betrachten und gleichzeitig Turing-Maschinen entsprechen.
Ich dachte Ich musste diese lange Antwort schreiben, um die Leute auf diese Zweiteilung aufmerksam zu machen. Wie ich zu Beginn sagte, ist der Begriff eines Algorithmus informell. Wir können es als äquivalent zur Berechnung von Funktionen (oder zu Turing-Maschinen) oder als alles betrachten, für das Sie ein Programm schreiben können, einschließlich interaktiver Echtzeitprogramme wie Betriebssysteme oder automatische Autos. Die beiden Definitionen sind jedoch trotz der allgemeinen gegenteiligen Verwirrung nicht gleichwertig.