Programowanie funkcyjne/Procedury wyższych rzędów/Ćwiczenia: Różnice pomiędzy wersjami

Aktualna wersja na dzień 13:58, 1 cze 2020

Praca domowa

Wygładzenie funkcji z odstępem $d x$ polega na uśrednieniu $f (x - d x)$ , $f (x)$ i $f (x + d x)$ . 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 $ε$ , że jeżeli wynik $x$ spełnia $| f x | \leq ε$ , to jest dobrym przybliżeniem zera.

Laboratorium

Ćwiczenie [Odwrotność funkcji]

Niech $f : ℛ \to ℛ$ będzie funkcją 1-1 i "na" oraz taką, że $f (0) = 0$ , $f$ jest rosnąca i $| f (x) | \geq | 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) | \leq e p s i l o n$ ).

Ć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.;;

@@ Linia 1: / Linia 1: @@
+==Praca domowa==
+* Wygładzenie funkcji z odstępem <math>dx</math> polega na uśrednieniu <math>f(x - dx)</math>, <math>f(x)</math> i <math>f(x + dx)</math>. Napisz procedurę wygładzającą daną funkcję z zadanym odstępem.
+* Jaki typ ma procedura <tt>compose</tt> zastosowana w wyrażeniu:
+ compose twice twice;;
 ==Ćwiczenia==
+{{cwiczenie|[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ść.
+}}
-* Dane są: definicja typu <tt>tree</tt> i procedura <tt>fold_tree</tt>:
+{{cwiczenie|[Przybliżanie zer przez bisekcję]||
+Zaimplementuj przybliżanie zer funkcji przez bisekcję.
+Parametrami powinny być:
+* funkcja <math>f</math>, której zer szukamy,
+* dwa punkty, w których funkcja przyjmuje wartości przeciwnych znaków,
+* precyzja poszukiwać, tzn. taki <math>\varepsilon</math>, że jeżeli wynik <math>x</math> spełnia <math>|f\ x| \le \varepsilon</math>, to jest dobrym przybliżeniem zera.
+}}
- '''type''' tree = Node '''of''' tree * int * tree | Leaf;;
+== Laboratorium ==
- '''let''' '''rec''' fold_tree f a t =
+{{cwiczenie|[Odwrotność funkcji]||}}
- &nbsp;&nbsp;'''match''' t '''with'''
+Niech <math>f : \mathcal{R} \to \mathcal{R}</math> będzie funkcją 1-1 i "na" oraz taką, że <math>f(0) = 0</math>,
- &nbsp;&nbsp;Leaf -> a |
+<math>f</math> jest rosnąca i <math>|f(x)| \ge |x|</math>. Zaimplementuj procedurę <tt>odwrotnosc</tt>,
- &nbsp;&nbsp;Node (l, x, r) -> f x (fold_tree f a l) (fold_tree f a r);;
+której wynikiem dla parametru <math>f</math> będzie przybliżenie <math>f^{-1}</math> z dokładnością zadaną przez stałą <tt>epsilon</tt>
+(czyli jeśli <tt>g = odwrotnosc f</tt>, to <math>\forall x\ |g(x) - f^{-1}(x)| \le epsilon</math>).
-Powiemy, że liczba w węźle drzewa jest ''widoczna'', jeżeli na ścieżce od tego węzła do korzenia drzewa nie ma większej liczby. W szczególności liczba w korzeniu drzewa jest zawsze widoczna, a liczby mniejsze od niej nie są nigdy widoczne.
-* Napisz procedurę <tt>widoczne:drzewo <math>\to</math> int</tt>, która dla zadanego drzewa (zawierającego wyłącznie liczby nieujemne) obliczy liczbę widocznych liczb. Rozwiązując to zadanie nie wolno Ci tworzyć żadnych definicji rekurencyjnych. Powinieneś natomiast skorzystać z procedury <tt>fold_tree</tt>.
-==Laboratorium==
+{{cwiczenie|[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 <math>y \to \frac{x}{y^{n-1}}</math> jest <math>\sqrt[n]{x}</math>.
+Zaimplementuj obliczanie <math>n</math>-tego pierwiastka z <math>x</math> za pomocą obliczania punktu stałego i
+tłumienia przez uśrednianie z odpowiednimi wagami.
+Uwaga: W jaki sposób wagi zależą od <math>n</math>?
+}}
-* Niech <math>f : \mathcal{R} \to \mathcal{R}</math> będzie funkcją 1-1 i "na" oraz taką, że <math>f(0) = 0</math>, <math>f</math> jest rosnąca i <math>|f(x)| \ge |x|</math>. Zaimplementuj procedurę <tt>odwrotność</tt>, której wynikiem dla parametru <math>f</math> będzie przybliżenie <math>f^{-1}</math> z dokładnością zadaną przez stałą <tt>epsilon</tt> (czyli jeśli <math>g = (\texttt{odwrotnosc} f)</math>, to <math>\forall x\ |g(x) - f^{-1}(x)| \le epsilon</math>).
+<div class="mw-collapsible mw-made=collapsible mw-collapsed">
-* Wygładzenie funkcji z odstępem <math>dx</math> polega na uśrednieniu <math>f(x - dx)</math>, <math>f(x)</math> i <math>f(x + dx)</math>. Napisz procedurę wygładzającą daną funkcję z zadanym odstępem.
+<span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Rozwiązanie</span>
-* Punktem stałym funkcji <math>y \to \frac{x}{y^{n-1}}</math> jest <math>\sqrt[n]{x}</math>. Zaimplementuj obliczanie <math>n</math>-tego pierwiastka z <math>x</math> za pomocą obliczania punktu stałego i tłumienia przez uśrednianie. Uwaga: ile razy należy stosować tłumienie w zależności od <math>n</math>?
+<div class="mw-collapsible-content" style="display:none">
+Uśrednienie funkcji <math>f</math> z wagą <math>a</math> 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 <math>y \to \frac{x}{y^{n-1}}</math> było zbieżne do jego punktu stałego, musimy je uśrednić ze współczynnikiem mniejszym od <math>\frac{2}{n}</math>, np. <math>\frac{2}{n+1}</math>.
-* Napisz odpowiedniki <tt>map</tt> i <tt>filter</tt> dla drzew. Rozważ drzewa binarne i drzewa o wierzchołkach dowolnego skończonego stopnia (por. ćw. do poprzedniego wykładu).
+  '''let''' root n x =
+    punkt_staly (usrednij (2. /. float(n+1)) (fun y -> x /. potega y (n-1))) 1.;;
+</div></div>

Programowanie funkcyjne/Procedury wyższych rzędów/Ćwiczenia: Różnice pomiędzy wersjami

Aktualna wersja na dzień 13:58, 1 cze 2020

Praca domowa

Ćwiczenia

Laboratorium

Menu nawigacyjne

Działania na stronie

Opcje strony

Narzędzia osobiste

Nawigacja

Szukaj

Narzędzia