Prozedurale Programmierung - Kapitel 1 - Einführung

Inhalte von Dr. E. Nadobnyh

1.1. Algorithmen

Schritte zur Problemlösung

1.Problemanalyse
Die Problemstellung (Aufgabenstellung) wird präzise definiert und spezifiziert.

2. Algorithmenentwurf
Ein Algorithmus ist eine endliche Folge von eindeutigen und ausführbaren Anweisungen zur Lösung eines allgemeinen Problems.

3.Programmierung (Codierung, Implementierung)
Ein Programm ist ein in einer Programmiersprache formulierter Algorithmus.

4.Programmausführung
Gültige Eingaben liefern korrekte Ergebnisse.

Anforderungen an Algorithmen

1.Eindeutigkeit (Determinismus)
Die Reihenfolge der Schritte ist eindeutig festgelegt.

2.Determiniertheit
Der Algorithmus muss bei denselben Eingaben das gleiche Ergebnis liefern.

3.Endlichkeit
Das Verfahren darf nur endlich viele Schritte benötigen.

4.Ausführbarkeit
Es dürfen keine Bedingungen für Entscheidungen vorkommen, die erst in nachfolgenden Schritten festgelegt werden.

5.Allgemeinheit
Ein Algorithmus löst nicht nur ein einziges Problem, sondern eine Klasse von Problemen.

6.Effizienz
Die Anzahl der benötigen Schritte soll möglichst gering sein.


Beispiele - Folgende Anweisungen sind keine Algorithmen:

N	Anweisung	Ursache
1	Gehe bis zum Theaterplatz. Dort biege ab und gehe bis zum Bahnhof.	nicht eindeutig: z.B. wohin abbiegen?
2	Bezahle, wenn Ostern und Pfingsten auf einen Tag fallen.	nicht ausführbar.
3	Addiere zu einer beliebigen geraden Zahl mehrere anderen geraden Zahlen bis das Ergebnis 99 ist!	nicht endlich: 99 wird nie als Ergebnis herauskommen.

Darstellung von Algorithmen

1.Umgangssprachliche Formulierung
Es gibt häufig keine vorgegebenen Schemata oder Regeln. Die Beschreibung sollte jedoch exakt sein.

2.Pseudocode
Pseudocode ist eine sprachliche Mischung aus natürlicher Sprache, mathematischer Notation und einer höheren Programmiersprache.

3.Programmablaufplan
Stellt in Symbolen die einzelnen Programmanweisungen in ihrer Logik dar.

4.Struktogramm
Die Darstellung erfolgt grafisch angeordnet innerhalb eines Rechtecks und entspricht der Methode der strukturierten Programmierung.

PAP -Programmablaufplan

PAP ist eine normierte Methode zur graphischen Darstellung von Algorithmen.



PAP. Beispiel
Ausgabe von allen natürlichen Zahlen von 1 bis 39 sowie 61 bis 100.

Struktogramm

Ein Struktogramm (Nassi-Shneiderman-Diagramm) ist eine normierte Methode zur Algorithmen-Darstellung mit den so genannten Strukturblöcken. Strukturblöcke können ineinander geschachtelt werden. Typische Strukturblöcke sind:

Sequenz


Aufruf


Alternativ


Wiederholung



Struktogramm. Beispiel

Euklidischer Algorithmus für ggT.

Der größte gemeinsame Teiler (ggT) zweier ganzer Zahlen a und b ist die größte natürliche Zahl, durch die sowohl a als auch b ohne Rest teilbar sind.

1.2. Programm und Programmausführung

Programm

Programme sind letztlich konkrete Formulierungen der Algorithmen, die sich auf bestimmte Darstellungen und Datenstrukturen stützen. [Wirth, N.]

Ein Programm beinhaltet zwei wesentliche Teile:
1. Daten, auf die Wirkung ausgeübt wird.
2. Handlungen (Anweisungen), mit denen auf die Daten in bestimmter Reihenfolge eingewirkt wird.

Anweisungen eines Programms beinhalten drei wesentliche Teile:

• Eingabe,

• Verarbeitung und

• Ausgabe

Damit entspricht eines Programm dem klassischen EVA-Prinzip der Datenverarbeitung.

Computeraufbau

Zwei grundsätzliche Bausteine eines Computers sind Software und Hardware.

1. Hardware: Prozessor, Hauptspeicher (RAM), Sekundärspeicher (Festplatte, USB-Stick), Peripherie (Bildschirm, Tastatur, Maus) usw. Die Hardware wurde nach der Von-Neumann-Architektur konzipiert.

2. Software: Anwendungen (Word, Power Point, Eigene Programme), Betriebssysteme (Windows, Unix), Bibliotheken (stdio, iostream, math). Man kann verschiedene Schichten der Software identifizieren. Sie unterscheiden sich durch ihren Abstand zur Hardware.

Schichtenmodell der Software

Ein einfaches Vierschichtenmodell:



1. Ein Betriebssystem vermittelt zwischen der Hardware und der Anwendung und gestaltet den Umgang mit der Hardware komfortabel und hardwareunabhängig.

2.Eine Programmbibliothek ist eine Sammlung von Hilfsprogrammen, die das Programmieren vereinfachen und die betriebssystemunabhängige Programmierung erlauben.

3.Eine Anwendung verwendet Dienste von den niedrigen Schichten und damit ist von der Hardware isoliert.

Von-Neumann-Rechner

Die Von-Neumann-Architektur ist ein bis heute gültigesnModell für sequentiellen Computer, wonach ein gemeinsamer Speicher sowohl Programm (Anweisungen) als auch Daten hält.



Das Programm wird sequentiell, Schritt für Schritt abgearbeitet. Dafür werden einzelne Anweisungen (Befehle) aus dem Hauptspeicher gelesen und dann auf dem Prozessor ausgeführt.

Eingabe und Ausgabe

Die Eingabe/Ausgabe ist ein Kommunikationsverfahren zwischen dem laufenden Programm und der Außenwelt.

Von der Seite des laufenden Programms sind die Eingabe und Ausgabe den Datentransport zwischen der Peripheriegeräten und dem Hauptspeicher.

1.3. Die Programmiersprache C/C

Programmiersprachen

Eine Programmiersprache ist eine Notation für Computer-Programme.

Es gibt einige tausende von Programmiersprachen, von denen wenige Dutzende wirklich wichtig sind. Viele sind für spezielle Anwendungen entworfen worden.

Höhere (problemorientierte) Programmiersprachen orientieren sich an den zu lösenden Problemen und nicht an den benutzten Maschinen. Diese Sprachen sind hardwareunabhängig. Dazu zählt "C" und ihr Nachfolger "C“.

C und C

Die Sprache C wurde 1972 von Dennis M. Ritchie und C 1979 von Bjarne Stroustrup entwickelt.

C ist die Weiterentwicklung der Programmiersprache C für die objektorientierte Programmierung.

Die Sprache C ist in C vollständig enthalten. Manchmal wird diese Kombination als C/C bezeichnet.

Die prozedurale Programmierung kann man mit C oder auch mit C lernen. Einige Funktionalitäten sind in der Sprache C didaktisch besser realisiert, u.a.:

• dynamische Speicherzuweisung,

• Ausnahmebehandlung,

• Variableninitialisierung,

• Eingabe und Ausgabe mit der Stream-I/O-Bibliothek.

Charakteristika der Sprache C/C

1) C/C ist eine der weit verbreitetsten, höheren Programmiersprachen.

2) Kern ist relativ klein und extrem maschinennah. Folge:

• hohe Laufzeiteffizienz,

• hohe Kompaktheit.

• hohe Portabilität.

3) Fehlende Funktionalitäten werden durch die Standardbibliothek bereitgestellt. C/C hat:

• keine mathematischen Standardfunktionen,

• keine Mechanismen für parallele Prozesse,

• keine Sprachelemente für Ein-/Ausgabe.

Das macht diejenigen Programme schlanker, die keine zusätzliche Funktionalitäten benötigen.

Nachteile von C/C

1) Eine große Freiheit beim Kodieren kann dazu führen, dass schwer lesbarer Code geschrieben wird.

2) Als Anfänger haben Sie bereits direkten Zugriff auf die Hardware und können somit vieles durcheinander bringen, wenn Sie nicht wissen, was Sie genau tun.

3) Fehler, die bei anderen Sprachen bei Compilerlauf abgeschaltet werden, bergen die Gefahr, nicht gefunden zu werden.

Meist treten solche Fehler erst dann auf, wenn das Programm bereits freigegeben wurde.

1.4. Programmerzeugung

Programmerzeugung

1.Editor
Beim Editieren entsteht der Quelltext (Quellcode, source) in der Datei namens „xxx.cpp“, z.B. „hallo.cpp“.

2.Präprozessor
Ein Präprozessor ist ein Programm, welches Präprozessordirektiven, z.B. #include „header.h“, verarbeitet und die Kommentare ausblendet.

3.Compiler
Ungeachtet aller höheren Programmiersprachen können Computer nur Maschinenprogramme ausführen.
Der Compiler erzeugt den Objektcode namens, z.B. „hallo.obj“, der noch nicht ausführbar ist.

4.Linker
Der Linker bindet den Objektcode mit dem Objektcode der Bibliotheksdateien zusammen und erzeugt das Maschinenprogramm in einer ausführbaren Datei namens, z.B. „hallo.exe“.

5.Lader
Ein Lader ist ein Programm des Betriebssystems, das das Maschinenprogramm in den Speicher lädt und startet.

6.Debugger
Ein Debugger (debugging, dt.: entwanzen) ist eine spezielle Software zur Fehlersuche.

Erzeugung eines lauffähigen Programms

Syntaxfehler

Oft unterscheidet man drei Arten von Fehlern:

• Syntaxfehler,

• Laufzeitfehler und

• Logikfehler.

Ein Syntaxfehler ist ein Verstoß gegen die Regel der Programmiersprache. Syntaxfehler gehören zur einfachsten Fehlerart.

Syntaxfehler werden vom Compiler und vom Linker diagnostiziert und gemeldet. Warnungen werden dann gemeldet, wenn einige Konstrukte syntaktisch korrekt sind, aber erfahrungsgemäß nicht korrekt sein könnten.

Laufzeitfehler

Ein Laufzeitfehler ist ein Verstoß gegen eine Regel der Ausführungsumgebung. Typische Laufzeitfehler sind z.B.: falscher Umgang mit Datentypen, Speicherschutzverletzung, Division durch Null, Überlauf.

Diese Fehler können nicht in jedem Fall auftreten, sondern nur in einem bestimmten Kontext (z.B.: Benutzereingaben, Uhrzeit etc.). Sie können auch nicht immer reproduzierbar sein.

Ein Programm ist semantisch korrekt, wenn die Bedeutung der einzelnen Programmkonstrukte richtig ist. Die semantische Korrektheit eines Programms kann teilweise durch den Compiler und zur Laufzeit geprüft werden.

Logikfehler

Ein Logikfehler ist ein Verstoß gegen der Spezifikation des Programms.

Wegen des Logikfehlers kann ein syntaktisch und semantisch korrektes Programm die nicht erwarteten Ergebnisse liefern. Das Programm erfüllt nicht das, was man gemeint hat. Ein Programm ist korrekt, wenn es genau das in der Spezifikation festgelegte funktionale Verhalten zeigt. Laufzeitfehler und Logikfehler können in einem Test sichtbar werden.

Fehler- Entdeckung

Die Fehlersuche ist eine Hauptbeschäftigung beim Programmieren. Es gibt verschiedene Techniken für die Überprüfung, ob
das Programm so reagiert wie erwartet, z.B.:

1) Verifikationen und

2) Tests.

Eine Programmverifikation ist eine allgemeingültiger Nachweis, dass ein Programm eine Spezifikation erfüllt.

Tests

Testen ist der Vorgang, bei dem ein Programm mit der Absicht ausgeführt wird, um Fehler zu finden.

Werden bei einem Test keine Fehler gefunden, so beweist dies niemals, dass das Programm korrekt ist. Die Korrektheit eines Programms kann durch Testen (außer in trivialen Fällen) nicht bewiesen werden. Der Grund ist, dass alle Kombinationen aller möglichen Werte der Eingabedaten getestet werden müssten. Die Anzahl der Kombinationen ist bei realen Programmen zu groß, um diese alle zu testen.

Wurde ein Programm sorgfältig getestet, so steigt die Wahrscheinlichkeit, dass das Programm sich auch in den nicht getesteten Fällen wunschgemäß verhält.

Einige Test-Varianten

1. Wegwerf-Test
Jedes Programm muss mit einfachen Daten (die man im Kopf schnell nachrechnen kann) sorgfältig testet werden.

2. Schreibtischtest (Code-Review)
Die Fehlersuche erfolgt durch aufmerksames Studium des Quelltextes.

3. Systematischer Test
Ableitung von Testfällen aus der Spezifikation.