Theoretische Informatik

it.thin.v, 64 Lektionen in FS2026

Im Stundenplan

Lektionen (alle vorbei)

Di., 17.02.08:00-11:35IT25a_ZH-1IT25a_ZH-2IT25a_ZH-3IT25a_ZH-4ZL O5.09Olaf Stern
Di., 17.02.14:00-17:35IT25a_WIN-1IT25a_WIN-2IT25a_WIN-3IT25a_WIN-4TS O2.17Dandolo Flumini
Do., 19.02.18:40-21:50IT25ta_ZH-1IT25ta_ZH-2IT25ta_ZH-3IT25ta_ZH-4+3ZL O6.10Roland BüchiDandolo Flumini
Fr., 20.02.08:00-11:35IT25ta_WIN-1IT25ta_WIN-2IT25ta_WIN-3IT25ta_WIN-4TE 407Elio Bazzi
Fr., 20.02.08:00-11:35IT25tb_WIN-1IT25tb_WIN-2IT25tb_WIN-3IT25tb_WIN-4TH 363Olaf Stern
Di., 24.02.08:00-11:35IT25a_ZH-1IT25a_ZH-2IT25a_ZH-3IT25a_ZH-4ZL O5.09Olaf Stern
Di., 24.02.14:00-17:35IT25a_WIN-1IT25a_WIN-2IT25a_WIN-3IT25a_WIN-4TS O2.17Dandolo Flumini
Do., 26.02.18:40-21:50IT25ta_ZH-1IT25ta_ZH-2IT25ta_ZH-3IT25ta_ZH-4+3ZL O6.10Roland BüchiDandolo Flumini
Fr., 27.02.08:00-11:35IT25ta_WIN-1IT25ta_WIN-2IT25ta_WIN-3IT25ta_WIN-4TE 407Elio Bazzi
Fr., 27.02.08:00-11:35IT25tb_WIN-1IT25tb_WIN-2IT25tb_WIN-3IT25tb_WIN-4TH 363Olaf Stern
Di., 03.03.08:00-11:35IT25a_ZH-1IT25a_ZH-2IT25a_ZH-3IT25a_ZH-4ZL O5.09Olaf Stern
Di., 03.03.14:00-17:35IT25a_WIN-1IT25a_WIN-2IT25a_WIN-3IT25a_WIN-4TS O2.17Dandolo Flumini

Und 52 weitere. Alle im Stundenplan

Klassen

IT25a_WIN-1IT25a_WIN-2IT25a_WIN-3IT25a_WIN-4IT25a_ZH-1IT25a_ZH-2IT25a_ZH-3IT25a_ZH-4IT25ta_WIN-1IT25ta_WIN-2IT25ta_WIN-3IT25ta_WIN-4IT25ta_ZH-1IT25ta_ZH-2IT25ta_ZH-3IT25ta_ZH-4IT25tb_WIN-1IT25tb_WIN-2IT25tb_WIN-3IT25tb_WIN-4IT25tb_ZH-1IT25tb_ZH-2MI25a-1

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