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

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania
← poprzednia edycja
WizualnieWikikod
Przemek (dyskusja | edycje)
799 edycji
 
(Nie pokazano 18 wersji utworzonych przez jednego użytkownika)
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==
==Ć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ść.
}}


* Zapisz procedurę <tt>length</tt> za pomocą <tt>foldr</tt>.
{{cwiczenie|[Przybliżanie zer przez bisekcję]||
* Zapisz procedurę <tt>append</tt> za pomocą <tt>foldr/foldl</tt>.
Zaimplementuj przybliżanie zer funkcji przez bisekcję.  
* Za pomocą <tt>foldl</tt> zapisz procedurę <tt>rev</tt>.
Parametrami powinny być:
* suma listy funkcji,
* funkcja <math>f</math>, której zer szukamy,  
* złożenie listy funkcji,  
* dwa punkty, w których funkcja przyjmuje wartości przeciwnych znaków,  
* 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.
* 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.
* 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;;
== 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>?
}}


* Korzystając z <tt>filter</tt> zaimplementuj Quick-sort.
<div class="mw-collapsible mw-made=collapsible mw-collapsed">
* 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>).  
<span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Rozwiązanie</span>
* 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 class="mw-collapsible-content" style="display:none">
* 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>?
Uśrednienie funkcji <math>f</math> z wagą <math>a</math> możemy zdefiniować następująco:
* 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.
 
  '''let''' usrednij a f x = a *. (f x) +. (1. -. a) *. x;;
  ''val usrednij : float -> (float -> float) -> float -> float = <fun>''


kompresuj [1; 2; 2; 5; 11; 11; 2];;
Ż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>.
''- : int list = [1; 6; 9; 42; 3]''


* 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>

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

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 ε, że jeżeli wynik x spełnia |f x|≤ε, to jest dobrym przybliżeniem zera.

Laboratorium

Ćwiczenie [Odwrotność funkcji]

Niech f:ℛ→ℛ będzie funkcją 1-1 i "na" oraz taką, że f(0)=0, f jest rosnąca i |f(x)|≥|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 ∀x |g(x)−f−1(x)|≤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→xyn−1 jest xn. 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

Źródło: „https://wazniak.mimuw.edu.pl/index.php?title=Programowanie_funkcyjne/Procedury_wyższych_rzędów/Ćwiczenia&oldid=76435”