Lehrbuch Grundlegende AlgorithmenTextbook Fundamental Algorithms
- Titel:
- Grundlegende Algorithmen —
Einführung in den Entwurf und die Analyse effizienter Algorithmen - Autor:
- Volker Heun
- Verlag:
- Vieweg Verlag
- Auflage:
- 1. Auflage, Oktober 2000
2. Auflage, Mai 2003 - ISBN:
- 1. Auflage: 978-3-528-03140-4 (3-528-03140-9)
2. Auflage: 978-3-528-13140-1 (3-528-13140-3) - Überblick:
Das Entwerfen und Analysieren von effizienten Algorithmen ist eine der Hauptaufgaben 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 eingehen. 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.- Inhalt:
-
Maschinenmodelle und Komplexitätsmaße, Sortieralgorithmen,
Selektionsalgorithmen, Suchalgorithmen, Graphalgorithmen,
Textalgorithmen und Datenkompression, artithmetische Algorithmen und
Public-Key-Kryptographie, Berechenbarkeit,
NP-Vollständigkeit und approximative Algorithmen.
Das Inhaltsverzeichnis ist verfügbar: - Corrigenda:
-
Eine Liste mit bekannten Fehlern, Korrekturen und Ergänzungen
ist verfügbar:
- erste Auflage [2002-12-19],
- zweite Auflage [2009-08-25].
- Aufgaben:
- Zu den Übungsaufgaben des Buches werden nach und nach Lösungen, Lösungshinweise und Bemerkungen zur Verfügung gestellt.