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 organization 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 pay attention, 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 info zu effizienten Implementierungen gegeben, auch in Bezug auf konkrete Sprachen wie C++ und Java.

Show description

Read or Download Algorithmen und Datenstrukturen: Die Grundwerkzeuge PDF

Best data modeling & design books

Medical Imaging and Augmented Reality Second International Workshop

This scholarly set of well-harmonized volumes offers crucial and whole insurance of the interesting and evolving topic of clinical imaging structures. top specialists at the foreign scene take on the newest state of the art concepts and applied sciences in an in-depth yet eminently transparent and readable strategy.

Metaheuristics

Metaheuristics convey fascinating homes like simplicity, effortless parallelizability, and prepared applicability to sorts of optimization difficulties. After a entire advent to the sector, the contributed chapters during this publication contain reasons of the most metaheuristics suggestions, together with simulated annealing, tabu seek, evolutionary algorithms, synthetic ants, and particle swarms, by way of chapters that exhibit their functions to difficulties equivalent to multiobjective optimization, logistics, automobile routing, and air site visitors administration.

Extra resources for Algorithmen und Datenstrukturen: Die Grundwerkzeuge

Sample text

3 Das Sprungziel k kann, falls nötig, auch als Inhalt S[R j ] einer Speicherzelle angegeben sein. 30 2 Einleitung Ein solches Programm wird auf einer gegebenen Eingabe Schritt für Schritt ausgeführt. Die Eingabe steht zu Beginn in den Speicherzellen S[1] bis S[R1 ]; die erste ausgeführte Programmzeile ist Zeile 1. Mit Ausnahme der Sprungbefehle JZ und J folgt auf die Ausführung einer Programmzeile stets die Ausführung der darauffolgenden Programmzeile. Die Ausführung des Programms endet, wenn eine Zeile ausgeführt werden soll, deren Nummer außerhalb des Bereichs 1..

Der erste Algorithmus multipliziert zwei n-Bit-Zahlen mit O(n log n log log n) Bitoperationen; er kann auch auf einer Turingmaschine mit der entsprechenden Anzahl von Schritten ablaufen. 2 vorgestellt wird. In diesem Modell können ganze Zahlen mit log n Bits in konstanter Zeit multipliziert werden. Der erste Algorithmus wurde 2007 und 2009 von Fürer [76] und von De, Kurur, Saha und Saptharishi [51] ∗ auf O (n log n)2c log n Bitoperationen verbessert. Dabei ist log∗ n die kleinste Zahl k ≥ 0 mit der Eigenschaft, dass log(log(.

Dabei steht „1“ für die konstante Funktion n → 1, die überall den Wert 1 hat. Damit liegt eine Funktion f (n) in o(1), wenn f (n) ≤ c · 1 für jedes positive c gilt, wenn nur n genügend groß ist, d. , wenn f (n) für wachsendes n gegen Null strebt. Allgemein ist O( f (n)) die Menge all der Funktionen, die „nicht schneller wachsen als“ f (n); ähnlich ist Ω( f (n)) die Menge der Funktionen, die „mindestens so schnell wachsen wie“ f (n). 585 , wohingegen die asymptotische Rechenzeit der Schulmethode in Ω n2 liegt.

Download PDF sample

Rated 5.00 of 5 – based on 11 votes

About the Author

admin