Universität Bielefeld Technische Fakult¨ at AG Praktische Informatik ¨ Ubung zu den Vorlesungen Algorithmen & Datenstrukturen Programmieren in Haskell Wintersemester 2014/2015 Aufgabe 9.1 (8 Punkte): Gegeben sei die Matrix-Kette M1 · M2 · . . . · M6 mit den folgenden Dimensionen: (8, 17), (17, 5), (5, 55), (55, 9), (9, 4), (4, 77). 1. Bestimmen Sie die optimale Klammerung f¨ ur die Berechnung des oben genannten Matrix-Ketten-Produkts. Wie hoch ist hierbei der Aufwand in Form von Multiplikationen? Das Kriterium f¨ ur Optimalit¨ at und die Definition von Aufwand wurden in der Algorithmen & Datenstrukturen-Vorlesung definiert. 2. Schreiben Sie eine Haskell -Funktion aufwand’ :: Dim -> Dim -> Aufw, die den Aufwand der Multiplikation zweier Matrizen berechnet, wobei type Dim = (Int, Int) und type Aufw = Int. 3. Im Allgemeinen bestimmt sich der Aufwand zur Berechnung eines Matrix-KettenProdukts nicht nur aus dem Aufwand der finalen Multiplikation, sondern zus¨atzlich auch aus dem gesamten vorherigen Aufwand. Zur genauen Berechnung des GesamtAufwands ist bei jedem Zwischenschritt notwendig, die Dimensionen der bis dahin berechneten Matrizen zu kennen. Adaptieren Sie aufwand’ daher so, dass der Gesamtaufwand berechnet wird: aufwand :: (Dim, Aufw) -> (Dim, Aufw) -> (Dim, Aufw). F¨ ur eine einzelne Matrix (zeilen,spalten) :: Dim gilt ((zeilen,spalten),0). 4. Schreiben Sie eine Funktion minMat :: [Dim] -> (Dim, Aufw), die den minimalen Aufwand einer Matrix-Ketten-Multiplikation berechnet. Verwenden Sie, falls m¨oglich, die bereits implementierte Funktion auf Aufgabenteil 3. 5. Die Anzahl m¨ oglicher Klammerungen f¨ ur eine Matrix-Ketten-Multiplikation ist exponentiell bez¨ uglich der Anzahl enthaltener Matrizen. Mittels dynamischer Programmierung (DP) l¨ asst sich eine optimale Klammerung innerhalb polynomieller Laufzeit bestimmen. Entwickeln Sie eine DP Variante von minMat, die sich des Tabellierens von Zwischenergebnissen bedient. 6. In welcher Effizienzklasse liegt die DP Variante von minMat? Begr¨ unden Sie diese ¨ Uberlegung. Aufgabe 9.2 (3 Punkte): Beweisen oder widerlegen Sie die folgenden Aussagen: 1. foldr (-) 0 [1..n] = - (foldr (-) 0 [0..n]) 2. F¨ ur gerade n gilt: foldr (-) 0 [1..n] = - n/2 Abgabe: Mittwoch, 17.12.2014, 16:00 Uhr. Bearbeitung in 2er Gruppen (alle Namen und Tutor auf die Abgabe schreiben). 1
© Copyright 2024 ExpyDoc
