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>.
-* Zapisz procedurę <tt>append</tt> za pomocą <tt>foldr/foldl</tt>.
-* Za pomocą <tt>foldl</tt> zapisz procedurę <tt>rev</tt>.
-* suma listy funkcji,
-* złożenie listy funkcji,
-* 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.
-* Za pomocą <tt>filter</tt> zaimplementuj procedurę <tt>not_divisivble</tt>, która pozostawia na liście wszystkie elementy niepodzielne przez zadaną liczbę.
-* 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;;
+{{cwiczenie|[Pierwiastkowanie jako punkt stały [AS] ]||
- '''let''' '''rec''' fold_tree f a t =
+Przedstawione w wykładzie tłumienie przez uśrednianie opiera się na średniej arytmetycznej.
- &nbsp;&nbsp;'''match''' t '''with'''
+Czasami zamiast średniej arytmetycznej należy użyć średniej ważonej, z odpowiednio dobraną wagą.
- &nbsp;&nbsp;Leaf -> a |
+Punktem stałym funkcji <math>y \to \frac{x}{y^{n-1}}</math> jest <math>\sqrt[n]{x}</math>.
- &nbsp;&nbsp;Node (l, x, r) -> f x (fold_tree f a l) (fold_tree f a r);;
+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.
-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.
+Uwaga: W jaki sposób wagi zależą od <math>n</math>?
+}}
-* 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>.
+<div class="mw-collapsible mw-made=collapsible mw-collapsed">
+<span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Rozwiązanie</span>
+<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:
-==Laboratorium==
+  '''let''' usrednij a f x = a *. (f x) +. (1. -. a) *. x;;
+  ''val usrednij : float -> (float -> float) -> float -> float = <fun>''
-* Korzystając z <tt>filter</tt> zaimplementuj Quick-sort.
+Ż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>.
-* 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{odwrotność} f)</math>, to <math>\forall x\ |g(x) - f^{-1}(x)| \le <tt>epsilon</tt></math>). 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.  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.
- kompresuj [1; 2; 2; 5; 11; 11; 2];;
+  '''let''' root n x =
- ''- : int list = [1; 6; 9; 42; 3]''*;\end{flushleft}
+    punkt_staly (usrednij (2. /. float(n+1)) (fun y -> x /. potega y (n-1))) 1.;;
+</div></div>
-* 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).

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