- Titel: Algorithmentheorie
- Organisation: UNI FRANKFURT
- Seitenzahl: 175
Inhalt
- Prof Dr Georg Schnitger WS
- Einfuhrung Grundlagen Einige Grundlagen aus der Stochastik Asymptotik
- Graphalgorithmen Suche in Graphen Tiefensuche Breitensuche
- Krzeste Wege u Minimale Spannbume a Zusammenfassung
- Entwurfsmethoden GreedyAlgorithmen Scheduling HumanCodes
- Die Lineare Programmierung Zusammenfassung
- Algorithmen fur schwierige Probleme
- Einige Grundlagen aus der Stochastik
- b Der Erwartungswert ist E p
- gn n f n f n n gn
- Bubble Sort Selection Sort und Insertion Sort
- BUBBLE SORT SELECTION SORT UND INSERTION SORT
- Eine LaufzeitAnalyse von Quicksort
- n i n n n
- und deshalb ist
- n n i ji n ni i j
- n logn i i n i
- Weitere Verbesserungen von Quicksort
- EINE UNTERE SCHRANKE
- Eine untere Schranke
- DISTRIBUTION COUNTING RADI E CHANGE UND RADI SORT
- Distribution Counting RadixExchange und Radixsort
- SAMPLE SORT PARALLELES SORTIEREN
- Aufgabe Sind die Sammelphasen wirklich notwendig
- Sample Sort Paralleles Sortieren
- Schlssel parallel u
- Schlssel nach Schritt u
- Suche in Graphen
- SUCHE IN GRAPHEN
- lnges v wenn s v E a sonst
- s z y x
- d c d m d E
- Minimale Spannbume a
- d d e e
- d d d m e
- g e d c
- minimieren Hier ist die zentrale Uberlegung
- Eine schnelle Multiplikation naturlicher Zahlen
- Eine Schnelle Matrizenmultiplikation
- Das gewichtete Intervall Scheduling
- Kurzeste Wege und Routing im Internet
- lngeu w distanzi wv a
- lngeu w Dw v a
- Paarweises Alignment in der Bioinformatik
- duk und D j
- Voraussage der RNA Sekundrstruktur a
- Aus wwwzibdeMDGrouptemplecturelp secondaryrna secondpdf
- kkj ist waehlbar
- Di k Dk j Di j
- DIE LINEARE PROGRAMMIERUNG
- Die Lineare Programmierung
- ist dann unter den Nebenbedingungen
- P NP und die NPVollstndigkeit a
- KAPITEL P NP UND DIE NPVOLLSTANDIGKEIT
- TURINGMASCHINEN UND DIE KLASSE P
- Turingmaschinen und die Klasse P
- Die Berechnungskraft von Turingmaschinen
- x a b B x a b B
- lschen B links o
- qrucklauf B links
- c c c c
- Die Klasse NP
- DIE KLASSE NP
- Der Begri der Reduktion und die NPVollstndigkeit a
- NPvollstndige Probleme a
- Die NPVollstndigkeit von KNFSAT a
- KAPITEL NPVOLLSTANDIGE PROBLEME
- DIE NPVOLLSTANDIGKEIT VON KNFSAT
- Zelle wo wwo
- iBzwas T t T t T
- Zellet wo Zellet wo Zellet wo B
- Angenommen wir haben er
- Aufgabe Zeige dass SAT P
- WEITERE NPVOLLSTANDIGE PROBLEME
- Weitere NPvollstndige Probleme a
- Independent Set Vertex Cover und Set Cover
- Al eine Uberdeckung mit
- Programmierung und Ganzzahlige Programmierung
- Aufgabe Beweise Satz
- Wege in Graphen
- Beispiel Betrachte folgenden ungerichteten Graphen
- ein Weg in G ist dann erhalten wir
- NPVollstndigkeit in Anwendungen a
- NPVOLLSTANDIGKEIT IN ANWENDUNGEN
- Phylogenetische Bume a
- falls oder Eingnge logisch sind a sonst
- KAPITEL NPVOLLSTANDIGE PROBLEME A A A A A
- Wir erhalten dann die folgende Datenbank
- Existenz von Gewinnstrategien
- Algorithmen fur schwierige Probleme
- n tk m k
- DAS RUCKSACK PROBLEM
- wenn Aufgaben gemß fallender a
- und das war zu zeigen
- Das Rucksack Problem
- kann in Zeit
- APPRO IMATION UND LINEARE PROGRAMMIERUNG
- j n n maxj wj
- Fall Es ist
- Approximation und lineare Programmierung
- KAPITEL LOKALE SUCHE
- Lokale Suche in variabler Tiefe
- DER METROPOLIS ALGORITHMUS UND SIMULATED ANNEALING
- Der Metropolis Algorithmus und Simulated Annealing
- UphillQ y ry
- Evolutionre Algorithmen a
- und PunktCrossover sowie
- V C fur kleine Uberdeckungen
- KAPITEL E AKTE ALGORITHMEN
- Die Webseite wwwtspgatechedu erhlt weitere Informationen a
- ur gradB r
- Branch Cut Verfahren
- drs xrs so dass
- xrs fr jede Stadt s u
- DER ALPHABETA ALGORITHMUS
- Der AlphaBeta Algorithmus
- Aufgabe Zeige Lemma
Vorschau
Skript zur Vorlesung Algorithmentheorie“ ”
Prof. Dr. Georg Schnitger WS 2010/11
Hinweise auf Fehler und Anregungen zum Skript bitte an matthias@thi.informatik.uni-frankfurt.de Mit einem Stern gekennzeichnete Abschnitte werden in der Vorlesung nur kurz angesprochen.
Inhaltsverzeichnis
1 Einfuhrung ¨ 1.1 Grundlagen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.1.1 1.1.2 1.2 Einige Grundlagen aus der Stochastik . . . . . . . . . . . . . . . . . . Asymptotik . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 5 6 9 10
Literatur . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
I
Effiziente Algorithmen
11
13 13 16 18 21 22 23 27 29 31 33 35 36 36 38 39 44 49
2 Sortieren 2.1 2.2 Bubble Sort, Selection Sort und Insertion Sort . . . . . . . . . . . . . . . . . . Quicksort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.2.1 2.2.2 2.2.3 2.3 2.4 2.5 2.6 2.7 Eine Laufzeit-Analyse von Quicksort . . . . . . . . . . . . . . . . . . . Weitere Verbesserungen von Quicksort . . . . . . . . . . . . . . . . . . Das Auswahlproblem . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Mergesort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Eine untere Schranke . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Distribution Counting, Radix-Exchange und Radixsort . . . . . . . . . . . . . Sample Sort: Paralleles Sortieren . . . . . . . . . . . . . . . . . . . . . . . . . usammenfassung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3 Graphalgorithmen 3.1 Suche in Graphen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.1.1 3.1.2 3.2 3.3 3.4 Tiefensuche . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Breitensuche . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
K¨rzeste Wege . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . u Minimale Spannb¨ume . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . a usammenfassung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1