By Thomas Ottmann

In diesem Buch werden alle Themen ausführlich behandelt, die üblicherweise den Kern des Curriculums zur Standardvorlesung ''Algorithmen und Datenstrukturen'' bilden. Daher hat sich dieses Buch einen festen Platz im Vorlesungsbetrieb erobert. Das Themenspektrum reicht von Algorithmen zum Suchen und Sortieren über Adreßberechnungsmethoden und Listenstrukturen (Bäume aller paintings) bis zu Geometrischen Algorithmen und Graphenalgorithmen. Diese Themen werden präzise, aber nicht allzu formal behandelt. Dabei geht es sowohl um den Entwurf effizienter Algorithmen und Datenstrukturen als auch um die examine ihres Verhaltens mittels mathematischer Methoden. Übungsaufgaben dienen zur Vertiefung des dargestellten Stoffs.

Show description

Read or Download Algorithmen und Datenstrukturen PDF

Similar algorithms and data structures books

Combinatorial and Algorithmic Aspects of Networking: First Workshop on Combinatorial and Algorithmic Aspects of Networking, CAAN 2004, Banff, Alberta, Canada, August 5-7, 2004, Revised Selected Papers

This booklet constitutes the refereed lawsuits of the 1st workshop on Combinatorial and Algorithmic features of Networking, held in Banff, Alberta, Canada in August 2004. The 12 revised complete papers including invited papers provided have been rigorously reviewed and chosen for inclusion within the booklet.

Manual on Presentation of Data and Control Chart Analysis, 7th Edition

This entire guide assists within the improvement of supportive information and research while getting ready ordinary attempt tools, requisites, and practices. It presents the newest information about statistical and quality controls tools and their purposes. this is often the seventh revision of this renowned handbook first released in 1933 as STP 15 and is a superb educating and reference instrument for facts research and enhances paintings wanted for ISO quality controls necessities.

Extra resources for Algorithmen und Datenstrukturen

Example text

Darüberhinaus wird stillschweigend vorausgesetzt, daß es eine Operation zur Initialisierung des leeren Wörterbuches gibt. 6 Ausblick auf weitere Datenstrukturen 41 Regel ganzzahligen Schlüssel identifizierbar sind. Es ist üblich, die Such-, Einfüge- und Entferne-Operation nur vom jeweiligen Schlüssel abhängig zu machen, so daß man zur weiteren Vereinfachung häufig annimmt, daß ein Wörterbuch eine Menge S ganzzahliger Schlüssel ist, auf der folgende Operationen ausgeführt werden. Suchen(x): Liefert den Wert true genau dann, wenn x in S vorkommt, und false sonst.

Man sieht in dieser Formulierung, daß auch einige weitere Operationen für eine Punktmenge M (nicht nur „nächster Nachbar“ und „Distanz zweier Punkte“) ausführbar sein müssen: Es muß möglich sein, festzustellen, ob M = 0/ ist oder ob M nur einen Punkt enthält; ferner muß es möglich sein, einen Punkt aus M auszuwählen und aus M zu entfernen. Es werden jedoch keinerlei implementationsabhängige Details für Punktmengen benötigt. Soll der Algorithmus in einer konkreten Programmiersprache implementiert werden, ist es nötig, den ADT Punktmenge durch Angabe von Datenstrukturen für die Objektmengen und Algorithmen für die benutzten Operationen zu realisieren.

Key ist. Die hier angegebene Realisierung des Suchverfahrens für perfekte Skip-Listen kann jedoch unverändert auch für die später erklärten randomisierten Skip-Listen benutzt werden. Aus der Beschränkung für die Höhe einer perfekten Skip-Liste folgt natürlich sofort, daß das Suchen stets in O(log N ) Schritten ausgeführt werden kann. Einfügen oder Entfernen eines Schlüssels x würde jedoch eine vollständige Reorganisation der perfekten Skip-Liste erfordern und daher Ω(N ) Schritte benötigen. 13 (b) ein neues kleinstes Element mit Schlüssel 1 einfügen, so müssen sämtliche bisherigen Elemente ihre Höhen ändern, um wieder eine perfekte Skip-Liste zu ergeben.

Download PDF sample

Rated 4.26 of 5 – based on 31 votes