Current entry

Logfile: Diskrete Modellierung

Lecture  in Winter 2012/13

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


  1. Di, 16.10.2012
  2. Eröffnungsveranstaltung. Kapitel 1: Einführung ins Thema "Diskrete Modellierung". Organisatorisches.
    Material:
    Skript, Seiten 1-23
    Vortragsfolien
    Videoaufzeichnung der Vorlesung aus dem WS 11/12: Die E-Lecture zum Thema
    Weitere Lektüre:
    Kapitel 1 und 2.1 in [KBB]
  3. Do, 18.10.2012
  4. Beginn mit Kapitel 2: Mathematische Grundlagen und Beweistechniken - heute: Mengen.
    Material:
    Skript, Seiten 24-29
    Vortragsfolien
    Videoaufzeichnung der Vorlesung aus dem WS 11/12: Die E-Lecture zum Thema
    Weitere Lektüre:
    Kapitel 1 und 2.1 in [KBB]

    Im Anschluss an die Vorlesung fand eine Fragestunde statt, in der die Aufgaben 1 und 3 des Präsenzblatts aus dem WS 11/12 besprochen wurden.

  5. Di, 23.10.2012
  6. Weiter mit Kapitel 2: Mathematische Grundlagen und Beweistechniken - heute: Mengenalgebra, Potenzmengen, kartesische Produkte.
    Material:
    Skript, Seiten 29-36 (bis inkl. Beispiel 2.19)
    Vortragsfolien
    Videoaufzeichnung der Vorlesung: Die E-Lecture zum Thema
    Weitere Lektüre:
    Kapitel 1 in [J] und Kapitel 2 in [KBB]
    Übungsaufgaben:
    Das Präsenzblatt sowie das Übungsblatt 1 wurden online gestellt.
  7. Do, 25.10.2012
  8. Weiter mit Kapitel 2: Mathematische Grundlagen und Beweistechniken - heute: kartesische Produkte, Worte, Relationen.
    Material:
    Skript, Seiten 36-39 (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]

    Im Anschluss an die Vorlesung fand eine Fragestunde statt, in der u.a. Hinweise zur Lösung von Übungsblatt 1 gegeben wurden.

  9. Di, 30.10.2012
  10. Weiter mit Kapitel 2: Mathematische Grundlagen und Beweistechniken - heute: Funktionen und Multimengen.
    Material:
    Skript, Seiten 40-44 (bis inkl. Beispiel 2.42)
    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.
  11. Do, 01.11.2012
  12. Weiter mit Kapitel 2: Mathematische Grundlagen und Beweistechniken - heute: ein Beispiel zur Modellierung mit Wertebereichen, Was sind "Sätze" und "Beweise"?, Einführung in verschiedene Beweistechniken: direkte Beweise, Beweis durch Kontraposition.
    Material:
    Skript, Seiten 45-47 (bis inkl. Satz 2.44)
    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]

    Im Anschluss an die Vorlesung fand eine Fragestunde statt, in der u.a. Hinweise zur Lösung von Übungsblatt 2 gegeben wurden.

  13. Di, 06.11.2012
  14. Weiter mit Kapitel 2: Mathematische Grundlagen und Beweistechniken - heute: Beweis durch Widerspruch, Beweis per Induktion.
    Material:
    Skript, Seiten 48-54 (bis inkl. Beispiel 2.52)
    Vortragsfolien
    Videoaufzeichnung der Vorlesung: Die E-Lectures zu den Themen
    • Funktionen; Modellierung mit Wertebereichen; "Sätze" und "Beweise"; Beweistechniken "direkter Beweis", "Beweis durch Kontraposition", "Beweis durch Widerspruch" [Flash | QuickTime | Mobile | MP3]
    • Induktion und Rekursion [Flash | QuickTime | Mobile | MP3]
    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.
    Anmerkung: Aufgabe 4 wird von Blatt 3 gestrichen (und auf Blatt 4 verschoben), da die darin verwendeten Begriffe in den Vorlesungen vom 6.11.12 und 8.11.12 noch nicht behandelt wurden. Die Punkte für die auf Blatt 3 verbleibenden Aufgaben werden wie folgt verteilt: Aufgabe 1: 40 Punkte, Aufgabe 2: 27 Punkte, Aufgabe 3: 33 Punkte.
  15. Do, 08.11.2012
  16. Weiter mit Kapitel 2: Mathematische Grundlagen und Beweistechniken - heute: rekursive Definition von Funktionen.
    Material:
    Skript, Seiten 54-57 (bis inkl. Bemerkung 2.56)
    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]

    Im Anschluss an die Vorlesung fand eine Fragestunde statt, in der u.a. Hinweise zur Lösung von Übungsblatt 3 gegeben wurden.
    Anmerkung: Aufgabe 4 wird von Blatt 3 gestrichen (und auf Blatt 4 verschoben), da die darin verwendeten Begriffe in den Vorlesungen vom 6.11.12 und 8.11.12 noch nicht behandelt wurden. Die Punkte für die auf Blatt 3 verbleibenden Aufgaben werden wie folgt verteilt: Aufgabe 1: 40 Punkte, Aufgabe 2: 27 Punkte, Aufgabe 3: 33 Punkte.

  17. Di, 13.11.2012
  18. Abschluss von Kapitel 2: Mathematische Grundlagen und Beweistechniken - heute: rekursive Definition von Mengen.
    Beginn mit Kapitel 3: Aussagenlogik - heute: Klärung der Frage "Wozu Logik im Informatik-Studium?"; Syntax der Aussagenlogik; Beispiele
    Material:
    Skript, Seiten 57-75 (bis direkt vor Definition 3.8)
    Vortragsfolien
    Videoaufzeichnung der Vorlesung: Die E-Lectures zu den Themen
    Weitere Lektüre:
    Zu Kapitel 2: Kapitel 1 und 2.3-2.4 in [J] und Kapitel 3, 6 und 7 in [MM]; siehe auch [B]

    Zu Kapitel 3: 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.
  19. Do, 15.11.2012
  20. Weiter mit Kapitel 3: Aussagenlogik - heute: Semantik der Aussagenlogik; Syntaxbäume; ASCII-Repräsentation von Formeln; Wahrheitstafeln; Formelchecker (tks.AL).
    Material:
    Skript, Seiten 75-83 (bis direkt vor Satz 3.20)
    (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.

    Im Anschluss an die Vorlesung fand eine Fragestunde statt, in der u.a. Hinweise zur Lösung von Übungsblatt 4 gegeben wurden.

  21. Di, 20.11.2012
  22. Weiter mit Kapitel 3: Aussagenlogik - heute: Erfüllbarkeit und Allgemeingültigkeit; semantische Folgerung; logische Äquivalenz; Normalformen: DNF, KNF, NNF
    Material:
    Skript, Seiten 83-91 (bis direkt vor Beobachtung 3.37)
    (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].
    Übungsaufgaben:
    Übungsblatt 5 wurde ausgeteilt.
  23. Do, 22.11.2012
  24. Abschluss von Kapitel 3: Aussagenlogik - heute: Umformung einer Formel in eine äquivalente Formel in DNF, KNF oder NNF; ein effizienter Erfüllbarkeitstest für DNF-Formeln.
    Material:
    Skript, Seiten 91-106 (bis zum Ende von Kapitel 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.2 in [S-Logik]; Kapitel 4.1 und 5.2 in [KKB].

    Im Anschluss an die Vorlesung fand eine Fragestunde statt, in der u.a. Hinweise zur Lösung von Übungsblatt 5 gegeben wurden.

  25. Di, 27.11.2012
  26. 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. 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.
    Material:
    Skript, Seiten 107-118 (bis direkt vor Beispiel 4.20)
    Vortragsfolien
    Videoaufzeichnung der Vorlesung: Die E-Lecture zum Thema
    • Graphen und Bäume: Grundlegende Definitionen; Darstellung von Graphen (abstrakt, graphisch, Adjazenzliste, Adjazenzmatrix) [Flash | QuickTime | Mobile | MP3]
    • Wege; Hamilton-Kreise; Euler-Kreise; Isomorphie; Matchings; bipartite Graphen; konfliktfreie Färbungen [Flash | QuickTime | Mobile | MP3]
    Weitere Lektüre:
    Teile der Kapitel 0, 1, 3, 4, 8 in [D]; Kapitel 7 in [LPV]; Kapitel 5.2, 5.3 und 5.5 in [KKB].
    Übungsaufgaben:
    Übungsblatt 6 wurde ausgeteilt.
  27. Di, 27.11.2012
  28. Weiter mit Kapitel 4: Graphen und Bäume - heute: Ähnlichkeit von Graphen (Teilgraph, induzierter Teilgraph, Isomorphismus), Zuordnungsprobleme, Matchings, bipartite Graphen.
    Material:
    Skript, Seiten 118-124 (bis direkt vor Beispiel 4.34)
    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:
    Teile der Kapitel 0, 1, 3, 4, 8 in [D]; Kapitel 7 in [LPV]; Kapitel 5.2, 5.3 und 5.5 in [KKB].

    Im Anschluss an die Vorlesung fand eine Fragestunde statt, in der u.a. Hinweise zur Lösung von Übungsblatt 6 gegeben wurden.

  29. Di, 04.12.2012
  30. Weiter mit Kapitel 4: Graphen und Bäume - heute: Modellierung mit Hilfe von Konfliktgraphen, konfliktfreie Knotenfärbung, das 4-Farben-Problem, planare Graphen, chromatische Zahl, ungerichtete Bäume, Spannbäume, gerichtete Bäume.
    Material:
    Skript, Seiten 124-134 (bis inkl. Notation 4.55)
    Vortragsfolien
    Videoaufzeichnung der Vorlesung: Die E-Lectures zu den Themen
    • Wege; Hamilton-Kreise; Euler-Kreise; Isomorphie; Matchings; bipartite Graphen; konfliktfreie Färbungen [Flash | QuickTime | Mobile | MP3]
    • Ungerichtete bzw. gerichtete Bäume; einige spezielle Arten von Graphen [Flash | QuickTime | Mobile | MP3]
    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.
  31. Do, 06.12.2012
  32. Weiter mit Kapitel 4: Graphen und Bäume - heute: Binärbäume, Modellierungsbeispiele, einige spezielle Arten von Graphen: vollständiger Graph, vollständiger bipartiter Graph
    Material:
    Skript, Seiten 134-140 (bis direkt vor Beginn des Abschnitts "4.3.2 Spezielle gerichtete Graphen")
    Vortragsfolien
    Videoaufzeichnung der Vorlesung: Die E-Lectures zu den Themen
    Weitere Lektüre:
    Kapitel 5.3 und 5.4 in [KKB]; Kapitel 8 und 13 in [LPV]; Kapitel 11 in [MM].

    Im Anschluss an die Vorlesung fand eine Fragestunde statt, in der u.a. Hinweise zur Lösung von Übungsblatt 7 gegeben wurden.

  33. Di, 11.12.2012
  34. Abschluss von Kapitel 4: Graphen und Bäume - heute: die Begriffe "reflexiv", "symmetrisch", "antisymmetrisch", "transitiv" und "konnex" eingeführt; Äquivalenzrelationen und Äquivalenzklassen betrachtet; Präordnungen, partielle Ordnungen, lineare Ordnungen betrachtet; die transitive und reflexive Hülle einer Relation definiert.
    Beginn von Kapitel 5: Markov-Ketten als Grundlage der Funktionsweise von Suchmaschinen im Internet - heute: die Architektur von Suchmaschinen, der Page-Rank einer Webseite.
    Material:
    Skript, Seiten 140-163 (bis zum Anfang von Abschnitt 5.2)
    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.
  35. Do, 13.12.2012
  36. Weiter mit Kapitel 5: Markov-Ketten als Grundlage der Funktionsweise von Suchmaschinen im Internet - heute: die Page-Rank-Eigenschaft, der Zufalls-Surfer, die Page-Rank-Matrix.
    Material:
    Skript, Seiten 163-167 (bis inkl. Beispiel 5.6)
    Vortragsfolien
    Videoaufzeichnung der Vorlesung: Die E-Lecture zum Thema
    • Die Architektur von Suchmaschinen; der Page-Rank einer Webseite; der Zufalls-Surfer [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/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.

    Im Anschluss an die Vorlesung fand eine Fragestunde statt, in der u.a. Hinweise zur Lösung von Übungsblatt 8 gegeben wurden.

  37. Di, 18.12.2012
  38. Weiter mit Kapitel 5: Markov-Ketten als Grundlage der Funktionsweise von Suchmaschinen im Internet - heute: Korrespondenz zwischen der Page-Rank-Eigenschaft und Eigenvektoren zum Eigenwert 1 der Page-Rank-Matrix; Markov-Ketten; Existenz und Eindeutigkeit eines Tupels, das die Page-Rank-Eigenschaft besitzt; ergodische Markov-Ketten.
    Material:
    Skript, Seiten 167-172 (bis direkt vor Beobachtung 5.19)
    Vortragsfolien
    Videoaufzeichnung der Vorlesung: Die E-Lectures zu den Themen
    • Die Architektur von Suchmaschinen; der Page-Rank einer Webseite; der Zufalls-Surfer [Flash | QuickTime | Mobile | MP3]
    • 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.
    Hinweis: Auf der in der Vorlesung ausgeteilten Version von Übungsblatt 9 hat sich in Aufgabe 4b ein Fehler eingeschlichen: Die Werte der unteren Zeile der Matrix PA wurden vertauscht. In der hier verfügbaren Version von Blatt 9 wurde dieser Fehler behoben.
  39. Do, 20.12.2012
  40. Abschluss von Kapitel 5: Markov-Ketten als Grundlage der Funktionsweise von Suchmaschinen im Internet - heute: die effiziente Berechnung des Page-Rank.
    Material:
    Skript, Seiten 172-174 (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.

    Im Anschluss an die Vorlesung fand eine Fragestunde statt, in der u.a. Hinweise zur Lösung von Übungsblatt 9 gegeben wurden.

  41. Di, 15.01.2013
  42. Start mit Kapitel 6: Logik erster Stufe (Prädikatenlogik) - heute: Motivation zur Logik erster Stufe; Strukturen; Isomorphie; Syntax und Semantik von Termen.
    Material:
    Skript, Seiten 178-184 (bis inkl. Beispiel 6.17).
    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.
    Hinweis: Auf der in der Vorlesung ausgeteilten Version von Übungsblatt 10 war die Nummerierung der Aufgabenteile von Aufgabe 2a inkonsistent. In der hier verfügbaren Version von Blatt 10 wurde diese Inkonsistenz behoben.
  43. Do, 17.01.2013
  44. Weiter mit Kapitel 6: Logik erster Stufe (Prädikatenlogik) - heute: Syntax der Logik erster Stufe; Beispiele zur Semantik der Logik erster Stufe.
    Material:
    Skript, Seiten 184-188 (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.

    Im Anschluss an die Vorlesung fand eine Fragestunde statt, in der alte Klausuraufgaben besprochen wurden - heute insbes. Aufgabe 5 ("Page-Rank") der Klausur aus dem WS 11/12 (siehe Kapitel 10 des Vorlesungsskripts).

  45. Di, 22.01.2013
  46. Weiter mit Kapitel 6: Logik erster Stufe (Prädikatenlogik) - heute: formale Definition der Semantik der Logik erster Stufe; Anwendung der Logik erster Stufe als Datenbank-Anfragesprache.
    Material:
    Skript, Seiten 188-195 (bis zum Ende von Kapitel 6.6).
    Vortragsfolien
    Videoaufzeichnung der Vorlesung: Die E-Lecture zum Thema
    • Formale Semantik der Logik erster Stufe; Formeln zur Beschreibung von Datenbankanfragen; Erfüllbarkeit und Äquivalenz; die Grenzen der Ausdrucksstärke [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.
    Mehr Hintergrundinformationen zum Thema "Logik und Datenbanken" werden in der folgenden E-Lecture der ersten Vorlesungenstunde der Veranstaltung Logik und Datenbanken gegeben:
    • Kapitel 0: Einführung ins Thema; Organisatorisches [Flash | QuickTime | Mobile | MP3] (Aufzeichnung vom 16.10.2012)
    Übungsaufgaben:
    Übungsblatt 11 wurde ausgeteilt.
  47. Do, 24.01.2013
  48. Abschluss von Kapitel 6: Logik erster Stufe (Prädikatenlogik) - heute: Beispiele zur Verwendung der Logik erster Stufe zum Formulieren von Datenbankanfragen; Erfüllbarkeit, Allgemeingültigkeit, logische Äquivalenz, semantische Folgerung; Grenzen der Logik erster Stufe.
    Material:
    Skript, Seiten 195-197 (bis zum Ende von Kapitel 6).
    Vortragsfolien
    Videoaufzeichnung der Vorlesung: Die E-Lecture zum Thema
    • Formale Semantik der Logik erster Stufe; Formeln zur Beschreibung von Datenbankanfragen; Erfüllbarkeit und Äquivalenz; die Grenzen der Ausdrucksstärke [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.

    Im Anschluss an die Vorlesung fand eine Fragestunde statt, in der alte Klausuraufgaben besprochen wurden - heute insbes. Aufgabe 1 ("Aussagenlogik") der Klausur aus dem WS 11/12 (siehe Kapitel 10 des Vorlesungsskripts).

  49. Di, 29.01.2013
  50. Start mit Kapitel 7: Endliche Automaten zur Modellierung von Abläufen - heute: Motivation, DFAs, NFAs, viele Beispiele
    Material:
    Skript, Seiten 205-214 (bis inkl. Definition 7.12).
    Vortragsfolien
    Videoaufzeichnung der Vorlesung: Die E-Lectures zu den Themen
    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.
  51. Do, 31.01.2013
  52. Weiter mit Kapitel 7: Endliche Automaten zur Modellierung von Abläufen - heute: Wiederholung "DFAs" und "NFAs"; die Äquivalenz von NFAs und DFAs (die Potenzmengenkonstruktion); reguläre Sprachen.
    Material:
    Skript, Seiten 214-216 (bis direkt vor Beispiel 7.16).
    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].

    Im Anschluss an die Vorlesung fand eine Fragestunde statt, in der alte Klausuraufgaben besprochen wurden - heute insbes. Aufgabe 3 ("Logik erster Stufe") der Klausur aus dem WS 11/12 (siehe Kapitel 10 des Vorlesungsskripts).

  53. Di, 05.02.2013
  54. Abschluss von Kapitel 7: Endliche Automaten zur Modellierung von Abläufen - heute: Pumping-Lemma inkl. Spiel-Charakterisierung und Anwendungsbeispiel; reguläre Ausdrücke; Ausblick.
    Material:
    Skript, Seiten 216-222 (bis zum Ende von Kapitel 7).
    Vortragsfolien
    Videoaufzeichnung der Vorlesung: Die E-Lecture zum Thema
    Weitere Lektüre:
    Kapitel 2.5, 3.1-3.3 in [HU]; Kapitel 1.2 in [S-Theo]; Kapitel 7.1 in [KKB]; Kapitel 4 in [W-Komp]; Kapitel 4.1 in [W-Theo].
    Übungsaufgaben:
    Übungsblatt 13 wurde ausgeteilt.
    Hinweis: Auf der in der Vorlesung ausgeteilten Version von Übungsblatt 13 haben sich zwei Fehler eingeschlichen. In Aufgabe 1(a) waren die Wörter w2 und w4 ein wenig langweilig, außerdem entsprachen die regulären Ausdrücke in Aufgabe 2(a) nicht der in der Vorlesung vorgestellten Syntax. In der hier verfügbaren Version von Blatt 13 wurden diese Fehler behoben.
  55. Do, 07.02.2013
  56. Start mit Kapitel 8: Kontextfreie Grammatiken zur Modellierung von Strukturen - heute: Syntax und Semantik von KFGs; Ableitungen und Ableitungsbäume; Beispiele.
    Material:
    Skript, Seiten 231-237 (bis inkl. Beispiel 8.8).
    Vortragsfolien
    Videoaufzeichnung der Vorlesung: Die E-Lecture zum Thema
    Weitere Lektüre:
    Kapitel 4.1-4.3 in [HU]; Kapitel 1.3 in [S-Theo]; Kapitel 6.1-6.2 in [KKB]; Kapitel 6 in [W-Komp]; Kapitel 6.1 in [W-Theo].

    Im Anschluss an die Vorlesung fand eine Fragestunde statt, in der die Anwendung des Pumping-Lemmas geübt wurde - insbes. Aufgabe 4(c) der Klausur aus dem WS 11/12 (siehe Kapitel 10 des Vorlesungsskripts) sowie Beispiel 7.20 aus dem Vorlesungsskript.

  57. Di, 12.02.2013
  58. Abschluss von Kapitel 8: Kontextfreie Grammatiken zur Modellierung von Strukturen - heute: weitere Beispiele für KFGs (Menüstrukturen, HTML-Tabellen); Ausblick.
    Start mit Kapitel 9: Ausblick auf weitere Modellierungstechniken - heute: Petri-Netze zur Modellierung von Abläufen.
    Material:
    Skript, Seiten 237-249 und 259-260 (d.h.: Rest von Kapitel 8, Kapitel 9.1 und 9.3.2).
    Vortragsfolien
    Videoaufzeichnung der Vorlesung: Die E-Lectures zu den Themen
    Weitere Lektüre:
    Kapitel 4.1-4.3 in [HU]; Kapitel 1.3 in [S-Theo]; Kapitel 6.1-6.2 in [KKB]; Kapitel 6 in [W-Komp]; Kapitel 6.1 in [W-Theo];
    Kapitel 7.2 und 8 in [KKB]; einen umfassenden Überblick zum Thema Petri-Netze gibt das Buch [R].
  59. Do, 14.02.2013
  60. Abschluss von Kapitel 9: Ausblick auf weitere Modellierungstechniken - heute: das Entity-Relationship-Modell zur Modellierung von Datenbanken.
    Material:
    Skript, Seiten 250-252 und 254-256 (ER-Modell ohne Kardinalitätsangaben).
    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 6.3 und 8 in [KKB]; 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 alte Klausuraufgaben besprochen wurden - heute insbes. Aufgabe 4 (a) und(b) ("reguläre Sprachen") der Klausur aus dem WS 11/12 (siehe Kapitel 10 des Vorlesungsskripts) sowie Aufgabe 3 (a) und (c) von Übungsblatt 13 ("reguläre Sprachen und Pumping-Lemma").

  61. Di, 19.02.2013
  62. Hilfestellungen zur Klausurvorbereitung. Insbes.: Details zum Ablauf der Klausur sowie Durcharbeiten der Aufgaben 2, 3(b)+(c) und 6 der Klausur aus dem WS 11/12 (siehe Kapitel 10 des Vorlesungsskripts).
    Material:
    Skript, Kapitel 10.
    Videoaufzeichnung der Vorlesung: Die E-Lecture zum Thema