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

Algorithmen

& Komplexit"at I

Wintersemester 1994/1995

INHALTSVERZEICHNIS i Inhaltsverzeichnis 1 Graphenalgorithmen 1

1.1 Grundlagen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1.2 Billigste Wege . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3

1.2.1 Billigste Wege von einem Knoten aus . . . . . . . . . . . . . . 3 1.2.2 Warteschlangen . . . . . . . . . . . . . . . . . . . . . . . . . . 5 1.3 Amortisierte Analyse . . . . . . . . . . . . . . . . . . . . . . . . . . . 8

1.3.1 Amortisierte Analyse f"ur Fibonacci-Heaps . . . . . . . . . . . 9 1.4 Depth First Search (Tiefensuche) . . . . . . . . . . . . . . . . . . . . 11

1.4.1 Wichtige Eigenschaften . . . . . . . . . . . . . . . . . . . . . 11 1.4.2 Starke Zusammenhangskomponenten . . . . . . . . . . . . . . 13 1.5 Matchings . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16

2 W"orterb"ucher 23

2.1 Hashing mit Verkettung . . . . . . . . . . . . . . . . . . . . . . . . . 23 2.2 Hashing mit offener Adressierung . . . . . . . . . . . . . . . . . . . . 25 2.3 Universelles Hashing . . . . . . . . . . . . . . . . . . . . . . . . . . . 27 2.4 Perfektes Hashing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29

3 H"ohenbalancierte B"aume, Union Find 35

3.1 (2,4)-B"aume . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35 3.2 Union Find . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38

4 Lineare Programmierung 43

4.1 Simplexalgorithmus . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45 4.2 Dualit"at . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49 4.3 Alternative Darstellung . . . . . . . . . . . . . . . . . . . . . . . . . 49

5 NP-Vollst"andigkeit 53

5.1 Weitere Komplexit"atsklassen . . . . . . . . . . . . . . . . . . . . . . 60

1 1 Graphenalgorithmen 1.1 Grundlagen Definition 1.1: Ein Paar (V; E) heisst gerichteter Graph :, V ist endliche Menge von Knoten. E ` V \Theta V ist eine Menge von Kanten. Ein Element e = (u; v) 2 E heisst Kante von u nach v (u ! v). u ist Startknoten von e, v ist Zielknoten. v ist Nachbarknoten von u (v ist adjacent zu u).

Ein Pfad im Graph G ist eine Folge (v0; : : : ; vk) von Knoten mit k * 0 und (vi; vi+1) 2 E f"ur 0 ^ i ^ k \Gamma 1. Das ist ein Pfad von v0 nach vk. Die L"ange des Pfades ist k. Falls v0 = vk und k * 1, so heisst der Pfad Kreis. Falls vi 6= vj f"ur

i 6= j, so heisst der Pfad einfach. F"ur einen Pfad von u nach v in G schreibe u \Lambda !G v. Ein gerichteter Graph ist zyklisch, falls es einen Kreis gibt, sonst azyklisch.