Bernd Baumgarten New Home Page

Dr. Bernd Baumgarten

Lehrbeauftragter h_da, FBI
E-Mail: baumgarten_bernd at-symbol web.de

Publikationen Publications

zuletzt: Kompendium der diskreten Mathematik, De Gruyter, 2014
Infoseite
Errata/Korrigenda
Lösungen der Aufgaben in Kapitel 2    Lösungen der Aufgaben in Kapitel 6
Lösungen der Aufgaben in Kapitel 3    Lösungen der Aufgaben in Kapitel 7
Lösungen der Aufgaben in Kapitel 4    Lösungen der Aufgaben in Kapitel 8
Lösungen der Aufgaben in Kapitel 5

Lehre Teaching

· Theoretische Informatik SS 2018
· Einige frühere Kurse Some former courses

Vorlesung (4+2) Theoretische Informatik SS 2018 an der h_da, [Hochschule|University of Applied Sciences] Darmstadt

Zeit/Ort: V: Di+Do 14:15 / D14/204; Ü: Mo 14:15+16:00 / D14/303 (kann durch Änderung in OBS überholt sein)
Beginn: V: Do 05.04.; Ü: Mo 09.04.
Vorlesungsende: Di 26.06.

Inhalt (geplant: schwarz, bis 26.06. behandelt: grün)
0. Organisatorisches
    Einleitung                       Hinführung zu Formalen Sprachen, Komplexitäts- und Berechenbarkeitstheorie,
                                             Problemreduktion, Beispiel: Cliquen in Graphen
    Grundbegriffe                Sprachen, Mengen, Relationen, Graphen, Wege
1. Endliche Automaten      Grundlagen, Minimierung, Nicht-Automaten-Sprachen, Pumping-Lemma
2. Formale Sprachen    Chomsky-Grammatiken, Chomsky-Hierarchie, Kontextsensitive Sprachen
    Reguläre Sprachen       Reguläre Grammatiken, Nichtdeterministische Automaten, Abgeschlossenheitseigenschaften,
                                             Reguläre Ausdrücke
    Kontextfreie Sprachen Grundlagen, Chomsky-Normalform, CYK-Algorithmus, Normalisierung, Kellerautomaten
3. Berechnungstheorie       Grundlagen, Turing-Maschinen, Churchsche These, Algorithmisch unlösbare Probleme,
                                           Halteprobleme, Satz von Rice
4. Komplexität                    Grundbegriffe, Komplexitätsklassen P & NP, Reduktionsergebnisse

Folien (einige mittlerweile geändert mit Mini-Korrekturen)
0/1, 0/2 , 1/1, 1/2, 1/3,
2/1, 2/2, 2/3, 2/4, 2/5, 2/6, 2/7,
3/1, 3/2, 3/3, 3/4, 3/5, 4/1, 4/2, 4/3

Übungsblätter
U-1, U-2, U-3, U-4, U-5, U-6, U-7, U-8, U-9,
U-10+W-1-6, U-11+W-7-12, W-13-16

Lösungen der Wiederholungsaufgaben
W 1-6, W 7-12, W 13-16
... aber beachten Sie das Kaffeelemma!

Ergänzende Materialien
Minimierung eines deterministischen endlichen Automaten - animiert
Über das Pumping-Lemma
Pumping-Lemma, Logisch
Currying
Über wackelnde Tische und Chomsky-Grammatiken
Beschreibungen regulärer Sprachen
Umformung in Chomsky-NF - animiert
CYK - animiert
Erkennen von Klammerausdrücken
Ein kleiner Einblick in den Themenbereich Komplexität
Ein kleiner Einblick in den Themenbereich Kryptologie

Klausur laut OBS (Stand 27.06. 09:00): Do12.07.2018 14:15-15:45 D14/111
Erlaubte Unterlagen: 2 DIN-A4-Seiten Notizen, handschriftlich/ausgedruckt, z.B. meine.

Frühere Vorlesungen Former Courses

1. Vorlesung Logik WS 2017/18 an der h_da, [Hochschule|University of Applied Sciences] Darmstadt

Beginn: ...
Zeit/Ort: ...

Neues Skript (entspricht weitestgehend den Folien)
Mathematische Grundlagen - Aussagenlogik - (Rest, s. altes Skript, noch in Arbeit)
--> Das zusätzliche Sonderskript multimodale/epistemische Logik (ohne Folien)
ist für die Klausur selbstständig durchzuarbeiten, am besten nach "Modale Logiken"
Es gehört zum Klausurstoff.
Altes Skript
Modale Logiken - Prädikatenlogik - Literaturliste & Inhaltsverzeichnis (ohne Sonderskript)

Neue Folien
Mathematische Grundlagen A
Aussagenlogik B C D (mittlerweile um 1 Folie erweitert) E
                          KNF-Animation Resolution-Animation Tableau-Animation (mittlerweile erweitert)
Modale Logiken    F G
Prädikatenlogik H  I
Alte Folien --

Übungsaufgaben
Übungen (mittlerweile geringfügig geändert: 1a, 2b, 6b+c, 25e, 50)
Zusatzaufgaben zur Wiederholung
eine alte Klausur

Tipps: Selbst eigene ...
- Aufgaben erfinden, untereinander austauschen und lösen, z.B.
- Buechi-Aut., Omega-regul. Ausdr., ML-Formeln aufstellen und ineinander umrechnen
- kontingente PL1-Formeln aufstellen und Modelle und Gegenbeispiele suchen
Lieblingsfehler und Punktefresser
Last Minute: (Beantwortete) Fragen von Studierenden nach Vorlesungsende (lfd. aktualisiert, zuletzt 1.2.18)

Lösungen >>> ACHTUNG!!! <<<
Lösungen komplett
Lösungen Zusatzaufgaben
Lösungen alte Klausur

Literatur: siehe Liste im Skript

Inhalt im Detail: grün = bisher im lfd. Semester behandelt (Stand: 20.01.18)
Math. Grundlagen - Mengen, Relationen, Funktionen, Induktion, Rekursion, Grammatiken, Graphen, Bäume
Aussagenlogik - Syntax, semantische Grundlagen, Junktoren, Modelle, Tautologien u.a. spezielle Formeltypen,
Anwendungen, Substitution und Ersetzung, Junktorenbasen, Folgerungen, Wissen, Konjunktive Normalform,
AL-Resolution, Disjunktive Normalform, AL-Tableaux, SAT, Logik-Programmierung, Binary Decision Diagrams,
AL-Kalküle, "Werkzeugkasten", Interpolations- und Kompaktheitssätze
Andere Logiken - Modale Logik, Temporale Logik PLTL, Buechi-Automaten, omega-reguläre Ausdrücke
[Multimodale Logik ist mit Sonderskript selbst zu erarbeiten!]
Prädikatenlogik - Syntax & Anwendungen, Semantik, wichtige Äquivalenzen, Halbentscheidbarkeit, PL1-Kalküle,
PL1-Tableaux, PL1-Werkzeugkasten, Normalformen (PNF, Skolem, Klausel-NF), Erfüllbarkeitsäquvalenz,
Resolution mit Unifikation
Behandlung der Zusatzaufgaben ◄

Prüfungsvorleistungen

Jede(r) Teilnehmende wählt sich zwei der gegebenen PVL-geeigneten Übungsaufgaben
aus, variiert sie auf nicht triviale Weise und löst diese neuen Aufgaben.
Abgabe war per E-Mail bis 15.1.18, als Word-, txt- oder pdf-Datei,
möglichst getippt und kein Foto von Handschrift.
x
Es hat sich wiederum als sinnvoll erwiesen, die PVL frühestmöglich abzugeben!
Gründe: Sie können die Rückmeldung erhalten, dass die Aufgabe zu einfach,
fehlerhaft gestellt oder falsch gelöst ist. Dann wird die Zeit zur Korrektur knapp -
erst recht, wenn am Ende alle auf einmal abgeben, viel zu überprüfen ist
und die Rückmeldungen daher spät kommen.

Klausur ...
Erlaubte Materialien:
Skript, Folien, Übungen und Lösungen von dieser Webseite zu dieser Vorlesung -
ausgedruckt, sowie anderes original Handschriftliches.

2. Vorlesung Petrinetze WS 2008/09 an der h_da, Hochschule Darmstadt

Stoff:
Spezifikationen und formale Sprachen, Induktion und Rekursion
Akzeptoren (Automaten), kanonischer Akzeptor einer Sprache, Grammatiken,
reguläre Ausdrücke, kommunizierende Automaten, Netzgraphen, ST-Systeme
Netzdynamik, Netzsprachen, Übungen
Netzsprachen weiter, Lebendigkeit, Analyse-Ziele, Übungen
Erreichbarkeitsanalyse + Übungen, Überdeckungsanalyse
Überdeckungsanalyse + Übungen, Lineare Analyse
Analyse-Übungen, Nebenläufigkeitsaspekte, High Level Petri Nets (HLPN)
HLPNs: Anwendung und Übungsaufgaben (1)
HLPNs (2), Netze mit quantitativer Zeit (1)
Netze mit quantitativer Zeit (2), Übungsaufgaben zur Wiederholung
Übungsaufgaben zur Wiederholung

Skript
Seiten 1 bis 8
Seiten 9 bis 16
Seiten 17 bis 24
Seiten 25 bis 30

Lösungen der Modellaufgaben >>> ACHTUNG!!!
1: Induktive Mengen- und rekursive Funktionsdefinitionen
2: Kanonischer Akzeptor und reguläre Ausdrücke
3: Netzsprachen
4: Netzsprachen
5: Grammatiken, Ziel-Netzsprachen
6: Erreichbarkeitsanalyse
7: Erreichbarkeitsanalyse, Erreichbarkeitsanalysegraph
8: ST-System für einen Erreichbarkeitsgraphen vorgegebener Form
9: Überdeckungsanalyse
10: Überdeckungsanalyse
11: Netze mit individuellen Marken (HLPN)
12: Netze mit individuellen Marken (HLPN) und Faltung
13: Systemmodellierung mit HLPN
14: Timernetze

Worum geht es bei den Petrinetzen?

Petrinetze sind ein formales Beschreibungsmittel (FBM) für das Verhalten verteilter
Systeme. Sie verallgemeinern auf naheliegende Weise die endlichen Automaten.

Mit FBMs allgemein kann man Systeme (in gewissem Sinne) mathematisch genau
spezifizieren. Mit einer formalen Spezifikation kann man in vielen Fällen ...

alle möglichen Verhaltensweisen eines spezifikationsgemäßen Systems untersuchen,
prüfen, ob ein spezifikationsgemäßes System gewünschte Dinge tun oder unerwünschte unterlassen wird,
prüfen, ob eine Implementierung (mit formaler Semantik) die Spezifikation erfüllt,
rasch eine evtl. langsame Implementierung erzeugen (rapid prototyping),
Testfälle für Implementierungen automatisch generieren,
schon beim Hinschreiben Fehler in der informellen Spezifikation finden.

Viele Analysemethoden für die obigen Aufgaben existieren in jeweils angepasster Form für
fast alle FBMs. Petrinetze zeichnen sich aber vor anderen FBMs durch ihre anschauliche
Verständlichkeit und spezielle - nur bei ihnen funktionierende - Analysemöglichkeiten aus.

3. Course Formal Methods WS 2007/08 at h_da, University of Applied Sciences Darmstadt

Achtung: Aus mir nicht ganz klaren Gründen hielten wir die Vorlesung auf Deutsch
but with English slides and lecture notes.
Aber wir sind ja auch Dinge wie "Back-Shops" gewohnt ... (Gegenteil: Forward-Shop?)
und eine Ausstellung "Boot & Fun" (bei der es gar nicht um Stiefel geht!).
Als Hilfestellung für die Hörer gab es ein partielles einschlägiges Vokabelverzeichnis.

My part of the course covered
Petri Nets and Abstract Data Types.
Mathematical preliminaries, languages, canonical automaton of a language
Languages continued, PT systems
PT systems continued; Analysis introduction
Net languages: target markings, exercises.
Analysis of PT systems: Boundedness, Reachability analysis (2 Exercises), Coverability analysis (Part 1)
Part 2+Exercise Coverability analysis, Linear analysis
High Level Petri Nets (HLPNs)
Abstract data types (ADT) overview
Data objects, data types, abstraction
Single-/many-sorted algebras and signatures, isomorphisms,
Congruences, quotients. Assignment, evaluation, substitution. Consequences of axioms
Junk, confusion, and initiality.What is specified by an ADT spec?
ADT Practicalities and extensions. PN and ADT review exercises.

Course Notes
PN+ADT notes
Model Exercises for Petri Nets
Model Exercises for ADTs
Additional Exercises
Languages and PT Systems, Abstract Data Types
Additional Petri net exercises in German can be found here.
Additional Help
1. Two people asked about additional exercise #9(b).
    I thought it might be in order here to review a few ADT notions and give some hints.
2. Some people use programming language assignments in transiton conditions of HLPNs.
    Don't! Here is why.

4. Druskininkai Lectures (May 2007)

Corrected + supplemented version of slides:

Last Change: June 27, 2018