Programowanie funkcyjne/Procedury wyższych rzędów/Ćwiczenia

From Studia Informatyczne

Praca domowa

  • Wygładzenie funkcji z odstępem dx polega na uśrednieniu f(x - dx), f(x) i f(x + dx). Napisz procedurę wygładzającą daną funkcję z zadanym odstępem.
  • Jaki typ ma procedura compose zastosowana w wyrażeniu:
compose twice twice;;

Ćwiczenia

Ćwiczenie [Semantyka wyrażeń]

Przypomnij sobie zadanie dotyczące wyliczania wartości wyrażeń. Rozszerz składnię wyrażeń o zmienne. Procedura obliczająca wartość wyrażenia będzie wymagać dodatkowego parametru -- wartościowania zmiennych, czyli procedury, która nazwie zmiennej przyporządkowuje jej wartość.

Ćwiczenie [Przybliżanie zer przez bisekcję]

Zaimplementuj przybliżanie zer funkcji przez bisekcję. Parametrami powinny być:

  • funkcja f, której zer szukamy,
  • dwa punkty, w których funkcja przyjmuje wartości przeciwnych znaków,
  • precyzja poszukiwać, tzn. taki \varepsilon, że jeżeli wynik x spełnia |f\ x| \le \varepsilon, to jest dobrym przybliżeniem zera.

Laboratorium

Ćwiczenie [Odwrotność funkcji]

Niech f : \mathcal{R} \to \mathcal{R} będzie funkcją 1-1 i "na" oraz taką, że f(0) = 0, f jest rosnąca i |f(x)| \ge |x|. Zaimplementuj procedurę odwrotnosc, której wynikiem dla parametru f będzie przybliżenie f^{-1} z dokładnością zadaną przez stałą epsilon (czyli jeśli g = odwrotnosc f, to \forall x\ |g(x) - f^{-1}(x)| \le epsilon).


Ćwiczenie [Pierwiastkowanie jako punkt stały [AS] ]

Przedstawione w wykładzie tłumienie przez uśrednianie opiera się na średniej arytmetycznej. Czasami zamiast średniej arytmetycznej należy użyć średniej ważonej, z odpowiednio dobraną wagą. Punktem stałym funkcji y \to \frac{x}{y^{n-1}} jest \sqrt[n]{x}. Zaimplementuj obliczanie n-tego pierwiastka z x za pomocą obliczania punktu stałego i tłumienia przez uśrednianie z odpowiednimi wagami. Uwaga: W jaki sposób wagi zależą od n?

Rozwiązanie

Uśrednienie funkcji f z wagą a możemy zdefiniować następująco:

 let usrednij a f x = a *. (f x) +. (1. -. a) *. x;;
 val usrednij : float -> (float -> float) -> float -> float = <fun>

Żeby iterowanie przekształcenia y \to \frac{x}{y^{n-1}} było zbieżne do jego punktu stałego, musimy je uśrednić ze współczynnikiem mniejszym od \frac{2}{n}, np. \frac{2}{n+1}.

 let root n x = 
   punkt_staly (usrednij (2. /. float(n+1)) (fun y -> x /. potega y (n-1))) 1.;;