Studium
Bachelor
- 1.Semester (WS 07/08)
- 2.Semester (SoSe 2008)
- 3.Semester (WS 08/09)
- 4.Semester (SoSe 2009)
- 5.Semester (WS 09/10)
- 6.Semester (SoSe 2010)
- 7.Semester (WS 10/11)
Master
- 8.Semester (SoSe 2011)
- 9.Semester (WS 11/12)
Mathematik für Informatiker I - Logik und Diskrete Mathematik
Dozent: Prof. Dr. Günter Rote
Inhalt
- Aussagenlogik und mathematische Beweistechniken
- Mengenlehre: Mengen, Relationen, Äquivalenz- und Ordnungsrelationen, Funktionen, Natürliche Zahlen und vollständige Induktion, Abzählbarkeit
- Kombinatorik: Abzählprinzipien, Binomialkoeffizienten und Stirling-Zahlen, Rekursion, Schubfachprinzip
- Graphentheorie: Graphen und ihre Darstellungen, Wege und Kreise in Graphen, Bäume
- Boolesche Formeln und Boolesche Funktionen, DNF und KNF, Erfüllbarkeit, Resolutionskalkül
- Prädikatenlogik und mathematische Strukturen
Vorlesung
Folgende Themen wurden in der Vorlesung behandelt:
- Aussagenlogik
- Dienstag, 16. Oktober 2007:
- Aussagen, Boole'sche Formeln, Junktoren
- Donnerstag, 18. Oktober 2007:
- Syntax und Semantik der Aussagenlogik
- Vorrangregeln, Weglassen von Klammern
- Baumstruktur Boole'scher Formeln
- Wahrheitsbelegung, Wahrheitstafel
- semantische Äquivalenz
- Erfüllbarkeit, Tautologie, Kontradiktion
- logische Gesetze, Umformungen
- Das Leibniz'sche Ersetzungsprinzip
- Dienstag, 23. Oktober 2007:
- semantische Äquivalenz und Äquivalenzjunktor
- Umformen von logischen Ausdrücken
- konjunktive Normalform
- Umwandlung in konjunktive Normalform durch Umformen
- Donnerstag, 25. Oktober 2007:
- Boole'sche Funktionen
- Umwandeln einer Boole'schen Funktion in konjunktive Normalform
- Dienstag, 16. Oktober 2007:
- Prädikatenlogik
- Donnerstag, 25. Oktober 2007:
- Variablen, Aussageformen, Funktionen, Prädikate, Quantoren
- Präfix- und Infix-Schreibweise von Prädikaten und Funktionen
- Gültigkeitsbereiche bei Quantoren
- Dienstag, 30. Oktober 2007:
- Syntax der Prädikatenlogik: Terme, Formeln
- freie und gebundene Variablen
- Semantik der Prädikatenlogik
- Prädikatenlogische Gesetze: de Morgan'sche Regeln
- Donnerstag, 1. November 2007:
- Beispiele zur Formulierung mathematischer Aussagen mit Prädikatenlogik
- Donnerstag, 25. Oktober 2007:
- Mengen, Relationen, Funktionen
- Donnerstag, 1. November 2007:
- Mengenoperationen, Potenzmenge, geordnete Paare, kartesisches Produkt
- Dienstag, 6. November 2007:
- Relationen
- Eigenschaften von Relationen, Verknüfung von Relationen, inverse Relation
- Donnerstag, 8. November 2007:
- Äquivalenzrelationen, Klasseneinteilungen (Partitionen)
- Ordnungsrelationen (Halbordnungen): minimale und maximale Elemente, kleinstes und größtes Element, lineare Ordnung
- Dienstag, 13. November 2007:
- Halbordnungen: Ketten und Antiketten, Supremum und Infimum, Verbände
- Funktionen. Darstellung von Funktionen
- Injektive, surjektive, bijektive Funktionen; Verknüpfung und inverse Funktion
- Anzahl von Funktionen
- Donnerstag, 15. November 2007:
- Der Graph einer Funktion
- Anzahl von injektiven und bijektiven Funktionen
- Das Schubfachprinzip
- Permutationen: inverse Permutation, Zyklendarstellung, Transpositionen
- Dienstag, 20. November 2007:
- Gerade und ungerade Permutationen, Inversionen (Fehlstände)
- Potenzen und inverse Permutationen in Zyklendarstellung
- Donnerstag, 22. November 2007:
- Endliche und unendliche Mengen, abzählbare und überabzählbare Mengen
- Abzählbarkeit der rationalen Zahlen
- Das Cantor'sche Diagonalargument
- Folgen
- Verallgemeinertes Schubfachprinzip
- Anwendungen des Schubfachprinzips
- Donnerstag, 1. November 2007:
- Beweistechniken
- Dienstag, 27. November 2007:
- Direkter Beweis, Kontraposition, Beweis durch Widerspruch (indirekter Beweis), Fallunterscheidung
- Vollständige Induktion
- Donnerstag, 29. November 2007:
- Varianten der vollständigen Induktion
- Strukturelle Induktion
- Logische Basis von Junktoren (funktional vollständige Signaturen)
- Induktive Definitionen
- Dienstag, 27. November 2007:
- Kombinatorik
- Donnerstag, 29. November 2007:
- Binomialkoeffizienten
- Dienstag, 4. Dezember 2007:
- unverbindliche und freiwillige Probeklausur, Musterlösungen
- Donnerstag, 6. Dezember 2007:
- Elementare Zählprinzipien: Gleichheitsregel, Summenregel, Produktregel
- Das Pascal'sche Dreieck
- Der binomische Lehrsatz
- Dienstag, 11. Dezember 2007:
- Gitterpfade
- Partitionen und Stirlingzahlen zweiter Art
- Kombinationen mit Wiederholung (Multimengen)
- Donnerstag, 13. Dezember 2007:
- Inklusion-Exklusion (die Siebformel)
- Doppeltes Abzählen
- Donnerstag, 29. November 2007:
- Elementare Wahrscheinlichkeitstheorie
- Donnerstag, 13. Dezember 2007:
- Diskreter Wahrscheinlichkeitsraum, Elementarereignisse und Ereignisse, Gleichverteilung
- Dienstag, 18. Dezember 2007:
- Bedingte Wahrscheinlichkeit
- Unabhängige Ereignisse
- Formel von der totalen Wahrscheinlichkeit
- Donnerstag, 20. Dezember 2007:
- Zufallsvariablen und Erwartungwert
- Linearität des Erwartungswertes
- Dienstag, 8. Januar 2008:
- Wahrscheinlichkeitsfunktion und Verteilungsfunktion von Zufallsvariablen
- Einige diskrete Verteilungen von Zufallsvariablen: Gleichverteilung, Bernoulli-Verteilung, Binomialverteilung, geometrische Verteilung
- Klebebildchensammler (Das coupon-collector-Problem)
- Irrfahrten: einführendes Beispiel aus der Warteschlangentheorie
- Donnerstag, 10. Januar 2008:
- Symmetrische Irrfahrt als Beispiel einer Markoffkette
- Bayes'sche Formel
- Donnerstag, 13. Dezember 2007:
- Algebraische Strukturen
- Donnerstag, 10. Januar 2008:
- Operationen, Verknüpfungstafel
- Kommutative und assoziative Operationen, neutrales Element
- Halbgruppen und Monoide
- Dienstag, 15. Januar 2008:
- Inverse Elemente
- Gruppen, Permutationsgruppen
- Homomorphismen
- Isomorphie
- Donnerstag, 17. Januar 2008:
- Homomorphismen in der Informatik: Modellierung und Darstellung von Datenstrukturen
- Donnerstag, 10. Januar 2008:
- Lineare Rekursionsgleichungen
- Donnerstag, 17. Januar 2008:
- Beispiele: Türme von Hanoi, Bitfolgen mit verbotenen Mustern
- Verifikation durch vollständige Induktion
- Superpositionsprinzip
- Dienstag, 22. Januar 2008:
- Homogene und inhomogene lineare Rekursionen mit konstanten Koeffizienten
- Charakteristische Gleichung
- Donnerstag, 17. Januar 2008:
- Graphentheorie
- Dienstag, 22. Januar 2008:
- Gerichtete und ungerichtete Graphen
- Schleifen, Mehrfachkanten und Multigraphen; schlichte Graphen
- Fragestellungen und Anwendungen: Färbung
- Donnerstag, 24. Januar 2008:
- Fragestellungen und Anwendungen: Euler'sche und Hamilton'sche Wege, das Rundreiseproblem, kürzeste Wege, planare Graphen, optimale Netzwerke
- Grad eines Knotens, Untergraphen und induzierte Untergraphen
- Spezielle Graphen: vollständiger Graph, vollständiger bipartiter Graph, Hyperwürfel, Kreis, Weg
- Isomorphe Graphen
- Erreichbarkeit und Zusammenhang, Zusammenhangskomponenten
- Bäume und Spannbäume
- Dienstag, 29. Januar 2008:
- Charakterisierung von Bäumen
- Existenz eines Spannbaumes
- Charakterisierung von bipartiten Graphen
- Donnerstag, 31. Januar 2008:
- Darstellung von Graphen
- Gerichtete und geordnete Bäume
- Euler'sche Graphen
- Planare Graphen und die Euler'sche Polyederformel
- Dienstag, 5. Februar 2008:
- Maximale Kantenzahl planarer Graphen
- Polyeder, konvexe Mengen
- Paarungen
- Hall-Bedingung, Heiratssatz
- Wegesuchprobleme in der künstlichen Intelligenz
- Dienstag, 22. Januar 2008:
- Logik: Resolution
- Donnerstag, 7. Februar 2007:
- Resolvent, Resolutionssatz für die Aussagenlogik
- Dienstag, 12. Februar 2008:
- Hornklauseln und 2-SAT
- Der Satz von Schröder-Bernstein
- Donnerstag, 14. Februar 2007:
- Satz von Erdös und Szekeres über monotone Teilfolgen
- Das 15er-Spiel
- Zerlegung in Rechtecke mit einer ganzzahlige Seite
- Donnerstag, 7. Februar 2007: