Informatik (Subject) / A&D (Rekursion) (Lesson)

This lesson was created by scarvy.

Learn lesson

This lesson is not released for learning.

back  |  next 1 / 1

• Erkläre wohlfundierte Rekursion anhand von build: build :: [a] -> Tree abuild [] = Nilbuild [a] = Leaf abuild as = Br (build (take k as)) (build (drop k as))where k = length as ‘div‘ 2
• Erkläre die Beziehung von wohlfundierter und struktureller Rekursion anhand von isort: > -- insertion sort: die Elemente werden nacheinander an die richtige Position "geschoben" (vgl. insert). > isort :: (Ord a) => [a] -> [a]> isort []     = []> isort (x:xs) = insert x (isort xs) > insert :: (Ord a) => a -> [a] -> [a]> insert x []     = [x]> insert x (a:as) = if x <= a >                   then (x:a:as) >                   else a : insert x as
• Erkläre wohlfundierte und strukturierte Rekursion anhand von Beispielen. wohlfundiert: > qsort :: (Ord a) => [a] -> [a]> qsort (x:xs) = qsort less ++ [x] ++ qsort more>  where >  less = filter (x >) xs>  more = filter (x <=) xs> qsort [] = []   strukturell: > length' :: [a] -> Int> length' []     = 0> length' (x:xs) = 1 + length xs   ham: [a] -> [a] -> Boolham: [] _ = 0 ham (x:xs) (y:ys) = if x == y                                 then ham xs yx                                  else 1+ham xs ys  
• Was versteht man unter struktureller Rekursion? = Problemzerlegung durch direkte Zerlegung der Datenstruktur, d.h. die Struktur der Daten ist entscheidend für die Anwendbarkeit der Rekursion.Letztendlich ist es ein Induktionsverfahren, bei dem das Ergebnis der Funktion für einen Wert definiert ist über das Ergebnis eines kleineren Wertes (i-1, xs aus (x:xs). Damit ist die Terminierung garantiert, da man irgendwann beim kleinsten Element ankommt. (0, [], etc.)
• Was versteht man unter wohlfundierter Rekursion? = Zerlegung des Problems erfolgt nicht dem rekursiven Aufbau der Datenstruktur. Die Aufgabe wird auf beliebig einfacherer Aufgaben zurückgeführt - Hilfskonstrukt Ord( -nungrelation)--> heißt wohlfundiert, wenn jede absteigende Kette endlich ist
• Was bedeutet: Dynamische Programmierung= Rekursion + Tabelle - Dynamische PRogrammierung ist eine Methode zum algorithmische Lösen von Optimierungsproblemen - Begriff wurde in den 1949er Jahren von Richard Bellman eingeführt, der duese Methode der Regelugstheorie anwandte: Bellmans Prinzip der dynamische Programmierung - kann erfolgreich genutzt werden, wenn das Problem aus vielen gleichartigen Teilproblemen besteht und eine optimale Lösung des Problens sich aus Lösungen der Teilprobleme zusammensetzt: Optimalitätsprinzip von Bellmann. -dieses Verfahren setzt man fort bis das ursprüngliche Problem gelöst wurde-> einmal berechnte Teilergebnisse werden in einer Liste gespeichert-> bei gleichartigen Teilproblemen wird darauf zugegriffen => so vermeidet man kospielige Rekursion, weil bekannte Ergebnisse wieder verwendet werden.

back  |  next 1 / 1