|
|
Bei Amazon kaufen|
Umschlagtext
Zum Buch:
Eine anschauliche Einführung in die klassischen Themenbereiche der Theoretischen Informatik für Studierende der Informatik im Haupt- und Nebenfach. Die Autoren wählen einen Ansatz, der durch zahlreiche ausgearbeitete Beispiele auch LeserInnen mit nur elementaren Mathematikkenntnissen den Zugang zu Berechenbarkeit, Komplexitätstheorie und formalen Sprachen ermöglicht. Die mathematischen Konzepte werden sowohl formal eingeführt als auch informell erläutert und durch grafische Darstellungen veranschaulicht. Das Buch umfasst den Lehrstoff einführender Vorlesungen in die Theoretische Informatik und bietet zahlreiche Übungsaufgaben zu jedem Kapitel an. Aus dem Inhalt: Berechenbarkeit Abstrakte Rechnermodelle Entscheidungsprobleme Komplexität Komplexitätsklassen Das P-NP-Problem Formale Sprachen Grammatiken Reguläre Sprachen Kontextfreie Sprachen Deterministisch kontextfreie Sprachen Entscheidungsprobleme für formale Sprachen Über die Autoren: Christel Baier ist Professorin an der Rheinischen Friedrich Wilhelms-Universität Bonn und bietet Vorlesungen zur Einführung in die Theoretische Informatik und zur Verifikation an. Alexander Asteroth ist inzwischen in der Industrie tätig. Auf der Website: Rund 100 Übungsaufgaben und Lösungsvorschläge Vorlesungsfolien Alle Abbildungen des Buches EBook Volltextsuche: ideal zum schnellen Nachschlagen Vollständig druckbar Mit einem Klick ins Inhaltsverzeichnis bzw. in den Index sofort am Ziel Wissen zum Mitnehmen - immer und überall dabei Spart Papier und schont die Umwelt Systemvoraussetzungen Pentium 4 ab 2,6 GHz oder G4 ab 1 GHz, 512 MB RAM CD-Laufwerk Windows 98/2000 Vista oder Mac OS X 10. 1 PDF-Reader Rezension
Da die Informatik immer mehr auch in der Oberstufe des Gymnasiums gelehrt wird, werden auch die Themen der theoretischen Informatik für den Informatiklehrer relevant.
In diesem Buch von Asteroth und Baier werden diese Grundlagen der Computertechnik dargestellt. So wird anfangs in die abstrakten Rechnermodelle eingeführt und diese mit Hilfe der beiden Turing- und Registermaschinen dargestellt. Darauf folgen Entscheidungsprobleme, Komplexität und Formale Sprachen. kurz der gesamte klassische Stoff der theoretischen Informatik wird vorgestellt. Was dieses Buch von vielen anderen unterscheidet, ist, dass sich die Autoren viel Mühe gegeben haben, den (abstrakten) Stoff möglichst anschaulich darzustellen. Dazu dienen viele Diagramme und Zeichnungen, aber vor allem auch die Texte, in denen die Grundgedanken der Beweise, ohne Verwendung der formalen Sprache der Mathematik vorgestellt werden. Gerade dies ist eine Fundgrube für den Lehrer, denn die formalen Beweise werden auch für die Schüler der Oberstufe oft zu schwierig sein. Auch die oft eingesetzten Beispiele unterstützen das Verständnis. Schade finde ich es, dass das Buch zur Zeit nur als CD-ROM vorliegt. Den - trotz der schönen Darstellung - schwierigen Stoff am Bildschirm zu erfassen fiel mir schwer. Darum ist zu hoffen, dass diese Buch - oder ein Nachfolger - bald wieder als "normales" Buch erhältlich sein wird. Verlagsinfo
as Standardwerk zur Theoretischen Informatik liegt nun als eBook vor. Eine anschauliche Einführung in die klassischen Themenbereiche der Theoretischen Informatik für Studierende der Informatik im Haupt- und Nebenfach. Die Autoren wählen einen Ansatz, der durch zahlreiche ausgearbeitete Beispiele auch LeserInnen mit nur elementaren Mathematikkenntnissen den Zugang zu Berechenbarkeit, Komplexitätstheorie und formalen Sprachen ermöglicht. Die mathematischen Konzepte werden sowohl formal eingeführt als auch informell erläutert und durch grafische Darstellungen veranschaulicht. Das eBook umfasst den Lehrstoff einführender Vorlesungen in die Theoretische Informatik und bietet zahlreiche Übungsaufgaben zu jedem Kapitel an. Aus dem Inhalt: Berechenbarkeit * Abstrakte Rechnermodelle * Entscheidungsprobleme Komplexität * Komplexitätsklassen * Das P-NP-Problem Formale Sprachen * Grammatiken * Reguläre Sprachen * Kontextfreie Sprachen * Deterministisch kontextfreie Sprachen * Entscheidungsprobleme für formale Sprachen Über die Autoren: Christel Baier ist Professorin an der TU-Dresden und bietet Vorlesungen zur Einführung in die Theoretische Informatik und zur Verifikation an. Alexander Asteroth ist in der Industrie tätig. Companion Website zum Buch unter www.pearson-studium.de Auf der Website: * Rund 100 Übungsaufgaben und * Lösungsvorschläge * Vorlesungsfolien * Alle Abbildungen des Buches Inhaltsverzeichnis
Teil I Berechenbarkeit 13
1 Abstrakte Rechnermodelle 17 1.1 Registermaschinen 18 1.2 Turingmaschinen 36 1.3 Äquivalenz der Berechenbarkeitsbegriffe 63 1.4 Übungen 77 2 Entscheidungsprobleme 85 2.1 Entscheidbarbeit und Semientscheidbarkeit 88 2.2 Das Halteproblem 99 2.3 Nichtdeterminismus 116 2.4 Übungen 126 Teil II Komplexität 131 3 Komplexitätsklassen 137 3.1 Zeitkomplexität 137 3.2 Platzkomplexität 145 3.3 Übungen 149 4 Das P-NP-Problem 151 4.1 NP-Vollständigkeit 151 4.2 Der Satz von Cook 155 4.3 Weitere NP-vollständige Probleme 162 4.4 Die Klasse coNP 178 4.5 PSPACE-Vollständigkeit 182 4.6 Übungen 187 Teil III Formale Sprachen 193 5 Grammatiken 195 5.1 Die Chomsky-Hierarchie 196 5.2 Sprachen vom Typ 0 210 5.3 Kontextsensitive Sprachen 211 5.4 DasWortproblem für Sprachen vom Typ 0 und vom Typ 1 215 5.5 Übungen 218 6 Reguläre Sprachen 221 6.1 Endliche Automaten 221 6.2 Eigenschaften regulärer Sprachen 236 6.3 Reguläre Ausdrücke 252 6.4 Minimierung von endlichen Automaten 260 6.5 Übungen 272 7 Kontextfreie Sprachen 277 7.1 Grundbegriffe 277 7.2 Die Chomsky-Normalform 283 7.3 Der Cocke-Younger-Kasami-Algorithmus 289 7.4 Eigenschaften kontextfreier Sprachen 292 7.5 Die Greibach-Normalform 296 7.6 Kellerautomaten 299 7.7 Übungen 312 8 Deterministisch kontextfreie Sprachen 317 8.1 Deterministische Kellerautomaten 318 8.2 LR(0)-Grammatiken 324 8.3 LR(k)-Grammatiken 367 8.4 Übungen 380 9 Entscheidungsprobleme für formale Sprachen 381 9.1 Das Postsche Korrespondenzproblem 382 9.2 Unentscheidungsergebnisse für formale Sprachen 392 9.3 »Schwierige« Probleme für reguläre Sprachen 400 9.4 Übungen 403 10 Zusammenfassung 405 A Die Güte von Algorithmen 407 B Aussagenlogik 409 C Formale Sprachen 413 Literaturverzeichnis 415 Register 419 |