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 NachnahmenHörsaal
A - EH 1
F - KH 22
L - OH 20
P - SH 2
T - ZH 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   
VorlesungsstoffMaterial / LinksLösungsvorschlag
Blatt 1GraphenGraphenbeispieleLösung 1
Blatt 2GraphenLink zu Aufgabe 1Lösung 2
Blatt 3GraphenLösung 3
Blatt 4GraphenPlanarity SpielLösung 4
Blatt 5GraphenFord-Fulkerson Lösung 5
Blatt 6Graphen,Petri-NetzeLösung 6
Blatt 7GrammatikenLösung 7
Blatt 8Endliche AutomatenLösung 8
Blatt 9Konstruktionen mit endlichen AutomatenLösung 9
Blatt 10reguläre Ausdrücke, SyntaxdiagrammeLösung 10
Blatt 11Entscheidbarkeit, HalteproblemLösung 11
Blatt 12Aussagenlogik ILösung 12
Blatt 13Aussagenlogik IILösung 13
Blatt 14CodierungstheorieLösung 14
Blatt 15Probeklausur

Vorlesungszeiten

Mittwoch   14:00  -  16:00 H22
Donnerstag   10:00  -  12:00 H20

 

Übungsleiter

Adrian Balint

Tutorien

 Alle Räume befinden sich in O27

Termin Raum Semester
Mo 10-121221
Do 10-1232113
Di 08-10 20031
Mi 10-121213
Do 10-12H203
Fr 08-10H211
Fr 12-141231

Weiter Informationen

LSF-Eintrag