Informatik III

Aktuelles

• Die Nachklausur findet am 10. September um 9:00 Uhr in Gebäude 101 (026 und 036) statt. Erneut ist als Hilfsmittel ein DIN A4-Zettel (beidseitig beschrieben) mit beliebigem Inhalt zugelassen. Bitte vergessen Sie nicht, Ihre UniCard (oder Vergleichbares) mitzubringen.
• Die Klausurnoten wurden an das Prüfungsamt gemeldet. Am Montag, den 17.3.2014, von 14 Uhr bis 16 Uhr kann die Klausur in Raum 00-016 in Gebäude 52 eingesehen werden. Bitte bringen Sie dazu Ihre UniCard mit.
  
• Bitte beachten Sie, dass die Klausur bereits um 14:00 Uhr (s.t.) beginnt. Bitte vergessen Sie nicht, Ihre UniCard (oder Vergleichbares) mitzubringen.
  
• Die Zulassungsvoraussetzung wurde von 50 % (97 Punkte) auf 48 % (93 Punkte) gesenkt.
  
• Korrigierte Übungsblätter (z.B. Übungsblatt 14) können im Büro von Alexander Nutz und Matthias Heizmann abgeholt werden.
  
• Für die Prüfung ist als Hilfsmittel ein DIN A4-Zettel (beidseitig beschrieben) mit beliebigem Inhalt zugelassen.
• Die Probeklausur und ein Lösungsvorschlag zu Übungsblatt 14 sind online.
  
• Am Dienstag, den 25.2.2014, wird von 14 Uhr (s.t.) bis 16 Uhr eine Fragestunde im Hinblick auf die Klausur angeboten. Diese findet im Hörsaal 00-036 in Gebäude 101 statt. Damit wir uns auf Ihre Fragen vorbereiten können, bitten wir Sie, diese im Vorfeld per E-Mail an die Assistenten zu senden.
  
• Am Dienstag, den 11.2.2014, wird in der Vorlesung die "Probeklausur" besprochen.
  
• Das Tutorat am Freitag, den 14.2.2014, findet nicht mehr statt.
  
• Am Donnerstag, den 6.2.2014, wird in der Vorlesung eine "Probeklausur" angeboten. Dazu werden Ihnen einige Aufgaben in Stil einer Klausur gestellt, die Sie bearbeiten sollen. Die Bearbeitung wird nicht korrigiert oder bewertet. Die Teilnahme ist freiwillig. Wir planen, die "Probeklausur" am Dienstag, den 11.2.2014, in der Vorlesung zu besprechen.
• Ein Lösungsvorschlag zu Übungsblatt 8 ist online. In den Tutoraten im neuen Jahr wird bereits Übungsblatt 9 besprochen.
  
• Die Übungsaufgaben und Lösungsskizzen der Präsenzaufgaben aus der Vorlesung vom 21.11.2013 sind online.
  
• Am Donnerstag, den 21.11.2013, wird in der Vorlesung eine Wiederholung des bisherigen Stoffs angeboten. Dazu werden Ihnen im ersten Teil einige Aufgaben gestellt, die Sie bearbeiten sollen. Die Bearbeitung wird nicht korrigiert oder bewertet. Anschließend werden wir die Aufgaben besprechen und auf etwaige Fragen eingehen. Sollten Sie bereits vorher Fragen zu Vorlesung oder Übungsbetrieb haben, schicken Sie bitte eine E-Mail mit diesen an die Assistenten.
  
• Der Link zum Vorlesungsmitschrieb ist unten angegeben.
  
• Die Einteilung der Übungsgruppen ist online.
  
• Der Übungsbetrieb beginnt bereits in der ersten Vorlesungswoche -- allerdings erst ab Freitag, d.h. am Montag den 21.10.2013 finden noch keine Übungen statt.
  

Übungen

Jeden Donnerstag wird ein Übungsblatt hier ins Netz gestellt.

Die Übungsgruppe soll auch dazu dienen, Fragen aus der Vorlesung zu klären und den Vorlesungsstoff mit dem Tutor und den anderen Teilnehmern zu diskutieren. Eine regelmäßige Teilnahme an den Übungen ist verpflichtend und wichtig für das Verständnis der Vorlesung.

Wir empfehlen ausdrücklich beim Bearbeiten der Übungsaufgaben Lösungsansätze mit Kommilitonen zu besprechen und Lerngruppen zu bilden. Die Lösung muss aber von jedem Studenten selbstständig aufgeschrieben werden.

Leistungsnachweis

Die Prüfung besteht aus einer zweistündigen Klausur, die am Ende des Semesters stattfindet.

Regelmäßige Teilnahme an den Übungen ist Zulassungsvorraussetzung zur Klausur.  Die regelmäßige Teilnahme kann daran festgehalten werden, dass mindestens 50 % 48 % der Punkte aus den Übungen erreicht werden und mindestens einmal im Tutorium vorgerechnet wird.

Lernziel

Studierende sollen lernen, intuitive Konzepte wie Algorithmen, Berechenbarkeit, Komplexität formal und präzise zu fassen und ihre grundsätzliche Bedeutung für die Lösbarkeit von Problemen mit Hilfe von Rechnern erkennen zu können. Sie sollen Methoden zur Klassifikation von Problemen in verschiedene Komplexitätsklassen verstehen. Sie sollen Techniken, wie z.B. Reduktionstechniken, zur Einschätzung der Komplexität von Problemen beherrschen und anwenden können. Ferner sollen sie formale Sprachen und (endliche) Automaten als präzise Werkzeuge zur formalen Beschreibung von Sprachen und Prozessen einsetzen können.

Skript

Das Skript ist passwortgeschützt hier zugreifbar.

Zusätzlich wurde hier freundlicherweise ein Mitschrieb von Teilnehmern der Vorlesung erstellt und soll als Ergänzung zu obigem Skript dienen. Wir übernehmen keine Garantie auf Korrektheit oder Vollständigkeit.

Literatur

1. I. Wegener: Theoretische Informatik - eine algorithmenorientierte Einführung, 2. Auflage 1999, Teubner, Stuttgart. ISBN 3-5191-2123-9
2. U. Schöning: Theoretische Informatik kurzgefasst, Spektrum Taschenbuch, 5. Auflage, 2008, Spektrum Akademischer Verlag, Heidelberg. ISBN 3-8274-1824-0
3. H. Lewis, C. Papadimitriou: Elements of the Theory of Computation, 2. Auflage, 1997, 361 Seiten, kart., Prentice Hall, New Jersey. ISBN 0-13-262478-8
4. J. Hopcroft, J. Ullman: Einführung in die Automatentheorie, Formale Sprachen und Komplexitätstheorie, 3. Auflage 1994, 461 Seiten, kart., Addison Wesley, Bonn. ISBN 3-89319-744-3