Diskrete Modellierung (WS 2022/2023)

Vorlesung

Prof. Dr. Ulrich Meyer

Dienstag 14:00 - 16:00 in Hörsaal H V (Bockenheim)
Donnerstag 14:00 - 16:00 in Hörsaal H VI (Bockenheim)

Alle anderen Termine werden rechtzeitig hier angekündigt.

LSF

Übungsbetrieb

Alex Schickedanz
Anselm Haak

Organisatorische Fragen rund um die Vorlesung senden Sie bitte an dismod22@ae.cs.uni-frankfurt.de.

Hinweis: In der Vergangenheit kam es immer wieder zu Zustellungsproblemen bei externen E-Mail Providern. Wenn Sie eine Antwort auf Ihre E-Mail erwarten, verwenden Sie bitte Ihre Uni-Mailadresse.

Fragen zu Vorlesungsinhalten oder Übungsaufgaben stellen Sie bitte in den Tutorien oder beim Lernzentrum.

Das Lösen von Übungsaufgaben geschieht auf freiwilliger Basis. Dennoch ist die Teilnahme am Übungsbetrieb unbedingt zu empfehlen. Es werden weiterführende Inhalte vermittelt und es gibt die Möglichkeit Bonuspunkte zu sammeln. Eine Beobachtung unsererseits ist: Je höher die Bonuspunkte, desto höher die Wahrscheinlichkeit, eine gute Note zu erhalten. Weiterhin gilt aber, dass leider in der Vergangenheit immer wieder Betrugsversuche bei Übungsabgaben vorkamen. Deshalb bitten wir Sie darum, von solchen Täuschungsversuchen Abstand zu nehmen. Es lohnt sich nicht! Eine Zuwiderhandlung kann dazu führen, dass wir Ihnen alle Bonuspunkte aberkennen (genaue Regelung: siehe “Hinweise zu den Übungsabgaben”).

Es gibt wöchentlich Übungsblätter. Die Abgabe der Lösungen erfolgt dieses Semester ausschließlich über unseren Online-Briefkasten. Den genauen Ablauf erfahren Sie rechtzeitig hier auf der Webseite.

Sie können durch die Teilnahme an den Übungen bis zu 10% Bonuspunkte in der Klausur erhalten. Diese werden auf die Note einer bestanden Klausur angerechnet.

Termine der Übungsgruppen

Ab dem 3.10. können Sie sich über AUGE anmelden. Die Anmeldung endet am 20.10. um 23:55. Die Zuteilung erfolgt dann am 21.10.

Bis auf Gruppen 3 und 18 finden vorerst alle Übungsgruppen in Präsenz statt. Sollten wir auf Onlinebetrieb umstellen müssen werden Sie hier rechtzeitig informiert.

Hinweise zu den Übungsabgaben

• Wie immer gilt: Was unsere Tutoren nicht lesen können, müssen sie auch nicht korrigieren und es gibt dementsprechend auch keine Punkte.
• Da es eine online Abgabe gibt, ist eine Abgabe per E-Mail dieses Semester nicht vorgesehen.

Onlineabgabe:

• Die Abgabe wird Ihnen automatisch zugeordnet. Es schadet jedoch nicht Matrikelnummer und Namen darauf zu vermerken.
• Laden Sie Ihre Lösung nicht in der letzten Minute hoch. Wir können den reibungslosen Ablauf nicht garantieren, wenn alle in den 5 Minuten vor Schluss abgeben wollen.
• Wir nehmen Lösungen nur als eine PDF-Datei entgegen. Bitte stellen Sie sich darauf ein und testen Sie vorher.
  • Sie können Scans oder Bilder zu einer PDF zusammenfügen. Wenn Sie dafür ein Smartphone verwenden, nutzen Sie eine Scannerapp Ihres Vertrauens. Damit lassen sich Ränder wegschneiden und Seiten gerade ziehen.
  • Verwenden Sie eine angemessene Bildauflösung. Für Dokumente ist normalerweise nicht die höchst mögliche Auflösung nötig.

Vorrechnen:

• In der Besprechung in den Übungen bieten wir Ihnen an die Lösungen Ihrer Aufgaben zu präsentieren. So üben Sie Ihren Gedankengang schlüssig darzulegen und frei zu sprechen. Dies kommt Ihnen dann in den folgenden Semestern z.B. in einem Seminar (voraussichtlich 4. bis 6. Semester) oder Ihrem Abschlussvortrag (voraussichtlich 6. Semester) zugute.
• Zu jedem Blatt können Sie maximal einmal vorrechnen und bis zu 10 verlorene Punkte zurückgewinnen.
• Wir akzeptieren nur hochwertige Lösungen zur Präsentation, die Entscheidung liegt im Ermessen Ihres Tutors / Ihrer Tutorin. Bitte beachten Sie, dass wir versuchen möglichst viele verschiedene Studierende vorrechnen zu lassen.

Plagiate und Betrugsversuche:

• Wenn festgestellt wird, dass eine Aufgabe abgeschrieben wurde, dann…
  • … gibt es beim ersten Mal für alle Beteiligten 0 Punkte auf das Blatt.
  • … wird beim zweiten Mal allen Beteiligten die Bonifikation sowohl für die Erst- als auch die Zweitklausur aberkannt. Außerdem werden keine weiteren Abgaben der Beteiligten mehr korrigiert.
• Wichtig: Wer bereits in einer unseren anderen Veranstaltung erwischt wurde, bekommt keine Verwarnung. In dem Fall wird die Bonifikation sofort aberkannt. Leider sehen wir uns zu diesem Schritt gezwungen nachdem die Zahlen der abgeschriebenen Lösungen in den letzten Semestern massiv angestiegen sind.
• Sie dürfen in Gruppen über die Aufgaben diskutieren und zusammen Lösungswege erarbeiten (es ist sogar empfohlen). Jedoch muss jeder Student in der Abgabe die Lösung selbst schreiben und somit erkennbar machen, dass der Lösungsweg verstanden wurde. Im Zweifelsfall kann der Tutor verlangen, dass Sie eine Lösung vorrechnen. Sind Sie im Tutorium gar nicht anwesend, so kann der Tutor die Punkte vom Übungsblatt aberkennen.

Hinweise zu den Korrekturen

Sie sollen anhand der Übungsaufgaben den Stoff der Vorlesung besser verstehen. Ein wichtiger Teil davon sind die Kommentare der Tutoren auf den korrigierten Abgaben. Hier finden Sie die Gründe, wenn nicht die vollen Übungspunkte erreicht wurden.

Inhalte

In der Informatik wird das Modellieren mittels diskreter Strukturen als typische Arbeitsmethode in vielen Bereichen angewandt. Es dient der präzisen Beschreibung von Problemen durch spezielle Modelle und ist damit Voraussetzung für die Lösung eines Problems bzw. ermöglicht oft einen systematischen Entwurf. In den verschiedenen Gebieten der Informatik werden unterschiedliche, jeweils an die Art der Probleme und Aufgaben angepasste, Modellierungsmethoden verwendet. Innerhalb der Veranstaltung sollen zunächst die grundlegenden Begriffe wie z.B. ‚Modell‘ und ‘Modellierung‘, geklärt werden. Anschließend werden verschiedene Ausdrucksmittel der Modellierung untersucht: Grundlegende Kalküle wie der Kalkül der Mengen, die Aussagen- und Prädikatenlogik, Graphen, endliche Automaten, Markov-Ketten, kontextfreie Grammatiken.

Lernergebnisse / Kompetenzziele

Wissen und Verstehen: Kenntnis der grundlegenden Modellierungsmethoden und Beherrschen der entsprechenden Techniken.

Können: Die Studierenden erlernen die Fähigkeit zur präzisen und formalen Ausdrucksweise bei der Analyse von Problemen (systemische Kompetenz). Modellierungskonzepte wie etwa der Kalkül der Mengen, Aussagen- und Prädikatenlogik, Graphen, Markov-Ketten, endliche Automaten, kontextfreie Grammatiken sollen als Werkzeuge der Modellierung auch in ihren Anwendungsmöglichkeiten verstanden werden (instrumentale Kompetenz). Kommunikative Kompetenzen werden durch Arbeiten in Gruppen-Übungen und die dortige Vorstellung und Diskussion von Übungsaufgaben erworben.

Literatur

• A. Beutelspacher. “Das ist o.B.d.A. trivial!” Tipps und Tricks zur Formulierung mathematischer Gedanken. Vieweg Studium.
• D. Grieser. Mathematisches Problemlösen und Beweisen. Springer Verlag, 2013.
• S. Jukna. Crashkurs Mathematik für Informatiker. Teubner, 2008.
• U. Kastens und H. Kleine Büning. Modellierung. Grundlagen und formale Methoden. Hanser, 2005
• L. Lovász, J. Pelikan und K. Vesztergombi. Discrete Mathematics. Elementary and Beyond. Springer, 2003.
• U. Schöning. Logik für Informatiker. Springer, 2000.

Klausur

Hauptklausur: 02.03.2023

Zweitklausur: 06.04.2023

Bitte beachten Sie die An- und Abmeldefristen.

Details zum genauen Ablauf werden rechtzeitig bekannt gegeben.

Die Klausur ist bestanden, wenn mindestens 50% aller erreichbaren Punkte erzielt wurden. Zur Benotung werden neben dem Klausurergebnis Bonuspunkte aus den Übungen mit einem Maximalgewicht von 10% eingehen.

Freiversuchsregelung

Auf der Seite des Prüfungsamts finden Sie die aktuellen Freiversuchsregelungen der Informatik.

Materialien

Folien

Videoaufzeichnungen

Die Videoaufzeichnungen werden von studiumdigitale erstellt und gehostet. Die Sammlung mit allen bisherigen Aufzeichnungen finden Sie hier.

Logbuch

V28 (07.02.2023) Besprechung von Blatt 13

Video: Link

V27 (02.02.2023) 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 {anbn : 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: Bis einschließlich Abschnitt 8.5
• Folien: Kontextfreie Grammatiken (Seiten 16-48)
• Video: Link

V26 (31.01.2023) Reguläre Ausdrücke, Ausblick, Kontextfreie Grammatiken

Reguläre Ausdrücke: rekursive Definition der Ausdrücke und ihrer Sprachen, reguläre Ausdrücke beschreiben genau die Klasse der regulären Sprachen, 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: Bis Beispiel 8.8
• Folien: Endliche Automaten (Seiten 115-118), Kontextfreie Grammatiken (Seiten 1-16)
• Video: Link

V25 (26.01.2023) Reguläre Sprachen, Nichtdeterministische endliche Automaten, Potenzmengenkonstruktion, Reguläre Ausdrücke

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, Reguläre Sprachen: Zusammenfassung

Materialien und weitere Lektüre:

• Skript: Bis Ende Kapitel 7.6
• Folien: Endliche Automaten (Seiten 99-116)
• Video: Link

V24 (24.01.2023) Nerode-Relation, Nerode-Automat, Der Satz von Myhill-Nerode

Nerode-Relation; die Nerode-Relation ist eine Äquivalenzrelation; Beispiele, Nerode-Automat; 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, 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: Bis Definition 7.59 aus Abschnitt 7.5
• Folien: Endliche Automaten (Seiten 70-99)
• Video: Link

V23 (19.01.2023) Minimierungsalgorithmus, Nerode-Relation, Nerode-Automat

Wiederholung, Beispiele für den Minimierungsalgorithmus, Nerode-Relation; die Nerode-Relation ist eine Äquivalenzrelation; Beispiele, Nerode-Automat

Materialien und weitere Lektüre:

• Skript: Bis Definition 7.41. auf Seite 282
• Folien: Endliche Automaten (Seiten 70-78)
• Video: Link

V22 (17.01.2023) Minimierung, Verschmelzungsrelation, Paare nicht-äquivalenter Zustände, Äquivalenzklassenautomat, Minimierungsalgorithmus

Minimierung (Verschmelzungsrelation, Äquivalenzrelationen), 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

Materialien und weitere Lektüre:

• Skript: Bis Beispiel 7.32, Seite 275
• Folien: Endliche Automaten (Seiten 39-60)
• Video: Link

V21 (12.01.2023) Deterministische endliche Automaten, Äquivalenzrelationen

Wörter und Sprachen, DFAs (Zustandsdiagramm, erweiterte Übergangsfunktion, die Sprache des DFA), Paritätscheck, Minimierung (Äquivalenzrelationen)

Materialien und weitere Lektüre:

• Skript: Bis Seite 266, Beispiel 7.21
• Folien: Endliche Automaten (Seiten 10-38)
• Video: Link

V20 (10.01.2023) Stationäre Verteilungen, Markov-Ketten und Google’s Page-Rank; Alphabete, Worte und Sprachen

Wiederholung Hauptsatz für ergodische Markov-Ketten, Beispiele für stationäre Verteilungen (Irrfahrten in ungerichteten Graphen, symmetrische Ketten, Ehrenfest-Kette, Gambler’s Ruin), effiziente Approximation des Page-Ranks, Wörter und Sprachen

Materialien und weitere Lektüre:

• Skript: Bis Seite 255, Beispiel 7.5 (Natürliche Sprachen)
• Folien: Markov-Ketten (Seiten 66-82) und Endliche Automaten (Seiten 1-9)
• Video: Link

V19 (20.12.2022) - Die Grenzverteilung einer Markov-Kette, ergodische Ketten

Analyse des 2-SAT-Algorithmus, 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; stationäre Verteilungen; Hauptsatz für ergodische Markov-Ketten

Materialien und weitere Lektüre:

• Skript: Bis Satz 6.35 aus Abschnitt 6.3.4
• Folien: Markov-Ketten (Seiten 44-66)
• Video: Link

V18 (15.12.2022) - Irrfahrt einer Markov-Kette, Markov-Ketten und Beispiele

Markov-Ketten, das Vektor-Matrix-Produkt und ein Schritt einer Markov-Kette, die k-fache Potenz der Übergangsmatrix und k Schritte einer Markov-Kette 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

Materialien und weitere Lektüre:

• Skript: bis Beispiel 6.25 aus Abschnitt 6.3.3
• Folien: Markov-Ketten (Seiten 25-44)
• Video: Link

V17 (13.12.2022) - Suchmaschinen, Page-Rank, Zufallssurfer, Übergangsmatrix

Suchmaschinen (Crawler, Index und invertierter Index, wie misst man Renommee?), Page-Rank, Zufallssurfers (Verteilungen, Option Webgraph und Option “Wildes Hüpfen”, Übergangsmatrix des Webgraphen, stochastische Matrizen)

Materialien und weitere Lektüre:

• Skript: bis Ende Abschnitt 6.2
• Folien: Markov-Ketten (Seiten 1-25)
• Video: Link

V16 (08.12.2021) - Binärbäume, Entscheidungsbäume

Rekursionsbäume (Türme von Hanoi)); Spielbäume und Entscheidungsbäume

Materialien und weitere Lektüre:

• Skript: bis Beispiel 5.3.3.1 aus Abschnitt 5.3.3
• Folien: Bäume (Seiten 27-48)
• Video: Link

V15 (06.12.2022) - Bäume

ungerichtete Bäume (Blätter, Zusammenhang, Kreisfreiheit); Spannbäume, gewurzelte Bäume (Eltern und Kinder, Höhe und Tiefe, Blätter, Volle und vollständige Binärbäume, Syntaxbäume

Materialien und weitere Lektüre:

• Skript: bis Ende Abschnitt 5.3.1
• Folien: Bäume (Seiten 1-27)
• Video: Link

V14 (01.12.2022) - Zusammenhang, Matching, Färbung, Isomorphie (starker) Zusammenhang, 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 Graphen;

Materialien und weitere Lektüre:

• Skript: bis Ende Kapitel 5
• Folien: Graphen (Seiten 36-64)
• Video: Link

V13 (29.11.2022) - Graphen, Wege, Kreise

Anwendungsbeispiele von Graphen (RMV Schnellbahnplan, Kaffeekochen) 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,

Materialien und weitere Lektüre:

• Skript: bis Definition 5.9 aus Kapitel 5
• Folien: Graphen (Seiten 1-31), Algorithm Engineering im Kontext von Routenplanung
• Video: Link

V12 (24.11.2022) - rekursiv definierte Funktionen (2), vollständige Induktionen (mögliche Fehler)

Rekursive Definitionen und der Beweis von Eigenschaften über die vollständige Induktion (die Fibonacci-Zahlen, der Algorithmus von Euklid); vollständige Induktion: was so alles schiefgehen kann; Zusammenfassung der Beweistechniken;

Materialien und weitere Lektüre:

• Skript: bis Ende Kapitel 4
• Folien: Beweise (Seiten 42-49)
• Video: Link

V11 (22.11.2022) - Diagonalisierung, vollständige Induktion, rekursiv definierte Funktionen

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)

Materialien und weitere Lektüre:

• Skript: bis einschließlich Beispiel 4.19 aus Abschnitt 4.3.1 aus Kapitel 4
• Folien: Beweise (Seiten 16-41)
• Video: Link

V10 (17.11.2022) - DPLL, Beweise: direkte, Kontraposition, Widerspruch

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); Beweis durch Widerspruch (√2 ist irrational; es gibt unendlich viele Primzahlen)

Materialien und weitere Lektüre:

• Skript: bis einschließlich Satz 4.4 aus Abschnitt 4.2.3 aus Kapitel 4
• Folien: Aussagenlogik (Seiten 96-99), Beweise (Seiten 1-15)
• Video: Link

V09 (15.11.2022) - KNF-SAT, Resolution Hinweis: Da die Vorlesung am 15.11. ausfällt, ist hier bereits das Log und das Video zur Vorlesung aus dem letzten Jahr.

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 {(D1 ∨ X), (D2 ∨ ¬X)} ⊧ (D1 ∨ D2); Resolutionsbeweise; Frankfurt 31

Materialien und weitere Lektüre:

• Skript: bis Satz 3.59 aus Abschnitt 3.4.2.2 aus Kapitel 3
• Folien: Aussagenlogik (Seiten 82-95)
• Video: Link (von letztem Jahr)

V08 (10.11.2022) - Disjunktive Normalform, Konjunktive Normalform

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; Größe von DNFs und KNFs, Modellierung von Sudoku durch eine KNF

Materialien und weitere Lektüre:

• Skript: bis Definition 3.47 aus Abschnitt 3.4.2 aus Kapitel 3, ohne Satz 3.43
• Folien: Aussagenlogik (Seiten 67-86)
• Video: Link

V07 (08.11.2022) - Aussagenlogik in Python, fundamentale Äquivalenzen, die Größe von Wahrheitstafeln

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); SymPy und semantische Folgerung/Äquivalenz; fundamentale Äquivalenzen; die Größe von Wahrheitstafeln

Materialien und weitere Lektüre:

• Skript: bis zum ende von Abschnitt 3.3.3 aus Kapitel 3
• Folien: Aussagenlogik (Seiten 45-66)
• Video: Link

V06 (03.11.2022) - Belegungen, Wahrheitstafeln, erfüllbare/falsifizierbare Formeln, Widersprüche und Tautologien, Semantische Äquivalenz

Wahrheitstafeln, erfüllende und falsifizierende Belegungen; erfüllbare, falsifizierbare, allgemeingültige und unerfüllbare Formeln; Semantische Folgerung und Äquivalenz

Materialien und weitere Lektüre:

• Skript: Bis Abschnitt 3.3.3 aus Kapitel 3
• Folien: Aussagenlogik (Seiten 25-45)
• Video: Link

V05 (01.11.2022) - Aussagenlogik

Syntax und Semantik der Aussagenlogik, Variablen einer Formel, Atomare Aussagen und Junktoren, rekursive Definition der Syntax der Aussagenlogik, Syntaxbäume, Belegungen, Wahrheitstafeln

Materialien und weitere Lektüre:

• Skript: Bis Abschnitt 3.3.2 aus Kapitel 3
• Folien: Aussagenlogik (Seiten 5-25)
• Video: Link

V04 (27.10.2022) - Mächtigkeit und Kardinalität von Mengen, Aussagenlogik

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; Formeln und ihre Bedeutung in der Aussagenlogik

Materialien und weitere Lektüre:

• Skript: bis einschließlich Abschnitt 3.1.
• Folien: Mathematische Grundlagen (Seiten 61-68) und Aussagenlogik (Seiten 1-5)
• Video: Link

V03 (25.10.2022) - Mengenoperationen, Potenzmengen, Kartesisches Produkt, Relationen und Funktionen, Hilberts Hotel

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: bis Abschnitt einschließlich 2.4.3 aus Kapitel 2
• Folien: Mathematische Grundlagen (Seiten 40-61)
• Video: Link

V02 (20.10.2022) - 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; Komplementbildung; Potenzmenge;

Materialien und weitere Lektüre:

• Skript: Abschnitt 2.2.2 bis einschließlich 2.2.4
• Folien: Mathematische Grundlagen (Seiten 15-40)
• Video: Link

V01 (18.10.2022) - Einführung

Bitte unbedingt an den Übungen teilnehmen, Übungsbetrieb beginnt nächste Woche ab Donnerstag 27.10.2022. 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? Die Russellsche Antinomie. Beschreibung von Mengen.

Materialien und weitere Lektüre:

• Skript: Kapitel 1 und Kapitel 2 bis einschließlich 2.2.1
• Folien: Einführung, Mathematische Grundlagen (Seiten 1-15)
• Video: Link

Altklausuren

Altklausuren finden Sie hier.

Übungsblätter

Die Bearbeitung der Übungsblätter in Gruppen ist erlaubt, jedoch müssen Sie Ihre Lösungen eigenständig aufschreiben.

Die Übungsblätter werden so entworfen, dass ihre Bearbeitung mit den Kenntnissen aus der Vorlesung und aus vorangegangenen Übungsblättern möglich ist. Sollten Sie in Ihrer Lösung dennoch andere Quellen (Bücher, Skripte, Internetforen, soziale Netzwerke, Lösungen anderer Studenten, etc.) verwenden, so müssen Sie die entsprechenden Stellen als direkte oder indirekte Zitate kennzeichnen. Darüber hinaus muss Ihre persönliche Leistung stets deutlich erkennbar sein. Bei direkten Zitaten oder fast unverändert übernommenen Passagen liegt keine persönliche Leistung vor.

Beachten Sie auch die Hinweise zu Plagiaten und Betrugsversuchen.

Selbsttests

Selbststests sind ein zusätzliches Übungsangebot. Hier finden Sie Aufgaben und Lösungen mit denen Sie Ihren Wissensstand selbst überprüfen können.

Mathematische Grundlagen

Aussagenlogik

Skript

Es steht das Skript von Herrn Prof. Dr. G. Schnitger Diskrete Modellierung zur Verfügung.