Diskrete Modellierung

Vorlesung

• Diskrete Modellierung im WS 2012/13
• Diskrete Modellierung im WS 2011/12
• Diskrete Modellierung im WS 2010/11
• Diskrete Modellierung im WS 2009/10
• Diskrete Modellierung im WS 2008/09
• Diskrete Modellierung im WS 2007/08

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

• Kapitel 1: Einführung ins Thema "Diskrete Modellierung"
• Kapitel 2: Mathematische Grundlagen und Beweistechniken (Modellierung mit Wertebereichen)
• Kapitel 3: Aussagenlogik
• Kapitel 4: Graphen und Bäume
• Kapitel 5: Markov-Ketten als Grundlage der Funktionsweise von Suchmaschinen im Internet
• Kapitel 6: Logik erster Stufe (Prädikatenlogik)
• Kapitel 7: Endliche Automaten zur Modellierung von Abläufen
• Kapitel 8: Kontextfreie Grammatiken zur Modellierung von Strukturen
• Kapitel 9: Ausblick auf weitere Modellierungstechniken: Petri-Netze und das Entity-Relationship-Modell
• Kapitel 10: Beispielklausuren

Skript

• N. Schweikardt. Skript zur Vorlesung "Diskrete Modellierung", Goethe-Universität Frankfurt am Main, 2012.

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:

• Kapitel 1: Einführung ins Thema "Diskrete Modellierung" [Flash | QuickTime | Mobile | MP3] (Aufzeichnung vom 19.10.2011)
• Kapitel 2: Mathematische Grundlagen und Beweistechniken
  1. Teil 1: Mengen [Flash | QuickTime | Mobile | MP3] (Aufzeichnung vom 19.10.2011)
  2. Teil 2: Mengenalgebra; Potenzmengen; kartesische Produkte; Worte; Relationen [Flash | QuickTime | Mobile | MP3] (Aufzeichnung vom 26.10.2011)
  3. Teil 3: Funktionen; Modellierung mit Wertebereichen;"Sätze" und "Beweise"; Beweistechniken "direkter Beweis", "Beweis durch Kontraposition", "Beweis durch Widerspruch" [Flash | QuickTime | Mobile | MP3] (Aufzeichnung vom 02.11.2011)
  4. Teil 4: Induktion und Rekursion [Flash | QuickTime | Mobile | MP3] (Aufzeichnung vom 09.11.2011)
• Kapitel 3: Aussagenlogik
  1. Teil 1: Syntax und Semantik der Aussagenlogik [Flash | QuickTime | Mobile | MP3] (Aufzeichnung vom 16.11.2011)
  2. Teil 2: Wahrheitswert; Intuitive Bedeutung der Semantik; Graphische Darstellung von Formeln [Flash | QuickTime | Mobile | MP3] (Aufzeichnung vom 16.11.2011)
  3. Teil 3: Wahrheitstafeln; Erfüllbarkeit und Allgemeingültigkeit [Flash | QuickTime | Mobile | MP3] (Aufzeichnung vom 16.11.2011)
  4. Teil 4: Semantische Folgerung; Äquivalenz; Normalformen [Flash | QuickTime | Mobile | MP3] (Aufzeichnung vom 23.11.2011)
• Kapitel 4: Graphen und Bäume
  1. Teil 1: Grundlegende Definitionen; Darstellung von Graphen (abstrakt, graphisch, Adjazenzliste, Adjazenzmatrix) [Flash | QuickTime | Mobile | MP3] (Aufzeichnung vom 23.11.2011)
  2. Teil 2: Wege; Hamilton-Kreise; Euler-Kreise; Isomorphie; Matchings; bipartite Graphen; konfliktfreie Färbungen [Flash | QuickTime | Mobile | MP3] (Aufzeichnung vom 30.11.2011)
  3. Teil 3: Ungerichtete bzw. gerichtete Bäume; einige spezielle Arten von Graphen [Flash | QuickTime | Mobile | MP3] (Aufzeichnung vom 07.12.2011)
  4. Teil 4: Äquivalenzrelationen; Ordnungsrelationen; der reflexive und transitive Abschluss [Flash | QuickTime | Mobile | MP3] (Aufzeichnung vom 14.12.2011)
• Kapitel 5: Markov-Ketten als Grundlage der Funktionsweise von Suchmaschinen im Internet
  1. Teil 1: die Architektur von Suchmaschinen; der Page-Rank einer Webseite; der Zufalls-Surfer [Flash | QuickTime | Mobile | MP3] (Aufzeichnung vom 14.12.2011)
  2. Teil 2: Markov-Ketten; Existenz und Eindeutigkeit eines Tupels, das die Page-Rank-Eigenschaft besitzt; die effiziente Berechnung des Page-Ranks [Flash | QuickTime | Mobile | MP3] (Aufzeichnung vom 21.12.2011)
• Kapitel 6: Logik erster Stufe (Prädikatenlogik)
  1. Teil 1: Einführung in die Syntax und Semantik der Logik erster Stufe [Flash | QuickTime | Mobile | MP3] (Aufzeichnung vom 11.01.2012)
  2. Teil 2: Formale Semantik der Logik erster Stufe; Formeln zur Beschreibung von Datenbankanfragen; Erfüllbarkeit und Äquivalenz; die Grenzen der Ausdrucksstärke [Flash | QuickTime | Mobile | MP3] (Aufzeichnung vom 18.01.2012)
• Kapitel 7: Endliche Automaten zur Modellierung von Abläufen
  1. Teil 1: Endliche Automaten: Motivation und Beispiele [Flash | QuickTime | Mobile | MP3] (Aufzeichnung vom 18.01.2012)
  2. Teil 2: Endliche Automaten: DFAs, NFAs, Potenzmengenkonstruktion, Pumping-Lemma [Flash | QuickTime | Mobile | MP3] (Aufzeichnung vom 25.01.2012)
  3. Teil 3: Reguläre Sprachen, Pumping-Lemma, Reguläre Ausdrücke [Flash | QuickTime | Mobile | MP3] (Aufzeichnung vom 01.02.2012)
• Kapitel 8: Kontextfreie Grammatiken zur Modellierung von Strukturen [Flash | QuickTime | Mobile | MP3] (Aufzeichnung vom 01.02.2012)
• Kapitel 9: Ausblick auf weitere Modellierungstechniken: Petri-Netze und das Entity-Relationship-Modell [Flash | QuickTime | Mobile | MP3] (Aufzeichnung vom 08.02.2012)
• Kapitel 10: Beispielklausuren [Flash | QuickTime | Mobile | MP3] (Aufzeichnung vom 15.02.2012)

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