Aktuelles:

An dieser Stelle finden Sie im Laufe des Semesters aktuelle Mitteilungen. Bitte sehen Sie regelmäßig nach, ob es Neues gibt. Das Übungsblatt mit den Präsenzaufgaben steht zum Download bereit, siehe dazu Übungsaufgaben. Die Webseite zur Vorlesung ist umgezogen. Die neue Adresse lautet www.tks.informatik.uni-frankfurt.de/lehre/WS0910/DM/index.html. Ab sofort ist die Anmeldung für die Übungsgruppen im LSF möglich. Beachten Sie diese Anleitung. 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. Ab 21. Oktober 2009 wird die Vorlesung im Hörsaal H II, Jügelhaus stattfinden. Am 21. Oktober 2009 wird im Anschluss an die Vorlesung eine Fragestunde stattfinden. Der Übungsbetrieb startet am Montag, den 26.10.2009. Es ist nötig sich für eine der Übungsgruppen (siehe Übungsgruppen) anzumelden. 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: 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: 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: Markov-Ketten als Grundlage der Funktionsweise von Suchmaschinen im Internet Abschnitt 5.1: Die Architektur von Suchmaschinen Abschnitt 5.2: Page-Rank, Zufalls-Surfer und Markov-Ketten Abschnitt 5.3: 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: Modellierung von Abläufen Abschnitt 7.1: Endliche Automaten Abschnitt 7.2: Reguläre Ausdrücke Abschnitt 7.3: Petri-Netze Kapitel 8: Modellierung von Strukturen Abschnitt 8.1: Kontextfreie Grammatiken Abschnitt 8.2: Das Entity-Relationship-Modell Kapitel 9: 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 WS08/09: 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 118, Neue Mensa Leitung: Khan Linh Doan Mittwochs 12-14, NM 119, Neue Mensa Leitung: Alexander Komissarenko   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 kann man sich bis spätestens 22. Oktober, 12:00 Uhr anmelden. Hinweis: Die Studierenden der Kognitiven Liniguistik werden bei der Vergabe der Plätze für die Mittowchsgruppen bevorzugt. Eine Anmeldung ist dennoch notwendig. Zur Anmeldung für die Übungen verfahren Sie am besten wie folgt: Rufen Sie die Webseite zur Übungsanmeldung auf. Falls Sie sich im LSF noch nicht angemeldet haben, klicken Sie im Menü direkt unter dem Goethe-Universitäts-Logo (oben links) auf "Anmelden" und tragen Sie unter "Login" und "Passwort" Ihren HRZ-Benutzernamen und das dazugehörige Passwort ein. Nachdem Sie mit "Ok" bestätigt haben, kommen Sie wieder auf die Seite für die Anmeldung für die Übungen zur "Diskreten Modellierung" zurück. Klicken Sie nun direkt unterhalb der Überschrift "Diskrete Modellierung - Einzelansicht" auf den Link "belegen/abmelden". Sie sehen jetzt eine Ansicht aller verfügbaren Übungsgruppen. Sie können jetzt bis zu drei Tutoriumstermine auswählen, wobei für jeden Termin eine Priorität festgelegt werden kann. Wählen Sie dazu für jeden Termin die Priorität aus und beachten Sie, dass jede Priorität nur einmal vergeben werden kann. Klicken Sie abschließend auf "Platz beantragen". Melden Sie sich nach der Anmeldung zu den Übungen am besten im oberen Menü wieder aus dem LSF ab. Beachten Sie bitte: Erst nach dem abschließenden Losverfahren nach Ende der Anmeldefrist am 22. Oktober sind Sie einer Übungsgruppe fest zugeordnet.

Übungsaufgaben:

Das aktuelle Übungsblatt ist jeweils spätestens mittwochs nach der Vorlesung auf dieser Seite (www.tks.informatik.uni-frankfurt.de/lehre/WS0910/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. 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.

Klausur:

Termin: Die Klausur (= Modulabschlussprüfung Diskrete Modellierung) dauert 120 Minuten und findet Ende des Semesters 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. [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:

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