Formale Methoden der Informatik (WiWi)

Ankündigung

Die Einsicht der Nachlausur ist am Dienstag (22.4.08) von 10:00 bis 11:30 Uhr in O27/531 möglich.

Prüfungstermin:

am 18.02. um 14:00 - 16:00 Uhr

18.2.2008: Die Lösung zur Klausur

Die Prüfungsergebnisse gibt es hier: korrigierte Ergebnisse

Einige Personen haben sich zur Prüfung angemeldet, sind aber unentschuldigt nicht erschienen. Dies ergibt die Note 5,0.

Die Klausuren können eingesehen werden. Der Termin hierzu wird noch hier bekanntgegeben.

7.2.08: Die Anmeldung zur Prüfung ist ab sofort möglich!

Hörsaal-Zuordnung:

Anfangsbuchstabe des Nachnahmen	Hörsaal
A - E	H 1
F - K	H 22
L - O	H 20
P - S	H 2
T - Z	H 3

Keine Hilfsmittel erlaubt! Studenten deren Muttersprache nicht Deutsch ist, dürfen ein Wörterbuch verwenden.

Inhalt

Von realen Systemen, samt aller betreffenden Einwirkungen und Auswirkungen, macht man sich formale Modelle, um diese im Computer speichern, bearbeiten, analysieren, weiter berechnen bzw. Voraussagen ermöglichen zu können. Solche Modelle können sein: (Differential-) Gleichungen, Formeln, logische Aussagen, Graphen, Automaten, Grammatiken, Algorithmen, u.a.m. Informatiker haben ein Vielzahl derartiger Modelle, Konzepte, Beschreibungsmethoden für komplexe Sachverhalte entwickelt, bzw. aus der Mathematik, Linguistik oder Elektrotechnik entlehnt. Diese Modellierungsmöglichkeiten und die dahinter stehenden "algorithmischen Denkweisen" sollen in dieser Vorlesung behandelt werden. Im Einzelnen werden behandelt: Graphen, Grammatiken, Automaten, Berechenbarkeit, NP-Vollständigkeit, Anwendungen in der Kryptografie, formale Logik.

Literatur

Uwe Schöning: Ideen der Informatik, Oldenbourg Verlag.

Übungen

Blatt	Vorlesungsstoff	Material / Links	Lösungsvorschlag
Blatt 1	Graphen	Graphenbeispiele	Lösung 1
Blatt 2	Graphen	Link zu Aufgabe 1	Lösung 2
Blatt 3	Graphen		Lösung 3
Blatt 4	Graphen	Planarity Spiel	Lösung 4
Blatt 5	Graphen	Ford-Fulkerson	Lösung 5
Blatt 6	Graphen,Petri-Netze		Lösung 6
Blatt 7	Grammatiken		Lösung 7
Blatt 8	Endliche Automaten		Lösung 8
Blatt 9	Konstruktionen mit endlichen Automaten		Lösung 9
Blatt 10	reguläre Ausdrücke, Syntaxdiagramme		Lösung 10
Blatt 11	Entscheidbarkeit, Halteproblem		Lösung 11
Blatt 12	Aussagenlogik I		Lösung 12
Blatt 13	Aussagenlogik II		Lösung 13
Blatt 14	Codierungstheorie		Lösung 14
Blatt 15	Probeklausur