Übung 02

Übung Algorithmen und Datenstrukturen
Sommersemester 2015
Marc Bux, Humboldt-Universität zu Berlin
Organisatorisches
• Korrektur: Tutorium bei Michael R. Jung am Dienstag 13 – 15
Uhr in RUD 25, 4.112 (statt am Mittwoch)
• Als Absicherung und um die eigene Abgabe in der Übung
parat zu haben: Abgabe kopieren
• In KW 19, 21, 23, 25, 27, 29: Pflichttermin
 Pro Aufgabe werden zwei bis drei Studenten zur Vorstellung der
Lösung ihrer Gruppe ausgelost
 Keine Konsequenzen wenn Student nicht anwesend ist oder Lösungen
nicht reproduzieren kann bzw. möchte
2
Agenda
1.
2.
3.
4.
5.
Organisatorisches
Die Landau-Notation (Fortsetzung)
Fragen und Übungsaufgaben zum ersten Übungsblatt
Rekursive Algorithmen
Divide & Conquer
3
Die Landau-Notation (Wiederholung)
• Definitionen:
Ο 𝑔 =
𝑓: ℝ+
0
→
ℝ+
0
+
 Ω 𝑔 = 𝑓: ℝ+
→
ℝ
0
0
+
 Θ 𝑔 = 𝑓: ℝ+
0 → ℝ0
+
 𝜊 𝑔 = 𝑓: ℝ+
0 → ℝ0
+
 𝜔 𝑔 = 𝑓: ℝ+
0 → ℝ0
∃𝑐 ∈ ℝ+ > 0 ∃𝑛0 ∈ ℝ+
0 >0
∀𝑛 ≥ 𝑛0 : 𝑓 𝑛 ≤ 𝑐 ∙ 𝑔(𝑛)
∃𝑐 ∈ ℝ+ > 0 ∃𝑛0 ∈ ℝ+
0 >0
∀𝑛 ≥ 𝑛0 : 𝑓 𝑛 ≥ 𝑐 ∙ 𝑔(𝑛)
∃𝑐1 , 𝑐2 ∈ ℝ+ > 0 ∃𝑛0 ∈ ℝ+
0 >0
∀𝑛 ≥ 𝑛0 : 𝑐1 ∙ 𝑔 𝑛 ≤ 𝑓 𝑛 ≤ 𝑐2 ∙ 𝑔(𝑛)
∀𝑐 ∈ ℝ+ > 0 ∃𝑛0 ∈ ℝ+
0 >0
∀𝑛 ≥ 𝑛0 : 𝑓 𝑛 < 𝑐 ∙ 𝑔(𝑛)
∀𝑐 ∈ ℝ+ > 0 ∃𝑛0 ∈ ℝ+
0 >0
∀𝑛 ≥ 𝑛0 : 𝑓 𝑛 > 𝑐 ∙ 𝑔(𝑛)
• Bedeutung: „𝑓 wächst ...





nicht wesentlich schneller als 𝑔
nicht wesentlich langsamer als 𝑔
ungefähr genauso schnell wie 𝑔
wesentlich langsamer als 𝑔
wesentlich schneller als 𝑔
4
Transitivität der Landau-Notation
• Satz: 𝑓 𝑛 = Ο 𝑔 𝑛
• Beweis:






⇒
⇒
⇒
∧𝑔 𝑛 =Ο ℎ 𝑛
⇒𝑓 𝑛 =Ο ℎ 𝑛
Voraussetzungen:
∃𝑐 ∃𝑛0 ∀𝑛 ≥ 𝑛0 : 𝑓 𝑛 ≤ 𝑐 ∙ 𝑔(𝑛)
∃𝑐′ ∃𝑛0′ ∀𝑛 ≥ 𝑛0′ : 𝑔 𝑛 ≤ 𝑐′ ∙ ℎ(𝑛)
Zu zeigen:
∃𝑐′′ ∃𝑛0′′ ∀𝑛 ≥ 𝑛0′′ : 𝑓 𝑛 ≤ 𝑐′′ ∙ ℎ(𝑛)
Beweis:
Wähle 𝑛0′′ = max 𝑛0 , 𝑛0′
∀𝑛 ≥ 𝑛0′′ : 𝑓 𝑛 ≤ 𝑐 ∙ 𝑔 𝑛 ≤ 𝑐 ∙ 𝑐 ′ ∙ ℎ(𝑛)
Für 𝑐 ′′ = 𝑐 ∙ 𝑐′ folgt 𝑓 𝑛 = Ο ℎ 𝑛
∎
• Beispiel:



⇒
⇒
⇒
⇒
𝑓 𝑛 = 3𝑛5 + 4𝑛3 + 15
𝑔 𝑛 = 𝑛5
ℎ 𝑛 = 7𝑛7 + 2𝑛4 + 3𝑛
𝑓 𝑛 = Ο 𝑔 𝑛 haben wir bereits gezeigt
1
1
Für 𝑐 = 7, 𝑛0 = 1 gilt: ∀𝑛 ≥ 1: 𝑛5 ≤ 7 ∙ 7𝑛7 + 2𝑛4 + 3𝑛
𝑔 𝑛 =Ο ℎ 𝑛
𝑓 𝑛 =Ο ℎ 𝑛
5
Ausnutzen der Monotonie
+
• Satz: Seien 𝑓, 𝑔 und ℎ Funktionen von ℝ+
nach
ℝ
0
0 . Sei ℎ
streng monoton wachsend. Dann gilt
∃𝑛0 > 0 ∀𝑛 ≥ 𝑛0 : 𝑓 𝑛 ≤ 𝑔 𝑛
⟺ ∃𝑛0′ > 0 ∀𝑛 ≥ 𝑛0′ : ℎ 𝑓 𝑛 ≤ ℎ 𝑔 𝑛
• Beweis:
 „⇒“ folgt aus Monotonie von ℎ, wobei 𝑛0′ = 𝑛0
 „⇐“:
⇒ Angenommen, es gibt ein 𝑛0′′ ≥ 𝑛0′ mit 𝑓 𝑛0′′ > 𝑔 𝑛0′′
⇒ Aus der Monotonie von ℎ folgt: ℎ 𝑓 𝑛0′′ > ℎ 𝑔 𝑛0′′ ↯
∎
• Beispiel:
 𝑓 𝑛 = log 𝑛
 𝑔 𝑛 = 𝑛
 ℎ 𝑛 = 2𝑛
⇒ log 𝑛 = Ο 𝑛 haben wir bereits gezeigt
⇒ 2log 𝑛 = Ο 2 𝑛
6
Agenda
1.
2.
3.
4.
5.
Organisatorisches
Die Landau-Notation (Fortsetzung)
Fragen und Übungsaufgaben zum ersten Übungsblatt
Rekursive Algorithmen
Divide & Conquer
7
Fragen zu Aufgabe 1
8
Übungsaufgabe zu Aufgabe 1
1. Seien 𝑎, 𝑏 ∈ ℝ positive Konstanten, dann gilt 𝑎 𝑥+𝑏 ∈ Θ 𝑎 𝑥 .
𝑓(𝑛)
lim
𝑛→∞ 𝑔(𝑛)
2. Wenn
𝑓 ∈ Ο(𝑔).
existiert und 0 ≤
𝑓 𝑛
lim
𝑛→∞ 𝑔 𝑛
< ∞, dann gilt
Hinweis: Der Grenzwert ist definiert als
lim 𝑓(𝑥) = 𝑘 ⇔ ∀𝜖 > 0 ∃𝑥0 ∀𝑥 ≥ 𝑥0 : 𝑓 𝑥 − 𝑘 < 𝜖
𝑛→∞
9
Fragen zu Aufgabe 2
10
Übungsaufgabe zu Aufgabe 2
𝑓(𝑛)
𝑔(𝑛)
2𝑛
2𝑛+1
2𝑛
22𝑛
2𝑛
𝑛!
11
Fragen zu Aufgabe 3-1
12
Fragen zu Aufgabe 3-2
13
Übungsaufgabe zu Aufgabe 3
14
Übungsaufgabe zu Aufgabe 3 (2)
15
Fragen zu Aufgabe 4-1
16
Fragen zu Aufgabe 4-2
17
Übungsaufgabe zu Aufgabe 4
Gegeben sei ein Array 𝐴 von Zahlen mit |𝐴| = 𝑛
Elementen aus {1, … , 𝑛}. Es soll überprüft werden, ob das
Array eines oder mehrere Duplikate enthält.
1. Entwerfen Sie einen Algorithmus, der als Eingabe das
Array 𝐴 erhält und ausgibt, ob in diesem Array
Duplikate enthalten sind. Notieren Sie diesen
Algorithmus als Pseudocode.
2. Analysieren Sie die Laufzeit Ihres in Pseudocode
vorgestellten Algorithmus (d.h. geben Sie eine
möglichst gute obere Schranke für die Komplexität an
und begründen Sie diese).
18
Agenda
1.
2.
3.
4.
5.
Organisatorisches
Die Landau-Notation (Fortsetzung)
Fragen und Übungsaufgaben zum ersten Übungsblatt
Rekursive Algorithmen
Divide & Conquer
19
Münzen wiegen
• Gegeben




𝑛 identisch aussehende Münzen, eine Waage mit zwei Waagschalen
genau eine der 𝑛 Münzen ist gefälscht
alle echten Münzen wiegen exakt dasselbe
die falsche Münze ist leichter
• Aufgabe
 Finde die falsche Münze mit möglichst wenigen Wiegeoperationen
20
Naive Lösung
• Algorithmus: Direktvergleich
 Input: 𝑛 Münzen 𝑚1 , … , 𝑚𝑛
 for 𝑖 = 2 to 𝑛 do
 if Münze 𝑚1 und 𝑚𝑖 haben ungleiches Gewicht then
• return leichtere der beiden Münzen
• Korrektheit:
 alle echten Münzen haben identisches Gewicht
 somit genügt es, alle Münzen mit der ersten Münze zu vergleichen
• Laufzeit:
 Best-case: 𝑚1 oder 𝑚2 ist die falsche Münze (1 Wiegeoperation)
 Worst-case: 𝑚𝑛 ist die falsche Münze (𝑛 − 1 Wiegeoperationen)
 Algorithmus Direktvergleich benötigt somit Θ(𝑛) Wiegeoperationen
21
Rekursive Lösung
• Annahme: 𝑛 = 2𝑘 für ein beliebiges 𝑘 ∊ ℕ
• Algorithmus: D&C-Wiegen(𝑀)
 Input: Münzmenge 𝑀
 if |𝑀| = 2 then
 return leichteres Element von 𝑀
 else
 teile 𝑀 in zwei gleich große Münzmengen 𝑀1 und 𝑀2
 𝑀′ ← leichtere der beiden Mengen 𝑀1 und 𝑀2
 D&C-Wiegen(𝑀′)
• Korrektheit: falsche Münze muss immer in der leichteren Hälfte
liegen muss
• Laufzeit (informell):
 Wiegeoperation halbiert die Anzahl der möglichen Kandidaten
 nach log n Wiegeoperationen nur genau ein Kandidat
 Fall: 𝑛 ≠ 2𝑘
 Falls in irgendeinem Schritt |𝑀| ungerade
•
•
•
•
entferne zunächst eine Münze und teile dann
Falls Gleichheit beim Wiegen: entfernte Münze ist die gesuchte
Andernfalls: weiter wie beschrieben
Anzahl der Kandidaten verkleinert sich um mehr als die Hälfte
 Fall 𝑛 = 2𝑘 ist worst case
22
Agenda
1.
2.
3.
4.
5.
Organisatorisches
Die Landau-Notation (Fortsetzung)
Fragen und Übungsaufgaben zum ersten Übungsblatt
Rekursive Algorithmen
Divide & Conquer
23
Divide & Conquer
• Idee
 Teile Problem in Teilprobleme auf (divide)
 Löse diese rekursiv (conquer)
 Setze aus den Lösungen der Teilprobleme die Lösung für das
Gesamtproblem zusammen (merge)
• Darstellung als Rekursionsbaum
 𝑇(𝑛) = Anzahl Operationen für Eingabe der Größe 𝑛
T(n)
divide
divide
Kosten pro innerer Knoten:
divide + merge
merge
T(m)
T(m)
…
…
wichtig: 𝑚 < 𝑛
T(m)
merge
T(2)
T(2)
T(2)
Abbruch, wenn
Eingabe klein genug
…
T(2)
T(2)
Kosten pro Blatt:
conquer
T(2)
24
Ausblick: Nächste Woche
•
•
•
•
Besprechung der Lösungen des ersten Übungsblatts
Vorstellung des zweiten Übungsblatts
Fragen?
Gruppen „TT“ und „complexity102“
25

Download Report