English English
Berechenbarkeit und Komplexität (WS 18/19)

Allgemeine Informationen

ECTS: 6

RWTHonline: Link
L2P: Link
Typ  Zeit / Ort Start Vortragender

V Donnerstag,  12:30 - 14:00 / Aula  11.10  Woeginger
Freitag, 16:30 - 18:00 / Audimax  12.10  Woeginger

Mittwoch,  12:30 - 14:00 / AH IV  31.10  Jan Böker,
Tim Hartmann
Tut 26 Orte und Zeiten  22-26.10  Viele Tutoren


Informationen zur Klausur

Falls Sie zur Klausur im Akademischen Jahr 2018/19 antreten wollen, so
  • müssen Sie Sich beim ZPA zur Klausur anmelden;
  • müssen Sie Sich bei unserem [Uebungssystem] registrieren;
  • müssen Sie zur Zulassung mindestens 50% der Punkte bei den Hausübungen erreichen.
Bonusregel:
Falls Sie (1) mindestens 70% der Punkte bei den Hausübungen erreichen, und falls Sie (2) die Klausur mit einer positiven Note bestehen, so verbessert sich Ihre Endnote um einen 0.3 Schritt.

Informationen zu den Übungen

  • Übungsblätter, Lösungen zu den Übungsblättern und Vortragsfolien werden im L2P bereitgestellt. Um Zugang zu unserem L2P Raum zu erhalten, müssen Sie Sich zuerst via RWTHOnline für die Vorlesung registrieren.
  • Jeden Freitag wird ein neues Übungsblatt veröffentlicht.
  • Die Hausübungen sind in Zweiergruppen zu bearbeiten und müssen jede Woche am Mittwoch bis 12:15 im Abgabekasten am i1 abgegeben werden (Informatik-Zentrum, Erweiterungsbau E1, Erdgeschoss; siehe Abbildung unten).
  • Die Verwaltung der Übungspunkte und die Einteilung in Übungsgruppen werden mit dem vom LuFGI2 entwickelten [System] durchgeführt. Weitere Details dazu finden Sie in [Uebung 0].


Vortragsfolien

Thema           Datum    Folien / Handout    
VL-00   Einführung 11 Oct 2018   [Slides 00] / [Handout 00]
VL-01 Turing Maschinen I 12 Oct 2018 [Slides 01] / [Handout 01]
VL-02 Turing Maschinen II   25 Oct 2018 [Slides 02] / [Handout 02]
VL-03 Registermaschinen 26 Oct 2018 [Slides 03] / [Handout 03]
VL-04 Unentscheidbarkeit I 2 Nov 2018 [Slides 04] / [Handout 04]
VL-05 Unentscheidbarkeit II 15 Nov 2018 [Slides 05] / [Handout 05]
VL-06 Rekursive Aufzählbarkeit 16 Nov 2018 [Slides 06] / [Handout 06]
VL-07 Post Correspondenzproblem   22 Nov 2018 [Slides 07] / [Handout 07]
VL-08 Turing Mächtigkeit 23 Nov 2018 [Slides 08] / [Handout 08]
VL-09 LOOP und WHILE I 29 Nov 2018 [Slides 09] / [Handout 09]
VL-10 LOOP und WHILE II 30 Nov 2018 [Slides 10] / [Handout 10]
VL-11 Primitiv rekursive Funktionen 6 Dec 2018 [Slides 11] / [Handout 11]
VL-12 P versus NP 13 Dec 2018 [Slides 12] / [Handout 12]
VL-13 Polynomielle Reduktionen 14 Dec 2018 [Slides 13] / [Handout 13]
VL-14 Satz von Cook-Levin 20 Dec 2018
VL-15 NPC Graphprobleme 10 Jan 2019
VL-16 NPC Zahlprobleme


Weitere Informationen

  • [Vorlesungsskript] vom WS 2014/15 als pdf-file (139 Seiten)
  • [Arbeitsheft] zur Berechenbarkeit
  • Informationen zur [Klausur]
  • Informationen zur [Einsichtnahme]
  • Paul Rendell's [Webseite] über Conway's Game of Life. Einige YouTube Videos zeigen, wie Turingmaschinen durch das Game of Life simuliert werden können.
  • Massachusetts Institute of Technology: [Online course] for high school students "Gödel, Escher, Bach: A Mental Space Odyssey", built around the 1979 book by Douglas Hofstadter.
  • The 1977 ACM Turing Award [lecture] by John Backus: "Can Programming Be Liberated from the von Neumann Style? A Functional Style and Its Algebra of Programs"
  • On the [origin] of the term "NP-complete" by Donald Knuth

Contact

buk(at)lists.rwth-aachen.de
  • In Ihren E-mails sollten Sie immer Ihren NAMEN und Ihre MATRIKELNUMMER angeben.
  • Masterstudenten der Informatik, die dieses Modul als Auflage erhalten haben, müssen sich per E-mail mit dem Subject "[Auflage]" bei uns registrieren.