Aktueller Eintrag

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
  • Funktionen; Modellierung mit Wertebereichen;"Sätze" und "Beweise"; Beweistechniken "direkter Beweis", "Beweis durch Kontraposition", "Beweis durch Widerspruch" [Flash | QuickTime | Mobile | MP3]
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
  • Semantische Folgerung; Äquivalenz; Normalformen [Flash | QuickTime | Mobile | MP3]
  • Graphen und Bäume: Grundlegende Definitionen; Darstellung von Graphen (abstrakt, graphisch, Adjazenzliste, Adjazenzmatrix) [Flash | QuickTime | Mobile | MP3]
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
  • Wege; Hamilton-Kreise; Euler-Kreise; Isomorphie; Matchings; bipartite Graphen; konfliktfreie Färbungen [Flash | QuickTime | Mobile | MP3]
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
  • Äquivalenzrelationen; Ordnungsrelationen; der reflexive und transitive Abschluss [Flash | QuickTime | Mobile | MP3]
  • Die Architektur von Suchmaschinen; der Page-Rank einer Webseite; der Zufalls-Surfer [Flash | QuickTime | Mobile | MP3]
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
  • Markov-Ketten; Existenz und Eindeutigkeit eines Tupels, das die Page-Rank-Eigenschaft besitzt; die effiziente Berechnung des Page-Ranks [Flash | QuickTime | Mobile | MP3]
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
  • Formale Semantik der Logik erster Stufe; Formeln zur Beschreibung von Datenbankanfragen; Erfüllbarkeit und Äquivalenz; die Grenzen der Ausdrucksstärke [Flash | QuickTime | Mobile | MP3]
  • Endliche Automaten: Motivation und Beispiele [Flash | QuickTime | Mobile | MP3]
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
  • Ausblick auf weitere Modellierungstechniken: Petri-Netze und das Entity-Relationship-Modell [Flash | QuickTime | Mobile | MP3]
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