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.
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).
Funktionen; Modellierung mit Wertebereichen;"Sätze" und "Beweise"; Beweistechniken "direkter Beweis", "Beweis durch Kontraposition", "Beweis durch Widerspruch"
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.
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.
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.
Wahrheitswert; Intuitive Bedeutung der Semantik; Graphische Darstellung von Formeln
Wahrheitstafeln; Erfüllbarkeit und Allgemeingültigkeit
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.
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.
Graphen und Bäume: Grundlegende Definitionen;
Darstellung von Graphen (abstrakt, graphisch,
Adjazenzliste, Adjazenzmatrix)
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].
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.
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".
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)
Äquivalenzrelationen; Ordnungsrelationen; der reflexive und transitive Abschluss
Die Architektur von Suchmaschinen; der Page-Rank einer Webseite; der Zufalls-Surfer
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.
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).
Markov-Ketten; Existenz und Eindeutigkeit
eines Tupels, das die Page-Rank-Eigenschaft besitzt; die effiziente Berechnung des Page-Ranks
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.
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).
Einführung in die Syntax und Semantik der Logik erster Stufe
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
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).
Formale Semantik der Logik erster Stufe; Formeln zur
Beschreibung von Datenbankanfragen; Erfüllbarkeit und
Äquivalenz; die Grenzen der Ausdrucksstärke
Endliche Automaten: Motivation und Beispiele
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
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).
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).
Kontextfreie Grammatiken zur Modellierung von Strukturen
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].
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).
Ausblick auf weitere Modellierungstechniken: Petri-Netze und das Entity-Relationship-Modell
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.