Algorithmen & Komplexität

Arbeitsgruppe

Forschung

Lehre

Abschlussarbeiten

zurück zur Übersicht

Logbuch Diskrete Modellierung - Winter 2020/21

• V26 - Die Semantik von KFGs; Beispiele; Reguläre und kontextfreie Sprachen:
  kontextfreie Sprachen, kontextfreie Grammatiken und Programmiersprachen, 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 {aⁿbⁿ : n ∈ ℕ} ist kontextfrei

  Zusammenfassung (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.2, 8.3 und 8.4.1
  • Folien: Kontextfreie Grammatiken (Seiten 15-43)



• V25 - Kontextfreie Grammatiken:
  Reguläre Sprachen: Zusammenfassung

  Kontextfreie 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

  Materialien und weitere Lektüre:
  • Skript: Abschnitt 7.7, 8.1 und 8.2.1
  • Folien: Endliche Automaten (Seiten 115-118), Kontextfreie Grammatiken (Seiten 1-14)



• V24 - Reguläre Sprachen, Nichtdeterministische endliche Automaten, Reguläre Ausdrücke:
  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; 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

  Materialien und weitere Lektüre:
  • Skript: Abschnitt 7.4, 7.5 und 7.6
  • Folien: Endliche Automaten (Seiten 80-114)



• V23 - Nerode-Relation:
  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

  Materialien und weitere Lektüre:
  • Skript: Abschnitt 7.3.5
  • Folien: Endliche Automaten (Seiten 71-79)



• V22 - Äquivalenzklassenautomat, Minimierungsalgorithmus:
  Korrektheitsbeweis für die Bestimmung der Äquivalenzklassen, der Minimierungsalgorithmus; Der Äquivalenzklassenautomat ist äquivalent zum ursprünglichen Automaten; Beispiel: Minimierung des Suffix-Automaten

  Materialien und weitere Lektüre:
  • Skript: Abschnitte 7.3.3, 7.3.4, 7.3.5
  • Folien: Endliche Automaten (Seiten 49-70)



• V21 - Inäquivalenzen und Zeugen, Paare nicht-äquivalenter Zustände:
  die Verschmelzungsrelation ist eine Äquivalenzrelation; Inäquivalenzen und Zeugen; die Bestimmung aller Paare inäquivalenter Zustände ist korrekt

  Materialien und weitere Lektüre:
  • Skript: Abschnitt 7.3.3
  • Folien: Endliche Automaten (Seiten 39-48)



• V20 - Alphabete, Worte und Sprachen; Deterministische endliche Automaten; Minimierung:
  Wörter und Sprachen, DFAs (Zustandsdiagramm, erweiterte Übergangsfunktion, die Sprache des DFA), Minimierung (Verschmelzungsrelation, Äquivalenzrelationen)

  Materialien und weitere Lektüre:
  • Skript: Abschnitte 7.1, 7.2, 7.3.1 und 7.3.2
  • Folien: Endliche Automaten (Seiten 1-38)



• V19 - Markov-Ketten und Google’s Page-Rank:
  Beispiele für stationäre Verteilungen (Irrfahrten in ungerichteten Graphen, symmetrische Ketten, Ehrenfest-Kette, Gambler's Ruin), effiziente Approximation des Page-Ranks

  Materialien und weitere Lektüre:
  • Skript: Kapitel 6
  • Folien: Markov-Ketten (Seiten 67-82)



• V18 - Die Grenzverteilung einer Markov- Kette, Stationäre Verteilungen:
  Ehrenfest-Kette, 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 Teil 1: die Grenzverteilung ist stationär.

  Materialien und weitere Lektüre:
  • Skript: Abschnitt 6.3.3 und 6.3.4
  • Folien: Markov-Ketten (Seiten 44-66)



• V17 - Markov-Ketten und Beispiele:
  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

  Materialien und weitere Lektüre:
  • Skript: Abschnitt 6.3.1
  • Folien: Markov-Ketten (Seiten 35-43)



• V16 - Zufallssurfer, Übergangsmatrix, Irrfahrt einer Markov-Kette:
  Korrektur des Page-Ranks: Grundeinkommen und zusätzliches Einkommen
  die Perspektive des Zufallssurfers (Verteilungen, Option Webgraph und Option "Wildes Hüpfen", Übergangsmatrix des Webgraphen, stochastische Matrizen), Markov-Ketten, das Vektor-Matrix-Produkt und ein Schritt einer Markov-Kette, die k-fache Potenz der Übergangsmatrix und k Schritte einer Markov-Kette

  Materialien und weitere Lektüre:
  • Skript: Abschnitte 6.2 und 6.3 bis Seite 220
  • Folien: Markov-Ketten (Seiten 15-34)



• V15 - Markov-Ketten und Page-Rank:
  Suchmaschinen (Crawler, Index und invertierter Index, wie misst man Renommee?),
  Baron von Münchhausen: Renommee von Seite i ist die Summe der anteilig erhaltenen Renommees der Webseiten, die auf Seite i zeigen! Aber wie bestimmt man Renommee? Als Lösung eines linearen Gleichungssystems! Aber wie geht man mit Senken um?

  Materialien und weitere Lektüre:
  • Skript: Abschnitte 6.1 und 6.2.1
  • Folien: Markov-Ketten (Seiten 1-14)



• V14 - Eigenschaften von Bäumen, Minimale Spannbäume, Binärbäume, Entscheidungsbäume:
  Spannbäume, gewurzelte Bäume (Eltern und Kinder, Höhe und Tiefe, Blätter, volle und vollständige Binärbäume, Syntaxbäume, Rekursionsbäume (Türme von Hanoi)); Spielbäume und Entscheidungsbäume

  Materialien und weitere Lektüre:
  • Skript: Abschnitt 5.2.1 und 5.3
  • Folien: Bäume (Seiten 5-48)



• V13 - Färbung, Isomorphie, Bäume:
  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 Graphen;
  ungerichtete Bäume (Blätter, Zusammenhang, Kreisfreiheit);

  Materialien und weitere Lektüre:
  • Skript: Abschnitte 5.1 und Anfang von 5.2 (Seiten 180-182)
  • Folien: Graphen (Seiten 48-64), Bäume (Seiten 1-4)



• V12 - Wege, Kreise, Zusammenhang, Zuordnungsprobleme:
  Wege und Kreise, Königsberger Brückenproblem, machbare Probleme (Modellierung mit gerichteten Graphen: Routenplaner, Bestimmung kürzester Wege, (starker) Zusammenhang, Matching), schwierige Probleme (Bestimmung von Hamiltonwegen und Hamiltonkreisen), Konfliktgraph

  Materialien und weitere Lektüre:
  • Skript: Abschnitte 5.1.2 und 5.1.3
  • Folien: Graphen (Seiten 20-47)



• V11 - Graphen:
  Zusammenfassung der Beweistechniken;
  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)

  Materialien und weitere Lektüre:
  • Skript: Abschnitt 5.1.1.1
  • Folien: Beweise (Seite 45), Graphen (Seiten 1-19)



• V10 - Rekursiv definierte Funktionen, rekursive Programme:
  Rekursive Definitionen und der Beweis von Eigenschaften über die vollständige Induktion (die Reiskornlegende, die Fibonacci-Zahlen, der Algorithmus von Euklid); vollständige Induktion: was so alles schiefgehen kann

  Materialien und weitere Lektüre:
  • Skript: Abschnitt 4.3
  • Folien: Beweise (Seiten 29-47)



• V09 - Beweise: direkte, Kontraposition, Widerspruch; Diagonalisierung, vollständige Induktion:
  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); 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.

  Materialien und weitere Lektüre:
  • Skript: Abschnitte 4.1, 4.2 und 4.3 (bis 4.3.1)
  • Folien: Beweise (Seiten 1-28)



• V08 - Disjunktive Normalform, Konjunktive Normalform, Resolution, DPLL, Zsfg. Aussagenlogik:
  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); ein Resolutionsschritt {(D₁ ∨ X), (D₂ ∨ ¬X)} ⊧ (D₁ ∨ D₂); Resolutionsbeweise; Frankfurt 31, das DPLL-Verfahren (pure literal, unit resolution, backtracking)

  Materialien und weitere Lektüre:
  • Skript: Abschnitte 3.4.1 und 3.4.2
  • Folien: Aussagenlogik (Seiten 79-97)



• V07 - Semantische Folgerung, Äquivalenz, DNF, KNF:
  SymPy und semantische Folgerung/Äquivalenz; fundamentale Äquivalenzen; aus einer Wahrheitstafel eine DNF bauen, kanonische DNF (1-Zeilen, Konjunktionsterme); 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

  Materialien und weitere Lektüre:
  • Skript: Abschnitte 3.4.1 (ohne 3.4.1.1) und 3.4.2 (ohne 3.4.2.1 und 3.4.2.2)
  • Folien: Aussagenlogik (Seiten 55-78)



• V06 - Semantische Folgerung und Äquivalenz:
  Semantische Folgerung und Äquivalenz, der Typ bool in Python, Auswertung von Formeln in Python; Überprüfen der Erfüllbarkeit in SymPy (und damit Falsifizierbarkeit, Allgemeingültigkeit und Unerfüllbarkeit)

  Materialien und weitere Lektüre:
  • Skript: Abschnitt 3.3
  • Folien: Aussagenlogik (Seiten 38-54)



• V05 - Aussagenlogik:
  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); erfüllende und falsifizierende Belegungen; erfüllbare, falsifizierbare, allgemeingültige und unerfüllbare Formeln

  Materialien und weitere Lektüre:
  • Skript: Abschnitte 3.1, 3.2 und 3.3.1
  • Folien: Aussagenlogik (Seiten 1-37)



• V04 - Funktionen, Mengen:
  Die 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

  Materialien und weitere Lektüre:
  • Skript: Kapitel 2
  • Folien: Grundlagen (Seiten 57-64, 66-68)



• V03 - Komplementbildung, Potenzmengen, Kartesisches Produkt, Relationen, Funktionen:
  Komplementbildung; 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)); Hilberts Hotel

  Materialien und weitere Lektüre:
  • Skript: Abschnitte 2.2, 2.3, 2.4.1 und 2.4.2
  • Folien: Grundlagen (Seiten 32-61)



• V02 - Mengen:
  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;

  Materialien und weitere Lektüre:
  • Skript: Abschnitte 2.2.1, 2.2.2 und 2.2.3
  • Folien: Grundlagen (Seiten 17-31)



• V01 - Einführung:
  Bitte unbedingt an den Übungen teilnehmen, Übungsbetrieb beginnt nächste Woche. 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.

  Materialien und weitere Lektüre:
  • Skript: Kapitel 1 und Abschnitte 2.1 und 2.2.1 aus Kapitel 2
  • Folien: Einführung, Grundlagen (Seiten 1-16)