| 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 2017· Einige frühere Kurse Some former courses
Vorlesung (4+2) Theoretische Informatik SS 2017 an der h_da, [Hochschule|University of Applied Sciences] Darmstadt
Zeit/Ort: 29.06.2017, 3. Block: fällt ausInhalt (geplant,
mittlerweile behandelt: grün)
0. Organisatorisches
Einleitung
Hinführung zur 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, CYK-Algorithmus, Chomsky-Normalform, 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
5. Ausblick
Kryptographie
0/1, 0/2, 1/1, 1/2, 1/3, 2/1, 2/2, 2/3, 2/4, 2/5, 2/6, 3/1, 3/2, 3/3, 3/4, 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
Lösungen der Wiederholungsaufgaben ... aber beachten Sie das Kaffeelemma! (klingt besser als Kaffeesatz)
Ergänzende Materialien
Minimierung eines deterministischen endlichen Automaten - animiert
Über das Pumping-Lemma
Pumping-Lemma, Logisch
Currying
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
17.07.2017, 14:15-15:45, D14/004 (im Zweifelsfalle hat OBS Recht)
Erlaubte Materialien: Merkzettel für Klausur (aktuelle Version) doppelseitig ausgedruckt, auch mit manuellen Randnotizen
Frühere Vorlesungen Former Courses
1. Vorlesung Logik WS 2016/17 an der h_da, [Hochschule|University of Applied Sciences] Darmstadt
 (W. Shakespeare) |
Beginn: 5.10.16
Zeit/Ort: ...
Neues Skript (entspricht weitestgehend den Folien)
Mathematische Grundlagen - Aussagenlogik - Modale Logiken - Prädikatenlogik
Literaturliste & Inhaltsverzeichnis (ohne Sonderskript)
-- Das zusätzliche Sonderskript multimodale/epistemische Logik (ohne Folien)
ist für die Klausur selbstständig durchzuarbeiten, am besten nach "Modale Logiken" --
Neue Folien
Mathematische Grundlagen A
Aussagenlogik B C D E
KNF-Animation Resolution-Animation Tableau-Animation
Modale Logiken F G
Prädikatenlogik H I
Neue Übungsaufgaben
Übungen
Voraussichtlich werden am 11.01.17 die restlichen Übungen besprochen.
Zusatzaufgaben zur Wiederholung
Alt
eine alte Klausur
Lieblingsfehler und Punktefresser
Last Minute: (Beantwortete) Fragen von Studierenden nach Vorlesungsende
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
Lösungen >>> ACHTUNG!!! <<<
Lösungen 1-59 25a-Lösung korrigiert
Zusatzaufgaben 1-24
alte Klausur
Literatur: siehe Liste im Skript
Inhalt im Detail: grün = bisher im lfd. Semester behandelt
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, Theorien, 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
[Multimodale Logik ist mit Sonderskript selbst zu erarbeiten!]
Prädikatenlogik - Syntax, 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 ◄
evtl. Beschreibungslogik
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 ist per E-Mail bis 15.1.17, als Word-, txt- oder pdf-Datei,
möglichst getippt und kein Foto von Handschrift.
x
Es hat sich 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 01.02. D14/204 (laut obs vom 20.01.)
Erlaubte Materialien:
Skript, Folien, Übungen und Lösungen von dieser Webseite zu dieser Vorlesung -
ausgedruckt, auch mit handschriftlichen Randnotizen - 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 Deutschbut with English slides and lecture notes.
Aber wir sind ja auch Dinge wie "Back-Shops" gewohnt ... (Gegenteil: Front-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:- Formal specification, observability, discreteness, and languages
- Abstract Data Types
- Petri Net Basics
- High Level Petri Nets 1
- High Level Petri Nets 2
- Petri Nets with Timing Notions