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

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania
← poprzednia edycjanastępna edycja →
WizualnieWikikod
Kubica (dyskusja | edycje)
630 edycji
Nie podano opisu zmian
Kubica (dyskusja | edycje)
630 edycji
Nie podano opisu zmian
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==


* Dane są: definicja typu <tt>tree</tt> i procedura <tt>fold_tree</tt>:
'''type''' tree = Node '''of''' tree * int * tree | Leaf;;
'''let''' '''rec''' fold_tree f a t =
&nbsp;&nbsp;'''match''' t '''with'''
&nbsp;&nbsp;Leaf -> a |
&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>.
==Laboratorium==


* 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>).  
* 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>).  
* 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>?
* 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>?
* 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).

Wersja z 18:10, 27 sie 2006

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

  • 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ę odwrotność, której wynikiem dla parametru f będzie przybliżenie f−1 z dokładnością zadaną przez stałą epsilon (czyli jeśli g=(odwrotnoscf), to ∀x |g(x)−f−1(x)|≤epsilon).
  • 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. Uwaga: ile razy należy stosować tłumienie w zależności od n?
Źródło: „https://wazniak.mimuw.edu.pl/index.php?title=Programowanie_funkcyjne/Procedury_wyższych_rzędów/Ćwiczenia&oldid=29907”