Informatik III

Allgemeines

Aktuelles

Neue Seite
Diese Seiten sind nicht mehr aktuell.

Inhalte

Worum geht es:

Im Gegensatz zu anderen Grundstudiumsvorlesungen werden hier Themen behandelt, die weiter von den Anwendungen entfernt sind. Es geht um prinzipielle Fragestellungen, d.h. Fragen, die zum Beispiel unabhängig von „Programmierungsaspekten“ oder „konkreten Rechnern“ sind.

Typische Fragestellungen:

  • Gibt es Aufgaben, die von einem Rechner – unabhängig von der Art der Programmierung beziehungsweise von physikalischen und elektronischen Beschränkungen – nicht gelöst werden können?
  • Welche Aufgaben können prinzipiell effizient (in vernünftiger Rechenzeit, mit vernünftigem Speicherplatzbedarf) gelöst werden?

Einige Themen:

Deterministische und nicht deterministische endliche Automaten, Turing-Maschinen, Berechenbarkeit, Church'sche These, Sprachen, P und NP, NP-vollständige Probleme, Grammatiken, Chomsky-Hierarchie …

Termine

Veranstaltung Zeit Beginn 2003 Ende 2004
Vorlesung Mittwoch 11.30-13.00 Mi. 15.10. Mi, 11.02.
Freitag 11.30-13.00 Fr. 17.10. Fr, 13.02.
Übung Donnerstag 11.30-13.00 Do, 23.10. Do, 12.02.

Newsgroup

Die Newsgroup uka.info3 dient der Diskussion von inhaltlichen und organisatorischen Fragen zur Vorlesung, Übung und den Tutorien in Informatik III an der Universität Karlsruhe im Wintersemester 03/04. Wir begrüßen es, wenn Studenten ihre Probleme in der Newsgroup untereinander lösen. Zur technischen Verwendung des Newsservers der Universität siehe http://news.rz.uni-karlsruhe.de.

Material

  • zum Pumping-Lemma (PDF)
  • zum Äquivalenzklassenautomaten (PDF)
  • Musteraufgaben zur Klausurvorbereitung… (PDF)
  • … und deren Lösungen (PDF)
  • Musterklausur… (PDF)
  • … Lösungen zur Musterklausur (PDF)
  • 1. Klausur mit Lösungen (PDF)
  • 2. Klausur mit Lösungen (PDF)

Übungsblätter

Warum Übungsblätter?

Vorlesung und große Übung können Lehrmaterial nur präsentieren. Tutorien machen es verständlicher und helfen bei individuellen Problemen. Aber allein die Übungsblätter zwingen zur tatsächlichen Auseinandersetzung mit dem Material. Sie zeigen Euch und uns, was verstanden wurde, und wo Lücken bestehen.

Wir raten dringend, die Übungsblätter selbstständig und kontinuierlich zu bearbeiten. Fremde Lösungen als die Eigenen auszugeben ist nicht nur unehrlich. Durch Abschreiben schadet Ihr allein Euch selbst - spätestens in der Klausur müsst Ihr selbstständig arbeiten.

Allgemeine Geschäftsbedingungen

Die im Folgenden gegebenen Informationen können sich noch im Detail ändern, beabsichtigt ist jedoch Folgendes:

Jedes Übungsblatt hat zwei Sorten von Aufgaben. Rechnerübungen wird es nicht geben. Der erste Teil beschäftigt sich überwiegend mit dem Stoff der Vorlesung in der Woche der Ausgabe. Diese Aufgaben werden eine Woche später in der großen Übung am Donnerstag besprochen.

Der zweite Teil befasst sich überwiegend mit dem Stoff der Vorwoche. Diese Aufgaben sollten eine Woche nach der Ausgabe, am Donnerstag bis 14 Uhr in den mit 'Informatik III' beschrifteten Einwurfschlitz im Keller des Informatikgebäudes eingeworfen werden. Die Blätter sind zusammenzuheften, oben rechts mit der Nummer des Tutoriums zu versehen und sollten außerdem Namen und dem Namen der Vorlesung ('Informatik III') enthalten. Das ganze sollte etwa so aussehen:

[Tacker] Matrikelnummer Übungsblatt X Tut.nr.
Name, Vorname Informatik III


Sie werden dann von den Tutoren korrigiert und in den Tutorien der Folgewoche zurückgegeben und besprochen. Die Abgabe kann und soll in Zweiergruppen erfolgen. Beide Teammitglieder sollten dann in einem Tutorium sein.

Die bearbeiteten Aufgaben werden mit Punkten bewertet. Für jedes Übungsblatt können etwa gleich viele Punkte erreicht werden. Wer am Ende des Semesters mindestens 50% der Punkte erhalten hat und darüber hinaus aktiv an den Tutorien teilgenommen und mindestens einmal seine Lösung vorgeführt hat, bekommt auf die Note der bei uns bestandenen Klausur einen Bonus von 0,3. Eine ohne diesen Bonus nicht bestandene Klausur kann dadurch jedoch nicht noch als bestanden gewertet werden.

Newsgroup

Die Newsgroup uka.info3 dient der Diskussion von inhaltlichen und organisatorischen Fragen zur Vorlesung, Übung und den Tutorien in Informatik III an der Universität Karlsruhe im Wintersemester 03/04. Wir begrüßen es, wenn Studenten ihre Probleme in der Newsgroup untereinander lösen. Zur technischen Verwendung des Newsservers der Universität siehe http://news.rz.uni-karlsruhe.de.

(Nicht mehr) Aktuelles

21.4.2004 Nachklausur – Ergebnisse
Die Klausurergebnisse sind im Foyer vor der Informatik-Bibliothek ausgehängt. Die Klausur mit Lösungen ist in der Rubrik „Zusatzmaterial“ veröffentlicht. Eine Notenstatistik ist hier.
Die Klausureinsicht findet am Montag, 26. April 2004 im Raum -108 im Informatik-Hauptgebäude statt. Ab 13 Uhr bevorzugt für diejenigen, die im Audimax geschrieben haben und ab 16 Uhr bevorzugt diejenigen, die im HSaF geschrieben haben.
Die mündlichen Nachprüfungen (bei nicht bestandenen Wiederholungsprüfungen) finden am 5. und 6. Mai statt. Anmeldung dazu ab sofort bis 30. April im Sekretariat.
8.4.2004 Nachklausur – Update
Die Studierenden mit folgenden Matrikelnummern sind noch „nachnominiert“: 893401, 1153795, 1154618, 1157855; Platznummern 58 bis 61 im HSaF!
6.4.2004 Nachklausur
Die Raumeinteilung für die 2. Klausur am Mittwoch, 14.4.2004, 11.00 Uhr s.t. hängt aus am schwarzen Brett, gegenüber dem Sekretariat, Info-Gebäude, 3. Stock, Raum 321 und hier: PDF, PS. Bitte rechtzeitig erscheinen und Studentenausweis mitbringen!
8.3.2004 Mündliche Nachprüfung(en)
Die 1. mündliche Nachprüfung findet am Dienstag, 30. März 2004, ab 13:00 Uhr statt. Anmeldung dazu ab sofort im Sekretariat (Raum 321). Die 2. mündliche Nachprüfung findet voraussichtlich Ende April statt.
3.3.2004 Notenstatistik
Eine Notenstatistik zur ersten Klausur befindet sich hier.
2.3.2004 Zweite Klausur
Die zweite Klausur findet am Mittwoch, 14. April 2004, 11:00 Uhr statt. Anmeldungen dazu bis spätestens Montag, 5. April 2004, 16:00 Uhr, in den Briefkasten am schwarzen Brett gegenüber dem Sekretariat (Raum 321).
2.3.2004 Klausurergebnisse und -einsicht
Die Klausurergebnisse sind im Foyer vor der Informatik-Bibliothek ausgehängt. Die Klausureinsicht findet am Dienstag, 9. März 2004, 14-16 Uhr im Raum SR 301 im Informatik-Hauptgebäude statt.
24.2.2004 Klausur – Lösung
In der Rubrik „Zusatzmaterial“ gibt es die Klausur mit Lösung zum runterladen. Mit den Ergebnissen ist, wie angekündigt, bis Anfang nächster Woche zu rechnen.
Studenten mit folgenden Matrikelnummern sind ohne sich abgemeldet zu haben nicht zur Klausur erschienen. Falls sie nicht umgehend ein Attest vorweisen, gilt die Klausur für sie als nicht bestanden:
1107399, 1108712, 1132114, 1152974
20.2.2004 Klausur
Die Raumeinteilung für die 1. Klausur am Freitag, 20.2., 11.00 Uhr s.t. hängt aus am schwarzen Brett, gegenüber dem Sekretariat, Info-Gebäude, 3. Stock, Raum 321 und hier: PDF, PS. Bitte rechtzeitig erscheinen!
4.2.2004 Server-Umstellung
Bei uns gab es heute eine Server-Umstellung. Von der Homepage aus sollte aber alles wie gewohnt funktionieren. Bitte aber evtl. vorhandene „tiefe Links“ von „i11test“ auf „i11www“ umstellen.
4.2.2004 Musterklausur
Eine Musterklausur mit Lösungen ist ab sofort in der Rubrik „Zusatzmaterial“ der Info III Webseiten zu finden. Die vorgesehene Bearbeitungszeit beträgt 1 Stunde.
23.1.2004 Anpassung Übungsblatt 13
Zu beachten: Auf Übungsblatt 13, Aufgabe 7 ist die Fragestellung geändert worden zu „Ist der Schnitt einer kontextfreien mit einer regulären Sprache regulär?“ (die Frage nach der Kontextfreiheit wird auf das 14. Übungsblatt verlegt).
Leider bedeutet dies auch eine Anpassung der erreichbaren Punkte für diese Aufgabe auf 2. (Insgesamt sind die Aufgaben auf diesem Übungsblatt jedoch relativ einfach gehalten, sodass sich die Bearbeitung auch punktetechnisch auf jeden Fall lohnt! ;-) )
15.1.2004 Klausur; Anmeldung
Die Klausur findet am Freitag, 20. Februar 2004, um 11.00 Uhr statt (Raum wird noch bekanntgegeben werden).
Anmeldung ist bis 13. Februar 2004 möglich; hierzu bitte die Prüfungsscheine in den Briefkasten am schwarzen Brett gegenüber dem Sekretariat (Raum 321) einwerfen. Abmeldungen können bis kurz vor Beginn der Klausur erfolgen.
Zur Klausur sind keine Hilfsmittel zugelassen. Es ist der Studenten-Ausweis mitzubringen.
16.1.2004 Musteraufgaben – Lösungen
Die Lösungen zu den Musteraufgaben sind online (Menüpunkt Zusatzmaterial).

Literatur

  • Ingo Wegener, Theoretische Informatik, B.G. Teubner Verlag Stuttgart, 1993
  • Uwe Schöning, Theoretische Informatik - kurzgefasst, Hochschultaschenbuch, Spektrum Akademischer Verlag, 1997
  • R. Garey und D. S. Johnson, Computers and Intractibility: A Guide to the Theory of NP-Completeness, W. H. Freeman, New York, 1979
  • Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Introduction to Algorithms, The MIT press, 1997, 2001.
  • Alexander Asteroth, Christel Baier, Theoretische Informatik: eine Einführung in Berechenbarkeit, Komplexität und formale Sprachen mit 101 Beispielen, Pearson Studium, 2002, ISBN 3-8273-7033-7