185.203 Theorie der Berechenbarkeit
Diese Lehrveranstaltung ist in allen zugeordneten Curricula Teil der STEOP.
Diese Lehrveranstaltung ist in mindestens einem zugeordneten Curriculum Teil der STEOP.

2022S, VU, 2.0h, 3.0EC, wird geblockt abgehalten
TUWEL

LVA-Bewertung

Merkmale

  • Semesterwochenstunden: 2.0
  • ECTS: 3.0
  • Typ: VU Vorlesung mit Übung
  • Format der Abhaltung: Präsenz

Lernergebnisse

Nach positiver Absolvierung der Lehrveranstaltung sind Studierende in der Lage fortgeschnittene Beweise aus der Berechenbarkeitstheorie unabhängig durchzuführen und dafür verschiedene vorgetragene Theoreme anzuwenden.

Inhalt der Lehrveranstaltung

Introduction to computability theory: unsolvable problems, models of computations (Turing machines, register machines, recursive functions, lambda calculus), Church-Turing thesis, numbering of computable functions, numbering programs, the diagonal method, the s-m-n theorem, universal programs, Kleene's theorem, recursive and recursively enumerable sets, Rice's theorem. Die LOOP-Hierarchie und Aufzaehlungen subrecursiver Klassen. Didaktisches Vorgehen: Zu der Vorlesung werden 2 Uebungsblaetter verteilt, welche von den Studenten selbstaendig zu loesen sind. Abschliessende muendliche Pruefung.

Methoden

Vortrag 

Prüfungsmodus

Schriftlich und Mündlich

Weitere Informationen

Aufwandsabschaetzung

24 h: 6-8 Vorlesungseinheiten

16 h: Loesen von 2 Uebungsblaettern a 7 Beispielen

4 h: tippen der Loesung in LaTeX

30 h: Vorbereitung auf abschliessende Pruefung

1 h: abschl. Pruefung

---------------------------------------------------

75 Std  = 3 ECTS

 

Vortragende Personen

Institut

LVA Termine

TagZeitDatumOrtBeschreibung
Do.13:00 - 13:3003.03.2022 https://tuwien.zoom.us/j/98040878882?pwd=R01PNEhrSUV0R3RjWHFQNUdOTUd3Zz09 (LIVE)Theorie der Berechenbarkeit - Vorbesprechung
Do.13:00 - 15:3017.03.2022 - 07.04.2022 Besprechungszimmer des Institutes für Diskrete Mathematik, Freihaus, grüner Bereich, 5. Stock, DA05 C22Computability Theory Lecture
Theorie der Berechenbarkeit - Einzeltermine
TagDatumZeitOrtBeschreibung
Do.03.03.202213:00 - 13:30 https://tuwien.zoom.us/j/98040878882?pwd=R01PNEhrSUV0R3RjWHFQNUdOTUd3Zz09Theorie der Berechenbarkeit - Vorbesprechung
Do.17.03.202213:00 - 15:30 Besprechungszimmer des Institutes für Diskrete Mathematik, Freihaus, grüner Bereich, 5. Stock, DA05 C22Computability Theory Lecture
Do.24.03.202213:00 - 15:30 Besprechungszimmer des Institutes für Diskrete Mathematik, Freihaus, grüner Bereich, 5. Stock, DA05 C22Computability Theory Lecture
Do.31.03.202213:00 - 15:30 Besprechungszimmer des Institutes für Diskrete Mathematik, Freihaus, grüner Bereich, 5. Stock, DA05 C22Computability Theory Lecture
Do.07.04.202213:00 - 15:30 Besprechungszimmer des Institutes für Diskrete Mathematik, Freihaus, grüner Bereich, 5. Stock, DA05 C22Computability Theory Lecture
LVA wird geblockt abgehalten

Leistungsnachweis

2 Übungsblätter und eine mündliche Prüfung

LVA-Anmeldung

Nicht erforderlich

Curricula

Literatur

P. Odifreddi, Classical Recursion Theory, Studies in Logic, North Holland 1989

Vorkenntnisse

Grundkenntnisse der mathematischen Logik und der Theoretischen Informatik. Im besonderen sind Grundkenntnisse der Praedikatenlogik erforderlich

Sprache

Englisch