Informatik B SoSe 2016

6. Aufgabenblatt zur Vorlesung
Informatik B
SoSe 2016
Wolfgang Mulzer
Abgabe am 7. Juni 2016 bis 12 Uhr in die Tutorenfächer
Aufgabe 1 Heap-Sort
10 Punkte
Die folgende Variante von Heapsort kommt nur mit bubbleDown aus.
def heapSort2(a):
# Erstelle Heap in der Eingabeliste
for i in range(len(a) - 1, -1, -1):
bubbleDown(a, len(a), i)
# Entferne wiederholt das Maximum
for i in range(len(a) - 1, 0, -1):
# Tausche Wurzel an die richtige Stelle
swapElements(a, 0, i)
# Benutze bubbledown, um die Max-Heap-Eigenschaft
# herzustellen der Heap befindet sich in den ersten
# i Plaetzen der Eingabeliste
bubbleDown(a, i)
(a) Demonstrieren Sie den modifizierten Algorithmus für die folgende Eingabeliste:
2; 5; 16; 4; 10; 23; 29; 18; 26; 15.
(b) Begründen Sie kurz, warum der modifizierte Algorithmus funktioniert. Argumentieren Sie dazu mit Hilfe von binären Heaps.
Vorschlag: Es ist hifreich, sich mehrere Heaps vorzustellen, die in der Eingabeliste angelegt werden. Durch die bubbleDown-Aufrufe werden Heaps zusammengeführt.
(c) Beweisen Sie, dass die folgende Schleife nur O(n) Vergleiche der Eingabeelemente durchführt:
for i in range(len(a) - 1, -1, -1):
bubbleDown(a, len(a), i)
Hinweis: Wie viele Vergleiche benötigt bubbleDown
maximal bei einem Heap
Plog(n+1)
n+1
· 3(i − 1) = O(n).
mit i Ebenen? Außerdem gilt für alle n ∈ N: i=1
2i
Aufgabe 2 O-Notation
10 Punkte
√
(a) Algorithmus A hat Laufzeit 10n log2 n, Algorithmus B hat Laufzeit n n und
Algorithmus C hat Laufzeit n2 . Bestimmen Sie die Eingabegröße n0 , ab der A
effizienter ist als B, und die Eingabegröße n1 , ab der A effizienter ist als C.
(b) Zeigen Sie anhand der Definition, dass n log8 n ∈ Θ(n log2 n2 ) ist.
(c) Sortieren Sie die folgenden Funktionen aufsteigend bezüglich ihres asymptotischen Wachstums und markieren Sie die Funktionen mit gleichem asymptotischen Verhalten:
3
10
n ; 4n log n + 2n; 2 ; 2
log4 n
n
2
; 3n + 100 log n; 4n; 2 ; n + 10n;
n−1
X
i2 .
i=0
Aufgabe 3 Algorithmik
10 Punkte
(a) Geben Sie ein Verfahren mit Laufzeit O(n + k log n) zur Bestimmung des k.kleinsten Elementes unter n Zahlen an. Begründen Sie die Laufzeit. Implementieren Sie Ihren Algorithmus in Python.
Hinweis: Beachten Sie Aufgabe 1c.
(b) Gegeben sei eine n × n Matrix mit ganzzahligen Einträgen. Dabei seien jeweils
jede Zeile und jede Spalte aufsteigend sortiert. Geben Sie einen Algorithmus
mit Laufzeit O(n) an, der entscheidet, ob eine Anfragezahl x in der Matrix
vertreten ist oder nicht. Begründen Sie die Laufzeit. Implementieren Sie Ihren
Algorithmus in Python.
Machen Sie geeignete Testläufe, und achten Sie auf eine angemessene Fehlerbehandlung und Dokumentation Ihres Programms.

Download Report