Komplexität von Algorithmen

• Titel: Komplexität von Algorithmen
• Organisation: UNI ERLANGEN
• Seitenzahl: 236

Skript herunterladen (PDF)

Inhalt

• Skriptum zur Vorlesung Komplexitt von Algorithmen a
• c Volker Strehl Informatik FAU ErlangenNrnberg u
• Operationen Addition koezientenweise
• y x y Hammingdistanz
• a f Zyklen gerader Lnge in Transpositionen in
• t tr t B tr Br
• k k
• Logarithmische Reihe k
• fac N N n n Spezieller Wert Bedeutung
• Binomialformel fr Polynome u
• n k Y nk k
• Spezialflle davon a
• Polynom vom Grad k Dies deniert durch Einsetzen
• Newtons Binomialreihe a
• Potenzsummen harmonische Reihe
• St n St n Spezialflle a
• k t t t nt
• nn nn n nn
• Wachstum von Folgen und Funktionen
•  Wachstum von Folgen und Funktionen
• Polynome Exponentialfunktionen Logarithmen eine Konstante so gilt
• Summen und Integrale
• analog fr monoton fallende Funktionen u
• Summationen von Potenzen
• Abschtzung fr t a u
• ak nd Juni
• Wichtiger Spezialfall harmonische Zahlen
• Ist a gilt
• Konvergenzkriterium von CauchyHadamard MATHEMATISCHE HILFSMITTEL Juni
• verhlt sich so a
• Zweite Version Die Lsung der Rekursion o
• Lineare Rekursionen mit konstanten Koezienten
• Der Konvergenzradius von b
• a b c c cr
• DerErwartungswert von ist E
• n n n GU
• k k e z ez k
• Grasche Darstellungen der Verteilungen
• Binomialverteilung mit n p n p n p
• Geometrische Verteilung mit p p p
• Wichtige Abschtzungen a
• Zum Aufwrmen worm up a
•  Zerteilen von hochdimensionalen Quadern
• Zerteilen von hochdimensionalen Quadern
•  Kommunikation uber eingeschrnkte Kanle a a
• Kommunikation uber eingeschrnkte Kanle a a
• L Bn herausnden
•  Kollisionen Das Geburtstagsparadoxon
• Kollisionen Das Geburtstagsparadoxon
• Serien Das Sammeln von Coupons
•  Gameshow hats das Spiel mit den Hten u
• Gameshow hats das Spiel mit den Huten
• A B C r b A B C
•  Variet the best card trick e
• Variet the best card trick e
• Crekursive Folgen Theorie
• Zwei Beispiele zur Motivation
• CREKURSIVE FOLGEN THEORIE
•  Zwei Beispiele zur Motivation
• Diese Verhltnisse ergeben sich aus der Formel a
• Fn Fn Fn n
• Abbildung TrellisDiagramm fr das FrisbeeSpiel u h hi
• fr n u
• h h fr n verhalten u
• und sich durch die Startwerte unterscheiden h h
• Lineare Rekursionen Ordnung
•  Denitionen grundlegende Eigenschaften
• Denitionen grundlegende Eigenschaften
•  Die beiden Probleme revisited
• Die beiden Probleme revisited
• gengen der gleichen Reu
• h h h h
• tungswert von erhlt man dann a E
• k P k P k
• P k PSpiel bentigt n Wrfe o u
• n n n n n
• Abbildung Schiebegister zur Rekursion xn xn xn
• so wird folgende Zustandsfolge durchlaufen spaltenweise zu lesen
•  Matrizen Theorem von CayleyHamilton
• Matrizen Theorem von CayleyHamilton
• Fr die Hankelmatrizen der Ordnungen u det H
• gilt und dies ist da a ist
• Eine Aquivalenzklasse von wird als rationale Funktion bezeichnet
• was per Koezientenvergleich fn
• t nt n Satz
•  Newtons Formel und die Folgen
• Newtons Formel und die Folgen
• kj j kj
• kk kk kk kk k
• p k k kk
•  Inhomogene forcierte lineare Rekursionen
• j ztj pj nn z n j
• Inhomogene forcierte lineare Rekursionen
• deniert durch das Rekursionspolynom
• bz z k yz az
• bz z z k az z
•  Kommentare Literatur Ausblicke
• Kommentare Literatur Ausblicke
• Crekursive Folgen Dierenzenrechnung
• zTransformation Lineare Dierenzen und Dierentialgln
• Crekursive Folgen Anwendungen
• Interessanter wird die Angelegenheit wenn trix B A
• B B B B
• CREKURSIVE FOLGEN ANWENDUNGEN
• gegen die Matrix
• oder approximiert B
•  Graphen und regulre Sprachen a
• sein Aber warum ist das so
• Graphen und regulre Sprachen a
•  Graphen und Matrizen
• Graphen und Matrizen
• i n j G G
• Nun deniert man noch wij
• w i jn A G
• falls ri falls ri falls ri falls ri
• falls ri falls ri
• Abbildung Gerichteter Graph mit Knoten und Kanten
• GoggleMatrix mit G
• Eine Potenz der GoogleMatrix auf Stellen gerundet G
• CREKURSIVE FOLGEN ANWENDUNGEN Juni
•  Googles PageRankAlgorithmus Die Eigenwerte von G i
•  Googles PageRankAlgorithmus Adjazenzmatrix A GoogleMatrix mit
• Der LinksEigenvektor zum Eigenwert
• Der normalisierte Eigenvektor
• Vergleiche wiederum mit der Matrix G
• t t t t t t t t
• ausgehend vom Startvektor ai ei ai
• ni i n n n n
• Lnge der Binrdarstellung von n logn a a
• Lemma Die Funktionen n n n n
• falls n falls n gerade falls n ungerade
• Szenario statische DCRekursionen
•  Szenario statische DCRekursionen
• falls n bound TA nj gn sonst
• Im zweiten Fall gilt mit TA n
• TA n rj gn
• bz cz z k dz az cz
• Einfache DivideandConquerRekursionen MasterTheorem
• falls a bd falls a bd
• f n nd log n
• f n nlogb a
• ai f nbi ns logt n b
• ai gm i bms mt Juni
• Betrachte dies als eine inhomogene forcierte lineare Rekursion
• ai gm i c bms mt
• Merge two sorted lists
• Compare head elements
• logm log m log log n
• wobei man nun zu unterscheiden hat DIVIDEANDCONQUERREKURSIONEN Juni
• Rekursive Multiplikation von Zahlen und Polynomen
• miteinander zu multiplizieren so besagt die Formel
• Es gilt die Rekursion
• uj us us
• Test F for Satisability Trivial case
• Select clause Test subcases recursively
• Einige Zahlenwerte k k k k k
• Distanzen berechnen On
• Pr p P m px
• Abbildung Situation im zentralen Streifen
• Abbildung Disjunkte Kreisscheiben in einem Rechteck
• N N N N N N
• wobei N eiN cos
• falls j k falls j k
• N N jk jk N
• DF TN V N
• und Lemma besagt
• DF TN DF TN N IN
• Beispiele fr DFTMatrizen u n DF T n
• i i i i i i
• i i i i
• n DF T mit
• Beachtet man nun noch die simplen Tatsachen
• k k N ekN ekN N
• N k k aN ak N ak
• k k aN ak N ak
• k aN N k aN
• k aeven N k aodd N
• a a a a a a a a
• hk k f g
• mittels Interpolation DIVIDEANDCONQUERREKURSIONEN Juni
• Schema der Polynommultiplikation mittels Auswertung und Interpolation
• Dynamisches DivideandConquer Quicksort
• und ar ak ak an
•  Dynamisches DivideandConquer Quicksort
• tk tnk dt an
• sn s n lim n sn n
• in der Form n F n nn
• Gi Gi i i i
• Eine nichtlineare Rekursion fur binre Bume a a
• Siehe fr die spannende Geschichte dieser Zahlen u
• Erster Beweis fur die CatalanFormel
• Damit hat man
• n n zn z n n n n
• und das liefert wie erwartet bz
• woraus sich bn ergibt
• Zweiter Beweis fur die CatalanFormel
• Abbildung Kellerautomat fr die LukasiewiczSprache u
• Dritter Beweis der CatalanFormel
• P k eindeutig
•  Binrbume und Dynamische Programmierung a a
• Binrbume und Dynamische Programmierung a a
• falls t Bi tr Bj i j n
• Information und Komplexitt a
• Parameter von Binrbumen a a
• Die Menge der Binrbume ist B a a
• INFORMATION UND KOMPLE ITAT
•  Parameter von Binrbumen a a
• maxht htr h t tr INFORMATION UND KOMPLE ITAT
•  Binre Suchbume a a
• die ußere Weglnge als a a we t
• Binre Suchbume a a
• wit wet it wt
• t tr und mit a
• Suche a im Suchbaum v t
• falls t pt ptr falls t
• pt pt ptr n ptr
• itc it t vtr
• i im j jn
• ist kommutativ und assoziativ
•  Binre Suchbume a a t tr Bn
•  Sortierkomplexitt und Information a
• Sortierkomplexitt und Information a
• Mittlere Hhe von Binrbumen o a a
• ist klar Der Induktionsschritt
• Abbildung Graph der Entropiefunktion Hx x gelb
• n O n Juni
• n n n n
• fr ein k n u
• pk qk Juni
• qj log qj qj log log qj
• pi log log pi
• Ai die disjunkte Vereinigung der Ai
• Hp pn c mit einer Konstanten c
• ht p ht p
• Abbildung Gewichtete mittlere Hhe o
• ht q ht q
• Dann gilt Induktion ht p
• wegen der Eigenschaften und der Entropiefunktion
• Codes variabler Lnge a
• a b c d e
• Quellen und Datenkompression
• mittlere Codewortlnge a
• Ungleichung von Kraft
• pk log pk Hp Juni
• Huffmans Konstruktion optimaler PrxCodes a
• Q Q ab cdef
• Q a b c d e f
• Q ab cdf e
• Bottomup Implementierung der HuffmanKonstruktion
• tk tk h gk gk
• e e a b c
• Bume und Suchbume Sortierkomplexitt a a a
• Primzahlverikation Primzahltests Faktorisierungsmethoden PublickeyKryptograe
• Schnelle Multiplikation von Zahlen und Polynomen

Vorschau