Aktuelles:

An dieser Stelle finden Sie im Laufe des Semesters aktuelle Mitteilungen. Bitte sehen Sie regelmäßig nach, ob es Neues gibt. Die vorläufigen Ergebnisse der Klausur vom 28. September 2010 finden Sie hier und per Aushang links neben dem Raum 116 (Robert-Mayer-Str. 11-15). Am folgenden Termin besteht die Möglichkeit zur Klausureinsicht: Dienstag, 26.10.2010, 10-11 Uhr, Raum 117 (Robert-Mayer-Str. 11-15) Zweiter Klausurtermin: Die zweite Klausur findet am 28. September von 9-11 Uhr im Hörsaal V (Hörsaalgebäude) statt. 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 (1) ggf. beim für sie zuständigen Prüfungsamt und (2) per E-Mail bei André Böhm (aboehm@informatik.uni-frankfurt.de) mit den folgenden Informationen an: Name, Vorname, Matrikelnummer, Geburtsdatum, Studiengang. Bei Bedarf findet am 14. September von 11-13 Uhr ein Help-Desk im Raum 117, Robert-Mayer-Str. 11-15, statt. Bei Interesse melden Sie sich bis zum 10. September per E-Mail bei André Böhm (aboehm@informatik.uni-frankfurt.de) an. Ohne Anmeldungen entfällt dieser Termin. Fundsache: Es hat sich eine Federtasche angefunden. Selbige kann bei Fr. Nadland (Raum 116; Robert-Mayer-Str. 11-15) abgeholt werden. Die Ergebnisse der Klausur vom 02. März 2010 finden Sie hier und per Aushang links neben dem Raum 116 (Robert-Mayer-Str. 11-15). An den folgenden Terminen besteht die Möglichkeit zur Klausureinsicht: Montag, 29.03.2010, 14-16 Uhr, Raum 117 (Robert-Mayer-Str. 11-15) Dienstag, 30.03.2010, 11-12 Uhr, Raum 117 (Robert-Mayer-Str. 11-15) Die Liste mit den Bonuspunkten für die Klausur finden Sie hier. Bonuspunkte für die Klausur: Der Anteil von maximal 10 Bonuspunkten, den Sie für die Klausur gutgeschrieben bekommen wird bestimmt durch den Anteil, den Sie von 1300 maximal zu vergebenen Übungspunkten erreicht haben und berechnet sich folgendermaßen: Die Anzahl der von Ihnen erreichten Übungspunkte wird durch 1300 dividiert, mit 10 multipliziert und danach auf die erste Nachkommastelle aufgerundet. Ein Beispiel: Sie haben 430 Übungspunkte gesammelt, es gilt (430/1300)*10 = 3,3076923. Diese Zahl wird auf die erste Nachkommastelle aufgerundet, damit erhalten Sie 3,4 Bonuspunkte für die Klausur. Achtung: Die Bonuspunkte werden Ihnen für die Klausur nur unter der Bedingung gutgeschrieben, dass Sie mindestens einmal im Tutorium vorgerechnet haben. Prüfen Sie bitte in der Liste der Bonuspunkte, ob Ihre Bonuspunkte korrekt eingetragen sind. Einsprüche gegen den in der Liste eingetragenen Punktestand müssen bis spätestens Freitag, den 26.02.2010, 12:00 Uhr erfolgen, um für die Klausur berücksichtigt werden zu können. Zur Unterstützung Ihrer Klausurvorbereitungen gibt es folgende Termine: Mi, 24.02.2010, 11-13 Uhr im Magnus-Hörsaal: Überblick über die wichtigsten Themen der Vorlesung, sowie die Möglichkeit, Fragen zum Vorlesungs- und Übungsstoff zu stellen. Help-Desk: An folgenden Zeiten stehen die Tutoren für Fragen zum Vorlesungs- und Übungsstoff bereit: Mo, 22.02.2010, 12-14 Uhr in Raum 117: Alexander Komissarenko Di, 23.02.2010, 14-16 Uhr in Raum 117: Khan Linh Doan Mi, 24.02.2010, 9-11 Uhr in Raum 117: Sandra Kiefer Do, 25.02.2010, 10-12 Uhr in Raum 117: Gunnar Rieger Fr, 26.02.2010, 13-15 Uhr in Raum 117: Altug Anis 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 am 2. Februar 2010. 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 (aboehm@informatik.uni-frankfurt.de) mit den folgenden Informationen an: Name, Vorname, Matrikelnummer, Geburtsdatum, Studiengang. Auf Blatt 12 der Übung hat sich ein kleiner Fehler eingeschlichen: Der Startzustand des NFA in Aufgabe 4 (a) ist offensichtlich z0 anstelle des im Aufgabentext verwendeten q0. Berücksichtigen Sie dementsprechend bei der Konstruktion von A' nur die Zustände, die vom Startzustand {z0} aus erreichbar sind. Die Einteilung der Übungsgruppen ist einsehbar [Link]. Das Skript zur Vorlesung "Diskrete Modellierung" finden Sie hier. Die Eröffnungsveranstaltung am 14. Oktober 2009 fand von 8.15 Uhr - 10.45 Uhr im MAGNUS-Hörsaal in der Informatik, Robert-Mayer-Str. 11 -15, statt. Von 21. Oktober 2009 bis 4. November 2009 fand die Vorlesung im Hörsaal H II, Jügelhaus statt. Seit 11.11.09 findet die Vorlesung im MAGNUS-Hörsaal statt! Am 21.10.09, am 04.11.09 und am 25.11.09 fand im Anschluss an die Vorlesung eine Fragestunde statt. Am 02.12.2009 fand im Anschluss an die Vorlesung eine Fragestunde statt, in der die Lösung zu Aufgabe 4 von Blatt 6 besprochen wurde. Am 09.12.2009 fand im Anschluss an die Vorlesung eine Fragestunde statt, in der die Lösung zu Aufgabe 3 von Blatt 7 besprochen wurde. Am 16.12.2009 fand im Anschluss an die Vorlesung eine Fragestunde statt, in der die Lösung zu Aufgabe 4 von Blatt 8 besprochen wurde. Am 13.01.2010 fand im Anschluss an die Vorlesung eine Fragestunde statt, in der die Lösung zu Aufgabe 2 von Blatt 9 besprochen wurde. Am 20.01.2010 fand im Anschluss an die Vorlesung eine Fragestunde statt. Am 27.01.2010 fand im Anschluss an die Vorlesung eine Fragestunde statt, in der die Lösung zu Aufgabe 3 von Blatt 11 besprochen wurde. Am 03.02.2010 fand im Anschluss an die Vorlesung eine Fragestunde statt, in der die Lösung zu Aufgabe 3 und 4(b) von Blatt 12 besprochen wurde. Am 10.02.2010 wird im Anschluss an die Vorlesung eine Fragestunde stattfinden, in der die Lösung zu einer Aufgabe von Blatt 13 besprochen werden wird. Der Übungsbetrieb startete am Montag / Dienstag / Mittwoch, den 26. / 27. / 28. Oktober 2009. 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, 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: Der Begriff "Diskrete Modellierung" Kapitel 2: Modellierung mit Wertebereichen – mathematische Grundlagen und Beweistechniken Abschnitt 2.1: Mengen Abschnitt 2.2: Kartesische Produkte und Relationen Abschnitt 2.3: Funktionen Abschnitt 2.4: Ein Beispiel zur Modellierung mit Wertebereichen Abschnitt 2.5: Beweise verstehen und selbst formulieren Abschnitt 2.6: 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: Erfüllbarkeit und Allgemeingültigkeit Abschnitt 3.4: Folgerung und Äquivalenz Abschnitt 3.5: 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: Markov-Ketten als Grundlage der Funktionsweise von Suchmaschinen im Internet Abschnitt 5.1: Die Architektur von Suchmaschinen Abschnitt 5.2: Der Page-Rank einer Webseite Abschnitt 5.3: Der Zufalls-Surfer Abschnitt 5.4: Markov-Ketten Abschnitt 5.5: Die effiziente Berechnung des Page-Rank Kapitel 6: Logik erster Stufe (Prädikatenlogik) Abschnitt 6.1: Motivation zur Logik erster Stufe Abschnitt 6.2: Strukturen Abschnitt 6.3: Syntax der Logik erster Stufe Abschnitt 6.4: Semantik der Logik erster Stufe Abschnitt 6.5: Erfüllbarkeit, Allgemeingültigkeit, Folgerung und Äquivalenz Abschnitt 6.6: Grenzen der Logik erster Stufe Abschnitt 6.7: Ein Anwendungsbereich der Logik erster Stufe: Datenbanken Kapitel 7: Endliche Automaten zur Modellierung von Abläufen Abschnitt 7.1: Deterministische endliche Automaten Abschnitt 7.2: Nichtdeterministische endliche Automaten Abschnitt 7.3: Äquivalenz von NFAs und DFAs Abschnitt 7.4: Das Pumping-Lemma für reguläre Sprachen Abschnitt 7.5: Reguläre Ausdrücke Abschnitt 7.6: Ausblick Kapitel 8: Kontextfreie Grammatiken zur Modellierung von Strukturen Abschnitt 8.1: Definition des Begriffs „Kontextfreie Grammatiken” Abschnitt 8.2: Bedeutung der Produktionen: Semantik von KFGs Abschnitt 8.3: Beispiele Abschnitt 8.4: Ausblick Kapitel 9: Ausblick auf weitere Modellierungstechniken Abschnitt 9.1: Petri-Netze zur Modellierung von Abläufen Abschnitt 9.2: Das Entity-Relationship-Modell zur Modellierung von Datenbanken Abschnitt 9.3: Eine Fallstudie 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 in der Informatik, 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 WS09/10: Mittwochs 15-16 Uhr, Raum 115)   Übungsgruppen: Montags 14-16,   SR 11, Robert-Mayer-Str. 11-15   Leitung:   Altug Anis Dienstags 10-12, NM 117, Neue Mensa Leitung: Altug Anis Dienstags 10-12, NM 125, Neue Mensa  Leitung: Sandra Kiefer Dienstags 14-16, SR 11, Robert-Mayer-Str. 11-15   Leitung: Khan Linh Doan Mittwochs 12-14, NM 129, Neue Mensa Leitung: Khan Linh Doan Mittwochs 12-14, NM 133, Neue Mensa Leitung: Alexander Komissarenko Mittwochs 12-14, Jüg 120c, Jügelhaus, Mertonstr. 17-21 Leitung: Gunnar Rieger Dienstags 10-12, Magnus-Hörsaal, Robert-Mayer-Str. 11-15   Leitung: N.N.   (Mangels Beteiligung entfällt diese Übungsgruppe. Teilnehmer, die dieser Gruppe zugeordnet sind, setzen sich bitte mit Dr. Mariano Zelke in Verbindung, um einer anderen Übungsgruppe zugeordnet zu werden.)   Betreuer:   Dr. Mariano Zelke und Dipl.-Inf. André Böhm. 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 Vorlesung findet am 14. Oktober 2009 von 8.15 Uhr - 10.45 Uhr, die erste Übungsstunde am Montag, dem 26.10.2009, 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: Über HIS-LSF konnte man sich bis 22. Oktober, 12:00 Uhr anmelden. Die Einteilung der Übungsgruppen ist hier einsehbar.

Übungsaufgaben:

Das aktuelle Übungsblatt ist jeweils spätestens mittwochs nach der Vorlesung auf dieser Seite (www.tks.informatik.uni-frankfurt.de/lehre/ws09/dismod/) 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. Präsenzaufgaben: Zu diesem Aufgabenblatt findet keine schriftliche Abgabe statt, es werden keine Punkte vergeben. Die Aufgaben werden gemeinsam in den Übungsstunden am 26., 27. und 28. Oktober gelöst. Blatt 1 (ausgeteilt am 21.10.2009; abzugeben am 28.10.2009) Blatt 2 (ausgeteilt am 28.10.2009; abzugeben am 04.11.2009) Blatt 3 (ausgeteilt am 4.11.2009; abzugeben am 11.11.2009) Blatt 4 (ausgeteilt am 11.11.2009; abzugeben am 18.11.2009) Blatt 5 (ausgeteilt am 18.11.2009; abzugeben am 25.11.2009) Blatt 6 (ausgeteilt am 25.11.2009; abzugeben am 02.12.2009) Blatt 7 (ausgeteilt am 2.12.2009; abzugeben am 09.12.2009) Blatt 8 (ausgeteilt am 9.12.2009; abzugeben am 16.12.2009) Blatt 9 (ausgeteilt am 16.12.2009; abzugeben am 13.01.2010) Blatt 10 (ausgeteilt am 13.01.2010; abzugeben am 20.01.2010) Blatt 11 (ausgeteilt am 20.01.2010; abzugeben am 27.01.2010) Blatt 12 (ausgeteilt am 27.01.2010; abzugeben am 03.02.2010) Beachten Sie bitte die Anmerkung zu diesem Blatt unter Aktuelles. Blatt 13 (ausgeteilt am 03.02.2010; abzugeben am 10.02.2010)

Klausur:

Termin: Die Wiederholungsklausur findet am Dienstag, den 28. September 2010 von 9:00 bis 11:00 Uhr in Hörsaal V (Jügelhaus) statt. Die Klausur (= Modulabschlussprüfung Diskrete Modellierung) dauert 120 Minuten und findet am Dienstag, den 2. März 2010 von 9:00 bis 11:00 Uhr in Hörsaal V und Hörsaal VI (Jügelhaus) 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)

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. [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. [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. [HS] A. Heuer und G. Saake. Datenbanken: Konzepte und Sprachen. MITP-Verlag, 2. Auflage, 2000. Mehr Informationen (incl. Leseprobe): hier.

Weiteres Material:

• (tks.AL) — Formelchecker für die Aussagenlogik