Nr. | Datum | Thema | Skript |
1 | 18.10.05 | Grundbegriffe der Aussagenlogik
- Was sind Aussagen?
- Logische Operatoren
- Induktive Definition der Syntax der Aussagenlogik
- Boolesche Formeln (Terme)
- Rechnen mit Wahrheitswerten (Boolesche Algebra)
| VL1 |
2 | 20.10.05 | Vom Booleschen Term zur Booleschen Funktion
- Baumdarstellung eines Terms, Klammerstruktur
- Rang einer Formel
- bottom-up-Auswertung bei gegebener Variablenbelegung, zugeordnete Boolesche Funktion
- Semantische Äquivalenz von Termen
- Bindungsstärke der logischen Operatoren
- Boolesche Gesetze beim Umformen von Termen
- das Substitutionsprinzip
| VL2 |
3 | 25.10.05 | Von der Booleschen Funktion zum Booleschen Term
- Anzahl n-stelliger Boolescher Funktionen
- Aufgabe: Finde zur Funktion einen Term, der sie repräsentiert
- Terme in DNF, KNF
- die kanonische dnf(f), knf(f)
- Interpretation im Hyperwürfel
- vollständige Mengen Boolescher Operatoren
| VL3 |
4 | 27.10.05 | Minimierung von DNF-Formeln, Prädikate und Quantoren
- vollständige Minterme
- Überdeckungen mit Unterwürfeln
- geometrische Interpretation
- Aussageformen
- Quantifizierte Aussagen
- Rechnen mit Quantoren
| VL4 |
5 | 01.11.05 | Mengen und Operationen auf Mengen
- Mengen Begriff
- Darstellung von Mengen
- Operationen auf Mengen, Identitäten
- Mengen Familien, Potenzmenge und ihre Mächtigkeit
- Kartesisches Produkt
| VL5 |
6 | 03.11.05 | Binäre Relationen und Operationen auf Relationen
- Binäre Relationen
- Darstellungen
- Operationen auf Relationen, Verknüpfung
- Eigenschaften von Relationen
- Abschluss bezüglich einer Eigenschaft
- Äquivalenzrelation, Äquivalenzklassen
| VL6 |
7 | 08.11.05 | Äquivalenzrelationen
- Partition einer Menge
- Äquivalenzrelation definiert Partition
- Partition definiert Äquivalenzrelation
- Operationen auf Äquivalenzrelationen
| VL7 |
8 | 10.11.05 | Halbordnungsrelationen
- Vollständiges Repräsentantensystem einer Äquivalenzrelation
- Halbordnungsrelation, Ordnungsrelation
- Hasse-Diagramm
- Lexikografische Ordnung
- untere/obere Schranken
| VL8 |
9 | 15.11.05 | Lineare Erweiterungen von Posets; Funktionen
- totale Ordnung, lineare Erweiterung eines Posets
- Satz: Jedes endliche Poset hat lineare Erweiterung (totpologisches Sortieren)
- Grundlegende Begriffe zu Funktionen
- Charakteresierung surjektiver, injektiver, bijektiver Funktionen
| VL9 |
10 | 17.11.05 | Abzählbare und überabzählbare Mengen
- Mächtigkeit, Gleichmächtigkeit
- endliche, abzählbar unendliche Mengen
- Rationale Zahlen sind abzählbat
- Überabzählbarkeit, Diagonalisierungsbeweise
- Bsp.: Reele Zahlen sind überabzählbar, Potenzmenge von N ist überabzählbar
| VL10 |
11 | 22.11.05 | Beweistechniken
- direkter Beweis, Kontraposition, Widerspruchsbeweis, Fallunterscheidung
- Taubenschlagprinzip, Satz von Erdös-Szekeres
| VL11 |
12 | 24.11.05 | Beweis mittels vollständiger Induktion
- Peanoschen Axiome
- Beispiele
| VL12 |
13 | 29.11.05 | Strukturelle Induktion, Grundlegende Zählprinzipien
- Strukturelle Induktion
- Grundlegende Zählprinzipien: Summenregel, Produktregel, Inklusion-Exklusion Prinzip
- Permutationen
- k-elementige Untermengen
| VL13 |
14 | 01.12.05 | Rechnen mit Binomialkoeffizienten, Gitterwege
- Binomialkoeffizienten
- Pascalsches Dreieck, Vandermondsche Gleichung, Binomischer Satz
- Gitterwege
| VL14 |
15 | 06.12.05 | Mengenpartitionen, Zahlpartitionen
- Partitionen von n-elementigen Mengen, Stirling Zahlen 2. Art
- Zahlpartitionen, geordnet und ungeordnet
| VL15 |
16 | 08.12.05 | Abzählen, die Übersicht | VL16 |
17 | 13.12.05 | Diskrete Wahrscheinlichkeitsrechnung, die Grundlagen
- endlicher Wahrscheinlichkeitsraum, Ereignis
- elementare Eigenschaften eines Wahrscheinlichkeitsraums
- bedingte Wahrscheinlichkeit, unabhängige Ereignisse
| VL17 |
18 | 15.12.05 | Diskrete Wahrscheinlichkeit, Beispiele, Zufallsvariable, Erwartungswert
- Satz von Bayes
- Rechnen mit bedingten Wahrscheinlichkeiten
- Zufallsvariable, Erwartungswert
| VL18 |
19 | 03.01.06 | Erwartungswert | VL19 |
20 | 05.01.06 | Varianz, Ungleichungen von Markov und Tschebyschev, spezielle Verteilungen | VL20 |
21 | 10.01.06 | Geometrische Verteilung, das Coupon-Collector-Problem Einführung in die Graphentheorie und algorithmische Fragen | VL21(1) VL21(2) [ps] VL21(2) [pdf] |
22 | 12.01.06 | Grundlegende graphentheoretische Begriffe, Bipartite Graphen | VL22 [ps] VL22 [pdf] |
23 | 17.01.06 | Bäume und ihre Charakterisierung, Breitensuche | VL23 |
24 | 19.01.06 | Korrektheit BFS, Tiefensuche und Topologisches Sortieren | VL24 |
25 | 24.01.06 | Minimum Spanning Tree, Algorithmen von Prim und Kruskal | VL25 |
26 | 26.01.06 | Flüsse in Netzwerken | VL26 Ford-Fulkerson-Beispiel |
27 | 31.01.06 | Resolution I | VL27 |
28 | 02.02.06 | Resolution II | VL28 |
29 | 07.02.06 |
30 | 09.02.06 |
31 | 14.02.06 |
32 | 16.02.06 |