Diskrete Modellierung

Vorlesung im WS 2010/11

Gehalten von Prof. Dr. Nicole Schweikardt
Betreuung der Übungen durch Dipl.-Inf. André Frochaux, Dr. Mariano Zelke

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: 7.  SWS: 3 V, 2 Ü.

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 Mittwoch 08:00-11:00 Magnus-Hörsaal (Robert-Mayer-Str. 11-15) oder Jügelhaus - H III Prof. Dr. Nicole Schweikardt
Fragestunde Im Anschluss an die VL Magnus-Hörsaal (Robert-Mayer-Str. 11-15) oder Jügelhaus - H III Prof. Dr. Nicole Schweikardt, Dipl.-Inf. André Böhm, Dr. Mariano Zelke
Übung 1 Montag 14:00-16:00 Robert-Mayer-Str. 11-15 - SR 11 Sandra Kiefer
Übung 2 Dienstag 10:00-12:00 Neue Mensa - NM 125 Christoph Burschka
Übung 3 Dienstag 10:00-12:00 Neue Mensa - NM 126 Dipl.-Inf. Lucas Heimberg
Übung 4 Mittwoch 12:00-14:00 Neue Mensa - NM 126 Thomas Reichenbächer
Übung 5 Mittwoch 12:00-14:00 AfE-Turm - AfE 102a Jens Keppeler
Übung 6 Mittwoch 12:00-14:00 Neue Mensa - NM 117 Hannes Seiwert
Übung 7 Mittwoch 12:00-14:00 Neue Mensa - NM 133 Christoph Burschka

Ü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 mittwochs nach der Vorlesung an dieser Stelle zu finden und wird außerdem mittwochs in gedruckter Form am Ende der Vorlesung ausgeteilt. Die Abgabe der bearbeiteten Übungsaufgaben erfolgt in der jeweils darauf folgenden Woche mittwochs, 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.

Die Aufteilung der Übungsgruppen finden Sie in folgender PDF-Datei.

Anleitung für die Übungsgruppen-Anmeldung im LSF

Falls Sie an den Übungen teilnehmen wollen, müssen Sie sich über HIS-LSF in der Zeit vom 20. Oktober (12.00 Uhr) bis zum 28. Oktober (12:00 Uhr) für die Übung anmelden.
Zur Anmeldung für die Übungen verfahren Sie am besten wie folgt:

Klausur

Termin:
Die Klausur (= Modulabschlussprüfung Diskrete Modellierung) dauert 120 Minuten und findet am Dienstag, den 1. März 2011 von 9:00 bis 11:00 Uhr in Hörsaal V und Hörsaal VI (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! Für Informatik-Bachelor-Studierende endet die Frist 4 Wochen vor Stattfinden der Klausur; Informationen zur Anmeldung finden sich auf den Webseiten des Prüfungsamts Informatik (insbesondere hier und hier).
Nicht-Bachelor-Studierende melden sich bitte (1) ggf. beim für sie zuständigen Prüfungsamt und (2) per E-Mail bei André Böhm 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 10% 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/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)

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