Theoretische Grundlagen der Informatik
Quelle: Modulkatalog Moses
Die Studierenden können eigenständig die grundlegenden Begriffe und Formalismen der Diskreten Mathematik anwenden. Sie beherrschen den Umgang mit formalen Sprachen und Grammatiken sowie mit den zentralen theoretischen Maschinenmodellen und verfügen über ein Verständnis der grundlegenden Komplexitätsklassen; sie sind in der Lage, die Komplexität ausgewählter Beispielprobleme einzuschätzen.
Universität: Technische Universität Berlin
Kategorie: Informatik
Wissensbasis / Lernziele
In der theoretischen Informatik und Mathematik betrachtet man zunächst Mengen, Logik, Abbildungen, Relationen und Ordnungen; anschließend gehen Grammatiken und die Chomsky-Hierarchie in den Blick, danach beschäftigen wir uns mit endlichen Automaten, Kellerautomaten und Turingmaschinen sowie der Frage der Berechenbarkeit; schließlich geht es um den Aufwand von Algorithmen und die Komplexität von Problemen, die Komplexität der Wortprobleme innerhalb der Chomsky-Hierarchie und die Konzepte P, NP sowie NP-Vollständigkeit.
Verfügbare Lernmittel
Theoretische Grundlagen der Informatik
Veröffentlicht: 19.09.2025 17:44
Theoretische Grundlagen der Informatik
Veröffentlicht: 19.09.2025 17:49
Theoretische Grundlagen der Informatik
Veröffentlicht: 19.09.2025 17:52
Mengen, Relationen, Abbildungen und Ordnungen
Veröffentlicht: 19.09.2025 17:53
Logik: Aussagenlogik und Prädikatenlogik
Veröffentlicht: 19.09.2025 17:54
Formale Sprachen, Alphabet, Wörter und Sprachen
Veröffentlicht: 19.09.2025 17:55
Grammatiken: Typen, Generierung und Ableitungsregeln
Veröffentlicht: 19.09.2025 17:56
Die Chomsky-Hierarchie: Typ-0 bis Typ-3
Veröffentlicht: 19.09.2025 17:57
Endliche Automaten: DFA/NFA und reguläre Sprachen
Veröffentlicht: 19.09.2025 17:58
Kellerautomaten (Pushdown-Automaten) und kontextfreie Sprachen
Veröffentlicht: 19.09.2025 17:58
Turingmaschinen, Berechenbarkeit und Entscheidbarkeit
Veröffentlicht: 19.09.2025 17:59
Halteproblem, Unentscheidbarkeit und Beweistechniken
Veröffentlicht: 19.09.2025 18:01
Komplexität von Algorithmen: Zeit- und Platzkomplexität
Veröffentlicht: 19.09.2025 18:02
P, NP, NP-Vollständigkeit und Reduktionen
Veröffentlicht: 19.09.2025 18:05
Theoretische Grundlagen der Informatik
Fragen: 15, Dauer: 20 Min
Theoretische Grundlagen der Informatik
Fragen: 15, Dauer: 20 Min
Mengen, Relationen, Abbildungen und Ordnungen
Fragen: 10, Dauer: 15 Min
Logik: Aussagenlogik und Prädikatenlogik
Fragen: 10, Dauer: 15 Min
Formale Sprachen, Alphabet, Wörter und Sprachen
Fragen: 10, Dauer: 15 Min
Grammatiken: Typen, Generierung und Ableitungsregeln
Fragen: 10, Dauer: 15 Min
Die Chomsky-Hierarchie: Typ-0 bis Typ-3
Fragen: 10, Dauer: 15 Min
Endliche Automaten: DFA/NFA und reguläre Sprachen
Fragen: 10, Dauer: 15 Min
Kellerautomaten (Pushdown-Automaten) und kontextfreie Sprachen
Fragen: 10, Dauer: 15 Min
Turingmaschinen, Berechenbarkeit und Entscheidbarkeit
Fragen: 10, Dauer: 15 Min
Halteproblem, Unentscheidbarkeit und Beweistechniken
Fragen: 10, Dauer: 15 Min
Komplexität von Algorithmen: Zeit- und Platzkomplexität
Fragen: 10, Dauer: 15 Min
P, NP, NP-Vollständigkeit und Reduktionen
Fragen: 10, Dauer: 15 Min