
Informatik
Eine grundlegende Einführung, Teil IV. Theoretische Informatik, Algorithmen und Datenstrukturen, Logikprogrammierung, Objektorientierung
Manfred Broy(Author)
Springer (Publisher)
Published on 26. September 1995
Book
Paperback/Softback
IX, 215 pages
978-3-540-58602-9 (ISBN)
Article exhausted; check for reprint
Description
Dieser abschließende vierte Band der Einführung in die Informatik behandelt die theoretische Informatik und ausgewählte fundamentale Algorithmen, Datenstrukturen, Beschreibungs- und Programmierstile, die jeder Informatiker kennen sollte. Ausgehend von einem kurzen Kapitel über Relationenalgebra und Ordnungstheorie werden die Themen Grammatiken zur Beschreibung formaler Sprachen, Berechenbarkeit sowie Rechen- und Speicherkomplexität von Algorithmen und Problemstellungen besprochen. Techniken der axiomatischen Spezifikation und der Entity-Relationship-Modellierung werden eingeführt und Logik- und objektorientierte Programmierung behandelt. Ein Ausblick auf wichtige ökonomische, rechtliche und ethische Aspekte der Informatik rundet das Werk ab.
More details
Series
Language
German
Place of publication
Heidelberg
Germany
Publishing group
Springer Berlin
Target group
Professional and scholarly
Dimensions
Height: 23.5 cm
Width: 15.5 cm
Weight
365 gr
ISBN-13
978-3-540-58602-9 (9783540586029)
DOI
10.1007/978-3-642-97613-1
Schweitzer Classification
Other editions
New editions

Manfred Broy
Informatik
Eine grundlegende Einführung. Band 2: Systemstrukturen und Theoretische Informatik
Book
10/1998
2nd Edition
Springer
€32.99
Shipment within 10-15 days
Additional editions

Manfred Broy
Informatik
Eine grundlegende Einführung, Teil IV. Theoretische Informatik, Algorithmen und Datenstrukturen, Logikprogrammierung, Objektorientierung
E-Book
03/2013
Springer
€36.99
Available for download
Content
1. Formale Sprachen.- 1.1 Relationen und Graphen.- 1.1.1 Zweistellige Relationen.- 1.1.2 Wege in Graphen und Hüllenbildung.- 1.2 Grammatiken.- 1.2.1 Reduktive und generative Grammatiken.- 1.2.2 Die Sprachhierarchie nach Chomsky.- 1.2.3 Strukturgraphen und Strukturbäume.- 1.2.4 Sackgassen und unendliche Ableitungspfade.- 1.3 Chomsky-3-Sprachen und endliche Automaten.- 1.3.1 Reguläre Ausdrücke.- 1.3.2 Endliche Automaten.- 1.3.3 Äquivalenz der Darstellungsformen.- 1.3.4 Reguläre Ausdrücke, endliche Automaten und Chomsky-3-Sprachen.- 1.3.5 Minimale Automaten.- 1.4 Kontextfreie Sprachen und Kellerautomaten.- 1.4.1 Die BNF-Notation.- 1.4.2 Kellerautomaten.- 1.4.3 Kellerautomaten und kontextfreie Sprachen.- 1.4.4 Greibach-Normalform.- 1.4.5 LR(k)-Sprachen.- 1.4.6 LL(k)-Grammatiken.- 1.4.7 Das Verfahren des rekursiven Abstiegs.- 1.5 Kontextsensitive Grammatiken.- 2. Berechenbarkeit.- 2.1 Hypothetische Maschinen.- 2.1.1 Die Turing-Maschine.- 2.1.2 Registermaschinen.- 2.2 Rekursive Funktionen.- 2.2.1 Primitiv rekursive Funktionen.- 2.2.2 ?-rekursive Funktionen.- 2.2.3 Allgemein rekursive Funktionen.- 2.3 Äquivalenz der Berechenbarkeitsbegriffe.- 2.3.1 Äquivalenz von ?-Berechenbarkeit und Turing-Berechenbarkeit.- 2.3.2 Äquivalenz von RM- und Turing-Berechenbarkeit.- 2.3.3 Die Churchsche These.- 2.4 Entscheidbarkeit.- 2.4.1 Nichtberechenbare Funktion.- 2.4.2 Entscheidbare Prädikate.- 2.4.3 Rekursive und rekursiv aufzählbare Mengen.- 3. Komplexitätstheorie.- 3.1 Komplexitätsmaße.- 3.1.1 Zeitkomplexität.- 3.1.2 Bandkomplexität.- 3.1.3 Zeit- und Bandkomplexität von Problemen.- 3.1.4 Polynomiale und nichtdeterministisch polynomiale Zeitkomplexität.- 3.1.5 Backtracking-Nichtdeterminismus in Programmiersprachen.- 3.2 NP-Vollständigkeit.- 3.2.1 Das Erfüllbarkeitsproblem für Boolesche Ausdrücke.- 3.2.2 Weitere NP-vollständige Probleme.- 3.3 Effiziente Algorithmen für NP-vollständige Probleme.- 3.3.1 Geschicktes Durchsuchen großer Baumstrukturen.- 3.3.2 Alpha/Beta-Suche.- 3.3.3 Dynamisches Programmieren.- 3.3.4 Greedy-Algorithmen.- 4. Effiziente Algorithmen und Datenstrukturen.- 4.1 Ausgewählte Algorithmen.- 4.1.1 Komplexität von Sortieralgorithmen.- 4.1.2 Wege in Graphen.- 4.2 Bäume.- 4.2.1 Geordnete, orientierte und sortierte Bäume.- 4.2.2 Darstellung von Bäumen durch Felder.- 4.2.3 AVL-Bäume.- 4.2.4 B-Bäume.- 4.3 Effiziente Darstellung von Mengen.- 4.3.1 Die Rechenstruktur der Mengen mit Zugriff über Schlüssel.- 4.3.2 Mengendarstellung durch AVL-Bäume.- 4.3.3 Streuspeicherverfahren.- 5. Beschreibungstechniken in der Programmierung.- 5.1 Formalismen für die Spezifikation.- 5.1.1 Abstraktion in der Spezifikation.- 5.1.2 Die Spezifikation von abstrakten Rechenstrukturen.- 5.1.3 Spezifikation von Funktionen.- 5.1.4 Spezifikation von Anweisungen.- 5.2 Datenbanken und Informationssysteme.- 5.2.1 Die Entitäts/Relationsbeziehungsmodellierung.- 5.2.2 Entitäts/Relations-Diagramme.- 5.2.3 Charakterisierung von Relationen.- 5.2.4 Zur Verwendung von Datenbanksystemen.- 5.2.5 Das DB-Managementsystem.- 5.2.6 Datenbankabfragen und Ändern der Datenbestände.- 5.3 Logikprogrammierung.- 5.3.1 Eine Problemlösung mit Losikürosramm.- 5.3.2 Die Auswertung von Logikprogrammen.- 5.3.3 Unifikation.- 5.4. Objektorientierte Programmierung.- 6. Abschließende Bemerkungen zur Informatik.- 6.1 Anwendungen der Informatik.- 6.2 Informatik und Recht.- 6.3 Soziale Kompetenz der Informatiker.- 6.4 Informatik und Ükonomie.- 6.5 Informatik, Wissenschaftstheorie und Philosophie.- 6.6 Zur Verantwortung des Informatikers.- Literaturangaben.- Stichwortverzeichnis.