|
|
Bei Amazon kaufen|
Umschlagtext
Das Buch führt umfassend in das Gebiet der theoretischen Informatik ein und behandelt den Stoffumfang, der für das Bachelor-Studium an Universitäten und Hochschulen in den Fächern Informatik und Informationstechnik benötigt wird. Die Darstellung und das didaktische Konzept verfolgen das Ziel, einen durchweg praxisnahen Zugang zu den mitunter sehr theoretisch geprägten Themen zu schaffen. Theoretische Informatik muss nicht trocken sein. Sie kann Spaß machen und genau dies versucht das Buch zu vermitteln. Die verschiedenen Methoden und Verfahren werden anhand konkreter Beispiele eingeführt und durch zahlreiche Querverbindungen wird gezeigt, wie die fundamentalen Ergebnisse der theoretischen Informatik die moderne Informationstechnologie prägen.
Das Buch behandelt die Themengebiete: Logik und Deduktion, Automatentheorie, formale Sprachen, Entscheidbarkeitstheorie, Berechenbarkeitstheorie und Komplexitätstheorie. Die Lehrinhalte aller Kapitel werden durch zahlreiche Übungsaufgaben komplettiert, so dass sich die Lektüre neben der Verwendung als studienbegleitendes Lehrbuch auch bestens zum Selbststudium eignet. In der 3. Auflage wurden Fehler behoben, alle Kapitel aktualisiert und teilweise ergänzt. Prof. Dr. Dirk W. Hoffmann ist Dozent an der Fakultät für Informatik und Wirtschaftsinformatik der Hochschule Karlsruhe – Technik und Wirtschaft. Rezension
Hinter der Computertechnik verbirgt sich eine tiefgründige Wissenschaft, die all die Erfolge erst möglich macht: die theoretische Informatik. Informatik als die Wissenschaft von der systematischen Darstellung, Speicherung, Verarbeitung und Übertragung von Informationen, besonders mithilfe von Digitaler Technik wird in Theoretische Informatik, Praktische Informatik und Technische Informatik unterteilt. Historisch hat sich die Informatik theoretisch einerseits aus der Mathematik entwickelt, andererseits aus den Ingenieurswissenschaften aus dem praktischen Bedarf nach schnellen Berechnungen. Das Teil-Gebiet der Theoretischen Informatik befasst sich mit den abstrakten und mathematikorientierten Aspekten der Wissenschaft: Theorie formaler Sprachen bzw. Automatentheorie und Berechenbarkeits- und Komplexitätstheorie. Dieses Buch führt umfassend in das Gebiet der theoretischen Informatik ein und behandelt den Stoffumfang, der für das Bachelor-Studium an Universitäten und Hochschulen in den Fächern Informatik und Informationstechnik benötigt wird. Das Buch behandelt die Themengebiete: Logik und Deduktion, Automatentheorie, formale Sprachen, Entscheidbarkeitstheorie, Berechenbarkeitstheorie und Komplexitätstheorie. Die Lehrinhalte aller Kapitel werden durch zahlreiche Übungsaufgaben komplettiert. Dass die theoretische Informatik weder schwer noch trocken sein muss, versucht dieses Buch zu beweisen.
Jens Walter, lehrerbibliothek.de Verlagsinfo
Pressestimmen: „(Der Autor macht) keinen Bogen um Formeln und Definitionen, schafft es jedoch, den Stoff in einer präzisen, aber eingängigen Sprache zu vermitteln. Viele Beispiele und Illustrationen unterstützen die Verständlichkeit. Zudem werden immer wieder die praktischen Konsequenzen theoretischer Fragestellungen in den Blick gerückt.“ Jens-Christoph Brendel, Linux-Magazin, 01/2016 „Damit eignet sich das Buch hervorragend zum Selbststudium.“ dotnetpro, 5/2016 Inhaltsverzeichnis
1 Einführung 11
1.1 Was ist theoretische Informatik? 11 1.2 Zurück zu den Anfängen 14 1.2.1 Die Mathematik in der Krise 14 1.2.2 Metamathematik 18 1.2.3 Die ersten Rechenmaschinen 22 1.2.4 Der Computer wird erwachsen 24 1.2.5 Berechenbarkeit versus Komplexität 26 1.3 Theoretische Informatik heute 32 1.4 Übungsaufgaben 34 2 Mathematische Grundlagen 37 2.1 Grundlagen der Mengenlehre 38 2.1.1 Der Mengenbegriff 38 2.1.2 Mengenoperationen 41 2.2 Relationen und Funktionen 44 2.3 Die Welt der Zahlen 52 2.3.1 Natürliche, rationale und reelle Zahlen 52 2.3.2 Von großen Zahlen 55 2.3.3 Die Unendlichkeit begreifen 57 2.4 Rekursion und induktive Beweise 65 2.4.1 Vollständige Induktion 66 2.4.2 Strukturelle Induktion 68 2.5 Übungsaufgaben 70 3 Logik und Deduktion 81 3.1 Aussagenlogik 82 3.1.1 Syntax und Semantik 82 3.1.2 Normalformen 91 3.1.3 Beweistheorie 96 3.1.3.1 Hilbert-Kalkül 98 3.1.3.2 Resolutionskalkül 104 3.1.3.3 Tableaukalkül 109 3.1.4 Anwendung: Hardware-Entwurf 112 3.2 Prädikatenlogik 117 3.2.1 Syntax und Semantik 118 3.2.2 Normalformen 122 3.2.3 Beweistheorie 124 3.2.3.1 Resolutionskalkül 130 3.2.3.2 Tableaukalkül 135 3.2.4 Anwendung: Logische Programmierung 138 3.3 Logikerweiterungen 145 3.3.1 Prädikatenlogik mit Gleichheit 146 3.3.2 Logiken höherer Stufe 147 3.3.3 Typentheorie 149 3.4 Übungsaufgaben 150 4 Formale Sprachen 161 4.1 Sprache und Grammatik 162 4.2 Chomsky-Hierarchie 168 4.3 Reguläre Sprachen 170 4.3.1 Definition und Eigenschaften 170 4.3.2 Pumping-Lemma für reguläre Sprachen 172 4.3.3 Satz von Myhill-Nerode 174 4.3.4 Reguläre Ausdrücke 176 4.4 Kontextfreie Sprachen 179 4.4.1 Definition und Eigenschaften 179 4.4.2 Normalformen 179 4.4.2.1 Chomsky-Normalform 179 4.4.2.2 Backus-Naur-Form 181 4.4.3 Pumping-Lemma für kontextfreie Sprachen 182 4.4.4 Entscheidungsprobleme 186 4.4.5 Abschlusseigenschaften 188 4.5 Kontextsensitive Sprachen 191 4.5.1 Definition und Eigenschaften 191 4.5.2 Entscheidungsprobleme 192 4.5.3 Abschlusseigenschaften 193 4.6 Phrasenstruktursprachen 193 4.7 Übungsaufgaben 195 5 Endliche Automaten 201 5.1 Begriffsbestimmung 202 5.2 Deterministische Automaten 204 5.2.1 Definition und Eigenschaften 204 5.2.2 Automatenminimierung 206 5.3 Nichtdeterministische Automaten 208 5.3.1 Definition und Eigenschaften 208 5.3.2 Satz von Rabin, Scott 210 5.3.3 Epsilon-Übergänge 212 5.4 Automaten und reguläre Sprachen 216 5.4.1 Automaten und reguläre Ausdrücke 217 5.4.2 Abschlusseigenschaften 218 5.4.3 Entscheidungsprobleme 220 5.4.4 Automaten und der Satz von Myhill-Nerode 221 5.5 Kellerautomaten 223 5.5.1 Definition und Eigenschaften 223 5.5.2 Kellerautomaten und kontextfreie Sprachen 226 5.5.3 Deterministische Kellerautomaten 228 5.6 Transduktoren 230 5.6.1 Definition und Eigenschaften 230 5.6.2 Automatenminimierung 231 5.6.3 Automatensynthese 233 5.6.4 Mealy- und Moore-Automaten 234 5.7 Petri-Netze 238 5.8 Zelluläre Automaten 243 5.9 Übungsaufgaben 246 6 Berechenbarkeitstheorie 253 6.1 Berechnungsmodelle 254 6.1.1 Loop-Programme 254 6.1.2 While-Programme 260 6.1.3 Goto-Programme 264 6.1.4 Primitiv-rekursive Funktionen 269 6.1.5 Turing-Maschinen 277 6.1.5.1 Einband-Turing-Maschinen 277 6.1.5.2 Einseitig und linear beschränkte Turing-Maschinen 285 6.1.5.3 Mehrspur-Turing-Maschinen 286 6.1.5.4 Mehrband-Turing-Maschinen 286 6.1.5.5 Maschinenkomposition 288 6.1.5.6 Universelle Turing-Maschinen 289 6.1.5.7 Zelluläre Turing-Maschinen 293 6.1.6 Alternative Berechnungsmodelle 295 6.1.6.1 Registermaschinen 296 6.1.6.2 Lambda-Kalkül 300 6.2 Church’sche These 302 6.3 Entscheidbarkeit 309 6.4 Akzeptierende Turing-Maschinen 319 6.5 Unentscheidbare Probleme 319 6.5.1 Halteproblem 319 6.5.2 Satz von Rice 322 6.5.3 Reduktionsbeweise 325 6.5.4 Das Post’sche Korrespondenzproblem 326 6.5.5 Weitere unentscheidbare Probleme 330 6.6 Übungsaufgaben 333 7 Komplexitätstheorie 341 7.1 Algorithmische Komplexität 342 7.1.1 O-Kalkül 349 7.1.2 Rechnen im O-Kalkül 352 7.2 Komplexitätsklassen 356 7.2.1 P und NP 359 7.2.2 PSPACE und NPSPACE 365 7.2.3 EXP und NEXP 367 7.2.4 Komplementäre Komplexitätsklassen 369 7.3 NP-Vollständigkeit 371 7.3.1 Polynomielle Reduktion 371 7.3.2 P-NP-Problem 372 7.3.3 Satz von Cook 373 7.3.4 Reduktionsbeweise 380 7.4 Übungsaufgaben 386 A Notationsverzeichnis 397 B Abkürzungsverzeichnis 401 C Glossar 403 Literaturverzeichnis 419 Namensverzeichnis 423 Sachwortverzeichnis 425 |