Theorie komplexer Systeme
Prof. Dr. Nicole Schweikardt
Institut für Informatik
Johann Wolfgang Goethe-Universität
Frankfurt am Main

Logbuch zur Vorlesung Diskrete Modellierung
Wintersemester 2008/2009

 

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

  1. Mi, 15.10.2008:
    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 1-18.  
    Weitere Lektüre: Kapitel 1 und 2.1 in [KKB].

  2. Mi, 22.10.2008:
    Weiter mit Kapitel 2 (heute: Mengenalgebra, Potenzmengen, kartesische Produkte, Worte, Relationen, Funktionen)
    Material: Skript, Seiten 19-30.  
    Weitere Lektüre: Kapitel 2 in [KKB].  
    Übungsaufgaben: Blatt 1 ausgeteilt.

  3. Mi, 29.10.2008:
    Weiter mit Kapitel 2 (heute: Multimengen; ein Beispiel zur Modellierung mit Wertebereichen; Einführung in verschiedene Beweistechniken)
    Material: Skript, Seiten 30-39.  
    Weitere Lektüre: Kapitel 2 in [KKB];   Kapitel 3, 6 und 7 in [MM];   siehe auch [B]. .
    Übungsaufgaben: Blatt 2 ausgeteilt.

  4. Mi, 05.11.2008:
    Abschluss von Kapitel 2 (heute: Beweise per Induktion; Rekursive Definition von Funktionen und Mengen)
    Beginn mit Kapitel 3: Aussagenlogik (heute: Klärung der Frage "Wozu Logik im Informatik-Studium?"; Syntax und Semantik der Aussagenlogik)
    Material: Skript, Seiten 39-57.  
    Weitere Lektüre: Kapitel 3, 6 und 7 in [MM];   siehe auch [B];   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 3 ausgeteilt.

  5. Mi, 12.11.2008:
    Weiter mit Kapitel 3 (heute: Syntaxbäume, ASCII-Repräsentation von Formeln, Formelchecker (tks.AL), Wahrheitstafeln, semantische Folgerung, logische Äquivalenz, DNF, KNF)
    Material: Skript, Seiten 57-68 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, 19.11.2008:
    Abschluss von Kapitel 3 (heute: 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 Kreise", "zusammenhängend", "stark zusammenhängend", "Hamilton-Kreis")
    Material: Skript, Seiten 69-85.  
    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, 26.11.2008:
    Weiter mit Kapitel 4: Graphen und Bäume (heute: das Königsberger Brückenproblem, ein Satz über die Existenz von Euler-Kreisen und Euler-Wegen; die Begriffe "Teilgraph", "induzierter Teilgraph", "Isomorphismus" geklärt; Zuordnungsprobleme, Matchings, bipartite Graphen, Modellierung mit Hilfe von Konfliktgraphen, konfliktfreie Knotenfärbung, planare Graphen; viele Modellierungsbeispiele; ungerichtete Bäume; Spannbäume).
    Material: Skript, Seiten 86-97.  
    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, 03.12.2008:
    Weiter mit Kapitel 4: Graphen und Bäume (heute: ungerichtete Bäume, gerichtete Bäume, Modellierungsbeispiele, Entscheidungsbäume, einige spezielle Arten von Graphen: vollständiger Graph, vollständiger bipartiter Graph, Äquivalenzrelationen)
    Material: Skript, Seiten 98-107.  
    Weitere Lektüre: Kapitel 5.3 und 5.4 in [KKB];   Kapitel 4 und 11 in [MM].
    Übungsaufgaben: Blatt 7 ausgeteilt (Hinweis: Aufgabe 4(d) wird von Blatt 7 gestrichen, da die darin verwendeten Begriffe in der Vorlesung vom 03.12.08 noch nicht behandelt wurden).

  9. Mi, 10.12.2008:
    Abschluss von Kapitel 4: Graphen und Bäume (heute: weitere Beispiele für Äquivalenzrelationen; Präordnungen, partielle Ordnungen, lineare Ordnungen; die transitive und reflexive Hülle einer Relation).
    Start mit Kapitel 5: Logik erster Stufe (Prädikatenlogik) (heute: Motivation zur Logik erster Stufe; Strukturen; Syntax der Logik erster Stufe)
    Material: Skript, Seiten 107-122.  
    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 8 ausgeteilt. Hinweis: Aufgabe 2(b) wird von Blatt 8 gestrichen, da die darin verwendeten Begriffe in der Vorlesung vom 10.12.2008 noch nicht behandelt wurden.

  10. Mi, 17.12.2008:
    Weiter mit Kapitel 5: Logik erster Stufe (Prädikatenlogik) (heute: Beispiele zur Semantik der Logik erster Stufe; formale Definition der Semantik der Logik erster Stufe; Erfüllbarkeit, Allgemeingültigkeit, logische Äquivalenz, semantische Folgerung; Beginn mit dem Abschnitt "Ein Anwendungsbereich der Logik erster Stufe: Datenbanken").
    Material: Skript, Seiten 122-130.  
    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 9 ausgeteilt.
    Hinweis: Aufgabe 6 wird von Blatt 9 gestrichen, da die darin verwendeten Begriffe in der Vorlesung vom 17.12.2008 noch nicht behandelt wurden.
    Noch ein Hinweis: Blatt 9 (insbesondere die Aufgaben 1–4) stellt ein Beispiel dafür dar, welchen Schwierigkeitsgrad die Aufgaben in der Klausur haben könnten. Als Beispiele für wirkliche Klausuren können Sie auch die Klausur aus dem Wintersemester 2007/08 und die Klausur aus dem Sommersemester 2008 betrachten.

  11. Mi, 14.01.2009:
    Abschluss von Kapitel 5 (heute: Anwendung der Logik erster Stufe als Anfragesprache für Datenbanken).
    Start mit Kapitel 6: Modellierung von Strukturen (heute: das Entity-Relationship-Modell).
    Material: Skript, Seiten 128-143.  
    Weitere Lektüre: Kapitel 6.2 in [KKB].
    Übungsaufgaben: Blatt 10 ausgeteilt.

  12. Mi, 23.01.2008:
    Abschluss von Kapitel 6: Modellierung von Strukturen (heute: Kontextfreie Grammatiken).
    Start mit Kapitel 7: Modellieren von Abläufen (heute: Start mit Abschnitt 7.1: Endliche Automaten).
    Im Anschluss an die Vorlesung fand eine Fragestunde statt.
    Material: Skript, Seiten 143-154 und Seiten 155-158.  
    Weitere Lektüre: Kapitel 6.1 und 7.1 in [KKB];   Kapitel 4.1-4.3 und 2.1 in [HU];   Kapitel 6.1 und 4.1 in [W-Komp];   Kapitel 6.1 und 4.1 in [W-Theo].
    Übungsaufgaben: Blatt 11 ausgeteilt.

  13. Mi, 28.01.2009:
    Weiter mit Abschnitt 7.1: Endliche Automaten (heute: deterministische endliche Automaten, nicht-deterministische endliche Automaten, das Pumping-Lemma).
    Im Anschluss an die Vorlesung fand eine Fragestunde statt.
    Material: Skript, Seiten 158-165 sowie Notizen zum Pumping-Lemma.
    Weitere Lektüre: Kapitel 7.1 in [KKB];   Kapitel 2.1-2.3, 2.8 und 3.1 in [HU];   Kapitel 1.2 in [S-Theo];   Kapitel 4.1 und 4.2 in [W-Komp].
    Übungsaufgaben: Blatt 12 ausgeteilt.

  14. Mi, 04.02.2009:
    Abschluss von Kapitel 7: reguläre Ausdrücke; Petri-Netze.
    Kapitel 8: Eine Fallstudie (Autowerkstatt). 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 165-177 sowie Aufgabe 5 (a) und (b) der Klausur aus dem Wintersemester 2007/08.
    Weitere Lektüre: Kapitel 7.1.1, 7.2, 8.1.1 und 8.1.3 in [KKB];   Kapitel 2.5 in [HU];   Kapitel 1.2.3 in [S-Theo];   einen umfassenden Überblick zum Thema Petri-Netze gibt das Buch [R].

  15. Mi, 11.02.2009:
    Kapitel 9: Markov-Ketten als Grundlage der Funktionsweise von Suchmaschinen im Internet.
    Material: Skript, Kapitel 9 (zur Zeit leider nur handschriftlich).
    Weitere Lektüre: Kapitel 2 in [S-IA] (das Skript zu Prof. Schnitgers Vorlesung "Internet Algorithmen" finden Sie hier).

 

Last modified: Wed Feb 11 11:40:09 CET 2009
Nicole Schweikardt