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

Best data modeling & design books

The Data Model Resource Book, Vol. 2: A Library of Data Models by Industry Types

A brief and trustworthy technique to construct confirmed databases for center enterprise functionsIndustry specialists raved concerning the information version source e-book while it used to be first released in March 1997 since it supplied an easy, least expensive method to layout databases for middle company services. Len Silverston has now revised and up-to-date the highly winning First version, whereas including a significant other quantity to maintain extra particular necessities of other companies.

Coloured Petri Nets: Basic Concepts, Analysis Methods and Practical Use

This publication offers a coherent description of the theoretical and useful aspects
of colored Petri Nets (CP-nets or CPN). It exhibits how CP-nets were developed
- from being a promising theoretical version to being a full-fledged language
for the layout, specification, simulation, validation and implementation of
large software program platforms (and different structures during which humans and/or computers
communicate via a few kind of formal rules). The book
contains the formal definition of CP-nets and the mathematical concept behind
their research equipment. despite the fact that, it's been the purpose to jot down the ebook in
such a manner that it additionally turns into beautiful to readers who're extra in
applications than the underlying arithmetic. which means a wide a part of the
book is written in a method that's toward an engineering textbook (or a users'
manual) than it really is to a regular textbook in theoretical computing device technology. The book
consists of 3 separate volumes.

The first quantity defines the internet version (i. e. , hierarchical CP-nets) and the
basic ideas (e. g. , different behavioural homes corresponding to deadlocks, fairness
and domestic markings). It offers an in depth presentation of many smaIl examples
and a short evaluation of a few commercial functions. It introduces the formal
analysis tools. FinaIly, it includes a description of a collection of CPN tools
which help the sensible use of CP-nets. lots of the fabric during this quantity is
application orientated. the aim of the amount is to educate the reader how to
construct CPN types and the way to examine those via simulation.

The moment quantity encompasses a specified presentation of the speculation at the back of the
formal research equipment - particularly prevalence graphs with equivalence
classes and place/transition invariants. It additionally describes how those research methods
are supported via computing device instruments. elements of this quantity are really theoretical
while different components are program orientated. the aim of the amount is to teach
the reader how you can use the formal research equipment. this can now not unavoidably require
a deep knowing of the underlying mathematical concept (although such
knowledge will in fact be a help).

The 3rd quantity incorporates a distinct description of a range of industrial
applications. the aim is to rfile crucial rules and experiences
from the initiatives - in a fashion that's priceless for readers who don't yet
have own event with the development and research of huge CPN diagrams.
Another objective is to illustrate the feasibility of utilizing CP-nets and the
CPN instruments for such tasks.

Parallel Computational Fluid Dynamics 1995. Implementations and Results Using Parallel Computers

Parallel Computational Fluid Dynamics(CFD) is an the world over recognized fast-growing box. in view that 1989, the variety of members attending Parallel CFD meetings has doubled. so that it will hold tune of present international advancements, the Parallel CFD convention every year brings scientists jointly to debate and document effects at the usage of parallel computing as a pragmatic computational software for fixing advanced fluid dynamic difficulties.

Hadoop: The Definitive Guide, 2nd Edition

Notice how Apache Hadoop can unharness the ability of your facts. This complete source indicates you the way to construct and continue trustworthy, scalable, disbursed structures with the Hadoop framework - an open resource implementation of MapReduce, the set of rules on which Google outfitted its empire. Programmers will locate info for examining datasets of any dimension, and directors will how to organize and run Hadoop clusters.

Extra resources for Algorithmen und Datenstrukturen: Die Grundwerkzeuge

Example text

Ein solches Programm ist dabei eine Liste von Maschinenbefehlen, durchnummeriert von 1 bis zu einer Zahl . Die Einträge der Liste heißen Zeilen des Programms. Das Programm steht in einem Programmspeicher. Unsere RAM kann folgende Maschinenbefehle ausführen: • Ri := S[R j ] lädt den Inhalt der Speicherzelle, deren Index in Register R j steht, in Register Ri . • S[R j ] := Ri schreibt den Inhalt von Register Ri in die Speicherzelle, deren Index in Register R j steht. • Ri := R j Rh führt auf den Inhalten von Registern R j und Rh eine binäre Operation aus und speichert das Ergebnis in Register Ri .

Wenn der rekursive Schritt Multiplikationen von Zahlen der Länge n/k benötigt, wächst die Rechenzeit des resultierenden Algorithmus wie nlogk . Mit diesem Ansatz reduzierten Toom [211] und Cook [48] die Rechenzeit13 auf O n1+ε für beliebige positive ε . Lange Jahre waren die von Schönhage und Strassen [186] und Schönhage [185] angegebenen Algorithmen die asymptotisch effizientesten bekannten Verfahren. 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.

Die Größe der Eingabe I wird mit size(I) bezeichnet, und mit In die Menge aller Eingaben der Größe n, für n ∈ N. 1 Asymptotische Notation 25 maximalen, minimalen und mittleren Ausführungszeiten:2 schlechtester Fall (worst case): T (n) = max {time(I) : I ∈ In } bester Fall (best case): T (n) = min {time(I) : I ∈ In } 1 mittlerer Fall (average case): T (n) = ∑ time(I) . |In | I∈I n Die interessanteste Größe ist dabei die Ausführungszeit im schlechtesten Fall, weil sie die umfassendste Garantie für das Verhalten des Algorithmus darstellt.

Download PDF sample

Rated 4.84 of 5 – based on 26 votes