Vorlesung/Übung

Modelle der Informatik (MdI)

Lecturer:
  • Prof. Dr. Tobias Hoßfeld
Contact:
Term:
Winter Semester 2015/2016
Cycle:
Wintersemester
Time:
Mo 10:00 - 12:00, Mi 18:00 - 20:00
Room:
S04 T01 A01 Großer Hörsaal (Mo), R14 R00 A04 Audimax (Mi)
Start:
19.10.2015
End:
10.02.2016
Language:
German
Moodle:
Lecture in Moodle
LSF:
Lecture in LSF

Learning Targets:

  • Formale Sprachen: Buchstaben, Wörter, Sprachen, Klassen von unendlichen Sprachen, Grammatiken: Definitionen, Chomsky-Hierarchie, BNF, EBNF, Endliche Automaten und reguläre Sprachen: Moore- und Mealy-Automaten, Deterministische und Nichtdeterministische Automaten, reguläre Sprachen, Kontextfreie Sprachen, Ableitungsbäume, Scanner und Parser; Beispiele: HTML, XML.
  • Logik: Aussagenlogik, logische Ausdrücke und Wahrheitstafeln, Tautologien, de Morgansche Regeln, Beweismethoden, aussagenlogische Resolution, Normalformen, Resolvierung von Begründungen, Grundzüge der Prädikatenlogik, Einführung in die Temporale Logik.
  • Bäume, Graphen und Netzwerke: Definitionen von Bäumen, binäre Suchbäume, Baumdurchlauf, ausgeglichene Bäume, Mehrwegbäume, Exkurs über Hashverfahren, Definitionen von Graphen, Euler- und Hamilton-Graphen, Knotenfärbung, Schwacher und starker Zusammenhang, Tiefen- und Breitendurchlauf, Spannbäume, Minimale Spannbäume, kürzeste Wege (Dijkstra-Algorithmus), Anwendungen, z.B. Routing in Rechnernetzen, Netzwerke und Flüsse.
  • Petri-Netze: Definition von Petri-Netzen, Stellen/Transitionsnetze, Lebendigkeit, Beschränktheit, S- und T-Invarianten, Erreichbarkeit, Modelle für wechselseitigen Ausschluss, Produzent/Konsument-Problem und Leser/Schreiber-Problem, Bedingungs/Ereignisnetze, Farbige Petri-Netze, Petri-Netze mit Verbotskanten, Vergröberung/Verfeinerung und Faltung/Entfaltung von Petri-Netzen, Ausblick auf stochastische Petri-Netze.
  • Stochastische Modelle: Überblick über Stochastische Petri-Netze, Zeitdiskrete Markovketten, Pseudo-Zufallszahlen und Monte-Carlo-Simulation.
  • Ausblick auf weitere Aspekte der theoretischen Informatik

Literature:

  • Müller-Clostermann, B.: Skriptum "Modelle der Informatik" (siehe Moodle)
  • Hedstück, U.: Einführung in die Theoretische Informatik - Formale Sprachen und Automatentheorie, Oldenbourg, 2002 (176 Seiten), in ca. 50 Exemplaren in der Lehrbuchsammlung (am Campus Essen)
  • Schöning, U.: Theoretische Informatik - kurzgefasst, Heidelberg 2001 (4. Auflage, 198 Seiten)
  • Kelley, J: Logik im Klartext, Pearson Studium, München 2003, in ca. 50 Exemplaren in der Lehrbuchsammlung am Campus Essen
  • Baumgarten, B.: Petri-Netze: Grundlagen und Anwendungen; Spektrum-Akademischer Verlag, 1997

Methods of Assessment:

schriftlich

Formalities:

Zum Modul erfolgt eine modulbezogene Prüfung in der Gestalt einer schriftlichen Prüfung über die gemeinsamen Ziele von Vorlesung und Übung (in der Regel: 90 bis 120 Minuten).