Details

<p><b>Über den Autor 7</b></p> <p><b>Einleitung</b><b> 17</b></p> <p>Was ist theoretische Informatik? 17</p> <p>Über dieses Buch 18</p> <p>Wie dieses Buch aufgebaut ist 18</p> <p>Symbole in diesem Buch 20</p> <p>Wie Sie dieses Buch lesen sollten 20</p> <p><b>Teil I Endliche Automaten</b> <b>21</b></p> <p><b>Kapitel 1 Deterministische Endliche Automaten (DFAs)</b> <b>23</b></p> <p>Einführung 23</p> <p>Erste Beispiele 24</p> <p>Grundlegende Definitionen 27</p> <p>Symbole und Wörter 27</p> <p>Die Definition eines DFAs 28</p> <p>Reguläre Sprachen 30</p> <p>Die erweiterte Übergangsfunktion 30</p> <p>Beispiele regulärer Sprachen 31</p> <p>Das Pumping Lemma 34</p> <p>Minimalautomaten 38</p> <p>Der Satz von Myhill und Nerode 45</p> <p>DFAs mit Ausgabe (Moore- und Mealy-Automaten) 50</p> <p>Aufgaben zu DFAs 54</p> <p><b>Kapitel 2 Nichtdeterministische Endliche Automaten (NFAs)</b> <b>57</b></p> <p>Nichtdeterminismus 57</p> <p>Definition eines NFA 58</p> <p>Der Satz von Rabin-Scott 60</p> <p>NFAs mit <i>𝜖</i>-Übergängen 64</p> <p>Abschlusseigenschaften regulärer Sprachen 67</p> <p>Reguläre Ausdrücke 70</p> <p>Stochastische Automaten und Markov-Ketten 75</p> <p>Hidden Markov Models 80</p> <p>Aufgaben zu NFAs 80</p> <p><b>Kapitel 3 Kellerautomaten (PDAs)</b> <b>83</b></p> <p>Nichtdeterministische Kellerautomaten 83</p> <p>Deterministische Kellerautomaten 89</p> <p>Die Grenzen von PDAs 91</p> <p>Aufgaben zu PDAs 92</p> <p><b>Kapitel 4 Turing-Maschinen</b> <b>93</b></p> <p>Deterministische Turing-Maschinen 93</p> <p>Turing-Berechenbarkeit 102</p> <p>Mehrband-Turing-Maschinen 105</p> <p>Registermaschinen 109</p> <p>Nichtdeterministische Turing-Maschinen 110</p> <p>Linear beschränkte Turing-Maschinen 112</p> <p>Universelle Turing-Maschine (UTM) 113</p> <p>Die Grenzen von Turing-Maschinen 115</p> <p>Aufgaben zu Turing-Maschinen 120</p> <p><b>Teil II Formale Sprachen</b> <b>123</b></p> <p><b>Kapitel 5 Grammatiken</b> <b>125</b></p> <p>Einführung 125</p> <p>Ein erstes Beispiel 126</p> <p>Syntaxbäume 127</p> <p>Definition einer Grammatik 128</p> <p>Die von einer Grammatik erzeugte Sprache 128</p> <p>Wie man <i>𝜖</i>-Regeln loswird 129</p> <p>Das Wortproblem 131</p> <p>Chomsky-Hierarchie 131</p> <p>Aufgaben zu Grammatiken 133</p> <p><b>Kapitel 6 Reguläre (Typ-3-)Sprachen</b> <b>135</b></p> <p>Beispiele für Typ-3-Sprachen 135</p> <p>Das Wortproblem für Typ-3-Sprachen 136</p> <p>Aufgaben zu Typ-3-Sprachen 139</p> <p><b>Kapitel 7 Kontextfreie (Typ-2-)Sprachen</b> <b>141</b></p> <p>Erste Beispiele 141</p> <p>Backus-Naur-Form (BNF) 142</p> <p>Erweiterte Backus-Naur-Form (EBNF) 142</p> <p>Chomsky-Normalform 144</p> <p>Die Grenzen kontextfreier Sprachen 146</p> <p>Ein äquivalentes Maschinenmodell 150</p> <p>Deterministisch kontextfreie Sprachen 153</p> <p>Das Wortproblem für kontextfreie Sprachen 154</p> <p>Abschlusseigenschaften 156</p> <p>Aufgaben zu kontextfreien Sprachen 157</p> <p><b>Kapitel 8 Kontextsensitive und Phasen-Struktur-Sprachen</b> <b>159</b></p> <p>Ein erstes Beispiel 159</p> <p>Das Wortproblem für Typ-1-Sprachen 160</p> <p>Das Wortproblem für Typ-0-Sprachen 161</p> <p>Äquivalente Maschinenmodelle 162</p> <p>Typ-0-Sprachen 162</p> <p>Typ-1-Sprachen 164</p> <p><b>Teil III Harte Probleme</b> <b>167</b></p> <p><b>Kapitel 9 Zeitkomplexität von Algorithmen</b> <b>169</b></p> <p>Einführende Überlegungen 169</p> <p>Zeit- und Speicherkomplexität von Algorithmen 171</p> <p>Die <i>O</i>-Notation 175</p> <p>Komplexitätsklassen von Sprachen 177</p> <p>Aufgaben zur Komplexität von Algorithmen 179</p> <p><b>Kapitel 10 Die Klassen P und NP</b> <b>181</b></p> <p>Die Klasse P 181</p> <p>Die Klasse NP 182</p> <p>Zertifikate 182</p> <p>Das SAT-Problem 185</p> <p>Reduktion 188</p> <p>SAT, KNF-SAT und 3-SAT 190</p> <p>Reduktion und Entscheidbarkeit 196</p> <p>Aufgaben zu P und NP 197</p> <p><b>Kapitel 11 NP-Vollständigkeit</b> <b>199</b></p> <p>Der Satz von Cook 199</p> <p>Boolesche Schaltkreise und deterministische Turing-Maschinen 200</p> <p>Boolesche Schaltkreise und nichtdeterministische Turing-Maschinen 206</p> <p>Reduktion von CIRCUIT-SAT auf 3-SAT 208</p> <p>Beispiele <b>NP</b>-vollständiger Sprachen 210</p> <p>SUBSET-SUM-Problem 210</p> <p>Hamilton-Kreise 213</p> <p>Das Travelling-Salesman-Problem 219</p> <p>Das Cliquen-Problem 221</p> <p>Ist <b>P </b>= <b>NP</b>? 223</p> <p>Quantencomputer 223</p> <p>Die Klasse <b>BQP</b> 225</p> <p>Aufgaben zur <b>NP</b>-Vollständigkeit 227</p> <p><b>Teil IV Mathematische Grundlagen</b> <b>229</b></p> <p><b>Kapitel 12 Logische Grundlagen</b> <b>231</b></p> <p>Boolesche Variablen und boolesche Formeln 231</p> <p>Aussagen und Beweise 233</p> <p>Beweistechniken 234</p> <p>Aufgaben zur Logik 238</p> <p><b>Kapitel 13 Mengen und Relationen</b> <b>239</b></p> <p>Grundbegriffe 239</p> <p>Mengenoperationen 241</p> <p>Relationen 242</p> <p>Äquivalenzrelationen 242</p> <p>Ordnungsrelationen 244</p> <p>Funktionen 245</p> <p>Aufgaben zu Mengen und Relationen 247</p> <p><b>Kapitel 14 Graphen und Bäume</b> <b>249</b></p> <p>Graphen und ihre Eigenschaften 249</p> <p>Zusammenhängende Graphen 251</p> <p>Darstellung von Graphen im Computer 253</p> <p>Bäume 256</p> <p>Tourenprobleme 258</p> <p>Gewichtete Graphen 260</p> <p>Näherungsweise Lösung des TSP 261</p> <p>Aufgaben zu Graphen und Bäumen 265</p> <p><b>Teil V Top-Ten-Teil 267</b></p> <p><b>Kapitel 15 Top-Ten-Theoretiker</b> <b>269</b></p> <p>Charles Babbage (1791–1871) 269</p> <p>Ada Lovelace (1815–1852) 270</p> <p>Alonzo Church (1903–1995) 270</p> <p>Alan Turing (1912–1954) 271</p> <p>Claude Shannon (1916–2001) 272</p> <p>Richard Feynman (1918–1988) 273</p> <p>Noam Chomsky (geboren 1928) 274</p> <p>Michael Rabin (geboren 1931) und Dana Scott (geboren 1932) 274</p> <p>Stephen Cook (geboren 1939) 275</p> <p>Peter W. Shor (geboren 1959) 275</p> <p><b>Kapitel 16 Die Top-Ten-Bücher zum Weiterlesen 277</b></p> <p>Teil I: Endliche Automaten 277</p> <p>Teil II: Formale Sprachen 277</p> <p>Teil III: Harte Probleme 278</p> <p>Teil IV: Mathematische Grundlagen 278</p> <p>Teil V: Top-Ten-Teil 278</p> <p>Symbolverzeichnis 281</p> <p>Stichwortverzeichnis 283 </p>

"...das Buch wendet sich an Studienanfänger ..., [Der Autor] versucht, theoretische Informatik 'formelfrei' zu besprechen und viele Formeln noch einmal umgangssprachlich zu erklären. ... Didaktisch gut aufgebaut. Jeder der drei Teile wird mit einem kurzen Absatz eingeleitet; ein nichtkonsekutives Durcharbeiten des Buches ist somit leicht möglich. ..."<br> (EKZ 28. Oktober 2019)<br>

Roland Schmitz ist promovierter Mathematiker und seit 2001 Professor für Internet-Security im Studiengang Medieninformatik an der Hochschule der Medien in Stuttgart. Vorher war er sechs Jahre lang wissenschaftlicher Mitarbeiter am Technologiezentrum der Deutschen Telekom mit den Hauptarbeitsgebieten Sicherheit mobiler Kommunikation sowie Standardisierung digitaler Signaturen.

DE