Funktionale Programmierung und Verifikation - Exam.pdf

Aufgabe 1)

Angenommen Du hast eine funktionale Sprache, die Funktionen als erstklassige Bürger unterstützt. Diese Sprachmerkmale ermöglichen es Funktionen, als Argumente übergeben, von anderen Funktionen zurückgegeben und in Variablen gespeichert zu werden. Funktionale Programmierung fördert den höheren Abstraktionsgrad und wiederverwendbaren Code. Betrachte die folgende Funktionalität für die nächsten Teilaufgaben.

a)

Definiere eine Funktion

compose

, die zwei Funktionen

f

und

g

nimmt und eine neue Funktion zurückgibt, welches das Ergebnis der Anwendung von

f

auf das Ergebnis von

g

ausführt. Das bedeutet, wenn

f(x)

und

g(x)

Funktionen sind, sollte

compose(f, g)(x)

das gleiche Ergebnis wie

f(g(x))

liefern.

Lösung:

Um die Funktion

compose

in einer funktionalen Sprache zu definieren, die Funktionen als erstklassige Bürger unterstützt, müssen wir eine Funktion schreiben, die zwei andere Funktionen,

f

und

g

, als Argumente akzeptiert und eine neue Funktion zurückgibt. Diese neue Funktion wendet zuerst

g

auf ein Argument

x

an und übergibt das Ergebnis dann an die Funktion

f

.

Hier ist ein Beispiel, wie Du dies in Python tun könntest:

def compose(f, g):  return lambda x: f(g(x))

• Die Funktion

  compose

  nimmt die Funktionen

  f

  und

  g

  als Argumente.
• Sie gibt eine neue Funktion zurück, die ein Argument

  x

  akzeptiert.
• Die neue Funktion wendet zuerst

  g

  auf

  x

  an und dann

  f

  auf das Ergebnis von

  g(x)

  .

Ein Beispiel zur Verwendung der

compose

Funktion:

# Definition von zwei einfachen Funktionen def add_one(x):     return x + 1 def square(x):     return x * x # Erzeugen einer neuen Funktion durch Komposition der oben definierten Funktionen new_function = compose(add_one, square) # Anwendung der neuen Funktion auf ein Argument result = new_function(5)  # Dies ergibt (5 * 5) + 1, also 26 print(result)  # Ausgabe: 26

In diesem Beispiel haben wir zwei Funktionen

add_one

und

square

definiert. Mit der

compose

Funktion erzeugen wir eine neue Funktion

new_function

, die zuerst

square

auf

x

anwendet und dann

add_one

auf das Ergebnis von

square(x)

.

b)

Implementiere eine Funktion

filter

, die eine Liste von Werten und eine Prädikatsfunktion (eine Funktion, die

true

oder

false

zurückgibt) akzeptiert und eine neue Liste zurückgibt, die nur die Werte enthält, für die das Prädikat

true

zurückgibt. Zeige ein Beispiel mit einer Liste von ganzen Zahlen und einer Prädikatsfunktion, die prüft, ob eine Zahl gerade ist.

Lösung:

Um die Funktion

filter

in einer funktionalen Sprache zu implementieren, die Funktionen als erstklassige Bürger unterstützt, müssen wir eine Funktion schreiben, die eine Liste von Werten und eine Prädikatsfunktion als Argumente akzeptiert. Diese Funktion sollte eine neue Liste zurückgeben, die nur die Werte enthält, für die das Prädikat

true

zurückgibt.

Hier ist ein Beispiel, wie Du dies in Python tun könntest:

def filter(predicate, values):  return [value for value in values if predicate(value)]

• Die Funktion

  filter

  nimmt eine Prädikatsfunktion

  predicate

  und eine Liste von Werten

  values

  als Argumente.
• Sie gibt eine neue Liste zurück, die nur die Werte enthält, für die das Prädikat

  true

  zurückgibt.

Ein Beispiel zur Verwendung der

filter

Funktion:

# Definition der Prädikatsfunktion def is_even(x):     return x % 2 == 0 # Eine Liste von ganzen Zahlen numbers = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10] # Anwendung der filter Funktion mit der Prädikatsfunktion und der Liste result = filter(is_even, numbers) print(result)  # Ausgabe: [2, 4, 6, 8, 10]

In diesem Beispiel haben wir eine Prädikatsfunktion

is_even

definiert, die prüft, ob eine Zahl gerade ist. Mit der

filter

Funktion erzeugen wir eine neue Liste

result

, die nur die geraden Zahlen aus der ursprünglichen Liste

numbers

enthält.

c)

Erläutere die Mathematik hinter der Anwendung von Funktionen als erstklassige Bürger durch das Lösen folgender mathematischer Kompositionsregeln. Beweise, dass für alle Funktionen

f

,

g

und

h

die Komposition

compose(compose(f, g), h)

gleich

compose(f, compose(g, h))

ist.

Lösung:

Die Mathematik hinter der Anwendung von Funktionen als erstklassige Bürger kann durch die Untersuchung der Eigenschaften der Komposition von Funktionen beschrieben werden. Insbesondere können wir die Assoziativität der Funktionkomposition beweisen. Das bedeutet, dass die Komposition von drei Funktionen in einer bestimmten Reihenfolge das gleiche Ergebnis liefert, unabhängig davon, wie wir die Funktionen gruppieren. Im Folgenden zeigen wir den Beweis für die Assoziativität der Funktionkomposition:

Angenommen, wir haben drei Funktionen

f

,

g

und

h

. Wir zeigen, dass

compose(compose(f, g), h)

gleich

compose(f, compose(g, h))

ist.

• Schritt 1: Definiere die Kompositionen. Für zwei Funktionen

  f

  und

  g

  ist die Komposition

  compose(f, g)

  definiert als:

  compose(f, g)(x) = f(g(x))

• Schritt 2: Anwenden der Definition. Für

  compose(compose(f, g), h)

  gilt:

  compose(compose(f, g), h)(x) = compose(f, g)(h(x)) = f(g(h(x)))

• Schritt 3: Erneutes Anwenden der Definition. Für

  compose(f, compose(g, h))

  gilt:

  compose(f, compose(g, h))(x) = f(compose(g, h)(x)) = f(g(h(x)))

In beiden Fällen erhalten wir:

compose(compose(f, g), h)(x) = f(g(h(x))) = compose(f, compose(g, h))(x)

Damit haben wir gezeigt, dass für alle Funktionen

f

,

g

und

h

die Komposition

compose(compose(f, g), h)

gleich

compose(f, compose(g, h))

ist. Diese Eigenschaft wird Assoziativität der Funktionkomposition genannt.

Zusammenfassend kann gesagt werden, dass die Assoziativität der Funktionkomposition sicherstellt, dass wir Funktionen in beliebiger Reihenfolge gruppieren können, ohne das Ergebnis zu verändern. Dies ist eine grundlegende Eigenschaft der Funktionkomposition und hilft dabei, höhere Abstraktionsebenen in der funktionalen Programmierung zu erreichen.

d)

Berücksichtige den folgenden Codeausschnitt. Erkläre den Nutzen von Funktionen als erstklassige Bürger in diesem Kontext und diskutiere, wie dies den Programmierstil und die Lesbarkeit beeinflusst:

let double = (x) => x * 2; let increment = (x) => x + 1; let incrementThenDouble = compose(double, increment); let result = map(incrementThenDouble, [1, 2, 3, 4]);

.

Lösung:

Der Begriff „Funktionen als erstklassige Bürger“ bedeutet, dass Funktionen in einer Sprache wie andere Werte behandelt werden können. Dies schließt ein, dass sie als Argumente übergeben, als Rückgabewerte von anderen Funktionen zurückgegeben und in Variablen gespeichert werden können. In diesem Kontext bringt dies zahlreiche Vorteile mit sich und beeinflusst den Programmierstil und die Lesbarkeit erheblich.

Wir analysieren den gegebenen Codeausschnitt, um dies zu verdeutlichen:

let double = (x) => x * 2; let increment = (x) => x + 1; let incrementThenDouble = compose(double, increment); let result = map(incrementThenDouble, [1, 2, 3, 4]);

• Definition einfacher Funktionen: Die Funktionen

  double

  und

  increment

  sind einfache Funktionen, die ein Argument akzeptieren und eine Berechnung durchführen.

  double

  multipliziert das Argument mit 2 und

  increment

  erhöht das Argument um 1.
• Komposition von Funktionen: Mit der Funktion

  compose

  können wir die beiden einfachen Funktionen zu einer neuen Funktion

  incrementThenDouble

  kombinieren. Diese Funktion führt zuerst

  increment

  aus und übergibt dann das Resultat an

  double

  . Das Resultat ist also das gleiche wie

  double(increment(x))

  .
• Anwendung auf Listen: Die Funktion

  map

  akzeptiert eine Funktion und eine Liste und wendet die Funktion auf jedes Element der Liste an. In diesem Fall wird

  incrementThenDouble

  auf jedes Element der Liste

  [1, 2, 3, 4]

  angewendet, was zu der neuen Liste

  [4, 6, 8, 10]

  führt.

Nutzen und Auswirkungen auf den Programmierstil und die Lesbarkeit:

• Abstraktion und Wiederverwendbarkeit: Mit Funktionen als erstklassige Bürger können wir wiederverwendbare und gut abstrahierte Bausteine erstellen. Die Funktion

  compose

  ermöglicht es uns, neue Funktionen aus bestehenden Bausteinen zu schaffen, ohne redundante oder duplizierte Logik.
• Lesbarkeit: Der Code wird durch die Verwendung von abstrakten Funktionen wie

  compose

  und

  map

  lesbarer. Er zeigt klar die Absicht und Struktur des Programms, indem er die Verarbeitungsschritte in einfache, verständliche Teile zerlegt.
• Flexibilität: Durch die Möglichkeit, Funktionen in Variablen zu speichern und als Argumente zu übergeben, wird der Code flexibler und dynamischer. Es wird einfach, verschiedene Funktionen miteinander zu kombinieren und zu manipulieren.
• Funktionale Programmierung: Diese Programmierweise fördert einen funktionalen Programmierstil, der für seine hohe Abstraktionsfähigkeit und die Möglichkeit bekannt ist, komplexe Operationen auf einfache Weise zu komponieren.

Zusammenfassend lässt sich sagen, dass Funktionen als erstklassige Bürger den Programmierstil durch hohe Abstraktionsebenen, Wiederverwendbarkeit und bessere Lesbarkeit positiv beeinflussen. Sie ermöglichen es, komplexe Logik in einfache und leicht verständliche Bausteine zu zerlegen.

Aufgabe 2)

Immutabilität und ihre BedeutungUnveränderlichkeit von Datenstrukturen nach ihrer Erzeugung hat verschiedene Vorteile:

• Sicherstellung der Zustandskonsistenz
• Einfachere Nebenläufigkeit und Parallelität
• Erleichtert Debugging und Testen
• Reduziert Seiteneffekte
• Funktionale Programmierung: Unveränderliche Datenstrukturen und reine Funktionen fördern

a)

Erkläre anhand eines Beispiels in Haskell, wie eine unveränderliche Datenstruktur den Zustand konsistent halten kann. Schreibe eine Funktion, die eine Liste von ganzen Zahlen um eins erhöht und dabei die ursprüngliche Liste unverändert lässt.

Lösung:

Immutabilität und ihre BedeutungUnveränderlichkeit von Datenstrukturen nach ihrer Erzeugung hat verschiedene Vorteile:

• Sicherstellung der Zustandskonsistenz
• Einfachere Nebenläufigkeit und Parallelität
• Erleichtert Debugging und Testen
• Reduziert Seiteneffekte
• Funktionale Programmierung: Unveränderliche Datenstrukturen und reine Funktionen fördern

Beispiel in Haskell:Um zu zeigen, wie eine unveränderliche Datenstruktur den Zustand konsistent halten kann, betrachten wir eine Funktion in Haskell. Diese Funktion erhält eine Liste von ganzen Zahlen und erhöht jede Zahl um eins, wobei die ursprüngliche Liste unverändert bleibt.Hier ist der Haskell-Code dazu:

 'incrementList :: [Int] -> [Int]  incrementList xs = map (+1) xs ' 

• incrementList :: [Int] -> [Int]: Dies definiert eine Funktion incrementList, die eine Liste von ganzen Zahlen als Eingabe erhält und eine neue Liste von ganzen Zahlen zurückgibt.
• incrementList xs = map (+1) xs: Diese Zeile implementiert die Funktion. Sie nutzt die map-Funktion, um die anonyme Funktion (+1), die jede Zahl um eins erhöht, auf jedes Element der Liste xs anzuwenden. Das Ergebnis ist eine neue Liste, die um eins erhöhte Zahlen enthält, während die ursprüngliche Liste xs unverändert bleibt.

Dieses Beispiel zeigt, wie Haskell und funktionale Programmierung im Allgemeinen die Unveränderlichkeit fördern, indem neue Datenstrukturen erzeugt werden, anstatt bestehende zu verändern. Dadurch werden Zustandskonsistenz und Vorhersehbarkeit des Codes sichergestellt.

b)

Diskutiere, wie Immutabilität die Umsetzung von nebenläufigen Programmen erleichtert. Gib ein Beispiel in einer funktionalen Programmiersprache (z.B. Haskell), das diese Vorteile verdeutlicht.

Lösung:

Immutabilität und ihre BedeutungUnveränderlichkeit von Datenstrukturen nach ihrer Erzeugung hat verschiedene Vorteile:

• Sicherstellung der Zustandskonsistenz
• Einfachere Nebenläufigkeit und Parallelität
• Erleichtert Debugging und Testen
• Reduziert Seiteneffekte
• Funktionale Programmierung: Unveränderliche Datenstrukturen und reine Funktionen fördern

Immutabilität und Nebenläufigkeit:Immutabilität kann die Entwicklung von nebenläufigen Programmen erheblich erleichtern. In Programmen, die Nebenläufigkeit oder Parallelität nutzen, ist die Koordination und Synchronisation des Zugriffs auf veränderbare Zustände oft eine große Herausforderung. Unveränderliche Datenstrukturen beseitigen viele dieser Probleme, da mehrere Threads oder Prozesse dieselben Daten lesen können, ohne sich Sorgen um konkurrierende Schreibvorgänge machen zu müssen. Das schließt Race Conditions und andere Synchronisationsprobleme weitgehend aus.Betrachten wir ein Beispiel in Haskell, das die Vorteile von Immutabilität bei der Umsetzung von nebenläufigen Programmen verdeutlicht.Hier ist ein Haskell-Code, der zeigt, wie mehrere Threads unveränderliche Datenstrukturen sicher verwenden können:

 'import Control.Concurrentimport Control.Monad-- Eine Funktion, die eine Liste von ganzen Zahlen druckt, wird implementiertprintList :: [Int] -> IO ()printList xs = forM_ xs printmain :: IO ()main = do    let numbers = [1, 2, 3, 4, 5]    -- Erstellen von zwei Threads, die beide die unveränderliche Liste verwenden    forkIO $ printList numbers    forkIO $ printList numbers    -- Warten, um sicherzustellen, dass die Threads beendet sind    threadDelay 1000000 -- 1 Sekunde in Mikrosekunden ' 

• import Control.Concurrent: Importiert das Modul zur Handhabung von Nebenläufigkeit in Haskell.
• import Control.Monad: Importiert das Modul zur Nutzung monadischer Funktionen.
• printList :: [Int] -> IO (): Definiert eine Funktion printList, die eine Liste von ganzen Zahlen erhält und diese Zahlen druckt.
• main :: IO (): Implementiert die Hauptfunktion.
• let numbers = [1, 2, 3, 4, 5]: Erzeugt eine unveränderliche Liste von ganzen Zahlen.
• forkIO $ printList numbers: Erstellt einen neuen Thread, der die printList-Funktion aufruft und die unveränderliche Liste druckt.
• threadDelay 1000000: Wartet eine Sekunde, um sicherzustellen, dass die Threads ihre Arbeit beenden.

In diesem Beispiel gibt es zwei Threads, die gleichzeitig dieselbe unveränderliche Liste von Zahlen drucken. Da die Liste unveränderlich ist, kann sie von beiden Threads sicher verwendet werden, ohne dass Synchronisation oder Sperrmechanismen notwendig sind. Dies zeigt, wie Immutabilität die parallele Programmierung sicherer und einfacher machen kann.

c)

Nenne und erkläre mindestens drei weitere Vorteile von unveränderlichen Datenstrukturen in der funktionalen Programmierung. Erkläre, wie diese Vorteile zu sichererem und effizienterem Code führen.

Lösung:

Immutabilität und ihre BedeutungUnveränderlichkeit von Datenstrukturen nach ihrer Erzeugung hat verschiedene Vorteile:

• Sicherstellung der Zustandskonsistenz
• Einfachere Nebenläufigkeit und Parallelität
• Erleichtert Debugging und Testen
• Reduziert Seiteneffekte
• Funktionale Programmierung: Unveränderliche Datenstrukturen und reine Funktionen fördern

Weitere Vorteile von unveränderlichen Datenstrukturen:Unveränderliche Datenstrukturen bieten in der funktionalen Programmierung eine Vielzahl von weiteren Vorteilen, die zu sichererem und effizienterem Code führen. Hier sind drei weitere wichtige Vorteile:

• Referenzielle Transparenz: In der funktionalen Programmierung ist einer der Hauptgedanken die referenzielle Transparenz. Eine Funktion ist referenziell transparent, wenn sie für dieselben Eingaben immer dieselben Ausgaben liefert und keinen Zustand ändert. Unveränderliche Datenstrukturen tragen wesentlich zur referenziellen Transparenz bei, da sie garantieren, dass der Zustand der Datenstruktur nach der Erstellung nicht verändert wird. Beispiel: Angenommen, wir haben eine Funktion in Haskell, die eine unveränderliche Liste absteigend sortiert. Da die Liste unveränderlich ist, wird das Ergebnis der Sortierung immer dasselbe sein, wenn die Eingabeliste dieselbe ist. Dies erleichtert das Verstehen und Testen der Funktion erheblich.
• Optimierungen durch Compiler: Unveränderliche Datenstrukturen erlauben es Compilern, aggressive Optimierungen vorzunehmen. Da der Compiler sicher sein kann, dass eine unveränderliche Datenstruktur nie geändert wird, kann er bestimmte Kopiervorgänge vermeiden und gemeinsame Daten effizient wiederverwenden. Beispiel: Eine unveränderliche Zeichenkette (String) kann von verschiedenen Teilen des Programms sicher verwendet werden, ohne dass Kopien der Zeichenkette erstellt werden müssen. Der Compiler kann die gleiche Speicheradresse an mehreren Stellen im Code verwenden, was zu einer effizienteren Speicher- und Laufzeitnutzung führt.
• Einfacherer Rückgriff auf frühere Zustände: Da unveränderliche Datenstrukturen nach ihrer Erzeugung nicht geändert werden können, ist es einfach, Sicherungskopien (Snapshots) von früheren Zuständen zu erstellen. Dies kann besonders in Programmen nützlich sein, die persistente Daten speichern oder komplexe Rückgängig-Operationen implementieren müssen. Beispiel: Angenommen, wir programmieren eine Anwendung für die Bildbearbeitung. Wenn wir jede Veränderung des Bildes in einer unveränderlichen Datenstruktur speichern, können wir leicht frühere Versionen des Bildes wiederherstellen, ohne komplizierte Rückgängig-Mechanismen implementieren zu müssen.

Diese Vorteile von unveränderlichen Datenstrukturen führen dazu, dass der Code sicherer, einfacher zu debuggen und effizienter hinsichtlich Speicher- und Laufzeitnutzung ist. Unveränderliche Datenstrukturen sorgen dafür, dass Programme vorhersagbarer und weniger fehleranfällig sind, was letztendlich die Qualität und Wartbarkeit des Codes verbessert.

Aufgabe 3)

Rekursionsprinzip und seine AnwendungenRekursionsprinzip ist eine Methode, bei der eine Funktion sich selbst aufruft, um Probleme zu lösen.

• Basisfall: stoppt die Rekursion und gibt ein direktes Ergebnis zurück.
• Rekursiver Fall: Funktion löst ein kleineres Teilproblem und verwendet dessen Lösung zur Lösung des Gesamtproblems.
• Anwendungsbeispiele:
  • Summe einer Liste: sum(lst) = lst[0] + sum(lst[1:])
  • Fakultät: n! = n * (n-1)!
  • Fibonacci-Folge: fib(n) = fib(n-1) + fib(n-2)

a)

Teilaufgabe 1:Implementiere eine rekursive Funktion in Haskell, die die Summe einer Liste von ganzen Zahlen berechnet. Erläutere den Basisfall und den rekursiven Fall. Schreibe die Funktion so, dass sie folgende Eigenschaften erfüllt:

sumList :: [Int] -> IntsumList [] = 0sumList (x:xs) = x + sumList xs

• Hinweis: Teste Deine Funktion mit den Listen [1,2,3,4,5] und [] und gib jeweils das Ergebnis an.

Lösung:

Rekursionsprinzip und seine Anwendungen

Das Rekursionsprinzip ist eine Methode, bei der eine Funktion sich selbst aufruft, um Probleme zu lösen.

• Basisfall: stoppt die Rekursion und gibt ein direktes Ergebnis zurück.
• Rekursiver Fall: Die Funktion löst ein kleineres Teilproblem und verwendet dessen Lösung zur Lösung des Gesamtproblems.
• Anwendungsbeispiele:
  • Summe einer Liste: sum(lst) = lst[0] + sum(lst[1:])
  • Fakultät: n! = n * (n-1)!
  • Fibonacci-Folge: fib(n) = fib(n-1) + fib(n-2)

Teilaufgabe 1:

Implementiere eine rekursive Funktion in Haskell, die die Summe einer Liste von ganzen Zahlen berechnet. Erläutere den Basisfall und den rekursiven Fall. Schreibe die Funktion so, dass sie folgende Eigenschaften erfüllt:

sumList :: [Int] -> IntsumList [] = 0sumList (x:xs) = x + sumList xs

• Erklärung:
  • Basisfall: Wenn die Liste leer ist (d.h. []), dann ist die Summe 0. Dies wird durch die Zeile sumList [] = 0 dargestellt.
  • Rekursiver Fall: Wenn die Liste nicht leer ist, wird der erste Wert der Liste (d.h. x) genommen und die Summe der restlichen Liste (xs) rekursiv berechnet. Dies wird durch die Zeile sumList (x:xs) = x + sumList xs dargestellt.
• Hinweis: Teste Deine Funktion mit den Listen [1,2,3,4,5] und [] und gib jeweils das Ergebnis an.

Testergebnisse:

• sumList [1,2,3,4,5] ergibt 15.
• sumList [] ergibt 0.

b)

Teilaufgabe 2:Implementiere eine rekursive Funktion in Haskell, die die Fibonacci-Folge für ein gegebenes n berechnet. Diskutiere die Effizienz dieser Methode und vergleiche sie mit einer iterativen Implementierung. Schreibe die Funktionen so, dass Sie beide folgende Eigenschaften erfüllen:

-- Rekursive Implementierungfib :: Int -> Intfib 0 = 0fib 1 = 1fib n = fib (n-1) + fib (n-2)-- Iterative ImplementierungfibIter :: Int -> IntfibIter n = fibHelper n 0 1 where    fibHelper 0 a _ = a    fibHelper n a b = fibHelper (n-1) b (a+b)

• Hinweis: Vergleiche die Ergebnisse und die Performance der beiden Implementierungen für die Werte n = 10 und n = 20.

Lösung:

Rekursionsprinzip und seine Anwendungen

Das Rekursionsprinzip ist eine Methode, bei der eine Funktion sich selbst aufruft, um Probleme zu lösen.

• Basisfall: stoppt die Rekursion und gibt ein direktes Ergebnis zurück.
• Rekursiver Fall: Die Funktion löst ein kleineres Teilproblem und verwendet dessen Lösung zur Lösung des Gesamtproblems.
• Anwendungsbeispiele:
  • Summe einer Liste: sum(lst) = lst[0] + sum(lst[1:])
  • Fakultät: n! = n * (n-1)!
  • Fibonacci-Folge: fib(n) = fib(n-1) + fib(n-2)

Teilaufgabe 2:

Implementiere eine rekursive Funktion in Haskell, die die Fibonacci-Folge für ein gegebenes n berechnet. Diskutiere die Effizienz dieser Methode und vergleiche sie mit einer iterativen Implementierung. Schreibe die Funktionen so, dass sie beide folgende Eigenschaften erfüllen:

-- Rekursive Implementierungfib :: Int -> Intfib 0 = 0fib 1 = 1fib n = fib (n-1) + fib (n-2)-- Iterative ImplementierungfibIter :: Int -> IntfibIter n = fibHelper n 0 1 where    fibHelper 0 a _ = a    fibHelper n a b = fibHelper (n-1) b (a+b)

• Diskussion der Effizienz:
  • Die rekursive Implementierung der Fibonacci-Folge ist ineffizient, da sie eine exponentielle Laufzeit hat. Das liegt daran, dass viele Berechnungen mehrfach ausgeführt werden.
  • Die iterative Implementierung der Fibonacci-Folge ist effizienter, da sie eine lineare Laufzeit hat. Hier werden die Zwischenresultate in Variablen gespeichert und schrittweise berechnet, wodurch keine doppelten Berechnungen notwendig sind.
• Vergleich der Ergebnisse und der Performance:
  • Für n = 10 ergeben beide Implementierungen den Wert 55.
  • Für n = 20 ergeben beide Implementierungen den Wert 6765. Allerdings ist die iterative Implementierung deutlich schneller.
• Hinweis: Teste Deine Funktionen mit den Werten n = 10 und n = 20 und beobachte die Performance.

Aufgabe 4)

Du bist Entwickler einer funktionalen Programmiersprache und sollst eine Funktion implementieren, die eine Liste von Ganzzahlen analysiert und bestimmte Operationen ausführt, basierend auf den Mustern der Elemente in der Liste.

a)

Implementiere eine Funktion sumFirstTwo, die eine Liste von Ganzzahlen als Eingabe nimmt und die Summe der ersten beiden Elemente zurückgibt. Wenn die Liste weniger als zwei Elemente hat, soll die Funktion 0 zurückgeben.

fun sumFirstTwo(lst: List[Int]): Int = lst match {  // Dein Code hier}

Lösung:

Hier ist die Lösung für das Teilproblem:Eine Funktion, die die Beschreibung erfüllt, kann in einer funktionalen Programmiersprache wie Scala implementiert werden. Diese Funktion prüft die Anzahl der Elemente in der Liste und bestimmt dann, ob sie die Summe der ersten beiden Elemente oder 0 zurückgeben soll.Schreibe den Code wie folgt:

fun sumFirstTwo(lst: List[Int]): Int = lst match {  case x :: y :: _ => x + y  case _ => 0}

• case x :: y :: _: Wenn die Liste mindestens zwei Elemente x und y enthält, wird die Summe von x und y zurückgegeben.
• case _: Wenn die Liste weniger als zwei Elemente hat, wird 0 zurückgegeben.

b)

Erweitere die Funktion sumFirstTwo, damit sie nicht nur die Summe der ersten zwei Elemente ausgibt, sondern auch die Summe aller Elemente, falls die Liste mehr als zwei Elemente hat. Wenn die Liste genau zwei Elemente hat, soll die Funktion die Summe dieser beiden Elemente zurückgeben. Anderenfalls soll sie 0 zurückgeben.

fun sumFirstTwoOrAll(lst: List[Int]): Int = lst match {  // Dein Code hier}

Lösung:

Hier ist die erweiterte Lösung für das Teilproblem:Die Funktion soll verschiedene Bedingungen prüfen und basierend darauf unterschiedliche Summen zurückgeben. Hier ist der passende Scala-Code, um die erweiterten Anforderungen zu erfüllen:

fun sumFirstTwoOrAll(lst: List[Int]): Int = lst match {  case x :: y :: Nil => x + y       // Wenn die Liste genau zwei Elemente hat  case _ if lst.length > 2 => lst.sum   // Wenn die Liste mehr als zwei Elemente hat  case x :: y :: _ => x + y      // Für alle anderen Fälle mit mindestens zwei Elementen  case _ => 0                   // Wenn die Liste weniger als zwei Elemente hat}

• case x :: y :: Nil: Wenn die Liste genau zwei Elemente hat, wird die Summe dieser beiden Elemente zurückgegeben.
• case _ if lst.length > 2: Wenn die Liste mehr als zwei Elemente hat, wird die Summe aller Elemente in der Liste berechnet und zurückgegeben.
• case x :: y :: _: Ein zusätzlicher Fall, um die Summe der ersten zwei Elemente für alle Listen mit mindestens zwei Elementen sicherzustellen.
• case _: Wenn die Liste weniger als zwei Elemente hat, wird 0 zurückgegeben.

c)

Nehmen wir an, Du hast eine komplexere Datenstruktur wie die folgende:

sealed trait Treecase class Node(value: Int, left: Tree, right: Tree) extends Treecase object Leaf extends Tree

Implementiere eine Funktion sumTree, die den Wert aller Knoten in einem solchen Baum summiert. Benutze dabei Musterabgleich.

fun sumTree(tree: Tree): Int = tree match {  // Dein Code hier}

Lösung:

Hier ist die Lösung für das Teilproblem:Um die Summe aller Knotenwerte in einem Baum einer komplexeren Datenstruktur zu berechnen, können wir Musterabgleich verwenden. Hier ist der passende Scala-Code dazu:Zuerst definieren wir die Datenstruktur:

sealed trait Tree case class Node(value: Int, left: Tree, right: Tree) extends Tree case object Leaf extends Tree

Nun implementieren wir die Funktion sumTree:

fun sumTree(tree: Tree): Int = tree match {   case Leaf => 0   case Node(value, left, right) => value + sumTree(left) + sumTree(right) }

• case Leaf: Wenn der Baum ein Blatt ist, gibt die Funktion 0 zurück, da es keine Werte gibt, die summiert werden könnten.
• case Node(value, left, right): Wenn der Baum ein Knoten ist, summiert die Funktion den Wert des Knotens mit der rekursiven Summe der linken und rechten Teilbäume.

Dieser Code stellt sicher, dass alle Knotenwerte im Baum rekursiv summiert werden.