Theoretische Informatik

it.thin.v, 95 Lektionen in FS2025

Im Stundenplan

Lektionen (alle vorbei)

Di., 18.02.08:00-09:35IT24a_ZH-1ZL O6.16Olaf Stern
Di., 18.02.08:00-11:35IT24a_ZH-2IT24a_ZH-3IT24a_ZH-4ZL O6.16Olaf Stern
Di., 18.02.10:00-11:35IT24a_ZH-1ZL O6.16Olaf Stern
Di., 18.02.14:00-17:35IT24a_WIN-1IT24a_WIN-2IT24a_WIN-3IT24a_WIN-4TS O1.19Dandolo Flumini
Do., 20.02.18:40-21:50DS22aIT24ta_ZH-1IT24ta_ZH-2IT24ta_ZH-3+5ZL O6.12Roland Büchi
Fr., 21.02.08:00-11:35IT24ta_WIN-1IT24ta_WIN-2IT24ta_WIN-3IT24ta_WIN-4TS O3.47Elio Bazzi
Fr., 21.02.08:00-11:35IT24tb_WIN-1IT24tb_WIN-2IT24tb_WIN-3IT24tb_WIN-4TE 414Olaf Stern
Di., 25.02.08:00-09:35IT24a_ZH-1ZL O6.16Olaf Stern
Di., 25.02.08:00-11:35IT24a_ZH-2IT24a_ZH-3IT24a_ZH-4ZL O6.16Olaf Stern
Di., 25.02.10:00-11:35IT24a_ZH-1ZL O6.16Olaf Stern
Di., 25.02.14:00-17:35IT24a_WIN-1IT24a_WIN-2IT24a_WIN-3IT24a_WIN-4TS O1.19Dandolo Flumini
Do., 27.02.18:40-21:50DS22aIT24ta_ZH-1IT24ta_ZH-2IT24ta_ZH-3+5ZL O6.12Roland Büchi

Und 83 weitere. Alle im Stundenplan

Klassen

IT24a_ZH-1IT24a_WIN-1IT24a_WIN-2IT24a_WIN-3IT24a_WIN-4IT24a_ZH-2IT24a_ZH-3IT24a_ZH-4DS22aIT24ta_WIN-1IT24ta_WIN-2IT24ta_WIN-3IT24ta_WIN-4IT24ta_ZH-1IT24ta_ZH-2IT24ta_ZH-3IT24ta_ZH-4IT24tb_WIN-1IT24tb_WIN-2IT24tb_WIN-3IT24tb_WIN-4IT24tb_ZH-1IT24tb_ZH-2IT24tb_ZH-3IT24tb_ZH-4

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