Algorithmen und Datenstrukturen: Die Grundwerkzeuge by Martin Dietzfelbinger, Kurt Mehlhorn, Peter Sanders

By Martin Dietzfelbinger, Kurt Mehlhorn, Peter Sanders

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 agency 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 hear, 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 set of rules Engineering, Speicherhierarchien, Algorithmenbibliotheken und zertifizierenden Algorithmen. Die Algorithmen werden zunächst mit Hilfe von Bildern, textual content und Pseudocode erläutert; dann werden information zu effizienten Implementierungen gegeben, auch in Bezug auf konkrete Sprachen wie C++ und Java.

Show description

Read Online or Download Algorithmen und Datenstrukturen: Die Grundwerkzeuge PDF

Similar data modeling & design books

Crystal Reports 2008 The Complete Reference

Your One-Stop advisor to company Reporting with Crystal experiences 2008Transform disconnected company facts into compelling, interactive enterprise intelligence utilizing all the strong instruments to be had in Crystal reviews 2008. via unique motives, real-world examples, and professional recommendation, this accomplished advisor exhibits you the way to create, continue, and distribute dynamic, visually attractive firm database experiences.

Advanced Computational Methods in Heat Transfer IX

Warmth move subject matters are often of a truly advanced nature. frequently assorted mechanisms like warmth conduction, convection, thermal radiation, and non-linear phenomena, akin to temperature-dependent thermophysical houses, and part adjustments take place at the same time. New advancements in numerical resolution equipment of partial differential equations and entry to high-speed, effective and inexpensive pcs have ended in dramatic advances in the course of fresh years.

Privacy in Statistical Databases: UNESCO Chair in Data Privacy International Conference, PSD 2010 Corfu, Greece, September 22-24, 2010 Proceedings

This ebook constitutes the court cases of the foreign convention on privateness in Statistical Databases held in Corfu, Greece, in September 2010.

Applications

The instruction manual at the Economics of Giving, Reciprocity and Altruism presents a entire set of experiences of literature at the economics of nonmarket voluntary transfers. the principles of the sector are reviewed first, with a chain of chapters that current the difficult center of the theoretical and empirical analyses of giving, reciprocity and altruism in economics, interpreting their family with the viewpoints of ethical philosophy, psychology, sociobiology, sociology and monetary anthropology.

Extra resources for Algorithmen und Datenstrukturen: Die Grundwerkzeuge

Sample text

Ebenso soll das Wort „asymptotisch“ in „asymptotische Analyse“ hervorheben, dass es um das Verhalten für große n geht. Weshalb interessieren wir uns nur für Wachstumsordnungen und das Verhalten für große Eingabegrößen n? Nun, man entwirft effiziente Algorithmen meistens zu dem Zweck, große Instanzen bearbeiten und lösen zu können. Wenn die Rechenzeit eines Algorithmus A eine kleinere Wachstumsordnung hat als die eines anderen Algorithmus B, wird für große n Algorithmus A überlegen sein. Auch die Tatsache, dass unser Maschinenmodell eine Abstraktion ist und reale Rechenzeiten nur bis auf einen (maschinenabhängigen) konstanten Faktor vorhersagen kann, legt es nahe, keinen Unterschied zwischen Algorithmen zu machen, deren Rechenzeiten dieselbe Wachstumsordnung haben.

Wir können aber das Programm wie folgt erweitern: wenn es erklärt, dass G bipartit ist, liefert es auch eine 2-Färbung der Knoten des Graphen; wenn es erklärt, dass G nicht bipartit ist, liefert es auch einen Kreis ungerader Länge in G. Für das so erweiterte Programm kann die Nachbedingung leicht überprüft werden. Im ersten Fall testen wir jede Kante darauf, ob ihre Endpunkte verschiedenfarbig sind. Im zweiten Fall testen wir, ob die ausgegebene Knotenfolge, etwa v0 , v1 , . . , vk , tatsächlich einen Kreis in G mit ungerader Länge bildet.

Wenn n ungerade ist, verringern wir n um 1 und multiplizieren r mit p. Diese Operationen stellen die Invariante wieder her. ) Wenn n gerade ist, halbieren wir n und quadrieren p; auch in diesem Fall ist die Invariante wieder hergestellt. Wenn die Schleife endet, gilt pn r = an0 wegen der Invarianten und n = 0 wegen der Schleifenendebedingung. Daraus folgt r = an0 , und wir haben die Nachbedingung bewiesen. Der Algorithmus in Abb. 4 und viele andere Algorithmen in diesem Buch haben eine recht einfache Struktur.

Download PDF sample

Rated 4.96 of 5 – based on 27 votes