Diskrete Modellierung
Wintersemester 2008/2009

Aktuelles   Einführung   Inhalt   Logbuch   Vorlesung&Übung   Übungsaufgaben   Klausur    Literatur   

Aktuelles:
An dieser Stelle finden Sie im Laufe des Semesters aktuelle Mitteilungen. Bitte sehen Sie regelmäßig nach, ob es Neues gibt.
  • Die Klausur vom 3. März 2009 finden Sie hier.

  • Die Ergebnisse der Klausur vom 29. September 2009 finden Sie hier oder links neben Raum 116 (Robert-Mayer-Str. 11-15).
    An den folgenden Terminen besteht die Möglichkeit zur Klausureinsicht:
    • Mittwoch, 14.10.2009, 14-15 Uhr, Raum 114 (Robert-Mayer-Str. 11-15)
    • Donnerstag, 22.10.2009, 10-11 Uhr, Raum 114 (Robert-Mayer-Str. 11-15)

  • Die Ergebnisse der Klausur vom 3. März 2009 finden Sie hier oder links neben Raum 116 (Robert-Mayer-Str. 11-15).
    An den folgenden Terminen besteht die Möglichkeit zur Klausureinsicht:
    • Mittwoch, 15.04.2009, 11-12 Uhr, Raum 117 (Robert-Mayer-Str. 11-15)
    • Donnerstag, 23.04.2009, 15-16 Uhr, Raum 117 (Robert-Mayer-Str. 11-15)

  • Es gibt einen zusätzlichen Help-Desk-Termin am Freitag, den 27.2.09, 12-14 Uhr in Raum 117 (Robert-Mayer-Str. 11-15).
  • Das vollständige und aktualisierte Skript zur Vorlesung "Diskrete Modellierung" finden Sie hier.
    Eine Beispiellösung für das 13. Übungsblatt finden sie hier.

  • Die Liste mit den Bonuspunkten finden Sie hier.

    Wichtig: Prüfen Sie, ob ihre Bonuspunkte korrekt eingetragen sind. Einsprüche gegen den in der Liste eingetragenen Punktestand müssen bis spätestens 2.3.2009 erfolgen.

  • Zur Unterstützung Ihrer Klausurvorbereitungen gibt es folgende Termine:
  • Details zum Ablauf der Klausur finden Sie hier.
  • Ab Donnerstag, den 12.02.2009 finden keine Übungsstunden mehr statt.
  • Die korrigierten Lösungen zu Übungsblatt 13 können ab Freitag, den 20.02.2009 im Sekretariat bei Frau Nadland (Raum 116) abgeholt werden.
  • Eine Beispiellösung für das 13. Übungsblatt finden sie hier.

  • Zur Teilnahme an der Klausur ist eine vorherige Anmeldung erforderlich.
    Bachelor-Studierende müssen sich beim für den jeweiligen Studiengang zuständigen Prüfungsamt anmelden. (Bitte stellen Sie sicher, dass Sie die Anmeldefristen nicht verpassen!)
    Nicht-Bachelor-Studierende melden sich bitte per E-Mail bei André Hernich (hernich@informatik.uni-frankfurt.de) mit den folgenden Informationen an: Name, Vorname, Matrikelnummer, Geburtsdatum, Studiengang, soll der Schein benotet oder unbenotet sein?

  • Als Hilfe für Ihre Vorbereitung auf die Klausur stellen wir Ihnen hier die Klausur aus dem Sommersemester 2008 zur Verfügung.
  • Das vollständige und aktualisierte Skript zur Vorlesung "Diskrete Modellierung" finden Sie hier.
  • Link zu (tks.AL) — Formelchecker für die Aussagenlogik

  • Am Mittwoch, den 04.02.2009 fand im Anschluss an die Vorlesung eine Fragestunde im Magnus Hörsaal statt.
  • Am Mittwoch, den 28.01.2009 fand im Anschluss an die Vorlesung eine Fragestunde im Magnus Hörsaal statt.
  • Am Mittwoch, den 21.01.2009 fand im Anschluss an die Vorlesung eine Fragestunde im Magnus Hörsaal statt.
  • Am Mittwoch, den 17.12.2008 fand im Anschluss an die Vorlesung eine Fragestunde im Magnus Hörsaal statt.
  • Am Mittwoch, den 26.11.2008 fand im Anschluss an die Vorlesung eine Fragestunde im Magnus Hörsaal statt.
  • Am Mittwoch, den 05.11.2008 fand im Anschluss an die Vorlesung eine Fragestunde im Magnus Hörsaal statt.
  • Die erste Übungsstunde fand am Donnerstag, 30.10.2008 statt.
  • Am Mittwoch, den 22.10.2008 fand im Anschluss an die Vorlesung eine Fragestunde im Magnus Hörsaal statt.
  • Die erste Vorlesung fand am Mittwoch, den 15.10.2008 von 8:15 Uhr bis 11:00 Uhr im Magnus Hörsaal, Robert-Mayer-Str. 11-15, statt.
  • Informationen zum Inhalt der einzelnen Vorlesungsstunden und gelegentlich ergänzende Bemerkungen finden Sie (nach den Vorlesungen) im Logbuch.

Einführung:
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, diskrete 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, Aussagen- und Prädikatenlogik, Graphen, endliche Automaten, Markov-Ketten, kontextfreie Grammatiken, Kellerautomaten, kontextsensitive Grammatiken, Entity-Relationship-Modell, Petri-Netze.

Lernziele:
Kenntnis der grundlegenden Modellierungsmethoden und Beherrschen der entsprechenden Techniken.
Fähigkeit zur präzisen und formalen Ausdrucksweise bei der Analyse von Problemen.

Inhalt:
  • Kapitel 1: Einführung ins Thema "Diskrete Modellierung"
    • Abschnitt 1.1: Wozu diskrete Modellierung im Informatik-Studium?
    • Abschnitt 1.2: Ziele der Veranstaltung "Diskrete Modellierung"
    • Abschnitt 1.3: Allgemeiner Modellbegriff
  • Kapitel 2: Modellierung mit Wertebereichen – mathematische Grundlagen und Beweistechniken
    • Abschnitt 2.1: Mengen, Relationen und Funktionen
    • Abschnitt 2.2: Ein Beispiel zur Modellierung mit Wertebereichen
    • Abschnitt 2.3: Beweise verstehen und selbst formulieren
    • Abschnitt 2.4: Rekursive Definitionen von Funktionen und Mengen
  • Kapitel 3: Aussagenlogik
    • Abschnitt 3.1: Wozu Logik im Informatik-Studium?
    • Abschnitt 3.2: Syntax und Semantik der Aussagenlogik
    • Abschnitt 3.3: Folgerung und Äquivalenz
    • Abschnitt 3.4: Normalformen
  • Kapitel 4: Graphen und Bäume
    • Abschnitt 4.1: Graphen
    • Abschnitt 4.2: Bäume
    • Abschnitt 4.3: Einige spezielle Arten von Graphen
  • Kapitel 5: Logik erster Stufe (Prädikatenlogik)
    • Abschnitt 5.1: Motivation zur Logik erster Stufe
    • Abschnitt 5.2: Strukturen
    • Abschnitt 5.3: Syntax der Logik erster Stufe
    • Abschnitt 5.4: Beispiele zur Semantik der Logik erster Stufe
    • Abschnitt 5.5: Semantik der Logik erster Stufe
    • Abschnitt 5.6: Ein Anwendungsbereich der Logik erster Stufe: Datenbanken
  • Kapitel 6: Modellierung von Strukturen
    • Abschnitt 6.1: Das Entity-Relationship-Modell
    • Abschnitt 6.2: Kontextfreie Grammatiken
  • Kapitel 7: Modellierung von Abläufen
    • Abschnitt 7.1: Endliche Automaten
    • Abschnitt 7.2: Petri-Netze
  • Kapitel 8: Eine Fallstudie
  • Kapitel 9: Markov-Ketten als Grundlage der Funktionsweise von Suchmaschinen im Internet
    • Abschnitt 9.1: Die Architektur von Suchmaschinen
    • Abschnitt 9.2: Page-Rank, Zufalls-Surfer und Markov-Ketten
    • Abschnitt 9.3: Die effiziente Berechnung des Page-Rank
Das Skript zur Vorlesung finden Sie hier.

Logbuch:
Hier finden Sie (nach den Vorlesungen) Informationen zum Inhalt der einzelnen Vorlesungsstunden und gelegentlich ergänzende Bemerkungen.

Informationen zum Vorlesungs- und Übungsbetrieb:
Vorlesung:
Mittwochs 8-11 im Magnus Hörsaal, Robert-Mayer-Str. 11-15
Start der Vorlesung: 8:15 Uhr;   Ende der Vorlesung: 10:45 Uhr;   Pause: 9:45–10:00 Uhr.
 
Dozentin:   Prof. Dr. Nicole Schweikardt   (Sprechstunde im WS08/09: Mittwochs 15-16 Uhr, Raum 115)
 
Übungsgruppen:
Montags 14-16,   NM 103, Bockenheimer Landstr. 133 (Neue Mensa / Sozialzentrum)   Leitung:   Khan Linh Doan
Dienstags 10-12, Raum 110, Robert-Mayer-Str. 10 Leitung: Ela Sibilska
Dienstags 14-16, NM 103, Bockenheimer Landstr. 133 (Neue Mensa / Sozialzentrum)   Leitung: Gülsah Kabakci
Mittwochs 12-14, Raum 110, Robert-Mayer-Str. 10 Leitung: Altug Anis
Donnerstags   8-10, NM 103, Bockenheimer Landstr. 133 (Neue Mensa / Sozialzentrum)   Leitung: Gunnar Rieger
Donnerstags  16-18, Raum 110, Robert-Mayer-Str. 10 Leitung: Altug Anis
Freitags   8-10, Raum 110, Robert-Mayer-Str. 10 Leitung: Alexander Komissarenko
 
Betreuer:   Dipl.-Inf. André Hernich   (Sprechstunde im WS08/09: Donnerstags 15-16 Uhr, Raum 113)

Ergänzend zu den Vorlesungen finden 2-stündige Übungen in kleinen Gruppen statt, in denen Fragen zur Vorlesung diskutiert und die Hausaufgaben besprochen werden. Die erste Übungsstunde findet am Donnerstag, 30.10.2008 statt.
Es wird regelmäßig Übungsaufgaben geben. Die Teilnahme an den Übungsstunden und das Bearbeiten der Übungsaufgaben ist für eine erfolgreiche Prüfung unbedingt empfohlen. Insbesondere kann durch die in den Übungen gesammelten Punkte ein Bonus für die Klausur erworben werden (Details siehe "Klausur").

Übungsaufgaben:

Das aktuelle Übungsblatt ist jeweils spätestens mittwochs nach der Vorlesung auf dieser Seite zu finden und wird mittwochs in gedruckter Form am Ende der Vorlesung ausgeteilt. Die Abgabe der bearbeiteten Übungsaufgaben erfolgt in der darauf folgenden Woche mittwochs, bis spätestens 8:15 Uhr vor dem Magnus Hörsaal. Auf dem abgegebenen Übungsblatt müssen Name und Übungsgruppe vermerkt sein. Mehrseitige Abgaben sind zusammenzuheften.

Obwohl es sicherlich sinnvoll ist, über die Aufgaben mit Kommilitonen/innen gemeinsam zu reden und nachzudenken, sollte jede/r Student/in seine eigene Lösung aufschreiben und abgeben.

  • Blatt 1 (ausgeteilt am 22.10.2008; abzugeben am 29.10.2008)
  • Blatt 2 (ausgeteilt am 29.10.2008; abzugeben am 05.11.2008)
  • Blatt 3 (ausgeteilt am 05.11.2008; abzugeben am 12.11.2008)
  • Blatt 4 (ausgeteilt am 12.11.2008; abzugeben am 19.11.2008)
  • Blatt 5 (ausgeteilt am 19.11.2008; abzugeben am 26.11.2008)
  • Blatt 6 (ausgeteilt am 26.11.2008; abzugeben am 03.12.2008)
  • Blatt 7 (ausgeteilt am 03.12.2008; abzugeben am 10.12.2008)
    Hinweis: Aufgabe 4(d) wird von Blatt 7 gestrichen, da die darin verwendeten Begriffe in der Vorlesung vom 03.12.08 noch nicht behandelt wurden.
  • Blatt 8 (ausgeteilt am 10.12.2008; abzugeben am 17.12.2008)
    Hinweis: Aufgabe 2(b) wird von Blatt 8 gestrichen, da die darin verwendeten Begriffe in der Vorlesung vom 10.12.08 noch nicht behandelt wurden.
  • Blatt 9 (ausgeteilt am 17.12.2008; abzugeben am 14.01.2009)
    Hinweis: Aufgabe 6 wird von Blatt 9 gestrichen, da die darin verwendeten Begriffe in der Vorlesung vom 17.12.08 noch nicht behandelt wurden.
  • Blatt 10 (ausgeteilt am 14.01.2009; abzugeben am 21.01.2009)
  • Blatt 11 (ausgeteilt am 21.01.2009; abzugeben am 28.01.2009)
  • Blatt 12 (ausgeteilt am 28.01.2009; abzugeben am 04.02.2009)
  • Blatt 13 (ausgeteilt am 04.02.2009; abzugeben am 11.02.2009) ;  Beispiellösung für Blatt 13

Klausur:
Termin:
Die Klausur (= Modulabschlussprüfung Diskrete Modellierung) dauert 120 Minuten und findet am Dienstag, 03.03.2009 von 9:00 bis 11:00 Uhr in Hörsaal V und Hörsaal VI (Hörsaalgebäude) statt.
 
Benotung:
Durch die in den Übungen gesammelten Punkte kann ein Bonus für die Klausur erworben werden. Zur Benotung werden neben dem Klausurergebnis Bonuspunkte mit einem Maximalgewicht von 10% eingehen. Die Klausur ist bestanden, wenn mit dem Bonus mindestens 50% der in der Klausur erzielbaren Punkte erreicht werden.

Bei einem Ergebnis von x% aus der Klausur und y% aus den Übungen werden die folgenden Noten vergeben, wobei   z = x + (y/10):

Note   Prozentpunkte
1.0 90% <= z
1.3 85% <= z < 90%
1.7 80% <= z < 85%
2.0 76% <= z < 80%
2.3 72% <= z < 76%
2.7 67% <= z < 72%
3.0 63% <= z < 67%
3.3 59% <= z < 63%
3.7 54% <= z < 59%
4.0 50% <= z < 54%

 
Details zum Ablauf der Klausur:
  • Grundsätzlich gelten die in der Ordnung Ihres Studiengangs festgelegten Regelungen. Dieses hier sind nur ergänzende Hinweise.
  • Alle Klausurteilnehmer/innen müssen sich zu Beginn der Klausur durch (1) den Studierendenausweis und (2) die "Goethe-Card" oder einen Lichtbildausweis ausweisen.
  • Außer einem dokumentenechten Schreibstift sind keine weiteren Hilfsmittel zugelassen. (Insbesondere: Kein Vorlesungsskript, keine mitgebrachten Notizen, kein von Ihnen mitgebrachtes Papier, kein Taschenrechner, kein Handy. Bitte beachten Sie, dass ein während der Klausur eingeschaltetes Handy als Betrugsversuch gewertet wird.)
  • Schreibpapier wird von uns bereitgestellt.
  • Die Sitzordnung wird von uns festgelegt und kurz vor Beginn der Klausur bekanntgegeben.
 
Checkliste — zur Klausur müssen Sie mitbringen:
  • einen dokumentenechten Schreibstift
  • einen gültigen Lichtbildausweis (z.B. Ihre Goethe-Card oder Ihren Personalausweis)
  • Ihren Studierendenausweis (... es sei denn, Sie sind als "Schülerstudent" für die Veranstaltung angemeldet)
 
Zur Unterstützung Ihrer Klausurvorbereitungen gibt es folgende Termine:
 
Generell empfehlen wir Ihnen, zur Vorbereitung auf die Klausur die Materialien aus der Vorlesung sowie die Übungsaufgaben und deren Lösungen durchzuarbeiten.
Als weitere Hilfe für Ihre Vorbereitung auf die Klausur stellen wir Ihnen hier die Klausur aus dem Sommersemester 2008 zur Verfügung.
Vorsicht: Alle in der Vorlesung bzw. der Übung behandelten Themen sind prüfungsrelevant. D.h.: In der Klausur im WS 08/09 können auch solche Themen vorkommen, die in den Klausuren im WS 07/08 oder im SoSe 08 nicht vorkamen (z.B. die Themen "ER-Modell", "Pumping-Lemma" und "Petrinetze").

Literatur:
[S] N. Schweikardt. Skript zur Vorlesung "Diskrete Modellierung", Goethe-Universität Frankfurt am Main, 2009.
Eine pdf-Datei des Skripts finden Sie hier.
[KKB] U. Kastens und H. Kleine Büning. Modellierung. Grundlagen und formale Methoden. Hanser, 2005.
[MM] C. Meinel und M. Mundhenk. Mathematische Grundlagen der Informatik. Mathematisches Denken und Beweisen. Teubner, 2002.
[B] A. Beutelspacher. „Das ist o.B.d.A. trivial!“ Tipps und Tricks zur Formulierung mathematischer Gedanken. Vieweg Studium.
[KK] M. Kreuzer und S. Kühling. Logik für Informatiker. Pearson Studium, 2006.
[S-Logik] U. Schöning. Logik für Informatiker. Springer, 2000.
[D] R. Diestel. Graphentheorie. Springer, 2006 (3. Auflage). Als pdf-Datei ist das Buch hier frei erhältlich.
[LPV] L. Lovasz, J. Pelikan und K. Vesztergombi. Discrete Mathematics. Elementary and Beyond. Springer, 2003.
[HU] J. E. Hopcroft und J. D. Ullman. Introduction to Automata Theory, Languages, and Computation. Addison-Wesley, 1979.
[S-Theo] U. Schöning. Theoretische Informatik — kurzgefasst. Springer, 2001 (4. Auflage).
[W-Komp] I. Wegener. Kompendium Theoretische Informatik — eine Ideensammlung. Teubner, 1996.
[W-Theo] I. Wegener. Theoretische Informatik. Teubner, 1999 (2. Auflage).
[R] W. Reisig. Petrinetze. Springer, 1982.
[S-IA] G. Schnitger. Skript zur Vorlesung "Internet Algorithmen", Goethe-Universität Frankfurt am Main, 2009.
Eine pdf-Datei des Skripts finden Sie hier.

Weiteres Material:

 

Last modified: Mon Apr 27 12:30:24 CET 2009
Nicole Schweikardt