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.

2020S, VU, 2.0h, 3.0EC, wird geblockt abgehalten
Diese Lehrveranstaltung wird nach dem neuen Modus evaluiert. Mehr erfahren

LVA-Bewertung

Merkmale

  • Semesterwochenstunden: 2.0
  • ECTS: 3.0
  • Typ: VU Vorlesung mit Übung

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: 5 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

Institut

LVA Termine

TagZeitDatumOrtBeschreibung
Di.09:15 - 12:0003.03.2020 - 28.04.2020 Besprechungsraum des Instituts für Diskrete Mathematik und Geometrie, E104, Freihaus, 5. Stock, grüner Bereich, DA05C22Theorie der Berechenbarkeit; wird geblockt abgehalten
Theorie der Berechenbarkeit - Einzeltermine
TagDatumZeitOrtBeschreibung
Di.03.03.202009:15 - 12:00 Besprechungsraum des Instituts für Diskrete Mathematik und Geometrie, E104, Freihaus, 5. Stock, grüner Bereich, DA05C22Theorie der Berechenbarkeit; wird geblockt abgehalten
Di.10.03.202009:15 - 12:00 Besprechungsraum des Instituts für Diskrete Mathematik und Geometrie, E104, Freihaus, 5. Stock, grüner Bereich, DA05C22Theorie der Berechenbarkeit; wird geblockt abgehalten
Di.17.03.202009:15 - 12:00 Besprechungsraum des Instituts für Diskrete Mathematik und Geometrie, E104, Freihaus, 5. Stock, grüner Bereich, DA05C22Theorie der Berechenbarkeit; wird geblockt abgehalten
Di.24.03.202009:15 - 12:00 Besprechungsraum des Instituts für Diskrete Mathematik und Geometrie, E104, Freihaus, 5. Stock, grüner Bereich, DA05C22Theorie der Berechenbarkeit; wird geblockt abgehalten
Di.31.03.202009:15 - 12:00 Besprechungsraum des Instituts für Diskrete Mathematik und Geometrie, E104, Freihaus, 5. Stock, grüner Bereich, DA05C22Theorie der Berechenbarkeit; wird geblockt abgehalten
Di.21.04.202009:15 - 12:00 Besprechungsraum des Instituts für Diskrete Mathematik und Geometrie, E104, Freihaus, 5. Stock, grüner Bereich, DA05C22Theorie der Berechenbarkeit; wird geblockt abgehalten
Di.28.04.202009:15 - 12:00 Besprechungsraum des Instituts für Diskrete Mathematik und Geometrie, E104, Freihaus, 5. Stock, grüner Bereich, DA05C22Theorie der Berechenbarkeit; wird geblockt abgehalten
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