"Datenstrukturen und Algorithmen 001.ps.gz" - читать интересную книгу автора

Datenstrukturen und Algorithmen

Sommersemester 1998 Dr. Rudolf Fleischer

Universit"at Trier

und Max-Planck-Institut

f"ur Informatik

Saarbr"ucken

5. August 1998

2 Vorwort Ich habe die Vorlesung Informatik II (Datenstrukturen und Algorithmen) im Sommersemester 1998 an der Universit"at Trier im Rahmen einer Vertretungsprofessur gelesen. Das vorliegende Skript ist eng angelehnt an das Skript einer gleichnamigen Vorlesung, die im Wintersemester 1997/98 an der Universit"at Saarbr"ucken zusammen mit Prof. Dr. Kurt Mehlhorn gelesen hatte. Die Reihenfolge, in der der Stoff pr"asentiert wird, entspricht nicht immer genau dem Ablauf der Vorlesung. Ausserdem enth"alt das Skript sicher auch noch einige kleinere Druckfehler, die mir bei der "Uberarbeitung entgangen sind.

Trier, den 5. August 1998 Dr. Rudolf Fleischer

Inhaltsverzeichnis 1 Einf"uhrung 4

1.1 Lernziele . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 1.2 Literatur . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 1.3 Asymptotik . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 1.4 Amortisierte Analyse - Der Bin"arz"ahler . . . . . . . . . . . . . . 9 1.5 Das Master Theorem f"ur Rekursionsgleichungen . . . . . . . . . . 12 1.6 Multiplizieren beliebig langer Zahlen . . . . . . . . . . . . . . . . 19

1.6.1 Der Algorithmus von Karazuba-Offman . . . . . . . . . . 19

2 Sortieren 22

2.1 Splitsort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22

2.1.1 Implementierung von Select durch Goodsplitter . . . . 23 2.1.2 Goodsplitter, randomisiert . . . . . . . . . . . . . . . . . 24 2.1.3 Goodsplitter, deterministisch . . . . . . . . . . . . . . . 25 2.2 Quicksort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28 2.3 Informationstheoretische untere Schranke . . . . . . . . . . . . . 31 2.4 Sortieren ohne Vergleiche . . . . . . . . . . . . . . . . . . . . . . 32

2.4.1 Countingsort . . . . . . . . . . . . . . . . . . . . . . . . . 32 2.4.2 Radixsort . . . . . . . . . . . . . . . . . . . . . . . . . . . 33

3 Hashing 35

3.1 Dynamische Verwaltung von Mengen . . . . . . . . . . . . . . . . 35

3.1.1 Realisierungen . . . . . . . . . . . . . . . . . . . . . . . . 35 3.1.2 Hashing mit Verkettung . . . . . . . . . . . . . . . . . . . 36 3.2 Mittlere Laufzeit von Hashing . . . . . . . . . . . . . . . . . . . . 37 3.3 Universelles Hashing . . . . . . . . . . . . . . . . . . . . . . . . . 39 3.4 Perfektes Hashing . . . . . . . . . . . . . . . . . . . . . . . . . . . 42 3.5 Dynamisches Hashing . . . . . . . . . . . . . . . . . . . . . . . . 44