Kommentar |
Inhalte:
Gliederung:
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, 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, z.B. Turingmaschinen, Berechenbarkeit, Komplexität und Effizienz von Algorithmen, Konzept der NP-Vollständigkeit.
Lernziele:
Kennenlernen von Modellierungsparadigmen und Formalismen, die sich in der praktischen Anwendung als erfolgreich erwiesen haben; Erlernen der grundlegenden Konzepte, der zugehörigen Formalismen und Notationen, der Anwendungsbereiche und der wichtigsten Algorithmen.
|