Logik und Grundlagen der Informatik 2014/2015

Vorlesung an der DHBW Stuttgart, 2014/2015.

Inhalte

Informatik ist eine Wissenschaft, die Ihre Wurzeln in Mathematik und Logik hat. Die Mengenlehre ist die Grundage der modernen Mathematik und somit auch eine der Grundlagen der Informatik. Sie findet aber auch direkte Anwendung z.B. in der Modellierung von Systemen und Daten. Die Aussagenlogik bildet nicht nur die nahezu universelle Basis für komplexere Logiken, sie ist auch ein direktes Abbild der Schaltvorgänge in digitalen Rechenanlagen. Die Prädikatenlogik ermöglicht es dagegen, auch das Verhalten von sehr großen und sogar unendlichen Systemen in vielen Aspekten exakt zu beschreiben und so sichere Aussagen über Systemeigenschaften zu machen.

In dieser Vorlesung erarbeiten wir diese Grundlagen der Informatik und der symbolischen Logik. Wir lernen das Vokabular und die Verfahren kennen, um formale Systeme und Algorithmen und deren Eigenschaften beschreiben zu können und sichere Schlüsse über Ihr Verhalten machen zu können.

Unterlagen

Folienskript (Hoffentlich fertig, Stand 25.2.2015)
- Vollversion
- Handout (jetzt auch mit weniger Graphik-Problemen)
- Aufgabensammlung (Version 4 vom 24.2.2015 (mit einigen Lösungsansätzen))
- Übungsklausur
- Dieselbe, aber mit Lösungen
- Klausur (die Musterlösung (noch mal nachgebessert) ist eigentlich nur für mich erstellt, also eher kompakt...)
Scheme-Dokumentation
- R5RS (unser Sprachstandard für Scheme)
- Guile, eine empfohlene Implementierung von Scheme
- rlwrap kann dem Scheme-Interpreter zu Kommandozeilen-Editing verhelfen. Es kann auf den meisten Linux-Distributionen mit dem Paket-Manager installiert werden, auf dem Mac z.B. mit Fink
Scheme-Progrämmchen
- Hello World
- Fakultätsberechnung
- Fibonacci (3 Versionen, 2 naiv, eine schnell)
- Revert (2 Versionen)
- Zusatzübung (split/mix)
- Mengenlehre in Scheme
- Beispiel für Zugriff auf Kommandozeilenargumente
- Erzeugen von Listen von Zufallszahlen (in Guile). Aufruf z.B.: guile randlist.scm sortlists.txt
- Datei mit Scheme-Listen von Zufallszahlen
- Potenzmengen in zwei Varianten
- Sortieren durch Einfügen (einfach und generisch)
- Benchmarking für Sortieren durch Einfügen/Mergesort. Erwartet die Datei mit Zufallszahlenlisten im akuellen Ordner. Enthält auch ein Implementierungsbeispiel für Mergesort.
- Eine Lösung für die Türme von Hanoi
- Skalarprodukt und Listenverflachung
- Damen
- Evaluierung von logischen Formeln (leicht funktionaler Overkill ;-)
- Python-Implementierung des aussagenlogischen Tableaux-Kalküls:
  - Library, die Python das grobe Äquivalelent zu Scheme-Symbolen oder C-enums gibt
  - Lexikalische Analyse - Basis für das Einlesen von Formeln
  - Datentyp, der aussagenlogische Formeln repräsentiert
  - Tableux-Beweiser - Kalkül-Library und Hauptprogramm
  - Beispielformeln
  - Vorgehen: Alle Dateien in einem Verzeichnis abspeichern. Aufruf unter Linux z.B. tableaux.py test_expr.txt
    Eventuell müssen die Python-Programme ausführbar gemacht werden (chmod ugo+x *.py) und der Name des Python-Interpreters in der ersten Zeile angepasst werden.

DHBW Stuttgart, Prof. Dr. Stephan Schulz