Algorithmen zur Automatentheorie
SoSe 10 (Ankündigung)
Organisatorisches
Dozentin: Wiebke Petersen
Sitzungen: Mo. 18-20 Uhr in Raum 23.21.04.87
Sprechstunde: Do. 16:00-17:00 in Raum 23.21.04.45
Telefon: 81-15295
Dieser Kurs kann in zwei Varianten studiert werden:
- Variante 1 für Personen mit eher fortgeschrittenen Programmierkenntnissen: Teilnahme an den Sitzungen und gemeinsame Erstellung eines modular aufgebauten Systems zur Verarbeitung endlicher Automaten, rechtslinearer Grammatiken und regulärer Ausdrücke
- Variante 2 für Personen mit geringen Programmierkenntnissen: Selbständiges Erlernen einer Programmiersprache und Bearbeitung einer kleinen Programmieraufgabe zum Ende des Semesters
Hinweise:
- Hinweis für Variante 1: Bitte meldet Euch bei Origo an und schickt Euren Nutzernamen an Peter (siehe Email). Origo-Seite des Kurses
- Übungsaufgabe für Variante 2 (prozedurale Programmiersprachen): Die Textdatei (a136lw1000.txt) enthält die offiziellen Ergebnisse der Landtagswahlen. Schreiben Sie bitte ein Programm, um die Daten auszulesen. Folgende Fragetypen sollten beantwortet werden können (nach Schwierigkeit sortiert): Wieviele Stimmen bekam die SPD in dem Wahlkreis Düsseldorf II? Welchem prozentualen Stimmanteil entspricht das? In welchem Wahlkreis holten die Grünen absolut die meisten Stimmen, in welchem prozentual? Welches ist das insgesamt höchste prozentuale Ergebnis, das eine Partei in einem Wahlkreis geholt hat? In welchem Wahlkreis war die Wahlbeteiligung am geringsten?
- Übungsaufgabe für Variante 2 (Prolog): Schreiben Sie ein Programm, das endliche Automaten in rechtslineare Grammatiken und rechtslineare Grammatiken in endliche Automaten umwandelt.
Aufgabe für Variante 2:
- Die Aufgabe finden Sie hier. Elektronische Abgabe bis zum 26.7.2010.
Sitzungen (für Variante 1)
| Datum | Thema |
|---|---|
| 12.4.2010 | Vorbesprechung |
| 19.4.2010 | Einführung und Übung |
| 26.4.2010 | Festlegung eines externen Dateiformats (Aufgabe 1+2) |
| 3.5.2010 | keine Präsenzsitzung |
| 10.5.2010 | Umwandlung NEA in DEA (Aufgabe 3+4) |
| 17.5.2010 | keine Präsenzsitzung |
| 24.5.2010 | fällt aus: Feiertag |
| 31.5.2010 | Umwandlung Typ3 Grammatik - endlicher Automat |
| 7.6.2010 | keine Präsenzsitzung |
| 14.6.2010 | Minimierung endlicher Automaten, Prüfung der Äquivalenz minimaler Automaten |
| 21.6.2010 | keine Präsenzsitzung |
| 28.6.2010 | effizientere Minimierung |
| 5.7.2010 | keine Präsenzsitzung |
| 12.7.2010 | Zusammenbau der einzelnen Module |
| 19.7.2010 |