Hier finden Sie (nach den Vorlesungen) Informationen zum Inhalt der einzelnen Vorlesungsstunden sowie gelegentlich ergänzende Bemerkungen.

1. Mi, 14.10.2009:
   Kapitel 1: Einführung ins Thema "Diskrete Modellierung". Organisatorisches. Beginn mit Kapitel 2: Modellierung mit Wertebereichen – mathematische Grundlagen und Beweistechniken (heute: Mengen).
   Material: Skript, Seiten 7-27 (bis incl. Notation 2.8).  
   Weitere Lektüre: Kapitel 1 und 2.1 in [KKB].

2. Mi, 21.10.2009:
   Weiter mit Kapitel 2: Mengenalgebra, Potenzmengen, kartesische Produkte, Worte, Relationen, Funktionen
   Im Anschluss an die Vorlesung fand eine Fragestunde statt.
   Material: Skript, Seiten 28-37 (bis incl. Bemerkung 2.35).  
   Weitere Lektüre: Kapitel 2 in [KKB].  
   Übungsaufgaben: Blatt 1 ausgeteilt.

3. Mi, 28.10.2009:
   Weiter mit Kapitel 2 (heute: Eigenschaften von Funktionen; Multimengen; ein Beispiel zur Modellierung mit Wertebereichen; Einführung in verschiedene Beweistechniken)
   Material: Skript, Seiten 38-44 (bis incl. Satz 2.46).  
   Weitere Lektüre: Kapitel 2 in [KKB];   Kapitel 3, 6 und 7 in [MM];   siehe auch [B]. .
   Übungsaufgaben: Blatt 2 ausgeteilt.

4. Mi, 04.11.2009:
   Abschluss von Kapitel 2 (heute: Beweise durch Widerspruch; Beweise per Induktion; Rekursive Definition von Funktionen und Mengen)
   Im Anschluss an die Vorlesung fand eine Fragestunde statt.
   Material: Skript, Seiten 45-55 (bis zum Ende von Kapitel 2).   Beachten Sie: Seit dem 02.11.09 ist eine neue Version des Skripts erhältlich (Änderungen im Vergleich zur alten Version: überarbeitete Version von Kapitel 3 sowie kleine Korrekturen und Ergänzungen in Kapitel 1 und 2).
   Weitere Lektüre: Kapitel 3, 6 und 7 in [MM];   siehe auch [B].  
   Übungsaufgaben: Blatt 3 ausgeteilt.

5. Mi, 11.11.2009:
   Beginn mit Kapitel 3: Aussagenlogik (heute: Klärung der Frage "Wozu Logik im Informatik-Studium?"; Syntax und Semantik der Aussagenlogik; Syntaxbäume; ASCII-Repräsentation von Formeln; Wahrheitstafeln; Formelchecker (tks.AL); Erfüllbarkeit und Allgemeingültigkeit; semantische Folgerung)
   Material: Skript, Seiten 62-75 (bis incl. Beobachtung 3.26) sowie (tks.AL) — Formelchecker für die Aussagenlogik.
   Weitere Lektüre: Kapitel 4.1 in [KKB];   Kapitel 1 und Kapitel 2.A in [KK];   Einleitung und Kapitel 1.1 in [S-Logik].
   Vorsicht: Jedes dieser Bücher verwendet unterschiedliche Notationen, die wiederum etwas von den in der Vorlesungen eingeführten Notationen abweichen. Für die Lösung der Übungsaufgaben verwenden Sie bitte die in der Vorlesung eingeführten Notationen.
   Übungsaufgaben: Blatt 4 ausgeteilt.

6. Mi, 18.11.2009:
   Abschluss von Kapitel 3 (heute: logische Äquivalenz, DNF, KNF, NNF, ein KNF-Algorithmus, ein DNF-Algorithmus, effizienter Erfüllbarkeitstest für DNF-Formeln).
   Beginn mit Kapitel 4: Graphen und Bäume (heute: grundlegende Definitionen zu gerichteten und ungerichteten Graphen, Modellierungsbeispiele, Darstellung von Graphen durch Adjazenzlisten und Adjazenzmatrizen, die Begriffe "Weg", "Kreis", "einfacher Kreis")
   Material: Skript, Seiten 76-97 (bis incl. Definition 4.12).  
   Weitere Lektüre: Kapitel 4.1 in [KKB];   Kapitel 1 und Kapitel 2.A in [KK];   Kapitel 1.2 in [S-Logik].
   Kapitel 5.1 und 5.2 in [KKB];   Teile von Kapitel 0 und Kapitel 8 in [D];   Kapitel 7 in [LPV].
   Übungsaufgaben: Blatt 5 ausgeteilt.

7. Mi, 25.11.2009:
   Weiter mit Kapitel 4: Graphen und Bäume (heute: "zusammenhängend", "stark zusammenhängend", "Hamilton-Kreise", Das Königsberger Brückenproblem, ein Satz über die Existenz von Euler-Kreisen und Euler-Wegen, "Teilgraph", "induzierter Teilgraph", "Isomorphismus", Zuordnungsprobleme, Matchings, bipartite Graphen, Modellierung mit Hilfe von Konfliktgraphen).
   Im Anschluss an die Vorlesung fand eine Fragestunde statt.
   Material: Skript, Seiten 97-107 (bis incl. Beispiel 4.34).
   Weitere Lektüre: Kapitel 5.2, 5.3 und 5.5 in [KKB];   Teile der Kapitel 0, 1, 3, 4 in [D];   Kapitel 7 in [LPV].
   Übungsaufgaben: Blatt 6 ausgeteilt.

8. Mi, 02.12.2009:
   Weiter mit Kapitel 4: Graphen und Bäume (heute: konfliktfreie Knotenfärbung, planare Graphen, chromatische Zahl, ungerichtete Bäume, Spannbäume, gerichtete Bäume, Binärbäume, Modellierungsbeispiele, einige spezielle Arten von Graphen: vollständiger Graph, vollständiger bipartiter Graph)
   Im Anschluss an die Vorlesung fand eine Fragestunde statt.
   Material: Skript, Seiten 109-124 (bis direkt vor Definition 4.67).   Beachten Sie: Seit dem 01.12.09 ist eine neue Version des Skripts erhältlich (Änderungen im Vergleich zur alten Version: überarbeitete Version von Kapitel 4 sowie kleine Korrekturen und Ergänzungen in den Kapiteln 1 bis 3).
   Weitere Lektüre: Kapitel 5.3 und 5.4 in [KKB], Kapitel 8 und 13 in [LPV] sowie Kapitel 11 in [MM].
   Übungsaufgaben: Blatt 7 ausgeteilt. Hinweis: In Übungsblatt 7 hat sich ein kleiner Fehler eingeschlichen: Im Text der Aufgabe 1 ist von den Radiostationen r₁,...,r₇ die Rede, in der dazugehörigen Abbildung sind die Radiostationen r₁ bis r₉ abgebildet. Bitte behandeln Sie in Ihrer Lösung zur Aufgabe 1 alle Radiostationen r₁ bis r₉. Eine aktualisierte Version des Übungsblattes finden Sie hier.

9. Mi, 09.12.2009:
   Abschluss von Kapitel 4: Graphen und Bäume (heute: die Begriffe "reflexiv", "symmetrisch", "antisymmetrisch", "transitiv", "konnex"; Äquivalenzrelationen; Präordnungen, partielle Ordnungen, lineare Ordnungen; die transitive und reflexive Hülle einer Relation).
   Beginn mit Kapitel 5: Markov-Ketten als Grundlage der Funktionsweise von Suchmaschinen im Internet (heute: die Architektur von Suchmaschinen, der Page-Rank einer Webseite, der Zufalls-Surfer).
   Im Anschluss an die Vorlesung fand eine Fragestunde statt.
   Material: Skript, Seiten 124-141 (bis zum Ende von Abschnitt 5.3).   Beachten Sie: Seit dem 08.12.09 ist eine neue Version des Skripts erhältlich (Änderungen im Vergleich zur alten Version: überarbeitete Version von Kapitel 5).
   Weitere Lektüre: Kapitel 4 in [MM], Kapitel 1.1 in [J] und Kapitel 2 in [S-IA]. Viele weitere Informationen und Literaturhinweise zum Thema Suchmaschinen finden sich auf der Webseite von Martin Sauerhoffs Vorlesung Internet Algorithmen an der TU Dortmund; siehe http://ls2-www.cs.uni-dortmund.de/lehre/winter200910/IntAlg/. Ein kurzer und allgemein verständlicher Überblick über das Page-Rank Verfahren wird in dem Spiegel-Online Artikel Wie Google mit Milliarden Unbekannten rechnet von Holger Dambeck gegeben.
   Übungsaufgaben: Blatt 8 ausgeteilt.

10. Mi, 16.12.2009:
    Abschluss von Kapitel 5: Markov-Ketten als Grundlage der Funktionsweise von Suchmaschinen im Internet (heute: Beweis von Satz 5.7(a); Markov-Ketten; Existenz und Eindeutigkeit eines Tupels, das die Page-Rank-Eigenschaft besitzt; ergodische Markov-Ketten; die effiziente Berechnung des Page-Ranks).
    Im Anschluss an die Vorlesung fand eine Fragestunde statt.
    Material: Skript, Seite 137 und Seiten 141-146 (bis zum Ende von Kapitel 5).   Beachten Sie: Seit dem 12.12.09 ist eine neue Version des Skripts erhältlich (Änderungen im Vergleich zur alten Version: überarbeitete Version von Kapitel 5).
    Weitere Lektüre: Kapitel 2 in [S-IA]. Viele weitere Informationen und Literaturhinweise zum Thema Suchmaschinen finden sich auf der Webseite von Martin Sauerhoffs Vorlesung Internet Algorithmen an der TU Dortmund; siehe http://ls2-www.cs.uni-dortmund.de/lehre/winter200910/IntAlg/. Ein kurzer und allgemein verständlicher Überblick über das Page-Rank Verfahren wird in dem Spiegel-Online Artikel Wie Google mit Milliarden Unbekannten rechnet von Holger Dambeck gegeben.
    Übungsaufgaben: Blatt 9 ausgeteilt.

11. Mi, 13.01.2010:
    Start mit Kapitel 6: Logik erster Stufe (Prädikatenlogik) (heute: Motivation zur Logik erster Stufe; Strukturen; Syntax der Logik erster Stufe; Beispiele zur Semantik der Logik erster Stufe).
    Im Anschluss an die Vorlesung fand eine Fragestunde statt.
    Material: Skript, Seiten 147-155.  
    Weitere Lektüre: Kapitel 2.1 in [S-Logik];   Kapitel 4.A in [KK];   Kapitel 4.2 in [KKB].
    Vorsicht: Jedes dieser Bücher verwendet unterschiedliche Notationen, die wiederum etwas von den in der Vorlesungen eingeführten Notationen abweichen. Für die Lösung der Übungsaufgaben verwenden Sie bitte die in der Vorlesung eingeführten Notationen.
    Übungsaufgaben: Blatt 10 ausgeteilt.

12. Mi, 20.01.2010:
    Abschluss von Kapitel 6: Logik erster Stufe (Prädikatenlogik) (heute: formale Definition der Semantik der Logik erster Stufe; Erfüllbarkeit, Allgemeingültigkeit, logische Äquivalenz, semantische Folgerung; Grenzen der Logik erster Stufe; Anwendung der Logik erster Stufe als Anfragesprache für Datenbanken).
    Im Anschluss an die Vorlesung fand eine Fragestunde statt.
    Material: Skript, Seiten 156-165.   Beachten Sie: Seit dem 20.01.10 ist eine neue Version des Skripts erhältlich (Änderungen im Vergleich zur alten Version: überarbeitete Version von Kapitel 6).
    Weitere Lektüre: Kapitel 2 in [S-Logik];   Kapitel 4.A in [KK];   Kapitel 4.2 in [KKB].
    Übungsaufgaben: Blatt 11 ausgeteilt.

13. Mi, 27.01.2010:
    Start mit Kapitel 7: Endliche Automaten zur Modellierung von Abläufen (heute: DFAs, NFAs, viele Beispiele, die Äquivalenz von NFAs und DFAs: die Potenzmengenkonstruktion, reguläre Sprachen, Vorarbeiten zum Pumping-Lemma)
    Im Anschluss an die Vorlesung fand eine Fragestunde statt.
    Material: Skript, Seiten 169-181.   Beachten Sie: Seit dem 26.01.10 ist eine neue Version des Skripts erhältlich (Änderungen im Vergleich zur alten Version: überarbeitete Version der Kapitel 7, 8 und 9).
    Weitere Lektüre: Kapitel 2.1-2.3 und 2.8 in [HU];   Kapitel 4 in [W-Komp];   Kapitel 4.1, 4.3 und 4.4 in [W-Theo]. Kapitel 7.1 in [KKB];  
    Übungsaufgaben: Blatt 12 ausgeteilt.

14. Mi, 03.02.2010:
    Abschluss von Kapitel 7: Endliche Automaten zur Modellierung von Abläufen (heute: das Pumping-Lemma; reguläre Ausdrücke; Ausblick)
    Kapitel 8: Kontextfreie Grammatiken zur Modellierung von Strukturen (Syntax und Semantik von KFGs; Beispiele; Ausblick).
    Im Anschluss an die Vorlesung fand eine Fragestunde statt.
    Material: Skript, Seiten 181-198.  
    Weitere Lektüre: Kapitel 2.5, 3.1-3.3 und 4.1-4.3 in [HU];   Kapitel 1.2 und 1.3 in [S-Theo];   Kapitel 7.1 und 6.1-6.2 in [KKB];   Kapitel 4 und 6 in [W-Komp];   Kapitel 4.1 und 6.1 in [W-Theo].
    Übungsaufgaben: Blatt 13 ausgeteilt.

15. Mi, 10.02.2010:
    Kapitel 9: Ausblick auf weitere Modellierungstechniken (heute: Petri-Netze zur Modellierung von Abläufen; das Entity-Relationship-Modell zur Modellierung von Datenbanken).
    Abschließende Bemerkungen zum Ablauf der Klausur und Hilfestellungen für Ihre Klausurvorbereitungen gegeben (Details: hier).
    Im Anschluss an die Vorlesung fand eine Fragestunde statt.
    Material: Skript, Seiten 200-210.  
    Weitere Lektüre: Kapitel 7.2, 6.3 und 8 in [KKB];   einen umfassenden Überblick zum Thema Petri-Netze gibt das Buch [R]; eine Einführung ins Entity-Relationship-Modell gibt das Buch [HS].