Appelrath / Ludewig Skriptum Informatik

Eine konventionelle Einführung
3. Auflage 1995
ISBN: 978-3-322-91824-6
Verlag: Vieweg & Teubner
Format: PDF
Kopierschutz: 1 - PDF Watermark

E-Book, Deutsch, 464 Seiten, eBook

Es handelt sich um ein alltägliches Problem, wie es einem in Oldenburg und Umge bung (immer noch, aber seltener werdend) begegnet. Jemand betritt einen Milchladen mit einer Kanne K, die genau die Menge V K (z. B. VK = 7 1) faßt, und möchte die Menge Soll kaufen (mit 0 < Soll S; VK , z. B. Soll = 41). Der Milchverkäufer hat nur einen Eimer E, der es erlaubt, die Menge VE (mit VE ~ VK, z. B. VE = 10 1) abzumessen. Frage: Kann man mit diesen beiden Gefäßen aus einer großen Milchwanne die gewünschte Menge abfüllen oder nicht? Und falls ja, wie soll das vor sich gehen? Die Lösung soll also möglichst für beliebige Werte von VK, Soll S; VK und VE ~ VK anwendbar sein; der Fall VE < VK läßt sich durch Tausch der Gefäße analog behandeln. Der Einfachheit halber nehmen wir an, daß es sich stets um ganze Liter handelt, daß wir also VK, Soll und VE durch natürliche Zahlen darstellen können. Da wir nur mit Vielfachen des Volumens 11 zu tun haben, können wir die Einheit weg lassen. Wenn Soll null oder VK ist, ist die Lösung trivial; andernfalls läßt sich das Problem immer dann lösen, wenn die gewünschte Menge Soll ein Vielfaches des größten gemeinsamen Teilers von VK und VE ist; das ist sicher der Fall, wenn VK und VE teilerfremd sind.

Zielgruppe

Upper undergraduate

Autoren/Hrsg.

Appelrath, Hans-Jürgen

Ludewig, Jochen

Inhaltsverzeichnis

1. Grundlagen.- 1.1 Algorithmus und Berechenbarkeit.- 1.1.1 Algorithmus.- 1.1.2 Turing-Maschine.- 1.1.3 Berechenbarkeit.- 1.2 Sprache und Grammatik.- 1.2.1 Sprache.- 1.2.2 Grammatik.- 1.3 Rechner.- 1.3.1 Von-Neumann-Rechnerarchitektur.- 1.3.2 Rechnersysteme.- 1.4 Informatik als Wissenschaft.- 2. Imperative Programmierung — die Sprache Modula-2.- 2.1 Syntaxdarstellungen.- 2.2 Elementare funktionale Modula-2-Programme.- 2.2.1 Eine Modula-2-Teilsprache.- 2.2.2 Programmverzweigungen.- 2.2.3 Funktionen und Prozeduren.- 2.2.4 Elementare Datentypen, Aufzählungs- und Bereichstypen.- 2.2.5 Eingabevariablen.- 2.2.6 Rekursive Funktionen und Prozeduren.- 2.2.7 Nachteile funktional-rekursiver Programme.- 2.3 Iterative Programme.- 2.3.1 Wertzuweisungen und Referenzparameter.- 2.3.2 Gültigkeitsbereich und Lebensdauer.- 2.3.3 Anweisungen zur Iteration.- 2.3.4 Vergleich iterativer und rekursiver Lösungen.- 2.3.5 Sprunganweisungen.- 2.3.6 Prozedurtypen.- 2.4 Komplexe Datentypen.- 2.4.1 Mengen (Sets).- 2.4.1.1 Darstellung und Manipulation von Mengen.- 2.4.1.2 Ein Beispiel für Sets.- 2.4.2 Arrays (Felder).- 2.4.3 Records (Verbunde).- 2.4.3.1 Einfache Records.- 2.4.3.2 Records mit Varianten.- 2.4.4 Zeiger (Pointer) und dynamische Variablen.- 2.4.4.1 Die Speicherung auf der Halde.- 2.4.4.2 Operationen auf Zeigern.- 2.4.4.3 Verkettete Listen.- 2.4.4.4 Anwendungen und Probleme dynamischer Variablen.- 2.4.5 Dateien (Files).- 2.4.5.1 Eigenschaften und formale Beschreibung.- 2.4.5.2 Dateien in Pascal.- 2.4.5.3 Dateien in Modula-2.- 3. Abstraktion.- 3.1 Abstraktionskonzepte in Programmiersprachen.- 3.2 Abstraktion in Modula-2.- 3.2.1 Das Prinzip der separaten Übersetzung.- 3.2.2 Modularisierung eines Programms.- 3.2.3 Datenkapselung.- 3.2.4 Abstrakte Datentypen.- 3.2.4.1 Das Prinzip des Abstrakten Datentyps.- 3.2.4.2 Abstrakte Datentypen Schlange und Stack.- 3.2.4.3 Abstrakter Datentyp für große Zahlen.- 3.2.4.4 Abstrakter Datentyp für komplexe Zahlen.- 4. Semantik, Verifikation und Test.- 4.1 Konzepte für eine Semantikdefinition.- 4.1.1 Semantik: Begriff und Motivation.- 4.1.2 Grundprinzipien von Semantiknotationen.- 4.1.3 Fin Beispiel für die operationale Semantik.- 4.2 Spezifikation und Verifikation von Programmen.- 4.2.1 Vor- und Nachbedingungen.- 4.2.2 Schwächste Vorbedingungen.- 4.2.3 Die Verifikation.- 4.2.4 Beschreibung einer Schleife durch eine Invariante.- 4.2.5 Konstruktion iterativer Programme.- 4.2.6 Zusammenfassung.- 4.3 Test.- 4.3.1 Begriffsbildung und Prinzipien.- 4.3.1.1 Begriffliche Abgrenzung.- 4.3.1.2 Aufgabenteilung und Zielsetzung.- 4.3.1.3 Material und Resultate des Tests.- 4.3.2 Grenzen des Testens.- 4.3.3 Die Konstruktion von Testdaten.- 4.3.4 Zusammenfassung.- 5. Programmierparadigmen und -sprachen.- 5.1 Programmierparadigmen.- 5.1.1 Imperatives Programmieren.- 5.1.2 Funktionales Programmieren.- 5.1.3 Logik-basiertes Programmieren.- 5.1.4 Objektorientiertes Programmieren.- 5.1.5 Regel-basiertes Programmieren.- 5.1.6 Programmierung von Mehrprozessor-Systemen.- 5.2 Übersicht über Programmiersprachen.- 6. Datenstrukturen und Algorithmen.- 6.1 Komplexität und Effizienz.- 6.1.1 Motivation und Begriffsbildung.- 6.1.2 Effizienz und Komplexität von Algorithmen.- 6.1.3 Komplexität von Funktionen und Sprachen.- 6.2 Graphen und Bäume.- 6.2.1 Graphen.- 6.2.2 Bäume.- 6.3 Suchen in gegebenen Datenstrukturen.- 6.3.1 Suchen in Tabellen.- 6.3.2 Suchen von Zeichenketten.- 6.4 Datenorganisationen für effizientes Suchen.- 6.4.1 Suchverfahren auf Bäumen.- 6.4.1.1 Binäre Suchbäume.- 6.4.1.2 AVL-Bäume.- 6.4.1.3 Optimale Suchbäume.- 6.4.1.4 B-Bäume.- 6.4.1.5 Weitere balancierte Suchbäume.- 6.4.2 Hashing.- 6.4.2.1 Begriffsbildung und Anforderungen.- 6.4.2.2 Perfektes Hashing.- 6.4.2.3 Kollisionsbehandlung.- 6.4.2.4 Löschen in Hash-Tabellen.- 6.4.2.5 Aufwandsabschätzung.- 6.4.2.6 Implementierung von Kollisionsbehandlungen.- 6.5 Sortieren.- 6.5.1 Klassifizierung und allgemeine Betrachtungen.- 6.5.2 Interne Sortierverfahren.- 6.5.2.1 Einfache Sortierverfahren.- 6.5.2.2 Schnelle Sortierverfahren.- 6.5.2.3 Implementierung ausgewählter Sortierverfahren.- 6.5.2.4 Aufwandsvergleich der Sortierverfahren.- 6.5.2.5 Sortieren durch Streuen und Sammeln.- 6.5.3 Externe Sortierverfahren.- 6.5.3.1 Direktes Mischen.- 6.5.3.2 Natürliches Mischen.- 6.5.3.3 Mehrwege-Mischen.- 6.6 Speicherverwaltung.- 6.6.1 Algorithmische Konzepte.- 6.6.2 Implementierung von Stacks.- Anhang A: Mathematische Grundbegriffe und Formeln.- Anhang B: Syntaxdiagramme für Modula-2.- Literatur.- Abkürzungsverzeichnis.- Modula-2-Index.