Algorithmen und Datenstrukturen

Inhalt

Vorwort

Teil I: Grundlagen

1 Einführung

1.1 Berechenbarkeit von Algorithmen

1.2 Wie eine Turing-Maschine arbeitet

1.2.1 Beispiel 1: Addition zweier Zahlen mit einer Turing-Maschine

1.2.2 Beispiel 2: Suchen und ersetzen

1.2.3 Beispiel 3: Multiplikation zweier Zahlen mit einer erweiterten Turing-Maschine

1.2.4 Von der Turing-Maschine zum Prozessor

1.3 Laufzeitanalyse von Algorithmen

1.3.1 Das P-NP-Problem

1.4 Laufzeitabschätzungen von C-Programmen

1.5 Übungen

2 Basisalgorithmen

2.1 Der Ringtausch

2.2 Einfache Textsuche

2.3 Einfaches Suchen und Ersetzen

2.3.1 Entfernen eines Textes aus einer Zeichenkette

2.3.2 Einfügen von Freiräumen in den Text

2.3.3 Ein vollständiges Programm zum Suchen und Ersetzen

2.4 Einfaches Sortieren von Zahlen

2.4.1 Bubble Sort

2.4.2 Einfaches, sortiertes Einfügen

2.5 Primfaktorzerlegung

2.5.1 Wann ist eine Zahl eine Primzahl

2.5.2 Die Primfaktorzerlegung das Programm Primteiler

2.6 Berechnung des GGT (größter gemeinsamer Teiler)

2.7 Gezielte Suche nach Primzahlen

2.7.1 Das Sieb des Eratosthenes

2.8 Rechnen mit beliebig langen Zahlen

2.8.1 Addition beliebig langer Zahlen

2.8.2 Subtraktion beliebig langer Zahlen

2.8.3 Multiplikation beliebig langer Zahlen (Ägyptische Multiplikation)

2.8.4 Division beliebig langer Zahlen (Ägyptische Division)

2.9 Übungen

3 Rekursive Algorithmen

3.1 Der Prozessorstapel (Stack)

3.2 Was sind Rekursionen und wozu werden sie benötigt

3.3 Beispielprogramme zur Rekursion

3.3.1 Berechnung der Fakultät

3.3.2 Berechnung von Fibonacci-Zahlen

3.3.3 Das Erstellen von Galois-Feldern

3.3.4 Die Türme von Hanoi

3.3.5 Ein Backtracking-Algorithmus

3.3.6 Ein einfacher Taschenrechner

3.4 Wann Rekursion und wann lieber nicht

3.5 Übungen

Teil II: Fortgeschrittene Themen

4 Verkettete Listen

4.1 Die Erstellung verketteter Listen

4.1.1 Einfach verkettete Listen

4.1.2 Doppelt verkettete Listen

4.2 Blockchains und Listen mit beliebigen Objekten

4.2.1 Blockchains

4.2.2 Listen mit beliebigen Objekttypen

4.3 Listen mit Java erstellen

4.3.1 Erstellen von Java-Listen mit LinkedList

4.3.2 Erstellen von Java-Listen mit Vector

4.3.3 Wann LinkedList und wann Vector

4.4 Übungen

5 Bäume

5.1 Allgemeine Bäume

5.1.1 Einfach strukturierte allgemeine Bäume

5.1.2 Allgemeine Bäume mit beliebigen Objekten

5.2 Binärbäume

5.3 Bäume in Java

5.4 Übungen

6 Such- und Sortierverfahren

6.1 Wichtige effiziente Sortierverfahren

6.1.1 Min-Max-Sort

6.1.2 Mergesort

6.1.3 Quicksort

6.1.4 Treesort

6.1.5 Heapsort

6.2 Effiziente Suchalgorithmen

6.2.1 Der KMP-Algorithmus

6.2.2 Threadsearch

6.3 Übungen

Teil III: Weiterführende Themen

7 Signalverarbeitung

7.1 Was ist ein Signal

7.1.1 Korrektes Messen von Signalen

7.2 Generierung digitaler Signale

7.2.1 Das Rechtecksignal

7.2.2 Das Sägezahnsignal

7.2.3 Das Dreiecksignal

7.2.4 Das weiße Rauschen

7.2.5 Das Sinussignal

7.2.6 Zeitveränderliche diskrete Signale

7.3 Filteralgorithmen

7.3.1 Der Pop-Klick-Filter

7.3.2 Der Distortion-Filter

7.3.3 Der EMA-Filter

7.3.4 Diskrete Fourier-Transformation (DFT)

7.4 Übungen

8 Grafische Bildverarbeitung

8.1 Der Medianfilter

8.2 Binärfilter

8.3 Lineares Filtern mit Filtermasken

8.4 Chroma Keying

8.5 Übungen

9 Simulation neuronaler Netze

9.1 Zeichenerkennung mit neuronalen Netzen

9.2 Spracherkennung

10 Kryptographische Algorithmen

10.1 Historische Chiffren

10.1.1 Die Caesar-Chiffre

10.1.2 Die Vigenre-Verschlüsselung

10.1.3 Die Enigma

10.2 Sichere Schlüsselübertragung

10.2.1 Verwenden der Modulo-Operation

10.2.2 Verwenden des RSA-Algorithmus

10.3 Blockchiffren

10.4 Hashing-Verfahren

10.4.1 Erweitertes XOR-Hashing

10.4.2 Der SHA-Algorithmus

10.5 Erzeugen sicherer Pseudo-Zufallszahlen

10.6 Übertragen von Nachrichten durch Quantenkryptographie

11 Graphen

11.1 Darstellung eines Graphen als Adjazenzmatrix

11.2 Darstellung eines Graphen als verallgemeinerte Baumstruktur

11.3 Eulerkreise

11.4 Petri-Netze

11.4.1 Prozess-Synchronisation

11.4.2 Das Erzeuger-Verbraucher-Problem

11.4.3 Das Philosophenproblem von Dijkstra

11.4.4 Simulation von Petri-Netzen mit Inzidenzmatrizen

11.5 Übungen

Anhang: Lösung der Übungsaufgaben

Anhang zu Kapitel 1 Einführung

Anhang zu Kapitel 2 Basisalgorithmen

Anhang zu Kapitel 3 Rekursive Algorithmen

Anhang zu Kapitel 4 Verkettete Listen

Anhang zu Kapitel 5 Bäume

Anhang zu Kapitel 6 Such- und Sortierverfahren

Anhang zu Kapitel 7 Signalverarbeitung

Anhang zu Kapitel 8 Grafische Bildverarbeitung

Anhang zu Kapitel 11 Graphen

Index