Effiziente Algorithmen

• Titel: Effiziente Algorithmen
• Organisation: UNI DORTMUND
• Seitenzahl: 295

Skript herunterladen (PDF)

Inhalt

• Universitt Dortmund a Lehrstuhl Informatik Dortmund
• Version vom November Uhr
• Einleitung Starker Zusammenhang in Graphen
• Starker Zusammenhang in Graphen
• Maximale Matchings in bipartiten Graphen
• beschrnkt Nach O a
• M Runden ist also die erste Phase beendet
• Maximale Matchings in allgemeinen Graphen
•  FindePfadh l B
• Der Algorithmus von Ford und Fulkerson
• und Restkapazitten r E R mit a
• falls e E falls reve E
• und es folgt wVQ VS e
• Der Algorithmus von Dinic
• Der Algorithmus von Malhotra Pramodh Kumar und Maheshwari
• das Potenzial des Knotens v V
• Flussalgorithmen nach Goldberg und Tarjan
• Q ev gilt dabei ist ev
•  der Knoten aus V also
• ew Natrlich gilt u
• ew da ja sogar
• und haben jetzt einerseits
• seits natrlich wie oben erlutert u a
• ew Wir haben damit insgesamt
• Amortisierte Analyse mit der Potenzialmethode
• Standardbinrcodierung verwaltet es soll also z a
• izi gelten Wir benut
• Binrzhler also z a a
• zi Wir bestimmen Ti Di Di in
• Amortisierte Analyse durch Kostenverteilung
• Amortisierte Analyse mit der Kontenmethode
• UnionFindDatenstrukturen mit schnellen Unions und Pfadkompression
• n n Zg r Zg
• String Matching mit endlichen Automaten
• Der Algorithmus von Knuth Morris und Pratt
• q Außerdem sei q
• Der Algorithmus von Boyer und Moore
• Prob q x
• fk n schreiben knnen Dieo
• i fk i Prob qi k i x
• Prob qi j qi k i xi
• t Prob qt t t x
• Prob n xn qi j i i
• akj bj i ej xi
• t t Prob qt i x
• und knnen zunchst direkt zu o a
• betrachten sehen wir dass Tij
• Tij t gilt und wir haben
• E Tij E Ti
• i t xt b E Ti
• Ein echt polynomielles Approximationsschema
• Version vom November Uhr Version vom November Uhr
• vs OPTw OPTw vs
• Ein echt polynomielles Approximationsschema fur das Rucksackproblem
• Beweis Fr i n und V u
• denieren wir MiV
• gj B i
• Das metrische TSP
• Das euklidische TSP
• O m r rr r O log nO
• falls i falls i
• Kostenzunahme durch Modifyg i b insgesamt durch
• E Kosten fr g u
• cgj b j j
• g vertikal g horizontal
• Erf llbarkeitsprobleme u
• Analyse randomisierter Algorithmen
• d pd p p
• p p p
• d id d d d
• pd p p pd p
• t Prob T t
• m Prob M m m
•  durch Addition also ist
• Approximation von MA kSAT und MA SAT
•  und damit auch
• Prob b erfllt ite Klausel u
• Ci p p pn
• Approximation fr MA kSAT u
• erfllt ist Damit knnen wir u o
• zj als Zielfunktion festlegen Wir legen fr u
• z z zm so dass
• zj maximal ist Natrlich lassen sich solche u
• a a ak Lemma
• x x k N k
• Prob cj nicht erfllt u
• gilt so dass
• lj lj lj
• Erfullbarkeitsprobleme exakt losen
• bi b i den Hammingabstand
• k ni n k ni n
• n i i nk n
• kn in in ik
• und sehen dass
• fr i kn n gilt entsprechend gilt u
•  und knnen jetzt Lemma benutzen um o
• Hd d Hd d
• Hd H d d
• o und knnen E
• p p p Fall bi bi bi
•  Fall bi bi bi
• Oensichtlich gilt wV V
• E e E E e
• dw v und sehen dass wir
• Aj Ai Damit
• haben wir Prob Algorithmus berechnet V V
• Prob kontrahiere e in iter Kontraktion Ai
• we wE minCutG wEi wEi wEi
• minCutG minCutG Vi V i ni
• und sehen dass Prob Algorithmus berechnet V V
• n n nn n folgt wie behauptet
• ni ni ni ni
• i ni i n i
• logn i logq log
• q i log q
• i logn log
• Ein randomisierter Primzahltest
• max k pk i
• Addieren wir andererseits zeilenweise so erhalten wir Rpn
• i i n und pk i
• und haben zusammen p n
• und knnen Lemma verwenden um o l
• n n k k p p
• alle paarweise disjunkt sind und H G folgt
• e e ee n mit n pp n
• p prim p prim
• kgV pp n p prim
• falls a QRp sonst
• pi dabei sei pi prim fr u
• a n a n a n a n
• falls ggTb n
• falls ggTa m
• a n a mod n a
• in Olog n Durchlufen a
• hat eine eindeutige Lsung x o
• Beweis Wir denieren m
• Allgemeine randomisierte Suchheuristiken
• ei ei und we
• f x cx wb x n wb wEx
• i i i i i i
• Prob B E A B
• Minimale Spannbume multikriteriell a
• q a q s qA q s
• a mT a e m m
• und Ausgabe ist ein
•  Wenn wir uns eine Nebenbedingung
•  und gemß Denition der Lnge ist a a
• de p so dass x
• i xi gilt Fr wollen zeigen dass u
• S knnen wir y o
• i xi schreiben Wir wollen zeigen dass
• Lemma Seien M M Mt konvex sei M
• Mi Ist x Rand
• fr alle m M u
• i xi eine kon
• gehren Daraus folgt x o
• gilt Aus Theorem folgt dass x
• i xi gilt mit i fr alu
• das zugehrige Simplextableau o
• i m Bu die Gleichung
• aij xj bi Die Gleichungen xi
• j G und ajk
• b bi bm
• u ui um Z
• y a ak an b
• yi ai aik ain bi
• ym am amk amn bm
• c ck cn
• v vk vn Z
• ak aik ak aik
• ai am amk aik ai c ck aik
• aik a ck aik
• u xk um Z
• bm bm amk aik ck abi ik
• Ausgewhlte Themen a
• nn n Mn M
• Statisches perfektes Hashing
• bi n Also ist
• Es gilt a gilt E
• M i M i bi M i
• und es gengt E u
• nach oben abzuschtzen Oenbar bezeichnet a
• n nn n M n
• und insgesamt folgt E
• b eine nichtnegative Zufallsi
• ai xi mod p
• v M v nv v M M n
• Prob T t kmax n

Vorschau