Aktuelles
17.08.2001 Die Ergebnisse der Nachklausur sind FU-intern
hier zu finden. Die Klausureinsicht findet am 22.08.11 von 11-12 Uhr im Raum 050, Takustraße 9 statt.
20.07.2001 Am
17.08.11 um 10:00 Uhr findet eine Nachklausur im Raum 005, Takustraße 9 statt.
15.07.2001 Die Ergebnisse der Klausur sind FU-intern
hier zu finden. Die Klausureinsicht findet am 20.07.11 von 11-12 Uhr im Raum 006, Takustraße 9 statt.
11.07.2001 Die Klausur findet am
15.07.11 um 9:00 Uhr in der Takustraße 9, SR 005, statt. Alle Klausurdetails finden sich ganz unten auf dieser Seite.
22.06.2011 Bitte über die
KVV-Vorlesungsseite zu
jeweils einer Übunggruppe (A-D) anmelden. Zwecks Fairness werden die
Zeiten der Gruppen nach den ersten zwei Wochen getauscht. Die
Übungszuordnung ist bindend.
20.06.2011 Start der Vorlesung.
Link zum KVV. Erste Übungstermine und auch der erste Übungszettel sind online.
26.05.2011 Die erste Vorlesung beginnt am Montag, den 20.06., um
9:00 Uhr, im Raum 005 der Takustraße 9.
25.05.2011 Vorläufige Version der Seite; bitte beachten, dass es noch zu Änderungen kommen kann.
Vorlesung
| Montag |
9-12 Uhr |
Takustraße 9 SR 005 |
| Dienstag |
9-12 Uhr |
Takustraße 9 SR 005 |
| Mittwoch |
9-12 Uhr |
Takustraße 9 SR 005 |
| Donnerstag |
9-12 Uhr |
Takustraße 9 SR 005 |
| Freitag |
9-12 Uhr |
Takustraße 9 SR 005 |
Die Vorlesung orientiert sich im Wesentlichen an diesem
Skript
(nur FU-intern erreichbar) von Herrn Dr. Hoffman und Herrn PD Dr.
Kriegel. Inhaltlich wird der Stoff der entsprechenden
Erstsemester-Veranstaltung MafI 1 abgedeckt. Für
ProInformatik-Teilnehmer wird zusätzlich ein Ausdruck des Skriptes in Zi. 122, Takustraße 9, vorrätig sein
(bitte Anmeldebestätigung mitbringen).
20.06.2011: Aussagenlogik: Grundbegriffe, Operatoren, Syntax: Induktive
Definition von Booleschen Termen, Rang, Boolesche Funktionen, Substitution
21.06.2011:
Aussagenlogik: Von Booleschen Funktionen zu Termen, DNF, KNF,
Signaturen, Prädikatenlogik: Aussageformen, Quantoren
22.06.2011: Einführung von Mengen, Mengenoperatoren und -identitäten,
Rückführung auf Aussagenlogik, n-Tupel, Definition von Relationen
23.06.2011: Operationen auf Relationen, Äquivalenzrelationen,
Verschiedene Darstellungsmöglichkeiten, Äquivalenzklassen, Kongruenz
modulo m
24.06.2011: Äquivalenzrelationen und Partitionen, Abschluss,
Halbordnungen, Hasse-Diagramm, Totalordnungen, Lexikographische
Ordnung, Schranken auf Halbordnungen, Eigenschaften von Funktionen
27.06.2011: Charakterisierungen von Surjektivität, Abzählbarkeit,
Diagonalisierungsargumente, Hierarchie überabzählbarer Mengen,
Schubfachprinzip, Satz von Erdós-Szekeres
28.06.2011: Weitere Beispiele zum Schubfachprinzip, Beweisschemata:
direkt, durch Kontraposition, durch Widerspruch, durch
Fallunterscheidung, mit vollst. Induktion; Peano-Axiome, Def. der
Addition/Multiplikation, Summenformeln
29.06.2011: Verallgemeinerte und strukturelle Induktion, Abzählen,
Inklusions- / Exklusionsprinzip, Definition Binomialkoeffizienten
30.06.2011: Identitäten und rekursiver Zugang zu Binomialkoeffizienten, monotone Gitterwege, Mengenpartitionen
01.07.2011: Anzahl Surjektiver Funktionen, Summendarstellungen,
Zahlpartitionen (geordnete und ungeordnete), Prinzip des doppelten
Abzählens, Anzahl von Funktionenmengen, Die 12 Arten des
Abzählens
04.07.2011: Ein Kartentrick und seine Analyse, Diskrete
Wahrscheinlichkeitsräume, Bedingte Wahrscheinlichkeiten, Satz von
Bayes, Anwendung Inklusion/Exklusion, Unabhängigkeit
05.07.2011: Satz von der totalen Wahrscheinlichkeit, Zufallsvariablen,
Erwartungswert, Varianz, Linearität des Erwartungswertes,
Verteilungen: Gleichverteilung, Binomialverteilung, Geometrische
Verteilung; Coupon Collector-Problem
06.07.2011: Lineare Rekursionsgleichungen, Türme von Hanoi,
Fibonacci-Folge, Homogene Rekursionsgleichungen vom Grad d, Inhomogene Rekursionsgleichungen
07.07.2011: Einführung Graphentheorie, Definitionen,
Representationen, Handschlaglemma, Verschiedene Eigenschaften von
Graphen, Bäume und Wälder
08.07.2011: Charakterisierung bipartiter
Graphen und Zusammenhang zur 2-Färbbarkeit, Datenstrukturen Queue
und Stack, Graph-Traversierungen Breitensuche und
Tiefensuche, Tiefensuche auf gerichteten Graphen mit
Kantenklassifizierung, DAGs
11.07.2011: Topologische Sortierung, Erkennung von DAGs, Planare
Graphen, Kreuzungsfreie Zeichnungen in die Ebene, Eulerformel für
zshng. und unzshng. Graphen, Kantenanzahl (maximal) planarer Graphen,
Reguläre Polyeder und Bestimmung Platonischer Körper, Eulerkreise
12.07.2011: Eulerpfade, Algorithmus von Hierholzer, Duale Graphen,
Brücken, Knoten mit kleinem Grad in planaren Graphen, nicht-planare
Graphen K
5 und K
3,3, Der 5-Farbensatz
13.07.2011: Resolutionskalkül, Resolventen, Korrektheit des Kalküls,
Anwendung auf Tautologien und Implikationen, Hornformeln,
Markierungsalgorithmus,
14.07.2011: Einheitsresolventen, Markierungsalgorithmus als Kalkül, Definition von Gruppen, Beispiele zu Gruppen
Ergänzende und weiterführende Literatur (meist im Handapparat der Fachbereichs-Bibliothek vorrätig):
- Christoph Meinel, Martin Mundhenk: Mathematische Grundlagen der Informatik, Teubner; 2. Auflage 2002
(Standardbuch zur Vorlesung, deckt den Stoff weitgehend ab)
- Lehman, Leighton - Mathematics for Computer Science, Handout, 2004
(unterhaltsam geschriebene englische Einführung mit vielen Beispielen)
- Uwe Schöning: Logik für Informatiker, B.I.-Wissenschaftsverlag; 5. Auflage 2000
(enthält einige Ergänzungen zur Logik, überdeckt aber auch nur dieses Teilthema)
- Kenneth H. Rosen: Discrete Mathematics and its Applications, Mc-Graw Hill; 1999
(sehr gut lesbare und elementare englische Einführung)
- M. Aigner: Diskrete Mathematk, Vieweg, 5. Auflage 2004
(über den Vorlesungsstoff hinausgehendes Buch zum Teilthema Kombinatorik)