Grundlagen der Theoretischen Informatik mit Anwendungen: Eine Einführung für Studierende der Informatik, Wirtschaftsinformatik und Technischen Informatik - Taschenbuch

EAN (ISBN-13): 9783528131470
ISBN (ISBN-10): 3528131470
Taschenbuch
Erscheinungsjahr: 29
Herausgeber: Springer Fachmedien Wiesbaden

Buch in der Datenbank seit 2007-06-04T17:35:54+02:00 (Berlin)
Detailseite zuletzt geändert am 2023-09-27T13:51:33+02:00 (Berlin)
ISBN/EAN: 3528131470

ISBN - alternative Schreibweisen:
3-528-13147-0, 978-3-528-13147-0
Alternative Schreibweisen und verwandte Suchbegriffe:
Autor des Buches: kurt ulrich witt, vossen, kurt gottfried, vieweg
Titel des Buches: theoretischen grundlagen, grundlagen technischen informatik, grundkurs theoretische informatik, einführung die theoretische informatik, technische und theoretische informatik, grundlagen der theoretische informatik mit anwendungen, wirtschaftsinformatik eine einführung, einfuehrung die wirtschaftsinformatik, einführung die technische anwendung, informatik für

---

Daten vom Verlag:

Autor/in: Gottfried Vossen; Kurt-Ulrich Witt
Titel: Grundlagen der Theoretischen Informatik mit Anwendungen - Eine Einführung für Studierende der Informatik, Wirtschaftsinformatik und Technischen Informatik
Verlag: Vieweg+Teubner Verlag; Vieweg & Teubner
353 Seiten
Erscheinungsjahr: 2002-04-29
Wiesbaden; DE
Sprache: Deutsch
49,99 € (DE)
51,39 € (AT)
62,56 CHF (CH)
Not available, publisher indicates OP

BC; Book; Hardcover, Softcover / Informatik, EDV/Informatik; Informatik; Verstehen; reguläre Sprache; Informatik; endlicher Automat; Automatentheorie; Komplexität(Math.); Berechenbarkeit; kontextfreie Sprache; lineare Optimierung; Chomsky-Hierarchie; Kellerautomat; formale Sprache; Automaten; Komplexität; theoretische Informatik; B; Theory of Computation; Computer Science; Computer Science, general; Theoretische Informatik; Informatik; BC; EA; BC

1 Einführung und Übersicht.- 1.1 Ausgangspunkte für das Themengebiet.- 1.2 Anwendungen theoretischer Erkenntnisse.- 1.3 Stoffübersicht und -abgrenzung.- 1.4 Externe Lernhilfen und Web-Seiten.- 1.5 Allgemeine Bibliographische Hinweise.- I Endliche Automaten und reguläre Sprachen.- 2 Endliche Automaten.- 2.1 Deterministische endliche Automaten.- 2.1.1 Beispiel: Der Schwimmbadautomat Aswim.- 2.1.2 Alphabete, Wörter, Sprachen.- 2.1.3 Zustände und Zustandsübergänge.- 2.1.4 Deterministische endliche Automaten und reguläre Sprachen.- 2.1.5 Vollständige Automaten.- 2.1.6 Zusammenfassung.- 2.2 Nichtdeterministische endliche Automaten.- 2.2.1 Definitionen.- 2.2.2 Äquivalenz von deterministischen und nichtdeterministischen endlichen Automaten.- 2.2.3 Zusammenfassung.- 2.3 Endliche Automaten mit ?-Übergängen.- 2.3.1 Definitionen.- 2.3.2 Äquivalenz von ?-Automaten zu nichtdeterministischen endlichen Automaten.- 2.3.3 Zusammenfassung.- 2.4 Verallgemeinerte endliche Automaten.- 2.4.1 Definitionen.- 2.4.2 Äquivalenz von verallgemeinerten und endlichen Automaten.- 2.5 Minimierung endlicher Automaten.- 2.5.1 Isomorphie endlicher Automaten.- 2.5.2 Ein Verfahren zur Minimierung endlicher Automaten.- 2.6 Anwendungen endlicher Automaten.- 2.6.1 Rechnersysteme und Systemprogrammierung.- 2.6.2 Teilworterkennung.- 2.6.3 Suchmaschinen im Internet.- 2.6.4 Objektorientierte Modellierung. Interaktionsdiagramme.- 2.7 Bibliographische Hinweise und Ergänzungen.- 2.8 Übungen.- 3 Reguläre Sprachen.- 3.1 Reguläre Ausdrücke.- 3.1.1 Definitionen und Eigenschaften.- 3.1.2 Anwendung regulärer Ausdrücke.- 3.1.3 Äquivalenz von endlichen Automaten und regulären Ausdrücken.- 3.1.4 Scanner-Generatoren.- 3.1.5 Zusammenfassung.- 3.2 Typ-3-Grammatiken.- 3.2.1 Rechtslineare Grammatiken.- 3.2.2 Linkslineare Grammatiken.- 3.2.3 Äquivalenz rechtslinearer und linkslinearer Grammatiken.- 3.2.4 Verallgemeinerte Typ-3-Grammatiken.- 3.2.5 Äquivalenz von endlichen Automaten und Typ-3-Grammatiken.- 3.2.6 Zusammenfassung.- 3.3 Eigenschaften regulärer Sprachen.- 3.3.1 Abschlusseigenschaften von REG?.- 3.3.2 Das Pumping-Lemma für reguläre Sprachen.- 3.3.3 Entscheidbarkeitsprobleme.- 3.3.4 Grenzen endlicher Automaten.- 3.4 Bibliographische Hinweise und Ergänzungen.- 3.5 Übungen.- 4 Endliche Maschinen und Automatennetze.- 4.1 Endliche Maschinen.- 4.1.1 Erweiterung des endlichen Automaten Aswim.- 4.1.2 Mealy-Maschinen.- 4.1.3 Ein formales Vorgehensmodell bei der Problemlösung.- 4.1.4 Gegenseitige Simulation von Mealy-Maschinen und endlichen Automaten.- 4.1.5 Moore-Maschinen.- 4.1.6 Äquivalenz von Mealy- und Moore-Maschinen.- 4.1.7 Grenzen endlicher Maschinen.- 4.2 Endliche Transducer.- 4.3 Beispiele für Automatennetze.- 4.3.1 Synchrone Automaten: Zellulare Automaten.- 4.3.2 Asynchrone Automaten: Petri-Netze.- 4.3.3 Anwendungen und Varianten von Petri-Netzen.- 4.4 Anwendungen endlicher Maschinen.- 4.4.1 Software- und Systementwurf. Statecharts.- 4.4.2 Workflow-Management.- 4.4.3 Elektronischer Handel.- 4.5 Bibliographische Hinweise und Ergänzungen.- 4.6 Übungen.- II Kontextfreie Sprachen und Kellerautomaten.- 5 Kontextfreie Sprachen.- 5.1 Kontextfreie Grammatiken.- 5.1.1 Beispiele und Definitionen.- 5.1.2 Normalformen.- 5.2 Eigenschaften kontextfreier Sprachen.- 5.2.1 Mehrdeutigkeit.- 5.2.2 Das Pumping-Lemma für kontextfreie Sprachen.- 5.2.3 Abschlusseigenschaften.- 5.3 Übungen.- 6 Kellerautomaten.- 6.1 Nichtdeterministische Kellerautomaten.- 6.1.1 Grundlegende Definitionen.- 6.1.2 Akzeptieren mit leerem Keller.- 6.2 Äquivalenz von kontextfreien Grammatiken und Kellerautomaten.- 6.3 Deterministische Kellerautomaten.- 6.4 Übungen.- 7 Anwendungen kontextfreier Sprachen.- 7.1 Ableitungs-und Syntaxbäume.- 7.2 Compilerbau.- 7.3 Syntax von Programmiersprachen.- 7.3.1 Erweiterte Backus-Naur-Form.- 7.3.2 Syntaxdiagramme.- 7.4 Reguläre Definitionen.- 7.4.1 SADT.- 7.4.2 XML.- 7.5 Bibliographische Hinweise.- 7.6 Übungen.- III Berechenbarkeit und Komplexität.- 8 Typ-1- und Typ-O-Sprachen.- 8.1 Die Chomsky-Hierarchie.- 8.1.1 Typ-1-Sprachen (kontextsensitive Sprachen).- 8.1.2 Typ-O-Sprachen (rekursiv-aufzählbare Sprachen).- 8.1.3 Die Hierarchie.- 8.1.4 Das Wortproblem.- 8.2 Turingautomaten.- 8.2.1 Definitionen und Beispiele.- 8.2.2 Varianten von Turingautomaten.- 8.2.3 Äquivalenz von deterministischen und nichtdeterministischen Turingautomaten.- 8.2.4 Linear beschränkte Automaten.- 8.2.5 Äquivalenz zwischen linear beschränkten Automaten und Typ1-Grammatiken.- 8.2.6 Äquivalenz zwischen Turingautomaten und Typ-O-Grammatiken.- 8.3 Zusammenfassung.- 8.4 Bibliographische Hinweise.- 8.5 Übungen.- 9 Berechenbarkeit.- 9.1 Turing-Berechenbarkeit.- 9.1.1 Definition und Beispiele.- 9.1.2 Die Programmiersprache Turing.- 9.2 Loop-, While- und Goto-Berechenbarkeit.- 9.2.1 Loop-Berechenbarkeit.- 9.2.2 While-Berechenbarkeit.- 9.2.3 Goto-Berechenbarkeit.- 9.2.4 Die Churchsche These.- 9.2.5 Die Ackermannfunktion.- 9.3 Universelle Turingmaschinen.- 9.3.1 Codierung von Turingmaschinen.- 9.3.2 Das utm-Theorem.- 9.3.3 Das smn-Theorem.- 9.4 Bibliographische Hinweise.- 9.5 Übungen.- 10 Entscheidbarkeit.- 10.1 Existenz unentscheidbarer Probleme.- 10.2 Entscheidbare und semi-entscheidbare Mengen.- 10.3 Reduzierbarkeit von Mengen.- 10.4 Unentscheidbare Mengen.- 10.4.1 Das Halteproblem.- 10.4.2 Das Korrektheitsproblem.- 10.4.3 Das Äquivalenzproblem.- 10.4.4 Der Satz von Rice.- 10.4.5 Das Postsche Korrespondenzproblem.- 10.4.6 Anwendungen des Postschen Korrespondenzproblems.- 10.5 Übungen.- 11 Komplexität.- 11.1 Die O-Notation.- 11.2 Komplexität von Algorithmen.- 11.3 Wichtige Komplexitätsklassen.- 11.4 Die Klassen P und NP.- 11.4.1 Die Klasse P.- 11.4.2 Die Klasse NP.- 11.4.3 Das P-NP-Problem.- 11.4.4 NP-Vollständigkeit.- 11.5 Konkrete NP-vollständige Probleme.- 11.5.1 Das Erfüllbarkeitsproblem der Aussagenlogik.- 11.5.2 Weitere NP-vollständige Probleme.- 11.6 Heuristiken zur Behandlung NP-vollständiger Probleme.- 11.6.1 Eine Heuristik für TSP.- 11.6.2 Untere Schranken für das Approximieren.- 11.7 Zusammenfassung.- 11.8 Bibliographische Hinweise und Ergänzungen.- 11.9 Übungen.
Lehrbuch Theoretische Informatik: modern und anwendungsbezogen; Theoretischen Informatik. Es stellt grundlegende Konzepte, Methoden und Techniken der Informatik dar, mit denen praktische Problemstellungen beschrieben und gelöst werden können und auf deren Basis kommerziell verfügbare Informations- und Kommunikationssyteme entwickelt worden sind. So ist z. B. das Konzept des ''endlichen Automaten'' nicht nur Bestandteil von fast allen Software-Engineering-Werkzeugen, sondern es wird unter anderem auch verwendet bei der Realisierung von Workflowmanagementsystemen, der Gestaltung von Mensch-Maschine-Schnittstellen, der Implementierung von Netzwerkprotokollen, der Datenkompression, beim Schaltkreisentwurf, bei der Realisierung von Funktionen in Textverarbeitungssystemen und zur Internetsuche. Der Einsatz formaler Konzepte wird anhand von vielen Beispielen motiviert und ausprobiert.