Description
Diese kompakte Einfhrung in die Theoretische Informatik stellt die wichtigsten Modelle fr zentrale Probleme der Informatik vor. Dabei werden u.a. folgende Fragestellungen behandelt: Welche Probleme sind algorithmisch lsbar? (Theorie der Berechenbarkeit und Entscheidbarkeit) Wie schwierig ist es algorithmische Probleme zu lsen? (Theorie der Berechnungskomplexitt, NP-Theorie) Wie sind informationsverarbeitende Systeme prinzipiell aufgebaut? (Theorie der endlichen Automaten) Welche Strukturen besitzen Programmiersprachen? (Theorie der formalen Sprachen) In der Erarbeitung dieser Themen wird der Abstraktionsproze von den realen Gegenstnden der Informatik zu den in der Theoretischen Infromatik etabliertern Modellen, wie z.B. Random-Access-Maschinen, Turingmaschinen und endliche Automaten, nachvollzogen und umgekehrt verdeutlicht, was diese Modelle aufgrund der ber sie gewonnenen Erkenntnisse fr die Praxis leisten knnen. 1 Mathematische Grundlagen.- 1.1 Mengen, Relationen, Funktionen und Graphen.- 1.2 Wrter und natrliche Zahlen.- 1.3 Algebraische Erzeugung.- 1.4 Das Induktionsprinzip.- 1.5 Aufgaben.- 2 Berechenbarkeit.- 2.1 Random-Access-Maschinen.- 2.1.1 Definition und Beispiele.- 2.1.2 RAM-Berechenbarkeit.- 2.2 Die Programmiersprache RIES.- 2.2.1 Die Syntax und Semantik von RIES.- 2.2.2 RIES-Berechenbarkeit.- 2.2.3 MINI-RIES und der Compiler.- 2.3 Zur Geschichte des Algorithmenbegriffes.- 2.4 Turingmaschinen.- 2.4.1 Definition und Beispiele.- 2.4.2 Turing-Berechenbarkeit.- 2.4.3 quivalenz zu anderen Berechenbarkeitsbegriffen.- 2.5 Partiell-rekursive Funktionen.- 2.5.1 Primitiv-rekursive Funktionen.- 2.5.2 Die Ackermannfunktion.- 2.5.3 Partiell-rekursive Funktionen.- 2.5.4 quivalenz zu anderen Berechenbarkeitsbegriffen.- 2.6 Der Hauptsatz der Algorithmentheorie.- 2.7 Entscheidbarkeit und Aufzhlbarkeit.- 2.7.1 Definitionen und einfache Resultate.- 2.7.2 Das Halteproblem.- 2.8 Aufgaben.- 3 Komplexitt.- 3.1 Die Laufzeit von Algorithmen.- 3.2 Die Klasse P.- 3.2.1 Polynomialzeit ist vom Maschinentyp unabhngig.- 3.2.2 Abschlueigenschaften der Klassen P und FP.- 3.2.3 Spezielle Polynomialzeitfunktionen und -mengen.- 3.3 Die Klasse NP.- 3.3.1 Das Durchmustern eines Lsungsraumes.- 3.3.2 Abschlueigenschaften der Klassen NP.- 3.3.3 NP und exponentielle Laufzeit.- 3.3.4 Nichtdeterministische Polynomialzeitmaschinen.- 3.4 NP-vollstndige Mengen.- 3.4.1 Polynomialzeit-Reduzierbarkeit.- 3.4.2 NP-Vollstndigkeit.- 3.4.3 Eine Liste NP-vollstndiger Probleme.- 3.5 Speicherplatzkomplexitt.- 3.5.1 Der Speicherplatzbedarf von Algorithmen.- 3.5.2 Die Klassen LIN und NLIN.- 3.6 Wie schwierig knnen Probleme sein?.- 3.7 Aufgaben.- 4 Boolesche Funktionen.- 4.1 Einfache Eigenschaften boolescher Funktionen.- 4.1.1 Definition und Besipiele.- 4.1.2 Erzeugung und Vollstndigkeit.- 4.2 Aussagenlogik.- 4.2.1 Syntax und Semantik.- 4.2.2 quivalenz, Allgemeingltigkeit und Erfllbarkeit.- 4.2.3 Wichtige aussagenlogische quivalenzen.- 4.3 Kombinatorische Schaltkreise.- 4.3.1 Definition und Beispiele.- 4.3.2 Welche Funktionen werden durch kombinatorische Schaltkreise berechnet?.- 4.4 Das Postsche Vollstndigkeitskriterium.- 4.4.1 Die Postschen Klassen.- 4.4.2 Das Kriterium.- 4.5 Aufgaben.- 5 Endliche Automaten.- 5.1 Endliche Automaten mit Ausgabe.- 5.1.1 Definition und Beispiele.- 5.1.2 Welche Funktionen werden von endlichen Automaten berechnet?.- 5.2 Logische Schaltkreise.- 5.2.1 Definition und Beispiele.- 5.2.2 Logische Schaltkreise und endliche Automaten.- 5.3 Endliche Automaten ohne Ausgabe.- 5.3.1 Deterministische endliche Automaten.- 5.3.2 Nichtdeterministische endliche Automaten.- 5.3.3 Die quivalenz deterministischer und nichtdeterministischer endlicher Automaten.- 5.3.4 Die Klasse EA der von endlichen Automaten akzeptierten Mengen.- 5.4 Regulre Mengen.- 5.4.1 Definition und Beispiele.- 5.4.2 Regulre Mengen und endliche Automaten.- 5.5 Aufgaben.- 6 Formale Sprachen.- 6.1 Die Chomsky-Hierarchie.- 6.2 Sprachen vom Typ 3.- 6.2.1 Regulre Sprachen und Sprachen vom Typ 3.- 6.2.2 Das Pumping-Lemma fr regulre Sprachen.- 6.3 Kontextfreie Sprachen.- 6.3.1 Die Hinzunahme von e-Regeln.- 6.3.2 Grammatiken in Chomsky-Normalform.- 6.3.3 Das Pumping-Lemma fr kontextfreie Sprachen.- 6.3.4 Abschlueigenschaften der Klasse der kontextfreien Sprachen.- 6.3.5 Die Zeitkomplexitt kontextfreier Sprachen.- 6.3.6 Kellerautomaten.- 6.4 Kontextsensitive Sprachen.- 6.4.1 Nichtverkrzende Grammatiken.- 6.4.2 Kontextsensitive Sprachen und linearer Speicherplatz.- 6.4.3 Abschlueigenschaften der Klasse der kontextsensitiven Sprachen.- 6.5 Sprachen vom Typ 0.- 6.5.1 Sprachen vom Typ 0 und aufzhlbare Mengen.- 6.5.2 Abschlueigenschaften der Klasse der Sprachen vom Typ 0.- 6.6 Zusammenfassung.- 6.7 Aufgaben.- Weiterfhrende Literatur.
