Saake / Sattler Algorithmen und Datenstrukturen

Eine Einführung mit Java
überarbeitete und erweiterte Auflage
ISBN: 978-3-96910-067-7
Verlag: dpunkt.verlag
Format: EPUB
Kopierschutz: 6 - ePub Watermark

E-Book, Deutsch, 608 Seiten

Algorithmen und Datenstrukturen von Grund auf verstehen

• Fundierte Einführung mit klarem didaktischen Aufbau
• Mit konkreten Anwendungsbeispielen
• Eine reichhaltige Fundgrube für Lehre und Selbststudium

Kenntnisse von Algorithmen und Datenstrukturen sind ein Grundbaustein des Studiums der Informatik und verwandter Fachrichtungen. Das Buch behandelt diese Thematik in Verbindung mit der Programmiersprache Java und schlägt so eine Brücke zwischen den klassischen Lehrbüchern zur Theorie von Algorithmen und Datenstrukturen und den praktischen Einführungen in eine konkrete Programmiersprache.

Die konkreten Algorithmen und deren Realisierung in Java werdenumfassend dargestellt. Daneben werden die theoretischen Grundlagen vermittelt, die in Programmiersprachen-Kursen oft zu kurz kommen: abstrakte Maschinenmodelle, Berechenbarkeit, Algorithmenparadigmen sowie parallele und verteilte Abläufe. Einen weiteren Schwerpunkt bilden Datenstrukturen wie Listen, Bäume, Graphen und Hashtabellen sowie deren objektorientierte
Implementierung mit modernen Methoden der Softwareentwicklung.

Die 6. Auflage führt einige neue Algorithmen ein und berücksichtigt die Neuerungen der aktuellen Java-Versionen, u.a. zu Themen wie Parallelisierung.

Gunter Saake ist Professor für Datenbanken und Informationssysteme an der Uni Magdeburg und forscht unter anderem auf den Gebieten Datenbankintegration, digitale Bibliotheken, objektorientierte Informationssysteme und Informationsfusion. Er ist Koautor mehrerer Lehrbücher, u.a. zu Datenbankkonzepten und -implementierungstechniken, Datenbanken & Java. Kai-Uwe Sattler ist Professor für Datenbanken und Informationssysteme an der TU Ilmenau. Zu seinen Arbeitsgebieten zählen Datenbankintegration und Anfrageverarbeitung in heterogenen sowie massiv verteilten Datenbanksystemen. Er ist Koautor mehrerer Lehrbücher, u.a. zu Datenbankkonzepten und zu Datenbanken & Java.

Autoren/Hrsg.

Saake, Gunter

Sattler, Kai-Uwe

Fachgebiete

• Mathematik | Informatik EDV | Informatik Programmierung | Softwareentwicklung Algorithmen & Datenstrukturen

Leseproben

Inhaltsverzeichnis

IGrundlegende Konzepte

1Vorbemerkungen und Überblick

1.1Informatik, Algorithmen und Datenstrukturen

1.2Historischer Überblick: Algorithmen

1.3Historie von Programmiersprachen und Java

1.4Grundkonzepte der Programmierung in Java

2Algorithmische Grundkonzepte

2.1Intuitiver Algorithmusbegriff

2.1.1Beispiele für Algorithmen

2.1.2Bausteine für Algorithmen

2.1.3Pseudocode-Notation für Algorithmen

2.1.4Struktogramme

2.1.5Rekursion

2.2Sprachen und Grammatiken

2.2.1Begriffsbildung

2.2.2Reguläre Ausdrücke

2.2.3Backus-Naur-Form (BNF)

2.3Elementare Datentypen

2.3.1Datentypen als Algebren

2.3.2Signaturen von Datentypen

2.3.3Der Datentyp bool

2.3.4Der Datentyp integer

2.3.5Felder und Zeichenketten

2.4Terme

2.4.1Bildung von Termen

2.4.2Algorithmus zur Termauswertung

2.5Datentypen in Java

2.5.1Primitive Datentypen

2.5.2Referenzdatentypen

2.5.3Operatoren

3Algorithmenparadigmen

3.1Überblick über Algorithmenparadigmen

3.2Applikative Algorithmen

3.2.1Terme mit Unbestimmten

3.2.2Funktionsdefinitionen

3.2.3Auswertung von Funktionen

3.2.4Erweiterung der Funktionsdefinition

3.2.5Applikative Algorithmen

3.2.6Beispiele für applikative Algorithmen

3.3Imperative Algorithmen

3.3.1Grundlagen imperativer Algorithmen

3.3.2Komplexe Anweisungen

3.3.3Beispiele für imperative Algorithmen

3.4Das logische Paradigma

3.4.1Logik der Fakten und Regeln

3.4.2Deduktive Algorithmen

3.5Weitere Paradigmen

3.5.1Genetische Algorithmen

3.5.2Neuronale Netze

3.6Umsetzung in Java

3.6.1Ausdrücke und Anweisungen

3.6.2Methoden

3.6.3Applikative Algorithmen und Rekursion

4Literaturhinweise zum Teil I

IIAlgorithmen

5Ausgewählte Algorithmen

5.1Suchen in sortierten Folgen

5.1.1Sequenzielle Suche

5.1.2Binäre Suche

5.2Sortieren

5.2.1Sortieren: Grundbegriffe

5.2.2Sortieren durch Einfügen

5.2.3Sortieren durch Selektion

5.2.4Sortieren durch Vertauschen: BubbleSort

5.2.5Sortieren durch Mischen: MergeSort

5.2.6QuickSort

5.2.7Sortieren durch Verteilen: RadixSort

5.2.8Sortierverfahren im Vergleich

6Formale Algorithmenmodelle

6.1Registermaschinen

6.2Abstrakte Maschinen

6.3Markov-Algorithmen

6.4Church’sche These

6.5Interpreter für formale Algorithmenmodelle in Java

6.5.1Java: Markov-Interpreter

6.5.2Registermaschine in Java

7Eigenschaften von Algorithmen

7.1Berechenbarkeit und Entscheidbarkeit

7.1.1Existenz nichtberechenbarer Funktionen

7.1.2Konkrete nichtberechenbare Funktionen

7.1.3Das Halteproblem

7.1.4Nichtentscheidbare Probleme

7.1.5Post’sches Korrespondenzproblem

7.2Korrektheit von Algorithmen

7.2.1Relative Korrektheit

7.2.2Korrektheit von imperativen Algorithmen

7.2.3Korrektheitsbeweise für Anweisungstypen

7.2.4Korrektheit imperativer Algorithmen an Beispielen

7.2.5Korrektheit applikativer Algorithmen

7.3Komplexität

7.3.1Motivierendes Beispiel

7.3.2Asymptotische Analyse

7.3.3Komplexitätsklassen

7.3.4Analyse von Algorithmen

8Entwurf von Algorithmen

8.1Entwurfsprinzipien

8.1.1Schrittweise Verfeinerung

8.1.2Einsatz von Algorithmenmustern

8.1.3Problemreduzierung durch Rekursion

8.2Algorithmenmuster: Greedy

8.2.1Greedy-Algorithmen am Beispiel

8.2.2Greedy: Optimales Kommunikationsnetz

8.2.3Verfeinerung der Suche nach billigster Kante

8.3Rekursion: Divide-and-conquer

8.3.1Das Prinzip »Teile und herrsche«

8.3.2Beispiel: Spielpläne für Turniere

8.4Rekursion: Backtracking

8.4.1Prinzip des Backtracking

8.4.2Beispiel: Das Acht-Damen-Problem

8.4.3Beispiel: Tic Tac Toe mit Backtracking

8.5Dynamische Programmierung

8.5.1Das Rucksackproblem

8.5.2Rekursive Lösung des Rucksackproblems

8.5.3Prinzip der dynamischen Programmierung

9Parallele und verteilte Berechnungen

9.1Grundlagen

9.2Modell der Petri-Netze

9.2.1Definition von Petri-Netzen

9.2.2Formalisierung von Petri-Netzen

9.2.3Das Beispiel der fünf Philosophen

9.3Programmieren nebenläufiger Abläufe

9.3.1Koordinierte Prozesse

9.3.2Programmieren mit Semaphoren

9.3.3Philosophenproblem mit Semaphoren

9.3.4Verklemmungsfreie Philosophen

9.4Nebenläufige Berechnungen in Java

9.4.1Threads und wechselseitiger Ausschluss

9.4.2Parallelisierung in Java

9.4.3Das Philosophenproblem in Java

10Literaturhinweise zum Teil II

IIIDatenstrukturen

11Abstrakte Datentypen

11.1Signaturen und Algebren

11.2Algebraische Spezifikation

11.2.1Spezifikationen und Modelle

11.2.2Termalgebra und Quotiententermalgebra

11.2.3Probleme mit initialer Semantik

11.3Beispiele für abstrakte...

Über Autor(innen)

Gunter Saake ist Professor für Datenbanken und Informationssysteme an der Uni Magdeburg und forscht unter anderem auf den Gebieten Datenbankintegration, digitale Bibliotheken, objektorientierte Informationssysteme und Informationsfusion. Er ist Koautor mehrerer Lehrbücher, u.a. zu Datenbankkonzepten und -implementierungstechniken, Datenbanken & Java.
Kai-Uwe Sattler ist Professor für Datenbanken und Informationssysteme an der TU Ilmenau. Zu seinen Arbeitsgebieten zählen Datenbankintegration und Anfrageverarbeitung in heterogenen sowie massiv verteilten Datenbanksystemen. Er ist Koautor mehrerer Lehrbücher, u.a. zu Datenbankkonzepten und zu Datenbanken & Java.