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

Publikationen     Publications

Liste

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

·  Logik WS 2017/18
·  Einige frühere Kurse     Some former courses

                                                                                                                                                                           

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

Beginn: 10.10.17
Zeit/Ort: Vorlesung D19/110 (geändert!), Übungen D19/502 (Beides kann durch neuere Angaben in OBS überholt werden.)

Neues Skript (entspricht weitestgehend den Folien)   ... (in Arbeit)
Altes 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"
Es gehört zum Klausurstoff. --

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)
Es sollen frühestens behandelt (und vorher möglichst selbstständig gelöst) werden:
am 17.(y)+24.(x)10.: Ü1 - Ü10
am 07.(y)+14.(x)11.: Ü6 - Ü26
am 21.(y)+28.(x)11.: Ü13 - Ü35
am 5.(y)+12.(x)12.:   Ü25 - Ü42

am 19.12.(y)+16.1.18(x): Ü33 - Ü50

Zusatzaufgaben zur Wiederholung
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!!! <<<
... (erscheinen jeweils nach der letzten (x-) Übungsstunde, in der sie erarbeitet werden)
Lösungen 1-32

Literatur: siehe Liste im Skript

Inhalt im Detail: grün = bisher im lfd. Semester behandelt (Stand: 07.12.17)
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
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.18, 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
14.02., 12:00, Ort? (kann durch neuere Angaben in OBS überholt sein)
Erlaubte Materialien:
    Skript, Folien, Übungen und Lösungen
von dieser Webseite zu dieser Vorlesung -
    ausgedruckt, sowie anderes original
Handschriftliches.

                                                                                                                                                                           

Frühere Vorlesungen     Former Courses

                                                                                                                                                                           

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

Zeit/Ort: ...

Inhalt (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

Folien
0/10/21/11/21/32/12/22/32/42/52/63/13/23/33/44/14/24/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!

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

                                                                                                                                        

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 ...

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: 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:

                                                                                                                                                                           



Last Change: December 17, 2017



































                                Kaffeelemma*:
               Das Anschauen einer gelösten Übungsaufgabe
     - ohne vorherigen ernsthaften eigenen Bearbeitungsversuch -
     nützt Ihnen oft nur soviel wie der Genuss einer Tasse Kaffee:
            Es bewirkt vorübergehend ein angenehmes Gefühl,
                       hat aber praktisch keinen Lerneffekt!
                                   Anders ausgedrückt:
                 Vom Ansehen der Sportschau werden Sie
                     noch kein(e) Bundesligaspieler(in)!

*) Lemma heißt soviel wie Hilfssatz (für sich nicht so spannend, wird aber bei Beweisen anderer Sätze verwendet).
    Ein Theorem ist ein besonders wichtiger (fundamentaler, Haupt-) Satz.
    Kaffeetheorem hätte zu anspruchsvoll geklungen, und Kaffeesatz wäre irgendwie seltsam ...