Logbuch: Diskrete Modellierung
Vorlesung im WS 2011/12
Hier finden Sie (nach den Vorlesungen) Informationen zum Inhalt der einzelnen Vorlesungsstunden sowie gelegentlich ergänzende Bemerkungen.
- Mi, 19.10.2011
-
Eröffnungsveranstaltung.
Kapitel 1: Einführung ins Thema "Diskrete
Modellierung". Organisatorisches. Beginn mit Kapitel 2:
Mathematische Grundlagen und
Beweistechniken - heute: Mengen.
- Material:
- Skript, Seiten 1-27 (bis inkl. Beweis von Satz 2.6)
- Vortragsfolien
- Videoaufzeichnung der Vorlesung: Die E-Lectures zu den Themen
- Weitere Lektüre:
- Kapitel 1 und 2.1 in [KBB]
- Übungsaufgaben:
- Ein Blatt mit Präsenzaufgaben (deren Lösung in der ersten Übungsstunde besprochen wird) wurde ausgeteilt.
Im Anschluss an die Vorlesung fand eine Fragestunde statt, in der u.a. Hinweise zur Lösung des Blatts mit den Präsenzaufgaben gegeben wurden.
- Mi, 26.10.2011
-
Weiter mit Kapitel 2:
Mathematische Grundlagen und
Beweistechniken - heute:
Mengenalgebra, Potenzmengen, kartesische Produkte, Worte,
Relationen.
- Material:
- Skript, Seiten 27-38 (bis inkl. Notation 2.28)
- Vortragsfolien
- Videoaufzeichnung der Vorlesung: Die E-Lecture zum Thema
- Weitere Lektüre:
- Kapitel 1 in [J] und Kapitel 2 in [KBB]
- Übungsaufgaben:
- Übungsblatt 1 wurde ausgeteilt.
Im Anschluss an die Vorlesung fand eine Fragestunde statt, in der u.a. Hinweise zur Lösung von Übungsblatt 1 gegeben wurden.
- Mi, 02.11.2011
-
Weiter mit Kapitel 2:
Mathematische Grundlagen und
Beweistechniken - heute:
Funktionen, Multimengen, ein Beispiel zur
Modellierung mit Wertebereichen, Was sind "Sätze" und "Beweise"?, Einführung in verschiedene
Beweistechniken (direkte Beweise, Beweis durch Kontraposition,
Beweis durch Widerspruch).
- Material:
- Skript, Seiten 38-47 (bis direkt vor Satz 2.47)
- Vortragsfolien
- Videoaufzeichnung der Vorlesung: Die E-Lecture zum Thema
- 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.
Im Anschluss an die Vorlesung fand eine Fragestunde statt, in der u.a. Hinweise zur Lösung von Übungsblatt 2 gegeben wurden.
- Mi, 09.11.2011
-
Abschluss von Kapitel 2:
Mathematische Grundlagen und
Beweistechniken - heute:
Beweis durch Widerspruch, Beweis per Induktion, rekursive
Definition von Funktionen und Mengen.
- Material:
- Skript, Seiten 47-57 (bis zum Ende von Kapitel 2)
- Vortragsfolien
- Videoaufzeichnung der Vorlesung: Die E-Lecture zum Thema
- 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.
Im Anschluss an die Vorlesung fand eine Fragestunde statt, in der u.a. Hinweise zur Lösung von Übungsblatt 3 gegeben wurden.
- Mi, 16.11.2011
-
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.
- Material:
- Skript, Seiten 68-81 (bis zum Ende von Abschnitt 3.3)
- (tks.AL) — Formelchecker für die Aussagenlogik
- Vortragsfolien
- Videoaufzeichnung der Vorlesung: Die E-Lectures zu den Themen
- Weitere Lektüre:
-
Kapitel 1 und Kapitel 2.A
in [KK];
Einleitung und Kapitel 1.1
in [S-Logik];
Kapitel 4.1 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 4 wurde ausgeteilt.
Im Anschluss an die Vorlesung fand eine Fragestunde statt, in der u.a. Hinweise zur Lösung von Übungsblatt 4 gegeben wurden.
- Mi, 23.11.2011
-
Abschluss von Kapitel 3: Aussagenlogik - heute:
semantische Folgerung; logische Äquivalenz; Normalformen (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; Darstellungen von Graphen: abstrakt, graphisch, durch Adjazenzlisten bzw. durch Adjazenzmatrizen.- Material:
- Skript, Seiten 81-105 (bis inkl. Bemerkung 4.11)
- (tks.AL) — Formelchecker für die Aussagenlogik
- Vortragsfolien
- Videoaufzeichnung der Vorlesung: Die E-Lectures zu den Themen
- Weitere Lektüre:
- Kapitel 1 und Kapitel 2.A in [KK]; Einleitung und Kapitel 1.2 in [S-Logik]; Kapitel 4.1 und 5.2 in [KKB]; Teile von Kapitel 0 und Kapitel 8 in [D]; Kapitel 7 in [LPV].
- Übungsaufgaben:
- Übungsblatt 5 wurde ausgeteilt.
Im Anschluss an die Vorlesung fand eine Fragestunde statt, in der u.a. Hinweise zur Lösung von Übungsblatt 5 gegeben wurden.
- Mi, 30.11.2011
-
Weiter mit Kapitel 4: Graphen und Bäume - heute:
die Begriffe "Weg", "Kreis", "einfacher Kreis",
"zusammenhängend", "stark zusammenhängend", "Hamilton-Kreis", 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.
Hinweis: Am Freitag, 02.12.2011 um 9:30 Uhr besteht die Möglichkeit, an einem Test zur Einschätzung des derzeitigen Kenntnisstands in den Bereichen "Diskrete Modellierung", "Grundlagen der Programmierung 1" und "Analysis und Lineare Algebra für die Informatik" teilzunehmen. Der Test findet in Hörsaal H V 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 01.12.2011 in der Vorlesung behandelten Stoff.- Material:
- Skript, Seiten 105-118 (bis inkl. Beispiel 4.37)
- Vortragsfolien
- Videoaufzeichnung der Vorlesung: Die E-Lecture zum Thema
- 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.
Im Anschluss an die Vorlesung fand eine Fragestunde statt, in der u.a. Hinweise zur Lösung von Übungsblatt 6 gegeben wurden.
- Mi, 07.12.2011
-
Weiter mit Kapitel 4: Graphen und Bäume - heute: das 4-Farben-Problem,
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".
- Material:
- Skript, Seiten 118-132 (bis inkl. Definition 4.68)
- Vortragsfolien
- Videoaufzeichnung der Vorlesung: Die E-Lecture zum Thema
- 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.
Im Anschluss an die Vorlesung fand eine Fragestunde statt, in der u.a. Hinweise zur Lösung von Übungsblatt 7 gegeben wurden.
- Mi, 14.12.2011
-
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).- Material:
- Skript, Seiten 133-155 (bis zum Ende von Abschnitt 5.3; der Beweis von Satz 5.7 wird erst in der nächsten Vorlesungsstunde behandelt)
- Vortragsfolien
- Videoaufzeichnung der Vorlesung: Die E-Lectures zu den Themen
- 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/winter200911/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.
Im Anschluss an die Vorlesung fand eine Fragestunde statt, in der u.a. Hinweise zur Lösung von Übungsblatt 8 gegeben wurden.
- Mi, 21.12.2011
-
Abschluss von Kapitel 5: Markov-Ketten als Grundlage der
Funktionsweise von Suchmaschinen im Internet (heute:
Beweis von Satz 5.7; Markov-Ketten; Existenz und Eindeutigkeit
eines Tupels, das die Page-Rank-Eigenschaft besitzt; ergodische
Markov-Ketten; die effiziente Berechnung des Page-Ranks).
- Material:
- Skript, Seiten 153-160 (bis zum Ende von Kapitel 5)
- Vortragsfolien
- Videoaufzeichnung der Vorlesung: Die E-Lecture zum Thema
- 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.
Im Anschluss an die Vorlesung fand eine Fragestunde statt, in der u.a. Hinweise zur Lösung von Übungsblatt 9 gegeben wurden.
- Mi, 11.01.2012
-
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).
- Material:
- Skript, Seiten 161-171 (bis inkl. Beispiel 6.23).
- Vortragsfolien
- Videoaufzeichnung der Vorlesung: Die E-Lecture zum Thema
- 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.
Im Anschluss an die Vorlesung fand eine Fragestunde statt, in der u.a. Hinweise zur Lösung von Übungsblatt 10 gegeben wurden.
- Mi, 18.01.2012
-
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).
Start mit Kapitel 7: Endliche Automaten zur Modellierung von Abläufen (heute: Motivation und Beispiele).- Material:
- Skript, Seiten 171-189.
- Vortragsfolien
- Videoaufzeichnung der Vorlesung: Die E-Lectures zu den Themen
- 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.
Im Anschluss an die Vorlesung fand eine Fragestunde statt, in der u.a. Hinweise zur Lösung von Übungsblatt 11 gegeben wurden.
- Mi, 25.01.2012
-
Weiter 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, Pumping-Lemma).
- Material:
- Skript, Seiten 197-207 (bis Satz 7.17).
- Vortragsfolien
- Videoaufzeichnung der Vorlesung: Die E-Lecture zum Thema
- 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.
Im Anschluss an die Vorlesung fand eine Fragestunde statt, in der u.a. Hinweise zur Lösung von Übungsblatt 12 gegeben wurden.
- Mi, 01.02.2012
-
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).- Material:
- Skript, Seiten 207-227 (bis zum Ende von Kapitel 8).
- Vortragsfolien
- Videoaufzeichnung der Vorlesung: Die E-Lectures zum Thema
- 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.
Im Anschluss an die Vorlesung fand eine Fragestunde statt, in der u.a. Hinweise zur Lösung von Übungsblatt 13 gegeben wurden.
- Mi, 08.02.2012
-
Kapitel 9: Ausblick auf weitere Modellierungstechniken (heute:
Petri-Netze zur Modellierung von Abläufen; das
Entity-Relationship-Modell zur Modellierung von Datenbanken; eine Fallstudie).
- Material:
- Skript, Kapitel 9.
- Vortragsfolien
- Videoaufzeichnung der Vorlesung: Die E-Lecture zum Thema
- 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].
Im Anschluss an die Vorlesung fand eine Fragestunde statt, in der u.a. die Lösung der Aufgaben 2 und 4 von Übungsblatt 13 besprochen wurden.
- Mi, 15.02.2012
-
Hilfestellungen zur Klausurvorbereitung. Insbes.: Details zum
Ablauf der Klausur, eine Beispiel-Aufgabe zum Thema "Page-Rank",
Durcharbeiten von Teilen der Klausur aus dem
Sommersemester 2011.
- Material:
- Skript, Kapitel 10.
- Eine alte Klausur (aus dem Sommersemester 2011)
- Videoaufzeichnung der Vorlesung: Die E-Lecture zum Thema