| 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.
|
| Bemerkung |
*Die Teilnahme an einer Übung (Wahlalternative) ist verpflichtend.
Mo, 08:00-10:00 Uhr, SA 018 (ÜB1)
Mo, 12:00-14:00 Uhr, SA 018 (ÜB2)
Mo, 14:00-16:00 Uhr, SA 018 (ÜB3)
Mo, 16:00-18:00 Uhr, SA 018 (ÜB4)
Mi, 08:00-10:00 Uhr, SM 205 (ÜB5)
Mi, 12:00-14:00 Uhr, SM 205 (ÜB6)
Do, 08:00-10:00 Uhr, SM 205 (ÜB7)
Do, 12:00-14:00 Uhr, SM 205 (ÜB8)
Fr, 08:00-10:00 Uhr, SM 205 (ÜB9)
Fr, 12:00-14:00 Uhr, SE 005 (ÜB10)
Übungen, die zeitlich vor der Vorlesung liegen, beginnen in der folgenden Woche.
Bitte melden Sie sich hier ausschl. für das fachfremde Modul E3 Studium liberale an. (Als Fachstudent wählen Sie zur Anmeldung das fachintern übliche Verfahren, bei LSF: die gleichnamige Veranstaltung ohne das Präfix "E3".)
Online-Anmeldung ab dem 19.09.2014. Alle Veranstaltungen als Vorlesungsverzeichnis im PDF-Format sowie weitere Details finden Sie unter dem oben genannten Link. |
