So entwerfen und analysieren Sie effiziente Algorithmen: unentbehrlich für IT-nahe Studiengänge
Dr. Volker Heun ist Professor für Bioinformatik an der Ludwig-Maximilians-Universität München.
"Die Stoffauswahl ist sehr gut! /.../auch Neuerungen enthalten /.../didaktisch hervorragend aufgebaut. Dieses Buch werde ich meinen Studenten empfehlen, wei es sich auch ideal zum Selbstudium eignet."
Prof. Dr. Silke Schlosser-Haupt, Bergische Universität Wuppertal
"Ein aktuelles Lehrbuch, das sich hervorragend als Leitfaden für eine Vorlesung eignet."
Prof. Dr. Elfriede Fehr, FU Berlin
Jeder Student IT-naher Studiengänge benötigt Grundkenntnisse im Bereich Algorithmen. Lernen Sie anhand alltäglicher Aufgabenstellungen aus der Informatik die richtigen Algorithmen einzusetzen. Sie werden auch die dahinter steckenden, allgemein anwendbaren Entwurfsmethoden sowie die grundlegenden Techniken zur Analyse verstehen und anwenden können.
Die 2. Auflage wurde erweitert. Behandelt werden Themen aus den folgenden Gebieten: Sortieren, Selektieren, Dynamische Datenstrukturen zur Suche, Graphalgorithmen, Textalgorithmen, arithmetische und zahlentheoretische Algorithmen, NP-Vollständigkeit und approximative Verfahren.
Grundlagen (Maschinenmodelle, Komplexitätsmaße) - Sortieren (Merge-Sort, Heap-Sort, Quick-Sort, Bucket-Sort) - Selektieren (lineare und randomisierte Verfahren) - Suchen (Hashing, Suchbäume) - Graphen (Traversieren, kürzeste Wege, minimale Spannbäume) - Texte (Suchen in Texten, Datenkompression) - Arithmetik (Euklidischer Algorithmus, RSA, Fouriertransformation, Matrizen) - Komplexität (Unentscheidbarkeit, NP-Vollständigkeit, Approximation)
Jeder Student IT-naher Studiengänge benötigt Grundkenntnisse im Bereich Algorithmen. Lernen Sie anhand alltäglicher Aufgabenstellungen aus der Informatik die richtigen Algorithmen einzusetzen. Sie werden auch die dahinter steckenden, allgemein anwendbaren Entwurfsmethoden sowie die grundlegenden Techniken zur Analyse verstehen und anwenden können.
Behandelt werden Themen aus den folgenden Gebieten: Sortieren, Selektieren, Dynamische Datenstrukturen zur Suche, Graphalgorithmen, Textalgorithmen, arithmetische und zahlentheoretische Algorithmen, NP-Vollständigkeit und approximative Verfahren.
"Man findet in dem Buch einen gut verständlichen Einstieg in die Welt der Algorithmen! Die zahlreichen Beispiele und praxisnahen Übungen helfen beim Verstehen entscheidend. [...] Ein sehr gelungenes Buch!"
www.postnuke.de, 09.07.2003
Grundkenntnisse im Bereich Algorithmen: Unentbehrlich für Informatik Studenten
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 $$mathcal{NP}$$-Vollständigkeit.- 8.3 Approximative Algorithmen.- 8.4 Übungsaufgaben.- A Literaturhinweise.- A.1 Lehrbücher zur Algorithmik.- A.2 Lehrbücherzu angrenzenden Themen.- A.3 Originalarbeiten.- B Gofer-Skripten.- B.1 Berechnung von Fibonacci Zahlen.- C Index.
"Man findet in dem Buch einen gut verständlichen Einstieg in die Welt der Algorithmen! Die zahlreichen Beispiele und praxisnahen Übungen helfen beim Verstehen entscheidend. [...] Ein sehr gelungenes Buch!"
www.postnuke.de, 09.07.2003
Über den Autor
Dr. Volker Heun ist Professor für Bioinformatik an der Ludwig-Maximilians-Universität München.
Inhaltsverzeichnis
Grundlagen (Maschinenmodelle, Komplexitätsmaße) - Sortieren (Merge-Sort, Heap-Sort, Quick-Sort, Bucket-Sort) - Selektieren (lineare und randomisierte Verfahren) - Suchen (Hashing, Suchbäume) - Graphen (Traversieren, kürzeste Wege, minimale Spannbäume) - Texte (Suchen in Texten, Datenkompression) - Arithmetik (Euklidischer Algorithmus, RSA, Fouriertransformation, Matrizen) - Komplexität (Unentscheidbarkeit, NP-Vollständigkeit, Approximation)
Klappentext
Jeder Student IT-naher Studiengänge benötigt Grundkenntnisse im Bereich Algorithmen. Lernen Sie anhand alltäglicher Aufgabenstellungen aus der Informatik die richtigen Algorithmen einzusetzen. Sie werden auch die dahinter steckenden, allgemein anwendbaren Entwurfsmethoden sowie die grundlegenden Techniken zur Analyse verstehen und anwenden können.
Jeder Student IT-naher Studiengänge benötigt Grundkenntnisse im Bereich Algorithmen. Lernen Sie anhand alltäglicher Aufgabenstellungen aus der Informatik die richtigen Algorithmen einzusetzen. Sie werden auch die dahinter steckenden, allgemein anwendbaren Entwurfsmethoden sowie die grundlegenden Techniken zur Analyse verstehen und anwenden können.
Die 2. Auflage wurde erweitert. Behandelt werden Themen aus den folgenden Gebieten: Sortieren, Selektieren, Dynamische Datenstrukturen zur Suche, Graphalgorithmen, Textalgorithmen, arithmetische und zahlentheoretische Algorithmen, NP-Vollständigkeit und approximative Verfahren.
