Algorithmen
Algorithmen
algorithmen, algorithmen kapieren.
 
Benutzerdefinierte Suche
Algorithmen
Algorithmen Kapieren
 
 
 
 
 
Gehen Sie zurück

Smartphone









Befreien die Animation VR / AR
Spielen, um 3D-Bilder und 3D-Modelle zeigen!
Demonstration A-Frame / Mehrspieler
Android app on Google Play
 
vlrPhone / vlrFilter
Sehr geringer verbrauch, strahlung und bitrate softphones projekt / Multifunktion Audio-Filter mit Fernbedienung!



 

Stadt Bilder, Reise Bilder, Safe Bilder

Howto - Wie Mache - Illustriert Antworten

 

Algorithmus
einfachste Algorithmen. Mit der Sprache ist auch eine geeignete Möglichkeit gegeben, Verfahren und Fertigkeiten weiterzugeben – komplexere Algorithmen. Aus

View Wikipedia Artikel

Al-Chwarizmi, der Namensgeber des Algorithmus, auf einer sowjetischen Briefmarke anlässlich seines 1200-jährigen Geburtsjubiläums

Ein Algorithmus ist eine eindeutige Handlungsvorschrift zur Lösung eines Problems oder einer Klasse von Problemen. Algorithmen bestehen aus endlich vielen, wohldefinierten Einzelschritten.[1] Damit können sie zur Ausführung in ein Computerprogramm implementiert, aber auch in menschlicher Sprache formuliert werden. Bei der Problemlösung wird eine bestimmte Eingabe in eine bestimmte Ausgabe überführt.[2]

Inhaltsverzeichnis
  • 1 Geschichtliche Entwicklung
  • 2 Wortherkunft
  • 3 Informatik und Mathematik
    • 3.1 Algorithmus und Programme
    • 3.2 Erster Computeralgorithmus
    • 3.3 Heutige Situation
  • 4 Definition
    • 4.1 Turingmaschinen und Algorithmusbegriff
    • 4.2 Church-Turing-These
    • 4.3 Abstrakte Automaten
  • 5 Abgrenzung zur Heuristik
  • 6 Eigenschaften
    • 6.1 Determiniertheit
    • 6.2 Determinismus
    • 6.3 Finitheit
      • 6.3.1 Statische Finitheit
      • 6.3.2 Dynamische Finitheit
      • 6.3.3 Terminiertheit
    • 6.4 Effektivität
    • 6.5 Beispiele für (weitere) Eigenschaften von Algorithmen
  • 7 Algorithmenanalyse
  • 8 Typen und Beispiele
    • 8.1 Alltagsformen von Algorithmen
  • 9 Geschichte des Algorithmus
    • 9.1 Antikes Griechenland
    • 9.2 Der Ursprung des Wortes
    • 9.3 Mathematik im 19. und 20. Jahrhundert
  • 10 Literatur
  • 11 Weblinks
  • 12 Fußnoten
Geschichtliche Entwicklung

Schon mit der Entwicklung der Sprache ersannen die Menschen für ihr Zusammenleben in größeren Gruppen Verhaltensregeln, Gebote, Gesetze – einfachste Algorithmen. Mit der Sprache ist auch eine geeignete Möglichkeit gegeben, Verfahren und Fertigkeiten weiterzugeben – komplexere Algorithmen. Aus der Spezialisierung einzelner Gruppenmitglieder auf bestimmte Fertigkeiten entstanden die ersten Berufe.

Der Algorithmusbegriff als abstrakte Sicht auf Aufgabenlösungswege trat zuerst im Rahmen der Mathematik, Logik und Philosophie ins Bewusstsein der Menschen. Ein Beispiel für einen mathematischen Algorithmus aus dem Altertum ist der Euklidische Algorithmus.

Wortherkunft Seite aus einer lateinischen Übersetzung (Cambridger Manuskript), beginnend mit „Dixit algorizmi“

Das Wort Algorithmus ist eine Abwandlung oder Verballhornung des Namens des persischen[3][4][5] Rechenmeisters und Astronomen Muḥammad Ibn-Mūsā al-H̱wārizmī, dessen Namensbestandteil (Nisba) al-Chwarizmi „der Choresmier“ bedeutet und auf die Herkunft des Trägers aus Choresmien verweist. Sein Lehrbuch Über die indischen Ziffern (verfasst um 825 im Haus der Weisheit in Bagdad) wurde im 12. Jahrhundert aus dem Arabischen ins Lateinische übersetzt und hierdurch in der westlichen Welt neben Leonardo Pisanos Liber Abaci zur wichtigsten Quelle für die Kenntnis und Verbreitung des indisch-arabischen Zahlensystems und des schriftlichen Rechnens. Mit der lateinischen Übersetzung al-Hwarizmis wurde auch der Name des Verfassers in Anlehnung an die Anfangsworte der ältesten Fassung dieser Übersetzung (Dixit Algorismi „Algorismi hat gesagt“) latinisiert.[6] Aus al-Hwarizmi wurde mittelhochdeutsch algorismus, alchorismus oder algoarismus – ein Wort, das aus dem Lateinischen nahezu zeitgleich und gleichlautend ins Altfranzösische (algorisme, argorisme) und Mittelenglische (augrim, augrym) übersetzt wurde. Mit Algorismus bezeichnete man bis um 1600 Lehrbücher, die in den Gebrauch der Fingerzahlen, der Rechenbretter, der Null, die indisch-arabischen Zahlen und das schriftliche Rechnen einführen.[7] Das schriftliche Rechnen setzte sich dabei erst allmählich durch. So beschreibt etwa der englische Dichter Geoffrey Chaucer noch Ende des 14. Jahrhunderts in seinen Canterbury Tales einen Astrologen, der Steine zum Rechnen („augrym stones“) am Kopfende seines Betts aufbewahrt:

This clerk was cleped hende Nicholas. / His augrym stones layen faire apart, / On shelves couched at his beddes heed;

In der mittelalterlichen Überlieferung wurde das Wort bald als erklärungsbedürftig empfunden und dann seit dem 13. Jahrhundert zumeist als Zusammensetzung aus einem Personennamen Algus und aus einem aus dem griechischen ῥυσμός (Nebenform von ῥυθμός) in der Bedeutung „Zahl“ entlehnten Wortbestandteil -rismus interpretiert.

Algus, der vermutete Erfinder dieser Rechenkunst, wurde hierbei von einigen als Araber, von anderen als Grieche oder zumindest griechisch schreibender Autor, gelegentlich auch als „König von Kastilien“ (Johannes von Norfolk) betrachtet. In der volkssprachlichen Tradition erscheint dieser „Meister Algus“ dann zuweilen in einer Reihe mit großen antiken Denkern wie Platon, Aristoteles und Euklid, so im altfranzösischen Roman de la Rose, während das altitalienische Gedicht Il Fiore ihn sogar mit dem Erbauer des Schiffes Argo gleichsetzt, mit dem Jason sich auf die Suche nach dem Goldenen Vlies begab.

Auf der para-etymologischen Zurückführung des zweiten Bestandteils -rismus auf griech. ῥυσμός, ῥυθμός beruht dann auch die präzisierende lateinische Wortform algorithmus, die seit der Frühen Neuzeit, anfangs auch mit der Schreibvariante algorythmus, größere Verbreitung erlangte und zuletzt die heute übliche Wortbedeutung als Fachterminus für geregelte Prozeduren zur Lösung definierter Probleme annahm.

Informatik und Mathematik

Algorithmen sind eines der zentralen Themen der Informatik und Mathematik. Sie sind Gegenstand einiger Spezialgebiete der Theoretischen Informatik, der Komplexitätstheorie und der Berechenbarkeitstheorie, mitunter ist ihnen ein eigener Fachbereich Algorithmik oder Algorithmentheorie gewidmet. In Form von Computerprogrammen und elektronischen Schaltkreisen steuern Algorithmen Computer und andere Maschinen.

Algorithmus und Programme

Für Algorithmen gibt es unterschiedliche formale Repräsentationen. Diese reichen vom Algorithmus als abstraktem Gegenstück zum konkret auf eine Maschine zugeschnittenen Programm (das heißt, die Abstraktion erfolgt hier im Weglassen der Details der realen Maschine, das Programm ist eine konkrete Form des Algorithmus, angepasst an die Notwendigkeiten und Möglichkeiten der realen Maschine) bis zur Ansicht, Algorithmen seien gerade die Maschinenprogramme von Turingmaschinen (wobei hier die Abstraktion in der Verwendung der Turingmaschine an sich erfolgt, das heißt, einer idealen mathematischen Maschine).

Algorithmen können in Programmablaufplänen nach DIN 66001 oder ISO 5807 grafisch dargestellt werden.

Erster Computeralgorithmus

Der erste für einen Computer gedachte Algorithmus (zur Berechnung von Bernoullizahlen) wurde 1843 von Ada Lovelace in ihren Notizen zu Charles Babbages Analytical Engine festgehalten. Sie gilt deshalb als die erste Programmiererin. Weil Charles Babbage seine Analytical Engine nicht vollenden konnte, wurde Ada Lovelaces Algorithmus nie darauf implementiert.

Heutige Situation Prinzipbild des Rete-Algorithmus für Expertensystem; veröffentlicht: 1979; frei

Algorithmen für Computer sind heute so vielfältig wie die Anwendungen, die sie ermöglichen sollen. Vom elektronischen Steuergerät für den Einsatz im KFZ über die Rechtschreib- und Satzbau-Kontrolle in einer Textverarbeitung bis hin zur Analyse von Aktienmärkten finden sich tausende von Algorithmen. Hinsichtlich der Ideen und Grundsätze, die einem Computerprogramm zugrunde liegen, wird einem Algorithmus in der Regel urheberrechtlicher Schutz versagt.[8] Je nach nationaler Ausgestaltung der Immaterialgüterrechte sind Algorithmen der Informatik jedoch dem Patentschutz zugänglich, so dass urheberrechtlich freie individuelle Werke, als Ergebnis eigener geistiger Schöpfung, wirtschaftlich trotzdem nicht immer frei verwertet werden können. Dies betrifft oder betraf z. B. Algorithmen, die auf der Mathematik der Hough-Transformation (Jahrzehnte alt, aber mehrfach aktualisiertes Konzept mit Neu-Anmeldung) aufbauen, Programme, die das Bildformat GIF lesen und schreiben wollten, oder auch Programme im Bereich der Audio- und Video-Verarbeitung, da die zugehörigen Algorithmen, wie sie in den zugehörigen Codecs umgesetzt sind, oftmals nicht frei verfügbar sind. Die entsprechenden Einsparpotentiale für alle Anwender weltweit (für den Rete-Algorithmus wurde einst eine Million USD auf DEC XCON genannt) dürften heute problemlos die Grenze von einer Milliarde USD im Jahr um ein Zigfaches überschreiten.

Definition Turingmaschinen und Algorithmusbegriff

Die mangelnde mathematische Genauigkeit des Begriffs Algorithmus störte viele Mathematiker und Logiker des 19. und 20. Jahrhunderts, weswegen in der ersten Hälfte des 20. Jahrhunderts eine ganze Reihe von Ansätzen entwickelt wurde, die zu einer genauen Definition führen sollten. Formalisierungen des Berechenbarkeitsbegriffs sind die Turingmaschine (Alan Turing), Registermaschinen, der Lambda-Kalkül (Alonzo Church), rekursive Funktionen, Chomsky-Grammatiken (siehe Chomsky-Hierarchie) und Markow-Algorithmen.

Es wurde – unter maßgeblicher Beteiligung von Alan Turing selbst – gezeigt, dass all diese Methoden die gleiche Berechnungsstärke besitzen (gleich mächtig sind). Sie können durch eine Turingmaschine emuliert werden, und sie können umgekehrt eine Turingmaschine emulieren.

Mit Hilfe des Begriffs der Turingmaschine kann folgende formale Definition des Begriffs formuliert werden:

Eine Berechnungsvorschrift zur Lösung eines Problems heißt genau dann Algorithmus, wenn eine zu dieser Berechnungsvorschrift äquivalente Turingmaschine existiert, die für jede Eingabe, die eine Lösung besitzt, stoppt.

Aus dieser Definition sind folgende Eigenschaften eines Algorithmus ableitbar:

  1. Das Verfahren muss in einem endlichen Text eindeutig beschreibbar sein (Finitheit).
  2. Jeder Schritt des Verfahrens muss tatsächlich ausführbar sein (Ausführbarkeit).
  3. Das Verfahren darf zu jedem Zeitpunkt nur endlich viel Speicherplatz benötigen (Dynamische Finitheit, siehe Platzkomplexität).
  4. Das Verfahren darf nur endlich viele Schritte benötigen (Terminierung, siehe auch Zeitkomplexität).

Darüber hinaus wird der Begriff Algorithmus in praktischen Bereichen oft auf die folgenden Eigenschaften eingeschränkt:

  1. Der Algorithmus muss bei denselben Voraussetzungen das gleiche Ergebnis liefern (Determiniertheit).
  2. Die nächste anzuwendende Regel im Verfahren ist zu jedem Zeitpunkt eindeutig definiert (Determinismus).
Church-Turing-These

Die Church-Turing-These besagt, dass jedes intuitiv berechenbare Problem durch eine Turingmaschine gelöst werden kann. Als formales Kriterium für einen Algorithmus zieht man die Implementierbarkeit in einem beliebigen, zu einer Turingmaschine äquivalenten Formalismus heran, insbesondere die Implementierbarkeit in einer Programmiersprache – die von Church verlangte Terminiertheit ist dadurch allerdings noch nicht gegeben.

Der Begriff der Berechenbarkeit ist dadurch dann so definiert, dass ein Problem genau dann berechenbar ist, wenn es einen (terminierenden) Algorithmus zu dem Problem gibt, das heißt, wenn eine entsprechend programmierte Turingmaschine das Problem in endlicher Zeit lösen könnte.

Es sei bemerkt, dass die Ambiguität des Begriffs „intuitiv berechenbares Problem“ den mathematischen Beweis dieser These unmöglich macht. Es ist also theoretisch denkbar, dass intuitiv berechenbare Probleme existieren, die nach dieser Definition nicht als „berechenbar“ gelten. Bis heute wurde jedoch noch kein solches Problem gefunden.[9]

Abstrakte Automaten

Turingmaschinen harmonieren gut mit den ebenfalls abstrakt-mathematischen berechenbaren Funktionen, reale Probleme sind jedoch ungleich komplexer, daher wurden andere Maschinen vorgeschlagen.

Diese Maschinen weichen etwa in der Mächtigkeit der Befehle ab; statt der einfachen Operationen der Turingmaschine können sie teilweise mächtige Operationen, wie etwa Fourier-Transformationen, in einem Rechenschritt ausführen.

Oder sie beschränken sich nicht auf eine Operation pro Rechenschritt, sondern ermöglichen parallele Operationen, wie etwa die Addition zweier Vektoren in einem Schritt.

Ein Modell einer echten Maschine ist die Sequential Abstract State Machine (kurz seq. ASM)[10] mit folgenden Eigenschaften:

Ein Algorithmus einer seq. ASM soll

  • durch einen endlichen Programmtext spezifiziert werden können
  • schrittweise ausgeführt werden können
  • für bestimmte Zustände terminieren, muss aber nicht immer terminieren (sinnvolle Gegenbeispiele für die Forderung, dass immer terminiert werden muss, wären etwa ein Programm, das fortgesetzt Primzahlen findet, oder ein Betriebssystem)
  • nur begrenzt viele Zustände pro Schritt ändern können (Begrenzung der Parallelität)
  • nur begrenzt viele Zustände pro Schritt inspizieren können (Begrenzung der Exploration).
Abgrenzung zur Heuristik → Hauptartikel: Heuristik

Der Übergang zwischen Algorithmus und Heuristik ist fließend: Eine Heuristik ist eine Methode, aus unvollständigen Eingangsdaten zu möglichst sinnvollen Ergebnissen zu gelangen. Viele heuristische Vorgehensweisen sind selbst exakt definiert und damit Algorithmen. Bei manchen ist jedoch nicht in jedem Schritt genau festgelegt, wie vorzugehen ist – der Anwender muss „günstig raten“. Sie können nicht (vollständig) als Algorithmus formuliert werden.

Eigenschaften Determiniertheit

Ein Algorithmus ist determiniert, wenn dieser bei jeder Ausführung mit gleichen Startbedingungen und Eingaben gleiche Ergebnisse liefert.

Determinismus

Ein Algorithmus ist deterministisch, wenn zu jedem Zeitpunkt der Algorithmusausführung der nächste Handlungsschritt eindeutig definiert ist. Wenn an mindestens einer Stelle mehr als eine Möglichkeit besteht (ohne Vorgabe, welche zu wählen ist), dann ist der gesamte Algorithmus nichtdeterministisch.

Beispiele für deterministische Algorithmen sind Bubblesort und der euklidische Algorithmus. Dabei gilt, dass jeder deterministische Algorithmus determiniert, während aber nicht jeder determinierte Algorithmus deterministisch ist. So ist Quicksort mit zufälliger Wahl des Pivotelements ein Beispiel für einen determinierten, aber nicht deterministischen Algorithmus, da sein Ergebnis bei gleicher Eingabe und eindeutiger Sortierung immer dasselbe ist, der Weg dorthin jedoch zufällig erfolgt.

Nichtdeterministische Algorithmen können im Allgemeinen mit keiner realen Maschine (auch nicht mit Quantencomputern) direkt umgesetzt werden.

Beispiel für einen nichtdeterministischen Algorithmus wäre ein Kochrezept, dass mehrere Varianten beschreibt. Es bleibt dem Koch überlassen, welche er durchführen möchte. Auch das Laufen durch einen Irrgarten lässt an jeder Verzweigung mehrere Möglichkeiten, und neben vielen Sackgassen können mehrere Wege zum Ausgang führen.

Finitheit Statische Finitheit

Die Beschreibung des Algorithmus besitzt eine endliche Länge, der Quelltext muss also aus einer begrenzten Anzahl von Zeichen bestehen.

Dynamische Finitheit

Ein Algorithmus darf zu jedem Zeitpunkt seiner Ausführung nur begrenzt viel Speicherplatz benötigen.

Terminiertheit

Ein Algorithmus ‚terminiert überall‘ oder ‚ist terminierend‘, wenn er nach endlich vielen Schritten anhält (oder kontrolliert abbricht) – für jede mögliche Eingabe. Ein nicht-terminierender Algorithmus (somit zu keinem Ergebnis kommend) gerät (für manche Eingaben) in eine so genannte Endlosschleife.

Für manche Abläufe ist ein nicht-terminierendes Verhalten gewünscht: Z. B. Steuerungssysteme, Betriebssysteme und Programme, die auf Interaktion mit dem Benutzer aufbauen. Solange der Benutzer keinen Befehl zum Beenden eingibt, laufen diese Programme beabsichtigt endlos weiter. Donald E. Knuth schlägt in diesem Zusammenhang vor, nicht terminierende Algorithmen als rechnergestützte Methoden (Computational Methods) zu bezeichnen.

Darüber hinaus ist die Terminierung eines Algorithmus (das Halteproblem) nicht entscheidbar. Das heißt, das Problem, festzustellen, ob ein (beliebiger) Algorithmus mit einer beliebigen Eingabe terminiert, ist nicht durch einen Algorithmus lösbar.

Effektivität

Der Effekt jeder Anweisung eines Algorithmus muss eindeutig festgelegt sein.

Beispiele für (weitere) Eigenschaften von Algorithmen
  • Einfache Grundoperation: „Öffne die Flasche Wein“ – hierbei wird das Wissen um das Öffnen vorausgesetzt.
  • Sequentieller Algorithmus: „Bier auf Wein, lass das sein“ – beiden Operationen ist eine Reihenfolge vorgegeben.
  • Nebenläufiger Algorithmus: „Schnaps und Bier“ – die Reihenfolge ist nicht vorgegeben und kann auch gleichzeitig erfolgen.
  • Parallele Ausführung: „Mit Sekt anstoßen“ – dies kann nur gleichzeitig (parallel) ausgeführt werden und nicht hintereinander (sequentiell).
  • Nichtdeterministischer/nichtdeterminierter Algorithmus: „Bier oder Wasser“ – das Ergebnis kann sich unterscheiden, je nachdem welches man wählt.
Algorithmenanalyse

Die Erforschung und Analyse von Algorithmen ist eine Hauptaufgabe der Informatik, und wird meist theoretisch (ohne konkrete Umsetzung in eine Programmiersprache) durchgeführt. Sie ähnelt somit dem Vorgehen in anderen mathematischen Gebieten, in denen die Analyse eher auf die zugrunde liegenden Konzepte als auf konkrete Umsetzungen ausgerichtet ist. Algorithmen werden zur Analyse in eine stark formalisierte Form gebracht und mit den Mitteln der formalen Semantik untersucht.

Die Analyse unterteilt sich in verschiedene Teilgebiete. Beispielsweise wird das Verhalten von Algorithmen bezüglich Ressourcenbedarf wie Rechenzeit und Speicherbedarf in der Komplexitätstheorie behandelt; die Ergebnisse werden als asymptotische Laufzeiten angegeben. Der Ressourcenbedarf wird dabei in Abhängigkeit von der Länge der Eingabe ermittelt, das heißt, die angegebene Komplexität hängt davon ab, wie groß die Zahlen sind, deren größter gemeinsamer Teiler gesucht wird, oder wie viele Elemente sortiert werden müssen etc.

Das Verhalten bezüglich der Terminierung, ob also der Algorithmus überhaupt jemals erfolgreich beendet werden kann, behandelt die Berechenbarkeitstheorie.

Typen und Beispiele Die Lösung für das Spiel Türme von Hanoi mit drei Spielsteinen – ein einfacher Algorithmus

Der älteste bekannte nicht-triviale Algorithmus ist der euklidische Algorithmus. Spezielle Algorithmus-Typen sind der randomisierte Algorithmus (mit Zufallskomponente), der Approximationsalgorithmus (als Annäherungsverfahren), die evolutionären Algorithmen (nach biologischem Vorbild) und der Greedy-Algorithmus.

Eine weitere Übersicht gibt die Liste von Algorithmen und die Kategorie Algorithmus.

Alltagsformen von Algorithmen

Rechenvorschriften sind eine Untergruppe der Algorithmen. Sie beschreiben Handlungsanweisungen in der Mathematik bezüglich Zahlen. Andere Algorithmen-Untergruppen sind z. B. (Koch-)Rezepte, Gesetze, Verordnungen, Regeln, Verträge.

Geschichte des Algorithmus Antikes Griechenland

Obwohl der etymologische Ursprung des Wortes arabisch ist, entstanden die ersten Algorithmen im antiken Griechenland. Zu den wichtigsten Beispielen gehören das Sieb des Eratosthenes zum Auffinden von Primzahlen, welches im Buch Einführung in die Arithmetik von Nikomachos beschrieben wurde[11] und der euklidische Algorithmus zum Berechnen des größten gemeinsamen Teilers zweier natürlicher Zahlen aus dem Werk „die Elemente“.[12] Einer der ältesten Algorithmen, die sich mit einer reellen Zahl beschäftigen, ist der Algorithmus des Archimedes zur Approximation von π {\displaystyle \pi } , was zugleich auch eines der ältesten numerischen Verfahren ist.[13]

Der Ursprung des Wortes

Das Wort „Algorithmus“ stammt aus dem 9. Jahrhundert und leitet sich vom Namen des choresmischen Mathematiker Al-Chwarizmi ab, der auf der Arbeit des aus dem 7. Jahrhundert stammenden indischen Mathematikers Brahmagupta[14][15] aufbaute. In seiner ursprünglichen Bedeutung bezeichnete ein Algorithmus nur das Einhalten der arithmetischen Regeln unter Verwendung der indisch-arabischen Ziffern. Die ursprüngliche Definition entwickelte sich mit Übersetzung ins Lateinische weiter.[16]

Mathematik im 19. und 20. Jahrhundert

Bedeutende Arbeit leisteten die Logiker des 19. Jahrhunderts. George Boole, der in seiner Schrift The Mathematical Analysis of Logic den ersten algebraischen Logikkalkül erschuf, begründete damit die moderne mathematische Logik, die sich von der traditionellen philosophischen Logik durch eine konsequente Formalisierung abhebt.[17] Gottlob Frege entwickelte als erster eine formale Sprache und die daraus resultierenden formalen Beweise.[18] Giuseppe Peano reduzierte die Arithmetik auf eine Sequenz von Symbolen manipuliert von Symbolen. Er beschäftigte sich mit der Axiomatik der natürlichen Zahlen. Dabei entstanden die Peano-Axiome.[19]

Die Arbeit von Frege wurde stark von Alfred North Whitehead und Bertrand Russell in ihrem Werk Principia Mathematica weiter ausgearbeitet und vereinfacht.[20] Zuvor wurde von Bertrand Russell die berühmte russellsche Antinomie formuliert, was zum Einsturz der naiven Mengenlehre führte. Das Resultat führte auch zur Arbeit Kurt Gödels.

David Hilbert hat um 1928 das Entscheidungsproblem in seinem Forschungsprogramm präzise formuliert.[21] Alan Turing und Alonzo Church haben für das Problem 1936 festgestellt, dass es unlösbar ist.[22]

Literatur
  • Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein: Algorithmen. Eine Einführung. 2., korr. Auflage. Oldenbourg, München, Wien 2007, ISBN 3-486-58262-3. (Originaltitel: Introduction to algorithms. Übersetzt von Karen Lippert, Micaela Krieger-Hauwede).
    Englischsprachige Originalausgabe: Introduction to Algorithms. 2. Auflage. MIT Press, Cambridge (Massachusetts) 2001, ISBN 0-262-03293-7.
  • Christoph Drösser: Total berechenbar? Wenn Algorithmen für uns entscheiden. Hanser-Verlag, 2016, ISBN 978-3-446-44699-1.[23]
  • John E. Hopcroft, Rajeev Motwani, Jeffrey Ullman: Einführung in die Automatentheorie, formale Sprachen und Komplexitätstheorie. 2., überarb. Auflage. Pearson Studium, München 2002, ISBN 3-8273-7020-5 (Originaltitel: Introduction to automata theory, languages, and computation. Übersetzt von Sigrid Richter, Ingrid Tokar). .
  • Donald E. Knuth: The Art of Computer Programming. Band 1–3. Addison Wesley, Reading (Mass.) 1998, ISBN 0-201-48541-9.
  • Anany Levitin: Introduction to The Design and Analysis of Algorithms. Addison Wesley, 2007, ISBN 0-321-36413-9.
  • Thomas Ottmann, Peter Widmayer: Algorithmen und Datenstrukturen. 4. Auflage. Spektrum Akademischer Verlag, Heidelberg 2002, ISBN 3-8274-1029-0.
  • Sebastian Stiller: Planet der Algorithmen – Ein Reiseführer. Knaus-Verlag, 2015. ISBN 978-3-641-16793-6.
  • Jochen Ziegenbalg, Oliver Ziegenbalg und Bernd Ziegenbalg: Zum Begriff des Algorithmus. In: Algorithmen von Hammurapi bis Gödel. 3. Auflage. Deutsch, Frankfurt 2010, ISBN 978-3-8171-1864-9, S. 24–31.
Weblinks  Wiktionary: Algorithmus – Bedeutungserklärungen, Wortherkunft, Synonyme, Übersetzungen
  • Tom Schimmeck: Algorithmen im US-Justizsystem: Schicksalsmaschinen. In: deutschlandfunk.de, 20. Juni 2017,
  • Der Algorithmus der Woche (Algorithmen anschaulich erklärt, herausgegeben vom Fakultätentag Informatik)
  • Dictionary of Algorithms and Data Structures des NIST (englisch)
  • Was ist Algorithmik? – Seite beim Fachbereich Informatik der TU Darmstadt
  • Vorlesungsmitschrift Höhere Algorithmik der FU Berlin (PDF; 1,9 MB)
Fußnoten
  1. ↑ Hartley Rogers, Jr.: Theory of Recursive Functions and Effective Computability, S. 2.
  2. ↑ Charles E. Leiserson, Ronald L. Rivest, Clifford Stein: Algorithmen – Eine Einführung. Oldenbourg Verlag, München 2010, ISBN 978-3-486-59002-9, S. 5. 
  3. ↑ Clifford A. Pickover: The Math Book: From Pythagoras to the 57th Dimension, 250 Milestones in the History of Mathematics. Sterling Publishing Company, Inc., 2009, ISBN 978-1-4027-5796-9 (eingeschränkte Vorschau in der Google-Buchsuche). 
  4. ↑ MHMC.htm. Abgerufen am 26. Mai 2018. 
  5. ↑ Al-Khwarizmi Persian Mathematician, Astronomer and Geographer part one : Persian Heritage. Abgerufen am 26. Mai 2018. 
  6. ↑ Muḥammad Ibn-Mūsā al-H̱wārizmī: Die älteste lateinische Schrift über das indische Rechnen nach al-Ḫwārizmī. Hrsg.: Menso Folkerts, Paul Kunitzsch. Verlag der Bayrischen Akademie der Wissenschaften, München 1997. 
  7. ↑ Kurt Vogel: Der Trienter Algorismus von 1475. In: Nova Acta Leopoldina, Neue Folge, Band 27, 1963, S. 183–200.
  8. ↑ Deutschland: § 69a Abs. (2) UrhG.
  9. ↑ Hromkovič, Juraj, 1958-: Theoretische Informatik Formale Sprachen, Berechenbarkeit, Komplexitätstheorie, Algorithmik, Kommunikation und Kryptographie /Juraj Hromkovič. 5., überarb. Aufl. Springer Vieweg, Wiesbaden 2014, ISBN 978-3-658-06432-7. 
  10. ↑ Sequential Abstract State Machine (seq. ASM).
  11. ↑ Roger L. Cooke: The History of Mathematics: A Brief Course, Wiley 2005, S. 166.
  12. ↑ http://aleph0.clarku.edu/~djoyce/elements/bookVII/propVII2.html
  13. ↑ http://itech.fgcu.edu/faculty/clindsey/mhf4404/archimedes/archimedes.html.
  14. ↑ http://www.andyborne.com/math/downloads/AL-Kwarazmi.pdf.
  15. ↑ Brahmagupta biography.
  16. ↑ History of Algorithms and Algorithmics. In: Scriptol.com. Abgerufen am 7. November 2012. 
  17. ↑ Project Gutenberg's The Mathematical Analysis of Logic, by George Boole.
  18. ↑ Gottlob Frege – Eine Einführung in sein Werk (PDF)
  19. ↑ Peano: Arithmetices principia nova methodo exposita, Turin 1889.
  20. ↑ http://name.umdl.umich.edu/AAT3201.0001.001 Principia Mathematica. 1. Auflage. 1910–1913, in der Onlineversion der University of Michigan.
  21. ↑ Tapp, Christian: An den Grenzen des Endlichen. Das Hilbertprogramm im Kontext von Formalismus und Finitismus. Springer, Heidelberg 2013, ISBN 978-3-642-29654-3.
  22. ↑ cf. footnote in Alonzo Church 1936a in Davis 1965:90 and 1936b in Davis 1965:110.
  23. ↑ Dagmar Röhrlich: Die neue Weltmacht. In: Deutschlandfunk.de, Wissenschaft im Brennpunkt, 20. März 2016, abgerufen am 28. März 2016.
Normdaten (Sachbegriff): GND: 4001183-5 (AKS)



Algorithmen - Eine Einführung
Algorithmen - Eine Einführung
Gebundenes BuchDer "Cormen" bietet eine umfassende und vielseitige Einführung in das moderne Studium von Algorithmen. Es stellt viele Algorithmen Schritt für Schritt vor, behandelt sie detailliert und macht deren Entwurf und deren Analyse allen Leserschichten zugänglich. Sorgfältige Erklärungen zur notwendigen Mathematik helfen, die Analyse der Algorithmen zu verstehen. Den Autoren ist es dabei geglückt, Erklärungen elementar zu halten, ohne auf Tiefe oder mathematische Exaktheit zu verzichten. Jedes der weitgehend eigenständig gestalteten Kapitel stellt einen Algorithmus, eine Entwurfstechnik, ein Anwendungsgebiet oder ein verwandtes Thema vor. Algorithmen werden beschrieben und in Pseudocode entworfen, der für jeden lesbar sein sollte, der schon selbst ein wenig programmiert hat. Zahlreiche Abbildungen verdeutlichen, wie die Algorithmen arbeiten. Ebenfalls angesprochen werden Belange der Implementierung und andere technische Fragen, wobei, da Effizienz als Entwurfskriterium betont wird, die Ausführungen eine sorgfältige Analyse der Laufzeiten der Programme mit ein schließen. Über 1000 Übungen und Problemstellungen und ein umfangreiches Quellen- und Literaturverzeichnis komplettieren das Lehrbuch, dass durch das ganze Studium, aber auch noch danach als mathematisches Nachschlagewerk oder als technisches Handbuch nützlich ist. Für die dritte Auflage wurde das gesamte Buch aktualisiert. Die Änderungen sind vielfältig und umfassen insbesondere neue Kapitel, überarbeiteten Pseudocode, didaktische Verbesserungen und einen lebhafteren Schreibstil. So wurden etwa - neue Kapitel zu van-Emde-Boas-Bäume und mehrfädigen (engl.: multithreaded) Algorithmen aufgenommen, - das Kapitel zu Rekursionsgleichungen überarbeitet, sodass es nunmehr die Teile-und-Beherrsche-Methode besser abdeckt, - die Betrachtungen zu dynamischer Programmierung und Greedy-Algorithmen überarbeitet; Memoisation und der Begriff des Teilproblem-Graphen als eine Möglichkeit, die Laufzeit eines auf...

Klicken Sie hier um zu sehen Augmented Reality

EUR 89,95



Algorithmen: Algorithmen und Datenstrukturen (Pearson Studium - IT)
Algorithmen: Algorithmen und Datenstrukturen (Pearson Studium - IT)
Algorithmen und DatenstrukturenBroschiertes BuchDie 4. Auflage des Klassikers Algorithmen von Robert Sedgewick und Kevin Wayne ermöglicht dem deutschsprachigen Leser einen grundlegenden und umfangreichen Einstieg in die wichtigsten Datenstrukturen und Algorithmen und deren Analyse und Anwendung. In der neuesten Auflage wurden Inhalte aktualisiert, um neue mächtige Algorithmen ergänzt und wieder in einem Band zusammengefasst.

Klicken Sie hier um zu sehen Augmented Reality

EUR 69,95



Algorithmen und Datenstrukturen
Algorithmen und Datenstrukturen
Gebundenes BuchDieses bestens eingeführte Lehrbuch wendet sich an Studierende der Informatik in Grund- und Hauptstudium. Die einzelnen Algorithmen werden theoretisch fundiert dargestellt; ihre Funktionsweise wird ausführlich anhand vieler Beispiele erläutert. Zusätzlich zur halbformalen Beschreibung werden wichtige Algorithmen in Java formuliert. Das Themenspektrum reicht von Algorithmen zum Suchen und Sortieren über Hashverfahren, Bäume, Manipulation von Mengen bis hin zu Geometrischen Algorithmen und Graphenalgorithmen. Dabei werden sowohl der Entwurf effizienter Algorithmen und Datenstrukturen als auch die Analyse ihres Verhaltens mittels mathematischer Methoden behandelt. Das Buch eignet sich zur Vorlesungsbegleitung, zum Selbststudium und zum Nachschlagen. Eine Vielzahl von Aufgaben dient der weiteren Vertiefung des Gelernten. Java-Programme für die wichtigsten Algorithmen und ergänzende Materialien zum Buch werden online bereitgestellt.

Klicken Sie hier um zu sehen Augmented Reality

EUR 59,99



Angriff der Algorithmen: Wie sie Wahlen manipulieren, Berufschancen zerstören und unsere Gesundheit gefährden
Angriff der Algorithmen: Wie sie Wahlen manipulieren, Berufschancen zerstören und unsere Gesundheit gefährden
Wie sie Wahlen manipulieren, Berufschancen zerstören und unsere Gesundheit gefährdenGebundenes BuchAlgorithmen nehmen Einfluss auf unser Leben: Von ihnen hängt es ab, ob man etwa einen Kredit für sein Haus erhält und wie viel man für die Krankenversicherung bezahlt. Cathy O'Neil, ehemalige Hedgefonds-Managerin und heute Big-Data-Whistleblowerin, erklärt, wie Algorithmen in der Theorie objektive Entscheidungen ermöglichen, im wirklichen Leben aber mächtigen Interessen folgen. Algorithmen nehmen Einfluss auf die Politik, gefährden freie Wahlen und manipulieren über soziale Netzwerke sogar die Demokratie. Cathy O'Neils dringlicher Appell zeigt, wie sie Diskriminierung und Ungleichheit verstärken und so zu Waffen werden, die das Fundament unserer Gesellschaft erschüttern.

Klicken Sie hier um zu sehen Augmented Reality

EUR 24,00



Algorithmen und Datenstrukturen: Eine Einführung mit Java
Algorithmen und Datenstrukturen: Eine Einführung mit Java
Eine Einführung mit JavaGebundenes BuchKenntnisse von Algorithmen und Datenstrukturen sind ein Grundbaustein des Studiums der Informatik und verwandter Fachrichtungen. Das Buch behandelt diese Thematik in Verbindung mit der Programmiersprache Java und schlägt so eine Brücke zwischen den klassischen Lehrbüchern zur Theorie von Algorithmen und Datenstrukturen und den praktischen Einführungen in eine konkrete Programmiersprache. Die konkreten Algorithmen und deren Realisierung in Java werden umfassend dargestellt. Daneben werden die theoretischen Grundlagen vermittelt, die in Programmiersprachen-Kursen oft zu kurz kommen: abstrakte Maschinenmodelle, Berechenbarkeit, Algorithmenparadigmen sowie parallele und verteilte Abläufe. Einen weiteren Schwerpunkt bilden Datenstrukturen wie Listen, Bäume, Graphen und Hashtabellen sowie deren objektorientierte Implementierung mit modernen Methoden der Softwareentwicklung. Die 5. Auflage wurde überarbeitet und gibt u.a. einen Überblick über die mit Java 8 eingeführten Lambda-Ausdrücke, die eine Anwendung des applikativen (funktionalen) Paradigmas darstellen. Weiter wurden neue Beispiele, die aus dem Einsatz des Buches in einigen Einführungsvorlesungen entstanden sind, aufgenommen. Das Buch richtet sich an Studierende im Grundstudium an Universitäten und Fachhochschulen sowie an alle, die die Grundlagen der praktischen Informatik strukturiert erlernen wollen. Sie erwerben damit die Basis für die theoretischen und praktischen Vertiefungen im Hauptstudium und lernen gleichzeitig die Umsetzung in den "Alltag" der Softwareentwicklung kennen.

Klicken Sie hier um zu sehen Augmented Reality

EUR 44,90



Algorithmen für Dummies
Algorithmen für Dummies
Wir leben in einer algorithmenbestimmten Welt. Deshalb lohnt es sich zu verstehen, wie Algorithmen arbeiten. Das Buch präsentiert die wichtigsten Anwendungsgebiete für Algorithmen: Optimierung, Sortiervorgänge, Graphentheorie, Textanalyse, Hashfunktionen. Zu jedem Algorithmus werden jeweils Hintergrundwissen und praktische Grundlagen vermittelt sowie Beispiele für aktuelle Anwendungen gegeben. Für interessierte Leser gibt es Umsetzungen in Python, sodass die Algorithmen auch verändert und die Auswirkungen der Veränderungen beobachtet werden können. Dieses Buch richtet sich an Menschen, die an Algorithmen interessiert sind, ohne eine Doktorarbeit zu dem Thema schreiben zu wollen. Wer es gelesen hat, versteht, wie wichtige Algorithmen arbeiten und wie man von dieser Arbeit beispielsweise bei der Entwicklung von Unternehmensstrategien profitieren kann.

Klicken Sie hier um zu sehen Augmented Reality



Künstliche Intelligenz: Mit Algorithmen zum wirtschaftlichen Erfolg
Künstliche Intelligenz: Mit Algorithmen zum wirtschaftlichen Erfolg
Mit Algorithmen zum wirtschaftlichen ErfolgBroschiertes BuchDieses Buch soll dabei helfen, die neuen Technologien und Anwendungspotenziale der künstlichen Intelligenz besser zu verstehen und einzuordnen. Neben einer ausführlichen und verständlichen Vermittlung grundlegender Kenntnisse und ökonomischer Effekte der künstlichen Intelligenz enthält es viele Anwendungsbeispiele bekannter Unternehmen. Konzerne wie Amazon, IBM, Microsoft, SAP oder VW lassen die Leser in ihre KI-Labors schauen und erklären konkrete Projekte zu Themen, wie z. B. Chatbots, Quantencomputing, Gesichtserkennung, sprachbasierte Systeme oder den Einsatz von KI-Anwendungen in den Bereichen Marketing, Vertrieb, Finanzen, Personalwesen, Produktion, Gesundheit sowie Logistik. Das Buch richtet sich an Entscheider in Unternehmen, Studierende, Dozenten und alle, die sich ein Bild über die vielleicht wichtigste technologische Entwicklung in diesem Jahrhundert machen möchten.

Klicken Sie hier um zu sehen Augmented Reality

EUR 34,99



Konkrete Mathematik (nicht nur) für Informatiker: Mit vielen Grafiken und Algorithmen in Python
Konkrete Mathematik (nicht nur) für Informatiker: Mit vielen Grafiken und Algorithmen in Python
Mit vielen Grafiken und Algorithmen in PythonGebundenes BuchDas etwas andere Mathe-Lehrbuch: Mathematik, die Informatiker (und nicht nur die!) wirklich brauchen, und die direkt am Computer umgesetzt wird in Form von kleinen Algorithmen, numerischen "Experimenten" und interaktiven Visualisierungen. Man lernt, wie man dem Computer das Rechnen überlässt, während man selbst den mathematischen Überblick behält, typische Fehler vermeidet und die Ergebnisse richtig interpretiert. (Und nebenbei lernt man noch die beliebte Programmiersprache Python sowie den Umgang mit einem Computeralgebrasystem.)Gleichzeitig wird die Mathematik aber nicht zur "Hilfswissenschaft" degradiert. Der Autor motiviert und begründet im "Plauderton" und mit konkreten Beispielen und Knobelaufgaben (und manchmal auch mit kleinen philosophischen und historischen Exkursen), um so den Leser zum Mitmachen und Mitdenken aufzufordern. Im Idealfall hat man am Ende nicht nur etwas gelernt, sondern verspürt Lust auf mehr - und sieht die Mathematik danach vielleicht mit anderen Augen.Mit informatik-spezifischen Anwendungen unter anderem aus der Kryptographie, der Kodierungs- und Komplexitätstheorie sowie der Computergrafik. Unterstützt durch viele farbige Grafiken, etwa 1000 Aufgaben mit Lösungen und nicht zuletzt Hunderte von Videos, in denen man sich das Gelesene vom Autor noch mal "persönlich" erklären lassen kann.

Klicken Sie hier um zu sehen Augmented Reality

EUR 44,99



Algorithmen kompakt und verständlich: Lösungsstrategien am Computer
Algorithmen kompakt und verständlich: Lösungsstrategien am Computer
Ameisen organisieren Städtereisen und ein Computer spielt Schach - wie es geht, das zeigt dieses Buch.Für Programmierer, die bereits erste Erfahrungen gesammelt haben, wird ein breites Spektrum an Problemlösungsstrategien anhand konkreter und verständlicher Beispiele vorgestellt.Sie können künftig selbstständig neue Aufgabenstellungen bewältigen, Optimierungspotential in bestehenden Programmen entdecken und damit bessere Software schreiben.

Klicken Sie hier um zu sehen Augmented Reality


Twitter
 
Facebook
 
LinkedIn
 
 

 
 

Trends
Flirten

WhmSoft Moblog
Copyright (C) 2006-2019 WhmSoft
All Rights Reserved