Embed Size (px)
Citation preview
1
Kapitel 2: Grundelemente von Programmiersprachen2.1 Syntaktische Elemente 2.2 Typsysteme 2.2.1 Einfache Datentypen 2.2.2 Zusammengesetzte Datentypen 2.2.3 Rekursive Datentypen 2.3 Kontrollstrukturen 2.4 Rekursion 2.4.1 Klassifikation und Beispiele 2.4.2 Umwandlung rekursiver in iterative Verfahren 2.5 Verzweigte Rekursion und Backtracking-Verfahren 2.5.1 Türme von Hanoi 2.5.2 Erzeugung fraktaler Muster durch Turtle-Programme 2.5.3 Backtracking: Hofstadters MU-Puzzle
2
2.1 Syntaktische Elemente
Grundelemente:
• Blöcke (Gültigkeitsbereiche von Vereinbarungen, z.B. der Rumpf einer Funktionsdefinition)
• zusammengesetzte Anweisungen (Schleifen, bedingte Verzweigungen)
• einfache Anweisungen (Zuweisungen, Prozeduraufrufe)
• Ausdrücke (Bedingungen, Terme) • Bezeichner (von Konstanten, Variablen,
Prozeduren/Funktionen) • Konstanten (Zahlen, Zeichenketten)
3
Die syntaktische Struktur eines Programmstücks ergibt sich eindeutig aus einer statischen Analyse (des Programmtextes).
Beschreibung der syntaktischen Strukturen durch kontextfreie Grammatiken (z.B. in Backus-Naur-Form) oder durch Syntax-Diagramme.
4
Beispiel: <ParListe> ::= '(' <ParDeklaration> ')' <ParDeklaration>::= <ParKomp> |
<ParKomp> ';'<ParDeklaration>
<ParKomp> ::= 'var' <Par> ':' <TypBez> |
<Par> ':' <TypBez>
<Par> ::= <ParBez> | <ParBez> ',' <Par>
5
Syntaxdiagramme
6
Term
7
2.2 Typsysteme
Elemente von Typsystemen:• Werte (Belegungen von Variablen, Komponenten von
Ausdrücken, Ausprägungen von Übergabeparametern) • Typen (Mengen von Werten, die unter entsprechenden
Operationen abgeschlossen sind, z.B. ganze Zahlen, true/false, Namen der Monate)
• Ausdrücke (Programmsegmente, die zu Werten evaluiert werden können, z.B. die rechte Seite einer Zuweisung)
• Typkonstruktoren (programmiersprachliche Konstrukte zur Definition neuer (zusammengesetzter) Datentypen)
8
• Statische Typisierung: (Pascal, Modula und Java) Der Typ jeder Variablen und jedes Übergabeparameters
wird im Programm explizit definiert. Die Typprüfung wird zur Übersetzungszeit durchgeführt.
• Dynamische Typisierung: (z.B. Prolog, Lisp, Logo). Variablen und Parameter sind nicht typisiert - wohl aber
deren aktuelle Werte. Ein Wert kann ggf. potentiell unterschiedliche Typen "bedienen" (z.B. kann eine Ziffer als Integer oder Character interpretiert werden). Die Typüberprüfung findet zur Laufzeit statt.
Formen der Typisierung
9
Einige einfache Datentypen
Vordefinierte
Truth-Value = {true, false}
Integer = {..., -2, -1, 0, +1, +2, +3, ...}
Real = {..., -1.0, ..., 0.0, ..., 1.0, ...}
Character = {'a', ..., 'z', 'A', ..., 'Z', ...}
Aufzählungstyp
type Tag = {montag, dienstag, mittwoch, donnerstag, freitag, samstag, sonntag}
10
Elementare Datentypen in Java
11
Typkonvertierungen in Java
• boolean kann nicht in einen numerischen Typ überführt werden.
• Die numerischen Typen bilden eine lineare Ordnung (byte -> short -> int -> long -> float -> double). In dieser Reihe kann ein Wert "niederen" Typs implizit in einen Wert höheren Typs überführt werden. Beispiel: int n; ... ; float x = n; ...
• Die Überführung eines höheren in einen niederen Typ erfordert einen sog. cast.
• Beispiel: float x; ... ; x = (float) Math.sin(...); ... (da sin einen Wert vom Typ double liefert.)
12
Typumwandlungen in Java
• Mittels der statischen Methode (Funktion) String.valueOf(x) aus der Klasse String können Werte x von einem beliebigen elementaren Typ in einen String überführt werden.
• Die statische Methode Integer.parseInt(String s) aus der Klasse Integer überführt einen String s in einen int-Wert (falls nicht möglich: exception).
• Zu jedem elementaren Typ gibt es eine zugeordnete
Objektklasse (Wrapper-Klasse, Konvertierung erforderlich!). Auf dieser Ebene sind weitere - einheitlichere - Konvertierungsmöglichkeiten definiert.
13
Beispiele
Beispiel: int i = 5; int j = 2; float x = i / j;
ergibt den Wert 2.0 für x.
int i = 5; int j = 2; float x = i / (float) j; ergibt den Wert 2.5 für x.
14
2.2.2 Zusammengesetzte Datentypen
• werden erst im Programm durch Verwendung von Typ-Konstruktoren (record, set, array, ...) definiert.
• Java kennt hiervon nur den Array-Konstruktor;
15
• Verbundtyp (record) in Pascal: allgemeine Form:
record I1 : T1; ... ; In : Tn end {Ik: Feldname, Tk: Feldtyp}
• Beispiel: type TelEintrag = record Name:string[20];
Nr : string[12] end
• Wertemenge des hierdurch konstruierten Typs: kartesisches Produkt T1 ... Tn
• Kardinalität: # (T1 ... Tn ) = # (T1 )•....• # (Tn )
16
Explizite Definition von Abbildungen durch Arrays (Java):
Schema: Sei m : I T, wobei I eine endliche Indexmenge,
T der Typ der Werte (Bildmenge) sei.
Für endliche T ergibt sich die Kardinalität: # ( I T ) = # ( T ) # ( I )
Der Ansatz kann iteriert werden, d.h. T kann selbst schon ein Array sein.
17
Beispiel: Labyrinth in Pascal
type dim_x = [1 .. n] ; dim_y = [1 .. m] ; Labyrinth = array dim_x, dim_y of boolean ; var Lab: Labyrinth ;
procedure wand(i: dim_x, j: dim_y): boolean ; begin wand := Lab[i,j] end {wand} ;
Beispiel: Labyrinth in Java ... int Lab[][] = new int[n][m] ; ... /* Initialisierung erfolgt z.B. in Konstruktor-Methode der Klasse */ public boolean wand(int i, int j) { return Lab[i][j] ; }
18
2.2.3 Rekursive Datentypen
Ein Datentyp heißt rekursiv, wenn in seiner Typdefinition der Typ selbst wieder vorkommt; d.h. Werte dieses Typs können wiederum Werte des gleichen Typs als Komponenten enthalten.
Beispiel: Liste von Zahlen: ListofInteger := {nil} + (Integer ListofInteger) Vereinbarung in Pascal: type List = ^ListElem; ListElem = record wert : Integer; nachf : List end;
19
2.3 Kontrollstrukturen- AnweisungenUnterscheide zwischen:Ausdruck (Term) - Anweisung (Befehl)
In C++ und Java ist die Trennung zwischen Ausdruck und Anweisung nicht durchgehalten; i++ und ++i sind Kurzformen für die Anweisung i := i + 1, sind aber auch Ausdrücke mit Wert(i++) = Wert(++i) = Wert(i) + 1.
Beispiele: Ausdruck oder Anweisung? a) 3 > sqrt(k);
b) int k = ++i;
20
• Elementare (atomare) Anweisungen: Zuweisungen, Prozeduraufrufe
• Strukturierte Anweisungen: Sequenzen, bedingte Anweisungen, iterierte Anweisungen (Schleifen), einige weitere.
Für jede strukturierte Anweisung lässt sich ein allgemeines Schema für die "Fortpflanzung„
von Zusicherungen (zum Korrektheitsnachweis)
(notiert in spitzen Klammern < ... > ) angeben.
21
• Anweisungssequenz:
In Java:
{ A1; A2; ...; An; }
Zusicherungen: Beispiel: Hier gilt für n=2:
Voraussetzungen:
<P> A1 <Q> und <Q> A2 <R> Folgerung:
<P> A1; A2 <R>
22
• Bedingte Anweisungen:
23
• Bedingte Anweisungen:
In Java: if (B) A1 else A2 bzw. if (B) A
Zusicherungen: <P & B> A1 <Q>, <P & ~B> A2 <Q>
----------------------------------------------- <P> if B then A1 else A2 <Q> bzw.
<P & B> A <Q> &(P & ~B => Q) ------------------------------- <P> if B then A <Q>
24
• Schleifen:
In Java:
while (B) A bzw. do A while (B);
Zusicherungen:
<P & B> A <P>
-------------------------------
<P> while B do A <P & ~B>
25
Beispiel:
{N > 0} i := 0;
fact := 1; {i = 0 & fact = 1 & N > 0}
while i < N do begin {fact = i! & i <= N}
i := i + 1;
fact := fact * i;
end; {fact = i! & i <= N & i >= N}
{fact = N!}
26
• Schleifen:
Zusicherungen:
<P> A <I> & <I & ~B> A <I> & (I & B => Q)
------------------------------------------
<P> repeat A until B <Q>
27
• Weitere strukturierte Anweisungen:
• selektive Anweisung:
in Pascal: case in Java: switch
• for-Schleife in Java:
for(init; test; update) Anweisung ;
28
2.4 Rekursion2.4.1 Klassifikation und Beispiele
Begriff der Rekursion:• allgemein:
selbstbezüglicher Verweis, Selbstbezüglichkeit / Selbstähnlichkeit einer Struktur
• spezielle Bedeutung im Bereich Programmierung:
Selbstaufruf einer Prozedur / Funktion
Anmerkung: die Theorie rekursiver Funktionen im Sinne der Mathematik baut auch auf Rekursion auf.
29
Beispiele rekursiver Algorithmen:
• größter gemeinsamer Teiler (ggT)
Eingaben a,b ganzzahlig, positiv
algorithmus ggT(a,b: int) int { wenn a=b dann rückgabe a;
wenn b>a dann rückgabe ggT(b,a);
rückgabe ggT(a-b,b) }
30
• Fakultät einer nat. Zahl (fak) Eingabe n 0, ganzzahlig
algorithmus fak(n: int) int { wenn n=0 dann rückgabe 1 sonst rückgabe n•fak(n-1) }
31
• Fibonacci-Folge (fibo)
Eingabe n 0, ganzzahlig
algorithmus fibo(n: int) int { wenn (n=0 oder n=1) dann rückgabe n
sonst rückgabe fibo(n-1)+fibo(n-2)
}
32
Klassifikation (Rekursionstypen):
• endständige Rekursion
Das rekursive Aufrufschema einer Prozedur oder Funktion heißt »endständig«, wenn auf jeder Aufrufebene maximal ein rekursiver Aufruf zur Ausführung gelangt und dieser Aufruf weder von weiteren Anweisungen gefolgt wird (d.h. letzte Anweisung) noch in andere Operationen als Rückgabe (return) eingebunden ist.
33
• verzweigte (vs. lineare) Rekursion Ein rekursives Aufrufschema heißt verzweigt,
wenn in bestimmten Fällen mehr als ein rekursiver Aufruf zur Ausführung auf einer Aufrufebene gelangt.
Bei maximal einem rekursiven Aufruf pro Ebene heißt das rekursive Aufrufschema linear.
• indirekte (vs. direkte) Rekursion Als indirekte Rekursion wird der Selbstaufruf
einer Prozedur "auf Umwegen" bezeichnet.
Beispiel: Funktion F ruft (in bestimmten Fällen) G, G ruft H und H wiederum F auf.
34
Vor- und Nachteile der Rekursion
• kompakt, elegant• abstrakt im math.
Sinne• Setzen von Variablen
ohne Zuweisungen (stattdessen: Parameterübergabe).
• schwierig zu handhaben
• hohe Ablaufkomplexi-tät, besonders bei verzweigten Rekur- sionen
• Speicherbedarf für Rekursionskeller
• Effizienznachteil gegenüber Iteration.
35
Beispiel: "Partitionszahl"
• Definition: Die Partitionszahl P(n) einer natürlichen Zahl n ist die Anzahl der - unabhängig von der Reihenfolge der Summanden - verschiedenen additiven Zerlegungen von n (positive Summanden).
Formal: P(n) := #( { {k1, … , kj} mit n = k1 + … + kj , 0 < ki n} ) Hier ist {k1 ,..,kj } eine Multimenge, d.h. ein
Element darf mehrfach vorkommen.
36
Problem: gegeben n, berechne P(n) !
Lösung: Rekursion.
Definition: P(n,k) sei die Anzahl der additiven Zerlegungen von n mit positiven Summanden k (hier sei n > 0 und k > 0).
Dann: P(n) = P(n,n) und• P(1,k) = 1• P(n,1) = 1• P(n,k) = P(n,n) für k > n• P(n,n) = P(n,n-1)+1• P(n,k) = P(n,k-1) + P(n-k,k) für k < n
Beispiel
• Sei n = 5 und k = 3
• P(5,3) = P(5,2) + P(2,2)
37
38
In Java:
public class Parti { private static int String2Int(String s)
{ Integer I = new Integer(s); return I.intValue(); }
private static int P(int n, int k) { if ( n == 1 ) return 1; if ( k == 1) return 1; if ( k > n ) return P(n,n); if ( k == n) return P(n,n-1) + 1; return P(n,k-1) + P(n-k,k); } public static void main(String[] args) { int n = String2Int(args[0]); System.out.println("------------"); System.out.println("P("+n+") = "+P(n,n)); System.out.println("------------"); } }
39
Verifikationskriterien:
• Vollständigkeit der Fallunterscheidung
• Korrektheit des Ergebnisses in terminalen Fällen
• Korrektheit der Reduktionsschritte (Fälle)
• Sicherstellung der Reduktion auf den terminalen Fall in endlich vielen Schritten
40
2.4.2 Umwandlung rekursiver in iterative Verfahren
Beispiel: größter gemeinsamer Teiler rekursiv:algorithmus ggT(a,b: int) int { wenn a=b dann rückgabe a; wenn b>a dann rückgabe ggT(b,a); rückgabe ggT(a-b,b) }
Iterativ: { solange nicht a=b do {wenn b > a dann vertausche(a,b) sonst a := a-b}; rückgabe a }
41
Beispiel: Fakultät.algorithmus fak(n: int) int { wenn n=0 dann rückgabe 1 sonst rückgabe n•fak(n-1) }
Nicht endständig. Zuerst: Umwandlung in einen Algorithmus mit endständiger Rekursion:
algorithmus fakt(n: int, akku: int) int { wenn n=0 dann rückgabe akku sonst rückgabe fakt(n-1,n•akku) }
(Aufruf mit akku=1).
42
Endständige Rekursion zur Berechnung der Fakultät:
algorithmus fakt(n: int, akku: int) int
{ wenn n=0 dann rückgabe akku
sonst rückgabe fakt(n-1,n•akku) }
Nun: ein iterativer Algorithmus:
algorithmus faks(n: int) int
{ akku: int;
akku := 1;
solange nicht n=0 führe_aus
{ akku := n•akku; n := n-1 };
rückgabe akku }
43
Ein anderer iterativer Algorithmus:
algorithmus fakr(n: int) int { akku : int;
akku := 1;
k : int;
k := 0,
solange k < n führe_aus
{ k := k+1; akku := k • akku };
rückgabe akku }
44
Primitive Rekursion:
Ein allgemeines Schema der linearen Rekursion.
Dient zur Definition einer Funktion
f: No X Y .
Gegeben:• a: X Y (Anfangswertfunktion),
• r: No X Y Y (Rekursionsschema).
Dann f definiert durch:
(1) f(n,x) = a(x), falls n=0
(2) f(n,x) = r(n, x, f(n-1,x)), sonst
45
• Beispiel: Mit X= No, Y= No, a(x)=1, r(n,x,y)=x•y erhält man die Potenzfunktion f(n,x) = xn.
• Beispiel: Mit X={()}, Y= No, a()=1, r(n,y)=n•y erhält man die Fakultätsfunktion.
• Beispiel: Was für eine Funktion erhält man mit X=Y= R+, a(x)=x/2, r(n,x,y)=1/2(y+(x/y)) ?
46
public class Iter {
private static int String2Int(String s) { Integer I = new Integer(s); return I.intValue(); }
private static double r(int n, double x, double y) { return 0.5*(y + x/y); }
private static double a(double x) { return x/2; }
private static double iter(int n, double x) { double akku = a(x); int k = 0; while ( k < n ) { System.out.println(k+": "+akku); akku = r(k+1,x,akku); k = k+1; } return akku; }
public static void main(String[] args) {
int x = String2Int(args[0]);
double y = iter(7,x);
System.out.println("-------------------"); System.out.println("Ergebnis: "+y); System.out.println("-------------------"); }}
47
• Iterativer Algorithmus für f, definiert durch primitive Rekursion aus a und r :
algorithmus iter(n: int, x: xVal) yVal { akku : yVal; akku := a(x); k : int; k := 0; solange k < n führe_aus { akku := r(k+1,x,akku); k := k+1 }; rückgabe akku }
