Theoretische Informatik

it.thin.v, 168 Lektionen in FS2023

Im Stundenplan

Lektionen (alle vorbei)

Mo., 20.02.17:45-21:05IT22ta_ZH-1IT22ta_ZH-2IT22ta_ZH-3ZL O3.01Dandolo Flumini
Mo., 20.02.17:45-18:30IT22ta_ZH-4ZL O3.01Dandolo Flumini
Mo., 20.02.17:45-21:05IT22tb_ZH-1IT22tb_ZH-2ZL O3.06Roland Büchi
Mo., 20.02.18:40-20:10IT22ta_ZH-4ZL O3.01Dandolo Flumini
Mo., 20.02.20:20-21:05IT22ta_ZH-4ZL O3.01Dandolo Flumini
Di., 21.02.08:00-11:35IT22a_ZH-1IT22a_ZH-2IT22a_ZH-3ZL O3.06Olaf Stern
Di., 21.02.08:00-09:35IT22a_ZH-4ZL O3.06Olaf Stern
Di., 21.02.10:00-11:35IT22a_ZH-4ZL O3.06Olaf Stern
Di., 21.02.14:00-17:35IT22a_WIN-1IT22a_WIN-2IT22a_WIN-3IT22a_WIN-4TS O2.12Dandolo Flumini
Di., 21.02.14:00-17:35IT22b_WIN-1IT22b_WIN-2TS O2.44Elio Bazzi
Fr., 24.02.08:00-11:35IT22ta_WIN-1IT22ta_WIN-2IT22ta_WIN-3IT22ta_WIN-4TS O3.12Elio Bazzi
Fr., 24.02.08:00-11:35IT22tb_WIN-1IT22tb_WIN-2IT22tb_WIN-3IT22tb_WIN-4TS O2.12Olaf Stern

Und 156 weitere. Alle im Stundenplan

Klassen

IT22ta_ZH-4IT22a_ZH-4IT22a_WIN-1IT22a_WIN-2IT22a_WIN-3IT22a_WIN-4IT22a_ZH-1IT22a_ZH-2IT22a_ZH-3IT22b_WIN-1IT22b_WIN-2IT22ta_WIN-1IT22ta_WIN-2IT22ta_WIN-3IT22ta_WIN-4IT22ta_ZH-1IT22ta_ZH-2IT22ta_ZH-3IT22tb_WIN-1IT22tb_WIN-2IT22tb_WIN-3IT22tb_WIN-4IT22tb_ZH-1IT22tb_ZH-2

Modulbeschreibung 19HS

Grundbegriffe sowie Konzepte der theoretischen Informatik, Modelle zur Beurteilung der Leistungsfähigkeit aktueller und zukünftiger Computersysteme: Formale Sprachen, Automatentheorie, Berechenbarkeit und Komplexität

ECTS
4
Institut
51415: T CAI
Verantwortung
Olaf Stern, strf
Sprache
(X) Deutsch ( ) Englisch

Modulinhalte

Motivation der theoretischen Informatik: Formale Berechnungsmodelle Grundlegende Prinzipien erkennen, unabhängig von Hard- und Software Grenzen der automatischen Berechnungen (1) Formale Sprachen / Automatentheorie: Grundlegende Definitionen der Formalen Sprachen Reguläre Sprachen, endlicher Automat (DEA, NEA, e-NEA) Kontextfreie Sprachen, Kellerautomaten (Rekursive Sprachen), Turingmaschine (TM) Chomsky-Hierarchie (2) Berechenbarkeit und Algorithmus-Begriff: Berechenbare Funktionen Church'sche These Äquivalenz von TM und Computer Berechenbarkeit und Programmier-Sprachen: GOTO-, While- und Loop-Programme. Algorithmus-Begriff Primitive Rekursion Nicht-Entscheidbarkeit und Entscheidbarkeit: Diagonalisierungssprache Ld, Satz von Rice, Fleissige Bieber Semi-entscheidbare Probleme: Halteproblem, Game-of-Life, (Collatz-Zahlen ?) Reduktion (3) Komplexitätstheorie Komplexität von Algorithmen O-Notation (Omega-Notation) polynomiale Funktionen und exponentielle Funktionen Klasse P, Klasse NP NP-vollständig, NP-schwierig Polynomialzeit-Reduktion

Voraussetzungen

keine

Versionen

  • 19HSt.BA.IT.THIN.19HS
  • 13HSt.BA.IT.THIN.13HS