Wintersemester 17/18

Vorlesung/Übung

Modelle der Informatik (MdI)

Dozent:
  • Prof. Dr. Tobias Hoßfeld
  • Christian Moldovan, M.Sc.
Ansprechpartner:
Semester:
Wintersemester 2017/2018
Turnus:
Wintersemester
Termin:
Mo 10:00 - 12:00, Mi 18:00 - 20:00
Raum:
SH 601 Großer Hörsaal (Mo), S05 T00 B08 (Mi)
Beginn:
09.10.2017
Ende:
02.02.2018
Sprache:
deutsch
Moodle:
Veranstaltung in Moodle
LSF:
Veranstaltung im LSF

Qualifikationsziele:

  • 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

Gliederung:

  1. Formale Sprachen
  2. Logik
  3. Bäume, Graphen und Netzwerke
  4. Petri-Netze
  5. Objektorientierte Modellierung mit Unified Modeling Language (UML)

Literatur:

  • 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

Prüfungsart:

schriftlich

Formalia:

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).

 Auf unserer Moodle-Plattform (https://moodle.uni-due.de/course/view.php?id=6793), befinden sich alle wichtigen Informationen zu der Veranstaltung ‚Modelle der Informatik‘. Unter anderem befindet sich hier eine Übersicht über alle Übungstermine, die von uns angeboten werden. Unter dem Button „Terminwahl“ (https://moodle.uni-due.de/mod/choicegroup/view.php?id=318249) ist es möglich, sich unverbindlich für einen Übungstermin anmelden. Für die Übungen ist eine offizielle Anmeldung nicht erforderlich.

 Wir werden mit dem Übungsbetrieb am Mo den 16.10. starten (zweite Vorlesungswoche). In dieser Woche werden hauptsächlich nochmal organisatorische Fragen und Grundlagen erklärt. zB Besprechung von Definition von Wort, Sprache, Grammatik mit Beispielen, sowie mathematische Ausdrücke zum Verständnis der Definitionen. Mit den mathematischen Formulierungen, die in der Informatik benutzt werden tun sich Erstis oft schwer. Während dieser Woche soll dann auch das erste Übungsblatt von den Studierenden daheim bearbeitet werden. In den Übungen der dritten Vorlesungswoche wird dann das erste Übungsblatt besprochen.