Programmierung Und Datenstrukturen: Eine Einführung Anhand Von Beispielen

ISBN-13: 9783540171003 / Niemiecki / Miękka / 1986 / 149 str.

Ja1/4rg Nievergelt; Klaus Hinrichs

Opis

Dieses Buch ist aus der zweisemestrigen EinfUhrungsvorlesung Informatik 1 und 2 an der ErR Ziirich entstanden. Da der Inhalt des ersten Semesters, der die Abschnitte 1 und 2 umfasst, eine unkonventione11e EinfUhrung in die Informatik darstellt, ist eine ErkHirung angebracht, damit der Leser beurteilen kann, ob die Voraussetzungen und Zielsetzungen dieses Buches auf ihn zutreffen. Zlihlen wir zuerst die Funktionen auf, die dieses Buch niche zu erfiillen versuchl Dieses Buch ist keine Anfangeranleitung zum Programmieren. Wir setzen voraus, dass der Leser eine moderne Programmiersprache nicht nur kennt, sondern auch geiibt hat, zum Beispiel anhand einer der vielen EinfUhrungen ins Programmieren in Pascal. Wir streben keine umfassende Darste11ung der Informatik an, sondern wlihlen gezielt Themen aus, die schnell zu wichtigen Begriffen, Methoden und Erkenntnissen in einigen Kernbereichen der Informatik fUhren. Wer eine Ubersicht iiber einen viel grasseren Themenkreis sucht, dem sei die Injormatik von Bauer und Goos [BG] empfohlen. Wir streben auch keine formale Darste11ung der behandelten Themen an. Informatik ist zwar die Technik der Formalisierung, aber formale Darste11ungen sind in erster Linie fUr den Umgang mit Maschinen geeignet, nicht fUr die Kommunikation von Mensch zu Mensch. Gerade bei der ersten Begegnung mit einem Gedankengang, wie es beim Lesen eines Lehrbuches die Regel ist, ist Intuition der Schliissel zum Verstiindnis. Wir versuchen mit Vielen Beispielen und Bildern des Lesers Intuition anzusprechen.

Spis treści

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.