Logbuch Diskrete Modellierung - Winter 2023/24
Vorlesung 27 -- 06.02.2024:
Materialien:
Besprechung von Übungsblatt 12 (NFAs und Potenzmengenkonstruktion, Reguläre Ausdrücke, Kontextfreie Grammatiken)Vorlesung 26 -- 01.02.2024:
Ableitungsbäume und die "Bedeutung" von Worten, eindeutige und mehrdeutige Grammatiken, Beispiele kontextfreier Sprachen (Aussagenlogik, Menüs in Benutzungsoberflächen, HTML-Tabellen), jede reguläre Sprache wird durch eine rechtsreguläre Grammatik erzeugt (Reguläre Sprachen sind kontextfrei!), die nicht-reguläre Sprache {anbn : n ∈ ℕ} ist kontextfreiZusammenfassung (KFGs drücken rekursive Definitionen aus, ihre Produktionen ersetzen eine Variable durch einen Wort über Buchstaben und Variablen, der Ableitungsbaum legt die Semantik eines syntaktisch korrekten Programms fest)
Materialien und weitere Lektüre:- Skript: Abschnitte 8, 8.1, 8.2, 8.3 und 8.4.1
- Folien: Kontextfreie Grammatiken (Seiten 22-48)
Vorlesung 25 -- 30.01.2024:
Unterschiedliche Größe von DFAs, NFAs und regulären Ausdrücken, reguläre Sprachen: ZusammenfassungKontextfreie Grammatiken (Terminale, Nichtterminale, Startsymbol, Produktionen der Form "Variable → Wort über Terminalen und Nichtterminalen"), kontextfreie Grammatiken für arithmetische Ausdrücke, wohlgeformte Klammerausdrücke), kontextfreie Sprachen, kontextfreie Grammatiken und Programmiersprachen, Ableitungsbäume
Materialien und weitere Lektüre:- Skript: Abschnitte 7.7, 8, 8.1, 8.2, 8.3.1
- Folien: Endliche Automaten (Seiten 115-118)
- Folien: Kontextfreie Grammatiken (Seiten 1-22)
Vorlesung 24 -- 25.01.2024:
Materialien und weitere Lektüre:
Die Potenzmengenkonstruktion zeigt, dass NFAs genau die Klasse der regulären Sprachen akzeptieren. Reguläre Ausdrücke: rekursive Definition der Ausdrücke und ihrer Sprachen, reguläre Ausdrücke beschreiben genau die Klasse der regulären Sprachen- Skript: Abschnitte 7.5 und 7.6
- Folien: Endliche Automaten (Seiten 100-115)
Vorlesung 23 -- 23.01.2024:
Nerode-Automat für die Suffixsprache, Myhill-Nerode I (Äquivalenzklassenautomat und Nerode-Automat sind minimal, der Index einer Sprache L ist die minimale Zustandszahl eines DFA A mit L(A)=L), Myhill-Nerode II (eine Sprache ist genau dann regulär, wenn ihr Index endlich ist; wie zeigt man, dass eine Sprache nicht regulär ist: bestimme unendlich viele Worte sodass keine zwei Worte Nerode-äquivalent sind)NFAs sind DFAs, die raten können: statt einem Nachfolgezustand gibt es eine Menge von möglichen Nachfolgezuständen.
Materialien und weitere Lektüre:- Skript: Abschnitt 7.3.5, 7.4 und 7.5
- Folien: Endliche Automaten (Seiten 77-99)
Vorlesung 22 -- 18.01.2024:
Materialien und weitere Lektüre:
Beispiel: Minimierung des Suffix-Automaten; Nerode-Relation für die Sprache L, Index(L), Zeugen für inäquivalente Wörter bzgl. der Nerode-Relation, die Äquivalenzklassen der Nerode-Relation sind die Zustände des Nerode-Automaten. Korrektheitsbeweis für den Nerode-Automaten- Skript: Abschnitt 7.3.3, 7.3.4, 7.3.5
- Folien: Endliche Automaten (Seiten 61-77)
Vorlesung 21 -- 16.01.2024:
Materialien und weitere Lektüre:
Die Verschmelzungsrelation ist eine Äquivalenzrelation; Inäquivalenzen und Zeugen; die Bestimmung aller Paare inäquivalenter Zustände ist korrekt, Korrektheitsbeweis für die Bestimmung der Äquivalenzklassen, der Minimierungsalgorithmus, Beispiele- Skript: Abschnitte 7.3.3 und 7.3.4
- Folien: Endliche Automaten (Seiten 40-69)
Vorlesung 20 -- 11.01.2024:
Materialien und weitere Lektüre:
DFAs (Zustandsdiagramm, erweiterte Übergangsfunktion, die Sprache des DFA), Minimierung (Verschmelzungsrelation, Äquivalenzrelationen)- Skript: Abschnitte 7.1, 7.2, 7.3.1 und 7.3.2
- Folien: Endliche Automaten (Seiten 6-39)
Vorelsung 19 -- 09.01.2024:
Materialien und weitere Lektüre:
Hauptsatz für ergodische Markov-Ketten Teil 1: die Grenzverteilung ist stationär, Beispiele für stationäre Verteilungen (Irrfahrten in ungerichteten Graphen, symmetrische Ketten, Ehrenfest-Kette, Gambler's Ruin), effiziente Approximation des Page-Ranks. Einführung endliche Automaten, Wörter und Sprachen.- Skript: Abschnitte 6.3.4, 6.3.5, 7, 7.1
- Folien: Markov-Ketten (Seiten 66-82)
- Folien: Endliche Automaten (Seiten 1-10)
Vorelsung 18 -- 21.12.2023:
Materialien und weitere Lektüre:
Anwendungen von Markov-Ketten: Ehrenfest-Kette, Warteschlangen. Grenzverteilung und Grenzmatrix, ergodische Ketten (irreduzible und aperiodische Graphen), Beispiele ergodischer Ketten: die Webkette, Irrfahrten auf zusammenhängenden, nicht bipartiten Graphen; Beispiele nicht-ergodischer Ketten: Gambler's Ruin, Ehrenfest-Kette. Stationäre Verteilungen; Hauptsatz für ergodische Markov-Ketten.- Skript: Abschnitt 6.3.3 und 6.3.4
- Folien: Markov-Ketten (Seiten 44-66)
Vorlesung 17 -- 19.12.2023:
Materialien und weitere Lektüre:
Zufallssurfer, Markov-Ketten, das Vektor-Matrix-Produkt und ein Schritt einer Markov-Kette, die k-fache Potenz der Übergangsmatrix und k Schritte einer Markov-Kette. Weitere Beispiele und Anwendungen von Markov-Ketten: relative Besuchshäufigkeiten für einen Zufallssurfer im Webgraphen, Rasenmähen (Irrfahrten in einem ungerichteten Graphen), Gambler's Ruin, Analyse des 2-SAT-Algorithmus, Ehrenfest-Kette- Skript: Abschnitte 6.3.1 und 6.3.2
- Folien: Markov-Ketten (Seiten 21-45)
Vorlesung 16 -- 14.12.2023:
Materialien und weitere Lektüre:
Spielbäume und Entscheidungsbäume. Suchmaschinen (Crawler, Index und invertierter Index, wie misst man Renommee?), Intuition und korrekte Definition des Page-Ranks (Grundeinkommen und zusätzliches Einkommen an Renommee), Perspektive des Zufallssurfers (Verteilungen, Option Webgraph und Option "Wildes Hüpfen", Übergangsmatrix des Webgraphen, stochastische Matrizen)- Skript: Abschnitte 5.3.3 und 6.2
- Folien: Bäume (Seiten 37-48)
- Folien: Markov-Ketten (Seiten 1-24)
Vorlesung 15 -- 12.12.2023:
Materialien und weitere Lektüre:
Bäume (volle und vollständige Binärbäume, Syntaxbäume, Rekursionsbäume (Türme von Hanoi))Vorlesung 14 -- 07.12.2023:
Materialien und weitere Lektüre:
Graphklassen (vollständige Graphen, Würfel, bipartite Graphen, planare Graphen, azyklische Graphen). Ungerichtete Bäume (Blätter, Zusammenhang, Kreisfreiheit); Spannbäume, gewurzelte Bäume (Eltern und Kinder, Höhe und Tiefe, Blätter)Vorlesung 13 -- 05.12.2023:
Materialien und weitere Lektüre:
(Starker) Zusammenhang, machbare Probleme (Matching), schwierige Probleme (Bestimmung von Hamiltonwegen und Hamiltonkreisen), Konfliktgraph, Färbungsproblem (Das Färben von Landkarten (planaren Graphen) gelingt mit höchstens vier Farben!), Graphisomorphie, Graphklassen (vollständige Graphen, Würfel, bipartite Graphen, planare Graphen, azyklische Graphen), einfache und schwierige Probleme für GraphenVorlesung 12 -- 23.11.2023:
Materialien und weitere Lektüre:
Ungerichtete Graphen (Knoten, Kanten (Paarmengen), Inzidenz, Adjazenz (Nachbarschaft), Grad); gerichtete Graphen (Anfangs- und Endknoten von Kanten, Inzidenz von Knoten mit Kanten, Ausgrad und Eingrad), Wege (Weglänge ist die Anzahl der Kanten); Wege und Kreise, Königsberger Brückenproblem, machbare Probleme (Modellierung mit gerichteten Graphen: Routenplaner, Bestimmung kürzester Wege, (starker) Zusammenhang).Vorlesung 11 -- 21.11.2023:
Materialien und weitere Lektüre:
Rekursion und Induktion (die Paritätsfunktion, die Fibonacci-Zahlen, der Algorithmus von Euklid); vollständige Induktion: was so alles schiefgehen kann. Zusammenfassung der Beweistechniken.Vorlesung 10 -- 16.11.2023:
Materialien und weitere Lektüre:
Beweis durch Widerspruch (√2 ist irrational; es gibt unendlich viele Primzahlen); Cantorsche Diagonalisierung (es gibt weitaus mehr algorithmische Probleme als Python-Programme), vollständige Induktion (die Summe der ersten n Zahlen ist n*(n+1)/2, geometrische Reihe. Rekursive Definitionen und der Beweis von Eigenschaften über die vollständige Induktion (die Reiskornlegende als Beispiel).Vorlesung 9 -- 14.11.2023:
Materialien und weitere Lektüre:
Resolution, ein Resolutionsschritt ((D1 ∨ X) ∧ (D2 ∨ ¬X)) ⊧ (D1 ∨ D2); Resolutionsbeweise; Frankfurt 31, das DPLL-Verfahren (pure literal, unit resolution, backtracking). Direkte Beweise (die Potenzmenge einer Menge der Mächtigkeit r hat die Größe 2^r, Zusammenhang zwischen arithmetischem und geometrischem Mittel); Kontraposition (wenn ein Quadrat gerade ist, dann auch die Wurzel).- Skript: Abschnitte 3.4.2.2, 4.1, 4.2 (bis 4.2.2)
- Folien: Aussagenlogik (Seiten 87-99) und Beweise (Seiten 1-12)
Vorlesung 8 -- 09.11.2023:
Materialien und weitere Lektüre:
Aus einer Wahrheitstafel eine KNF bauen (baue zuerst eine DNF für die negierte Wahrheitstafel und negiere die DNF: wir erhalten mit DeMorgan eine KNF für die ursprüngliche Wahrheitstafel), jede Wahrheitstafel und damit jede Formel besitzt eine DNF wie auch eine KNF Größe von DNFs und KNFs, Modellierung von Sudoku durch eine KNF, das Resolutionsverfahren (Resolutionsschritt, Transitivität der Implikation). KNF-SAT (Erfüllbarkeitsproblem für Formeln in konjunktiver Normalform).- Skript: Abschnitte 3.4.1 und 3.4.2 (ohne 3.4.2.2)
- Folien: Aussagenlogik (Seiten 67-89)
Vorlesung 7 -- 07.11.2023:
Materialien und weitere Lektüre:
Überprüfen der Erfüllbarkeit in SymPy (und damit Falsifizierbarkeit, Allgemeingültigkeit und Unerfüllbarkeit), SymPy und semantische Folgerung/Äquivalenz; fundamentale Äquivalenzen; aus einer Wahrheitstafel eine DNF bauen, kanonische DNF (1-Zeilen, Konjunktionsterme).- Skript: Abschnitte 3.3.3 und 3.4.1 (ohne 3.4.1.1)
- Folien: Aussagenlogik (Seiten 48-72)
Vorlesung 6 -- 02.11.2023:
Materialien und weitere Lektüre:
Erfüllende und falsifizierende Belegungen, erfüllbare, falsifizierbare, allgemeingültige und unerfüllbare Formeln; semantische Folgerung und Äquivalenz, der Typ bool in Python, Auswertung von Formeln in Python.- Skript: Abschnitt 3.3
- Folien: Aussagenlogik (Seiten 32-48)
Vorlesung 5 -- 31.10.2023:
Materialien und weitere Lektüre:
Atomare Aussagen und Junktoren, rekursive Definition der Syntax der Aussagenlogik, Syntaxbäume, die Semantik der Aussagenlogik (der Begriff der Belegung, eine rekursive Definition der Semantik, Wahrheitstafeln).- Skript: Abschnitte 3.1, 3.2 und 3.3.1
- Folien: Aussagenlogik (Seiten 1-31)
Vorlesung 4 -- 26.10.2023:
Materialien und weitere Lektüre:
Funktionen, Eigenschaften von Funktionen, Hilberts Hotel, Mächtigkeit einer endlichen Menge, unendliche Mengen, gleichmächtige Mengen; die Mächtigkeit eines kartesischen Produkts M × N für endliche Mengen M und N.- Skript: Abschnitte 2.3 und 2.4
- Folien: Grundlagen (Seiten 59-68)
Vorlesung 3 -- 24.10.2023:
Materialien und weitere Lektüre:
Potenzmenge, kartesisches Produkt (Paare, Tupel oder Vektoren oder Folgen); Relationen (Teilmengen eines kartesischen Produktes, Beispiele wie Graphen, Funktionen, Ordnungsrelationen, Teilbarkeitsrelation, Teilmengenrelation, Gleichheitsrelation, relationale Datenbanken); Funktionen (zweistellige Relation mit genau einem Paar (x,y) für jedes Element x des Definitionsbereichs), Eigenschaften von Funktionen (injektiv, surjektiv, bijektiv), Notation für Funktionen (f : A → B, Definitions- und Bildbereich, Bild(f)).- Skript: Abschnitte 2.3 und 2.4
- Folien: Grundlagen (Seiten 39-59)
Vorlesung 2 -- 19.10.2023:
Materialien und weitere Lektüre:
Beschreibung von Mengen in Python, Teilmengen und Obermengen, Mengengleichheit, wie zeigt man Mengengleichheit M=N? (Zeige beide Teilmengenbeziehungen M ⊆ N und N ⊆ M, verwende ein beliebiges Element x der Menge M zum Nachweis einer Teilmengenbeziehung M ⊆ N, analog für N ⊆ M); Operationen auf Mengen (Durchschnitt, Vereinigung, Differenz, symmetrische Differenz, Komplementbildung); Venn-Diagramme; Komplementbildung; Potenzmenge.- Skript: Abschnitte 2.2.1, 2.2.2, 2.2.3 und 2.2.4
- Folien: Grundlagen (Seiten 16-41)
Vorlesung 1 -- 17.10.2023:
Materialien und weitere Lektüre:
Bitte unbedingt an den Übungen teilnehmen!
Aufgabenstellung der Vorlesung: die verschiedenen Kalküle (Aussagenlogik, Graphen, Markov-Ketten, endliche Automaten, kontextfreie Grammatiken und Prädikatenlogik). Wir sprechen Mathematik, um präzise beschreiben und zweifelsfrei zu begründen. Was sind Mengen? Das Beispiel des Barbiers von Sonnenthal bzw. das Russel-Paradox erzwingen eine sorgfältige Beschreibung von Mengen, entweder durch extensionale (explizite) Auflistung der Elemente oder durch intensionale (implizite) Schreibweise {x : x ∈ A und x erfüllt Eigenschaft E}, die Reihenfolge der Elemente oder ihre Vielfachheit ist für die Beschreibung einer Menge irrelevant.- Skript: Kapitel 1 und Abschnitte 2.1 und 2.2.1 aus Kapitel 2
- Folien: Einführung, Grundlagen (Seiten 1-16)