Download e-book for iPad: Algorithmen und Datenstrukturen: Die Grundwerkzeuge by Martin Dietzfelbinger, Kurt Mehlhorn, Peter Sanders

By Martin Dietzfelbinger, Kurt Mehlhorn, Peter Sanders

ISBN-10: 3642054714

ISBN-13: 9783642054716

ISBN-10: 3642054722

ISBN-13: 9783642054723

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 information 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

Similar data modeling & design books

New PDF release: The Data Model Resource Book, Vol. 2: A Library of Data

A short and trustworthy approach to construct confirmed databases for center enterprise functionsIndustry specialists raved concerning the facts version source e-book whilst it was once first released in March 1997 since it supplied an easy, reasonably priced approach to layout databases for middle enterprise capabilities. Len Silverston has now revised and up-to-date the highly winning First variation, whereas including a better half quantity to maintain extra particular specifications of alternative companies.

Get Linear Programming: Algorithms and applications PDF

This article is predicated on a process approximately sixteen hours lectures to scholars of arithmetic, records, and/or operational examine. it's meant to introduce readers to the very wide variety of applicability of linear programming, overlaying difficulties of deal with­ ment, management, transportation and several other makes use of that are pointed out of their context.

Download e-book for iPad: Understanding Compression: Data Compression for Modern by Colt McAnlis, Aleks Haecky

So that you can allure and keep clients within the booming cellular companies industry, you wish a quick-loading app that won’t churn via their info plans. the bottom line is to compress multimedia and different facts into smaller records, yet discovering the proper procedure is hard. This witty ebook is helping you know the way information compression algorithms work—in thought and practice—so you could decide on the easiest resolution between the entire to be had compression instruments.

Extra info for Algorithmen und Datenstrukturen: Die Grundwerkzeuge

Sample text

Normalerweise kann man jeder Eingabe auf natürliche Art eine Größe zuordnen. Die Größe einer ganzen Zahl ist die Anzahl der Ziffern ihrer Binärdarstellung; die Größe einer Menge ist die Anzahl ihrer Elemente. Die Größe einer Eingabe ist immer eine natürliche Zahl. Manchmal verwendet man mehr als einen Parameter, um die Größe einer Eingabe anzugeben; beispielsweise ist es üblich, die Größe eines Graphen durch die Anzahl seiner Knoten und seiner Kanten zu charakterisieren. Diese kleine Komplikation werden wir hier zunächst außer Acht lassen.

Die Ausführung des Programms endet, wenn eine Zeile ausgeführt werden soll, deren Nummer außerhalb des Bereichs 1.. liegt. Wir legen den Zeitaufwand für die Ausführung eines Programms auf einer Eingabe auf denkbar einfache Art fest: Die Ausführung eines Maschinenbefehls dauert genau eine Zeiteinheit. Die Gesamtausführungszeit oder Rechenzeit eines Programms ist dann einfach die Gesamtzahl aller ausgeführten Befehle. Es ist wichtig, sich klarzumachen, dass die RAM eine Abstraktion ist; man darf das Modell nicht mit wirklichen Rechnern verwechseln.

3k−1 · (21 + 2)) ≤ 27 · 3k + 8 · 2k · 3k − 1 (3/2)k − 1 +2· 3/2 − 1 3−1 = 51 · 3k − 16 · 2k − 8 . Wir müssen nun nur noch diese Schranke auf alle n verallgemeinern. Dazu wählen wir das kleinste k, das n ≤ 2k + 2 erfüllt. Offensichtlich gilt k ≤ 1 + log n. Die Multiplikation von Zahlen mit n Ziffern kann nicht teurer sein als die von Zahlen mit 2k + 2 Ziffern. Daraus folgt: TK (n) ≤ 51 · 3k − 16 · 2k − 8 ≤ 153 · 3log n ≤ 153 · nlog 3 , wobei wir die Gleichung 3log n = 2(log 3)·(log n) = nlog 3 benutzt haben.

Download PDF sample

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


by Brian
4.3

Rated 4.27 of 5 – based on 7 votes