- Titel: Theoretische Informatik
- Organisation: UNI MAGDEBURG
- Seitenzahl: 97
Inhalt
- Bernd Reichel und Ralf Stiebe
- Magdeburg im April
- Relationen und Funktionen
- R R R R R R R R
- Abbildung Graphische Darstellung einer Relation
- MATHEMATISCHE GRUNDLAGEN M
- Abbildung Graphische Darstellung einer Verkpfung von Relationen u
- Uber die Mchtigkeit von Mengen a
- Uber die Mchtigkeit von Mengen a
- Alphabete Wrter Sprachen o
- Abbildung Veranschaulichung einer Turingmaschine
- steht z z z
- start M ze M stop
- Abbildung Eine sich verzweigende Turingmaschine
- LOOP WHILE und GOTOBerechenbarkeit
- Die Churchsche These
- Church Amerikanischer Mathematiker
- Halteproblem und Unentscheidbarkeit
- Abbildung Veranschaulichung von entscheidbaren Mengen
- Abbildung Veranschaulichung von semientscheidbaren Mengen
- binibinjbini binj binm
- c mit einem c gilt
- Tabelle Rechenzeiten eines Computers
- Nichtdeterministische Turingmaschinen und die Klasse NP
- wzy fr z E w y u
- Abbildung Komplexittsklassen a
- pn E z a a pn an
- KOMPLE ITATSTHEORIE E c T
- Abbildung Rahmen des Dominospiels
- Set Partition das Partitionierungsproblem
- Adjektiv Attribut Adjektiv bissige
- Abbildung Die ChomskyHierarchie mit weiteren Sprachklassen
- n n n Tm Tm Tm
- T T T T T
- Regulre Sprachen a
- fr z ai z u
- Abbildung Interpretation der Arbeitsweise eines endlichen Automaten
- ii z wa z w a
- Abbildung Konstruktion des Uberfhrungsgraphen eines DEA u
- Abbildung Uberfhrungsgraph des DEA aus Beispiel u
- Abbildung Nichtdeterminismus beim endlichen Automaten
- Abbildung Uberfhrungsgraph des NEA aus Beispiel u
- Abbildung Uberfhrungsgraph des DEA A aus Beispiel u
- Regulre Ausdr cke a u
- Abbildung Schema des NEAs fr L u
- Abbildung Schema des NEAs fr L u
- Abbildung Schema des NEAs fr L u
- fr z E und u
- ai Lzai fr z E u
- Abbildung Ein deterministischer endlicher Automat
- Menge aller Sprachen
- Greibach amerikanische Mathematikerin
- Abbildung Der Algorithmus von Cocke Younger und Kasami
- C a D b E c
- i a b b b c c x
- Abbildung Tabelle zum Algorithmus von CYK
- i i n k r
- i i n r
- z fr ein z Z u
- Rekursiv aufzhlbare und kontextabhngige Sprachen a a
- Tabelle Charakterisierungen der Sprachfamilien der Chomsky Hierarchie
- Tabelle Beziehungen zwischen deterministischen und nichtdeterministischen Automaten
- Tabelle Komplexitt des Wortproblems a
Vorschau
Theoretische Informatik
Vorlesungsscriptum Sommersemester 2003
Dr. Bernd Reichel1 und Dr. Ralf Stiebe2 Fakult¨t f¨r Informatik a u Otto-von-Guericke-Universit¨t Magdeburg a
1 Tel.: 2 Tel.:
+49’391’67’12851, e-mail: reichel@iws.cs.uni-magdeburg.de, URL: theo.cs.uni-magdeburg.de +49’391’67’12457, e-mail: stiebe@iws.cs.uni-magdeburg.de, URL: theo.cs.uni-magdeburg.de
2
INHALTSVER EICHNIS
Inhaltsverzeichnis
Vorwort Literatur 1 Mathematische Grundlagen 1.1 Elementare Aussagenlogik . . . . . 1.2 Elementare Mengenlehre . . . . . . 1.3 Relationen und Funktionen . . . . ¨ 1.4 Uber die M¨chtigkeit von Mengen a 1.5 Algebraische Strukturen . . . . . . 1.6 Alphabete, W¨rter, Sprachen . . . o 3 4 5 5 9 13 17 18 19 21 21 22 28 37 38 44 44 45 46 49 54 54 55 59 61 63 64 64 68 74 81 83 83 85 85 87 88 89 91 95 96
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
2 Berechenbarkeit 2.1 Intuitiver Berechenbarkeitsbegriff . . . . . . . . 2.2 Turing-Berechenbarkeit . . . . . . . . . . . . . 2.3 LOOP-, WHILE- und GOTO-Berechenbarkeit . 2.4 Die Churchsche These . . . . . . . . . . . . . . 2.5 Halteproblem und Unentscheidbarkeit . . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
3 Komplexit¨tstheorie a 3.1 Komplexit¨tsklassen . . . . . . . . . . . . . . . . . . . a 3.2 Das Domino-Problem . . . . . . . . . . . . . . . . . . 3.3 Nichtdeterministische Turingmaschinen und die Klasse 3.4 NP-Vollst¨ndigkeit . . . . . . . . . . . . . . . . . . . . a
. . . . NP . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
4 Formale Sprachen 4.1 Einf¨hrung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . u 4.2 Grammatiken . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.2.1 Chomsky-Hierarchie . . . . . . . . . . . . . . . . . . . . . . . . 4.2.2 Wortproblem . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.2.3 Syntaxb¨ume . . . . . . . . . . . . . . . . . . . . . . . . . . . . a 4.3 Regul¨re Sprachen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . a 4.3.1 Endliche Automaten . . . . . . . . . . . . . . . . . . . . . . . . 4.3.2 Nichtdeterministische endliche Automaten . . . . . . . . . . . . 4.3.3 Regul¨re Ausdr¨cke . . . . . . . . . . . . . . . . . . . . . . . . a u 4.3.4 Das Pumping Lemma . . . . . . . . . . . . . . . . . . . . . . . 4.3.5 Abschlusseigenschaften . . . . . . . . . . . . . . . . . . . . . . . 4.3.6 Wortproblem und andere Entscheidbarkeitsprobleme . . . . . . 4.4 Kontextfreie Sprachen . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.4.1 Normalformen . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.4.2 Das Pumping Lemma . . . . . . . . . . . . . . . . . . . . . . . 4.4.3 Abschlusseigenschaften . . . . . . . . . . . . . . . . . . . . . . . 4.4.4 Entscheidbarkeit und der Algorithmus von Cocke, Younger und 4.4.5 Kellerautomaten . . . . . . . . . . . . . . . . . . . . . . . . . . 4.5 Rekursiv aufz¨hlbare und kontextabh¨ngige Sprachen . . . . . . . . . a a ¨ 4.6 Tabellarischer Uberblick . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Kasami . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . .
INHALTSVER EICHNIS
Vorwort
Das vorliegende Scriptum soll dem Leser eine Hilfe zum Studium und beim Besuch der gleichnamigen Vorlesung geben. Es orientiert sich an [13], aus dem auch wesentliche Teile ubernommen ¨ wurden. F¨r weitergehende oder vertiefende Studien ist [8] sehr geeignet und zu empfehlen. Auch die u Lehrb¨cher [7, 5, 9, 14, 16, 17, 18, 2] sind zu empfehlen. u Das Scriptum ist (wie jedes solches Werk) unfertig und wird st¨ndig weiterbearbeitet. Deshalb a nehmen die Autoren Anregungen und Meinungen nicht nur gern entgegen, sondern w¨nschen sich u von allen Lesern solche ausdr¨cklich. u