LS 2 /
Informatik
Datenstrukturen, Algorithmen und Programmierung 2 (DAP2)
LS 2 /
Informatik
Organisatorisches
Heimübungsblatt 4


Aufgabe 1 wurde ausgetauscht
Falls Sie die alte 1 bereits gemacht haben, geben Sie sie mit ab
Praktikum


Ab dem nächsten Blatt (Blatt 9) fließt nur noch eine Aufgabe der
Präsenzübung in die Wertung ein
Weitere Aufgaben sind optional
2
LS 2 /
Informatik
Stand der Dinge
Gierige Algorithmen

Konstruiere Lösung Schritt für Schritt

In jedem Schritt: Optimiere ein einfaches, lokales Kriterium
Beobachtung

Man kann viele unterschiedliche gierige Algorithmen für ein Problem
entwickeln

Nicht jeder dieser Algorithmen löst das Problem korrekt
3
LS 2 /
Informatik
Gierige Algorithmen
Scheduling mit Deadlines
•
Resource (Hörsaal, Parallelrechner, Elektronenmikroskop,..)
•
Anfragen: Aufgabe, die Zeit t benötigt und bis Zeitpunkt d
bearbeitet sein soll
Länge 1 Deadline 2
Aufgabe 1 1
Deadline 4
Länge 2
2
Aufgabe 2
Deadline 6
Länge 3
3
Aufgabe 3
4
LS 2 /
Informatik
Gierige Algorithmen
Scheduling mit Deadlines
•
Resource (Hörsaal, Parallelrechner, Elektronenmikroskop,..)
•
Anfragen: Aufgabe, die Zeit t benötigt und bis Zeitpunkt d
bearbeitet sein soll
Länge 1 Deadline 2
Aufgabe 1 1
Deadline 4
Länge 2
2
Aufgabe 2
Deadline 6
Länge 3
3
Aufgabe 3
O.b.d.A. Resource steht ab
Zeitpunkt 0 zur Verfügung
5
LS 2 /
Informatik
Gierige Algorithmen
Scheduling mit Deadlines
•
Resource (Hörsaal, Parallelrechner, Elektronenmikroskop,..)
•
Anfragen: Aufgabe, die Zeit t benötigt und bis Zeitpunkt d
bearbeitet sein soll
Länge 1 Deadline 2
Aufgabe 1 1
Deadline 4
Länge 2
2
Aufgabe 2
Deadline 6
Länge 3
3
Aufgabe 3
1
Aufgabe 1: Fertig
zu Zeitpunkt 1
6
LS 2 /
Informatik
Gierige Algorithmen
Scheduling mit Deadlines
•
Resource (Hörsaal, Parallelrechner, Elektronenmikroskop,..)
•
Anfragen: Aufgabe, die Zeit t benötigt und bis Zeitpunkt d
bearbeitet sein soll
Länge 1 Deadline 2
Aufgabe 1 1
Deadline 4
Länge 2
2
Aufgabe 2
Aufgabe 2: Fertig
Deadline
6
Länge 3
zu Zeitpunkt 3
3
Aufgabe 3
1
2
Aufgabe 1: Fertig
zu Zeitpunkt 1
7
LS 2 /
Informatik
Gierige Algorithmen
Scheduling mit Deadlines
•
Resource (Hörsaal, Parallelrechner, Elektronenmikroskop,..)
•
Anfragen: Aufgabe, die Zeit t benötigt und bis Zeitpunkt d
bearbeitet sein soll
Länge 1 Deadline 2
Aufgabe 1 1
Deadline 4
Länge 2
2
Aufgabe 2
Aufgabe 2: Fertig
Deadline
6
Länge 3
zu Zeitpunkt 3
3
Aufgabe 3
1
2
Aufgabe 1: Fertig
zu Zeitpunkt 1
3
Aufgabe 3: Fertig
zu Zeitpunkt 6
8
LS 2 /
Informatik
Gierige Algorithmen
Scheduling mit Deadlines
•
Resource (Hörsaal, Parallelrechner, Elektronenmikroskop,..)
•
Anfragen: Aufgabe, die Zeit t benötigt und bis Zeitpunkt d
bearbeitet sein soll
Länge 1 Deadline 2
Alle Aufgaben sind rechtzeitig fertig!
Aufgabe 1 1
Deadline 4
Länge 2
2
Aufgabe 2
Aufgabe 2: Fertig
Deadline
6
Länge 3
zu Zeitpunkt 3
3
Aufgabe 3
1
2
Aufgabe 1: Fertig
zu Zeitpunkt 1
3
Aufgabe 3: Fertig
zu Zeitpunkt 6
9
LS 2 /
Informatik
Gierige Algorithmen
Scheduling mit Deadlines
•
Resource (Hörsaal, Parallelrechner, Elektronenmikroskop,..)
•
Anfragen: Aufgabe, die Zeit t benötigt und bis Zeitpunkt d
bearbeitet sein soll
Länge 1 Deadline 4
1
Aufgabe 1
Deadline 4
Länge 2
2
Aufgabe 2
Deadline 6
Länge 3
3
Aufgabe 3
10
LS 2 /
Informatik
Gierige Algorithmen
Scheduling mit Deadlines
•
Resource (Hörsaal, Parallelrechner, Elektronenmikroskop,..)
•
Anfragen: Aufgabe, die Zeit t benötigt und bis Zeitpunkt d
bearbeitet sein soll
Länge 1 Deadline 4
1
Aufgabe 1
Deadline 4
Länge 2
2
Aufgabe 2
Deadline 6
Länge 3
3
Aufgabe 3
1
11
LS 2 /
Informatik
Stand der Dinge
Scheduling mit Deadlines
•
Resource (Hörsaal, Parallelrechner, Elektronenmikroskop,..)
•
Anfragen: Aufgabe, die Zeit t benötigt und bis Zeitpunkt d
bearbeitet sein soll
Länge 1 Deadline 4
1
Aufgabe 1
Deadline 4
Länge 2
2
Aufgabe 2
Deadline 6
Länge 3
3
Aufgabe 3
1
2
12
LS 2 /
Informatik
Stand der Dinge
Scheduling mit Deadlines
•
Resource (Hörsaal, Parallelrechner, Elektronenmikroskop,..)
•
Anfragen: Aufgabe, die Zeit t benötigt und bis Zeitpunkt d
bearbeitet sein soll
Länge 1 Deadline 4
1
Aufgabe 1
Deadline 4
Länge 2
Aufgabe 2
2
Aufgabe 2
wird zu spät
Deadline 6
Länge 3
beendet
3
Aufgabe 3
1
2
13
LS 2 /
Informatik
Gierige Algorithmen
Scheduling mit Deadlines
•
Resource (Hörsaal, Parallelrechner, Elektronenmikroskop,..)
•
Anfragen: Aufgabe, die Zeit t benötigt und bis Zeitpunkt d
bearbeitet sein soll
Länge 1 Deadline 4
1
Aufgabe 1
Deadline 4
Länge 2
2
Aufgabe 2
Deadline 6
Länge 3
3
Aufgabe 3
2
14
LS 2 /
Informatik
Gierige Algorithmen
Scheduling mit Deadlines
•
Resource (Hörsaal, Parallelrechner, Elektronenmikroskop,..)
•
Anfragen: Aufgabe, die Zeit t benötigt und bis Zeitpunkt d
bearbeitet sein soll
Länge 1 Deadline 4
1
Aufgabe 1
Deadline 4
Länge 2
Aufgabe 1
2
Aufgabe 2
wird zu
spät 6
Deadline
Länge 3
beendet
3
Aufgabe 3
2
1
15
LS 2 /
Informatik
Gierige Algorithmen
Scheduling mit Deadlines
•
Resource (Hörsaal, Parallelrechner, Elektronenmikroskop,..)
•
Anfragen: Aufgabe, die Zeit t benötigt und bis Zeitpunkt d
bearbeitet sein soll
Länge 1 Deadline 4
1
Aufgabe 1
Deadline 4
Länge 2
2
Aufgabe 2
Deadline 6
Länge 3
3
Aufgabe 3
Wir können nicht alle Aufgaben
bearbeiten und gleichzeitig die
Deadlines einhalten!
16
LS 2 /
Informatik
Gierige Algorithmen
Scheduling mit Deadlines
•
Resource (Hörsaal, Parallelrechner, Elektronenmikroskop,..)
•
Anfragen: Aufgabe, die Zeit t benötigt und bis Zeitpunkt d
bearbeitet sein soll
Länge 1 Deadline 4
1
Aufgabe 1
Deadline 4
Länge 2
2
Aufgabe 2
Deadline 6
Länge 3
3
Aufgabe 3
Wir können nicht alle Aufgaben
bearbeiten und gleichzeitig die
Deadlines einhalten!
1
17
LS 2 /
Informatik
Gierige Algorithmen
Scheduling mit Deadlines
•
Resource (Hörsaal, Parallelrechner, Elektronenmikroskop,..)
•
Anfragen: Aufgabe, die Zeit t benötigt und bis Zeitpunkt d
bearbeitet sein soll
Länge 1 Deadline 4
1
Aufgabe 1
Deadline 4
Länge 2
2
Aufgabe 2
Deadline 6
Länge 3
3
Aufgabe 3
1
Wir können nicht alle Aufgaben
bearbeiten und gleichzeitig die
Deadlines einhalten!
2
18
LS 2 /
Informatik
Gierige Algorithmen
Scheduling mit Deadlines
•
Resource (Hörsaal, Parallelrechner, Elektronenmikroskop,..)
•
Anfragen: Aufgabe, die Zeit t benötigt und bis Zeitpunkt d
bearbeitet sein soll
Länge 1 Deadline 4
1
Aufgabe 1
Deadline 4
Länge 2
2
Aufgabe 2
Deadline 6
Länge 3
3
Aufgabe 3
1
Wir können nicht alle Aufgaben
bearbeiten und gleichzeitig die
Deadlines einhalten!
2
Aufgabe 2:
Verspätung 1
19
LS 2 /
Informatik
Gierige Algorithmen
Scheduling mit Deadlines
•
Resource (Hörsaal, Parallelrechner, Elektronenmikroskop,..)
•
Anfragen: Aufgabe, die Zeit t benötigt und bis Zeitpunkt d
bearbeitet sein soll
Länge 1 Deadline 4
1
Aufgabe 1
Deadline 4
Länge 2
2
Aufgabe 2
Deadline 6
Länge 3
3
Aufgabe 3
1
2
Aufgabe 2:
Verspätung 1
Wir können nicht alle Aufgaben
bearbeiten und gleichzeitig die
Deadlines einhalten!
3
20
LS 2 /
Informatik
Gierige Algorithmen
Scheduling mit Deadlines
•
Resource (Hörsaal, Parallelrechner, Elektronenmikroskop,..)
•
Anfragen: Aufgabe, die Zeit t benötigt und bis Zeitpunkt d
bearbeitet sein soll
Länge 1 Deadline 4
1
Aufgabe 1
Deadline 4
Länge 2
2
Aufgabe 2
Deadline 6
Länge 3
3
Aufgabe 3
1
2
Wir können nicht alle Aufgaben
bearbeiten und gleichzeitig die
Deadlines einhalten!
3
Aufgabe 3:
Aufgabe 2:
Verspätung 1 Verspätung 2
21
LS 2 /
Informatik
Gierige Algorithmen
Scheduling mit Deadlines
•
Resource (Hörsaal, Parallelrechner, Elektronenmikroskop,..)
•
Anfragen: Aufgabe, die Zeit t benötigt und bis Zeitpunkt d
bearbeitet sein soll
Länge 1 Deadline 4
1
Aufgabe 1
Deadline 4
Länge 2
2
Aufgabe 2
Deadline 6
Länge 3
3
Aufgabe 3
1
2
Ziel:
Minimiere maximale Verspätung
3
Aufgabe 3:
Aufgabe 2:
Verspätung 1 Verspätung 2
22
LS 2 /
Informatik
Gierige Algorithmen
Strategie 1

Bearbeite die Jobs nach ansteigender Länge
1
Deadline 9
3
Deadline 4
Deadline 6
4
Deadline 6
2
Deadline 3
5
6
Deadline 9
23
LS 2 /
Informatik
Gierige Algorithmen
Strategie 1

Bearbeite die Jobs nach ansteigender Länge
1
Deadline 9
3
Deadline 4
Deadline 6
4
Deadline 6
2
Deadline 3
5
Deadline 9
6
1
Keine
Verspätung
24
LS 2 /
Informatik
Gierige Algorithmen
Strategie 1

Bearbeite die Jobs nach ansteigender Länge
1
Deadline 9
3
Deadline 4
Deadline 6
4
Deadline 6
2
Deadline 3
5
Deadline 9
6
1
5
Keine
Verspätung
25
LS 2 /
Informatik
Gierige Algorithmen
Strategie 1

Bearbeite die Jobs nach ansteigender Länge
1
Deadline 9
3
Deadline 4
Deadline 6
4
Deadline 6
2
Deadline 3
5
Deadline 9
6
1
5
3
Keine
Verspätung
26
LS 2 /
Informatik
Gierige Algorithmen
Strategie 1

Bearbeite die Jobs nach ansteigender Länge
1
Deadline 9
3
Deadline 4
Deadline 6
4
Deadline 6
2
Deadline 3
5
Deadline 9
6
1
5
3
4
Keine
Verspätung
27
LS 2 /
Informatik
Gierige Algorithmen
Strategie 1

Bearbeite die Jobs nach ansteigender Länge
1
Deadline 9
3
Deadline 4
Deadline 6
4
Deadline 6
2
Deadline 3
5
Deadline 9
6
1
5
3
4
2
Verspätung 5
28
LS 2 /
Informatik
Gierige Algorithmen
Strategie 1

Bearbeite die Jobs nach ansteigender Länge
1
Deadline 9
3
Deadline 4
Deadline 6
4
Deadline 6
2
Deadline 3
5
Deadline 9
6
1
5
3
4
2
6
Verspätung 3
29
LS 2 /
Informatik
Gierige Algorithmen
Strategie 1

Bearbeite die Jobs nach ansteigender Länge
1
Deadline 9
Deadline 4
Deadline 6
Verspätung
DeadlineMaximale
6
durch Aufgabe 2
Deadline 3
(5 Zeiteinheiten)
Deadline 9
2
3
4
5
6
1
5
3
4
2
6
30
LS 2 /
Informatik
Gierige Algorithmen
Strategie 1


Bearbeite die Jobs nach ansteigender Länge
Optimalität?
1
Deadline 9
Deadline 4
Deadline 6
Verspätung
DeadlineMaximale
6
durch Aufgabe 2
Deadline 3
(5 Zeiteinheiten)
Deadline 9
2
3
4
5
6
1
5
3
4
2
6
31
LS 2 /
Informatik
Gierige Algorithmen
Strategie 1


Bearbeite die Jobs nach ansteigender Länge
Optimalität?
1
Deadline 9
3
Deadline 4
Deadline 6
4
Deadline 6
2
Deadline 3
5
Deadline 9
6
5
Keine
Verspätung
32
LS 2 /
Informatik
Gierige Algorithmen
Strategie 1


Bearbeite die Jobs nach ansteigender Länge
Optimalität?
1
Deadline 9
3
Deadline 4
Deadline 6
4
Deadline 6
2
Deadline 3
5
Deadline 9
6
5
2
Keine
Verspätung
33
LS 2 /
Informatik
Gierige Algorithmen
Strategie 1


Bearbeite die Jobs nach ansteigender Länge
Optimalität?
1
Deadline 9
3
Deadline 4
Deadline 6
4
Deadline 6
2
Deadline 3
5
Deadline 9
6
5
2
3
Keine
Verspätung
34
LS 2 /
Informatik
Gierige Algorithmen
Strategie 1


Bearbeite die Jobs nach ansteigender Länge
Optimalität?
1
Deadline 9
3
Deadline 4
Deadline 6
4
Deadline 6
2
Deadline 3
5
Deadline 9
6
5
2
3
4
Verspätung 2
35
LS 2 /
Informatik
Gierige Algorithmen
Strategie 1


Bearbeite die Jobs nach ansteigender Länge
Optimalität?
1
Deadline 9
3
Deadline 4
Deadline 6
4
Deadline 6
2
Deadline 3
5
Deadline 9
6
5
2
3
4
1
Keine
Verspätung
36
LS 2 /
Informatik
Gierige Algorithmen
Strategie 1


Bearbeite die Jobs nach ansteigender Länge
Optimalität?
1
Deadline 9
3
Deadline 4
Deadline 6
4
Deadline 6
2
Deadline 3
5
6
5
2
3
4
1
Maximale Verspätung
durch Aufgabe 6
(3 Zeiteinheiten)
Deadline 9
6
37
LS 2 /
Informatik
Gierige Algorithmen
Strategie 1



Bearbeite die Jobs nach ansteigender Länge
Optimalität?
Problem: Ignoriert Deadlines völlig
1
Deadline 9
3
Deadline 4
Deadline 6
4
Deadline 6
2
Deadline 3
5
6
5
2
3
4
1
Maximale Verspätung
durch Aufgabe 6
(3 Zeiteinheiten)
Deadline 9
6
38
LS 2 /
Informatik
Gierige Algorithmen
Strategie 2

Bearbeite zunächst die Aufgaben mit geringstem Spielraum d-t
1
Deadline 9
3
Deadline 4
Deadline 6
4
Deadline 6
2
Deadline 3
5
6
Deadline 9
39
LS 2 /
Informatik
Gierige Algorithmen
Strategie 2

Bearbeite zunächst die Aufgaben mit geringstem Spielraum d-t
Spielraum 8
1
Deadline 9
3
Deadline 4
Deadline 6
4
Deadline 6
2
Deadline 3
5
6
Deadline 9
40
LS 2 /
Informatik
Gierige Algorithmen
Strategie 2

Bearbeite zunächst die Aufgaben mit geringstem Spielraum d-t
1
Deadline 9
3
Deadline 4
Spielraum 4
Deadline 6
4
Deadline 6
2
Deadline 3
5
6
Deadline 9
41
LS 2 /
Informatik
Gierige Algorithmen
Strategie 2

Bearbeite zunächst die Aufgaben mit geringstem Spielraum d-t
1
2
3
Deadline 9
Spielraum 1
Deadline 4
Deadline 6
Deadline 6
4
Deadline 3
5
6
Deadline 9
2
42
LS 2 /
Informatik
Gierige Algorithmen
Strategie 2

Bearbeite zunächst die Aufgaben mit geringstem Spielraum d-t
1
Deadline 9
3
Deadline 4
Deadline 6
4
Deadline 6
2
5
Spielraum 2
Deadline 3
Deadline 9
6
2
5
43
LS 2 /
Informatik
Gierige Algorithmen
Strategie 2

Bearbeite zunächst die Aufgaben mit geringstem Spielraum d-t
1
Deadline 9
3
Deadline 4
Spielraum 4
Deadline 6
4
Deadline 6
2
Deadline 3
5
Deadline 9
6
2
5
3
44
LS 2 /
Informatik
Gierige Algorithmen
Strategie 2

Bearbeite zunächst die Aufgaben mit geringstem Spielraum d-t
1
Deadline 9
2
3
4
Deadline 4
Deadline 6
Spielraum 4 Deadline 6
Deadline 3
5
Deadline 9
6
2
5
3
4
45
LS 2 /
Informatik
Gierige Algorithmen
Strategie 2

Bearbeite zunächst die Aufgaben mit geringstem Spielraum d-t
1
Deadline 9
3
Deadline 4
Deadline 6
4
Deadline 6
2
5
6
2
Deadline 3
Spielraum 6
5
3
4
Deadline 9
6
46
LS 2 /
Informatik
Gierige Algorithmen
Strategie 2

Bearbeite zunächst die Aufgaben mit geringstem Spielraum d-t
Spielraum 8
1
Deadline 9
3
Deadline 4
Deadline 6
4
Deadline 6
2
Deadline 3
5
Deadline 9
6
2
5
3
4
6
1
47
LS 2 /
Informatik
Gierige Algorithmen
Strategie 2

Bearbeite zunächst die Aufgaben mit geringstem Spielraum d-t
1
Deadline 9
3
Deadline 4
Deadline 6
4
Deadline 6
2
Deadline 3
5
Deadline 9
6
2
5
3
4
6
1
Verspätung 3
48
LS 2 /
Informatik
Gierige Algorithmen
Strategie 2

Bearbeite zunächst die Aufgaben mit geringstem Spielraum d-t
1
Deadline 9
3
Deadline 4
Deadline 6
4
Deadline 6
2
Deadline 3
5
Deadline 9
6
2
5
3
4
6
Optimal für unsere
Eingabe
1
Verspätung 3
49
LS 2 /
Informatik
Gierige Algorithmen
Strategie 2

Bearbeite zunächst die Aufgaben mit geringstem Spielraum d-t

Optimalität?
Spielraum 2
1
Deadline 3
2
Deadline 9
Spielraum 0
50
LS 2 /
Informatik
Gierige Algorithmen
Strategie 2

Bearbeite zunächst die Aufgaben mit geringstem Spielraum d-t

Optimalität?
Spielraum 2
1
Deadline 3
2
Deadline 9
Spielraum 0
2
51
LS 2 /
Informatik
Gierige Algorithmen
Strategie 2

Bearbeite zunächst die Aufgaben mit geringstem Spielraum d-t

Optimalität?
Spielraum 2
1
Deadline 3
2
Deadline 9
Spielraum 0
2
Verspätung 7
1
52
LS 2 /
Informatik
Gierige Algorithmen
Strategie 2

Bearbeite zunächst die Aufgaben mit geringstem Spielraum d-t

Optimalität?
Spielraum 2
1
Deadline 3
Deadline 9
Spielraum 0
2
1
Optimale Lösung hat nur
Verspätung 1
2
Verspätung 1
53
LS 2 /
Informatik
Gierige Algorithmen
Strategie 3

Bearbeite zunächst die Aufgabe mit der frühesten Deadline
1
Deadline 9
3
Deadline 4
Deadline 6
4
Deadline 6
2
Deadline 3
5
6
Deadline 9
54
LS 2 /
Informatik
Gierige Algorithmen
Strategie 3

Bearbeite zunächst die Aufgabe mit der frühesten Deadline
1
Deadline 9
3
Deadline 4
Deadline 6
4
Deadline 6
2
Deadline 3
5
6
Deadline 9
5
55
LS 2 /
Informatik
Gierige Algorithmen
Strategie 3

Bearbeite zunächst die Aufgabe mit der frühesten Deadline
1
Deadline 9
3
Deadline 4
Deadline 6
4
Deadline 6
2
Deadline 3
5
Deadline 9
6
5
2
56
LS 2 /
Informatik
Gierige Algorithmen
Strategie 3

Bearbeite zunächst die Aufgabe mit der frühesten Deadline
1
Deadline 9
3
Deadline 4
Deadline 6
4
Deadline 6
2
Deadline 3
5
Deadline 9
6
5
2
3
57
LS 2 /
Informatik
Gierige Algorithmen
Strategie 3

Bearbeite zunächst die Aufgabe mit der frühesten Deadline
1
Deadline 9
3
Deadline 4
Deadline 6
4
Deadline 6
2
Deadline 3
5
Deadline 9
6
5
2
3
4
58
LS 2 /
Informatik
Gierige Algorithmen
Strategie 3

Bearbeite zunächst die Aufgabe mit der frühesten Deadline
1
Deadline 9
3
Deadline 4
Deadline 6
4
Deadline 6
2
Deadline 3
5
Deadline 9
6
5
2
3
4
6
59
LS 2 /
Informatik
Gierige Algorithmen
Strategie 3

Bearbeite zunächst die Aufgabe mit der frühesten Deadline
1
Deadline 9
3
Deadline 4
Deadline 6
4
Deadline 6
2
Deadline 3
5
Deadline 9
6
5
2
3
4
6
1
Verspätung 3
60
LS 2 /
Informatik
Gierige Algorithmen
Strategie 3

Bearbeite zunächst die Aufgabe mit der frühesten Deadline
1
Deadline 9
3
Deadline 4
Deadline 6
4
Deadline 6
2
Lösung optimal!
Deadline 3
5
Deadline 9
6
5
2
3
4
6
1
Verspätung 3
61
LS 2 /
Informatik
Gierige Algorithmen
Strategie 3

Bearbeite zunächst die Aufgabe mit der frühesten Deadline

Algorithmus ist optimal!
1
Deadline 9
3
Deadline 4
Deadline 6
4
Deadline 6
2
Lösung optimal!
Deadline 3
5
Deadline 9
6
5
2
3
4
6
1
Verspätung 3
62
LS 2 /
Informatik
Gierige Algorithmen
Strategie 3

Bearbeite zunächst die Aufgabe mit der frühesten Deadline

Algorithmus ist optimal!
Komisch, da Strategie
unabhängig von der Länge
der Aufträge
Deadline 9
1
3
Deadline 4
Deadline 6
4
Deadline 6
2
Deadline 3
5
Deadline 9
6
5
2
3
4
6
1
Verspätung 3
63
LS 2 /
Informatik
Gierige Algorithmen
Formale Problemformulierung



Problem: Scheduling mit Deadline
Eingabe: Felder t und d
t[i] enthält Länge des i-ten Intervals
d[i] enthält Deadline
Ausgabe: Startzeitpunkte der Intervalle
Wichtige Annahme


Eingabe sortiert nach Deadlines
d[1]d[2]…d[n]
64
LS 2 /
Informatik
Gierige Algorithmen
LatenessScheduling(t,d)
t
1
4
2
1. n  length[t]
d
3
4
6
2. new array A[1..n]
3. z  0
1
4. for i  1 to n do
5.
A[i]  z
6.
z  z + t[i]
2
3
7. return A
65
LS 2 /
Informatik
Gierige Algorithmen
LatenessScheduling(t,d)
t
1
4
2
1. n  length[t]
d
3
4
6
2. new array A[1..n]
3. z  0
1
4. for i  1 to n do
5.
A[i]  z
6.
z  z + t[i]
2
3
7. return A
66
LS 2 /
Informatik
Gierige Algorithmen
LatenessScheduling(t,d)
t
1
4
2
1. n  length[t]
d
3
4
6
2. new array A[1..n]
3. z  0
1
4. for i  1 to n do
5.
A[i]  z
6.
z  z + t[i]
2
3
7. return A
67
LS 2 /
Informatik
Gierige Algorithmen
LatenessScheduling(t,d)
t
1
4
2
1. n  length[t]
d
3
4
6
2. new array A[1..n]
3. z  0
1
4. for i  1 to n do
5.
A[i]  z
6.
z  z + t[i]
2
3
7. return A
z
68
LS 2 /
Informatik
Gierige Algorithmen
LatenessScheduling(t,d)
t
1
4
2
1. n  length[t]
d
3
4
6
2. new array A[1..n]
3. z  0
i
1
4. for i  1 to n do
5.
A[i]  z
6.
z  z + t[i]
2
3
7. return A
z
69
LS 2 /
Informatik
Gierige Algorithmen
LatenessScheduling(t,d)
t
1
4
2
1. n  length[t]
d
3
4
6
2. new array A[1..n]
3. z  0
i
1
4. for i  1 to n do
5.
A[i]  z
6.
z  z + t[i]
2
3
1
7. return A
z
70
LS 2 /
Informatik
Gierige Algorithmen
LatenessScheduling(t,d)
t
1
4
2
1. n  length[t]
d
3
4
6
2. new array A[1..n]
3. z  0
i
1
4. for i  1 to n do
5.
A[i]  z
6.
z  z + t[i]
2
3
1
7. return A
z
71
LS 2 /
Informatik
Gierige Algorithmen
LatenessScheduling(t,d)
t
1
4
2
1. n  length[t]
d
3
4
6
2. new array A[1..n]
3. z  0
4. for i  1 to n do
5.
A[i]  z
6.
z  z + t[i]
1
i
2
3
1
7. return A
z
72
LS 2 /
Informatik
Gierige Algorithmen
LatenessScheduling(t,d)
t
1
4
2
1. n  length[t]
d
3
4
6
2. new array A[1..n]
3. z  0
4. for i  1 to n do
5.
A[i]  z
6.
z  z + t[i]
1
i
2
3
2
1
7. return A
z
73
LS 2 /
Informatik
Gierige Algorithmen
LatenessScheduling(t,d)
t
1
4
2
1. n  length[t]
d
3
4
6
2. new array A[1..n]
3. z  0
4. for i  1 to n do
5.
A[i]  z
6.
z  z + t[i]
1
i
2
3
1
2
7. return A
z
74
LS 2 /
Informatik
Gierige Algorithmen
LatenessScheduling(t,d)
t
1
4
2
1. n  length[t]
d
3
4
6
2. new array A[1..n]
3. z  0
1
4. for i  1 to n do
5.
A[i]  z
6.
z  z + t[i]
2
i
3
1
2
7. return A
z
75
LS 2 /
Informatik
Gierige Algorithmen
LatenessScheduling(t,d)
t
1
4
2
1. n  length[t]
d
3
4
6
2. new array A[1..n]
3. z  0
1
4. for i  1 to n do
5.
A[i]  z
6.
z  z + t[i]
2
i
3
1
2
3
7. return A
z
76
LS 2 /
Informatik
Gierige Algorithmen
LatenessScheduling(t,d)
t
1
4
2
1. n  length[t]
d
3
4
6
2. new array A[1..n]
3. z  0
1
4. for i  1 to n do
5.
A[i]  z
6.
z  z + t[i]
2
i
3
1
2
3
7. return A
z
77
LS 2 /
Informatik
Gierige Algorithmen
LatenessScheduling(t,d)
t
1
4
2
1. n  length[t]
d
3
4
6
2. new array A[1..n]
3. z  0
1
4. for i  1 to n do
5.
A[i]  z
6.
z  z + t[i]
2
i
3
1
2
3
7. return A
z
78
LS 2 /
Informatik
Gierige Algorithmen
Beobachtung
Es gibt eine optimale Lösung ohne Leerlaufzeit.
1
2
3
Leerlauf
79
LS 2 /
Informatik
Gierige Algorithmen
Lemma 34
Alle Lösungen ohne Inversionen und Leerlaufzeit haben dieselbe maximale
Verzögerung.
1
Definition
2
Lösung hat Inversion, wenn Aufgabe i
Mit Deadline di vor Aufgabe j mit
Deadline d < d bearbeitet wird.
j
i
3
1
i
j
3
2
Inversion
80
LS 2 /
Informatik
Gierige Algorithmen
Lemma 34
Alle Lösungen ohne Inversionen und Leerlaufzeit haben dieselbe maximale
Verzögerung.
Beweis
•
Haben zwei Schedules weder Inversionen noch Leerlaufzeiten, so haben
sie zwar nicht notwendigerweise dieselbe Ordnung, aber sie können sich
nur in der Ordnung der Aufgaben mit identischer Deadline unterscheiden.
Betrachten wir eine solche Deadline d.
81
LS 2 /
Informatik
Gierige Algorithmen
Lemma 34
Alle Lösungen ohne Inversionen und Leerlaufzeit haben dieselbe maximale
Verzögerung.
Beweis
•
Haben zwei Schedules weder Inversionen noch Leerlaufzeiten, so haben
sie zwar nicht notwendigerweise dieselbe Ordnung, aber sie können sich
nur in der Ordnung der Aufgaben mit identischer Deadline unterscheiden.
Betrachten wir eine solche Deadline d. In beiden Schedules werden alle
Aufgaben mit Deadline d nacheinander ausgeführt.
82
LS 2 /
Informatik
Gierige Algorithmen
Lemma 34
Alle Lösungen ohne Inversionen und Leerlaufzeit haben dieselbe maximale
Verzögerung.
Beweis
•
Haben zwei Schedules weder Inversionen noch Leerlaufzeiten, so haben
sie zwar nicht notwendigerweise dieselbe Ordnung, aber sie können sich
nur in der Ordnung der Aufgaben mit identischer Deadline unterscheiden.
Betrachten wir eine solche Deadline d. In beiden Schedules werden alle
Aufgaben mit Deadline d nacheinander ausgeführt. Unter den Aufgaben
mit Deadline d hat die letzte die größte Verzögerung und diese hängt nicht
von der Reihenfolge der Aufgaben ab.
83
LS 2 /
Informatik
Gierige Algorithmen
Lemma 34
Alle Lösungen ohne Inversionen und Leerlaufzeit haben dieselbe maximale
Verzögerung.
Beweis
•
Haben zwei Schedules weder Inversionen noch Leerlaufzeiten, so haben
sie zwar nicht notwendigerweise dieselbe Ordnung, aber sie können sich
nur in der Ordnung der Aufgaben mit identischer Deadline unterscheiden.
Betrachten wir eine solche Deadline d. In beiden Schedules werden alle
Aufgaben mit Deadline d nacheinander ausgeführt. Unter den Aufgaben
mit Deadline d hat die letzte die größte Verzögerung und diese hängt nicht
von der Reihenfolge der Aufgaben ab.
84
LS 2 /
Informatik
Gierige Algorithmen
Lemma 35
Es gibt eine optimale Lösung ohne Inversionen und Leerlaufzeit.
1
2
3
1
2
3
85
LS 2 /
Informatik
Gierige Algorithmen
Lemma 35
Es gibt eine optimale Lösung ohne Inversionen und Leerlaufzeit.
1
2
3
Ohne Inversionen
und Leerlauf:
Also optimal!
1
2
3
86
LS 2 /
Informatik
Gierige Algorithmen
Lemma 35
Es gibt eine optimale Lösung ohne Inversionen und Leerlaufzeit.
Beweis
•
Sei O ein optimales Schedule ohne Leerlauf. Wir zeigen zunächst
•
(a) Wenn O eine Inversion hat, dann gibt es ein Paar Aufgaben i und j, so
dass j direkt nach i auftritt und d j < di ist.
(D.h. eine Inversion von aufeinanderfolgenden Aufgaben)
Deadline 9
Deadline 5
a
b
Deadline 9
87
LS 2 /
Informatik
Gierige Algorithmen
Lemma 35
Es gibt eine optimale Lösung ohne Inversionen und Leerlaufzeit.
Beweis
•
Sei O ein optimales Schedule ohne Leerlauf. Wir zeigen zunächst
•
(a) Wenn O eine Inversion hat, dann gibt es ein Paar Aufgaben i und j, so
dass j direkt nach i auftritt und d j < di ist.
(D.h. eine Inversion von aufeinanderfolgenden Aufgaben)
Deadline 9
Deadline 5
a
b
Deadline 9
88
LS 2 /
Informatik
Gierige Algorithmen
Lemma 35
Es gibt eine optimale Lösung ohne Inversionen und Leerlaufzeit.
Beweis
•
Sei O ein optimales Schedule ohne Leerlauf. Wir zeigen zunächst
•
(a) Wenn O eine Inversion hat, dann gibt es ein Paar Aufgaben i und j, so
dass j direkt nach i auftritt und d j < di ist.
(D.h. eine Inversion von aufeinanderfolgenden Aufgaben)
Deadline 9
Deadline 5
a
b
Spätestens hier Inversion von
aufeinander folgenden Aufgaben
89
LS 2 /
Informatik
Gierige Algorithmen
Lemma 35
Es gibt eine optimale Lösung ohne Inversionen und Leerlaufzeit.
Beweis
•
Sei O ein optimales Schedule ohne Leerlauf. Wir zeigen zunächst
•
(a) Wenn O eine Inversion hat, dann gibt es ein Paar Aufgaben i und j, so
dass j direkt nach i auftritt und d j < di ist.
(D.h. eine Inversion von aufeinanderfolgenden Aufgaben)
Deadline 9
Deadline 5
a
b
Spätestens hier Inversion von
aufeinander folgenden Aufgaben
90
LS 2 /
Informatik
Gierige Algorithmen
Lemma 35
Es gibt eine optimale Lösung ohne Inversionen und Leerlaufzeit.
Beweis
•
Sei O ein optimales Schedule ohne Leerlauf. Wir zeigen zunächst
•
(b) Nach dem Austauschen von einer benachbarten Inversion i und j
erhalten wir ein Schedule mit einer Inversion weniger.
•
Es wird die Inversion von i und j durch das Vertauschen aufgehoben und
es wird keine neue Inversion wird erzeugt.
91
LS 2 /
Informatik
Gierige Algorithmen
Lemma 35
Es gibt eine optimale Lösung ohne Inversionen und Leerlaufzeit.
Beweis
•
Sei O ein optimales Schedule ohne Leerlauf. Wir zeigen zunächst
•
(c) Das Tauschen von i und j erhöht nicht die maximale Verzögerung.
dj
di
i
j
Aufeinander folgende Inversion (i,j)
92
LS 2 /
Informatik
Gierige Algorithmen
Lemma 35
Es gibt eine optimale Lösung ohne Inversionen und Leerlaufzeit.
Beweis
•
Sei O ein optimales Schedule ohne Leerlauf. Wir zeigen zunächst
•
(c) Das Tauschen von i und j erhöht nicht die maximale Verzögerung.
Verzögerung
von j wird
kleiner
dj
di
j
i
Vertausche i und j
93
LS 2 /
Informatik
Gierige Algorithmen
Lemma 35
Es gibt eine optimale Lösung ohne Inversionen und Leerlaufzeit.
Beweis
•
Sei O ein optimales Schedule ohne Leerlauf. Wir zeigen zunächst
•
(c) Das Tauschen von i und j erhöht nicht die maximale Verzögerung.
Verzögerung
von i wird
dj
größer!
di
j
i
Vertausche i und j
94
LS 2 /
Informatik
Gierige Algorithmen
Lemma 35
Es gibt eine optimale Lösung ohne Inversionen und Leerlaufzeit.
Beweis
•
Sei O ein optimales Schedule ohne Leerlauf. Wir zeigen zunächst
•
(c) Das Tauschen von i und j erhöht nicht die maximale Verzögerung.
Ist aber kleiner als
Verzögerung von j
dj
vor Vertauschung!
di
j
i
Vertausche i und j
95
LS 2 /
Informatik
Gierige Algorithmen
Lemma 35
Es gibt eine optimale Lösung ohne Inversionen und Leerlaufzeit.
Beweis
•
Sei O ein optimales Schedule ohne Leerlauf. Wir zeigen zunächst
•
(c) Das Tauschen von i und j erhöht nicht die maximale Verzögerung.
Ist aber kleiner als
Verzögerung von j
dj
vor Vertauschung!
di
j
i
Vertausche i und j
96
LS 2 /
Informatik
Gierige Algorithmen
Formaler Beweis von (c)
•
Notation für O: Aufgabe r wird im Invervall [s(r),f(r)] ausgeführt und hat
Verzögerung l(r). Sei L = max l(r) die maximale Verzögerung dieses
Schedules.
dr
l(r)
r
s(r)
f(r)
•
Notation für das Schedule O* nach Austauschen: s*(r), f*(r), l*(r) und L* mit
der entsprechenden Bedeutung wie oben.
•
s(r), s*(r) heißt Startzeit
•
f(r), f*(r) heißt Abarbeitungszeit
97
LS 2 /
Informatik
Gierige Algorithmen
Formaler Beweis von (c)
•
Betrachten wir nun die benachbarte Inversion von i und j. Die
Abarbeitungszeit f(j) von j vor dem Austauschen ist gleich der
Abarbeitungszeit f*(i) von i nach dem Austauschen. Daher haben alle
anderen Aufgaben vor und nach dem Tauschen dieselbe Abarbeitungszeit.
dj
di
f(i) f(j)
i
j
Aufeinander folgende Inversion (i,j)
98
LS 2 /
Informatik
Gierige Algorithmen
Formaler Beweis von (c)
•
Betrachten wir nun die benachbarte Inversion von i und j. Die
Abarbeitungszeit f(j) von j vor dem Austauschen ist gleich der
Abarbeitungszeit f*(i) von i nach dem Austauschen. Daher haben alle
anderen Aufgaben vor und nach dem Tauschen dieselbe Abarbeitungszeit.
•
Für Aufgabe j ist das neue Schedule besser, d.h. f*(j)<f(j).
dj
f*(j)
f*(i)
f(i) f(j)
di
j
i
Aufeinander folgende Inversion (i,j)
99
LS 2 /
Informatik
Gierige Algorithmen
Formaler Beweis von (c)
•
Betrachte nur Aufgabe i: Nach dem Tauschen ist die Verzögerung
l*(i) = f*(i)-d i .
dj
f*(j)
f*(i)
f(i) f(j)
di
j
l*(i)
i
100
LS 2 /
Informatik
Gierige Algorithmen
Formaler Beweis von (c)
•
Betrachte nur Aufgabe i: Nach dem Tauschen ist die Verzögerung
l*(i) = f*(i)-d i .
•
Wegen d > d folgt l*(i) = f(j) - di < f(j) - dj = l(j).
•
Damit wird die maximale Verzögerung nicht erhöht.
i
j
dj
f*(j)
f*(i)
f(i) f(j)
di
j
l*(i)
i
101
LS 2 /
Informatik
Gierige Algorithmen
Lemma 35
Es gibt eine optimale Lösung ohne Inversionen und Leerlaufzeit.
Beweis
•
(a) Wenn O eine Inversion hat, dann gibt es ein Paar Aufgaben i und j, so
dass j direkt nach i auftritt und dj < d i ist.
•
(b) Nach dem Austauschen von einer benachbarten Inversion i und j
erhalten wir ein Schedule mit einer Inversion weniger.
•
(c) Das Tauschen von i und j erhöht nicht die maximale Verzögerung.
•
Die Anzahl Inversionen ist zu Beginn höchstens ( n ).Wir können (a)-(c)
2
solange anwenden, bis keine Inversionen mehr vorhanden sind.
102
LS 2 /
Informatik
Gierige Algorithmen
Satz 36
Die Lösung A, die von Algorithmus LatenessScheduling berechnet wird, hat
optimale (d.h. minimale) maximale Verzögerung.
Beweis
Aus dem ersten Lemma folgt, dass es ein optimales Schedule ohne
Inversionen gibt. Aus dem zweiten Lemma folgt, dass alle Schedules ohne
Inversionen dieselbe maximale Verzögerung haben. Damit ist die Lösung
des gierigen Algorithmus optimal.
103
LS 2 /
Informatik
Gierige Algorithmen
Zusammenfassung



Löse globales Optimierungsproblem durch lokale Optimierungsstrategie
Liefert häufig recht einfache Algorithmen
Funktioniert leider nicht immer und es ist manchmal nicht ganz einfach, die
‚richtige‘ Strategie zu finden
Algorithmische Entwurfsmethoden



Teile & Herrsche
Dynamische Programmierung
Gierige Algorithmen
104
LS 2 /
Informatik
Datenstrukturen
Was ist eine Datenstruktur?


Eine Datenstruktur ist eine Anordnung von Daten, die effizienten Zugriff auf
die Daten ermöglicht
Datenstrukturen für viele unterschiedliche Anfragen vorstellbar
105
LS 2 /
Informatik
Datenstrukturen
Ein grundlegendes Datenbank-Problem

Speicherung von Datensätzen
Beispiel

Kundendaten (Name, Adresse, Wohnort, Kundennummer, offene
Rechnungen, offene Bestellungen,…)
Anforderungen



Schneller Zugriff
Einfügen neuer Datensätze
Löschen bestehender Datensätze
106
LS 2 /
Informatik
Datenstrukturen
Zugriff auf Daten



Jedes Datum (Objekt) hat einen Schlüssel
Eingabe des Schlüssels liefert Datensatz
Schlüssel sind vergleichbar (es gibt totale Ordnung der Schlüssel)
Beispiel



Kundendaten (Name, Adresse, Kundennummer)
Schlüssel: Name
Totale Ordnung: Lexikographische Ordnung
107
LS 2 /
Informatik
Datenstrukturen
Zugriff auf Daten



Jedes Datum (Objekt) hat einen Schlüssel
Eingabe des Schlüssels liefert Datensatz
Schlüssel sind vergleichbar (es gibt totale Ordnung der Schlüssel)
Beispiel:



Kundendaten (Name, Adresse, Kundennummer)
Schlüssel: Kundennummer
Totale Ordnung: ‚‘
108
LS 2 /
Informatik
Datenstrukturen
Problem:

Gegeben sind n Objekte O1 ,.., O mit zugehörigen Schlüsseln s(Oi )
n
Operationen:



Suche(x); Ausgabe O mit Schlüssel s(O) =x;
nil, falls kein Objekt mit Schlüssel x in Datenbank
Einfügen(O); Einfügen von Objekt O in Datenbank
Löschen(O); Löschen von Objekt O mit aus der Datenbank
109
LS 2 /
Informatik
Datenstrukturen
Vereinfachung:


Schlüssel sind natürliche Zahlen
Eingabe nur aus Schlüsseln
Analyse von Datenstrukturen


Platzbedarf in Q- bzw. O-Notation
Laufzeit der Operationen in Q- bzw. O-Notation
110
LS 2 /
Informatik
Datenstrukturen
Einfaches Feld



Feld A[1,…,max]
Integer n, 1 n  max
n bezeichnet Anzahl Elemente in Datenstruktur
13
7
11
6
4
nil
nil
nil
nil
nil
n
111
LS 2 /
Informatik
Datenstrukturen
Einfügen(s)
1. if n=max then Ausgabe „Fehler: Kein Platz in Datenstruktur“
2.
3.
4.
else
n  n+1
A[n]  s
13
7
11
6
4
nil
nil
nil
nil
nil
n
112
LS 2 /
Informatik
Datenstrukturen
Einfügen(s)
1. if n=max then Ausgabe „Fehler: Kein Platz in Datenstruktur“
2.
3.
4.
else
n  n+1
A[n]  s
13
7
11
6
4
nil
nil
nil
nil
nil
n
Einfügen(2)
113
LS 2 /
Informatik
Datenstrukturen
Einfügen(s)
1. if n=max then Ausgabe „Fehler: Kein Platz in Datenstruktur“
2.
3.
4.
else
n  n+1
A[n]  s
13
7
11
6
4
2
nil
nil
nil
nil
n
Einfügen(2)
114
LS 2 /
Informatik
Datenstrukturen
Suche(x)
1.
2.
3.
for i  1 to n do
if A[i] = x then return i
return nil
13
7
11
6
4
2
nil
nil
nil
nil
n
115
LS 2 /
Informatik
Datenstrukturen
Annahme:
Wir bekommen
Index i des zu
löschenden Objekts
Löschen(i)
A[i]  A[n]
A[n]  nil
n  n-1
1.
2.
3.
13
7
11
6
4
2
nil
nil
nil
nil
n
116
LS 2 /
Informatik
Datenstrukturen
Löschen(i)
A[i]  A[n]
A[n]  nil
n  n-1
1.
2.
3.
13
7
11
6
4
2
nil
nil
nil
nil
n
Löschen(2)
117
LS 2 /
Informatik
Datenstrukturen
Löschen(i)
A[i]  A[n]
A[n]  nil
n  n-1
1.
2.
3.
13
2
11
6
4
nil
nil
nil
nil
nil
n
Löschen(2)
118
LS 2 /
Informatik
Datenstrukturen
Datenstruktur Feld



Platzbedarf Q(max)
Laufzeit Suche: Q(n)
Laufzeit Einfügen/Löschen: Q(1)
Vorteile

Schnelles Einfügen und Löschen
Nachteile


Speicherbedarf abhängig von max (nicht vorhersagbar)
Hohe Laufzeit für Suche
119
LS 2 /
Informatik
Datenstrukturen
Datenstruktur „sortiertes Feld“



Sortiertes Feld A[1,…,max]
Integer n, 1 n  max
n bezeichnet Anzahl Elemente in Datenstruktur
2
A
4
6
7
11
13
nil
nil
nil
nil
n
120
LS 2 /
Informatik
Datenstrukturen
Einfügen(s)
1.
2.
3.
4.
5.
6.
2
n  n+1
in
while s < A[i-1] do
A[i]  A[i-1]
i  i -1
A[i]  s
4
6
7
11
13
nil
nil
nil
nil
n
Einfügen(10)
121
LS 2 /
Informatik
Datenstrukturen
Einfügen(s)
1.
2.
3.
4.
5.
6.
2
n  n+1
in
while s < A[i-1] do
A[i]  A[i-1]
i  i -1
A[i]  s
4
6
7
11
13
nil
nil
nil
nil
n
Einfügen(10)
122
LS 2 /
Informatik
Datenstrukturen
Einfügen(s)
1.
2.
3.
4.
5.
6.
2
n  n+1
in
while s < A[i-1] do
A[i]  A[i-1]
i  i -1
A[i]  s
4
6
7
11
13
nil
nil
nil
nil
n
Einfügen(10)
123
LS 2 /
Informatik
Datenstrukturen
Einfügen(s)
1.
2.
3.
4.
5.
6.
2
n  n+1
in
while s < A[i-1] do
A[i]  A[i-1]
i  i -1
A[i]  s
4
6
7
11
11
13
nil
nil
nil
n
Einfügen(10)
124
LS 2 /
Informatik
Datenstrukturen
Einfügen(s)
1.
2.
3.
4.
5.
6.
2
Laufzeit O(n)
n  n+1
in
while s < A[i-1] do
A[i]  A[i-1]
i  i -1
A[i]  s
4
6
7
10
11
13
nil
nil
nil
n
Einfügen(10)
125
LS 2 /
Informatik
Datenstrukturen
Parameter ist der
Index des zu
löschenden Objekts
Löschen(i)
1.
2.
3.
4.
2
for j  i to n-1 do
A[j]  A[j+1]
A[n]  nil
n  n-1
4
6
7
11
13
nil
nil
nil
nil
n
126
LS 2 /
Informatik
Datenstrukturen
Parameter ist der
Index des zu
löschenden Objekts
Löschen(i)
1.
2.
3.
4.
2
for j  i to n-1 do
A[j]  A[j+1]
A[n]  nil
n  n-1
4
6
7
11
13
nil
nil
nil
nil
n
Löschen(2)
127
LS 2 /
Informatik
Datenstrukturen
Parameter ist der
Index des zu
löschenden Objekts
Löschen(i)
1.
2.
3.
4.
for j  i to n-1 do
A[j]  A[j+1]
A[n]  nil
n  n-1
i
2
4
6
7
11
13
nil
nil
nil
nil
n
Löschen(2)
128
LS 2 /
Informatik
Datenstrukturen
Löschen(i)
1.
2.
3.
4.
for j  i to n-1 do
A[j]  A[j+1]
A[n]  nil
n  n-1
i
2
4
6
7
11
13
nil
nil
nil
nil
n
Löschen(2)
129
LS 2 /
Informatik
Datenstrukturen
Löschen(i)
1.
2.
3.
4.
for j  i to n-1 do
A[j]  A[j+1]
A[n]  nil
n  n-1
i
2
6
7
11
13
13
nil
nil
nil
nil
n
Löschen(2)
130
LS 2 /
Informatik
Datenstrukturen
Löschen(i)
1.
2.
3.
4.
for j  i to n-1 do
A[j]  A[j+1]
A[n]  nil
n  n-1
i
2
6
7
11
13
nil
nil
nil
nil
nil
n
Löschen(2)
131
LS 2 /
Informatik
Datenstrukturen
Löschen(i)
1.
2.
3.
4.
for j  i to n-1 do
A[j]  A[j+1]
A[n]  nil
n  n-1
i
2
6
7
11
13
nil
nil
nil
nil
nil
n
Löschen(2)
132
LS 2 /
Informatik
Datenstrukturen
Suchen(x)


Binäre Suche
Laufzeit O(log n)
i
2
6
7
11
13
nil
nil
nil
nil
nil
n
Löschen(2)
133
LS 2 /
Informatik
Datenstrukturen
Datenstruktur sortiertes Feld



Platzbedarf Q(max)
Laufzeit Suche: Q(log n)
Laufzeit Einfügen/Löschen: Q(n)
Vorteile

Schnelles Suchen
Nachteile


Speicherbedarf abhängig von max (nicht vorhersagbar)
Hohe Laufzeit für Einfügen/Löschen
134

nil - TU Dortmund, Informatik 2