Nievergelt / Hinrichs Programmierung und Datenstrukturen

Eine Einführung anhand von Beispielen
1986
ISBN: 978-3-642-71605-8
Verlag: Springer
Format: PDF
Kopierschutz: 1 - PDF Watermark

E-Book, Deutsch, 149 Seiten, eBook

Reihe: Studienreihe Informatik

Zielgruppe

Research

Autoren/Hrsg.

Nievergelt, Jürg

Hinrichs, Klaus

Inhaltsverzeichnis

1 Sprachunabhängige Aspekte der Programmierung.- 1.1 Programmierumgebungen.- 1.1.1 Einfache künstliche Umgebungen.- 1.1.2 Die Umgebung „Turtle Graphics“.- 1.1.3 Die Prozedur als Baustein von Programmen.- 1.1.4 Ein primitives Rahmenprogramm.- 1.2 Divide et impera und Rekursion.- 1.2.1 Ein algorithmisches Prinzip.- 1.2.2 Sortieren.- 1.2.3 Die Türme von Hanoi.- 1.2.4 Rekursiv definierte Bäume.- 1.2.5 Rekursive Baumtraversierung.- 1.2.6 Hilberth raumfüllende Kurve.- 1.3 Syntax.- 1.3.1 Syntax und Semantik.- 1.3.2 Grammatiken und ihre Darstellung durch Syntaxdiagramme.- 1.3.3 Beispiel: Syntax sehr einfacher Ausdrücke.- 1.3.4 Allzu einfache Syntax für einfache Ausdrücke.- 1.3.5 Klammerfreie Notation für arithmetische Ausdrücke.- 1.4 Syntaxanalyse.- 1.4.1 Die Rolle der Syntaxanalyse.- 1.4.2 Syntaxanalyse klammerfreier Ausdrücke durch Zählen.- 1.4.3 Analyse durch rekursiven Abstieg.- 1.4.4 Umsetzung in ein Programm (parser).- 1.5 Dialogführende Rahmenprogramme.- 1.5.1 Trennung von Dialogführung und Inhalt.- 1.5.2 Ein einfaches Rahmenprogramm.- 1.5.3 Beispiel: Parser, eingebettet in ein Rahmenprogramm.- 1.5.4 Die zwei Netztypen.- 1.5.5 Eine Sammlung nützlicher Dialogprozeduren.- 1.6 Entwicklung eines interaktiven Programmes: Stackrechner.- 1.6.1 Wie ein Stackrechner funktioniert.- 1.6.2 Simulation eines Stackrechners: das Rahmenprogramm.- 2 Eine Sammlung von Algorithmen und deren Darstellung als Prozeduren.- 2.1 Rechnen mit Booleschen Werten und Mengen.- 2.1.1 Berechnung der transitiven Hülle.- 2.1.2 Die Bitsumme oder „Bevölkerungszählung“.- 2.2 Rechnen mit Zeichenketten.- 2.2.1 Erkennung eines Musters bestehend aus einer einzigen Kette.- 2.2.2 Erkennung einer Menge von Zeichenketten.- 2.3 Rechnen mit ganzen Zahlen.- 2.3.1 Der Euklidsche Algorithmus.- 2.3.2 Das Primzahlensieb von Eratosthenes.- 2.3.3 Billige grosse Zahlen - modulare Zahlensysteme.- 2.4 Rechnen mit reellen Zahlen.- 2.4.1 Gleitkommazahlen.- 2.4.2 Einige Gefahren.- 2.4.3 Das Horner Schema.- 2.4.4 Bisektion.- 2.4.5 Newton’s Methode zur Berechnung der Quadratwurzel.- 2.5 Zufallszahlen.- 2.6 Rechnen mit geometrischen Objekten.- 2.7 Berechenbarkeit und Komplexität.- 2.7.1 „Fast nichts ist berechenbar“.- 2.7.2 Das Halteproblem ist unentscheidbar.- 2.7.3 Komplexität der Matrizenmultiplikation.- 3 Datenstrukturen.- 3.1 Sortieren.- 3.1.1 Wie schwierig ist Sortieren?.- 3.1.2 Einige Typen von Sortieralgorithmen.- 3.1.3 Einfache Sortieralgorithmen mit Zeitaufwand O(n2).- 3.1.4 Eine untere Schranke ? (n*log n).- 3.1.5 Quicksort.- 3.1.6 Analyse von Quicksort in drei Fällen: „günstig“, „typisch“, „schlimm“.- 3.1.7 Sortieren durch Mischen.- 3.1.8 Kann man in linearer Zeit sortieren?.- 3.1.9 Praktische Aspekte des Sortierens.- 3.2 Abstrakte Datentypen.- 3.2.1 Begriffe: was und warum?.- 3.2.2 Stack.- 3.2.3 Fifo queue.- 3.2.4 Priority queue.- 3.2.5 Dictionary.- 3.3 Implizite Datenstrukturen.- 3.3.1 Was ist eine implizite Datenstruktur?.- 3.3.2 Arrayspeicherung.- 3.3.3 Implementation der fifo queue durch einen zirkulären Puffer.- 3.3.4 Implementation der priority queue durch einen heap.- 3.3.5 Heapsort.- 3.4 Listenstrukturen.- 3.4.1 Zeigervariablen und Listen.- 3.4.2 Implementation der fifo queue durch eine lineare Liste.- 3.4.3 Baumtraversierung.- 3.4.4 Binäre Suchbäume.- 3.4.5 Balancierte Bäume.- 3.4.6 AVL-Bäume.- 3.4.7 Mehrwegbäume.- 3.5 Adressberechnung.- 3.5.1 Begriffe.- 3.5.2 Spezialfall: kleiner Schlüsselwertebereich.- 3.5.3 Spezialfall: a priori bekannter Tabelleninhalt, perfekte Hashfunktion.- 3.5.4 Der Normalfall der Hashtabelle.- 3.5.5 Hashfunktionen und Randomisierung.- 3.5.6 Performanzanalyse.- 3.5.7 Ausdehnbare Formen von Hashing.- 4 Anhang.- 4.1 Notation.- 4.2 Komplexität von Problemen und Algorithmen.- 4.3 Asymptotik.- 4.4 Summenformeln.- 4.5 Rekursionsformeln.- 4.6 Permutationen.- 4.7 Geordnete Bäume.- 5 Übungen.- 5.1 Übungen zu Kapiteln 1 und 2.- 5.2 Übungen zu Datenstrukturen (Kapitel 3).- 5.3 Vordiplom Informatik 1 und 2.- Literaturübersicht.- Stichwortverzeichnis.