Kombinatorische Methoden in der Informatik

• Titel: Kombinatorische Methoden in der Informatik
• Organisation: UNI TUEBINGEN
• Seitenzahl: 80

Skript herunterladen (PDF)

Inhalt

• Kombinatorische Methoden in der Informatik
• Teilgebiete der Kombinatorik
• Anwendungen in der Informatik
• Hauptthemen der Vorlesung
• Elementare kombinatorische Techniken
• KAPITEL ELEMENTARE KOMBINATORISCHE TECHNIKEN
• Zum Verdeutlichen ein Baumdiagramm
• S Sik Sm
• Prinzip des doppelten Abzhlens a
• und durch spaltenweises Abzhlen a
• nte harmonische Zahl
• Abbildung Ober Untersummen der Funktion
• dt logn t dt logn t
• Abzhlen von Mengen und a Abbildungen
• nn n b n k nk k
• Binomische Formel a b
•  KAPITEL ABZAHLEN VON MENGEN UND ABBILDUNGEN
• x x n xn n i
• Lnge dieser Folge a
• xi n k n
• Anzahl der Einsen
• x xn xi N Umgekehrt
• n n y yn N i
• xi k so x xn Nn mit
• yi k n so y yn Nn mit
• k aus n Anordnung relevant Anordnung nicht relevant
• keine Mehrfachauswahl nk k n n b
• Mehrfachauswahl mglich o nk a
• Mglichkeiten f r n o u
• n jn n n jk
• bijektiv nk n n k
• Sei n Richtig f r k u
• Sn Sn Sn
• b T rme von Hanoi u
• Abbildung T rme von Hanoi u
• Abbildung Drei sich schneidende Geraden
• Cj Cnj n C C Konvention C
• c xn Am Anfang xk xn xk
• ck Ausgabe der Rekursionsfolge
• dettEk A det
• tk c tk ck t ck
• k k d s dk sk ak
• n n n n
• Gelegentlich wird die FibonacciFolge auch mit den Anfangswerten
• rn eine Lsung von R o
• r n c r k c
• KAPITEL REKURSIONEN Einsetzen
• ank k ak
• f j gn n ji f j
• Wachstum von Rekursionsfolgen
• Wachstum von Funktionen
• KAPITEL WACHSTUM VON REKURSIONSFOLGEN
• log x dx log n
• gen gend groß denn u
• sij nmi b n
• f r alle n m u
• f r alle n n u
• C ik log il ai ani
• also xn Onk log nl an
• ik log il n n
• nk log nl an kl
• n also nach c xn n
• KAPITEL ERZEUGENDE FUNKTIONEN
• u aj bij f r i N
• aj bij f r i N u
• Rekursive Denition f r die bi u
• b k N tk t k
• i ik ti alle geord ktupel
• i ik ij i i ik i
• kk k i i ki i i
• f r alle n N u
• ri i t tr i
• e er ei N e er i
• ae arer Koe von
• te ter te er
• t t t t t t
• t t t t t t t
• n n n n n n
• Partialbruchzerlegung t t t t t t
• t t n tn n n n n
• Danach die Inversen von
• Ci Cni n C
• Cn tn die erzeugende Funktion
• Koezientenvergleich bei t t n
• n n n n n n
• Was ist n n n n
• an t betrachtet n
• tn expt n n
• iii Aus aRb und bRc folgt aRc
• KAPITEL GEORDNETE MENGEN
• e c a d b f
• d MT Teiler von und Teilerrelation
• b muss man die Summe nur
• falls a b falls a b
• x falls x a falls x a
• Andererseits ist S
• am a m kgV a p m
• Analog Ist hx
• BK BK hhh h h A A
• I J K K
• Abbildung Klar BJ
• Aj A falls J und
• Ai falls I J
• Die Gleichung beschreibt also die Anzahl f J
• J n J l
• vielleicht noch weitere Daher ist Daher f J
• bliche Bezeichnung f n Dn u
• Der Satz von Dilworth und Folgerungen
• ist Kette ist Antikette
• KAPITEL DER SATZ VON DILWORTH UND FOLGERUNGEN
• bipartiter Graph uberdeckende Punktmenge Matching
• vollstndiges Matching von S nach T a
• KAPITEL DER SATZ VON DILWORTH UND FOLGERUNGEN v
• v v v v a v v v
• alternierender Weg f r M u
• M M M F M F F M
• v xk v v
• Endpunkt von k
• Anfangspunkt von k
• Kapazitt des Schnittes a

Vorschau