Das Entwerfen und Analysieren von effizienten Algorithmen ist eine der Haupt aufgaben eines/r jeden Informatikers/in. Obwohl für viele Probleme schon seit Jahrzehnten effiziente Algorithmen bekannt sind, tauchen dennoch immer wieder verblüffende und unerwartete Verbesserungen auf. Dies macht die Algorithmik zu einem höchst interessanten und spannenden Teilgebiet der Informatik, dessen Attraktivität und Reiz wir in diesem Buch einzufangen versuchen. Anhand alltäglicher Probleme aus der Welt der Informatik wollen wir die Methodik des Algorithmenentwurfs erläutern. Zum einen werden wir effiziente Algorithmen zur Lösung grundlegender Probleme kennen lernen und dabei auch auf die zum Teil überraschend einfachen, aber wirkungsvollen Verbesserungen ein gehen. Zum anderen werden wir die zugrunde liegenden, allgemein anwendbaren Methoden und Paradigmen präsentieren, die tagtäglich beim Algorithmenentwurf zum Einsatz kommen. Begleitend dazu stellen wir die grundlegenden Techniken zur Analyse von Algorithmen vor, ohne die Effizienzaussagen nicht möglich wären. Außerdem werden wir die Grenzen dessen aufzeigen, was algorithmisch überhaupt lösbar bzw. effizient realisierbar ist. Ein Hauptaugenmerk dieses Buch ist der Vollständigkeit der behandelten Algorithmen gewidmet, d.h. es wurde in der Regel vermieden, nur eine Beschrei bung von Algorithmen anzugeben, ohne deren Korrektheit zu beweisen bzw. deren Komplexität zu analysieren. Daher werden auch Themen angesprochen, die in Einführungsvorlesungen zur Algorithmik normalerweise nicht ausführlich behan delt werden, wie z.B. die Analyse des Boyer-Moore-Algorithmus oder der Beweis des Bertrandschen Postulats. Damit wird zu jedem behandelten Problemkreis eine möglichst abgeschlossene Einführung geboten.
Jeder Informatik Student benötigt Grundkenntnisse im Bereich Algorithmen. Diese Einführung wendet sich an alle Leser, die sich mit Entwurf und
der Analyse effizienter Algorithmen näher beschäftigen wollen.
An Hand alltäglicher Probleme aus der Informatik werden dem Leser sowohl
die gängigen Algorithmen zu deren Lösung als auch die dahinter
steckenden, allgemein anwendbaren Entwurfsmethoden präsentiert.
Autorentext
Klappentext
Inhalt
1 Einleitung und Grundlagen.- 1.1 Ziele.- 1.2 Einführendes Beispiel: Berechnung der Fibonacci-Zahlen.- 1.3 Grundlagen.- 1.4 Übungsaufgaben.- 2 Sortieren.- 2.1 Einfache Sortieralgorithmen.- 2.2 Mergesort.- 2.3 Heapsort.- 2.4 Quicksort.- 2.5 Interludium: Divide-and-Conquer-Algorithmen.- 2.6 Eine untere Schranke für das Sortieren.- 2.7 Bucketsort.- 2.8 Übungsaufgaben.- 3 Selektieren.- 3.1 Quickselect.- 3.2 Ein linearer Selektionsalgorithmus.- 3.3 Der Spinnen-Algorithmus.- 3.4 Eine untere Schranke.- 3.5 Ein randomisierter Median-Algorithmus.- 3.6 Neuere Ergebnisse.- 3.7 Übungsaufgaben.- 4 Suchen.- 4.1 Wörterbücher.- 4.2 Ausnutzen von Sortierung.- 4.3 Hashing.- 4.4 Binäre Suchbäume.- 4.5 AVL-Bäume.- 4.6 (a, b)-Bäume.- 4.7 Weitere Varianten von Suchbäumen.- 4.8 Tries.- 4.9 Übungsaufgaben.- 5 Graphen.- 5.1 Grundlagen der Graphentheorie.- 5.2 Traversieren von Graphen.- 5.3 Zusammenhang von Graphen.- 5.4 Kürzeste Wege.- 5.5 Interludium: Fibonacci-Heaps.- 5.6 Minimale Spannbäume.- 5.7 Interludium: Union-Find-Datenstrukturen.- 5.8 Übungsaufgaben.- 6 Texte.- 6.1 Alphabete und Zeichenketten.- 6.2 Der Algorithmus von Knuth, Morris und Pratt.- 6.3 Der Algorithmus von Boyer und Moore.- 6.4 Tries für Texte.- 6.5 Interludium: Datenkompression.- 6.6 Übungsaufgaben.- 7 Arithmetik.- 7.1 Euklidischer Algorithmus.- 7.2 Modulare Arithmetik.- 7.3 Primzahlen.- 7.4 Interludium: Kryptographie.- 7.5 Die schnelle Fouriertransformation.- 7.6 Multiplikation ganzer Zahlen.- 7.7 Optimale Klammerung von Matrizenprodukten.- 7.8 Matrizenmultiplikation.- 7.9 Übungsaufgaben.- 8 Schwierige Probleme.- 8.1 Unentscheidbarkeit.- 8.2 NP-Vollständigkeit.- 8.3 Approximative Algorithmen.- 8.4 Übungsaufgaben.- A Literaturhinweise.- A.1 Lehrbücher zur Algorithmik.- A.2 Lehrbücher zu angrenzendenThemen.- A.3 Originalarbeiten.- B Gofer-Skripten.- B.1 Berechnung von Fibonacci Zahlen.- C Index.
Jeder Informatik Student benötigt Grundkenntnisse im Bereich Algorithmen. Diese Einführung wendet sich an alle Leser, die sich mit Entwurf und
der Analyse effizienter Algorithmen näher beschäftigen wollen.
An Hand alltäglicher Probleme aus der Informatik werden dem Leser sowohl
die gängigen Algorithmen zu deren Lösung als auch die dahinter
steckenden, allgemein anwendbaren Entwurfsmethoden präsentiert.
Autorentext
Dr. Volker Heun ist Wiss. Assistent am "Lehrstuhl für Effiziente Algorithmen" der Fakultät für Informatik, TU München.
Klappentext
Diese Einführung wendet sich an alle Leser, die sich mit Entwurf und der Analyse effizienter Algorithmen näher beschäftigen wollen. An Hand alltäglicher Probleme aus der Informatik werden sowohl die gängigen Algorithmen zu deren Lösung als auch die dahinter steckenden, allgemein anwendbaren Entwurfsmethoden präsentiert und die grundlegenden Techniken zur Analyse von Algorithmen vorgestellt.
Inhalt
1 Einleitung und Grundlagen.- 1.1 Ziele.- 1.2 Einführendes Beispiel: Berechnung der Fibonacci-Zahlen.- 1.3 Grundlagen.- 1.4 Übungsaufgaben.- 2 Sortieren.- 2.1 Einfache Sortieralgorithmen.- 2.2 Mergesort.- 2.3 Heapsort.- 2.4 Quicksort.- 2.5 Interludium: Divide-and-Conquer-Algorithmen.- 2.6 Eine untere Schranke für das Sortieren.- 2.7 Bucketsort.- 2.8 Übungsaufgaben.- 3 Selektieren.- 3.1 Quickselect.- 3.2 Ein linearer Selektionsalgorithmus.- 3.3 Der Spinnen-Algorithmus.- 3.4 Eine untere Schranke.- 3.5 Ein randomisierter Median-Algorithmus.- 3.6 Neuere Ergebnisse.- 3.7 Übungsaufgaben.- 4 Suchen.- 4.1 Wörterbücher.- 4.2 Ausnutzen von Sortierung.- 4.3 Hashing.- 4.4 Binäre Suchbäume.- 4.5 AVL-Bäume.- 4.6 (a, b)-Bäume.- 4.7 Weitere Varianten von Suchbäumen.- 4.8 Tries.- 4.9 Übungsaufgaben.- 5 Graphen.- 5.1 Grundlagen der Graphentheorie.- 5.2 Traversieren von Graphen.- 5.3 Zusammenhang von Graphen.- 5.4 Kürzeste Wege.- 5.5 Interludium: Fibonacci-Heaps.- 5.6 Minimale Spannbäume.- 5.7 Interludium: Union-Find-Datenstrukturen.- 5.8 Übungsaufgaben.- 6 Texte.- 6.1 Alphabete und Zeichenketten.- 6.2 Der Algorithmus von Knuth, Morris und Pratt.- 6.3 Der Algorithmus von Boyer und Moore.- 6.4 Tries für Texte.- 6.5 Interludium: Datenkompression.- 6.6 Übungsaufgaben.- 7 Arithmetik.- 7.1 Euklidischer Algorithmus.- 7.2 Modulare Arithmetik.- 7.3 Primzahlen.- 7.4 Interludium: Kryptographie.- 7.5 Die schnelle Fouriertransformation.- 7.6 Multiplikation ganzer Zahlen.- 7.7 Optimale Klammerung von Matrizenprodukten.- 7.8 Matrizenmultiplikation.- 7.9 Übungsaufgaben.- 8 Schwierige Probleme.- 8.1 Unentscheidbarkeit.- 8.2 NP-Vollständigkeit.- 8.3 Approximative Algorithmen.- 8.4 Übungsaufgaben.- A Literaturhinweise.- A.1 Lehrbücher zur Algorithmik.- A.2 Lehrbücher zu angrenzendenThemen.- A.3 Originalarbeiten.- B Gofer-Skripten.- B.1 Berechnung von Fibonacci Zahlen.- C Index.
Titel
Grundlegende Algorithmen
Untertitel
Einführung in den Entwurf und die Analyse effizienter Algorithmen
Autor
EAN
9783322968371
Format
E-Book (pdf)
Hersteller
Genre
Veröffentlichung
09.03.2013
Digitaler Kopierschutz
Wasserzeichen
Anzahl Seiten
346
Auflage
2000
Lesemotiv
Unerwartete Verzögerung
Ups, ein Fehler ist aufgetreten. Bitte versuchen Sie es später noch einmal.