Diskrete Modellierung

Vorlesung im WS 2012/13

Gehalten von Prof. Dr. Nicole Schweikardt
Betreuung der Übungen durch Dr. Dominik D. Freydenberger, Dipl.-Inf. Lucas Heimberg

Aktuelles

Im Logbuch finden Sie nach den Vorlesungen Informationen zum Inhalt der einzelnen Vorlesungsstunden und gelegentlich ergänzende Bemerkungen.

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, 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.

Kürzel laut Studienordnung: B-MOD.  Creditpoints: 8.  SWS: 3 V, 2 Ü, 1 E.

Inhalte

Skript

Logbuch

Hier finden Sie (nach den Vorlesungen) Informationen zum Inhalt der einzelnen Vorlesungsstunden, die in der Vorlesung verwendeten Folien und gelegentlich ergänzende Bemerkungen.

E-Lectures

Im WS 2011/12 wurden die Vorlesungen von studiumdigitale, der E-Learning-Einrichtung der Goethe-Universität, auf Video aufgezeichnet. Die einzelnen Aufzeichnungen finden Sie hier:

Termine

ZeitOrtLeitung
Vorlesung Dienstag 8:00-10:00 Jügelhaus - H VI Prof. Dr. Nicole Schweikardt
Vorlesung Donnerstag 8:00-9:00 Jügelhaus - H VI Prof. Dr. Nicole Schweikardt
Fragestunde Donnerstag 9:00-10:00 Jügelhaus - H VI Prof. Dr. Nicole Schweikardt, Dr. Dominik D. Freydenberger, Dipl.-Inf. Lucas Heimberg
Übung 1 Dienstag 10:00-12:00 Neue Mensa - NM 125 Mario Holldack
Übung 2 Mittwoch 12:00-14:00 AfE-Turm - AfE 122 Jens Keppeler
Übung 3 Donnerstag 10:00-12:00 AfE-Turm - AfE 102b Sorin Constantinescu
Übung 4 Montag 14:00-16:00 Neue Mensa - NM 113 Mario Holldack
Übung 5 Dienstag 10:00-12:00 AfE-Turm - AfE 104b Norman Sutatyo
Übung 6 Mittwoch 12:00-14:00 AfE-Turm - AfE 902 Christoph Burschka
Übung 7 Donnerstag 10:00-12:00 AfE-Turm - AfE 902 Sofie van Geene

Übungsblätter

Es wird regelmäßige Übungsaufgaben geben. Die Teilnahme an den Übungsstunden und das Bearbeiten der Übungsaufgaben ist für das Verständnis der Vorlesung und 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).

Das aktuelle Übungsblatt ist jeweils spätestens dienstags nach der Vorlesung an dieser Stelle zu finden und wird außerdem dienstags in gedruckter Form am Ende der Vorlesung ausgeteilt. Die Abgabe der bearbeiteten Übungsaufgaben erfolgt in der jeweils darauf folgenden Woche dienstags, bis spätestens 8:15 Uhr vor Beginn der Vorlesung. Achtung: Auf dem abgegebenen Übungsblatt müssen Name, Matrikelnummer und Übungsgruppe vermerkt sein. Mehrseitige Abgaben sind zusammenzuheften. Die Abgabe erfolgt in Papierform (eine elektronische Abgabe ist aus logistischen Gründen leider nicht möglich).

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.

Klausur

Termin:
Die Klausur (= Modulabschlussprüfung Diskrete Modellierung) dauert 120 Minuten.
Im WS 2012/13 findet die Klausur am Mittwoch, den 27. Februar 2013 von 9:00 bis 11:00 Uhr in den Hörsälen H V und H VI (Jügelhaus) statt.
Im SoSe 2013 findet die Klausur voraussichtlich am Donnerstag, den 11. April 2013 von 9:00 bis 11:00 im Hörsaal H V (Jügelhaus) statt.
Anmeldung:
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! Die Frist ist abhängig von Ihrem Studiengang! Informationen zur Anmeldung für Informatik-Bachelor-Studierende finden sich auf den Webseiten des Prüfungsamts Informatik, insbesondere hier.
Nicht-Bachelor-Studierende melden sich bitte (1) ggf. beim für sie zuständigen Prüfungsamt und (2) per E-Mail bei Lucas Heimberg mit den folgenden Informationen an: Name, Vorname, Matrikelnummer, Geburtsdatum, Studiengang.
 
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 20% eingehen. Achtung: Die Bonuspunkte werden Ihnen für die Klausur nur unter der Bedingung gutgeschrieben, dass Sie mindestens einmal im Tutorium vorgerechnet haben.
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/5):

 

Note   Prozentpunkte
1.0 95% <= z
1.3 90% <= z < 95%
1.7 85% <= z < 90%
2.0 80% <= z < 85%
2.3 75% <= z < 80%
2.7 70% <= z < 75%
3.0 65% <= z < 70%
3.3 60% <= z < 65%
3.7 55% <= z < 60%
4.0 50% <= z < 55%
 
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.
  • Um festzustellen, in welchem der beiden Hörsäle Sie die Klausur schreiben werden, betrachten Sie die Zahl die von den letzten drei Stellen Ihrer Matrikelnummer gebildet wird. Liegt diese Zahl im Bereich von 000 bis 499, so schreiben Sie die Klausur in Hörsaal V. Liegt die Zahl im Bereich von 500 bis 999, so schreiben Sie in Hörsaal VI.
    • Beispiel 1: Angenommen, Ihre Matrikelnummer ist 7654321. Die letzten drei Stellen sind 321, diese Zahl liegt im Bereich von 000 bis 499, also schreiben Sie in Hörsaal V.
    • Beispiel 2: Angenommen, Ihre Matrikelnummer ist 1234567. Die letzten drei Stellen sind 567, diese Zahl liegt im Bereich von 500 bis 999, also schreiben Sie in Hörsaal VI.
    Die genaue Sitzordnung wird von uns festgelegt und kurz vor Beginn der Klausur am jeweiligen Hörsaal 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)

Literatur

[S] N. Schweikardt. Skript zur Vorlesung "Diskrete Modellierung", Goethe-Universität Frankfurt am Main, 2011-2012. Link
[KKB] U. Kastens und H. Kleine Büning. Modellierung. Grundlagen und formale Methoden. Hanser, 2005
[E] H.-D. Ebbinghaus.Einführung in die Mengenlehre. Spektrum Akademischer Verlag, Heidelberg Berlin, 2003.
[J] S. Jukna. Crashkurs Mathematik für Informatiker. Teubner, 2008.
[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.
[Logicomix] A. Doxiaidis, C.H. Papadimitriou, A. Papadatos, A. Di Donna. Logicomix: An Epic Search for Truth. Bloomsbury USA, 2009 :  Informationen zu diesem Comic sind hier erhältlich.
[D] R. Diestel. Graphentheorie. Springer, 2006 (3. Auflage) :  Informationen zum Buch sind hier erhältlich.
[LPV] L. Lovasz, J. Pelikan und K. Vesztergombi. Discrete Mathematics. Elementary and Beyond. Springer, 2003.
[HU] J. E. Hopcroft and 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.
[HS] A. Heuer und G. Saake. Datenbanken: Konzepte und Sprachen. MITP-Verlag, 2. Auflage, 2000.
[KE] A. Kemper und A. Eickler. Datenbanksysteme. Oldenbourg Verlag, 5. Auflage, 2004.

Links

[tks.AL] Formelchecker für die Aussagenlogik
[tks.FO] Formelchecker für die Logik erster Stufe