Rekursive Listenverarbeitung Prolog Grundkurs WS 99/00 Christof Rumpf rumpf@uni-duesseldorf.de

Rekursive Listenverarbeitung

Prolog Grundkurs WS 99/00

Christof Rumpf

rumpf@uni-duesseldorf.de

22.11.99 GK Prolog - Rekursive Listenverarbeitung

Datenstrukturen

Datenstrukturen sind mathematische Objekte wie– Mengen– Listen– Bäume– Gerichtete azyklische Graphen– ...

Datenstruktur-Komponenten

Eine abstrakte Datenstruktur besteht aus zwei Komponenten:– Einer Definition für die Repräsentation der

Daten.– Einer Menge von Operationen, mit denen die

Datenstruktur manipuliert werden kann.

Operationen auf Listen

Für die Manipulation von Listen stehen uns in Prolog zwei Basisoperationen zur Verfügung:– Der Listenkonstruktor zur Zerlegung einer Liste

in Kopf und Rest.– Unifikation.

Zusammen mit rekursiven Prädikaten er-lauben diese Mittel komplexere Operationen.

Basisprädikate zur Listenmanipulation

Vier Prädikate zur rekursiven Listenverarbeitung demonstrieren Basistechniken für beliebig komplexe Operationen auf Listen:

– member/2 Zugriff auf Listenelemente.– append/3 Konkatenation von Listen.– delete/3 Löschen/Einfügen in Listen.– reverse/2 Umkehren von Listen.

append/3

% append(L1,L2,L3)

append([],L,L). append([H|T1],L,[H|T2]):- append(T1,L,T2).

append/3 setzt drei Listenobjekte derart in Beziehung, daß das dritte Argument die Konkatenation (Verkettung, Aneinanderhängen) der ersten mit der zweiten Liste repräsentiert: L1^L2 = L3

Anfragen an append/3

?- append([1,2,3],[4,5,6],[1,2,3,4,5,6]). yes ?- append([1,2,3],[4,5,6],L). L = [1,2,3,4,5,6] yes ?- append(L,[4,5,6],[1,2,3,4,5,6]). L = [1,2,3] yes ?- append([1,2,3],L,[1,2,3,4,5,6]). L = [4,5,6] yes

Präfixe & Suffixe

?- append(L1,L2,[1,2,3,4]). L1 = [], L2 = [1,2,3,4] ->; L1 = [1], L2 = [2,3,4] ->; L1 = [1,2], L2 = [3,4] ->; L1 = [1,2,3], L2 = [4] ->; L1 = [1,2,3,4], L2 = [] ->; no

append/3 ist auch in der Lage, eine Liste in alle Präfixe und Suffixe zu zerlegen.

append/3 deklarativ

append([],L,L). append([H|T1],L,[H|T2]):- append(T1,L,T2).

– Die Konkatenation einer Liste L an die leere Liste liefert L als Ergebnis.

– Die Konkatenation einer Liste L an eine nichtleere Liste L1 ist L3, wobei der Kopf von L3 identisch mit dem Kopf von L1 ist und der Rest von L3 die Konkatenation von L an den Rest von L1 repräsentiert.

append/3 prozedural

(0) CALL: append([1,2,3],[4,5,6], _0084) (1) CALL: append( [2,3],[4,5,6], _06F0) (2) CALL: append( [3],[4,5,6], _0830) (3) CALL: append( [],[4,5,6], _0970) (3) EXIT(D): append( [],[4,5,6], [4,5,6]) (2) EXIT(D): append( [3],[4,5,6], [3,4,5,6]) (1) EXIT(D): append( [2,3],[4,5,6], [2,3,4,5,6]) (0) EXIT(D): append([1,2,3],[4,5,6],[1,2,3,4,5,6])

delete/3

% delete(Term,Liste1,Liste2) delete(X,[X|T],T). delete(X,[H|T1],[H|T2]):- delete(X,T1,T2).

delete/3 setzt einen Term und zwei Listen derart in Beziehung, daß Liste2 das Ergebnis des einmaligen Löschens von Term an einer beliebigen Position in Liste1 repräsentiert.

Anfragen an delete/3 I

?- delete(2,[1,2,3],[1,2]). yes ?- delete(2,[1,2,3],L). L = [1,3], yes ?- delete(X,[1,2,3],[1,3]). X = 2, yes ?- delete(2,L,[1,3]). % insert/3 L = [2,1,3] ->; L = [1,2,3] ->; L = [1,3,2] ->; no

Anfragen an delete/3 II

?- delete(X,[1,2,3],L). X = 1, L = [2,3] ->; X = 2, L = [1,3] ->; X = 3, L = [1,2] ->; no ?- delete(x,L,[a,b,c]). L = [x,a,b,c] ->; L = [a,x,b,c] ->; L = [a,b,x,c] ->; L = [a,b,c,x] ->; no

delete/3 deklarativ

delete(X,[X|T],T). delete(X,[H|T1],[H|T2]):- delete(X,T1,T2).

– Das Löschen von X aus dem Kopf einer Liste liefert als Ergebnis den Rest T.

– Das Löschen von X aus dem Rest T1 einer Liste L1 liefert die Liste T2, die Rest einer Liste L2 ist, deren Kopf H mit dem Kopf von L1 identisch ist.

delete/3 prozedural

(0) CALL: delete(1,[1,2,1,3], _0084) (0) EXIT(N):delete(1,[1,2,1,3],[2,1,3]) Backtracking (0) REDO: delete(1,[1,2,1,3],[2,1,3]) (1) CALL: delete(1, [2,1,3], _0728) (2) CALL: delete(1, [1,3], _0868) (2) EXIT(N):delete(1, [1,3], [3]) (1) EXIT(N):delete(1, [2,1,3], [2,3]) (0) EXIT(N):delete(1,[1,2,1,3],[1,2,3]) Backtracking

(0) REDO: delete(1,[1,2,1,3],[1,2,3]) (1) REDO: delete(1, [2,1,3], [2,3]) (2) REDO: delete(1, [1,3], [3]) (3) CALL: delete(1, [3], _09A8) (4) CALL: delete(1, [], _0AE8) (4) FAIL: delete(1, [], _0AE8) (3) FAIL: delete(1, [3], _09A8) (2) FAIL: delete(1, [1,3], _0868) (1) FAIL: delete(1, [2,1,3], _0728) (0) FAIL: delete(1,[1,2,1,3], _0084) No more solutions.

„Naives“ reverse/2

% reverse(Liste,UmgekehrteListe) reverse([],[]). reverse([H|T],RL):- reverse(T,RT), append(RT,[H],RL).

reverse/2 setzt zwei Listenobjekte derart miteinander in Beziehung, daß die eine Liste die Elemente der anderen Liste in umgekehrter Reihenfolge enthält.

Anfragen an reverse/2

?- reverse([1,2,3],[3,2,1]). yes ?- reverse([1,2,3],L). L = [3,2,1] yes ?- reverse(L,[3,2,1]). L = [1,2,3] yes ?- reverse([1,2,3],[1,2,3]). no

Naives reverse/2 deklarativ

reverse([],[]). reverse([H|T],RL):- reverse(T,RT), append(RT,[H],RL).

– Die Umkehrung der leeren Liste ist die leere Liste.

– Die Umkehrung einer nichtleeren Liste [H|T] ergibt sich, indem man an die Umkehrung von T eine Liste mit dem Kopf H als einzigem Element konkateniert.

Naives reverse/2 prozedural

(0) CALL: reverse([1,2,3], _0084) (1) CALL: reverse( [2,3], _0754) (2) CALL: reverse( [3], _08AC) (3) CALL: reverse( [], _0A04) (3) EXIT(D):reverse( [], []) (4) CALL: append( [],[3], _08AC) (4) EXIT(D):append( [],[3], [3]) (2) EXIT(D):reverse( [3], [3]) (5) CALL: append( [3],[2], _0754) (6) CALL: append( [],[2], _0F70)

(6) EXIT(D):append( [],[2], [2]) (5) EXIT(D):append( [3],[2], [3,2]) (1) EXIT(D):reverse( [2,3], [3,2]) (7) CALL: append([3,2],[1], _0084) (8) CALL: append( [2],[1], _13AC) (9) CALL: append( [],[1], _14EC) (9) EXIT(D):append( [],[1], [1]) (8) EXIT(D):append( [2],[1], [2,1]) (7) EXIT(D):append([3,2],[1],[3,2,1]) (0) EXIT(D):reverse( [1,2,3],[3,2,1])

reverse([],[]).reverse([H|T],RL):- reverse(T,RT), append(RT,[H],RL).

Warum naiv?

Das naive reverse/2 wird naiv genannt, weil das zu lösende Problem eigentlich mit linearer Laufzeit gelöst werden könnte. Das naive reverse/2 benötigt jedoch durch den Einsatz von append/3 kubische Laufzeit.– Listenlänge: n– linear: n Schritte– kubisch: n3 Schritte

reverse/3 mit Akkumulator

% reverse(Liste,UmgekehrteListe) reverse(L,RL):- reverse(L,[],RL). reverse([],L,L). reverse([H|T],RT,RL):- reverse(T,[H|RT],RL).

reverse/2 wird mit reverse/3 bewiesen, wobei ein Akkumulator (‚Aufsammler‘) mit der leeren Liste initialisiert wird.

Funktionsweise von reverse/3

reverse(L,RL):- reverse(L,[],RL). reverse([],L,L). reverse([H|T],RT,RL):- reverse(T,[H|RT],RL).

Der Kopf der ersten Liste wird im rekursiven Aufruf als Kopf des Akkumulators gesetzt. Die erste Liste wird kleiner, der Akkumulator wächst. Die Elemente aus der ersten Liste geraten im Akkumulator in umgekehrte Reihenfolge. Wenn die erste Liste leer ist, liefert der Akkumulator das Ergebnis. Die Anzahl der Beweisschritte wächst linear zur Listenlänge.

reverse/3 Trace

(0) CALL: reverse([1,2,3,4], _0084) (1) CALL: reverse([1,2,3,4], [], _0084) (2) CALL: reverse( [2,3,4], [1], _0084) (3) CALL: reverse( [3,4], [2,1], _0084) (4) CALL: reverse( [4], [3,2,1], _0084) (5) CALL: reverse( [],[4,3,2,1], _0084) (5) EXIT(D): reverse( [],[4,3,2,1],[4,3,2,1]) (4) EXIT(D): reverse( [4], [3,2,1],[4,3,2,1]) (3) EXIT(D): reverse( [3,4], [2,1],[4,3,2,1]) (2) EXIT(D): reverse( [2,3,4], [1],[4,3,2,1]) (1) EXIT(D): reverse([1,2,3,4], [],[4,3,2,1]) (0) EXIT(D): reverse([1,2,3,4], [4,3,2,1])

Akkumulatoren

‚Normale‘ rekursive Listenverarbeitung:– Zerlegung im Kopf der Regel.– Rekursive Weiterverarbeitung des Rests.– Liste wird mit Rekursion kürzer.

Listenverarbeitung mit Akkumulator:– Rest steht im Kopf der Regel.– Zerlegung im rekursiven Aufruf.– Liste wird mit Rekursion länger.

p(...,[H|T],...):- ..., p(...,T,...), ...

p(...,T,...):- ..., p(..., [H|T],...), ...

permute/2

% permute(Liste1,Liste2). permute([],[]). permute([H|T],P):- permute(T,TP), delete(H,P,TP).

permute/2 bildet eine Relation über zwei Listenobjekten, wobei die eine Liste eine beliebige Permutation der anderen ist.

Anfrage an permute/2

n! (Fakultät) Lösungen bei Listenlänge n.

?- permute([1,2,3],P). P = [1,2,3] ->; P = [2,1,3] ->; P = [2,3,1] ->; P = [1,3,2] ->; P = [3,1,2] ->; P = [3,2,1] ->; no

4! = 245! = 1206! = 7207! = 50408! = 403209! = 36288030! = 2,65...e+32

Permutationssortieren

sort(L1,L2):- permute(L1,L2), ordered(L2). ordered([]). ordered([_]). ordered([X,Y|T]):- X =< Y, ordered([Y|T]).

sort/2 bildet eine Relation über zwei Listen mit Zahlenelementen, wobei die zweite Liste eine sortierte Version der ersten ist. Permutationssortieren ist bezüglich Komplexität eines der schlechtesten Sortierverfahren.

Anfrage an sort/2

?- sort([9,8,2,4,1,3,7,5,6],L). L = [1,2,3,4,5,6,7,8,9] ->; no

Zum Beweis der Anfrage wurden im Generiere-und-Teste-Verfahren 9! = 362880 Permutationen erzeugt, obwohl nur eine der Permutationen eine Lösung repräsentiert.

Quicksort

qs([],[]). qs([H|T],S):- partition(T,H,L,B), qs(L,LS), qs(B,BS), append(LS,[H|BS],S).

Leere Liste ist sortiert.H ist Vergleichselement.T mit H in L und B teilen.L nach LB sortieren.B nach BS sortieren.LS^BS=S(ortierte Liste).

Quicksort teilt eine Liste mittels Vergleichselement in zwei Listen mit kleineren bzw. größeren Elementen, die dann rekursiv sortiert und zur sortierten Gesamtliste konkateniert werden.

partition/4

partition([],_,[],[]). partition([H|T],X,[H|L],B):- H =< X, partition(T,X,L,B). partition([H|T],X,L,[H|B]):- H > X, partition(T,X,L,B).

Termination.

H in L(ower),

falls H kleiner X.

Rest T partitionieren.

H in B(igger),

falls H größer X.

Rest T partitionieren.

partition/2 hat lineare Komplexität, Quicksort normaler-weise n log n. Hier kommt leider wegen append/3 nach der Rekursion noch eine quadratische Komponente hinzu.

Rekursive Listenverarbeitung Prolog Grundkurs WS 99/00 Christof Rumpf rumpf@uni-duesseldorf.de

Documents

Problemlösen mit Rekursion Klaus Becker 2009. 2 Problemlösen mit Rekursion Inhalte: Problemlösen durch Problemreduktion Selbstähnliche Figuren Rekursive

6. Rekursive und primitiv rekursive Funktionen · 6. Rekursive und primitiv rekursive Funktionen Ein maschinenunabh¨angiges formales Berechnungsmodell auf den naturlichen Zahlen

Abschlussworkshop CFK-Rumpf NG Simulation des - dlr.de · Leitprojekt CFK Rumpf NG 3 Wissenschaftliches Ergebnis Promotionen (im Kontext von CFK-Rumpf NG) Wetzel, Anja (2009) Zur

Teil II : Rekursive Algorithmen · Teil II : Rekursive Algorithmen § Rekursive Prozeduren und Funktionen § „Teilen-und-Herrschen“ § Türme von Hanoi K. Murmann , H. Neumann,

Vorschau Prolog Aufbaukurs SS 2003 Heinrich-Heine-Universität Düsseldorf Christof Rumpf

HAUPTABMESSUNGEN gemäß ISO 8666 - FYS · 2 x Volvo Penta IPS500 - Pod drive 28 Knoten* MOTOR OPTION 2 x Volvo Penta IPS600 - Pod drive 32 Knoten*.. RUMPF • GFK-Sandwich-Rumpf,

Timm Grams Hochschule Fulda Fachbereich Elektrotechnik und Informationstechnik Rekursive Funktionen in C © Timm Grams, Fulda, 13.08.2002 (korr.: 15.05.2008)

Vererbung Prolog Aufbaukurs SS 2000 Heinrich-Heine-Universität Düsseldorf Christof Rumpf

Rekursive Funktionen (Fakultät) class Fakultaet { static long fak(long n) { if (n

Listenverarbeitung in Python · Listenverarbeitung in Python Datentypen f¨ur Sequenzen von Objekten: Tupel, Listen und Strings Tupel und Listen sind analog zu Haskells Tupel und

08.02.00GK Prolog: Prolog und Prädikatenlogik II 1 Prolog und Prädikatenlogik II Prolog Grundkurs WS 99/00 Christof Rumpf rumpf@uni-duesseldorf.de

Gasschutz - Brandingeneur Hans Rumpf / 2. Auflage

Typinferenz Prolog Aufbaukurs SS 2000 Heinrich-Heine-Universität Düsseldorf Christof Rumpf

Rekursive Strukturen - uni-hamburg.de

1. Rekursive Algorithmen 2. Rekursive (dynamische ... · II.3.2 Rekursive Datenstrukturen - 3 - Ausdruck Grundwert Name Methodenaufruf ( Ausdruck ) Infix-Operator Ausdruck? Ausdruck:

Prof. Dr. Christian Rumpf - tuerkei-recht.de Dortmund Schmerzensgeldansp… · Prof. Dr. Christian Rumpf Lenzhalde 68 D-70192 Stuttgart Tel. +49(0)711 997 977-0 Fax. +49(0)711 997

EINI LogWing/WiMa - · • Prolog • Arrays • Sortieren • Rekursive Datenstrukturen. Begriffe Spezifikationen, Algorithmen, formale Sprachen ... (Baum, binärer Baum, Heap)

07.02.00GK Prolog: Prolog und Prädikatenlogik I 1 Prolog und Prädikatenlogik I Prolog Grundkurs WS 99/00 Christof Rumpf rumpf@uni-duesseldorf.de

Semantik von Prolog & Unifikation Prolog Grundkurs WS 99/00 Christof Rumpf rumpf@uni-duesseldorf.de

BOOTSMARKT 2010 Schlauchboote mit flexiblem Rumpf