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ść.
+}}
+{{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.
+}}
+== Laboratorium ==
+{{cwiczenie|[Odwrotność funkcji]||}}
+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>odwrotnosc</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 <tt>g = odwrotnosc f</tt>, to <math>\forall x\ |g(x) - f^{-1}(x)| \le epsilon</math>).
-* Zapisz procedurę <tt>length</tt> za pomocą <tt>foldr</tt>.
+{{cwiczenie|[Pierwiastkowanie jako punkt stały [AS] ]||
-* Zapisz procedurę <tt>append</tt> za pomocą <tt>foldr/foldl</tt>.
+Przedstawione w wykładzie tłumienie przez uśrednianie opiera się na średniej arytmetycznej.
-* Za pomocą <tt>foldl</tt> zapisz procedurę <tt>rev</tt>.
+Czasami zamiast średniej arytmetycznej należy użyć średniej ważonej, z odpowiednio dobraną wagą.
-* suma listy funkcji,
+Punktem stałym funkcji <math>y \to \frac{x}{y^{n-1}}</math> jest <math>\sqrt[n]{x}</math>.
-* złożenie listy funkcji,
+Zaimplementuj obliczanie <math>n</math>-tego pierwiastka z <math>x</math> za pomocą obliczania punktu stałego i
-* Za pomocą <tt>map</tt> zapisz procedurę <tt>heads</tt>, której wynikiem dla danej listy list, jest lista pierwszych elementów list składowych.
+tłumienia przez uśrednianie z odpowiednimi wagami.
-* Za pomocą <tt>filter</tt> zaimplementuj procedurę <tt>not_divisivble</tt>, która pozostawia na liście wszystkie elementy niepodzielne przez zadaną liczbę.
+Uwaga: W jaki sposób wagi zależą od <math>n</math>?
-* Wykorzystaj rozwiązanie poprzedniego zadania do zaimplementowania sita Eratostenesa.
+}}
-* Za pomocą <tt>foldr</tt> zapisz <tt>flatten</tt>. (<tt>let flatten l = foldr (@) l [];;</tt>)
-* Za pomocą <tt>foldl</tt> zapisz procedurę <tt>foldr</tt>.
-* Dane są: definicja typu <tt>tree</tt> i procedura <tt>fold_tree</tt>:
- '''type''' tree = Node '''of''' tree * int * tree | Leaf;;
+<div class="mw-collapsible mw-made=collapsible mw-collapsed">
- '''let''' '''rec''' fold_tree f a t =
+<span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Rozwiązanie</span>
- &nbsp;&nbsp;'''match''' t '''with'''
+<div class="mw-collapsible-content" style="display:none">
- &nbsp;&nbsp;Leaf -> a |
+Uśrednienie funkcji <math>f</math> z wagą <math>a</math> możemy zdefiniować następująco:
- &nbsp;&nbsp;Node (l, x, r) -> f x (fold_tree f a l) (fold_tree f a r);;
-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>.
+  '''let''' usrednij a f x = a *. (f x) +. (1. -. a) *. x;;
+  ''val usrednij : float -> (float -> float) -> float -> float = <fun>''
-==Laboratorium==
+Ż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>.
-* Korzystając z <tt>filter</tt> zaimplementuj Quick-sort.
+  '''let''' root n x =
-* Niech <math>f : {\cal R} \to {\cal 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 = (<tt>odwrotność </tt> f)</math>, to <math>\forall x\ |g(x) - f^{-1}(x)| \le <tt>epsilon</tt></math>).
+    punkt_staly (usrednij (2. /. float(n+1)) (fun y -> x /. potega y (n-1))) 1.;;
-* 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.
+</div></div>
-* 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>?
-* Rozważmy następującą metodę kompresji ciągów liczb całkowitych:
-*;Jeżeli w oryginalnym ciągu ta sama liczba powtarza się kilka
-*;razy z rzędu, to jej kolejne wystąpienia reprezentujemy za
-*;pomocą jednej tylko liczby.
-*;Konkretnie, <math>i</math> powtórzeń liczby <math>k</math> reprezentujemy w ciągu
-*;skompresowanym jako <math>2^{i-1} \cdot (2 \cdot k - 1)</math>.
-*;
-*;Napisz procedury: kompresującą i dekompresującą
-*;zadaną listę.
-*;Lista skompresowana powinna być oczywiście jak najkrótsza.
-*;Przy dekompresji możesz założyć, że lista skompresowana
-*;nie zawiera zer.
-*;
-*;Rozwiązując to zadanie, zamiast rekurencji, należy użyć
-*;standardowych procedur wyższych rzędów przetwarzających
-*;listy.
-*;
-*;\begin{flushleft} \tt
-*;kompresuj [1; 2; 2; 5; 11; 11; 2];;
-*;''- : int list = [1; 6; 9; 42; 3]''*;\end{flushleft}
-**;Napisz odpowiedniki \codeline{map} i <tt>filter</tt> dla drzew.*;Rozważ drzewa binarne i drzewa o wierzchołkach dowolnego
-*;skończonego stopnia (por.\ ćw.\ do poprzedniego wykładu).

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