Vorlesung
"Grundlagen der Theoretischen Informatik" (BSc) /
"Einführung in die Theoretische informatik I" (Dipl)
4.1.1 V4 a In b CV CVBSc InfBSc
Jun.-Prof. Dr.
Bernhard Beckert
4.1.2
Ü2 a In b CV CVBSc InfBSc
Ulrich Koch
Aktuelles
27.09.07: Die Ergebnisse der Nachklausur sind verschickt.
27.09.07: Die Musterlösung zur Nachklausur steht zur Verfügung.
08.08.07: Es gibt nun Musterlösungen für das 1. und das 3. Übungsblatt.
01.08.07: Die Ergebnisse der 3. Teilklausur und die Gesamtergebnisse samt Noten sind verschickt (per Email). Wer sein Ergebnis nicht bekommen hat, moege sich bitte bei mir melden.
01.08.07: Ergebis der Vorlesungsevaluation: ergebnisEvaluation.pdf.
01.08.07: Die Musterlösung zur 3. Teilklausur steht zur Verfügung.
Frühere aktuelle Informationen
Überblick
Zielgruppe
Studierende der
Diplom- und der Bachelorstudiengänge Informatik und Computervisualistik
Inhalte
Die Vorlesung vermittelt die grundlegenden
formalen Konzepten der Informatik und Verständnis für
die prinzipiellen Grenzen
des Berechenbaren bzgl. prinzipieller Unlösbarkeit oder unhandhabbarer
Komplexität.
- Reguläre Sprachen, endliche Automaten (determiniert und
indeterminiert)
- Kontextfreie Sprachen, indeterminierte Push-Down-Automaten
- Kontextsensitive Sprachen, indeterminierte linear
beschränkte Automaten
- Rekursiv aufzählbare Sprachen, determinierte und
indeterminierte Turing-Maschinen
- Unentscheidbarkeit des Halteproblems und verwandter Probleme
- Komplexität und NP-Vollständigkeit des SAT-Problems und
verwandter Probleme
Literatur
Grundlage der Vorlesung ist folgendes Buch:
Katrin Erk, Lutz Priese.
Theoretische Informatik: Eine umfassende Einführung.
2. Auflage.
Springer-Verlag, 2002.
Folien
Die Folien werden jeweils nach der Vorlesung hier zur Verfügung gestellt.
Vollständige Foliensätze zu den Vorlesungsteilen
Folien zu den einzelnen Vorlesungen
Sonstige Materialien zur Vorlesung
- Zur Demonstration von grep:
- Suche nach Kommazahlen: egrep " ([1-9][0-9]*|0),[0-9]+" zahlen.txt
- Die Datei mit Zahlen: zahlen.txt
- Die in der Vorlesung verwendete Datei mit Wörtern beruht auf einem Corpus aus der Leipzig Corpora Collection (kann von dort heruntergeladen werden).
- Das in der Vorlesung erwähnte Buch über den Satz von Fermat:
Simon Singh. Fermats letzter Satz: Die abenteuerliche Geschichte eines mathematischen Rätsels. Deutscher Taschenbuch Verlag, 1997.
- Simulator für endliche Automaten (der Ultimate Turing Simulator von Martin Gwerder):
- Das JAR-File mit dem Simulator: ultimateTuring.jar
- Ein endlicher Automat, der die Sprache der Wörter mit
gerader Anzahl von a's über der Signatur {a} akzeptiert
(Vorlesung am 02.05.07):
dea-2nAs.ts
- Ein endlicher Automat, der die Sprache der Wörter mit
gerader Anzahl von a's und beliebig vielen b's über der Signatur {a,b} akzeptiert
(Vorlesung am 02.05.07):
dea-2nAsAuchBs.ts
- Ein endlicher Automat, der die Sprache der Wörter mit
gerader Anzahl von a's und keinen b's über der Signatur {a,b} akzeptiert
(Vorlesung am 02.05.07):
dea-2nAsKeineBs.ts
- Ein endlicher Automat, der die Sprache aa{ab}*c akzeptiert
(Vorlesung am 02.05.07):
dea-aaabc.ts
- Ein endlicher Automat, der die Sprache akzeptiert, die aus den Dezimaldarstellungen der durch 3 teilbaren natürlichen Zahlen besteht
(Vorlesung am 02.05.07):
dea-dez3.ts
- Ein determinierter endlicher Automat, der die Sprache {ab,aba}* akzeptiert
(Vorlesung am 07.05.07):
dea-ab-aba.ts
- Ein indeterminierter endlicher Automat, der die Sprache {ab,aba}* akzeptiert
(Vorlesung am 07.05.07):
dea-ab-aba.ts
Übungsblätter
Jede Woche, am Montag, erscheint ein Übungsblatt (hier im Web). Die Aufgaben werden in den Übungen der darauffolgenden Woche besprochen.
Die Lösungen können - müssen aber nicht - schriftlich
abgegeben werden. Das birgt die Gefahr in sich, dass sich die
Studenten nicht mit den Aufgaben beschäftigen, sondern im
schlimmsten Falle lediglich in der nächsten Übung die
Lösungen unverstanden abschreiben. Das führt nicht zum
Erfolg! Bitte lösen Sie die Aufgaben selbständig, am besten
in kleinen(!) Lerngruppen von zwei, allenfalls drei Teilnehmern. So
sind Sie für die Klausuren gut vorbereitet.
Scheinerwerb (Klausuren)
Teilklausuren während des Semesters
- Während des Semesters gibt es drei kurze Teilklausuren (von je 30 Minuten Dauer plus 10 Minuten Einlesezeit). Diese finden statt:
- Montag, 14.05., 16 Uhr c.t., Aufteilung auf Räume nach Anfangsbuchstaben des Nachnamens wie folgt: K101 (A-Kad),
F313 (Kae-Sal), E413 (Sam-Z);
1. Teilklausur mit Musterlösung
- Montag, 11.06., 16 Uhr c.t., Aufteilung auf Räume nach Anfangsbuchstaben des Nachnamens wie folgt (wie bei der 1. Teilklausur): K101 (A-Kad),
F313 (Kae-Sal), E413 (Sam-Z);
2. Teilklausur mit Musterlösung
- Mittwoch, 25.07., 11 Uhr c.t, Raum D028;
3. Teilklausur mit Musterlösung.
- Zu den Teilklausuren kann man sich bis Freitag, den 11.05. über
MeToo anmelden. Die Anmeldung ist verbindlich (Nichtteilnahme trotz Anmeldung = 0 Punkte).
- Wer 50% der insgesamt in den drei Teilklausuren zu erzielenden Punkte
erreicht, hat die Prüfung insgesamt bestanden und erhät den Schein. Die Note richtet sich nach der insgesamt erreichten Punktzahl.
- Die Wiederholung einzelner Teilklausuren ist nicht möglich. Ein Freiversuch kann nur für alle Teilklausuren zusammen gesetzt werden.
- Zu den Klausuren sind keine Hilfsmittel (wie Bücher oder Skripten) zugelassen.
Nachklausur zum Ende der Semesters
- Die Nachklausur findet am Dienstag, dem 25.09.07, 10 Uhr, im Hörsaal D028 statt.
Nachklausur mit Musterlösung
- Dazu kann man sich bis Sonntag, den 23.09.07 anmelden (und auch wieder abmelden): MeToo. Danach ist die Anmeldung verbindlich (Nichtteilnahme trotz Anmeldung = nicht bestanden).
- Die Nachklausur hat den gleichen "Wert" wie alle drei Teilklausuren
zusammen (90 Minuten Dauer). Wer sie besteht, bekommt den Schein. Die Note richtet sich dann nach der in der Nachklausur erzielten Punktzahl.
- Achtung: Die Anmeldung zu und Teilnahme an der ersten Prüfung (also den Teilklausuren
während des Semesters) ist Voraussetzung für die Teilnahme
an der Nachklausur. Nur wer diese nicht bestanden oder einen
Freiversuch gesetzt hat, darf an der Nachklausur teilnehmen. Außerdem
darf an der Nachklausur teilnehmen, wer an einer Prüfung zu
"Einführung in die Theoretische Informatik I" in frühren
Semestern teilgenommen und diese nicht bestanden oder einen Freiversuch
gesetzt hat.
Zeit und Ort
Vorlesung
Montags, 16 Uhr c.t., Raum F313
Mittwochs, 10 Uhr c.t., Raum K101
Die Vorlesung beginnt in der ersten Vorlesungswoche. Sie findet
erstmals am 16.04.07 statt.
Übung
Gruppe A: Dienstags, 10 Uhr c.t., Raum F312
Gruppe B: Mittwochs, 14 Uhr c.t., Raum K107
Die Übung beginnt in der zweiten Vorlesungswoche.
Bitte melden Sie sich zu den beiden Übungsgruppen unter MeToo an.
Newsgroup
Newsgroup zur Vorlesung: infko.theoinf
Bernhard Beckert