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.

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

Merkmale

  • Semesterwochenstunden: 2.0
  • ECTS: 3.0
  • Typ: VU Vorlesung mit Übung
  • Format der Abhaltung: Distance Learning

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
Mo.10:00 - 10:3001.03.2021 https://tuwien.zoom.us/j/95093535054?pwd=Z0hKQ285ZWF1Z2hDL3Q2MFdsb0c5UT09 (LIVE)Theorie der Berechenbarkeit - Vorbesprechung
Mo.10:00 - 11:3008.03.2021 - 19.04.2021 TUWEL/Zoom (LIVE)Computability Theory Lecture
Theorie der Berechenbarkeit - Einzeltermine
TagDatumZeitOrtBeschreibung
Mo.01.03.202110:00 - 10:30 https://tuwien.zoom.us/j/95093535054?pwd=Z0hKQ285ZWF1Z2hDL3Q2MFdsb0c5UT09Theorie der Berechenbarkeit - Vorbesprechung
Mo.08.03.202110:00 - 11:30 TUWEL/ZoomComputability Theory Lecture
Mo.15.03.202110:00 - 11:30 TUWEL/ZoomComputability Theory Lecture
Mo.22.03.202110:00 - 11:30 TUWEL/ZoomComputability Theory Lecture
Mo.12.04.202110:00 - 11:30 TUWEL/ZoomComputability Theory Lecture
Mo.19.04.202110:00 - 11:30 TUWEL/ZoomComputability Theory Lecture
LVA wird geblockt abgehalten

Leistungsnachweis

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

LVA-Anmeldung

Von Bis Abmeldung bis
11.02.2021 12:00 14.03.2021 12:00

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