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]
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.
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.
Di, 06.11.2012
Weiter mit Kapitel 2:
Mathematische Grundlagen und
Beweistechniken - heute:
Beweis durch Widerspruch, Beweis per Induktion.
Funktionen; Modellierung mit Wertebereichen; "Sätze" und "Beweise"; Beweistechniken "direkter Beweis", "Beweis durch Kontraposition", "Beweis durch Widerspruch"
Induktion und Rekursion
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.
Do, 08.11.2012
Weiter mit Kapitel 2:
Mathematische Grundlagen und
Beweistechniken - heute:
rekursive Definition von Funktionen.
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.
Di, 13.11.2012
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
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.
Weiter mit Kapitel 3: Aussagenlogik - heute:
Semantik der Aussagenlogik;
Syntaxbäume; ASCII-Repräsentation von Formeln; Wahrheitstafeln;
Formelchecker (tks.AL).
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.
Di, 20.11.2012
Weiter mit Kapitel 3: Aussagenlogik - heute:
Erfüllbarkeit und Allgemeingültigkeit;
semantische Folgerung; logische Äquivalenz; Normalformen: DNF,
KNF, NNF
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.
Wahrheitstafeln; Erfüllbarkeit und Allgemeingültigkeit
Semantische Folgerung; Äquivalenz; Normalformen
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.
Di, 27.11.2012
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.
Weiter mit Kapitel 4: Graphen und Bäume - heute:
Ähnlichkeit von Graphen (Teilgraph, induzierter
Teilgraph, Isomorphismus), Zuordnungsprobleme, Matchings,
bipartite Graphen.
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.
Di, 04.12.2012
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.
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")
Ungerichtete bzw. gerichtete Bäume; einige spezielle
Arten von Graphen
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.
Di, 11.12.2012
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.
Ungerichtete bzw. gerichtete Bäume; einige spezielle
Arten von Graphen
Ä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.
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.
Die Architektur von Suchmaschinen; der Page-Rank einer Webseite; der Zufalls-Surfer
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.
Di, 18.12.2012
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.
Die Architektur von Suchmaschinen; der Page-Rank einer Webseite; der Zufalls-Surfer
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.
Ü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.
Do, 20.12.2012
Abschluss von Kapitel 5: Markov-Ketten als Grundlage der
Funktionsweise von Suchmaschinen im Internet - heute:
die effiziente Berechnung des Page-Rank.
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.
Di, 15.01.2013
Start mit Kapitel 6: Logik erster Stufe (Prädikatenlogik) - heute:
Motivation zur Logik erster Stufe; Strukturen; Isomorphie; Syntax
und Semantik von Termen.
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.
Ü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.
Do, 17.01.2013
Weiter mit Kapitel 6: Logik erster Stufe (Prädikatenlogik) - heute:
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
alte Klausuraufgaben besprochen wurden - heute insbes.
Aufgabe 5 ("Page-Rank") der Klausur aus dem WS 11/12 (siehe Kapitel 10 des Vorlesungsskripts).
Di, 22.01.2013
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.
Formale Semantik der Logik erster Stufe; Formeln zur
Beschreibung von Datenbankanfragen; Erfüllbarkeit und
Äquivalenz; die Grenzen der Ausdrucksstärke
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 (Aufzeichnung vom 16.10.2012)
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.
Formale Semantik der Logik erster Stufe; Formeln zur
Beschreibung von Datenbankanfragen; Erfüllbarkeit und
Äquivalenz; die Grenzen der Ausdrucksstärke
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).
Di, 29.01.2013
Start mit Kapitel 7: Endliche Automaten zur Modellierung von
Abläufen - heute: Motivation,
DFAs, NFAs, viele Beispiele
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.
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).
Di, 05.02.2013
Abschluss von Kapitel 7: Endliche Automaten zur Modellierung von
Abläufen - heute: Pumping-Lemma inkl. Spiel-Charakterisierung und Anwendungsbeispiel; reguläre Ausdrücke; Ausblick.
Ü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.
Do, 07.02.2013
Start mit Kapitel 8: Kontextfreie Grammatiken zur Modellierung von
Strukturen - heute: Syntax und Semantik von KFGs; Ableitungen und
Ableitungsbäume; Beispiele.
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.
Di, 12.02.2013
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.
Kontextfreie Grammatiken zur Modellierung von Strukturen
Ausblick auf weitere Modellierungstechniken: Petri-Netze und das Entity-Relationship-Modell
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].
Do, 14.02.2013
Abschluss von Kapitel 9: Ausblick auf weitere Modellierungstechniken -
heute:
das Entity-Relationship-Modell zur Modellierung von Datenbanken.
Ausblick auf weitere Modellierungstechniken: Petri-Netze und das Entity-Relationship-Modell
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").
Di, 19.02.2013
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).