English English

Allgemeine Informationen

ECTS: 6
Sprache: Deutsch
Campus: hier
Modul-
anmeldung:
über CampusOffice
Art Termin / Ort Beginn Dozent
V3 Mo 10:15h - 11:45h / Eph
Fr 12:15h - 13:45h / Eph
13.10.2014 Prof. Thomas

Ü2 siehe unten 20.10.2014 siehe unten


Aktuelles

  • Die Noten der zweiten Bachelorklausur sind im CampusOffice eingetragen. Die Einsicht findet am Donnerstag den 23.4. zwischen 10-11 Uhr im Raum 4017 statt.
  • Die Ergebnisse nach der Einsicht wurden im Campus-System veröffentlicht.
  • Die Vorlesung wird von Professor Thomas vom i7 gehalten, der Übungsbetrieb allerdings wird von Mitarbeitern des i1 organisiert.

Inhalt

Welche Probleme kann man mit Hilfe des Computers lösen? Und welche Probleme kann man effizient lösen? - Das sind die Fragestellungen, um die es in dieser Vorlesung geht. Wir versuchen diese Fragen mit mathematischen Methoden zu beantworten. Dazu müssen wir zunächst Begriffe wie Problem, Algorithmus und Effizienz modellieren. Anschließend werden wir verblüffend klare und weitgehende Aussagen über die (effiziente) Lösbarkeit von Problemen auf Rechnern machen können. Grundlage der Vorlesung sind mathematische Modelle und Methoden. Der Bezug zu praktischen Problemen und modernen Rechnern wird aber klar herausgearbeitet. Ein Highlight der Vorlesung ist die NP-Vollständigkeitstheorie, deren Auswirkung auf Theorie und Praxis wohl kaum überschätzt werden kann.


Vorlesungsmaterial

Skript zur Vorlesung (15.12.14: Neue Version!)

Folien
13. Okt. Folien
17. Okt. Folien
20. Okt. Folien [24.11.14: Korrektur in Folie 5]
27. Okt. Folien
3. Nov. Folien [24.11.14: Korrektur in Folie 14]
10. Nov. Folien
17. Nov. Folien
21. Nov. Folien
24. Nov. Folien
28. Nov. Folien
1. Dez. Folien
8. Dez. Folien
12. Dez. Folien
15. Dez. Folien
5. Jan. Folien
12. Jan. Folien
19. Jan. Folien
23. Jan. Folien
26. Jan. Folien
30. Jan.

Prüfungstermine
9. Jan. Präsenzübung
27. Feb. Bachelorklausur
26. Mrz. Wiederholungsklausur


Übungen

  • Der Raum 4017 ist der Seminarraum des Lehrstuhls Informatik 1. Er befindet sich im Erdgeschoss des Erweiterungsbaus 1 (E1).
1 Mo 8:15 - 9:45, 4017 Felix Bier
2 Mo 14:15 - 15:45, 2356|052 (5052) Tobias Räderscheidt
3 Mo 14:15 - 15:45, 4017 Eva Fluck
4 Mo 16:15 - 17:45, 4017 Eva Fluck
5 Di 8:30 - 10:00, 4017 Russ Jukic
6 Di 10:15 - 11:45, 4017 Russ Jukic
7 Di 12:15 - 13:45, 2356|056 (5056) Maximilian Gödicke
8 Mi 10:30 - 12:00, 4017 Hinrikus Wolf
9 Mi 13:30 - 15:00, 4017 Steffen van Bergerem
10 Mi 14:15 - 15:45, 2356|054 (5054) Andreas Tollkötter
11 Mi 15:15 - 16:45, 4017 Steffen van Bergerem
12 Do 10:00 - 11:30, 4017 Matthias Voit
13 Do 13:15 - 14:45, 4017 Johannes Lipp
14 Do 16:00 - 17:30, 4017 Jens Katelaan
15 Fr 14:00 - 15:30, 4017 Niklas Gehlen
16 Fr 16:15 - 17:45, 2356|056 (5056) Richard Wilke

Übungsblätter

Hinweise zu den Übungen

  • Die Übungen können in Gruppen bis zu drei Personen abgegeben werden.
  • Die Abgabe der Übungen ist bis Mittwochs um 14:00 Uhr im Sammelkasten am Lehrstuhl für Informatik 1 möglich.
  • Übungspunkte werden im kleinen Umfang in der Bachelorklausur berücksichtigt:
    Bei 50 + 10k erworbenen Übungspunkten für k ∈ {1,...,6} werden k Punkte angerechnet.


Prüfungszulassung (Bachelor Informatik/Mathematik) und Leistungsnachweis

Für die Zulassung zur Bachelor-Prüfung bzw. für einen Leistungsnachweis sind mindestens 50 Punkte zu sammeln. Hierzu gibt es folgende Möglichkeiten:
  • 90 Punkte in der Präsenzübung.
  • Je 4 Punkte pro Übungsblatt für die speziell ausgezeichnete Aufgabe.
  • Je 2 Punkte für das Vortragen der Lösung einer Aufgabe in den Übungsgruppen.
  • Abgaben zu den übrigen auf jedem Blatt enthaltenen Aufgaben werden ebenfalls korrigiert und, mit hilfreichen Kommentaren versehen, zurückgeben. Wir möchten jeden dazu ermuntern, diese Möglichkeit, gerne auch in Gruppenarbeit zusammen mit Mitstudenten, in Anspruch zu nehmen.

Weitere Literaturhinweise

Die folgenden Bücher eignen sich als zusätzliche Literatur und stehen in der Informatikbibliothek zur Verfügung.

  • J.E. Hopcroft, R. Motwani, J.D. Ullman: Introduction to Automata Theory, Languages, and Computation. Addison-Wesley 2001.
  • J. Hromkovic: Theoretische Informatik. Teubner 2004.
  • U. Schöning: Theoretische Informatik - kurzgefaßt. Spektrum Akademischer Verlag 2001.
  • M. Sipser: Introduction to the Theory of Computation. PWS Publishing 1997.
  • I. Wegener: Theoretische Informatik - eine algorithmenorientierte Einführung. Teubner Verlag 1999.
  • I. Wegener: Kompendium Theoretische Informatik - Eine Ideensammlung. Teubner 1996.

Zusätzlich ist Turings Arbeit von 1936

  • A.M. Turing: Computable numbers, with an application to the Entscheidungsproblem
im Internet verfügbar. Siehe hierzu auch
  • U. Schöning, W. Thomas, Turings Arbeiten zur Berechenbarkeit - eine Einführung und Lesehilfe [PDF]
  • (etwas überarbeitet erschienen im Jahrgang 2012 der Zeitschrift "Informatik-Spektrum")

Kontakt