Theorie komplexer Systeme
Prof. Dr. Nicole Schweikardt
Institut für Informatik
Johann Wolfgang Goethe-Universität
Frankfurt am Main

Diskrete Modellierung
Wintersemester 2007/2008

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 Klausurergebnisse der Klausur vom 08.09.2008 finden Sie hier oder rechts neben Raum 115 (Robert-Mayer-Str. 11-15).
    Am folgenden Termin besteht die Möglichkeit zur Klausureinsicht:
    • Mittwoch, 15.10.2008, 16-17 Uhr, Raum 115 (Robert-Mayer-Str. 11-15)

  • Termin für die Modulabschlussprüfung (120-minütige Klausur) für das Modul "Modellierung" (Modulnr: MOD) im Sommersemester 2008:
    Montag, 08.09.2008, 10:00 bis 12:00 Uhr, Hörsaal H II im Hörsaalgebäude.
    (Bitte beachten Sie die Anmeldefristen, die im Prüfungsamt zu erfahren sind.)

  • Die Klausurergebnisse der Klausur vom 23.02.2008 finden Sie hier oder links neben Raum 116 (Robert-Mayer-Str. 11-15).
    An den folgenden Terminen besteht die Möglichkeit zur Klausureinsicht:
    • Mittwoch, 12.03.2008, 10-13 Uhr, Raum 117 (Robert-Mayer-Str. 11-15)
    • Dienstag, 08.04.2008, 10-11 Uhr, Raum 117 (Robert-Mayer-Str. 11-15)

  • 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 22.02.2008 erfolgen.

  • Zur Unterstützung Ihrer Klausurvorbereitungen gibt es folgende Termine:
  • Details zum Ablauf der Klausur finden Sie hier.
  • Am Freitag, 08.02.2008 finden keine Übungsstunden mehr statt.
  • Beispiel-Lösungen für die Übungsblätter 11 und 13 finden Sie hier.
  • Die korrigierten Aufgaben zu Blatt 13 können Sie ab 13.02.2008 bei André Hernich oder Nicole Schweikardt abholen.
  • Am Mittwoch, 23.01.08 fand im Anschluss an die Vorlesung eine Fragestunde statt (im Magnus-Hörsaal).
  • Am Mittwoch, 16.01.08 fand im Anschluss an die Vorlesung eine Fragestunde statt (im Magnus-Hörsaal).
  • Am Mittwoch, 21.11.07 fand im Anschluss an die Vorlesung eine Fragestunde statt (im Magnus-Hörsaal).
  • Am Mittwoch, 14.11.07 fand im Anschluss an die Vorlesung eine Fragestunde statt (im Magnus-Hörsaal).
  • Die erste Vorlesung fand in der ersten Semesterwoche am Mittwoch, den 17.10.2007 von 8:15 Uhr bis 11:00 Uhr im Magnus Hörsaal, Robert-Mayer-Str. 11-15, statt. Die erste Übungsstunde fand am Mittwoch, 24.10.2007 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-Relationsship-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:

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: Mittwochs 15-16 Uhr, Raum 115)
 
Übungsgruppen:
Montags14-16,  NM 103, Bockenheimer Landstr. 133 (Neue Mensa / Sozialzentrum),   Leitung:   Erik Rohnfeld
Dienstags10-12,NM 103, Bockenheimer Landstr. 133 (Neue Mensa / Sozialzentrum),   Leitung: Sviatlana Danilava
Dienstags14-16,Raum 903, Robert-Mayer-Str. 6-10, Leitung: Irina Shelegeda
Mittwochs12-14, Raum 110, Robert-Mayer-Str. 10 Leitung: Thomas Schroeder
Donnerstags16-18,Raum 110, Robert-Mayer-Str. 10 Leitung: Christine Lenhart
Freitags  8-10,NM 103, Bockenheimer Landstr. 133 (Neue Mensa / Sozialzentrum), Leitung: William Blacoe
Freitags14-16,NM 103, Bockenheimer Landstr. 133 (Neue Mensa / Sozialzentrum), Leitung: Martin Flockenhagen
 
Betreuer:   Dipl.-Inf. André Hernich   (Sprechstunde: 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 Mittwoch, 24.10.2007 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").

Anmeldung für die einzelnen Übungsgruppen:
Im 1. Stock des Gebäudes in der Robert-Mayer-Str. 11-15, gegenüber von Raum 113 wird für jeden Übungstermin eine Liste ausgehängt, in die Sie sich eintragen können. Der Aushang der Listen startet am Donnerstag, 18.10.07 um 8:00 Uhr und endet am Dienstag, 23.10.07 um 18:00 Uhr.
Wichtig: Jede/r einzelne Teilnehmer/in trägt sich bitte in genau eine der Listen ein.
Hinweis: Die ersten 20 Plätze der Mittwochs-Gruppe sind für Studierende der Kognitiven Linguistik reserviert.

Übungsaufgaben:

Das aktuelle Übungsblatt ist jeweils spätestens mittwochs nach der Vorlesung auf dieser Seite (www.tks.informatik.uni-frankfurt.de/lehre/WS0708/DM/) 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 24.10.2007; abzugeben am 31.10.2007)
  • Blatt 2 (ausgeteilt am 31.10.2007; abzugeben am 07.11.2007)
  • Blatt 3 (ausgeteilt am 07.11.2007; abzugeben am 14.11.2007)
  • Blatt 4 (ausgeteilt am 14.11.2007; abzugeben am 21.11.2007)
  • Blatt 5 (ausgeteilt am 21.11.2007; abzugeben am 28.11.2007)
  • Blatt 6 (ausgeteilt am 28.11.2007; abzugeben am 05.12.2007)
    Hinweis: Aufgabe 2(b) und 2(e) werden von Blatt 6 gestrichen, da die darin verwendeten Begriffe in der Vorlesung vom 28.11.07 noch nicht behandelt wurden.
  • Blatt 7 (ausgeteilt am 05.12.2007; abzugeben am 12.12.2007)
    Hinweis: Aufgabe 1(b) wird von Blatt 7 gestrichen, da die darin verwendeten Begriffe in der Vorlesung vom 05.12.07 noch nicht behandelt wurden.
  • Blatt 8 (ausgeteilt am 12.12.2007; abzugeben am 19.12.2007)
  • Blatt 9 (ausgeteilt am 19.12.2007; abzugeben am 09.01.2008)
    Hinweis: Aufgabe 2 wird von Blatt 9 gestrichen und auf Blatt 10 verschoben, da die darin verwendeten Begriffe in der Vorlesung vom 19.12.07 noch nicht behandelt wurden.
  • Blatt 10 (ausgeteilt am 09.01.2008; abzugeben am 16.01.2008)
  • Blatt 11 ("Beispielklausur") (ausgeteilt am 16.01.2008; abzugeben am 23.01.2008);  Beispiellösung für Blatt 11
  • Blatt 12 (ausgeteilt am 23.01.2008; abzugeben am 30.01.2008)
  • Blatt 13 (ausgeteilt am 30.01.2008; abzugeben am 06.02.2008);  Beispiellösung für Blatt 13

Klausur:
Termin:
Die Klausur (= Modulabschlussprüfung Diskrete Modellierung) dauert 120 Minuten und findet am Samstag, 23.02.2008 von 9:00 bis 11:00 Uhr in Hörsaal V (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 mit Sicherheit bestanden, wenn mit dem Bonus mindestens 50% der in der Klausur erzielbaren Punkte erreicht werden.

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 22.02.2008 erfolgen.

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.

Literatur:
[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 (dritte 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.
[HMU] J. E. Hopcroft, R. Motwani und J. D. Ullman. Introduction to Automata Theory, Languages, and Computation. Addison-Wesley, 2001.
[S-Theo] U. Schöning. Theoretische Informatik — kurzgefasst. Springer, 2001.
[W-Komp] I. Wegener. Kompendium Theoretische Informatik — eine Ideensammlung. Teubner, 1996.
[W-Theo] I. Wegener. Theoretische Informatik. Teubner, 1993.

 

Last modified: Tue Sep 30 13:01:51 CEST 2008
Nicole Schweikardt