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.

2019S, VU, 2.0h, 3.0EC, wird geblockt abgehalten

Merkmale

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

Ziele der Lehrveranstaltung

Vermittlung eines grundsätzlichen Verständnisses von Berechenbarkeit, Algorithmus sowie der Grenzen der Automatisierbarkeit.

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.

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.14:00 - 18:0005.03.2019 - 02.04.2019 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.05.03.201914:00 - 18:00 Besprechungsraum des Instituts für Diskrete Mathematik und Geometrie, E104, Freihaus, 5. Stock, grüner Bereich, DA05C22Theorie der Berechenbarkeit; wird geblockt abgehalten
Di.12.03.201914:00 - 18:00 Besprechungsraum des Instituts für Diskrete Mathematik und Geometrie, E104, Freihaus, 5. Stock, grüner Bereich, DA05C22Theorie der Berechenbarkeit; wird geblockt abgehalten
Di.19.03.201914:00 - 18:00 Besprechungsraum des Instituts für Diskrete Mathematik und Geometrie, E104, Freihaus, 5. Stock, grüner Bereich, DA05C22Theorie der Berechenbarkeit; wird geblockt abgehalten
Di.26.03.201914:00 - 18:00 Besprechungsraum des Instituts für Diskrete Mathematik und Geometrie, E104, Freihaus, 5. Stock, grüner Bereich, DA05C22Theorie der Berechenbarkeit; wird geblockt abgehalten
Di.02.04.201914:00 - 18: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

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