#acl -All:read Sabine Storandt:read,write Björn Buchhold:read,write Claudius Korzen:read,write Elmar Haußmann:read,write == AUFGABE 1 (Programmm + Laufzeitbestimmung) == === 1.1 Funktion zur Berechnung der zweitgrößten Zahl in einem Feld der Größe >= 2 === {{{ def secondLargest(A): max1 = A[0] max2 = A[1] if max2 > max1: max1, max2 = max2, max1 for i in range(2, len(A)): if A[i] > max2: if A[i] > max1: max2 = max1 max1 = A[i] else: max2 = A[i] return max2 }}} === 1.2 Laufzeit rekursive Berechnung Fibonacci-Zahlen === Es gilt offensichtlich T,,n,, >= T,,n-1,, + T,,n-2,,. Induktionsanfang: T_1 >= 2 und T_2 >= 1 gilt offensichtliche. Induktionschritt: Nach Induktionsvoraussetzung ist T,,n-1,, >= F,,n-1,, und T,,n-2,, >= F,,n-2,,. Damit T,,n,, >= T,,n-1,, + T,,n-2,, >= F,,n-1,, + F,,n-2,, = F,,n,,. === 1.3 Funktion zur Berechnung von F_n in Zeit O(n), für n >= 2 === {{{ def fastFibonacci(n): fibs = [1] * n for i in range(2, n): fibs[i] = fibs[i - 1] + fibs[i - 2] return fibs[n-1] }}} == AUFGABE 2 (Felder + Hashing) == === 2.1 Funktion zum Suchen und Löschen eines Elementes aus einem Feld === {{{ def removeFromArray(A, x): i = 0 # Find the element. while i < len(A) and A[i] != x: i = i + 1 # If found, swap to the end and remove last element. if i < len(A): A[i], A[-1] = A[-1], A[i] A.pop() }}} === 2.2 Funktion zum Löschen eines Elementes aus einer Hashtabelle === {{{ def removeFromHashTable(T, h, x): removeFromArray(T[h(x)], x) }}} === 2.3 Laufzeit der Funktionen aus Aufgabe 2.1 und 2.2 === Die Funktion aus Aufgabe 2.1 hat Laufzeit Theta(i), wenn das Element an Stelle i steht bzw. Theta(n) wenn das Element nicht im Feld steht. Die Funktion aus Aufgabe 2.2 hat Laufzeit Theta(1) im besten Fall (unter h(x) stehen in T nur konstant viele Elemente) und Laufzeit Theta(n) im schlechtesten Fall (alle Elemente in T werden auf h(x) abgebildet und das gesuchte Element ist nicht dabei oder steht ganz am Ende des Feldes). === 2.4 Klasse H nicht 1-universell, wenn |H| < m und |U| > m === Nach Definition von 1-universell müsste für alle x, y mit x != y gelten, dass |{h: h(x) = h(y)}| <= c * |H| / m < 1, also = 0. Das heißt, für jedes Schlüsselpaar x, y mit x != y darf es keine Hashfunktion geben, unter der die beiden Schlüssel auf dasselbe abgebildet werden. Für jede Hashfunktion h muss es aber zwei Schlüssel geben, die auf dasselbe abgebildet werden, weil es > m Schlüssel gibt aber nur m Plätze in der Hashtabelle. == AUFGABE 3 (Binäre Heaps) == === 3.1 Heapzustand (als Baum und als Feld) nach dem Einfügen von 5, 4, 3, 2, 1 (in der Reihenfolge) === === 3.2 Funktion zur Überprüfung der Heapeigenschaft === {{{ def checkHeapProperty(heap): for i in range(2, len(heap)): child_value = heap(i) parent_value = heap(i/2) if child_value < parent_value: return False return True }}} == AUFGABE 4 (Graphen) == === 4.2 Funktion zur Berechnung der Anzahl Kanten mit Adjazenzlisten === {{{ # graph is represented as an array of n adjacency lists, where n = #nodes. def numEdges(graph): count = 0 for i in range(0, len(graph)): count += len(graph[i]) return count }}} === 4.3 Funktion zur Berechnung der Anzahl Kanten mit Adjazenzmatrix === {{{ # graph is represented as an array of n array, each of size n, where n = #nodes. def numEdges(graph): count = 0 n = len(graph) for i in range(0, n): for j in range(0, n): if graph[i][j] > 0: count += 1 return count }}}