Kapitel 5Der Algorithmus

Kapitel 5Kapitel 5 Der AlgorithmusDer Algorithmus

1. Definieren Sie den Datentyp für eine1. einfach verkettete Liste (die Datenwerte seien vom Typ: integer)

2. doppelt verkette Liste (die Datenwerte seien vom Typ: integer)

2. Definieren Sie den Datentyp für ein beliebiges Netz - siehe Bild(der Datenwert jedes Knotens sei vom Typ: integer)

<int>

<int>

<int>

<int>

<int>

<int>

<int>

<int>

<int>

5.15.1 Ein BeispielEin Beispiel

Zunächst soll ein kleines Beispiel in eine mögliche Aufgabenstellung aus dem (bekannten) Bereich der Mathematik einführen und dadurch auch eine (eingeschränkte) Vorstellung über die Aufgaben und Elemente eines Algorithmuses geben.

Inhalt1. Das Problem (Beispiel)

2. Ein Algorithmus I

3. Ein Algorithmus II

4. Vergleich der Algorithmen

5. Ein Algorithmus III

6. Fragestellungen

7. Ein weiterer Algorithmus

5.1.15.1.1 Das ProblemDas Problem

Eine quadratischen Gleichung:

Allgemeine Darstellung der quadratischen Gleichung

Allgemeine Lösung der quadratischen Gleichung

Lösung der quadratischen Gleichung

x2 + 8x + 7 = 0

x2 + px + q = 0

x1,2= -p/2 p2/4 - q +-

x1,2 = -8/2 82/4 - 7

= -4 3

+-

+-x1 = -1x2 = -7

ZuweisungenZuweisungen

5.1.35.1.3 Ein Algorithmus IEin Algorithmus I

1. Lies die Zahlen p und q ein

2. Berechne die Zahl w = p2/4 - q

3. Berechne die Zahl x1 = -p/2 + w

4. Berechne die Zahl x2 = -p/2 - w

5. Gib x1 und x2 als Ergebniss aus

Ein Algorithmus

BerechnungenBerechnungen

AusgabenAusgaben

EingabenEingaben

VariableVariable

KonstanteKonstante

x1,2= -p/2 p2/4 - q +-

5.1.45.1.4 Ein Algorithmus IIEin Algorithmus II

Ein zweiter Algorithmus


2. Berechne die Zahl p/2; Nenne diese Zahl a

3. Berechne die Zahl a2 ; Nenne diese Zahl b

4. Berechne die Zahl b-q ; Nenne diese Zahl c

5. Berechne die Zahl c ; Nenne diese Zahl d

6. Berechne die Zahl -a ; Nenne diese Zahl e

7. Berechne die Zahl e + d ; Nenne diese Zahl x1

8. Berechne die Zahl e - d ; Nenne diese Zahl x2

9. Gib x1 und x2 als Ergebniss ausFHSymbol1 Es gibt (oft unendlich) viele Algorithmen zur

Lösung eines Problems

x1,2= -p/2 p2/4 - q +-

5.1.55.1.5 Vergleich der AlgorithmenVergleich der Algorithmen

Berechne die Zahl w = p2/4 - q

Berechne die Zahl x1 = -p/2 + w

Berechne die Zahl x2 = -p/2 - w

Berechne die Zahl p/2; Nenne diese Zahl a

Berechne die Zahl a2 ; Nenne diese Zahl b

Berechne die Zahl b-q ; Nenne diese Zahl c

Berechne die Zahl c ; Nenne diese Zahl d

Berechne die Zahl -a ; Nenne diese Zahl e

Berechne die Zahl e + d ; Nenne diese Zahl x1

Berechne die Zahl e - d ; Nenne diese Zahl x2

A1 A2Anzahl Berechnungen 10 7Anzahl Zuweisungen 3 7Anzahl Variablen 5 9

FHSymbol1

WelcherAlgorithmusist besser ?Warum ?


2. Berechne die Zahl a = p/2

3. Berechne die Zahl b = a2

4. Berechne die Zahl c = b-q

5.a Wenn c negativ ist brich den Algorithmus abAnsonsten mache mit nächstem Schritt weiter

6. Berechne die Zahl d = c

7. Berechne die Zahl e = -a

8. Berechne die Zahl x1 = e + d 1

9. Berechne die Zahl x2 = e - d


5.1.65.1.6 Ein Algorithmus IIIEin Algorithmus III

Problem: Negatives Wurzelargument

BedingteAusführung

5.b Wenn c negativ istgehe zu Schritt 1

Schleife

5.1.75.1.7 FragestellungenFragestellungen

Wer gibt p und q ein ? Wie wird p und q eingegeben ? Werden p und q in endlicher Zeit

eingegeben ? Sind p und q im richtigen Format ? Ist Variable a im richtigen Format ? Gibt es die Quadrat-Funktion ? Ist c positiv ? Ist Variable e im richtigen Format ? Sind die restlichen Variablen im richtigen

Format Reicht die Genauigkeit der Darstellung ? Wo wird das Ergebnis ausgegeben ? Ist ausreichend Variablenkapazität für den

Algorithmus vorhanden ? Läuft der Algorithmus schnell genug ? ...


2. Berechne die Zahl a = p/2

3. Berechne die Zahl b = a2

4. Berechne die Zahl c = b-q

6. Berechne die Zahl d = c

7. Berechne die Zahl e = -a

8. Berechne die Zahl x1 = e + d 1

9. Berechne die Zahl x2 = e - d


FHSymbol1

Welche offenenFragen bestehennoch ?

5.1.85.1.8 Ein weiterer AlgorithmusEin weiterer Algorithmus

5.25.2 DefinitionDefinition

Der Begriff des Algorithmus ist zentral in der Informatik und soll in diesem Unterkapitel formal definiert werden

Inhalt1. Herkunft

2. Der Algorithmus

3. Beispiel: Algorithmenbeweis

4. Weitere Prinzipien

5. Algorithmen und Programme

6. Ausflug: Algorithmus und WinOSe

5.2.15.2.1 HerkunftHerkunft

Muhammad ibn Musa abu Djafar al-Choresmi (ca. 780-850 n.Chr) arabischer Mathematiker, geboren in Choresmien (heute: Usbekistan) lebte und wirkte in Bagdad im „Haus der Weisheit“ war beteiligt an der Übersetzung der Werke griechischer Mathematiker

ins Arabische schrieb ein „Kurzgefasstes Lehrbuch für die Berechnung durch Vergleich

und Reduktion“ die lateinische Übersetzung dieses Buches („liber algorismi“) kam durch

Kreuzfahrer nach Europa verfasste auch ein Buch mit dem Titel „Al-Mukhtasar fi Hisab al-Jahr va

l-Muqabala“

Algebra

Algorithmus

5.2.25.2.2 Der AlgorithmusDer Algorithmus

Definition:Ein Algorithmus (algorithm) ist die Beschreibung eines Verfahrens, um aus gewissen Eingabegrößen bestimmte Ausgabegrößen zu berechnen. Dabei müssen folgende Bedingungen erfüllt sein

Spezifikation Durchführbarkeit Korrektheit

Verfahren ohne Verständnis des Problemes

FHSymbol1 Erwarten Sie nie, dass ein Computer für Sie mitdenkt

5.2.25.2.2 Der Algorithmus : SpezifikationDer Algorithmus : Spezifikation

Eingabespezifikation: Es muss genau spezifiziert sein, welche Eingabegrößen erforderlich sind

und welchen Anforderungen diese Größen genügen müssen, damit das Verfahren funktioniert

Ausgabespezifikation Es muss genau spezifiziert sein, welche Ausgabegrößen (Resultate) mit

welchen Eigenschaften berechnet werden

EINGABEAlgorithmus

5.2.25.2.2 Der Algorithmus : DurchführbarkeitDer Algorithmus : Durchführbarkeit

Endliche Beschreibung das Verfahren muss in einem endlichen Text vollständig beschrieben

sein

Effektivität Jeder Schritt des Verfahrens muss effektiv (d.h. tatsächlich)

„mechanisch“ ausführbar seinBem.: „Effektivität“ ist nicht zu verwechseln mit „Effizienz“ („Wirtschaftlichkeit“)

Determiniertheit Der Verfahrensablauf ist zu jedem Zeitpunkt fest vorgeschrieben

5.2.25.2.2 Der Algorithmus : KorrektheitDer Algorithmus : Korrektheit

partielle Korrektheit Jedes berechnete Ergebnis genügt der Ausgabespezifikation, sofern die

Eingaben der Eingabespezifikation genügt haben

Terminierung Der Algorithmus hält nach endlich vielen Schritten mit einem Ergebnis

an, sofern die Eingaben der Eingabespezifikation genügt haben

5.2.25.2.2 Der Algorithmus : ZusammenfassungDer Algorithmus : Zusammenfassung

DefinitionEin Algorithmus (algorithm) ist die Beschreibung eines Verfahrens, um aus gewissen Eingabegrößen bestimmte Ausgabegrößen zu berechnen,der gekennzeichnet ist durch:

1. Spezifikation der Ein- und

2. Ausgabegrößen

3. eine endliche Beschreibung des Verfahrens

4. effektive Ausführbarkeit der Verfahrensschritte

5. Determiniertheit der Verfahrensschritte

6. partielle Korrektheit

7. Terminiertheit

Bemerkung: Algorithmen, die eine oder mehrere dieser Eigenschaften nicht besitzen

werden dann als Nicht-<Eigenschaft> Algorithmen bezeichnet. Bsp: Nicht-Deterministische Algorithmen.

5.2.35.2.3 Beispiel: AlgorithmenbeweisBeispiel: Algorithmenbeweis

In gängiger mathematischer Notation könnte ein Verfahren zur Berechnung der Modulus-Funktion a mod b wie folgt aussehen:

a falls a < bmod(a,b) =

mod(a-b,b) falls a b Um festzustellen, ob diese Berechnungsvorschrift einen Algorithmus im

Sinne der Definition darstellt, müssen folgende Punkte beachten werden:

Spezifikation Eingabe Ausgabe

Durchführbarkeit Endliche Beschreibung Effektivität Determiniertheit

Korrektheit Partielle Korrektheit Terminierung

5.2.35.2.3 Beispiel: SpezifikationBeispiel: Spezifikation

Lassen sich die möglichen Ein- und Ausgabewerte genau spezifizieren ?

5.2.35.2.3 Beispiel: DurchführbarkeitBeispiel: Durchführbarkeit

Ist der Algorithmus durchführbar ?

5.2.35.2.3 Beispiel: Korrektheit (partielle)Beispiel: Korrektheit (partielle)

Ist der Algorithmus korrekt (im Sinne der Spezifikation)

5.2.35.2.3 Beispiel: Korrektheit (Terminierung)Beispiel: Korrektheit (Terminierung)

Terminiert der Algorithmus ? Bemerkung: Es gibt kein Verfahren, das zu einem beliebigen

Algorithmus angibt, ob er terminiert oder nicht („Halte-Problem“)

5.2.35.2.3 Weitere PrinzipienWeitere Prinzipien

Neben den in der Definition angegebenen Eigenschaften gibt es weitere wichtige Prinzipien, die bei der Erstellung eines Algorithmuses zu beachten sind:

Effizienz Der Algorithmus soll möglichst wenig Aufwand verursachen

– Das Ergebnis mit möglichst wenig Rechenschritten (oder mit möglichst wenig Speicherbedarf) erzielen

Korrektheit beweisbar? Ein nicht-korrekter Algorithmus ist nach unserer Definition kein Algorithmus! Trotzdem sind nicht-korrekte Verfahren eher die Regel als die Ausnahme

5.2.45.2.4 Algorithmen und Programme: Der WegAlgorithmen und Programme: Der Weg

gegeben: das Problem durch Spezifizieren wird das Problem formal beschrieben

Durch Algorithmierung (Algorithmenentwurf) wird ein Algorithmus erzeugt

durch Verifizieren kann der Algorithmus auf Übereinstimmung mit der Spezifikation überprüft werden

Durch Programmieren wird aus den Algorithmus ein Programm erzeugt durch Testen kann das Programm auf Übereinstimmung mit der

Spezifikation und dem Algorithmus überprüft werden.

Problem Algorithmus Programm

Spezifizieren Verifizieren Testen

Algorithmierung Programmierung

5.2.45.2.4 Algorithmen und Programme: BeziehungenAlgorithmen und Programme: Beziehungen

Programmieren setzt Algorithmenentwicklung voraus Kein Programm ohne Algorithmus !

Jedes Programm repräsentiert einen bestimmten Algorithmus. Ein Algorithmus kann durch viele Programme repräsentiert werden.

Algorithmus ProgrammProgrammierung

ProblemAlgorithmierung

Problem

Algorithmus1 Algorithmus2

Programm21 Programm22

...

...

5.2.55.2.5 Ausflug: Algorithmus und WinOSeAusflug: Algorithmus und WinOSe

KlassischeProgrammierung

WindowsProgrammierung

Algorithmus

OS

OS Eventqueue

5.35.3 StrukturelementeStrukturelemente

Um die Dynamik - also die Abfolge von Aktionen - eines Algorithmu-ses zu beschreiben, benötigt man formale Beschreibungsmittel, sowie eine Festlegung, wie diese Beschreibungmittel zu notieren und zu interpretieren sind.Dieses Unterkapitel stellt die formalen Beschreibungsmittel für Algorithmen vor. Diese Beschreibungsmittel sind dabei gleichzeitig Strukturierungselemente für Algorithmen, denn sie definieren die Struktur von Algorithmen.

Inhalt:1. Die Elemente

2. Folge

3. Auswahl

4. Wiederholung

5.3.15.3.1 Die Elemente: Aus dem BeispielDie Elemente: Aus dem Beispiel

Zuweisungen Berechnungen

Mathematische Grundoperationen komplexe Funktionen ...

Bedingte Ausführungen Schleife ...

Variable Texte Zahlen ...

Konstanten(Literale)

Texte Zahlen ...

EINGABE

AUSGABE

5.3.15.3.1 Die Elemente: NotationDie Elemente: Notation

Für die Beschreibung von Algorithmen gibt es viele Möglichkeiten Alltagssprache Konkrete Programmiersprache Dazwischen gibt es eine Vielzahl von Notationen, die den Übergang

zwischen Problembeschreibung und Programm erleichtern sollen

Eine mögliche - eindimensionale - Notation ist Pseudocode: // Dies ist eine Zuweisung

x = 42; Kommentare werden (hier) mit vorangestellten Slashes „//“ gekennzeichnet Aktionen werden (hier) mit Semikolon „;“ getrennt

Visualisierung durch graphische - zweidimensionale -Notation Flussdiagramme Struktogramme (=Nasi-Schneidermann-Diagramme)

Aktion Aktion

5.3.15.3.1 Die Elemente: atomaren ElementeDie Elemente: atomaren Elemente

Anweisungen sind die atomaren Elemente eines Algorithmus‘, die Elemente also, aus denen ein Algorithmus aufgebaut ist.

Es gibt (zunächst) drei Arten dieser „atomaren“ Elemente Zuweisung:

Pseudocode X = y; Auf der linken Seite der Zuweisung steht eine Variable auf der rechten Seite der

Zuweisung steht entweder eine Variable, ein Literal oder eine Berechnung aus Varaibelen und Literalen

Eingabe Pseudocode: x << <Eingabegerät> ; Als Eingabegerät kann ein geeignetes physikalisches Geraöt (Tastatur,

Schnittstelle, ...) angegeben werden.

Ausgabe Pseudocode: x >> <Ausgabegerät> ; Als Ausgabegerät kann ein geeignetes physikalisches Geraöt (Bildschirm,

Drucker, Schnittstelle, ...) angegeben werden

Ein- und Ausgabe können auch als Zuweisung verstanden werden.

5.3.15.3.1 Die Elemente: KontrollelementeDie Elemente: Kontrollelemente

Die atomaren Elemente eines Algorithmuses können durch drei einfache Strukturierungsmethoden, den „Kontrollelementen“, zueinander in Beziehung gesetzt werden:

1. Folge (Sequenz)

2. Auswahl (Selektion, Fallunterscheidung)

3. Wiederholung (Iteration, Schleife)

Die Kontrollelemente bestimmen die Reihenfolge von Aktionen in Algorithmen

Eine Aktion (Ai) - auch Verarbeitung genannt - ist ein atomares Element oder eine durch die Strukturmethoden zusammengefasste Menge mehrerer Aktionen

5.3.25.3.2 FolgeFolge

Folgen bestimmen die lineare Reihenfolge von Aktionen in Algorithmen:

Flussdiagramm Struktogramm Pseudocode:

A1

A2

An

...

A1

A2

An

...

{ A1; A2; ... An;}

5.3.35.3.3 Auswahl : bedingte VerarbeitungAuswahl : bedingte Verarbeitung

Eine Aktion wird, in Abhängigkeit einer bool‘schen Bedingung ausgeführt oder nicht

auch „einarmiges if“ genannt.

Flussdiagramm Struktogramm Pseudocode:

Beispiel: if (x<0) then x = -x;

A1

BA1

if B then A1;Bf

wfw

A2

5.3.35.3.3 Auswahl : einfache AlternativeAuswahl : einfache Alternative

In Abhängigkeit einer bool‘schen Bedingung wird entweder eine Aktion oder eine andere Aktion ausgeführt

auch „zweiarmiges if“ genannt.

Flussdiagramm Struktogramm Pseudocode

Beispiel: if (x<0) then x:=-x else x=0;

A1

BA1

if B then A1

else A2;

Bfw

fw

A2

5.3.35.3.3 Auswahl : mehrfache AlternativeAuswahl : mehrfache Alternative

In Abhängigkeit einer Bedingung (mit mehreren möglichen Werten w1, w2, ..., wn) wird eine Aktion aus einer Menge möglicher Aktionen ausgewählt und ausgeführt


Beispiel: switch x: { case 0: x = x/2; case 1; x = x+1;}

Oft auch mit „else“-Alternative (statt wn)

A1

B switch B:{ case w1: A1; case w2: A2; ... case wn: An;}

Bw1

w1

A2 An

A1 A2 An

wnw2 wn

5.3.45.3.4 Schleife: Schleife: mit mit vorausgehender vorausgehender PrüfungPrüfung

Solange eine bool‘sche Bedingung erfüllt ist, wird eine Aktion ausgeführt.

Die Bedingung wird vor der ersten Ausführung der Aktion geprüft heißt auch: abweisende Schleife (While-Schleife)


Beispiel: while x < 100 { x = x + 1;}

A1

A1

while B{ A1

}

Bf

w

B

5.3.45.3.4 Schleife: Schleife: mit mit nachfolgender nachfolgender PrüfungPrüfung

Solange bis eine bool‘sche Bedingung erfüllt ist, wird eine Aktion ausgeführt.

Die Bedingung wird (erst) nach der ersten Ausführung der Aktion geprüft heißt auch: Repeat-Schleife


Beispiel: repeat { x = x + 1;} until x > 100

A1 A1repeat{ A1

} until BBf

w

B

5.3.45.3.4 Schleife: Beispiel (abweisende Schleife)Schleife: Beispiel (abweisende Schleife)

Untersuche ob eine gegebene natürliche Zahl Primzahl ist. p > 2 ist Primzahl, falls sie durch kein t mit 1<t<p teilbar ist (p mod t 0)

Idee: wenn p Primzahl, dann ist p ungerade es genügt, nur ungerade t zu untersuchen es genügt, nur solche t zu untersuchen die kleiner p sind,

Algorithmus:p << Tastatur;if ((p>2) and (p mod 2 != 0)) then { t = 3; // initialize t while ((t*t<p) and (p mod t != 0)) { t = t + 2; } // nach Schleife ist t*t >=p oder p mod t == 0 if (t*t>p) then „p ist Primzahl“ >> Bildschirm; else „p ist keine Primzahö“ >> Bildschrim;}else { „p <= 2 oder p gerade“ >> Bildschirm; } // Primzahl ?

5.3.45.3.4 Schleife: Beispiel (Vergleich while Schleife: Beispiel (Vergleich while repeat) repeat)

Sind diese Schleifen im Ergebnis identisch ?while x < 100 repeat{ { x = x + 1; x = x + 1;} } until x > 100

und jetzt ? repeat{

x = x + 1;} until x >= 100

Letzer Versuch: if (x <= 100) then { repeat {

x = x + 1; } until x >= 100}

Welche Lösung ist eleganter ? aber: oft wird eine erstmalige Aktion benötigt, um ein Datum überhaupt

überprüfen zu können.

5.3.45.3.4 Schleife: Beispiel (Vergleich repeat Schleife: Beispiel (Vergleich repeat while) while)

Ausdrucken einer Datei repeat{ x << Datei; if (x != eof) x >>

Drucker;} until x == eof

//endoffile ... das Ganze als while-Schleife ? while (x != eof )

{ x << Datei;

x >> Drucker;}

Noch‘n Versuch: x << Datei;while (x != eof ){

x >> Drucker; x << Datei;}

5.3.45.3.4 Schleife: Beispiel (Schleife mit Zählern)Schleife: Beispiel (Schleife mit Zählern)

Sehr häufig werden Schleifen verwendet, deren Bedingung abhängig von Zählerwerten sind.

Die Zählerwerte werden vor Eintritt in die Schleife initialisiert Die Bedingung prüft den Zählerwert Im Schleifenkörper wird der Zähler erhöht (increase) oder erniedrigt

(decrease) Vorsicht mit: dem Zählertyp, dem Additionswert, der Bedingung

Algorithmus:

// --- Initialisierung ------------------------------s = 0;i = 1; // Initialisierung des Schleifenzählers// --- Schleife (Berechnet Summe 1..n) -------------while ( i <= n ){ s = s + i; i = i + 1; // Erhöhung des Schleifenzählers (oft um 1)}

5.2.45.2.4 Schleife: Die „For“-SchleifeSchleife: Die „For“-Schleife

Da Schleifen mit Zähler sehr häufig auftreten, stellen viele Programmiersprachen ein eigenes sprachliches Mittel dafür zur Verfügung: Die „For“ Schleife

Pseudocode: Beispiel:for var=start_value to end_value for i=1 to 10{ { A; x = x + i; } }

Der Zähler (var) wird pro Schleifendurchlauf implizit um 1 erhöht(Bei manchen Sprachen - z.B. Basic, C, C++ - kann man dies ändern)

Dieser Code ist äquivalent mit folgender Schleife:

i = start_valuewhile i <= end_value{ A; i = i+1;}

5.3.45.3.4 Schleife: Beispiel (Endlosschleife)Schleife: Beispiel (Endlosschleife)

Manchmal macht es Sinn, Schleifen endlos laufen zu lassen: z.B. bei der zyklischen Abprüfung von Systemzuständen (Windows

Event-Queue) manchmal macht das keinen Sinn - passiert aber trotzdem ;-)


Beispiel: while true { „Druckerpapier ist teuer“ >> Drucker;}

A1

A1

while true{ A1

}

B

5.45.4 StrukturierungStrukturierung

Mit Hilfe atomarer Elemente und der Kontrollelemente lassen sich Algorithmen strukturieren. In diesem Kapitel sind einige Begriffe zur Strukturierung erläutert. Insbesondere wird ein weiteres - viertes - Kontrollelement vorgestellt (und auch gleich wieder verworfen)

Inhalt1. Control Flow

2. Strukturierung durch Sprung

3. Strukturiert-iterative Beschreibungsform

4. Strukturierungstypen

5.4.15.4.1 Control FlowControl Flow

Mithilfe der Kontrollelemente können die „atomaren“ Elemente (Anweisungen) strukturiert werden

Die Anordnung der Anweisungen (als atomare Elemente) eines Algorithmus, die bestimmt, in welcher Reihenfolge Dinge geschehen, heißt

control flow (Steuerungsverlauf, Kontrollfluss) des Algorithmus genannt

Manchmal wird auch der Programmablauf oder Kontrollfaden (thread of control, thread), also die tatsächlich abgespulten Schritte und Anweisungen so bezeichnet

5.4.25.4.2 Strukturierung durch SprungStrukturierung durch Sprung

Bei der Vorstellung der Kontrollelemente wurde (aus hinterhältig, didaktischen) Gründen auf ein viertes Element verzichtet:Der Sprung („Goto“-Anweisung)

Die Konstruktion „fahre fort mit Schritt x“ (goto x) stellt einen solchen Sprung (jump) im Steuerungsverlauf dar

Zur Anwendung von goto werden Schritte mit einer Marke (Label) versehen, um das Ziel des Sprunges zu kennzeichnen

Dies ist die elementarste Form, eine Wiederholung oder sonstige Verzweigung im Ablauf auszudrücken

Dadurch erhalten wir die elementar-iterative Beschreibungsform von Algorithmen, die die Strukturierung mit ein-/mehrfacher Auswahl und Schleifen funktional abdeckt.

Beispiel:while x<100 { 1: if x>0 100 goto 2 x = x+1 x = x+1;} goto 1;

2: ...

5.4.25.4.2 Strukturierung durch SprungStrukturierung durch Sprung

Anwendung von Sprüngen ist sehr gefährlich! Sprünge strukturieren komplexe Programm nicht ausreichend - der

Steuerungsverlauf kann verworren und unübersichtlich sein

Um den Steuerungsverlauf auch bei komplexen Algorithmen übersichtlich zu halten, schränkt man die Sprünge ein:

Schleifen der Flussdiagramme sind höchstens ineinander geschachtelt Schleifen überkreuzen sich nicht!

Bei gut strukturierten Algorithmen würde man z. B. nur wieder eine geschlossene Schleife oder einen (vorzeitigen) Sprung bedingt durch die Behandlung desTrivialfalls erlauben

Wir sprechen in diesem Fall von strukturierten Sprüngen im Gegensatz zu freien Sprüngen, die prinzipiell beliebige Ziele haben können

5.4.35.4.3 Strukturiert-iterative BeschreibungsformStrukturiert-iterative Beschreibungsform

Sprünge können die bestimmte „höhere“ Strukturierungsarten funktional abzubilden.Hier gilt auch der Umkehrschluss

In der strukturiert-iterativen Beschreibungsform kommen Sprünge nur noch implizit bei der Ausführung höherer Iterationsstrukturen vor

Dieses sind Fallunterscheidungen (Auswahl) wie if-then-else oder insbesondere Schleifenkonstrukte

Diese bewirken, dass der Programmfluss In einer Auswahl zu genau einer Auswahl geht. in einer Schleife von einer Prüfung zu den Aktionen des Schleifenkörpers

und wieder zurück zur Prüfung geht.

Viele höhere Programmiersprachen (Pascal, C, C++) erlauben jedoch die Verwendung von Sprüngen

Aus Optimierungsgründen (Nähe zur Maschinensprache) Aus Strukturierungsgründen)

5.4.45.4.4 StrukturierungstypenStrukturierungstypen

Beispiel: Schemen einiger Kontrollflüsse

Strukturiert-iterativ Elementar-iterativ Spaghetti-Code

5.55.5 BlockungBlockung

Mit Hilfe der bislang vorgestellten Kontrollelemente lassen sich die atomaren Elemente (Anweisungen) eines Algorithmus‘ zu einem Kontrolfluss strukturieren. Wie wir gesehen haben, kann dieser Kontrollfluss mehr oder weniger „wohlstrukturiert“ sein.In diesem Unterkapitel wird eine Element beschrieben, mit dem Aktionen statisch nochmals zusammengefasst werden können. Diese Zusammenfassung hat auch Einfluss auf das dynamische Verhalten von Verarbeitungsobjekten (Variable).

Inhalt:1. Die Idee

2. Notation

3. Formale Parameter

4. Beispiel: Ein einfacher Block

5. Eigenschaften

6. Beispiel: Seiteneffekte

7. Vorzeitiges Verlassen

8. Goldene Regeln

5.5.15.5.1 Die IdeeDie Idee

Idee:Eine Zusammenfassung von Aktionen bekommt einen Namen und kann durch das Nennen des Namens (Aufruf) aktiviert werden.

In einen Block sollen Daten formal hinein und herausgelangen Ein Block soll eigenen Daten besitzen

Vorteile: Gliederung des Algorithmus‘ durch hierarchische Dekomposition

(„Divide et impera: Teile und herrsche“) Wiederverwendbarkeit durch mehrfachen Aufruf statt durch mehrfaches

notieren. universeller ( Anzahl muss nicht bekannt sein) fehlerunanfälliger

Kapselung unwichtiger Details („information Hiding“) Vorteile bei der Organisation von Programmiertätigkeit durch

Verteilbarkeit der Aufgaben.

5.5.25.5.2 NotationNotation

Ein Block ist die Zusammenfassung von Aktionen und wird wie folgt beschrieben:

Pseudocode:blockname (IN: x1:Type1, … ; OUT: y1:Type2, … ; THROUGH: z1:Type3, … ){ lokal: w1:Type41; w2:Type42; … ; A;}

blockname ist der Name des Blockes xi,yi,zi heißen formale Parameter und sind typisiert

wi heißen lokale Variable

A ist eine Menge von Aktionen.

Blöcke werden in vielen Sprachen als Funktion (nur ein OUT-Parameter) bzw. Prozeduren umgesetzt

blockname

blockname

Flussdiagramm

Struktogramm

5.5.35.5.3 Formale ParameterFormale Parameter

IN-Parameter (Eingabeparameter) sind Parameter, die an den Block übergeben werden

Dazu werden beim Aufruf des Blockes an die Stelle der Eingabeparameter Variable, Literale oder Ausdrücke (Berechnungen) notiert. Diese werden beim Aufruf zu Werten transformiert, die an den entsprechnden Variablen zugewisen werden.(call by value)

OUT-Parameter (Ausgabeparameter) sind Parameter, die aus dem Block durch Zuweisung an Variable zurückgegeben werden.

Dazu werden beim Aufruf des Blockes an die Stelle der Ausgabeparameter Variablen notiert, die nach dem Aufruf die zurückgegeben Werte beinhalten(call-by refernce)

THROUGH-Parameter (Ein-/Ausgabeparameter) sind Parameter die Werte in den Block hinein und hinaus übermitteln.

Eingabe wie bei IN-Parametern (aber: nur Angabe einer Variable) Rückgabe wie bei OUT-Parametern

5.5.45.5.4 Beispiel: Ein einfacher BlockBeispiel: Ein einfacher Block

Ein Block zur Berechnung von Summen (mit Aufrufzähler)summe (IN: value1 : Integer; value2 : Integer; OUT: result : Integer; THROUGH: counter : Integer ){ i : integer: // lokale Variable result = 0; // Initialisierung for i=1 to value2 // ein wenig umständlich result = value1 + 1; counter = counter + 1;}

Aufrufanzahl = 1; // schon erste Summe hat zwei Summanden

initial = 5;

summe(initial, 9, ergebnis, anzahl);summe(ergebnis, 9, ergebnis, anzahl);ergebnis/anzahl >> Bildschirm // Mittelwert

5.5.55.5.5 EigenschaftenEigenschaften

Jeder Block kann über einen Satz lokaler Variable verfügen, die außerhalb des Blockes nicht sichtbar sind

Die Variablenbezeichner können also außerhalb ohne Einfluss auf den Block verwendet werden

Auch die in der Blockdefinition als formale Parameter verwendeten Variablenbezeichner sind nur im Block sichtbar:

Auch sie können außerhalb ohne Einfluss verwendet werden, Aber Vorsicht: die Veränderung von IN und THROUGH-Parametern bewirkt

(oft) eine Veränderung der beim Aufruf verwendeten zugehörigen Parameter (der zugehörigen „gebundenen“ Parameter).

Variable, die in einem Block verwendet aber nicht deklariert werden, werden als „global“ angenommen

Viele Sprachen erlauben die Definition von Blöcken innerhalb von Blöcken

Variablen, die in einem Block nicht deklariert sind, werden im umgebenden Block vermutet.

5.5.65.5.6 Beispiel: SeiteneffektBeispiel: Seiteneffekt

Das (ungewollte) implizite Verändern von „äußeren“ Parametern durch Veränderung „innerer“ Parameter nennt man „Seiteneffekt“

summe (THROUGH: value1 : Integer; value2 : Integer; result : Integer; ){ value1 = value1 + value2; result = value 1;}

Aufrufx = 5; y = 7;summe (x,y,z);„Die Summe von „ >> Bildschirm;x >> Bildschirm;„und“ >> Bildschirm;y >> Bildschirm;„ ist „ >> Bildschirm;z >> Bildschirm;

Die Summe von12und7Ist12

5.5.75.5.7 Vorzeitiges VerlassenVorzeitiges Verlassen

Manchmal ist es sinnvoll, die Abarbeitung eines Blockes vorzeitig zu beenden

Dies wird oft im Fehlerfall gemacht, wenn eine Weiterbearbeitung nicht mehr sinnvoll erscheint - z.B. nach einer negativen Überprüfung der Eingabeparameter


Beispiel: wurzel(IN: argument:real; OUT: result:real){ if (x<0) return; // return already here else result = sqr(argument);}

Block Return;Block

5.5.85.5.8 Goldene RegelnGoldene Regeln

Namen so lokal wie möglich deklarieren Möglichst keine globalen Variablen verwenden

Wenn doch: Ganz wenige - nur eine (z.B. strukturiert) Auffällig kennzeichnen: z.B. global_error_handle

Nach Möglichkeit „call by value“ verwenden Wird nicht von allen Programmiersprachen unterstützt Probleme bei der Rückgabe umfangreicher Daten (wg. Umkopieren)

Blöcke sind so zu wählen dass: Der innere Zusammenhang stark ist Der äußere Zusammenhang schwach ist (minimale Schnittstellen, keine

Datenteilung , z.B. durch globale Variable)

5.65.6 Iteration und RekursionIteration und Rekursion

Im Bereich der Datenstrukturen haben wir es oft mit rekursiven Strukturen z.B. Bäumen zu tun. Auch in der Mathematik sind rekursive Definition weit verbreitet.und finden über zugehörige Algorithmen Einzug in die Informatik.Das Konzept der Rekursion wird in der Informatik allerdings teilweise mit Skepsis umgesetzt, führt es doch, in ungeeigneten Fällen, zu inakzeptablen Laufzeiten. Hinzu kommt, dass einige Programmier-spachen (z.B. FORTRAN) Rekursion nicht unterstützen.In diesem Unterkapitel soll auf die Möglichkeiten der Verwendung von Rekursion bzw. Iteration eingegangen werden

Inhalt1. Definition

2. Beispiele

3. Aufrufverwaltung

4. Wo nicht

5. Wo nicht und wo

5.6.15.6.1 Definition: RekursionDefinition: Rekursion

Ein Objekt heißt rekursiv, wenn es sich selbst als Teil enthält oder mit Hilfe von sich selbst definiert ist.

Wesentlich ist die Möglichkeit, unendliche Mengen von Objekten durch eine endliche Aussage zu definieren.

Bsp.: Definition natürlicher Zahlen: 0 sei eine natürliche Zahl Der Nachfolger (n+1) einer natürlichen Zahl ist wieder eine natürliche Zahl

Ein Algorithmus heißt rekursiv, wenn er sich selbst als einen seiner Aktionen (Verarbeitungsschritten) enthält.

In der Regel enthält er sich mit „verkleinerter“ Aufgabenstellung. Damit er terminiert, muss er einen Zweig beinhalten, der einen (den)

elementaren Wert nicht rekursiv bestimmt. (den Basisfall) Objekte (Algorithmen), die andere Objekte (Algorithmen) enthalten, die

wiederum die ursprünglichen Objekte (Algorithmen) enthalten, heißen indirekt rekursiv

5.6.25.6.2 Beispiel: Hilbert-KurvenBeispiel: Hilbert-Kurven

D.Hilbert: Über stetige Abbildungen einer Linie auf ein Flächenstück, Math. Annalen, 1891:

Hilbert (IN: s,t,v : integer) {// s: Größe, t: Rekursionstiefe, v:+-1 Orientierung if (t>0) then { turnleft(v*90); // 90 Grad links hilbert(s/2,t-1,-v); // rekursiver Aufruf forward(s); // zeichne Strecke s turnright(v*90); // 90 Grad rechts hilbert(s/2,t-1,v); // rekursiver Aufruf forward(s); // zeichne Strecke s hilbert(s/2,t-1,v); // rekursiver Aufruf turnright(v*90); // 90 Grad rechts forward(s); // zeichne Strecke s hilbert(s/2,t-1,-v); // rekursiver Aufruf turnleft(v*90); // 90 Grad links }}

t = 1

t = 2

5.6.25.6.2 Beispiel: FakultätBeispiel: Fakultät

Mathematisch rekursive Definition: 1 n = 0

n ! = n x (n - 1) ! n > 0

Algorithmisch rekursive Definition:fakultaet (IN: n:integer, OUT: result:integer){ if (n == 0) then result = 1; else { fakultaet (n-1, ergebnis); ergebnis = ergebnis x n; }}

5.6.35.6.3 AufrufverwaltungAufrufverwaltung

Eine Aktivierung der Tiefe n wird erst verlassen, wenn die von ihr erzeugte Aktivierung der Tiefe n+1 schon verlassen wurde Verwaltung der Aktivierung als Stapel (Stack)

fakultaet(3,x)

fakultaet(2,x)

fakultaet(1,x)

fakultaet(0,x) result=1

result=1

result=2

result=6

5.6.45.6.4 Wo nicht: Modulo-BerechnungWo nicht: Modulo-Berechnung

Alle Grundrechenarten - und vergleichbar einfache mathematische Operationen - lassen sich mit Hilfe sog. „Primitiv Rekursiver Funktionen“ beschreiben (siehe Beispiel. „Algorithmenbeweis“)

a falls a < bmod(a,b) =

mod(a-b,b) falls a b

In gängiger mathematischer Notation könnte ein Verfahren zur Berechnung der Modulus-Funktion a mod b wie folgt aussehen:

modulo (IN a,b: integer, OUT result: integer){ if (a<b) result = a; else modulo (a-b,b,result);}

Offenbar einfacher ist: result = a - (a/b) x b

5.6.45.6.4 Wo nicht: Fibonacci-ZahlenWo nicht: Fibonacci-Zahlen

Fibonacci definiert im 13.Jahrhundert eine Zahlenfolge mit der die Verhältnisse des „goldenen Schnitts“ ebenso beschrieben werden können, wie die Populationsentwicklung in einem Kaninchenstall:

0 n = 0fib(n) = 1 n = 1

fib(n-2)+fib(n-1) n > 1 fib(IN: n:integer, OUT: result:integer)

{ r,s : integer; if (n==0) then result = 0 else if (n==1) then result = 1 else { fib(n-1,r); fib(n-2,s); result = r + s; }}

0112358

1321345589

144233

...


fib(IN: n:integer, OUT: result:integer){... fib(n-1,r); fib(n-2,s); result = r + s; ...}

n Aufrufe Rechenzeit (1 Aufruf = 1 nsec)0 1 n Zeit1 1 10 0,18 sec2 3 20 22 sec3 5 50 41 sec4 9 100 36000 Jahre5 156 25

Die Anzahl der Aufrufe verhält sich offenbar selbst ähnlichder Fibonacci-Reihe:

Anzahl (n) = 2 x fib(n+1) - 1

Anstieg ist praktisch exponentiell also nicht verwendbar

0112358

1321345589

144233

...


Idee: Merken von zwei Folgewerten in Variablen und Aufsummieren in Schleife, wobei die Werte immer umgespeichert werden:

fib (IN: n:integer, OUT: result:integer){ a,b,z : integer; a = 0; b = 1; // fib0, fib1 while (n > 0) do { z = a + b; // Berechnung der nächsten fib a = b; b = z; // Umspeichern der fibs n = n - 1; // dicrease n } result = a; // das Resultat steht in a}

Anzahl (n) = n Zeit (n=100) = 1 sec (anstatt 36000 Jahre !)

0112358

1321345589

144233

...

5.6.55.6.5 Wo nicht und wo?Wo nicht und wo?

Man sollte überall dort auf Rekursion verzichten, wo es eine offensichtliche Lösung mit Iteration gibt.

Jeder rekursive Algorithmus lässt sich in eine iterative Form umwandeln(z.B. über explizites Ausformulieren einer Stackverwaltung)

Es gibt allerdings einige Fälle, in denen Rekursion angewandt werden sollte:

Rekursion ist überall dort sinnvoll anwendbar, wo sich ein Problem in mehrere (oft: zwei) nicht überlappende Teilprobleme aufspalten lässt und sich die Teilprobleme leicht rekombinieren lassen.

Rekursion sollte dort verwendet werden, wo die zugrunde liegenden Datenstrukturen selbst rekursiver Art sind (z.B.: Bäume)

Für einige Probleme gibt es keine direkte Vorschrift zur Berechnung. Diese können oft nur durch „Trial and Error“ gelöst werden. Oft lassen sich diese Versuche (Trials) durch Untersuchung eines Teilproblems natürlich in rekursiver Form darstellen.Dieses Vorgehen nennt man „Backtracking“

5.6.65.6.6 Beispiel: BacktrackingBeispiel: Backtracking

Weg des Springers Gegeben sei ein n x n Spielbrett (z.B. n=8). Ein Springer - der nach den

Schachregeln bewegt werden darf - wird auf das Feld mit der Anfangskoordinate (x0,y0) gestellt (z.B. (1,1)).

Zu finden ist ein Weg des Springers, der genau einmal über jedes der Felder des Schachbrettes führt.

5.6.65.6.6 Beispiel: BacktrackingBeispiel: Backtracking

Ansatz eines Algorithmus (in unvollständiger Notation)track (IN: kandidat, OUT: erfolgreich){ trage_ein(kandidat); // erst mal eintragen erfolgreich = false; // Initialisierung if (fertig) erfolgreich = true; // Abbruchfall

else // weitersuchen

{ repeat { wähleKandidat(neukandidat); // wie auch immer if (neukandidat) then // es geht weiter track (neukandidat, erfolgreich) // Rekusion else // Sackgasse ! trage_aus (kandidat); // wieder austragen

} until (erfolgreich) or (not neukandidat) }}

5.75.7 BerechenbarkeitBerechenbarkeit

Wir haben den Begriff und die Elemente eines Algorithmus vorgestellt und Algorithmen zur Lösung von Problemen verwendet.In diesem Unterkapitel werden nun einige Fragen zur Anwendbar- und Sinnhaftigkeit von Algorithmen gestellt und beantwortet.

Inhalt:1. Einige Fragen

2. Das Entscheidungsproblem

3. Die Turing-Maschine

4. Berechenbarkeit

5. Rekursive Funktionen

6. Church‘sche These

H. Ernst:“Grundlagen und Konzepte der Informatik“,Vieweg-Verlag,2000

5.7.15.7.1 Einige FragenEinige Fragen

1. Kann jedes Problem durch einen Algorithmus beschrieben werden, d.h. prinzipiell - bei genügender Sorgfalt - gelöst werden ?

2. Kann jeder Algorithmus in ein Programm übertragen werden ? Welchen Anforderungen muss eine Programmiersprache genügen, damit

jeder Algorithmus damit formuliert werden kann ?

3. Ist ein Computer grundsätzlich in der Lage, einen bekannten, als Programm formulierten Algorithmus auszuführen ?

4. Ist ein solcher Computer formalisierbar ? Wie sieht ein solches abstraktes Model aus ? Gibt es genau ein Model oder mehrere ? Sind diese Modelle äquivalent ? Gibt es andere Modelle oder Beschreibungsformen, die diesem formalisierten

Computermodell entsprechen ?

Frage 1 und Frage 4 sind wesentlich für den Begriff der Berechenbarkeit, Frage 2 wird im anschließenden Kapitel behandelt, Frage 4 ist Gegenstand der Vorlesung „Compilerbau“

5.7.25.7.2 Das EntscheidungsproblemDas Entscheidungsproblem

Bis weit ins 20ste Jahrhundert war die Mehrzahl der Mathematiker (insb. David Hilbert: 1862-1942) der Ansicht, dass man von jeder Aussage algorithmisch beweisen könne, ob sie wahr oder falsch sein.

Anders ausgedrückt: Es sei entscheidbar, ob ein Problem lösbar oder unlösbar ist.

Die Frage, ob dies entscheibar ist oder nicht ging als Entscheidungs-problem in die Geschichte der Mathematik (und Informatik) ein.

Kurt Gödel wies in seinem Unvollständigkeits-Theorem 1931 nach, dass alle widerspruchsfreien axiomatischen Formulierungen der Zahlentheorie unentscheidbare Aussagen enthalten.

damit wurde insb. belegt, dass streng algorithmisch arbeitende Computer prinzipiell nicht jedes Problem lösen können.

Auf fast schon philosophischer Ebene wurde damit auch belegt, dass Wahrheit eine andere Qualität als Beweisbarkeit besitzt.

nicht alle „wahren“ Aussagen können auch bewiesen werden.

5.7.35.7.3 Die Turing-Maschine: DefinitionDie Turing-Maschine: Definition

Als abstraktes Modell eines Computers beschrieb Alan Turing (1912-1954) 1963 - also noch vor der Erfindung des Digitalrechners - eine nach ihm benannte abstrakte Maschine

Formal kann eine Turing-Maschine wie folgt beschrieben werden: Alphabet: A = {a0, ... , an}, der Zeichenvorrat der Turing-Maschine, wobei

a0 das Leerzeichen ("blank") darstellt (Oft: a1=0, a2=1)

Bandinschrift: B: Z A eine Zuordnung, die jeder Stelle des rechtsseitig unendlichen Bandes ein Zeichen zuordnet. Dabei wird festgesetzt, dass B(k) = a0 für alle bis auf endlich viele .

Kopfposition: k Z Zustände: eine endliche Menge von Maschinenzuständen.Q = {q0, ..., qm}

Darunter sind q0, der Anfangszustand und H Q , die Menge der

Haltezustände, ausgezeichnet. Turing-Tabelle:

eine Übergangsrelation: d : A Q A Q {r, l, n}, das jedem (gelesenen) Zeichen in Abhängigkeit eines Zustandes ein neues Zeichen, einen Folgezustand und eine Aktion (r,l,n} zuordnet

5.7.35.7.3 Die Turing-Maschine: ProgrammDie Turing-Maschine: Programm

Die Aktion: "aj" das Überschreiben des unter dem Kopf befindlichen

Zeichens durch aj,

r: das Verschieben des Kopfes nach rechts l: das Verschieben des Kopfes nach links. n: das Nicht-Verschieben des Kopfes

a1 a2 a3 a4 ... a6

falls die Maschineim Zustand

das unter dem Kopfgelesene Zeichen

so ist dieAktion

der neueZustand

q q‘aj, r oder lak

falls die Maschineim Zustand

das unter dem Kopfgelesene Zeichen

so ist dieAktion

der neueZustand

5.7.35.7.3 Die Turing-Maschine: Beispiel Die Turing-Maschine: Beispiel

Das „Busy beaver“-Problem:Wieviele „1“-en kann ein terminierendes Touring-Programm auf einem leeren Band mit einer vorgegebenen Anzahl von Zuständen maximal erzeugen.

Z1Z1Z2Z2Z3Z3Z4Z4Z5Z5

0101010101

llrrlrlrrr

Z2Z1Z3Z2Z1Z4Z1Z5SZ3

Fur |Z|=54096 „1“enJ.BuntrockH.Marxen(1989)

aktuell: 4098

5.7.45.7.4 Definition: BerechenbarkeitDefinition: Berechenbarkeit

Ein Problem ist genau dann algorithisch lösbar, wenn es durch eine Turing-Maschine darstellbar ist.

Eine Funktion f(x) heißt berechenbar, genau dann wenn es einen Algorithmus (eine Turing-Maschine) gibt, der bei gegebenem x das Ergebnis f(x) liefert

Ein Computer ist äquivalent zu einer universellen Turing-Maschine. d.h. ein Computer ist äquivalent zu einer Turing-Maschine, die jede

andere Turing-Maschine simulieren kann. Zur Simulation einer beliebigen Turing-Maschine muss auf dem

Eingabeband eine Beschreibung der zu simulierenden Maschine codiert werden und außerdem deren Eingabeband gespeichert sein.

Die Menge verschiedener universeller Turing-Maschinen ist abzählbar - denn das Band ist binär codiert, jede Kombination lässt sich auf eine natürliche Zahl abbilden. Die Menge aller Funktionen f(x) ist überabzählbar (z.B. Funktionen die auf eine reelle Zahl abbilden) Es gibt (unendlich viele) nicht berechenbare Funktionen

5.7.55.7.5 Beispiel: Das HalteproblemBeispiel: Das Halteproblem

Nicht berechenbare Probleme sind also keine Probleme, die noch nicht gelöst sind, sondern solche, für die es keine Lösung gibt.Das wohl bekannteste dieser Probleme ist das Halteproblem:Es gibt kein Programm, das für ein beliebiges gegebenes Programm, und für beliebige gegebene Eingabeparameter entscheidet, ob das gegebene Programm anhält.

Beweis: Geg. Programm P mit Quelltext(P) als EingabeAnnahme: Es gibt ein solches

Programm (Test)

Test(P)

ja nein

P stopptmit Py n

Test1(P)

stoppe

Test = jay n

Test(P)

Test(Test1)=ja Test1(Test1) läuft endlos Test(Test1)=nein Widerspruch !

5.7.65.7.6 Rekursive FunktionenRekursive Funktionen

Es gibt innerhalb der mathematischen Funktionen zwei Unterklassen: primitiv-rekursive Funktionen:

jede primitiv-rekursive Funktion ist berechenbar es gibt berechenbare Funktionen, die nicht primitiv-rekursiv sind primitiv-rekursive Funktionen lassen sich genau mit Algorithmen ohne

Schleifenkonstrukte (aber mit Blockung) darstellen.

-rekursive Funktionen jede -rekursive Funktion ist berechenbar es gibt berechenbare Funktionen, die nicht -rekursiv sind -rekursive Funktionen lassen sich mit Algorithmen mit Schleifenkonstrukte

(und Blockung) darstellen.

Es gilt folgende Beziehung innerhalb von Funktionen:

-rekursive Funktionen

primitiv-rekursive Funktionen

berechenbare Funktionen

5.7.65.7.6 Church‘sche TheseChurch‘sche These

Wir haben bislang verschiedene Äquivalenzen gefunden: Primitiv und -rekursive Funktionen sind Teilmengen von berechenbaren

Funktionen. Eine Funktion ist genau dann berechenbar, wenn es eine Turing-

Maschine zu deren Berechnung gibt,. Die Darstellung mit Hilfe einer Turing-Maschine ist äquivalent mit der

einer universellen Turingmaschinm, die wiederum eine Abstraktion eines Computers darstellt

Dies legt die Formulierung einer der Church‘schen These nahe:Alle im intuitiven Sinn vernünftigen Formalisierungen von Problemlösungen sind äquivalent

Wenn ein Problem nicht durch eine Turing-Maschine gelöst werden kann, so ist es algorithmisch überhaupt nicht lösbar

Da Begriffe wie „intuitiv“ und „vernünftig“ nicht definiert sind, ist die Church‘sche These nicht beweisbar.

5.85.8 KorrektheitKorrektheit

Wir haben diskutiert, ob man jede (mathematische) Funktion berechnen kann und haben dabei die Äquivalenz eines Algorithmus‘ mit berechenbaren Funktionen gesehen.In diesem Unterkapitel geht es nicht mehr nur darum, ob eine Funktion berechenbar ist, bzw. ein Algorithmus für deren Berechnung existiert, sondern ob der gegebene Algorithmus tatsächlich das macht, was er machen soll

Inhalt1. Ansatz

2. Definition

3. Logik zur Verifikation (C.A.R. Hoare)

4. Regeln

5. Terminierung

6. Beispiele

7. Beweis des Euklid‘schen Algorithmus

8. Kritische Anmerkungen

U.Kastens:“Modellierung“, Vorlesung WS‘00/‘01, Uni Paderborn

5.8.15.8.1 AnsatzAnsatz

Wir haben zu Beginn des Kapitels den Begriff der Korrektheit definiert: partielle Korrektheit:

Jedes berechnete Ergebnis genügt der Ausgabespezifikation, sofern die Eingaben der Eingabespezifikation genügt haben

Terminierung:Der Algorithmus hält nach endlich vielen Schritten mit einem Ergebnis an, sofern die Eingaben der Eingabespezifikation genügt haben

Zum Beweis der Korrektheit gehen wir also von der Eingabespezifi-kation aus und versuchen, mit den Aktionen (Statements) des Algorithmus die Ausgabespezifikation abzuleiten.

Die Eingabespezifikation wird dabei als Vorbedingung P(V) oder {P} und die Ausgabespezifikation Q(V) oder {Q} als Nachbedingung mathematisch formuliert

Über die Aktionen des Algorithmus wird die Vorbedingung über Zusicherungen Zi(V) zur Nachbedingung abgeleitet

Also: P(V) Z1(V) ... Zn(V) Q(V)

5.8.25.8.2 Definition: KorrektheitDefinition: Korrektheit

Beispiel: Lösung der quadratischen Gleichungqugl (IN: p,q: real, OUT x1,x2:real)// Vorbedingung: (p*p)/4 > q// Nachbedingung: x1 = (-b + sqr(p*p/4-q)) / (2*a) // x2 = (-b - sqr(p*p/4-q)) / (2*a){ w : real; w = sqr(p*p/4 - q); x1 = -p/2 + w; x2 = -p/2 - w:}

Ein Algorithmus heißt korrekt bezüglich seiner Spezifikation, wenn für jeden Aufruf, der die Vorbedingung erfüllt, nach dem Aufruf des Algorithmus‘ die Nachbedingung erfüllt ist (und er terminiert)

Achtung:Die Vorbedingung ist vom Aufrufer zu erfüllen, die Nachbedingung ist durch den Algorithmus (bzw. den Implementierer) zu erfüllen.

5.8.35.8.3 C.A.R. Hoare: Logik zur VerifikationC.A.R. Hoare: Logik zur Verifikation

C.A.R. Hoare formulierte 1969 ein Kalkül zum Beweis von Aussagen über Algorithmen und Programme

damit sind - im Gegensatz zum Testes - statische Aussagen über Zustände des Algorithmus ( Werte der Variablen) möglich. Diese Aussagen gelten für alle Ausführungen des Algorithmus

Durch logisch Schlüsse über die Elemente eines Algorithmus kann gezeigt werden, dass

an einer bestimmten Stelle im Algorithmus eine bestimmte Aussage gilt. eine Aussage an jeder Stelle eines Teils des Algorithmus invariant gilt Schleifen terminieren.

Also: ein Algorithmus aus jeder zulässigen Eingabe die geforderte Ausgabe

berechnet

5.8.35.8.3 C.A.R. Hoare: BeispielC.A.R. Hoare: Beispiel

min (IN: a,b: integer, OUT min:integer)// Vorbedingung: a,b > 0 (nicht unbedingt notwendig)// Nachbedingung: (min=a min=b) (mina) (minb){ if a<b then { // Z1: a<b min = a; // Z2: a<b min=a Z3: min=a mina minb } else { // Z4: ba min = b; // Z5: ba min=b Z6: min=b minb mina } // Z7: (min=aminaminb) (min=bminbmina) // Z8: (min=a min=b) (mina) (minb) = Q}

Damit ist aus der Vorbedingung P mit Hilfe der Anweisung in min() die Nachbedingung Q formal abgeleitet worden.

5.8.35.8.3 C.A.R. Hoare: VorgehenC.A.R. Hoare: Vorgehen

Aussagen über den Algorithmenzustand, über Werte von Variablen werden in den Algorithmus eingefügt:

{ P } A1 { Q } A2 { R } bedeutet: Q gilt immer zwischen der Ausführung von A1 und der Ausführung

von A2 Beispiel: { i + 1 0} i := i + 1; { i 0 } a [i] := k; {...}

Zur Verifikation eines Algorithmus muss für jede Anweisung S ein Nachweis geführt werden:

{ Vorbedingung P } S { Nachbedingung Q } nachweisen: Wenn vor der Ausführung des Schrittes S die P gilt, dann gilt Q

nach der Ausführung von S, falls S terminiert. Beispiel: { i + 10} i := i + 1; {i 0} mit Zuweisungsregel nachweisen

Die Aussagen werden entsprechend der Struktur von S verknüpft. Für jede Anweisungsform wird eine spezielle Schlussregel angewandt.

Die Spezifikation liefert Vorbedingung und Nachbedingung des gesamten Algorithmus:

5.8.45.8.4 Regel: ZuweisungRegel: Zuweisung

Die Zuweisung x = expr wertet den Ausdruck expr aus und weist das Ergebnis der Variablen x zu.Es gilt dann:

{P[x/expr]} x := expr {P}oder

{P(x)} x = f(x) {P(f--1(x))}

P[x/expr] steht für die Substitution von x durch expr in P Die Nachbedingung P erhält man dadurch, dass man jedes Vorkommen von

expr in der Vorbedingung durch x (die linke Seite der Zuweisung) ersetzt Wenn man also zeigen will, dass nach der Zuweisung eine Aussage P für x

gilt, muss man zeigen, dass vor der Zuweisung dieselbe Aussage P für expr gilt.

Beispiele: {a>0} x = a {x>0} {i+1>0} i=Succ(i) {i>0}: f(x)=Succ, f-1(x)=Pred(x), {P(Pred(x+1)}=(i+1-1>0) {i+1>0} i = i+1 {i>0}

5.8.45.8.4 Regel: Zuweisung - BeispieleRegel: Zuweisung - Beispiele

{P[x/expr]} x := expr {P} alle Aussagen der Vorbed. für expr, gelten für x in der Nachbedingung

Aussagen der Vorb. über x gelten in der Nachbedingung nicht mehr Die Nachbedingung P erhält man dadurch, dass man jedes Vorkommen von

expr in der Vorbedingung durch x ersetzt ggf ist die Vorbedingung so umzuformen, dass expr explizit Teil der Vorbedingung

ist (auf der linken Seite einer Aussage)

1. {y=5} x=y {x=5}2. {a>0 x>7} x=a {x>0 x>7} falsch !

3. {a>0 z>0} x=a {x>0 z>0} z>0 ist nicht betroffen

4. {i+1>0} i=i+1 {i>0}

5. {i0} {i+1>0} i=i+1 {i>0} passend umformen

6. {i=2} {i+1=3} i=i+1 {i=3} passend umformen

7. {i=2} {i+1=3} i=i+1 {i=3} passend umformen

8. {z=5} x=1 {z=5 x=1} z nicht betroffen, x neu

5.8.45.8.4 Regel: KonsequenzRegel: Konsequenz

Abschwächung der Nachbedingungwenn gilt und dann gilt auch

{P} S {R} {R} {Q} {P} S {Q}

Beispiel

{a+b>0} S {x>0} {x>0} {X0} {a+b>0} S {X0}

Verschärfung der Vorbedingung wenn gilt und dann gilt auch

{P} {R] {R} S {Q} {P} S {Q} Beispiel (Notation: Im Algorithmus können Implikationen in

Ausführungsrichtung eingefügt werden)

{a+b>0}x = a+b;{x>0} {2*x 0}y = 2 * x{y0}

5.8.45.8.4 Regel: SequenzRegel: Sequenz

Folgendes Schema lässt sich auf eine Sequenz von Aktionen (Statements) anwenden:

wenn gilt und dann gilt auch

{P} S {R} {R} S2 {Q} {P} S1,S2 {Q}

Beispiel:{x>0 y>0} {x>0 y>0}

a = x; a = x;

{a>0 y>0} {a>0 y>0} {a>0 y>0}

b = y; b = y;

{a>0 b>0} {a>0 b>0}

Bei trivialen Ableitungen können die Zwischenschritte (Zusicherungen, Aussagen) auch weggelassen werden:

{x>0 y>0}

a = x; b = y;

{a>0 b>0}

5.8.45.8.4 Regel: Bedingte AnweisungRegel: Bedingte Anweisung

Schema:wenn gilt und dann gilt auch

{P B} S {Q} {PB} {Q} {P} if B then S {Q}

Um die Nachbedingung einer bedingten Anweisung zu beweisen, muss1. aus der Vorbedingung und der Anweisungs-Bedingung über die Anweisung

die Nachbedingung nachgewiesen werden

2. aus der Vorbedingung und der Negation der Anweisung die Nachbedingung direkt folgen

Beispiel: Gegeben: if a<0 then a = -a Beweise, dass der Algorithmus a0 für alle a liefert:

1. {P a<0} {P -a>0} a=-a {P a>0} {P a 0}

2. {P (a<0)} {P a 0}

dann gilt auch

{P} if a<0 then a=-a {P a 0}

5.8.45.8.4 Regel: Bedingte Anweisung - NotationRegel: Bedingte Anweisung - Notation

Beispiel: Gegeben: if a<0 then a = -a Beweise, dass der Algorithmus a0 für alle a liefert:

1. {P a<0} {P -a>0} a=-a {P a>0} {P a 0}

2. {P (a<0)} {P a 0}

dann gilt auch

{P} if a<0 then a=-a {P a 0}

Notation:{P}if a<0 then {P a<0} {P -a>0} a = -a {P a>0} {P a 0}// leere Alternative: {P (a<0)} {P a 0}{P a 0}

5.8.45.8.4 Regel: Einfache AlternativeRegel: Einfache Alternative

Schema:wenn gilt und dann gilt auch

{P B} S1 {Q} {PB} Ss {Q} {P} if B then S1 else S2 {Q}

Aus der gemeinsamen Vorbedingung P muss für beide Alternativen dieselbe Nachbedingung Q nachweisbar sein

Beispiel: Gegeben: a>0, b>0, ab und ein Algorithmus (s.u) Beweise, dass nach den Operationen immer noch gilt: a>o, b>0

{a>0 b>0 ab}if a>b then {a>0 b>0 ab a>b} {b>0 a-b>0} a = a-b; {b>0 a>0}else {a>0 b>0 ab ab} {a>0 b-a>0} b = b-a; {a>0 b>0}{a>0 b>0}

5.8.45.8.4 Regel: SchleifeRegel: Schleife

Schema:wenn gilt dann gilt auch

{P I B} S {P} {I} while B { S } {I B Q} // I = Schleifeninvariante

Schleifeninvarianten sind Zusicherungen in Schleifen, die beim Durchlaufen des Schleifenkörpers erhalten bleiben. Es gelte

P Zusicherung über Variable vor Schleifeneintritt Q Zusicherung über Variable nach Schleifenende I Schleifeninvariante B Wiederholbedingung der Schleife S Statements (Aktionen) im Schleifenkörper

Die Nachbedingung einer Schleife ist über die Invariante nachgewiesen nachzuweisen, wenn gilt:

P I die Invariante muss vor Schleifeneintritt wahr sein (I B) I die Invariante darf in Schleife nicht verändert werden (I B) Q die Nachbedingung muss sich nach Verlassen der

Schleife aus der Invariante nachweisen lassen

5.8.45.8.4 Regel: Schleife - SchemaRegel: Schleife - Schema

Das Schema der Gültigkeit von Aussagen sei anhand des Flussdiagramms für Schleifen verdeutlicht:

B ?

S

P

I

I B

I

fw

I B Q(V)

Um Q(V) zu beweisen, mussman also I(V) so wählen, dassQ(V) aus I(V) B(V) ableitbarist

5.8.45.8.4 Regel: Schleife - BeispielRegel: Schleife - Beispiel

Algorithmus zum Potenzieren// Vorbedingung: y 0 (positive Exponenten)// Nachbedingung: z = ab

x=a, y=b, z=1;{ x=a, y=b, z=1; y 0}{INV: z * xy = ab y0}while y>0{ { INV y>0 z*x(y-1)+1=ab (y-1)+1 > 0 } y = y-1; { z*xy+1=ab y+1>0 } { ((z*x)/x)*xy+1 = ab y 0 } z = z*x; { z/x*xy+1 = ab y 0 } { z * xy = ab y 0 INV }}{ INV B z * xy = ab y0 y0 z*x0 = z = ab Q }

B ?

S

P

I

I B

I

fw

I B Q

5.8.45.8.4 Regel: Schleife - SchleifeninvarianteRegel: Schleife - Schleifeninvariante

Das Finden der „richtigen“ Invariante kann ganz schön kniffelig sein: Ein paar „Tips“: Gegeben: Vorbedingung y 0

Zu beweisen: Nachbedingung z = ab

Wenn die Nachbedingung nicht gegeben ist, versuche die Semantik des Algorithmus‘ zu verstehen, z.B. anhand von Beispielen.

Betrachte die Anweisungen in der Schleife:Meist wird etwas vergrößert (z.B. die Variable der Abbruchbedingung), während etwas anderes verkleinert wird - oder umgekehrt. Kombiniere diese: z * xy

Setze Ein- und Ausgabevariablen in Bezug zueinander z * xy = ab

Beachte, dass aus INV und B(V) Q(V) ableitbar sein soll Das bedeutet, dass man die In variante aus der Nachbedingung konstruieren kann, indem man die negierte Bedingung mit berücksichtigt

z * xy = ab y=0 z*x0 = z = ab Q

5.8.55.8.5 TerminierungTerminierung

Die Terminierung einer Schleife muss separat nachgewiesen werden Beweis der Terminierung

1. Gib einen ganzzahligen Ausdruck E an über Variablen, die in der Schleife vorkommen und zeige, dass E bei jeder Iteration durch S verkleinert wird

2. Zeige, dass E nach unten begrenzt ist, z.B. dass 0E eine Invariante der Schleife ist

3. Zeige, dass die Grenze auch erreicht wird. E kann nauch monoton vergrößert und nach oben begrenztb sein

Beweis der Nicht-Terminierung: Beweise,1. dass RB eine Invarianz der Schleife ist (also R in die Schleife geht) und

dass es eine Variablenbelegung gibt, so dass RB vor der Schleife gilt

2. dass R einen speziellen Zustand charakterisiert, in dem die Schleife nicht anhält

Es gint Schleifen, für die man nicht entscheiden kann, ob sie für jede Vorbedingung terminieren.

5.8.55.8.5 Terminierung - BeispieleTerminierung - Beispiele

{ a>0 b>0 }while ab { while a>b { a=a-b } while a<b { b=b-a }} // terminiert

{ a>0 b>0 }while ab { while ab { a=a-b } while a<b { b=b-a }} // terminiert nicht immer (a = 2*b)

{ n n>1 }while n>1 if n gerade then n = n/2 else n=3*n+1 // Terminierung unbewiesen

5.8.65.8.6 Beispiel: Multipl. durch fortgesetze AdditionBeispiel: Multipl. durch fortgesetze Addition

// Vorbedingung P: a0 b0, Beh.: Nachbedingung Q: z = a*b x = a; y = b; z = 0; { x0 b0 z=0 }// Auch hier: Die Summe von x*y+z bleibt konstant a*b { INV: z+xy = ab, x,y0 } while x > 0 {

{ INV x>0 } { (z+y)-y+xy = ab, x>0,y0 } z = z + y;

{ z-y+xy = ab, x>0,y0 } { z-y+((x-1)+1)y = ab, (x-1)+1>0,y0 } x = x - 1;

{ z-y+(x+1)y = ab, x+1>0,y0 } { z-y+xy+y = z+xy = ab, x,y0 } INV

}

{ INV B = (z+x*y=a*b) (x=0) z+0*y=a*b Q }

B ?

S

P

I

I B

I

fw

I B Q

5.8.65.8.6 Beispiel: Die ägyptische BauernmultiplikationBeispiel: Die ägyptische Bauernmultiplikation

// Vorbedingung P: a0 b0, Beh.: Nachbedingung Q: z = a*bx = a; y = b; z = 0; { x,y0 z=0 x=a y=b }// Schleife verdoppelt x und halbiert y: Invariante: INV INV = { z+x*y = a*b x,y0 }while x > 0 { { INV x>0 } if (odd(x) then { (z+y)-y+x*y = a*b) x>0,y0 } z = z+y; { odd(x) z-y+x*y = a*b x>0,y0 } // leere Anweisung { even(x) z+x*y = a*b x>0,y0 } { odd(x) z-(2y/2)+x*(2y/2) = a*b x>0,(2y/2)0 } even(x) z+x*(2y/2) = a*b x>0,(2y/2)0 } y = y * 2; { odd(x) z-y/2+x*y/2 = a*b x>0,y/20 even(x) z+x*y/2 = a*b x>0,y/20 } { odd(x) z-y/2+(2(x div 2)+1)*y/2 = a*b (2(x div 2)+1)>0,y0 even(x) z+(2(x div 2))*y/2 = a*b 2(x div 2) >0,y0 }

x = x div 2; // div = Ganzzahldivision { odd(2x+1) z-y/2+(2x+1)*y/2 = a*b (2x+1)>0,y/20 even(2x) z+ 2x *y/2 = a*b 2x >0,y/20 } { z-(y - y(2x+1))/2 = z-(y-2xy-y)/2 = z-(-2xy/2)= z+xy = a*b z + 2x * (y*2) = z+xy = a*b } INV } { INV B = (z+x*y=a*b) (x=0) z+0*y=a*b Q }

5.8.65.8.6 Beispiel: Euklid‘scher Algorithmus (ggT)Beispiel: Euklid‘scher Algorithmus (ggT)

// Vorbedingung P: a>0b0, Beh.: Nachbed. Q: x=ggT(a,b)x = a; y = b; // Z1: x>0b0// Die Summe von x*y+z bleibt konstant a*b{ INV: (ggT(x,y) = ggT(a,b)) (x>0y0) }while y > 0 { { INV (y>0) } r = x mod y; // r ist Rest aus x/y x = y; y = r; { ggT(y,x mod y) = ggT(x,y) = ggT(a,b) } { INV }}// I(A)B(V) = (ggT(x,y) = ggT(a,b)) (y=0) // (ggT(x,0) = x = ggT(a,b)) = Q(V)

5.8.75.8.7 Beweis Euklid‘scher Algorithmus IBeweis Euklid‘scher Algorithmus I

Zu beweisen: ggT(y,x mod y) = ggT(x,y), x>0, y0 Der Beweis stützt sich auf einen Hilfssatz, der zunächst bewiesen wird

Hilfssatz: Seien a 0, b . Dann gilt für alle d ( „|“: Ist Teiler von) a) d | a d | b d | (a mod b) b) d | b d | (a mod b) d | a

Beweis:a) Es sei a mod b = r. Dann ist a - r durch b teilbar. Also ist a - r auch

durch d teilbar. Da a durch d teilbar ist, muss auch r durch d teilbar sein, also gilt d | (a mod b).

b) Wiederum sei a mod b = r. Dann ist a - r durch b und damit durch d teilbar. Da r durch d teilbar ist, muss auch a durch d teilbar sein, d.h. es gilt d | a.

5.8.75.8.7 Beweis Euklid‘scher Algorithmus IIBeweis Euklid‘scher Algorithmus II

Beweis: Es wird gezeigt, dass ggt(a, b) und ggt(b, a mod b) sich gegenseitig teilen und daher gleich sein müssen.

1. Sei d = ggt(a, b). Dann gilt d | a und d | b

und nach dem Hilfssatz d | (a mod b)

Nach Definition des ggt gilt d | b d | (a mod b) d | ggt(b, a mod b)

2. Sei nun umgekehrt d = ggt(b, a mod b). Dann gilt d | b und d | (a mod b)

und nach dem Hilfssatz d | a

Nach Definition des ggt gilt d | a d | b d | ggt(a, b)

Mit 1. d=ggt(a,b) | ggt(b,a mod b) und2. d=ggt(b,a mod b) | ggt(a,b) ist gezeigt, dass

ggt(a, b) = ggt(b, a mod b)

5.8.85.8.8 Kritische AnmerkungenKritische Anmerkungen

Die Verifikation entspricht einer mathematischen Beweisführung und kann entsprechend kniffelig, aufwändig, wenn nicht gar unmöglich sein.

Durch formale Überprüfung der Korrektheit, lassen sich Schlüsselstellen eines Algorithmus‘ (eines Programmes) verifizieren

Durch das Denken mit Zusicherungen, Invarianten und mathematische Folgerungen wird die Erstellung fehlerfreier Programme gefördert.

Auch wenn es semi-automatische Systeme zur formalen Verifikation von Algorithmen gibt, ist es praktisch nicht möglich, auch nur halbwegs komplexe Programmsysteme damit zu verifizieren

Selbst wenn es möglich wäre, Algorithmen vollständig formal zu beweisen, so wäre dies keine Garantie, dass ein Programmsystem entsprechend den Wünschen eines „Kunden“ funktioniert. Dazu gehören alle Mechanismen eines ordentlichen Software-Engineerings.

Documents

Kapitel 5Der Algorithmus