Matthias Spohrer · TU München 8. Präsenzveranstaltung 08.04.2003 – TU Stammgelände Innenstadt Nachqualifizierungskurs für Informatiklehrkräfte

Matthias Spohrer · TU München

8. Präsenzveranstaltung 08.04.2003 – TU Stammgelände Innenstadt

Nachqualifizierungskurs für Informatiklehrkräfte

Nachqualifizierungskurs für Informatiklehrkräfte© 2003 Matthias Spohrer · TU München

Seite 2

Inhaltsübersicht

Aufwärmübung Informationen Rekursion Entrekursivierung Ausblick OOM-Modul


Seite 3

Infos - Präsenztage

Donnerstag, 13.03.03

14-18 Uhr HS 0670

Funktionale Modellierung

Dienstag, 08.04.03 14-18 Uhr HS 1601

Funkt. Mod. & OOM

Mittwoch, 07.05.03 14-18 Uhr HS 1601

OOM

Montag, 02.06.03* 15(?)-18 Uhr*

HS 0220

Auf Wunsch, zur Klausur

Donnerstag, 26.06.03

10-12 Uhr HS 0220

Klausur

*ob und ab wann dieser Präsenztag stattfinden soll, werden wir jetzt gemeinsam ausmachen. •Außerdem eine Abschlussveranstaltung im Juli.


Seite 4

Sonstiges / Infos / Aussprache

Präsenztag nächstes Schuljahr: wie angekündigt DienstagDienstag

Sorry für die fehlenden Korrekturen!!!

Anmerkungen / Wünsche / Fragen zum aktuellen Material...


Seite 5

Kleine Aufwärmübung

Staatsexamen Herbst 1997, Thema II, Aufgabe 3Staatsexamen Herbst 1997, Thema II, Aufgabe 3Gegeben sei das Alphabet A = (A, B, C). In A* zeichnen wir die Teilmenge T der Wörter aus, die weder ACC noch BCC als Teilzeichenreihe enthalten. Dabei ist x A* genau dann eine Teilzeichenreihe von y A*, wenn es ein y' A* und ein y" A* gibt, so dass y = y'xy" ist.Konstruieren Sie den (bis auf die Bezeichnungen der Zustände eindeutigen)minimalen deterministischen endlichen Automaten A = (S, I, , s0, F) mit derZustandsmenge S, dem Eingabealphabet I = A, der Zustandsübergangsfunktion : S x I S, dem Anfangszustand s0 und der Endzustandsmenge F, der genau T akzeptiert!Stellen Sie hierzu den Automaten A durch seinen Zustandsübergangsgraphen dar.


Seite 6

Rekursion

Linear rekursive Linear rekursive Funktionen...enthalten höchstens einen rekursiven Funktionsaufruf innerhalb jedes Fallunterscheidungszweiges.

function ggt (nat a, b): natreturn if a = b then a else if a < b then ggt(a, b–a) else ggt(a–b, b) fi fi

function fak(nat x): natreturn if x=0 then 1 else fak(x-1)*x fi

function potenz(nat x,n): natreturn if n=0 then 1 else potenz(x, n–1)*x fi


Seite 7

Rekursion

Repetitiv rekursive Repetitiv rekursive Funktionen...sind lineare rekursive Funktionen, die als letzten Verarbeitungsschritt den rekursiven Aufruf haben.


function fak(nat x): natreturn if x=0 then 1 else fak(x-1)*x fi fak NICHT repetitiv rekursivfak NICHT repetitiv rekursiv

function potenz(nat x,n): natreturn if n=0 then 1 else potenz(x, n–1)*x fi potenz NICHT repetitiv rekursivpotenz NICHT repetitiv rekursiv


Seite 8

Rekursion

Kaskadenartig rekursive Kaskadenartig rekursive Funktionen...sind rekursive Funktionen, die in mindestens einem Fallunterscheidungszweig mehr als einen rekursiven Aufruf enthalten.

function bn (nat n,k): natreturn if n=0 or k=0 or k =n then 1 else bn(n–1, k) + bn(n–1, k–1) fi

function qsort (natlist ls): natlistreturn if length(ls) <= 1 then lselse concat(concat(qsort(smaller(ls,ls.head)), equal(ls,ls.head)), qsort(greater(ls,ls.head)))

fi


Seite 9

Rekursion

Vernestet rekursive Vernestet rekursive Funktionen...sind rekursive Funktionen, in denen in den Parameterausdrücken eines rekursiven Aufrufs weitere rekursive Aufrufe auftreten

function acker(nat m, n): natreturn if m=0 then n+1

else if n=0 then acker (m–1, 1) else acker (m–1, acker (m, n–1)) fi fi

function quersumme(nat n): natreturn if n<=9 then n

else quersumme(quersumme(n div 10) + (n mod 10)) fi fi


Seite 10

Rekursion

Verschränkt rekursive Verschränkt rekursive Funktionen...sind mehrere rekursive Funktionen, die sich gegenseitig aufrufen

function gerade (nat n): boolreturn if n = 1 then false else ungerade(n-1) fi function ungerade (nat n): boolreturn if n = 1 then true else gerade(n-1) fi


Seite 11

Rekursion

Primitiv rekursive Primitiv rekursive Funktionen...entstehen aus sehr einfachen Grundfunktionen über den natürlichen Zahlen, indem man endlich viele Operationen hierauf anwendet.Grundfunktionen sind:

1 2

1 2

: , ( , ,..., ) : 0;

: , ( ) : 1;

: , ( , ,..., ) :

( , {1,..., })

n n nn

n n ni i n i

zero zero x x x

succ succ x x

proj proj x x x x

n i n

Operationen sind:

1

1

2

Substitution: Sind die Funktionen : und ,..., :

primitiv rekursiv, so ist auch : mit ( ) ( ( ),..., ( )) primitiv rekursiv.

Primitive Rekursion: : , : primitiv rekursiv,

n mn

mn

k k

h g g

f f x h g x g x

g h

1 1 1 1 1

dann auch jede Funktion ,

welche folgende Gleichungen erfüllt:

( ,..., ,0) ( ,..., ); ( ,..., , 1) ( ,..., , , ( ,..., , ))k k k k k

f

f x x g x x f x x y h x x y f x x y


Seite 12

Rekursion

Primitiv rekursive Primitiv rekursive Funktionen – Beispiel 1Die AdditionAddition ist primitiv rekursiv:

add(x,y)=x+y

add(x,0):=x

add(x,y+1)=succ(add(x,y))

Hier wäre g(x)=x=proj11(x) und h=succ°proj33

1 2

1 2

: , ( , ,..., ) : 0;

: , ( ) : 1;

: , ( , ,..., ) :

( , {1,..., })

n n nn

n n ni i n i

zero zero x x x

succ succ x x

proj proj x x x x

n i n

1

1

2




n mn

mn

k k

h g g

f f x h g x g x

g h

1 1 1 1 1



( ,..., ,0) ( ,..., ); ( ,..., , 1) ( ,..., , , ( ,..., , ))k k k k k

f



Seite 13

Rekursion

Primitiv rekursive Primitiv rekursive Funktionen – Beispiel 2Die MultiplikationMultiplikation ist prim. rekursiv:

mult(x,y)=x*y

mult(x,0):=0

mult(x,y+1)=add(x,mult(x,y))

Hier wäre g(x)=0=zero1(x) und h=add(proj13,proj3)

1 2

1 2

: , ( , ,..., ) : 0;

: , ( ) : 1;

: , ( , ,..., ) :

( , {1,..., })

n n nn

n n ni i n i

zero zero x x x

succ succ x x

proj proj x x x x

n i n

1

1

2




n mn

mn

k k

h g g

f f x h g x g x

g h

1 1 1 1 1



( ,..., ,0) ( ,..., ); ( ,..., , 1) ( ,..., , , ( ,..., , ))k k k k k

f



Seite 14

Rekursion

Primitiv rekursive Primitiv rekursive Funktionen – Beispiel 3Die Vorgängerfkt.Vorgängerfkt. ist prim. rek.:

pred(x)=x-1

pred(0):=0

pred(y+1)=y

Hier wäre g()=0=zero0() und h=proj12

1 2

1 2

: , ( , ,..., ) : 0;

: , ( ) : 1;

: , ( , ,..., ) :

( , {1,..., })

n n nn

n n ni i n i

zero zero x x x

succ succ x x

proj proj x x x x

n i n

1

1

2




n mn

mn

k k

h g g

f f x h g x g x

g h

1 1 1 1 1



( ,..., ,0) ( ,..., ); ( ,..., , 1) ( ,..., , , ( ,..., , ))k k k k k

f



Seite 15

Rekursion

Primitiv rekursive Primitiv rekursive Funktionen – Beispiel 4Die FakultätFakultät ist prim. rek.:

fak(x)=x!

fak(0):=1

fak(n+1)=(n+1)*fak(n)

Hier wäre g()=1=succ(zero0()) und h=mult(succ°proj12,proj22)

1 2

1 2

: , ( , ,..., ) : 0;

: , ( ) : 1;

: , ( , ,..., ) :

( , {1,..., })

n n nn

n n ni i n i

zero zero x x x

succ succ x x

proj proj x x x x

n i n

1

1

2




n mn

mn

k k

h g g

f f x h g x g x

g h

1 1 1 1 1



( ,..., ,0) ( ,..., ); ( ,..., , 1) ( ,..., , , ( ,..., , ))k k k k k

f



Seite 16

Rekursion

Primitiv rekursive Primitiv rekursive Funktionen – Beispiel StaatsexamenProbiert euch an die Staatsexamensaufgabe

Frühjahr 99 Thema II Aufgabe 1

1 2

1 2

: , ( , ,..., ) : 0;

: , ( ) : 1;

: , ( , ,..., ) :

( , {1,..., })

n n nn

n n ni i n i

zero zero x x x

succ succ x x

proj proj x x x x

n i n

1

1

2




n mn

mn

k k

h g g

f f x h g x g x

g h

1 1 1 1 1



( ,..., ,0) ( ,..., ); ( ,..., , 1) ( ,..., , , ( ,..., , ))k k k k k

f



Seite 17

Entrekursivierung

Repetitiv rekursive Repetitiv rekursive Funktionen...sind besonders einfach iterativ zu schreiben


function ggTit(nat a, b): natvar nat avar := a, bvar := b;beginwhile not avar=bvar do

if avar<bvar then bvar := bvar–avar else avar := avar–bvar fi

od;return avar;end ggTit

ggTit(12,8)

avar:=12, bvar:=8

avar:=12-8=4

bvar:=8-4=4

return 4


Seite 18

Entrekursivierung

Linear rekursive Linear rekursive Funktionen...können mit Hilfe der Einbettungstechnik durch repetitiv-rekursive Funktionen dargestellt und dann wie eben entrekursiviert, also iterativ dargestellt werden.Dies ist vergleichbar mit dem „Currying“ und den Akkumulatoren in HASKELL!

function fakallg(nat n, k): natreturn if n=0 then k else fakallg(n–1, k*n) fi

function fakallgit(nat n, k): natvar nat nvar := n, kvar := k;beginwhile nvar <> 0 dokvar := kvar*nvar;

nvar := nvar –1;od;return kvar;end fakallgit

fakallgit(4,1)

kvar:=1; nvar:=4

kvar:=1*4=4 ; nvar:=4-1=3

kvar:=4*3=12 ; nvar:=3-1=2

kvar:=12*2=24 ; nvar:=2-1=1

kvar:=24*1=24 ; nvar:=1-1=0

return 24


Seite 19

Entrekursivierung

Linear rekursive Linear rekursive Funktionen

function fakallg(nat n, k): natreturn if n=0 then k else fakallg(n–1, k*n) fi

function fakallgit(nat n, k): natvar nat nvar := n, kvar := k;beginwhile nvar <> 0 dokvar := kvar*nvar;

nvar := nvar –1;od;return kvar;end fakallgit

Die übliche Fakultätsfunktion ist dann durch fak(n) = fakallg(n,1) eingebettet.

Die Korrektheit der Einbettung wird i.a. mit vollständiger Induktionvollständiger Induktion bewiesen.


Seite 20

Entrekursivierung

Kaskadierend- Kaskadierend- oder verneste-rekursive verneste-rekursive Funktionen...können durch einen Kellerspeicher iterativ geschrieben werden (LIFO-Prinzip)

function acker(nat m, n): natreturn if m=0 then n+1 else if n=0 then acker (m–1, 1)

else acker (m–1, acker (m, n–1)) fi fi

fi

Iterative Version siehe Folie... (passt hier nicht drauf...)


Seite 21

Fragen

?

Documents

Matthias Spohrer · TU München 8. Präsenzveranstaltung 08.04.2003 – TU Stammgelände Innenstadt Nachqualifizierungskurs für Informatiklehrkräfte