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 2007/2008

 

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

  1. Mi, 17.10.2007:
    Kapitel 1: Einführung ins Thema "Diskrete Modellierung" (Abschnitt 1.1: Klärung der Frage "Wozu diskrete Modellierung im Informatik-Studium?"; Abschnitt 1.2: Organisatorisches; Abschnitt 1.3: Allgemeiner Modellbegriff)
    Material: Vorlesungsmitschrift.  
    Weitere Lektüre: Kapitel 1 in [KKB].

  2. Mi, 24.10.2007:
    Start mit Kapitel 2: Modellierung mit Wertebereichen – mathematische Grundlagen und Beweistechniken (heute: Mengen, Mengenalgebra, Potenzmengen, kartesische Produkte)
    Material: Vorlesungsmitschrift.  
    Weitere Lektüre: Kapitel 2 in [KKB].  
    Übungsaufgaben: Blatt 1 ausgeteilt.

  3. Mi, 31.10.2007:
    Weiter mit Kapitel 2: Modellierung mit Wertebereichen – mathematische Grundlagen und Beweistechniken (heute: Worte, Sprachen, Relationen, Funktionen; Abschnitt 2.2: Ein Beispiel zur Modellierung mit Wertebereichen)
    Material: Vorlesungsmitschrift.  
    Weitere Lektüre: Kapitel 2 in [KKB].
    Übungsaufgaben: Blatt 2 ausgeteilt.

  4. Mi, 07.11.2007:
    Abschluss von Kapitel 2: Modellierung mit Wertebereichen – mathematische Grundlagen und Beweistechniken (heute: Abschnitt 2.3: Beweise verstehen und selbst formulieren; Abschnitt 2.4: Rekursive Definitionen von Funktionen und Mengen)
    Material: Vorlesungsmitschrift.  
    Weitere Lektüre: Kapitel 3, 6 und 7 in [MM];   siehe auch [B].
    Übungsaufgaben: Blatt 3 ausgeteilt.

  5. Mi, 14.11.2007:
    Start mit Kapitel 3: Logik (Teil I) – Aussagenlogik (heute: Abschnitt 3.1: Klärung der Frage "Wozu Logik im Informatik-Studium?"; Abschnitt 3.2: Aussagenlogik, heute insbesondere: Syntax, Semantik, Wahrheitstafeln)
    Im Anschluss an die Vorlesung fand eine Fragestunde statt.
    Material: Vorlesungsmitschrift.  
    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, 21.11.2007:
    Weiter mit Kapitel 3: Logik (Teil I) – Aussagenlogik (heute: Folgerung, Äquivalenz, Normalformen)
    Im Anschluss an die Vorlesung fand eine Fragestunde statt.
    Material: Vorlesungsmitschrift.  
    Weitere Lektüre: Kapitel 4.1 in [KKB];   Kapitel 1 und Kapitel 2.A in [KK];   Kapitel 1.2 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 5 ausgeteilt.

  7. Mi, 28.11.2007:
    Abschluss von Kapitel 3: Logik (Teil I) – Aussagenlogik (heute: ein Algorithmus zur effizienten Lösung des Erfüllbarkeitsproblems für DNF-Formeln).
    Start mit Kapitel 4: Graphen und Bäume (heute: grundlegende Definitionen bzgl. ungerichteten und gerichteten Graphen, einige Modellierungsbeispiele, Darstellung von Graphen durch Adjazenzlisten und Adjazenzmatrizen, Wege, Zusammenhangskomponenten, starke Zusammenhangskomponenten, Hamilton-Kreise).
    Material: Vorlesungsmitschrift.  
    Weitere Lektüre: Kapitel 5.1 und 5.2 in [KKB];   Teile von Kapitel 0 und Kapitel 8 in [D];   Kapitel 7 in [LPV].
    Übungsaufgaben: Blatt 6 ausgeteilt. Hinweis: Aufgabe 2(b) und 2(e) werden von Blatt 6 gestrichen, da die darin verwendeten Begriffe in der Vorlesung vom 28.11.07 noch nicht behandelt wurden.

  8. Mi, 05.12.2007:
    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).
    Material: Vorlesungsmitschrift.  
    Weitere Lektüre: Kapitel 5.2 und 5.5 in [KKB];   Teile der Kapitel 0, 1, 3, 4 in [D];   Kapitel 7 in [LPV].
    Übungsaufgaben: Blatt 7 ausgeteilt. Hinweis: Aufgabe 1(b) wird von Blatt 7 gestrichen, da die darin verwendeten Begriffe in der Vorlesung vom 05.12.07 noch nicht behandelt wurden.

  9. Mi, 12.12.2007:
    Abschluss von Kapitel 4: Graphen und Bäume (heute: Abschnitt 4.2: Bäume (ungerichtete Bäume, gerichtete Bäume, Modellierungsbeispiele); Abschnitt 4.3: Einige spezielle Arten von Graphen (vollständiger Graph, vollständiger bipartiter Graph, Äquivalenzrelationen, Ordnungsrelationen))
    Material: Vorlesungsmitschrift.  
    Weitere Lektüre: Kapitel 5.3 und 5.4 in [KKB];   Kapitel 4 und 11 in [MM].
    Übungsaufgaben: Blatt 8 ausgeteilt.

  10. Mi, 19.12.2007:
    Start mit Kapitel 5: Logik (Teil II) — Logik erster Stufe (Prädikatenlogik) (heute: Abschnitt 5.1: Motivation zur Logik erster Stufe; Abschnitt 5.2: Strukturen; Abschnitt 5.3: Syntax der Logik erster Stufe; Abschnitt 5.4: Beispiele zur Semantik der Logik erster Stufe)
    Material: Vorlesungsmitschrift.  
    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 2 wird von Blatt 9 gestrichen und auf Blatt 10 verschoben, da die darin verwendeten Begriffe in der Vorlesung vom 19.12.07 noch nicht behandelt wurden. Die Punkteverteilung ist wie folgt: 24+18 Punkte auf Aufgabe 1, 13+15 Punkte auf Aufgabe 3 und 3 Mal 10 Punkte auf Aufgabe 4.

  11. Mi, 09.01.2008:
    Abschluss von Kapitel 5: Logik (Teil II) — Logik erster Stufe (Prädikatenlogik) (heute: Abschnitt 5.5: Semantik der Logik erster Stufe; Abschnitt 5.6: Ein Anwendungsbereich der Logik erster Stufe: Datenbanken).
    Material: Vorlesungsmitschrift.  
    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, 16.01.2008:
    Start mit Kapitel 6: Modellierung von Strukturen (heute: Abschnitt 6.1: Das Entity-Relationship-Modell; Start mit Abschnitt 6.2: Kontextfreie Grammatiken).
    Im Anschluss an die Vorlesung fand eine Fragestunde statt.
    Material: Vorlesungsmitschrift.  
    Weitere Lektüre: Kapitel 6.2 und 6.1 in [KKB];   Kapitel 6.1 in [W-Theo].
    Übungsaufgaben: Blatt 11 (Beispielklausur) ausgeteilt.

  13. Mi, 23.01.2008:
    Abschluss von Kapitel 6: Modellierung von Strukturen (heute: Abschnitt 6.2: Kontextfreie Grammatiken).
    Start mit Kapitel 7: Modellieren von Abläufen (heute: Start mit Abschnitt 6.1: Endliche Automaten).
    Im Anschluss an die Vorlesung fand eine Fragestunde statt.
    Material: Vorlesungsmitschrift.  
    Weitere Lektüre: Kapitel 6.1 und 7.1 in [KKB];   Kapitel 5.1-5.3, 1.1 und 2.1-2.2 in [HMU];   Kapitel 6.1 und 4.1 in [W-Komp];   Kapitel 6.1 und 4.1 in [W-Theo].
    Übungsaufgaben: Blatt 12 ausgeteilt.

  14. Mi, 30.01.2008:
    Weiter mit Abschnitt 6.1: Endliche Automaten (heute: deterministische endliche Automaten, nicht-deterministische endliche Automaten, reguläre Ausdrücke).
    Material: Vorlesungsmitschrift.  
    Weitere Lektüre: Kapitel 7.1 in [KKB];   Kapitel 2.1-2.4, 3.1 und 3.3 in [HMU];   Kapitel 1.2 in [S-Theo];   Kapitel 4.1 und 4.2 in [W-Komp].
    Übungsaufgaben: Blatt 13 ausgeteilt.

  15. Mi, 06.02.2008:
    Abschließende Bemerkungen zu Abschnitt 6.1: Endliche Automaten. Abschnitt 6.2: Petri-Netze und Kapitel 8: Eine Fallstudie (Autowerkstatt) behandelt. Abschließende Bemerkungen zum Ablauf der Klausur und Hilfestellungen für Ihre Klausurvorbereitungen gegeben (Details: hier).
    Material: Vorlesungsmitschrift.  
    Weitere Lektüre: Kapitel 7.2, 8.1.1 und 8.1.3 in [KKB].

 

Last modified: Wed Feb 6 15:51:55 GMT 2008
Nicole Schweikardt