Algorithmen und Datenstrukturen - Eine Einführung mit Java

von: Gunter Saake, Kai-Uwe Sattler

dpunkt, 2014

ISBN: 9783864914393

Sprache: Deutsch

576 Seiten, Download: 23510 KB

Format: EPUB, PDF, auch als Online-Lesen

geeignet für:

Apple iPod touch, iPhone und Android Smartphones

eBook anfordern

▸

Mehr zum Inhalt

Algorithmen und Datenstrukturen - Eine Einführung mit Java

Inhaltsverzeichnis

I Grundlegende Konzepte

1 Vorbemerkungen und Überblick

1.1 Informatik, Algorithmen und Datenstrukturen

1.2 Historischer Überblick: Algorithmen

1.3 Historie von Programmiersprachen und Java

1.4 Grundkonzepte der Programmierung in Java

2 Algorithmische Grundkonzepte

2.1 Intuitiver Algorithmusbegriff

2.1.1 Beispiele für Algorithmen

2.1.2 Bausteine für Algorithmen

2.1.3 Pseudocode-Notation für Algorithmen

2.1.4 Struktogramme

2.1.5 Rekursion

2.2 Sprachen und Grammatiken

2.2.1 Begriffsbildung

2.2.2 Reguläre Ausdrücke

2.2.3 Backus-Naur-Form (BNF)

2.3 Elementare Datentypen

2.3.1 Datentypen als Algebren

2.3.2 Signaturen von Datentypen

2.3.3 Der Datentyp bool

2.3.4 Der Datentyp integer

2.3.5 Felder und Zeichenketten

2.4 Terme

2.4.1 Bildung von Termen

2.4.2 Algorithmus zur Termauswertung

2.5 Datentypen in Java

2.5.1 Primitive Datentypen

2.5.2 Referenzdatentypen

2.5.3 Operatoren

3 Algorithmenparadigmen

3.1 Überblick über Algorithmenparadigmen

3.2 Applikative Algorithmen

3.2.1 Terme mit Unbestimmten

3.2.2 Funktionsdefinitionen

3.2.3 Auswertung von Funktionen

3.2.4 Erweiterung der Funktionsdefinition

3.2.5 Applikative Algorithmen

3.2.6 Beispiele für applikative Algorithmen

3.3 Imperative Algorithmen

3.3.1 Grundlagen imperativer Algorithmen

3.3.2 Komplexe Anweisungen

3.3.3 Beispiele für imperative Algorithmen

3.4 Das logische Paradigma

3.4.1 Logik der Fakten und Regeln

3.4.2 Deduktive Algorithmen

3.5 Weitere Paradigmen

3.5.1 Genetische Algorithmen

3.5.2 Neuronale Netze

3.6 Umsetzung in Java

3.6.1 Ausdrücke und Anweisungen

3.6.2 Methoden

3.6.3 Applikative Algorithmen und Rekursion

4 Literaturhinweise zum Teil I

II Algorithmen

5 Ausgewählte Algorithmen

5.1 Suchen in sortierten Folgen

5.1.1 Sequenzielle Suche

5.1.2 Binäre Suche

5.2 Sortieren

5.2.1 Sortieren: Grundbegriffe

5.2.2 Sortieren durch Einfügen

5.2.3 Sortieren durch Selektion

5.2.4 Sortieren durch Vertauschen: BubbleSort

5.2.5 Sortieren durch Mischen: MergeSort

5.2.6 QuickSort

5.2.7 Sortierverfahren im Vergleich

6 Formale Algorithmenmodelle

6.1 Registermaschinen

6.2 Abstrakte Maschinen

6.3 Markov-Algorithmen

6.4 Church’sche These

6.5 Interpreter für formale Algorithmenmodelle in Java

6.5.1 Java: Markov-Interpreter

6.5.2 Registermaschine in Java

7 Eigenschaften von Algorithmen

7.1 Berechenbarkeit und Entscheidbarkeit

7.1.1 Existenz nichtberechenbarer Funktionen

7.1.2 Konkrete nichtberechenbare Funktionen

7.1.3 Das Halteproblem

7.1.4 Nichtentscheidbare Probleme

7.1.5 Post’sches Korrespondenzproblem

7.2 Korrektheit von Algorithmen

7.2.1 Relative Korrektheit

7.2.2 Korrektheit von imperativen Algorithmen

7.2.3 Korrektheitsbeweise für Anweisungstypen

7.2.4 Korrektheit imperativer Algorithmen an Beispielen

7.2.5 Korrektheit applikativer Algorithmen

7.3 Komplexität

7.3.1 Motivierendes Beispiel

7.3.2 Asymptotische Analyse

7.3.3 Komplexitätsklassen

7.3.4 Analyse von Algorithmen

8 Entwurf von Algorithmen

8.1 Entwurfsprinzipien

8.1.1 Schrittweise Verfeinerung

8.1.2 Einsatz von Algorithmenmustern

8.1.3 Problemreduzierung durch Rekursion

8.2 Algorithmenmuster: Greedy

8.2.1 Greedy-Algorithmen am Beispiel

8.2.2 Greedy: Optimales Kommunikationsnetz

8.2.3 Verfeinerung der Suche nach billigster Kante

8.3 Rekursion: Divide-and-conquer

8.3.1 Das Prinzip »Teile und herrsche «

8.3.2 Beispiel: Spielpläne für Turniere

8.4 Rekursion: Backtracking

8.4.1 Prinzip des Backtracking

8.4.2 Beispiel: Das Acht-Damen-Problem

8.4.3 Beispiel: Tic Tac Toe mit Backtracking

8.5 Dynamische Programmierung

8.5.1 Das Rucksackproblem

8.5.2 Rekursive Lösung des Rucksackproblems

8.5.3 Prinzip der dynamischen Programmierung

9 Verteilte Berechnungen

9.1 Kommunizierende Prozesse

9.2 Modell der Petri-Netze

9.2.1 Definition von Petri-Netzen

9.2.2 Formalisierung von Petri-Netzen

9.2.3 Das Beispiel der fünf Philosophen

9.3 Programmieren nebenläufiger Abläufe

9.3.1 Koordinierte Prozesse

9.3.2 Programmieren mit Semaphoren

9.3.3 Philosophenproblem mit Semaphoren

9.3.4 Verklemmungsfreie Philosophen

9.4 Beispielrealisierung in Java

10 Literaturhinweise zum Teil II

III Datenstrukturen

11 Abstrakte Datentypen

11.1 Signaturen und Algebren

11.2 Algebraische Spezifikation

11.2.1 Spezifikationen und Modelle

11.2.2 Termalgebra und Quotiententermalgebra

11.2.3 Probleme mit initialer Semantik

11.3 Beispiele für abstrakte Datentypen

11.3.1 Der Kellerspeicher (Stack)

11.3.2 Beispiel für Kellernutzung

11.3.3 Die Warteschlange (Queue)

11.4 Entwurf von Datentypen

12 Klassen, Schnittstellen und Objekte in Java

12.1 Grundzüge der Objektorientierung

12.2 Klassen und Objekte in Java

12.3 Vererbung

12.4 Abstrakte Klassen und Schnittstellen

12.5 Ausnahmen

12.6 Umsetzung abstrakter Datentypen

12.6.1 Lambda-Ausdrücke in Java 8

13 Grundlegende Datenstrukturen

13.1 Stack und Queue als Datentypen

13.1.1 Implementierung des Stacks

13.1.2 Implementierung der Queue

13.1.3 Bewertung der Implementierungen

13.2 Verkettete Listen

13.3 Doppelt verkettete Listen

13.4 Das Iterator-Konzept

13.5 Java Collection Framework

13.6 J2SE 5.0 und...

Algorithmen und Datenstrukturen - Eine Einführung mit Java

von: Gunter Saake, Kai-Uwe Sattler

Algorithmen und Datenstrukturen - Eine Einführung mit Java

Inhaltsverzeichnis

Kategorien

eBooks