Dr. Bernd Baumgarten   Fraunhofer - SIT  Rheinstr. 75  D-64295 Darmstadt  Germany

Tel (+49 or 0) 6151 - 869 263                           Fax (+49 or 0) 6151 - 869 224  E-mail bernd.baumgarten at-symbol sit.fraunhofer.de

Working for Fraunhofer

·  Fraunhofer-Gesellschaft

·  Fraunhofer Institute for Secure Information Technology SIT

·  SIT-Betriebssport Swing-Tanzen

Teaching

·  Theoretische Informatik (Grundlagen)

·  Former Courses of Mine

Yours Truly

·  My Research Interests + Publications
·  My Hobbies

                                                                                                                                                                          

Vorlesung Theoretische Informatik SS 2009 an der h_da, Hochschule Darmstadt

Zeit/Ort
ab 24.03.09
Di., 08.30 Uhr Informatik D14, Raum 004
Mi., 08:30 Uhr D19, Raum 06

Folien (am besten ausdrucken, mitbringen und ggf. Notizen draufschreiben)
0_1 Organisatorisches, Motivation
0_2 Mathematische Grundbegriffe
1_1 Endliche Automaten - Grundlagen
1_2 Endliche Automaten - Minimierung
1_3 Endliche Automaten - String Matching
2_1 Chomsky-Grammatiken
2_2 Reguläre Sprachen - reguläre Grammatiken, ND-Automaten
2_3 Reguläre Sprachen - Abgeschlossenheit gegen ..., Pumping-Lemma
2_4 Kontextfreie Sprachen
2_5 Kellerautomaten, D und ND
2_6 Markup-Sprachen
3_1 Berechnungstheorie - Einordnung
3_2 Berechenbarkeitsmodelle - Random-Access-Maschine, Turing-Maschine
3_3 Churchsche These
3_4 Algorithmisch unlösbare Probleme, Entscheidbarkeit, Halteproblem
4_1 Komplexitätstheorie - Einordnung
4_2 Komplexitätsklassen P und NP, P=NP?
4_3 NP-Vollständigkeit
15.07.09 12:00-13:30 Klausur

NEU  Noten

Knappe Notizen, Verwendung in der Klausur zulässig; weitere Hilfsmittel sind nicht zugelassen.
Zusätzliche Übungen (nun mit Lösungen)
Antworten auf Fragen zum Pumping-Lemma, die bei der Wiederholung zu kurz kamen.

Übungsblätter Vorsicht!
Blatt 1 Relationen, Endliche Automaten
Blatt 2 Endliche Automaten, Minimierung
Blatt 3 Stringmatching, Grammatikableitung, ND-Automaten, Regularität
Blatt 4 Pumping Lemma, Regularität, Chomsky-NF & CYK-Algorithmus
Blatt 5 Kontextfreie Sprachen, Kellerautomaten
Blatt 6 RAM-Programme, Turing-Maschinen
Berechenbarkeit, Reduzierbarkeit (an der Tafel)


                                                                                                                                                                          

Former Courses

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

Zeit: Di., 08.30 Uhr
Ort: Informatik, Raum 303
Bisheriger 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 Vorsicht!
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.

In der Vorlesung arbeiten wir mit vielen praktischen Beispielen, auch solchen außerhalb der
Datenverarbeitung.

2. Vorlesung Logik SS 2008 an der h_da, [Hochschule|University of Applied Sciences] Darmstadt

(W. Shakespeare)

Zeitprotokoll und - plan
Skript und Übungen

Wir lernen intensiv Prinzipien und Methoden der Lo­gik kennen, aber keineswegs alle Bereiche, so z.B. die Prädika­tenlogik nur in den Grundzügen!

Bisheriger Stoff
01.04.08 Rekapitulation mathematischer Werkzeuge 1 (Mengen, Relationen, Funktionen)
08.04.08 Rekapitulation mathematischer Werkzeuge 2  (Induktion, Rekursion, Grammatiken, Graphen, Bäume),
15.04.08 aussagenlogische Formeln, Wahrheitswert, Wahrheitstafeln, Junktoren allgemein
22.04.08 Semantische Grundbegriffe, wichtige Tautologien, logische Konstanten, Schaltwerke
29.04.08 Substitution und Ersetzung, Junktorenbasen, Folgerungen und Theorien
06.05.08 AL-Algorithmen (1): Konjunktive Normalform, Resolution
13.05.08 Pfingstfrei
20.05.08 Übung Resolution, AL-Algorithmen (2): Disjunktive Normalform und Tableaux
27.05.07 Übung Tableaux, SAT, AL-Algorithmen (3): Binary Decision Diagrams (BDDs)
03.06.07 Aussagenlog. Kalküle (die axiomatische Methode), Gentzen-Kalkül, "AL-Beweis-Werkzeugkasten"
10.06.07 Werkzeugkastenübungen, Syntax der Prädikatenlogik erster Stufe ("PL1")
17.06.07 Restliche PL1-Syntax und PL1-Semantik
24.06.07 Rest PL1-Semantik, PL1-Werkzeugkasten, PL1-Problematik im Vergleich zu AL
01.07.07 Klausur in Raum D14/004

Skript, Lösungen
Skript Seiten 1-12,
Seiten 13-19, S. 16 am 2.6.08 korrigiert,
Seiten 20-26

Lösungen  Vorsicht! Aufgaben 1-31 2 Klammern in Aufg. 29 ergänzt
ab 24.06. 10 Uhr ! : Lösungen Aufgaben 32-34

Zusatzaufgaben 2007, mit Korrekturen vom 27.06.07
Die meisten sind typische Klausuraufgaben (nämlich der letzten Jahre).                                                                                                                                                                            

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: Front-Shop?)
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

                                                                                                                                                                           

If you care to know: I am also interested in ...

• Dancing (now Swing, i.e. Lindy Hop, East Coast, Charleston, Balboa;

                        formerly Standard and Latin ballroom, Line dance) 

• Languages (natural, not formal ones)
• History (once my weakest subject at school, and in spite of Nietzsche's warnings in

                       "Vom Nutzen und Nachtheil der Historie für das Leben")

• Logic (beyond the lecture above)
• Aikido (THE - now former - hobby of mine for 25 years)
• Guitar (formerly - I never got really good and haven't practiced for years now)
• how to find the time necessary to pursue these and other interests.

Are you interested in any of  these topics?
I've got a private homepage dealing with (some of) them.
Topics (partially) covered by now:
- Line dancing
- Logic
- Swing dancing

Last Change: July 27, 2009