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

Mi, 20.10.2010
Eröffnungsveranstaltung. Kapitel 1: Einführung ins Thema "Diskrete Modellierung". Organisatorisches. Beginn mit Kapitel 2: Mathematische Grundlagen und Beweistechniken (Modellierung mit Wertebereichen) - heute: Mengen.
Material:
Skript, Seiten 1-27 (bis inkl. Beweis von Satz 2.6)
Weitere Lektüre:
Kapitel 1 und 2.1 in [KBB]
Übungsaufgaben:
Ein Blatt mit Präsenzaufgaben wurde online gestellt.
Mi, 27.10.2010
Weiter mit Kapitel 2: Mathematische Grundlagen und Beweistechniken (Modellierung mit Wertebereichen) - heute: Mengenalgebra, Potenzmengen, kartesische Produkte, Worte, Relationen, Funktionen.
Im Anschluss an die Vorlesung fand eine Fragestunde statt, in der u.a. Hinweise zur Lösung von Übungsblatt 1 gegeben sowie die Aufgaben 1(a) und 2(a) des Präsenzblatts besprochen wurden.
Material:
Skript, Seiten 27-38 (bis inkl. Definition 2.31)
Weitere Lektüre:
Kapitel 1 in [J] und Kapitel 2 in [KBB]
Übungsaufgaben:
Übungsblatt 1 wurde ausgeteilt.
Mi, 03.11.2010
Weiter mit Kapitel 2: Mathematische Grundlagen und Beweistechniken (Modellierung mit Wertebereichen) - heute: Eigenschaften von Funktionen, Multimengen, ein Beispiel zur Modellierung mit Wertebereichen, Einführung in verschiedene Beweistechniken (direkte Beweise, Beweis durch Kontraposition, Beweis durch Widerspruch).
Im Anschluss an die Vorlesung fand eine Fragestunde statt, in der u.a. Hinweise zur Lösung von Übungsblatt 2 gegeben sowie Aufgabe 1 von Übungsblatt 1 besprochen wurde.
Material:
Skript, Seiten 38-46 (bis inkl. Satz 2.46)
Weitere Lektüre:
Kapitel 1 und 2.3 in [J] und Kapitel 3, 6 und 7 in [MM]; siehe auch [B]
Übungsaufgaben:
Übungsblatt 2 wurde ausgeteilt.
Mi, 10.11.2010
Abschluss von Kapitel 2: Mathematische Grundlagen und Beweistechniken (Modellierung mit Wertebereichen) - heute: Beweis durch Widerspruch, Beweis per Induktion, rekursive Definition von Funktionen und Mengen.
Im Anschluss an die Vorlesung fand eine Fragestunde statt, in der u.a. Hinweise zur Lösung von Übungsblatt 3 gegeben sowie Aufgabe 2 von Übungsblatt 2 besprochen wurde.
Material:
Skript, Seiten 46-56 (bis zum Ende von Kapitel 2)
Weitere Lektüre:
Kapitel 1 und 2.3-2.4 in [J] und Kapitel 3, 6 und 7 in [MM]; siehe auch [B]
Übungsaufgaben:
Übungsblatt 3 wurde ausgeteilt.
Mi, 17.11.2010
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; Formelchecker (tks.AL); Wahrheitstafeln; Erfüllbarkeit und Allgemeingültigkeit.
Im Anschluss an die Vorlesung fand eine Fragestunde statt, in der u.a. Hinweise zur Lösung von Übungsblatt 4 gegeben sowie Aufgabe 4(a) von Übungsblatt 3 besprochen wurde.
Material:
Skript, Seiten 67-79 (bis inkl. Beobachtung 3.23) 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:
Übungsblatt 4 wurde ausgeteilt.
Mi, 24.11.2010
Abschluss von Kapitel 3: Aussagenlogik - heute: semantische Folgerung; 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".
Im Anschluss an die Vorlesung fand eine Fragestunde statt, in der u.a. Hinweise zur Lösung von Übungsblatt 5 gegeben sowie Aufgabe 4 von Übungsblatt 4 besprochen wurde.
Material:
Skript, Seiten 79-104 (bis inkl. Definition 4.12) sowie (tks.AL) — Formelchecker für die Aussagenlogik
Weitere Lektüre:
Kapitel 4.1 und 5.2 in [KKB]; Kapitel 1 und Kapitel 2.A in [KK]; Einleitung und Kapitel 1.2 in [S-Logik]; Teile von Kapitel 0 und Kapitel 8 in [D]; Kapitel 7 in [LPV].
Übungsaufgaben:
Übungsblatt 5 wurde ausgeteilt.
Mi, 01.12.2010
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, konfliktfreie Knotenfärbung.
Im Anschluss an die Vorlesung fand eine Fragestunde statt, in der u.a. Hinweise zur Lösung von Übungsblatt 6 gegeben und Fragen zum Stoff der heutigen Vorlesung geklärt wurden.

Hinweis: Am Freitag, 03.12.2010 um 10:00-12:00 Uhr besteht die Möglichkeit, an einem Test zur Einschätzung des derzeitigen Kenntnisstands in den Bereichen "Diskrete Modellierung", "Programmierung 1" bzw. "Analysis und Lineare Algebra (für Informatiker)" teilzunehmen. Der Test findet in Hörsaal H I statt und wird von Prof. Krömker organisiert.
Wir empfehlen allen Teilnehmer/innen der Veranstaltung Diskrete Modellierung, an diesem Test teilzunehmen. Der Test ist nicht klausurrelevant, und das Testergebnis wird keinen Einfluss auf die Modulabschlussnote nehmen - aber der Test kann jedem/r Teilnehmer/in wertvolle Hinweise zur Selbsteinschätzung seines/ihres derzeitigen Kenntnisstands im Bereich "Diskrete Modellierung" geben. Die Themen, die bei diesem Test abgefragt werden, umfassen den bis zum 02.12.2010 in der Vorlesung behandelten Stoff.

Material:
Skript, Seiten 105-117 (bis inkl. Beispiel 4.37)
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:
Übungsblatt 6 wurde ausgeteilt.
Mi, 08.12.2010
Weiter mit Kapitel 4: Graphen und Bäume - heute: 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, die Begriffe "reflexiv", "symmetrisch", "antisymmetrisch", "transitiv" und "konnex".
Im Anschluss an die Vorlesung fand eine Fragestunde statt, in der u.a. Hinweise zur Lösung von Übungsblatt 7 gegeben und Fragen zum Stoff der Vorlesung und Übung geklärt wurden.
Material:
Skript, Seiten 117-131 (bis inkl. Definition 4.68)
Weitere Lektüre:
Kapitel 5.3 und 5.4 in [KKB]; Kapitel 8 und 13 in [LPV]; Kapitel 11 in [MM].
Übungsaufgaben:
Übungsblatt 7 wurde ausgeteilt.
Mi, 15.12.2010
Abschluss von Kapitel 4: Graphen und Bäume - heute: die Begriffe Äquivalenzrelationen; Präordnungen, partielle Ordnungen, lineare Ordnungen; die transitive und reflexive Hülle einer Relation.
Beginn von 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, in der u.a. Hinweise zur Lösung von Übungsblatt 8 gegeben und Fragen zum Stoff der Vorlesung und Übung geklärt wurden.
Material:
Skript, Seiten 132-153 (bis inkl. Notation 5.8)
Weitere Lektüre:
Kapitel 4 in [MM]; Kapitel 1.1 in [J]; 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:
Übungsblatt 8 wurde ausgeteilt.
Mi, 22.12.2010
Abschluss von Kapitel 5: Markov-Ketten als Grundlage der Funktionsweise von Suchmaschinen im Internet (heute: Beweis von Satz 5.7(b); 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, in der u.a. Hinweise zur Lösung von Übungsblatt 9 gegeben und Fragen zum Stoff der Vorlesung und Übung geklärt wurden.
Material:
Skript, Seiten 153-158 (bis zum Ende 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:
Übungsblatt 9 wurde ausgeteilt.
Mi, 12.01.2011
Start mit Kapitel 6: Logik erster Stufe (Prädikatenlogik) (heute: Motivation zur Logik erster Stufe; Strukturen; Terme; Syntax der Logik erster Stufe; Beispiele zur Semantik der Logik erster Stufe).
Im Anschluss an die Vorlesung fand eine Fragestunde statt, in der u.a. Hinweise zur Lösung von Übungsblatt 10 gegeben und Fragen zum Stoff der Vorlesung und Übung geklärt wurden.
Material:
Skript, Seiten 160-170 (bis inkl. Beispiel 6.23). Hinweis: Seit dem 11.01.2011 gibt es eine neue Version des Skripts, die eine überarbeitete und umstrukturierte Fassung von Kapitel 6 enthält; Details finden Sie hier.
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:
Übungsblatt 10 wurde ausgeteilt.
Mi, 19.01.2011
Abschluss von Kapitel 6: Logik erster Stufe (Prädikatenlogik) (heute: formale Definition der Semantik der Logik erster Stufe; Anwendung der Logik erster Stufe als Datenbank-Anfragesprache Erfüllbarkeit, Allgemeingültigkeit, logische Äquivalenz, semantische Folgerung; Grenzen der Logik erster Stufe).
Im Anschluss an die Vorlesung fand eine Fragestunde statt, in der u.a. Hinweise zur Lösung von Übungsblatt 11 gegeben und Fragen zum Stoff der Vorlesung und Übung geklärt wurden.
Material:
Skript, Seiten 170-178 (bis zum Ende von Kapitel 6).
Weitere Lektüre:
Kapitel 2 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:
Übungsblatt 11 wurde ausgeteilt.
Mi, 26.01.2011
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).
Im Anschluss an die Vorlesung fand eine Fragestunde statt, in der u.a. Hinweise zur Lösung von Übungsblatt 12 gegeben und Fragen zum Stoff der Vorlesung und Übung geklärt wurden.
Material:
Skript, Seiten 185-196 (bis direkt vor Beispiel 7.16).
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:
Übungsblatt 12 wurde ausgeteilt.
Mi, 02.02.2011
Abschluss von Kapitel 7: Endliche Automaten zur Modellierung von Abläufen (heute: 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, in der u.a. Hinweise zur Lösung von Übungsblatt 13 gegeben und Fragen zum Stoff der Vorlesung und Übung geklärt wurden.
Material:
Skript, Seiten 196-217 (bis zum Ende von Kapitel 8).
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:
Übungsblatt 13 wurde ausgeteilt.
Mi, 09.02.2011
Kapitel 9: Ausblick auf weitere Modellierungstechniken (heute: Petri-Netze zur Modellierung von Abläufen; das Entity-Relationship-Modell zur Modellierung von Datenbanken; eine Fallstudie).
Im Anschluss an die Vorlesung fand eine Fragestunde statt, in der u.a. Hinweise zur Lösung von Übungsblatt 14 gegeben und Fragen zum Stoff der Vorlesung und Übung geklärt wurden.
Material:
Skript, Seiten 220-234 (bis zum Ende von Kapitel 9).
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 geben die Bücher [KE] und [HS].
Übungsaufgaben:
Übungsblatt 14 wurde ausgeteilt.
Mi, 16.02.2011
Hilfestellungen zur Klausurvorbereitung. Insbes.: Details zum Ablauf der Klausur, eine Beispiel-Aufgabe zum Thema "Page-Rank", Durcharbeiten von Teilen der Beispiel-Klausur aus dem Sommersemester 2009 (siehe Skript ab Seite 237).
Im Anschluss an die Vorlesung fand eine Fragestunde statt, in der Teile der Lösung von Übungsblatt 14 besprochen wurden.
Material:
Skript, ab Seite 237 (Kapitel 10: Beispielklausuren).