Grundkurs Angewandte Informatik II

ISBN-13: 9783519029359 / Niemiecki / Miękka / 1993 / 292 str.

Reinhard Richter;Reinhard Richter;Peter Sander

Opis

Ein zentraler Begriff der Informatik ist der Begriff des Algorithmus. Wir haben bereits in Band I dieses Grundkurses die Programmiersprache Modula-2 kennengelernt, die wir zum Schreiben von Programmen und damit - mehr oder weniger intuitiv - zur formalen Beschreibung von Algorithmen benutzt haben. In diesem Kapitel soll der Begriff des Algorithmus naher beleuchtet werden. Wir werden ihn hier nicht prazise definieren, denn es gibt eine Viel zahl gleichberechtigter, formaler Moglichkeiten, dies zu tun (s. Band IV dieses Grundkurses), aber wir werden uns mit dem Entwurf, den Darstellungsmog lichkeiten und wichtigen Eigenschaften von Algorithmen beschaftigen. Ganz allgemein dienen Algorithmen dazu, durch zielgerichtetes Handeln Probleme zu losen. Ein Algorithmus legt in exakter, unmissverstandlicher Weise fest, wie man fur ein vorgelegtes Problem zu einer Losung des Problems kommt, und wir beschreiben dies durch die folgende, vage Charakterisierung (eine genauere Beschreibung der Eigenschaften von Algorithmen folgt spater): Ein Algorithmus ist ein exaktes Verfahren zur Losung eines Problems. 2.1.1 Beobachtungen zu Algorithmen Mit einer Vielzahl von Algorithmen wird jeder bereits fruhzeitig in seinem Leben - unabhangig von der Informatik - konfrontiert. Als Beispiele fur Prob leme, die algorithmisch losbar sind, kann man nennen: Binden eines Schnursenkels oder einer Krawatte, Multiplikation zweier natur licher Zahlen, Bedienung eines Fahrkartenautomaten, Auswechseln von Zundkerzen, etc."

Spis treści

1 Informatik: Eine Übersicht.- 1.1 Informationen und ihre Verarbeitung.- 1.2 Informatik: Inhalt, Teilgebiete, Anwendungen.- 1.3 Zur Entwicklung der Informatik.- 1.3.1 Mechanisierung des Rechnens.- 1.3.2 Die Entwicklung im 19. und 20. Jahrhundert.- 1.3.3 Rechnergenerationen.- 2 Vom Problem zum Algorithmus.- 2.1 Einführung.- 2.1.1 Beobachtungen zu Algorithmen.- 2.1.2 Vom Problem zum Algorithmus und zum Programm.- 2.2 Spezifikation von Problemen.- 2.2.1 Anforderungen an die Problemspezifikation.- 2.2.2 Spezielle Probleme: Suchen und Sortieren.- 2.3 Algorithmen und ihre Darstellung.- 2.3.1 Programmablaufpläne.- 2.3.2 Struktogramme.- 2.3.3 Pseudocode.- 2.3.4 Gegenüberstellung der einzelnen Ablaufstrukturen.- 2.3.5 Datenflußpläne.- 2.4 Eigenschaften von Algorithmen.- 2.4.1 Ein Beispiel: Suchen.- 2.4.2 Endlichkeit.- 2.4.3 Determiniertheit und Determinismus.- 2.4.4 Rekursivität.- 2.4.5 Parallelität.- 2.4.6 Universalität.- 2.4.7 Korrektheit.- 2.4.7.1 Nachweis der Korrektheit durch Verifikation.- 2.4.7.2 Überprüfung der Korrektheit durch Testen.- 2.4.7.3 Korrektheit vs. Robustheit.- 2.4.8 Effizienz.- 2.5 Entwurfsmethoden für Algorithmen.- 2.5.1 Vorbemerkung.- 2.5.2 Entwurfsprinzipien.- 2.5.2.1 Schrittweise Verfeinerung.- 2.5.2.2 Modularisierung.- 2.5.2.3 Strukturierung.- 2.5.3 Entwurfstechniken.- 2.5.3.1 Systematisches Probieren und Backtracking.- 2.5.3.2 Divide and Conquer.- 2.5.3.3 Problemtransformation.- 2.6 Spezielle Algorithmen: Sortieren.- 2.6.1 Sortieren durch direktes Einfügen.- 2.6.2 Sortieren durch Auswahl.- 2.6.3 Quicksort.- 2.6.4 Heapsort.- 3 Vom Algorithmus zum Programm — Konzepte imperativer Programmiersprachen.- 3.1 Vorbemerkungen.- 3.2 Datentypen in Modula-2-ähnlichen Sprachen.- 3.2.1 Skalare Datentypen.- 3.2.1.1 Der Datentyp BOOLEAN.- 3.2.1.2 Die Datentypen CARDINAL und INTEGER.- 3.2.1.3 Der Datentyp REAL.- 3.2.1.4 Der Datentyp CHAR.- 3.2.1.5 Aufzählungstypen.- 3.2.2 Statische strukturierte Datentypen.- 3.2.2.1 Der Datentyp ARRAY.- 3.2.2.2 Der Datentyp RECORD.- 3.2.2.3 Der Datentyp SET.- 3.2.3 Dynamische strukturierte Datentypen.- 3.2.3.1 Der Datentyp SEQUENZ.- 3.2.3.2 Das POINTER-Konzept.- 3.3 Andere Datentypen.- 3.3.1 Vorbemerkungen.- 3.3.2 Lineare Listen.- 3.3.2.1 Unterschiedliche Arten linearer Listen.- 3.3.2.2 Grundoperationen für einfach verkettete lineare Listen.- 3.3.3 Schlange (queue) und Keller (stack).- 3.3.3.1 Grundoperationen für Schlange und Keller.- 3.3.3.2 Implementierung einer Schlange.- 3.3.3.3 Implementierung eines Kellers.- 3.3.4 Bäume.- 3.3.4.1 Vorbemerkungen.- 3.3.4.2 Anwendungsbeispiele für Bäume.- 3.3.4.3 Implementierung von Bäumen.- 3.4 Spezifikation abstrakter Datentypen.- 3.4.1 Wodurch wird ein Datentyp abstrakt?.- 3.4.2 Algebraische Spezifikation von Datentypen.- 3.4.2.1 Beschreibung der Syntax eines Datentyps.- 3.4.2.2 Beschreibung der Semantik eines Datentyps.- 3.5. Programmbausteine.- 3.5.1 Unterprogramme.- 3.5.2 Koroutinen und Prozesse.- 3.5.3 Module.- 4 Höhere Programmiersprachen.- 4.1 Klassifikation höherer Programmiersprachen.- 4.1.1 Höhere Programmiersprachen versus Maschinensprachen.- 4.1.2 Sprachparadigmen.- 4.1.2.1 Imperative Programmiersprachen.- 4.1.2.2 Funktionale Programmiersprachen.- 4.1.2.3 Logische Programmiersprachen.- 4.1.2.4 Objektorientierte Programmiersprachen.- 4.2 Definition von Programmiersprachen.- 4.2.1 Formale Beschreibung der Syntax.- 4.2.1.1 Elemente einer Metasprache.- 4.2.1.2 Backus-Naur-Form (BNF).- 4.2.1.3 Syntaxdiagramme.- 4.2.1.4 Die CODASYL-Metanotation.- 4.2.2 Formale Beschreibung der Semantik.- Lösungen.