Richter Grundkurs Angewandte Informatik II

Problem - Algorithmus - Programm
1993
ISBN: 978-3-322-94767-3
Verlag: Vieweg & Teubner
Format: PDF
Kopierschutz: 1 - PDF Watermark

E-Book, Deutsch, Band 2, 292 Seiten, eBook

Reihe: XLeitfäden der angewandten Informatik

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 näher beleuchtet werden. Wir werden ihn hier nicht präzise definieren, denn es gibt eine Viel zahl gleichberechtigter, formaler Möglichkeiten, dies zu tun (s. Band IV dieses Grundkurses), aber wir werden uns mit dem Entwurf, den Darstellungsmög lichkeiten und wichtigen Eigenschaften von Algorithmen beschäftigen. Ganz allgemein dienen Algorithmen dazu, durch zielgerichtetes Handeln Probleme zu lösen. Ein Algorithmus legt in exakter, unmißverständlicher Weise fest, wie man für ein vorgelegtes Problem zu einer Lösung des Problems kommt, und wir beschreiben dies durch die folgende, vage Charakterisierung (eine genauere Beschreibung der Eigenschaften von Algorithmen folgt später): Ein Algorithmus ist ein exaktes Verfahren zur Lösung eines Problems. 2.1.1 Beobachtungen zu Algorithmen Mit einer Vielzahl von Algorithmen wird jeder bereits frühzeitig in seinem Leben - unabhängig von der Informatik - konfrontiert. Als Beispiele für Prob leme, die algorithmisch lösbar sind, kann man nennen: Binden eines Schnürsenkels oder einer Krawatte, Multiplikation zweier natür licher Zahlen, Bedienung eines Fahrkartenautomaten, Auswechseln von Zündkerzen, etc.

Zielgruppe

Upper undergraduate

Autoren/Hrsg.

Richter, Reinhard

Inhaltsverzeichnis

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.