Diskrete Modellierung (WS 2021/2022)

Update: Bei Blatt 11 Aufgabe 11.2 b)ii) wurde die Beschreibung verbessert.

Das Tutorium der Gruppe 18 wird am 18.02.22 auf 10 - 12 Uhr verschoben.

Bis auf weiteres finden freitags keine Fragestunden statt, Sie können stattdessen dienstags und donnerstags nach der Vorlesung Ihre Fragen stellen.

Achtung: Die Vorlesung muss ab 11.01.22 leider auf den virtuellen Modus umstellen. Das heißt, die Vorlesung findet Dienstag und Donnerstag online über Zoom statt. Die Zugangsdaten befinden sich im Moodle und werden an ihre stud.uni-frankfurt E-Mail Adresse gesendet.

Achtung: Gruppe 2 (Mo. 14-16) findet ab 17.01.2022 online statt.
Die Zugangsdaten wurden an Ihre @stud.uni-frankfurt.de E-Mail gesendet.

Achtung: Gruppe 4 (Di. 8-10) findet ab 11.01.2022 online statt.
Die Zugangsdaten wurden an Ihre @stud.uni-frankfurt.de E-Mail gesendet.

Achtung: Gruppe 9 (Di. 14-16) findet ab 11.01.2022 online statt.
Die Zugangsdaten wurden an Ihre @stud.uni-frankfurt.de E-Mail gesendet.

Achtung: Gruppe 13 (Do. 12-14) findet ab 13.01.2022 online statt.
Die Zugangsdaten wurden an Ihre @stud.uni-frankfurt.de E-Mail gesendet.

Hinweis zu den Fragestunden
Es werden dienstags und donnerstags Teile der Vorlesung im Sinne einer Fragestunde genutzt.
Weiterhin finden freitags vormittags Online-Fragestunden auf Zoom statt, der Zugangslink befindet sich im Moodle (siehe unten).

Hinweis zu Videoaufzeichnungen
Jede Vorlesung wird aufgezeichnet und zeitnah passwortgeschützt hier bereitgestellt.
Die Zugangsdaten erhalten Sie in der ersten Vorlesung sowie im Moodle (siehe unten).

Hinweis zu Zugangsdaten im Moodle
Die Zugangsdaten für die Materialien auf dieser Website für Übungsblätter und Selbsttests ist im Moodle auffindbar.
Für den Zugang zum Moodle benötigen Sie Ihren HRZ-Account.
Falls Sie noch keinen HRZ-Account besitzen melden Sie sich für die Zugangsdaten an die Veranstaltungs-Email dismod21@ae.cs.uni-frankfurt.de

Hinweis zum virtuellen Lernzentrum
Das virtuelle Lernzentrum wird über einen Discord-Server gehostet.
Den permanenten Einladungslink erhalten Sie im OLAT-Kurs. Falls Sie keinen HRZ-Account besitzen melden Sie sich bei dueffel AT cs.uni-frankfurt.de.

Hinweis zum Lernzentrum in Präsenz
Das Lernzentrum findet auch in Präsenz statt.
Genaue Details hier.

Hinweis zur Abgabe der Übungsblätter
Die Abgabe der Übungsblätter erfolgt über unser Online-Abgabesystem.
Nach erfolgreicher Anmeldung und Einteilung in eine Übungsgruppe erhalten Sie eine E-Mail mit Ihrem personalisierten Abgabelink.
Die E-Mail wird i.A. an Ihre Studierenden-Email versendet.

Vorlesung

Prof. Dr. Ulrich Meyer

Dienstag 12:15 - 13:45
Donnerstag 08:15 - 9:45
ab 11.01.2022 Online via Zoom, die Zugangsdaten finden sie im Moodle

Alle anderen Termine werden rechtzeitig hier angekündigt.

LSF

Übungsbetrieb

Daniel Allendorf
Hung Tran

Fragen rund um die Vorlesung bitte an dismod21@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

GruppeWochentagZeitRaum
Gruppe 1Mo8 - 10NM 102
Gruppe 2Mo14 - 16ab 17.01.2022 Online
Gruppe 3Mo16 - 18NM 112
Gruppe 4Di8 - 10ab 11.01.2022 Online
Gruppe 5Di10 - 12NM 111
Gruppe 6Di10 - 12ab 30.11.2021 Online
Gruppe 7Di10 - 12ab 30.11.2021 Online
Gruppe 8Di10 - 12H 13
Gruppe 9Di14 - 16ab 11.01.2022 Online
Gruppe 10Mi10 - 12H 1
Gruppe 11Mi10 - 12H 2
Gruppe 12Mi14 - 16ab 01.12.2021 Online
Gruppe 13Do12 - 14ab 13.01.2022 Online
Gruppe 14Do14 - 16H 2
Gruppe 15Fr10 - 12Online
Gruppe 16Fr10 - 12Online
Gruppe 17Fr12 - 14Online
Gruppe 18Fr14 - 16Online

Aus gegebenem Anlass sehen wir uns verpflichtet auf folgendes hinzuweisen:

  • Ein Wechsel der zugeteilten Übungsgruppe für die Abgabe ist NICHT möglich!

Hinweise zu den Übungsabgaben

  • Wie immer gilt: Was unsere Tutoren nicht lesen können, müssen sie auch nicht korrigieren und 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 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.

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.
  • D. D. Freydenberger. Skript zur Vorlesung “Theoretische Informatik 2”. Goethe-Universität Frankfurt am Main, 2014. [link]
  • Fachbereich Informatik und Mathematik. Goethe-Universität Frankfurt. Hinweise zum Zitieren in schriftlichen Arbeiten im Institut für Informatik [link]
  • U. Schöning. Logik für Informatiker. Springer, 2000.

Klausur

Hauptklausur: 03.03.2022

Zweitklausur: 04.04.2022

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

Hier finden Sie die aktuellen Freiversuchsregelungen der Informatik.

Materialien

Folien

Kapitel  StandVorlesungen
EinführungFolienHandout19.10.202101
Mathematische GrundlagenFolienHandout26.10.202101,02,03,04
AussagenlogikFolienHandout16.11.202105,06,07,08,09
BeweiseFolienHandout16.11.202110,11
GraphenFolienHandout23.11.202112,13,14
BäumeFolienHandout06.12.202115,16,17
Markov-KettenFolienHandout14.12.202117,18,19,20
Endliche AutomatenFolienHandout13.01.202221,22

Zusätzliche Folien

Thema StandVorlesungen
Algorithm Engineering im Kontext von RoutenplanungHandout30.11.202113

Videoaufzeichnungen

Vorlesung Datum
Vorlesung 01Link19.10.2021
Vorlesung 02Link21.10.2021
Vorlesung 03Link26.10.2021
Vorlesung 04Link28.10.2021
Vorlesung 05Link02.11.2021
Vorlesung 06Link04.11.2021
Vorlesung 07Link09.11.2021
Vorlesung 08Link11.11.2021
Vorlesung 09Link16.11.2021
Vorlesung 10Link18.11.2021
Vorlesung 11Link23.11.2021
Vorlesung 12Link25.11.2021
Vorlesung 13Link30.11.2021
Vorlesung 14Link02.12.2021
Vorlesung 15Link07.12.2021
Vorlesung 16Link09.12.2021
Vorlesung 17Link14.12.2021
Vorlesung 18Link16.12.2021
Vorlesung 19Link11.01.2022
Vorlesung 20Link13.01.2022
Vorlesung 21Link18.01.2022
Vorlesung 22Link20.01.2022
Vorlesung 23Link25.01.2022

Folien zu den Videos

Logbuch

V23 (25.01.2022) Paare nicht-äquivalenter Zustände, Äquivalenzklassenautomat, Minimierungsalgorithmus

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:

V22 (20.01.2022) Minimierung, Verschmelzungsrelation

Minimierung (Verschmelzungsrelation, Äquivalenzrelationen), die Verschmelzungsrelation ist eine Äquivalenzrelation; Inäquivalenzen und Zeugen

Materialien und weitere Lektüre:

V21 (18.01.2022) Alphabete, Worte und Sprachen; Deterministische endliche Automaten

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

Materialien und weitere Lektüre:

V20 (13.01.2022) Stationäre Verteilungen, Markov-Ketten und Google’s Page-Rank

Beispiele nicht-ergodischer Ketten: Ehrenfest-Kette; stationäre Verteilungen; 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

Materialien und weitere Lektüre:

V19 (11.01.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: Gambler’s Ruin

Materialien und weitere Lektüre:

V18 (16.12.2021) - Übergangsmatrix, Irrfahrt einer Markov-Kette, Markov-Ketten und Beispiele

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? 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 Anwendungen von Markov-Ketten: relative Besuchshäufigkeiten für einen Zufallssurfer im Webgraphen, Rasenmähen (Irrfahrten in einem ungerichteten Graphen), Gambler’s Ruin

Materialien und weitere Lektüre:

V17 (14.12.2021) - Zufallssurfer

Suchmaschinen (Crawler, Index und invertierter Index, wie misst man Renommee?)

Materialien und weitere Lektüre:

V16 (09.12.2021) - Eigenschaften von Bäumen, Minimale Spannbäume, Binärbäume, Entscheidungsbäume

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: bis Beispiel 5.3.3.1 aus Abschnitt 5.3.3
  • Folien: Bäume (Seiten 19-48) ohne TSP-Beispiel
  • Video: Link

V15 (07.12.2021) - Graphklassen, Bäume

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); Spannbäume, gewurzelte Bäume (Eltern und Kinder, Höhe und Tiefe, Blätter

Materialien und weitere Lektüre:

V14 (02.12.2021) - Matching, Färbung, Isomorphie

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

Materialien und weitere Lektüre:

V13 (30.11.2021) - Graphen, Wege, Kreise, Zusammenhang

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

Materialien und weitere Lektüre:

V12 (25.11.2021) - rekursiv definierte Funktionen (2), vollständige Induktionen (mögliche Fehler), Einführung Graphen

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

Materialien und weitere Lektüre:

V11 (23.11.2021) - 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), Definition der Fibonacci-Zahlen

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 (18.11.2021) - 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:

V09 (16.11.2021) - KNF-SAT, Resolution

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:

V08 (11.11.2021) - 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

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-81)
  • Video: Link

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

Materialien und weitere Lektüre:

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

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; Semantische Folgerung und Äquivalenz

Materialien und weitere Lektüre:

V05 (02.11.2021) - Aussagenlogik

Atomare Aussagen und Junktoren, rekursive Definition der Syntax der Aussagenlogik, Syntaxbäume

Materialien und weitere Lektüre:

V04 (28.10.2021) - Mächtigkeit und Kardinalität von Mengen

Notation für Funktionen (f : A → B, Definitions- und Bildbereich, Bild(f)); Hilberts Hotel; 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:

V03 (26.10.2021) - Mengenoperationen, Potenzmengen, Kartesisches Produkt, Relationen und Funktionen

Operationen auf Mengen (Durchschnitt, Vereinigung, Differenz, symmetrische Differenz, Komplementbildung); Venn-Diagramme; 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).

Materialien und weitere Lektüre:

V02 (21.10.2021) - 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).

Materialien und weitere Lektüre:

V01 (19.10.2021) - 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?

Materialien und weitere Lektüre:

Altklausuren

Altklausuren werden hier noch bereitgestellt.

Ü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. Orientieren Sie sich hierfür einfach an den Hinweisen zum Zitieren in schriftlichen Arbeiten am Institut für Informatik. 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.

DownloadAusgabeAbgabeKommentar
Übung 019.10.2021Entfällt-
Übung 128.10.202104.11.2021 8 Uhr im Abgabe-System-
Übung 204.11.202111.11.2021 8 Uhr im Abgabe-System-
Übung 311.11.202118.11.2021 8 Uhr im Abgabe-SystemUpdate: 10 Uhr am 12.11.2021
Übung 418.11.202125.11.2021 8 Uhr im Abgabe-SystemUpdate: 14 Uhr am 18.11.2021
Übung 525.11.202102.12.2021 8 Uhr im Abgabe-SystemUpdate: 9 Uhr am 26.11.2021
Übung 602.12.202109.12.2021 8 Uhr im Abgabe-System-
Übung 709.12.202116.12.2021 8 Uhr im Abgabe-SystemUpdate: 12 Uhr am 10.12.2021
Übung 816.12.202113.01.2022 8 Uhr im Abgabe-System-
Übung 913.01.202120.01.2022 8 Uhr im Abgabe-System-
Übung 1020.01.202127.01.2022 8 Uhr im Abgabe-System-
Übung 1127.01.202103.02.2022 8 Uhr im Abgabe-SystemUpdate: 11 Uhr am 27.01.2021

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

ThemaDownloadStand
MengenoperationenSelbsttest 0117.11.2021
-Selbsttest 0216.12.2021
-Selbsttest 0316.12.2021
MengenkardinalitätSelbsttest 0117.11.2021
-Selbsttest 0216.12.2021
-Selbsttest 0316.12.2021

Aussagenlogik

ThemaDownloadStand
BelegungenSelbsttest 0117.11.2021
-Selbsttest 0216.12.2021
-Selbsttest 0316.12.2021
ErfüllbarkeitSelbsttest 0117.11.2021
-Selbsttest 0216.12.2021
-Selbsttest 0316.12.2021
Semantische ÄquivalenzSelbsttest 0117.11.2021
-Selbsttest 0216.12.2021
-Selbsttest 0316.12.2021
ResolutionSelbsttest 0116.12.2021
-Selbsttest 0216.12.2021
-Selbsttest 0316.12.2021

Skript

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