Skip to main content

2014 | Buch

Algorithmen und Datenstrukturen

Die Grundwerkzeuge

verfasst von: Martin Dietzfelbinger, Kurt Mehlhorn, Peter Sanders

Verlag: Springer Berlin Heidelberg

Buchreihe : eXamen.press

insite
SUCHEN

Über dieses Buch

Algorithmen bilden das Herzstück jeder nichttrivialen Anwendung von Computern, und die Algorithmik ist ein modernes und aktives Gebiet der Informatik. Daher sollte sich jede Informatikerin und jeder Informatiker mit den algorithmischen Grundwerkzeugen auskennen. Dies sind Strukturen zur effizienten Organisation von Daten, häufig benutzte Algorithmen und Standardtechniken für das Modellieren, Verstehen und Lösen algorithmischer Probleme. Dieses Buch ist eine straff gehaltene Einführung in die Welt dieser Grundwerkzeuge, gerichtet an Studierende und im Beruf stehende Experten, die mit dem Programmieren und mit den Grundelementen der Sprache der Mathematik vertraut sind. Die einzelnen Kapitel behandeln Arrays und verkettete Listen, Hashtabellen und assoziative Arrays, Sortieren und Auswählen, Prioritätswarteschlangen, sortierte Folgen, Darstellung von Graphen, Graphdurchläufe, kürzeste Wege, minimale Spannbäume und Optimierung. Die Algorithmen werden auf moderne Weise präsentiert, mit explizit angegebenen Invarianten, und mit Kommentaren zu neueren Entwicklungen wie Algorithm Engineering, Speicherhierarchien, Algorithmenbibliotheken und zertifizierenden Algorithmen. Die Algorithmen werden zunächst mit Hilfe von Bildern, Text und Pseudocode erläutert; dann werden Details zu effizienten Implementierungen gegeben, auch in Bezug auf konkrete Sprachen wie C++ und Java.

Inhaltsverzeichnis

Frontmatter
1. Vorspeise: Arithmetik für ganze Zahlen
Zusammenfassung
Eine Vorspeise soll zu Beginn eines Essens den Appetit anregen. Genau dies ist der Zweck dieses Kapitels: Um das Interesse der Leserin für algorithmische Techniken zu wecken, wollen wir ein überraschenden Ergebnis vorstellen: Die Schulmethode für die Multiplikation von natürlichen Zahlen ist nicht der beste Multiplikationsalgorithmus. Für die Multiplikation sehr großer Zahlen, d. h. solcher mit Tausenden oder sogar Millionen von Ziffern, gibt es viel schnellere Methoden. Eine solche Methode wird die Leserin in diesem Kapitel kennenlernen.
Martin Dietzfelbinger, Kurt Mehlhorn, Peter Sanders
2. Einleitung
Zusammenfassung
Wer Bildhauer werden will, muss eine Reihe von Grundtechniken erlernen: woher man die geeigneten Steine bezieht, wie man sie bewegt, wie man mit dem Meißel arbeitet, wie man ein Gerüst aufbaut,… . Wer die Grundtechniken beherrscht, ist noch lange kein berühmter Künstler, aber selbst jemand mit außergewöhnlichem Talent wird kaum ein erfolgreicher Künstler werden, wenn er die Grundtechniken nicht kennt. Natürlich muss er nicht alle beherrschen, bevor er die erste Skulptur gestaltet. Aber er muss stets bereit sein, zu den Grundtechniken zurückzukehren, um sie immer besser beherrschen zu lernen.
Martin Dietzfelbinger, Kurt Mehlhorn, Peter Sanders
3. Darstellung von Folgen durch Arrays und verkettete Listen
Zusammenfassung
Vielleicht die ältesten Datenstrukturen der Welt waren die Keilschrifttafeln, die vor mehr als 5000 Jahren von den Aufsehern in sumerischen Tempeln benutzt wurden. Diese Aufseher führten Listen mit Waren, ihren Mengen, ihren Besitzern und Käufern. Das Bild links zeigt eine solche Tafel. Es handelt sich dabei möglicherweise um das erste Vorkommen geschriebener Sprache. Die Operationen, die auf solchen Listen durchgeführt wurden und werden, sind dieselben geblieben: Einträge werden hinzugefügt, sie werden für später gespeichert, es wird nach Einträgen gesucht und sie werden verändert, die ganze Liste wird durchmustert, um eine Zusammenfassung zu erstellen, usw.
Martin Dietzfelbinger, Kurt Mehlhorn, Peter Sanders
4. Hashtabellen und assoziative Arrays
Zusammenfassung
Wenn eine Benutzerin ein Buch aus der Zentralbibliothek des KIT (Karlsruher Institut für Technologie) ausleihen möchte, muss sie es vorbestellen. Ein Bibliotheksmitarbeiter holt das Buch aus dem Magazin und stellt es in einen Raum mit 100 Regalfächern. Die Benutzerin findet dann ihr Buch in einem Regalfach, dessen Nummer den beiden letzten Ziffern der Nummer auf ihrem Benutzerausweis entspricht. Man kann sich fragen, weshalb die beiden letzten Ziffern und nicht die beiden ersten verwendet werden. Wahrscheinlich führt diese Wahl dazu, dass die Bücher gleichmäßiger auf die Fächer verteilt werden. Wieso? Die Bibliotheksausweise werden in der Reihenfolge der Anmeldung fortlaufend nummeriert. Daher werden Studierende, die gleichzeitig immatrikuliert sind, fast die gleichen führenden Ziffern in ihrer Benutzernummer haben, und nur einige wenige Regalfächer würden benutzt werden.
Martin Dietzfelbinger, Kurt Mehlhorn, Peter Sanders
5. Sortieren und Auswählen
Zusammenfassung
In Telefonbüchern sind die Einträge nach Nachnamen alphabetisch geordnet. Wieso eigentlich? Weil man einen geordneten Index schnell durchsuchen kann. Sogar im Telefonbuch einer riesengroßen Stadt findet man einen Namen normalerweise innerhalb von Sekunden. Wären die Einträge unsortiert, würde man gar nicht erst anfangen, nach einem Namen zu suchen. Zunächst einmal wird in diesem Kapitel dargestellt, wie man eine ungeordnete Menge von Einträgen in eine geordnete Reihenfolge bringt, d. h., wie man die Menge sortiert. Dann kann man einen Eintrag schnell finden. Sortieren hat aber noch viele andere Anwendungen.
Martin Dietzfelbinger, Kurt Mehlhorn, Peter Sanders
6. Prioritätswarteschlangen
Zusammenfassung
Die Firma KnM vermarktet maßgeschneiderte Kleidung von höchster Qualität. Vorgänge wie Marketing, Maßnehmen, Versand usw. liegen bei der Firma, aber die tatsächliche Herstellung überlässt sie unabhängigen Schneidereien. Die Firma erhält 20% des Erlöses. Als sie im 19. Jahrhundert gegründet wurde, gab es fünf Vertragsschneidereien. Heute beherrscht sie 15% des Weltmarkts, und weltweit arbeiten Tausende von Schneidereien für KnM.
Martin Dietzfelbinger, Kurt Mehlhorn, Peter Sanders
7. Sortierte Folgen
Zusammenfassung
Wir alle verbringen einen beträchtlichen Teil unserer Zeit mit Suchen. Ebenso ist es mit Computern: Sie schlagen Telefonnummern nach, Kontostände, Flugreservierungen, Rechnungen und Zahlungen, …. In vielen Anwendungen soll in dynamischen, d. h. veränderlichen, Datenmengen gesucht werden. Neue Buchungen werden in Reservierungssysteme eingegeben, Reservierungen werden geändert oder storniert, und Buchungen verwandeln sich in tatsächlich durchgeführte Flüge. Eine Lösung für dieses Problem haben wir schon gesehen, nämlich Hashing. Es ist aber oft wünschenswert, dass die veränderliche Datenmenge stets sortiert bleibt.
Martin Dietzfelbinger, Kurt Mehlhorn, Peter Sanders
8. Darstellung von Graphen
Zusammenfassung
Wissenschaftliche Resultate sind zum größten Teil als Artikel in Zeitschriften und Konferenzbänden verfügbar, oder auch in verschiedenen Quellen im World Wide Web. Diese Artikel sind nicht in sich abgeschlossen, sondern zitieren früher erschienene Artikel mit verwandtem Inhalt. Wenn man heute einen im Jahr 1975 erschienenen Artikel liest, der ein interessantes Teilresultat enthält, fragt man sich natürlich, was der aktuelle Stand der Technik ist. Insbesondere würde man gerne wissen, in welchen neueren Artikeln dieser alte zitiert wird. Projekte wie „Google Scholar“ stellen diese Funktionalität zur Verfügung, indem sie die Literaturangaben in Artikeln analysieren und eine Datenbank aufbauen, mit deren Hilfe man zu einem gegebenen Artikel die neueren Artikel finden kann, von denen er zitiert wird.
Martin Dietzfelbinger, Kurt Mehlhorn, Peter Sanders
9. Graphdurchläufe
Zusammenfassung
Nehmen Sie an, Sie arbeiten in der Verkehrsplanungsabteilung einer Stadt mit einem hübschen mittelalterlichen Kern. Eine unheilige Allianz von Einzelhändlern, die sich mehr Parkraum am Straßenrand wünschen, und der grünen Partei, die am liebsten den gesamten Autoverkehr aus der Stadt vergraulen möchte, hat erreicht, dass fast alle Straßen zu Einbahnstraßen erklärt werden sollen. Sie möchten das Allerschlimmste verhüten und prüfen, ob der vorgeschlagene Plan wenigstens die Minimalanforderung erfüllt, dass man von jedem Punkt in der Stadt zu jedem anderen fahren kann.
Martin Dietzfelbinger, Kurt Mehlhorn, Peter Sanders
10. Kürzeste Wege
Zusammenfassung
Das Problem, in einem Netzwerk den kürzesten, schnellsten oder billigsten Weg zu finden, ist allgegenwärtig. Jeder von uns löst es jeden Tag. Wenn man an Ort s ist und zu einem Ort t gelangen möchte, fragt man nach dem Weg, der einen am schnellsten von s nach t bringt. Die Feuerwehr möchte vielleicht die schnellsten Wege von der Feuerwehrzentrale s zu allen Stellen t in der Stadt finden – dies führt zum Problem „mit einem Startpunkt“ (engl.: single source). Manchmal möchte man auch eine vollständige Tabelle aller Distanzen von jedem Ort zu jedem anderen haben – dies ist das Problem „kürzeste Wege für alle (Knoten-)Paare“ (engl.: all pairs). Zum Beispiel findet sich in einem Straßenatlas üblicherweise eine Tabelle mit den Distanzen zwischen allen größeren Städten.
Martin Dietzfelbinger, Kurt Mehlhorn, Peter Sanders
11. Minimale Spannbäume
Zusammenfassung
Die Bewohner des Atolls namens Taka-Tuka-Land in der Südsee bitten Sie um Hilfe. Sie möchten ihre Inseln durch Fährlinien verbinden. Weil das Geld knapp ist, sollen die Gesamtkosten für alle Verbindungen möglichst klein sein. Es muss möglich sein, von jeder Insel zu jeder anderen zu gelangen, aber direkte Verbindungen werden nicht verlangt. Sie erhalten eine Liste der möglichen Verbindungen mit den zugehörigen geschätzten Kosten.
Martin Dietzfelbinger, Kurt Mehlhorn, Peter Sanders
12. Generische Ansätze für Optimierungsprobleme
Zusammenfassung
Ein Schmuggler in der wilden Bergregion von Profitanien hat in seinem Keller n Gegenstände liegen, die er über die Berge ins Nachbarland schaffen könnte. Wenn er Gegenstand i dort verkauft, macht er Profit pi. Allerdings besagt eine Vorschrift der Schmugglergewerkschaft, dass der Rucksack, den er über die Grenze trägt, keinesfalls mehr als M Kilogramm wiegen darf. Nehmen wir an, Gegenstand i wiegt genau wi Kilogramm.
Martin Dietzfelbinger, Kurt Mehlhorn, Peter Sanders
Backmatter
Metadaten
Titel
Algorithmen und Datenstrukturen
verfasst von
Martin Dietzfelbinger
Kurt Mehlhorn
Peter Sanders
Copyright-Jahr
2014
Verlag
Springer Berlin Heidelberg
Electronic ISBN
978-3-642-05472-3
Print ISBN
978-3-642-05471-6
DOI
https://doi.org/10.1007/978-3-642-05472-3