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

Publikationen     Publications

Liste

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 2016/17
·  Einige frühere Kurse     Some former courses

                                                                                                                                                                           

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

2b v ~2b = ?
(W. Shakespeare)

Beginn: 5.10.16
Zeit/Ort: Vorlesung/Übung (beides im Plenum und ohne festen Wechselrhythmus)
                Mi 08:30 in 303(x)/111(y), Do 14:15 in 303

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 1_59
Voraussichtlich werden am 07.12.16 die Übungen 44 bis etwa 46 besprochen.
Alte Übungsaufgaben SS 2016
Zusatzaufgaben zur Wiederholung
eine alte Klausur
Lieblingsfehler und Punktefresser

Last Minute: (Beantwortete) Fragen von Studierenden nach Vorlesungsende SS 2016

Tipps: Selbst eigene ...
- Aufgaben erfinden, untereinander austauschen und lösen
- 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_43

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, (bis Folie H-291) 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
Erlaubte Materialien:
    Skript, Folien, Übungen und Lösungen
von dieser Webseite zu dieser Vorlesung -
    ausgedruckt, auch mit handschriftlichen Randnotizen - sowie anderes original
Handschriftliches.

                                                                                                                                                                           

Frühere Vorlesungen     Former Courses

                                                                                                                                                                           

1. Vorlesung Theoretische Informatik WS 2015/16 an der h_da, [Hochschule|University of Applied Sciences] Darmstadt

Beginn: Vorlesung 6.10., Übungen 14.10.
Zeit/Ort: Vorlesung Di1(x-Wochen) und Mi2 (x+y) in 111; Übung Mi4 (x/y) in 404

Inhalt (behandelt: grün)
Organisatorisches, Motivation, Einordnung (mit Beispielen zur Komplexitäts- und Berechenbarkeitstheorie)
Grundbegriffe  Sprachen, Mengen, Relationen, Graphen, Wege

Endliche Automaten
Grundlagen, Minimierung, Nicht-Automaten-Sprachen,
Pumping-Lemma,
Formale Sprachen Chomsky-Grammatiken
Reguläre Sprachen Reguläre Grammatiken, Nichtdeterministische Automaten, Abgeschlossenheitseigenschaften, Reguläre Ausdrücke
Kontextfreie Sprachen Grundlagen, CYK-Algorithmus, Chomsky-Normalform, Kellerautomaten

Berechnungstheorie
Grundlagen, RAM, Turing-Maschinen, Churchsche These, Algorithmisch unlösbare Probleme, Satz von Rice

Wiederholung
Besprechung der Übungen zur Wiederholung (s.u.)
ggf. noch Ausblicke
Kryptographie, Komplexität

Folien
0-10-21-1 1-21-32-1 2-22-32-4 2-52-63-13-2 3-33-4, Komplexität, Kryptologie

Übungsblätter  
Ueb1,
Ueb2, Ueb3, Ueb4, Ueb5,
Übungen  zur Wiederholung

Ergänzende Materialien
Minimierung eines deterministischen endlichen Automaten - animiert
   NEU: 2 Methoden
             - Dreiecksmatrix (kurz und etwas riskant)
             - Klassenübergangstabellen (lang und etwas sicherer)

Über das Pumping-Lemma
Pumping-Lemma, Logisch
Beschreibungen regulärer Sprachen
Umformung in Chomsky-NF - animiert
CYK - animiert
Erkennen von Klammerausdrücken

Klausur
Erlaubte Materialien: Merkzettel für Klausur

                                                                                                                                        

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: Dec 01, 2016




































               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,
                          aber praktisch keinen Lerneffekt!
                                   Anders ausgedrückt:
                 Vom Ansehen der Sportschau werden Sie
                     noch kein(e) Bundesligaspieler(in)!