Post on 15-Jan-2016
description
transcript
Telecooperation/RBG
Technische Universität Darmstadt
Copyrighted material; for TUD student use only
Grundlagen der Informatik 1Thema 7: Komplexität von Algorithmen
Prof. Dr. Max MühlhäuserDr. Guido Rößling
Dr. G. RößlingProf. Dr. M. Mühlhäuser
RBG / Telekooperation©
Grundlagen der Informatik I: T7
2
Auswahl von Algorithmen
• Zeitkomplexität – Wie lange dauert die Ausführung?
• Speicherbedarf– Wie viel Speicher wird zur Ausführung
benötigt?• Benötigte Netzwerkbandbreite
Betrachtung der nicht-funktionalen Eigenschaften von Algorithmen:
Zwei Algorithmen berechnen die gleiche Funktion.
Beispiel: merge-sort und insertion-sortWelcher Algorithmus ist der bessere?
Im Folgenden betrachten wir vor allem das Kriterium der Zeit, Speicher
wird ähnlich behandelt
Dr. G. RößlingProf. Dr. M. Mühlhäuser
RBG / Telekooperation©
Grundlagen der Informatik I: T7
3
Wie beurteilt man die Kosten der Berechnung?
• Das Messen der Zeit, die ein Programm für bestimmte Argumente benötigt, kann helfen, um sein Verhalten in einer bestimmten Situation zu verstehen– Aber mit einer anderen Eingabe kann das Programm eine
völlig andere Zeit beanspruchen … • Zeitmessungen von Programmen für bestimmte Eingaben
entsprechen dem Testen von Programmen für bestimmte Eingaben:– So wie das Testen Fehler aufdecken kann, können
Zeitmessungen Anomalien im Ausführungsverhalten für bestimmte Eingaben aufspüren
– Allerdings lässt sich davon keine generelle Aussage über das Verhalten eines Programms ableiten
• Diese Vorlesung gibt einen ersten Einblick in die Mittel zum Treffen allgemeiner Aussagen über die Ausführungskosten von Programmen – GdI 2 widmet sich diesem Thema genauer
Dr. G. RößlingProf. Dr. M. Mühlhäuser
RBG / Telekooperation©
Grundlagen der Informatik I: T7
4
Überblick
• Abstraktes Zeit- und Komplexitätsmaß• O-Notation und andere Wachstumsmaße• Techniken zur Bestimmung der Komplexität• Vektoren in Scheme
Dr. G. RößlingProf. Dr. M. Mühlhäuser
RBG / Telekooperation©
Grundlagen der Informatik I: T7
5
Konkretes Zeitmaß, Abstraktes Zeitmaß
• Die tatsächliche Ausführzeit ist von mehreren Faktoren abhängig– Prozessorgeschwindigkeit– Typ des Computers– Programmiersprache– Qualität des Compilers, …
Um sinnvolle Vergleiche von Algorithmen zu ermöglichen, benötigen wir ein Maß der Zeitkomplexität, das von derartigen Faktoren unabhängig sind.
Home computerDesktop ComputerMinicomputerMainframe computerSupercomputer
51.91511.5082.3820.431
0.087
Art des Computer
Zeit
Tatsächliche Ausführungszeit (Millisekunden) für das Berechnen von f
Dr. G. RößlingProf. Dr. M. Mühlhäuser
RBG / Telekooperation©
Grundlagen der Informatik I: T7
6
Komplexitätsmessung
• Idee: Beschreibung des Zeitverbrauchs als mathematische Funktion Kostenfunktion
• Definitionsbereich der Kostenfunktion: Eingabegröße n – Abhängig vom untersuchten Problem
• Für die Sortierung einer Liste: n = Anzahl der Elemente• Matrizenmultiplikation: n = Anzahl der Zeilen, m = Anzahl
Spalten• Graphenalgorithmen: n = Anzahl der Knoten, e = Anzahl
Kanten• Wertebereich der Kostenfunktion: benötigte
Anzahl der Rechenschritte T(n)– Ansatz: Anzahl der Rekursionsschritte ist ein gutes Maß
der Größe der Auswertungssequenz
Dr. G. RößlingProf. Dr. M. Mühlhäuser
RBG / Telekooperation©
Grundlagen der Informatik I: T7
7
Veranschaulichung des abstrakten Zeitmaßes
Untersuchen wir das Verhalten der Funktion length:
– Sie erhält eine Liste mit beliebigem Dateninhalt und berechnet wie viele Elemente in der Liste enthalten sind
(define (length a-list) (cond [(empty? a-list) 0] [else (+ (length (rest a-list)) 1)]))
length (list 'a 'b 'c))
= (+ (length (list 'b 'c)) 1)
= (+ (+ (length (list 'c)) 1) 1)
= (+ (+ (+ (length empty) 1) 1) 1)
= (+ (+ (+ 0 1) 1) 1)
= 3
Reku
rsion
s-sch
ritte
Dr. G. RößlingProf. Dr. M. Mühlhäuser
RBG / Telekooperation©
Grundlagen der Informatik I: T7
8
Veranschaulichung des abstrakten Zeitmaßes
Nur die Anzahl der Rekursionsschritte ist relevant für die Bestimmung der Komplexität.
• Schritte zwischen den Rekursionen unterscheiden sich nur bzgl. der Substitution von a-list.
(length (list 'a 'b 'c))= (cond [(empty? (list 'a 'b 'c)) 0] [else (+ (length (rest (list 'a 'b 'c))) 1)])= (cond [false 0] [else (+ (length (rest (list 'a 'b 'c))) 1)])= (cond [else (+ (length (rest (list 'a 'b 'c))) 1)])= (+ (length (rest (list 'a 'b 'c))) 1)= (+ (length (list 'b 'c)) 1)
Dr. G. RößlingProf. Dr. M. Mühlhäuser
RBG / Telekooperation©
Grundlagen der Informatik I: T7
9
Veranschaulichung des abstrakten Zeitmaßes
• Das Beispiel zeigt zweierlei:– Die Anzahl der Auswertungsschritte hängt von der
Länge der Eingabeliste ab– Die Anzahl der Rekursionsschritte ist ein gutes Maß
für die Länge einer Auswertungssequenz • Wir können die eigentliche Anzahl benötigter Schritte
aus diesem Maß und der Funktionsdefinition wieder rekonstruieren.
• Die abstrakte Laufzeit eines Programms ist das Verhältnis zwischen der Eingabegröße und der Anzahl der Rekursionsschritte in einer Auswertung– “abstrakt” heißt, die Messung ignoriert konstante
Faktoren: • wie viele primitive Schritte pro Rekursion benötigt
werden• wie viel Zeit primitive Schritte benötigen• wie viel tatsächliche Zeit die gesamte Berechnung
verbraucht
Dr. G. RößlingProf. Dr. M. Mühlhäuser
RBG / Telekooperation©
Grundlagen der Informatik I: T7
10
• Die folgende Applikation von contains-doll? benötigt keinen Rekursionsschritt.
• Die folgende Applikation benötigt so viele Rekursionsschritte, wie es Elemente in der Liste gibt.
• Im besten Fall wird die Lösung unmittelbar gefunden
• Im schlimmsten Fall wird die gesamte Liste durchsucht
Veranschaulichung des abstrakten Zeitmaßes
(define (contains-doll? alos) (cond [(empty? alos) false] [(symbol=? (first alos) 'doll) true] [else (contains-doll? (rest alos))]))
(contains-doll? (list 'doll 'robot 'ball 'game-boy))
(contains-doll? (list 'robot 'ball 'game-boy 'doll))
Dr. G. RößlingProf. Dr. M. Mühlhäuser
RBG / Telekooperation©
Grundlagen der Informatik I: T7
11
Abstraktes Zeitmaß und Eingabeform
• Wir können nicht davon ausgehen, dass Eingaben immer in bestmöglicher Form bereitgestellt werden – Genauso wenig können wir hoffen, dass sie nie in
schlechtmöglichster Form vorliegt. • Stattdessen können wir analysieren, wie viel Zeit die
Funktion durchschnittlich benötigt. • Zum Beispiel würde contains-doll? im
Durchschnitt 'doll irgendwo in der Mitte der Liste finden. – Deshalb können wir sagen, dass die abstrakte Laufzeit von contains-doll? (ungefähr oder durchschnittlich) n/2 beträgt, wenn die Eingabe n Elemente beinhaltet• Im Durchschnitt gibt es halb so viele Rekursionsschritte wie
Elemente in der Eingabe.
Dr. G. RößlingProf. Dr. M. Mühlhäuser
RBG / Telekooperation©
Grundlagen der Informatik I: T7
12
Komplexitätsklassen• Da das abstrakte Zeitmaß konstante Faktoren
ignoriert, können wir die Division durch 2 ignorieren. • Genauer gesagt
– Nehmen wir an, dass jeder Rekursionsschritt K Zeiteinheiten benötigt
– Wenn wir stattdessen K/2 als Konstante wählen, haben wir:
• Um zu zeigen, dass wir solche Konstanten vernachlässigen, sagen wir, contains-doll? benötige die „Größenordnung von n Schritten“, um 'doll in einer Liste mit n Elementen zu finden.
K *n
2
K
2* n
Dr. G. RößlingProf. Dr. M. Mühlhäuser
RBG / Telekooperation©
Grundlagen der Informatik I: T7
13
Komplexitätsklassen
T
n10000
F ~ in der Größenordnung von nG ~ in der Größenordnung von n2
F
G
n 1 10 50 500 1000 5000
F (1000 · n)
1000 10000 50000 500000 1000000
5000000
G (n · n) 1 100 2500 250000 1000000
25000000
Dr. G. RößlingProf. Dr. M. Mühlhäuser
RBG / Telekooperation©
Grundlagen der Informatik I: T7
14
Analyse: insertion-sort;; insertion-sort : list-of-numbers -> list-of-numbers ;; creates a sorted list of numbers from numbers in alon (define (insertion-sort alon) (cond [(empty? alon) empty] [else (insert (first alon) (insertion-sort (rest alon)))]))
(sort (list 3 1 2)) = (insert 3 (insertion-sort (list 1 2))) = (insert 3 (insert 1 (insertion-sort (list 2)))) = (insert 3 (insert 1 (insert 2 (insertion-sort empty)))) = (insert 3 (insert 1 (insert 2 empty))) = (insert 3 (insert 1 (list 2))) = (insert 3 (cons 1 (list 2))) = (insert 3 (list 1 2)) = (cons 1 insert 3 (list 2))= (cons 1 (cons 2 (insert 3 empty))) = (list 1 2 3)
Dr. G. RößlingProf. Dr. M. Mühlhäuser
RBG / Telekooperation©
Grundlagen der Informatik I: T7
15
Analyse: insertion-sort• Zwei Phasen der Auswertung:
1. Rekursive Anwendung von insertion-sort aktiviert so viele Applikationen von insert, wie sich Elemente in der Liste befinden
2. Jede Anwendung von insert durchläuft eine Liste von 1, 2,…,n - 1 Elementen (n ist die Anzahl der Elemente in der ursprünglichen Liste) – nach Gauß‘scher Formel ist das quadratisch.
• insert verhält sich ähnlich dem Suchen eines Elements:– Anwendungen von insert auf einer Liste mit n Elementen
benötigen im Schnitt ~ n Rekursionsschritte. – Bei n Anwendungen von insert gibt es eine Größenordnung
von n2 Rekursionsschritte von insert • Zusammengefasst: wenn lst n Elemente hat…
– benötigt die Auswertung von (insertion-sort lst) n Rekursionsschritte von insertion-sort und
– n2 Rekursionsschritte von insert. – Zusammen: n2 + n , d.h. ~ n2
Dr. G. RößlingProf. Dr. M. Mühlhäuser
RBG / Telekooperation©
Grundlagen der Informatik I: T7
16
Komplexitätsklassen
• insertion-sort benötigt ungefähr c1n2 Schritte, um n Elemente zu sortieren (proportional zu n2)– c1 ist eine Konstante unabhängig von n
• Im Folgenden werden wir merge-sort analysieren– Dies benötigt ungefähr c2n log2 n Schritte, um n Elemente
zu sortieren• c2 ist eine Konstante unabhängig von n
• c2 > c1
– Egal, wie viel kleiner c1 als c2 ist, es wird immer einen Schnittpunkt in den Eingabedaten geben (n groß genug), ab dem merge-sort schneller ist
– Wir können also die Konstanten ignorieren
Dr. G. RößlingProf. Dr. M. Mühlhäuser
RBG / Telekooperation©
Grundlagen der Informatik I: T7
17
Komplexitätsklassen• Stellen Sie sich vor, wir verwenden einen schnellen
Computer A für insertion-sort und einen langsamen Computer B für merge-sort– A ist 100 mal schneller als B betreffend der Rechenleistung
• A führt eine Milliarde (109) Anweisungen pro Sekunde aus• B führt nur 10 Millionen Anweisungen (107) pro Sekunde
• Zusätzlich nehmen wir an:– insertion-sort ist von dem weltbesten Programmierer in
der Maschinensprache für A implementiert • Der resultierende Code benötigt 2n2 (c1 = 2) Anweisungen,
um n Zahlen zu sortieren– merge-sort ist von einem durchschnittlichen
Programmierer in einer high-level Programmiersprache mit ineffizientem Compiler implementiert• Der resultierende Code benötigt 50 n log2 n (c2 = 50)
Anweisungen
Dr. G. RößlingProf. Dr. M. Mühlhäuser
RBG / Telekooperation©
Grundlagen der Informatik I: T7
18
Komplexitätsklassen
Wir sortieren eine Liste mit 1 Million Zahlen (n=106)…
2 x (106)2 instructions109 instructions/sec
= 2000 sec
A (insert-sort)
50 x 106 x log2 106 instructions107 instructions/sec
≈ 100 sec
B (merge-sort)
Da wir einen Algorithmus verwenden, dessen Laufzeit langsamerer wächst, läuft B 20 mal schneller als A (trotz des langsameren Rechners und schlechten Compilers)!Im Allgemeinen wächst der relative Vorteil von merge-sort mit der Problemgröße.
Dr. G. RößlingProf. Dr. M. Mühlhäuser
RBG / Telekooperation©
Grundlagen der Informatik I: T7
19
Zusammenfassung: abstrakte Zeit • Unsere abstrakte Beschreibung ist immer eine Aussage über
das Verhältnis zweier Mengen: – (mathematische) Funktion, die ein abstraktes Größenmaß der
Eingabe auf ein abstraktes Maß der Laufzeit abbildet (Anzahl natürlicher Rekursionen)
• Die genaue Anzahl der ausgeführten Operationen ist weniger wichtig
• Wichtiger ist die Komplexitätsklasse, zu der der Algorithmus gehört– z.B. linear, logarithmisch
• Wenn wir „Größenordnungs“-Eigenschaften von Algorithmen vergleichen, wie z.B. n, n2, 2n…, vergleichen wir die entsprechenden Funktionen, die n Elemente konsumieren und obige Ergebnisse produzieren.
Dr. G. RößlingProf. Dr. M. Mühlhäuser
RBG / Telekooperation©
Grundlagen der Informatik I: T7
20
Überblick
• Abstraktes Zeit- und Komplexitätsmaß• O-Notation und andere Wachstumsmaße• Techniken zur Bestimmung der Komplexität• Vektoren in Scheme
Dr. G. RößlingProf. Dr. M. Mühlhäuser
RBG / Telekooperation©
Grundlagen der Informatik I: T7
21
O-Notation
• Funktionen für alle natürlichen Zahlen N zu vergleichen ist schwierig: – Die Domäne der natürlichen Zahlen ist unendlich– Wenn eine Funktion f größere Ausgaben produziert als
eine Funktion g für alle n in N, dann ist f eindeutig größer als g
– Aber was können wir aussagen, wenn dieser Vergleich für einige Eingaben fehlschlägt? Z.B. für 1000?
• Um abschätzende Aussagen zu treffen, übernehmen wir eine mathematische Notation, die zum Vergleichen von Funktionen – bis zu einem Faktor und – bis auf eine endliche Anzahl von
Ausnahmen verwendet wird
T
n10000
F
G
Dr. G. RößlingProf. Dr. M. Mühlhäuser
RBG / Telekooperation©
Grundlagen der Informatik I: T7
22
O-NotationGrößenordnung-von (Groß-O): Falls g eine Funktion auf den natürlichen Zahlen ist, so ist O(g) (ausgesprochen: „groß-O von g“) eine Klasse von Funktionen auf den natürlichen Zahlen.
Eine Funktion f ist in O(g), wenn es die Zahlen c und n0 = großGenug gibt, so dass für alle n > n0 gilt: f(n) <= cg(n)
Die „O-Notation“ geht auf den Zahlentheoretiker Edmund Landau (1877-1938) zurück; das "O" bezeichnet man daher auch als „Landau Symbol“Wir sagen: "f(n) wächst höchstens so schnell wie g(n)" (g ist eine obere Schranke für f)
Dr. G. RößlingProf. Dr. M. Mühlhäuser
RBG / Telekooperation©
Grundlagen der Informatik I: T7
23
O-Notation
f(n) O(g(n)), wenn zwei positive Konstanten c und n0 existieren, mit |f(n)| c |g(n)| für alle n n0
125 250 500 1000 2000
0
1000
2000
3000 c g(n)
f(n)
n0
Funktion g definiert die Komplexitäts-klasse
Funktion f verhält sich asymptotisch wie g; ab n0 gilt immer f(n) < c g(n)
f „ist höchstens so groß wie“ g (n)
Asymptotisches Maß (n ). Es abstrahiert von unwichtigen Details für die Bestimmung der Komplexitätsklasse.
Dr. G. RößlingProf. Dr. M. Mühlhäuser
RBG / Telekooperation©
Grundlagen der Informatik I: T7
24
O-Notation: Beispiele
• Für f(n) = 1000 n und g(n) = n2 können wir sagen, dass f in O(g) ist, weil für alle n > 1000 gilt,
• f(n) <= c.g(n) (n0 = 1000 und c = 1)
• Die Groß-O Notation bietet eine Kurzform an, um Aussagen über die Laufzeit von Funktionen zu treffen: – Die Laufzeit von length ist O(n). – Im schlechtesten Fall ist die Laufzeit von insertion-sort O(n2)
– Dabei sind n und n2 Standardabkürzungen für die (mathematischen) Funktionen f(n) = n und g(n) =n2
Dr. G. RößlingProf. Dr. M. Mühlhäuser
RBG / Telekooperation©
Grundlagen der Informatik I: T7
25
Komplexitätsklassen
• Polynomielles Wachstum (O(nx)) verkleinert die Größe sinnvoller Eingaben stark
• Exponentielles Wachstum (O(an)) noch stärker
O(n)
O(log n)
O(n log n)
O(n2) O(n3)
An
zah
l d
er
Verg
leic
he
Eingabegröße (n)
Dr. G. RößlingProf. Dr. M. Mühlhäuser
RBG / Telekooperation©
Grundlagen der Informatik I: T7
26
Eigenschaften der O-Notation
0
200
400
600
800
1000
1200
1400
1600
1800
1 3 5 7 9 11 13 15 17 19 21 23 25 27
Heap
Insertion
• Vergleiche der „O“ Komplexität sind nur sinnvoll für große Eingaben- Bei kleinen Eingaben kann ein ineffizienter Algorithmus
manchmal schneller sein als ein effizienter- Beispiel: eine Funktion
aus 2n2 wächst schneller als eine in (184 log2n), sie ist aber besser für kleinere Eingaben (n < 20)
• Insbesondere bei Algorithmen mit linearem oder schwächerem Wachstum können sich derartige Faktoren bemerkbar machen- Der Vergleich der Komplexitätsklasse ist in diesen Fällen
u.U. nicht ausreichend.
Dr. G. RößlingProf. Dr. M. Mühlhäuser
RBG / Telekooperation©
Grundlagen der Informatik I: T7
27
Eigenschaften der O-Notation• Die O-Notation blendet proportionale Faktoren,
kleine Eingaben und kleinere Terme aus
Beispiele:2n3+n2-20 O(n3) log10 n O(log2 n)
n + 10000 O(n) n O(n2)O(1) O(log n) O(n) O(n2) O(n3) O(2n) O(10n)
10125250500
10002000
0.1212.8
11.043.4
172.9690.5
f(n) an2
0.0172.7
10.843.1
172.4689.6
n2 - Ausdruck in %vom ganzen
f(n) = an2 + bn +cmit a = 0.0001724, b = 0.0004 und c = 0.1
14.294.798.299.399.799.9
n
Dr. G. RößlingProf. Dr. M. Mühlhäuser
RBG / Telekooperation©
Grundlagen der Informatik I: T7
28
O-Notation: andere Symbole
• Es gibt noch mehr Symbole für verschiedene Zwecke:– Asymptotische untere Schranke [f(n) (g(n))]:
• f(n) (g(n)), wenn positive Konstanten c und n0 N existieren, so dass 0 cg(n) f(n), n n0
• Wir sagen: „f(n) wächst mindestens so schnell wie g(n)“
– Asymptotisch exakte Schranke [f(n) (g(n))]: • f(n) (g(n)), wenn die positiven Kostanten c1, c2, und n0 N
existieren, so dass c1 g(n) f(n) c2 g(n), n n0
• f(n) (g(n)) genau dann, wenn
– f(n) O(g(n)) und f(n) (g(n)) • Wir sagen „f(n) wächst genauso schnell wie g(n)“
Dr. G. RößlingProf. Dr. M. Mühlhäuser
RBG / Telekooperation©
Grundlagen der Informatik I: T7
29
O-Notation: andere Symbole
• Schema für O, und :
obere Schranke
untere Schranke
exakte Schranke
n0n0 n0
Dr. G. RößlingProf. Dr. M. Mühlhäuser
RBG / Telekooperation©
Grundlagen der Informatik I: T7
30
Andere asymptotische Notationen
• Eine Funktion f(n) ist in o(g(n)), wenn es positive Konstanten c und n0 gibt, so dass
f(n) < c g(n) n n0
• Eine Funktion f(n) ist in (g(n)), wenn es positive Konstanten c und n0 gibt, so dass
c g(n) < f(n) n n0
• Intuitiv:
o() ist ähnlich < O() ist ähnlich
() ist ähnlich > () ist ähnlich () ist ähnlich =
Dr. G. RößlingProf. Dr. M. Mühlhäuser
RBG / Telekooperation©
Grundlagen der Informatik I: T7
31
Übersicht
• Abstraktes Zeit- und Komplexitätsmaß• O-Notation und andere Wachstumsmaße• Techniken zur Bestimmung der Komplexität• Vektoren in Scheme
Dr. G. RößlingProf. Dr. M. Mühlhäuser
RBG / Telekooperation©
Grundlagen der Informatik I: T7
33
Beispiel: Exponentieren
• Eingabe: Basis b und positiver ganzzahliger Exponent n
• Ausgabe: bn
• Idee: bn = b* b(n-1) , b0 = 1
• Angenommen die Multiplikation benötigt eine konstante Zeit c
• Dann gilt T(n) = cn = O(n)
(define (expt b n) (cond [(= n 0) 1] [else (* b (expt b (- n 1)))]))
Dr. G. RößlingProf. Dr. M. Mühlhäuser
RBG / Telekooperation©
Grundlagen der Informatik I: T7
34
Beispiel: Exponentieren
• Idee: Weniger Schritte durch sukzessives Quadrieren– Statt b8 als b*b*b*b*b*b*b*b zu berechnen, können
wir es auch so machen:b2 = b*b, b4 = (b2)2, b8 = (b4)2
– Generell gilt die Regel• bn = (bn/2) 2 wenn n gerade ist
bn = b*bn-1 wenn n ungerade ist
• Zu welcher Komplexitätsklasse gehört dieser Algorithmus?
(define (fast-expt b n) (cond [(= n 0) 1] [(even? n) (sqr (fast-expt b (/ n 2)))) (else (* b (fast-expt b (- n 1))))))
Dr. G. RößlingProf. Dr. M. Mühlhäuser
RBG / Telekooperation©
Grundlagen der Informatik I: T7
35
Analyse von Teile-und-Herrsche Algorithmen
• Für rekursive Algorithmen kann die Laufzeit oft als Rekurrenzgleichung (Rekurrenz) beschrieben werden– Gesamtlaufzeit wird mittels der Laufzeit für kleinere
Eingaben definiert– Beispiel:
• Problem (n) wird in 2 Teilprobleme (n/2) zerlegt• Aufwand cn für Zerlegung und Kombination der
Teillösungen
• Eine Rekurrenz T(n) für die Laufzeit eines Teile-und-Herrsche Algorithmus der Größe n basiert auf den drei Schritten des Paradigma…
1
22
1
)(ncn
nT
nc
nT
Dr. G. RößlingProf. Dr. M. Mühlhäuser
RBG / Telekooperation©
Grundlagen der Informatik I: T7
36
Analyse von Teile-und-herrsche Algorithmen
• Fall 1: Die Problemgröße ist klein genug, sagen wir n <= c für eine Konstante c, so dass es trivial gelöst werden kann Lösung benötigt konstante Zeit (1)
• Fall 2: Das Problem ist nicht-trivial:– Die Teilung des Problems ergibt a Teilprobleme, die
alle 1/b der Größe des Originals haben• Beispiel: für merge-sort haben wir a = b = 2
– D(n): Aufwand für die Zerlegung in Teilprobleme– C(n): Aufwand für das Kombinieren der Teillösungen
sonstnCnD
b
naT
cn
nT)()(
)1(
)(
Dr. G. RößlingProf. Dr. M. Mühlhäuser
RBG / Telekooperation©
Grundlagen der Informatik I: T7
37
Die Türme von Hanoi!
Das „Türme von Hanoi“ Puzzle wurde 1883 vom französischen Mathematiker Édouard Lucas erfunden.
Wir bekommen einen Turm von Scheiben, in größer werdender Reihenfolge auf einen der drei Stäbe gesteckt.
Das Ziel ist, den ganzen Turm auf einen der anderen Stäbe zu bringen, wobei jeweils nur eine Scheibe bewegt und niemals eine größere auf eine kleinere Scheibe gelegt werden darf.
Dr. G. RößlingProf. Dr. M. Mühlhäuser
RBG / Telekooperation©
Grundlagen der Informatik I: T7
38
Die Türme von Hanoi: Algorithmus1
2 3
Um n Scheiben von Stange A zu Stange B zu bewegen:1. Bewege n−1 Scheiben von A nach C. Damit bleibt Scheibe #n
auf A2. Bewege Scheibe #n von A nach B 3. Bewege n−1 Scheiben von C nach B, so dass sie auf Scheibe
#n sitzen
A B C
Rekursiver Algorithmus: Um Schritte 1 und 3 auszuführen, wende den gleichen Algorithmus wieder für n-1 an. Die gesamte Prozedur ist eine endliche Anzahl von Schritten, denn irgendwann wird der Algorithmus für n = 1 angewendet werden. Dieser Schritt, eine einzelne Scheibe zu verschieben, ist trivial.
n
Dr. G. RößlingProf. Dr. M. Mühlhäuser
RBG / Telekooperation©
Grundlagen der Informatik I: T7
39
Die Türme von Hanoi
(define (move T1 T2 T3 n) (cond [(= n 0) empty] [else (append (move T1 T3 T2 (- n 1)) (list (list T1 T2)) (move T3 T2 T1 (- n 1))) ] ))
(move 'A 'B 'C 4)
(list (list 'A 'C) (list 'A 'B) (list 'C 'B) (list 'A 'C) (list 'B 'A) (list 'B 'C) (list 'A 'C) (list 'A 'B) (list 'C 'B) (list 'C 'A) (list 'B 'A) (list 'C 'B) (list 'A 'C) (list 'A 'B) (list 'C 'B))
Ausgegeben wird die Liste der Scheibenbewegungen
A B C
Wie viele Scheibenbewegungen sind erforderlich, um einen Stapel der Höhe n zu
bewegen?
Dr. G. RößlingProf. Dr. M. Mühlhäuser
RBG / Telekooperation©
Grundlagen der Informatik I: T7
40
Rekursive Komplexitätsfunktionfür die Türme von Hanoi
= 2n×T(0) + 2n-1 = 2n-1 => exponentielle Komplexität!
T(n) = T(n-1)+1+T(n-1) = 2×T(n-1)+1= 2×(2×T(n-2)+1)+1 = 2×(2×(2×T(n-
3)+1)+1)+1= 2i×T(n-i) + , für i=n, n-i wird 0
0å=
2ki-1
k
• Wie viele Umlagerungen von Scheiben sind notwendig …?
- für n < 2 ist die Antwort einfach: T(0)=0, T(1)=1- für n > 1 ist die Antwort rekursiv definiert:
Dr. G. RößlingProf. Dr. M. Mühlhäuser
RBG / Telekooperation©
Grundlagen der Informatik I: T7
41
Wenn das Universum sein Ende finden wird…
Es gibt eine Legende über ein buddhistisches Kloster bei Hanoi, in dem sich ein riesiger Raum mit drei abgenutzten Pfosten befindet, die von 64 goldenen Scheiben umgeben waren.
– Seit der Gründung des Klosters vor über tausend Jahren führen Mönche die Anordnung einer alten Prophezeiung aus:
• Sie bewegen die Scheiben in Übereinstimmung mit den Regeln des Puzzles
• Jeden Tag bewegen die Mönche eine Scheibe– Man sagt, sie glauben, wenn die letzte Bewegung
ausgeführt würde, wird die Welt mit einem Donnerschlag untergehen.
Dr. G. RößlingProf. Dr. M. Mühlhäuser
RBG / Telekooperation©
Grundlagen der Informatik I: T7
42
Wenn das Universum sein Ende finden wird…
• Zum Glück sind sie nicht mal annäherungsweise fertig
• Angenommen, die Legende wäre wahr und die Mönche könnten eine Scheibe pro Sekunde bewegen, mit der kleinsten Anzahl an nötigen Bewegungen:– Dann bräuchten sie zur Lösung 264−1 Sekunden -
das sind etwa 585 Milliarden Jahre– Unser Universum ist zur Zeit ungefähr 13,7
Milliarden Jahre alt
Dr. G. RößlingProf. Dr. M. Mühlhäuser
RBG / Telekooperation©
Grundlagen der Informatik I: T7
43
Analyse von Merge Sort
• Vereinfachung: Größe des ursprünglichen Problems ist eine Potenz von 2– Jeder Teilung liefert zwei Teilsequenzen von Länge n/2– Es gibt Beweise, dass eine solche Annahme die
Komplexitätsklasse der Lösung zur Rekurrenz nicht beeinflusst
• Worst case: n > 1 – Teile: Das Extrahieren der Elemente der beiden Teillisten
benötigt jeweils Zeit der Ordnung n D(n) = 2n ~ (n)– Herrsche: Das rekursive Lösen der 2 Teilprobleme dauert 2T(n/2)
– Kombiniere: Zusammenfügen der beiden Listen benötigt auch (n)
1)(
22
1)1(
)(nn
nT
n
nTworst-case Laufzeit für merge sort
Dr. G. RößlingProf. Dr. M. Mühlhäuser
RBG / Telekooperation©
Grundlagen der Informatik I: T7
44
Lösen von Rekurrenzen• Frage: Wie löst man Rekurrenzen wie diese?• Antwort: Mathematische Methoden die uns dabei
helfen:– Substitutionsmethode– Rekursionsbaum-Methode– Master-Methode basierend auf dem Master-Theorem
• Eine „Kochbuch“-Methode, um Rekurrenzen der Form T(n) = aT(n/b)+f(n) zu lösen, a 1, b>1, f(n) asymptotisch positive Funktion
• Kann benutzt werden, um zu zeigen, dass T(n) von merge sort in (n log n) ist
• Dabei vernachlässigen wir technische Details:– Wir ignorieren Rundungen nach unten und oben
(absorbiert durch O- oder -Q Notation)– Wir nehmen ganzzahlige Argumente für Funktionen an– Wir vernachlässigen Grenzbedingungen
Dr. G. RößlingProf. Dr. M. Mühlhäuser
RBG / Telekooperation©
Grundlagen der Informatik I: T7
45
Das Master-Theorem
• Wenn für eine Konstante e > 0,
dann
• Wenn , dann
• Wenn für eine Konstante e > 0 und wenn a f(n/b) <= c f(n) für eine Konstante c < 1 und alle hinreichend großen n, dann T(n) =Q(f(n))
)()( log abnOnf)()( log abnnT
)()( log abnnf )log()( log nnnT bab
)()( log abnnf
)()/(
)1()(
nfbnaTnT
falls n < c
falls n > 1
Betrachte
wobei a >= 1 und b >= 1
Dr. G. RößlingProf. Dr. M. Mühlhäuser
RBG / Telekooperation©
Grundlagen der Informatik I: T7
46
Die Rekursionsbaum-Methode
• In einem Rekursionsbaum repräsentiert jeder Knoten die Kosten eines Teilproblems in der Kette der rekursiven Funktionsapplikationen– Summiere Kosten auf jeder Ebene, um Kosten pro Ebene zu
bekommen– Summiere alle Kosten pro Ebenen, um Gesamtkosten zu
ermitteln• Besonders nützlich für Rekurrenzen, welche die
Laufzeit von Teile-und-herrsche Algorithmen beschreiben
• Oftmals verwendet, um eine gute Annäherung zu finden, die dann mit anderen Methoden verifiziert wird– Wenn sorgfältig entworfen, kann sie auch als direkter
Beweis einer Lösung für eine Rekurrenz dienen
Dr. G. RößlingProf. Dr. M. Mühlhäuser
RBG / Telekooperation©
Grundlagen der Informatik I: T7
47
Rekursionsbaum für Merge SortSchreiben wir die Rekurrenz für merge-sort wie
folgt:
1
22
1
)(ncn
nT
nc
nT
T(n/2)
cn
T(n/2)
Baum für die erste Applikation
T(n/4)
cn
cn/2 cn/2
T(n/4) T(n/4) T(n/4)
Baum für zwei Applikationsschritte
Dr. G. RößlingProf. Dr. M. Mühlhäuser
RBG / Telekooperation©
Grundlagen der Informatik I: T7
48
Rekursionsbaum für Merge Sort
cn
cn/2 cn/2
cn/4 cn/4 cn/4 cn/4
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
c c c c c c c c
n
log n + 1Ebene
(Induktion)
cn
cn
cn
cn
...
Gesamt:cn (log n + 1)
2ic(n/2i)
...
Ebene i 2i Knoten
Dr. G. RößlingProf. Dr. M. Mühlhäuser
RBG / Telekooperation©
Grundlagen der Informatik I: T7
49
Die Substitutionsmethode
• Auch bekannt als die “making a good guess method” („eine gute Annäherung finden“ - Methode)
• Funktionsweise:– Rate die Form der Antwort, – Benutze Induktion, um die Konstanten zu finden und
zeige, dass die Lösung funktioniert• Beispiele:
• T(n) = 2T(n/2) + (n) T(n) = (n log n)• T(n) = 2T(n/2) + n ???• T(n) = 2T(n/2 )+ 17) + n ???
• T(n) = 2T(n/2) + n T(n) = (n log n)• T(n) = 2T(n/2+ 17) + n (n log
n)
Dr. G. RößlingProf. Dr. M. Mühlhäuser
RBG / Telekooperation©
Grundlagen der Informatik I: T7
50
Die Substitutionsmethode
nnTnT )2/(2)(Geschätzte Lösung:
)log()( nnnT
Zu zeigen ist, dass für eine geeignete Konstante c > 0ncnnT lg)(
Anfangsannahme: die Schranke gilt für 2/n
)2/lg(2/)2/( nncnT also:
1c
222lg2)2(
42)1(2)2(2
cccT
TTn
Lösung: die Abschätzungist für n>n0 zu zeigen
???01log)1(11 1 cTn
Rekurrenz:
T(n) 2T n /2 n
2 c n /2 log n /2 n
cn log n /2 n
cn log n cn log2 n
cn log n cn n
cn log n
Dr. G. RößlingProf. Dr. M. Mühlhäuser
RBG / Telekooperation©
Grundlagen der Informatik I: T7
51
Performanz von Quicksort: bester FallDie Laufzeit von quicksort hängt von der Qualität der Partitionierung ab, d.h., von den Pivot-Elementen
)()2/(2)( nnTnT
T(n) (n log n)Master
Theore
m
• Bester Fall: die Partitionierung erzeugt in jedem Schritt zwei Teilprobleme der Größe n/2
Dr. G. RößlingProf. Dr. M. Mühlhäuser
RBG / Telekooperation©
Grundlagen der Informatik I: T7
52
Performanz von Quicksort: schlechtester Fall• Schlechtester Fall: die Partitionierung erzeugt in
jedem Rekursionsschritt ein Teilproblem mit n-1 Elementen und eines mit 0 Elementen
)()()()(1 22
1
nnnnknn
k
Der schlechteste Fall tritt ein, wenn die Liste bereits sortiert ist!
nn - 1
n - 2
n - 3
2
1
1
1
1
1
1
n
nnn - 1
n - 2
3
2
(n2)
☞ T(n)=T(n-1)+T(0)+(n)
= T(n-1)+(n)- Die aufsummierten Kosten
ergeben eine arithmetische Reihe, die (n2)ergibt
Sei D(n) = (n); Für die leere Liste T(0) = (1)
Dr. G. RößlingProf. Dr. M. Mühlhäuser
RBG / Telekooperation©
Grundlagen der Informatik I: T7
53
Performanz von Quicksort
• Im Durchschnitt ist quicksort deutlich näher am besten als am schlechtesten Fall. Um n Elemente zu sortieren, nimmt es Θ(n log n) Vergleiche vor.
• Um das nachzuvollziehen, muss man verstehen, wie die Balance ("Ausgewogenheit") der Partitionierung sich in der Rekurrenz für quicksort wiederfindet
• Ausgewogene Partitionierung: die Partitionierung erzeugt immer eine konstante Aufteilung
Dr. G. RößlingProf. Dr. M. Mühlhäuser
RBG / Telekooperation©
Grundlagen der Informatik I: T7
Performanz von Quicksort:ausgewogene Partitionierung
9-zu-1-Aufteilung erscheint ziemlich unausgewogen
T(n) = T(9n/10) + T(n/10) + n
54
(logn)
Sogar eine 99:1-Aufteilung ergibt O(n log n)
Der Grund: Aufteilungen mit konstanten Proportionen ergeben Rekursions- bäume der Tiefe (log n) mit Kosten von O(n) auf
jeder Ebene
Dr. G. RößlingProf. Dr. M. Mühlhäuser
RBG / Telekooperation©
Grundlagen der Informatik I: T7
55
Performanz von Quicksort• Durchschnittlicher Fall
– Alle Permutationen der Eingabezahlen sind gleich wahrscheinlich
– Bei einer zufälligen Eingabeliste wird eine Mischung von ausgewogenen und unausgewogenen Aufteilungen vorliegen
– Gute und schlechte Aufteilungen sind zufällig über den Baum verteilt
abwechselnd gute undschlechte Aufteilung
nahezu ausgewogeneAufteilung
nn - 11
(n – 1)/2(n – 1)/2
Die Laufzeit von quicksort bei abwechselnd guten und schlechten Aufteilungen ist O(n log n)
Gesamtkosten:2n-1 = (n)
Gesamtkosten:n = (n)n
(n – 1)/2(n – 1)/2 + 1
Dr. G. RößlingProf. Dr. M. Mühlhäuser
RBG / Telekooperation©
Grundlagen der Informatik I: T7
56
Performanz von Quicksort
• Typischerweise ist quicksort im praktischen Einsatz schneller als andere Θ(n log n)-Algorithmen– Seine innere Schleife kann auf den meisten
Architekturen effizient implementiert werden– Die meisten in der Praxis auftretenden Daten erlauben
Entwürfe, welche die Wahrscheinlichkeit des Auftretens quadratischer Komplexität minimieren
Dr. G. RößlingProf. Dr. M. Mühlhäuser
RBG / Telekooperation©
Grundlagen der Informatik I: T7
57
Zusammenfassung der Berechnungskosten
• Algorithmen können nach ihrer Komplexität eingeteilt werden O-Notation– Nur relevant für große Eingaben
• Maße sind maschinenunabhängig– Zählen der Operationen im Verhältnis zur Größe der
Eingabe– Analyse für den schlechtesten, durchschnittlichen,
besten Fall• Algorithmen variieren sehr stark in ihrer Effizienz
– Gute Programmierung ein oder zwei Komplexitätsklassen weniger
– Manche Probleme sind in sich komplex
Dr. G. RößlingProf. Dr. M. Mühlhäuser
RBG / Telekooperation©
Grundlagen der Informatik I: T7
58
Überblick
• Abstraktes Zeit- und Komplexitätsmaß• O-Notation und andere Wachstumsmaße• Techniken zur Bestimmung der Komplexität• Vektoren in Scheme
Dr. G. RößlingProf. Dr. M. Mühlhäuser
RBG / Telekooperation©
Grundlagen der Informatik I: T7
59
Die Kosten der Suche in Listen
Rückbesinnung auf das Beispiel der Pfadsuche in Graphen:
(define (find-route origination destination G) (cond [(symbol=? origination destination)
(list destination)] [else (local ((define possible-route
(find-route/list (neighbors origination G)
destination G))) (cond
[(boolean? possible-route) false] [else (cons origination possible-route)]))]))
Dr. G. RößlingProf. Dr. M. Mühlhäuser
RBG / Telekooperation©
Grundlagen der Informatik I: T7
60
Die Kosten der Suche in Listen
;; neighbors : node graph -> (listof node);; to lookup the node in graph(define (neighbors node graph) (cond [(empty? graph) (error “no neighbors")] [(symbol=? (first (first graph)) node) (second (first graph))] [else (neighbors node (rest graph))]))
neighbors ist der Funktion contains-doll? ähnlich,
d.h. neighbors ist in O(n)
Dr. G. RößlingProf. Dr. M. Mühlhäuser
RBG / Telekooperation©
Grundlagen der Informatik I: T7
61
Die Kosten der Suche in ListenDie Komplexität von neighbors ist O(n)
neighbors wird in jedem Schritt von find-route benutzt, also n mal im Fall eines maximalen Pfades
Der Algorithmus benötigt in neighbors O(n2) Schritte
neighbors kann der Flaschenhals von find-route sein!
• Es wird eine Datenstruktur benötigt, die den Zugriff auf die Nachbarn eines Knotens durch dessen Namen in konstanter Zeit erlaubt
• Vektoren sind Datenstrukturen in Scheme, die Elementzugriffe in konstanter Zeit ermöglichen.
Dr. G. RößlingProf. Dr. M. Mühlhäuser
RBG / Telekooperation©
Grundlagen der Informatik I: T7
62
Operationen auf Vektoren• vector erzeugt einen Vektor aus gegebenen
Werten:
• build-vector ist das Vektor-Analog zu build-list:
(vector V-0 ... V-n)
(build-vector n f) = (vector (f 0) ... (f (- n 1)))
• vector-ref extrahiert einen Wert aus einem Vektor
• vector-length liefert die Anzahl der Elemente:
• vector? ist das Vektor-Prädikat:
(vector-length (vector V-0 ... V-n)) = (+ n 1)
(vector? (vector V-0 ... V-n)) = true (vector? U) = false
(vector-ref (vector V-0 ... V-n) i) = V-i, 0 ≤ i ≤ n
Dr. G. RößlingProf. Dr. M. Mühlhäuser
RBG / Telekooperation©
Grundlagen der Informatik I: T7
63
Graphen als Vektoren
(define Graph-as-list '((A (B E)) (B (E F)) (C (D)) (D ()) (E (C F)) (F (D G)) (G ())))
(define Graph-as-vector (vector (list 1 4) (list 4 5) (list 3) empty (list 2 5) (list 3 6) empty))
A B C D E F G
0 1 2 3 4 5 6
Zur Darstellung der Graphenknoten können Zahlenverwendet werden:
Listenbasierte Darstellung:
Vektorbasierte Darstellung:
Das i-te Feld des Vektors enthält die Liste der Nachbarn des i-ten
Knotens
Dr. G. RößlingProf. Dr. M. Mühlhäuser
RBG / Telekooperation©
Grundlagen der Informatik I: T7
64
Graphen als Vektoren• Ein Knoten ist eine
natürliche Zahl zwischen 0 und n – 1, wobei n dieAnzahl der Knoten ist
• Ein Graph ist ein Vektor von Knoten:
• Jetzt ist neighbors für einen Knoten in konstanter Zeit ausführbar
=> Diese Operation kann bei der Betrachtung des abstrakten Zeitmaßes von find-route ignoriert werden. ;; neighbors : node graph -> (listof node)
;; to lookup the node in graph(define (neighbors node graph) (vector-ref graph node))
(vectorof (listof node))
A B C D E F G
0 1 2 3 4 5 6
Dr. G. RößlingProf. Dr. M. Mühlhäuser
RBG / Telekooperation©
Grundlagen der Informatik I: T7
65
Graphen als Vektoren
• Die neighbors eines Knoten sind nun eine Operation mit konstanter Laufzeit
=> Wir können sie bei der Betrachtung der abstrakten Laufzeit von find-route ignorieren.
;; neighbors : node graph -> (listof node);; to lookup the node in graph(define (neighbors node graph) (vector-ref graph node))
Dr. G. RößlingProf. Dr. M. Mühlhäuser
RBG / Telekooperation©
Grundlagen der Informatik I: T7
66
Verarbeitung von Vektoren
Beispiel: Die Funktion vector-sum-for-3 übernimmt aus drei Zahlen bestehende Vektoren und liefert deren Summe zurück:
;; (vector number number number) -> number(define (vector-sum-for-3 v) (+ (vector-ref v 0) (vector-ref v 1) (vector-ref v 2)))
Mit Vektoren programmieren heißt, mit vector-ref zu programmieren – man betrachtet Vektoren und Indizes in Vektoren.
Dr. G. RößlingProf. Dr. M. Mühlhäuser
RBG / Telekooperation©
Grundlagen der Informatik I: T7
67
Verarbeitung von VektorenDie allgemeinere Funktion vector-sum verarbeitet Vektoren beliebiger Größe:;; vector-sum : (vectorof number) -> number;; to sum up the numbers in v(define (vector-sum v) ...)
(= 0 (vector-sum (vector -1 3/4 1/4)))
(= 1 (vector-sum (vector .1 .1 .1 .1 .1 .1 .1 .1 .1 .1))
(= 0 (vector-sum (vector)))
Ein paar Beispiele:
Dr. G. RößlingProf. Dr. M. Mühlhäuser
RBG / Telekooperation©
Grundlagen der Informatik I: T7
68
Verarbeitung von Vektoren
vector-sum erhält nicht die Anzahl der zu verarbeitenden Elemente. Eine Hilfsfunktion mit einem solchen Argument ist zu definieren:
Dann ist vector-sum wie folgt definiert:
(define (vector-sum v) (vector-sum-aux v (vector-length v)))
;; (vectorof number) N -> number;; to sum up the numbers in v with index in;;[i, (vector-length v))(define (vector-sum-aux v i) ...)
Dr. G. RößlingProf. Dr. M. Mühlhäuser
RBG / Telekooperation©
Grundlagen der Informatik I: T7
69
Verarbeitung von VektorenZunächst entwerfen wir eine Schablone für diese Funktion.Die Implementierung von vector-sum-for-3 legt nahe, dass i die Veränderliche in der Schablone ist.
Die Schablone legt nahe, dass i die Anzahl der Elemente von v bezeichnet, die vector-sum-aux berücksichtigen muss.
;; (vectorof number) n -> number;; to sum up the numbers in v with index in [0, i) (define (vector-sum-aux v i) (cond [(zero? i) ...] [else ... (vector-sum-aux v (pred i)) ...]))
Dr. G. RößlingProf. Dr. M. Mühlhäuser
RBG / Telekooperation©
Grundlagen der Informatik I: T7
70
Verarbeitung von Vektoren
1. Falls i gleich 0 ist, so müssen keine weiteren Elemente berücksichtigt werden => Das Ergebnis ist 0.
2. Andernfalls – Berechne die Summe der Zahlen in v mit Index kleiner als
i-1:
– Nimm den Wert des Vektorfelds mit dem Index i-1:
Das Ergebnis ist ihre Summe:
(vector-sum-aux v (pred i))
(vector-ref v (pred i))
(+ (vector-ref v (pred i)) (vector-sum-aux v (pred i))
Dr. G. RößlingProf. Dr. M. Mühlhäuser
RBG / Telekooperation©
Grundlagen der Informatik I: T7
71
Verarbeitung von Vektoren
;; (vectorof number) -> number;; to compute the sum of the numbers in v(define (vector-sum v) (vector-sum-aux v (vector-length v)))
;; (vectorof number) n -> number;; to sum the numbers in v with index in [0, i)(define (vector-sum-aux v i) (cond [(zero? i) 0] [else (+ (vector-ref v (pred i))
(vector-sum-aux v (pred i)))]))
vector-sum-aux extrahiert die Zahlen von rechts nach links aus dem Vektor, wobei i in Richtung 0 schrumpft
Dr. G. RößlingProf. Dr. M. Mühlhäuser
RBG / Telekooperation©
Grundlagen der Informatik I: T7
72
Verarbeitung von VektorenDie Summe kann auch von links nach rechts berechnet werden:
;; lr-vector-sum : (vectorof number) -> number;; to sum up the numbers in v(define (lr-vector-sum v) (vector-sum-aux v 0))
;; vector-sum : (vectorof number) -> number;; to sum up the numbers in v with index in ;; [i, (vector-length v))(define (vector-sum-aux v i) (cond [(= i (vector-length v)) 0] [else (+ (vector-ref v i) (vector-sum-aux v (succ i)))]))
Dr. G. RößlingProf. Dr. M. Mühlhäuser
RBG / Telekooperation©
Grundlagen der Informatik I: T7
73
Vektoren erstellen
• In den nächsten Folien werden wir kurz betrachten, wie man Vektoren erstellt….
• Zur Illustration entwickeln wir eine Funktion, welche die Elemente eines angegebenen Vektors mit einer bestimmten Geschwindigkeit verschiebt
Dr. G. RößlingProf. Dr. M. Mühlhäuser
RBG / Telekooperation©
Grundlagen der Informatik I: T7
74
Vektoren erstellenDie Geschwindigkeit eines Objekts kann durch einen Vektor repräsentiert werden:
– (vector 1 2) – die Geschwindigkeit eines Objekts in der Ebene, das sich je Zeiteinheit um 1 Einheit nach rechts und 2 nach unten bewegt.
– (vector -1 2 1) – Geschwindigkeit im Raum; -1 Einheiten in x-Richtung, 2 Einheiten in y-Richtung, und 1 Einheit in z-Richtung.
Entwickeln wir nun eine Funktion zur Berechnung der Verschiebung (displacement) eines Objekts mit der Geschwindigkeit v in t Zeiteinheiten:
;; (vectorof number) number -> (vectorof number);; to compute the displacement of v and t(define (displacement v t) ...)
Dr. G. RößlingProf. Dr. M. Mühlhäuser
RBG / Telekooperation©
Grundlagen der Informatik I: T7
75
Vektoren erstellen
• Ein paar Beispiele
(equal? (displacement (vector 1 2) 3) (vector 3 6))
(equal? (displacement (vector -1 2 1) 6) (vector -6 12 6))
(equal? (displacement (vector -1 -2) 2) (vector -2 -4))
Um das Ergebnis zu berechnen, multiplizieren wir jede Komponente des Geschwindigkeitsvektors mit der Zeit t
Dr. G. RößlingProf. Dr. M. Mühlhäuser
RBG / Telekooperation©
Grundlagen der Informatik I: T7
76
Vektoren erstellen
(build-vector (vector-length v) ...)
;; new-item : n -> number(define (new-item index) ...)
;; (vectorof number) number -> (vectorof number);; to compute the displacement of v and t(define (displacement v t) (local ((define (new-item i) (* (vector-ref v i) t))) (build-vector (vector-length v) new-item)))
Wir konstruieren einen Vektor mit der gleichen Länge wie v:
Wir müssen ... mit einer Funktion ersetzen, die die 0te, 1te, … Komponente des neuen Vektors berechnet:
Dann multiplizieren wir (vector-ref v i) mit t – fertig!
Dr. G. RößlingProf. Dr. M. Mühlhäuser
RBG / Telekooperation©
Grundlagen der Informatik I: T7
77
Vektoren erstellen
Da die lokale Funktion new-item nicht rekursiv ist, können wir sie mit einem lambda-Ausdruck ersetzen
In der Mathematik nennen wir dies ein SkalarproduktDiese und viele andere mathematische Operationen mit Vektoren sind direkt in Scheme ausdrückbar.
;; (vectorof number) number -> (vectorof number);; to compute the displacement of v and t(define (displacement v t) (build-vector (vector-length v) (lambda (i) (* (vector-ref v i) t))))