Programowanie funkcyjne/Model obliczeń/Ćwiczenia: Różnice pomiędzy wersjami

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania
← poprzednia edycja
WizualnieWikikod
Kubica (dyskusja | edycje)
630 edycji
m Zastępowanie tekstu – „<math> ” na „<math>”
 
(Nie pokazano 9 wersji utworzonych przez 4 użytkowników)
Linia 1: Linia 1:
==Ćwiczenia==
== Praca domowa ==
*Porównaj <tt>foldr</tt> i <tt>foldl</tt>. Która z nich jest ogonowa?
* Porównaj <tt>foldr</tt> i <tt>foldl</tt>. Która z nich jest ogonowa?
*Potęgowanie liczb - liniowe i logarytmiczne, ogonowe.  
* Zaimplementuj potęgowanie liczb -- ogonowo, raz o złożoności liniowej, a raz o złożoności logarytmicznej.  
*Rozważ standardowe procedury przetwarzania list: <tt>length</tt>, <tt>map</tt>, <tt>append</tt>,<tt>rev</tt>. Czy w ich przypadku definicja ogonowa zmniejsza złożoność pamięciową?
 
*Potęgowanie funkcji - najpierw liniowe, potem logarytmiczne, ale obie wersje z rekurencją ogonową. Rozrysować w jaki sposób oblicza się:
== Ćwiczenia ==
{{cwiczenie|[Złożoność rekurencji ogonowej]||
Rozważ standardowe procedury przetwarzania list: <tt>length</tt>, <tt>map</tt>, <tt>append</tt>,<tt>rev</tt>.  
Czy w ich przypadku definicja ogonowa zmniejsza złożoność pamięciową?
}}
 
{{cwiczenie|[Potęgowanie funkcji]||
Potęgowanie funkcji -- najpierw liniowe, potem logarytmiczne, ale obie wersje z rekurencją ogonową.  
Rozrysuj w jaki sposób oblicza się:}}
            
            
  iterate 2 ('''function''' x -> x * (x+1)) 2
  iterate 2 ('''function''' x -> x * (x+1)) 2
  iterate 3 ('''function''' x -> x * (x+1)) 1
  iterate 3 ('''function''' x -> x * (x+1)) 1
         
(w zależności od wersji, cierpliwości i powierzchni tablic :-). W przypadku wersji logarytmicznej, procedura wynikowa jest
obliczana w czasie logarytmicznym, ale ona sama działa w czasie liniowym.


==Laboratorium==
(w zależności od wersji, cierpliwości i powierzchni tablic :-).
* Napisz procedurę <tt>sześciany : int -> int list</tt> taką, że wynikiem <tt>sześciany n</tt> jest lista postaci <math> [1^3; 2^3; \dots; n^3]</math>. Rozwiązując to zadanie:
W przypadku wersji logarytmicznej, procedura wynikowa jest
** możesz korzystać wyłącznie z rekurencji ogonowej,
obliczana w czasie logarytmicznym, ale ona sama działa w czasie liniowym.
** jedyne operacje na liczbach, z jakich możesz korzystać to: <tt>+</tt>, <tt>-</tt> oraz porównywanie.  
 
* Napisz procedurę <tt>podziel : int list -> int list list</tt>, która dla danej listy <math>[a_1; a_2; \dots; a_n]</math> zawierającej permutację zbioru <math>\{1, 2, \dots, n\}</math> znajdziejej podział na jak najliczniejszą listę list postaci:  
== Laboratorium ==
<center><math> [[a_1; a_2; \dots; a_{k_1}]; [a_{{k_1}+1}; a_{{k_1}+2}; \dots; a_{k_2}]; \dots; [a_{{k_{m-1}}+1}; a_{{k_{m-1}}+2}; \dots; a_{k_m}]] </math>,</center><br/>  
{{cwiczenie|[Sześciany]||
:taką, że:<br/>
Napisz procedurę <tt>sześciany : int -> int list</tt> taką, że wynikiem <tt>sześciany n</tt> jest lista postaci <math>[1^3; 2^3; \dots; n^3]</math>.  
Rozwiązując to zadanie:
* możesz korzystać wyłącznie z rekurencji ogonowej,
* jedyne operacje na liczbach, z jakich możesz korzystać to: <tt>+</tt>, <tt>-</tt> oraz porównywanie
* skorzystaj z tożsamości:
** <math>(n+1)^3 = n^3 + 3n^2 + 3n +1</math>,
** <math>(n+1)^2 = n^2 + 2n + 1</math>.
Twoje rozwiązanie powinno działać w czasie <math>\Theta(n)</math>.
}}
 
{{cwiczenie|[Podział permutacji]||
Napisz procedurę <tt>podziel : int list -> int list list</tt>,  
która dla danej listy <math>[a_1; a_2; \dots; a_n]</math> zawierającej permutację zbioru  
<math>\{1, 2, \dots, n\}</math> znajdzie jej podział na jak najliczniejszą listę list postaci:  
<center><math>[[a_1; a_2; \dots; a_{k_1}]; [a_{{k_1}+1}; a_{{k_1}+2}; \dots; a_{k_2}]; \dots; [a_{{k_{m-1}}+1}; a_{{k_{m-1}}+2}; \dots; a_{k_m}]]</math>,</center><br/>  
taką, że:<br/>
<center><math>\begin{matrix}
<center><math>\begin{matrix}
\{a_1, a_2, \dots, a_{k_1}\} & = &\{1, 2, \dots, k_1\} \quad\mbox{(równość zbiorów)}, \\
\{a_1, a_2, \dots, a_{k_1}\} & = &\{1, 2, \dots, k_1\} & \mbox{(równość zbiorów)}, \\
\{a_{{k_1}+1}, a_{{k_1}+2}, \dots, a_{k_2}\} &  = &\{k_1+1, k_1+2, \dots, k_2\},\\  
\{a_{{k_1}+1}, a_{{k_1}+2}, \dots, a_{k_2}\} &  = &\{k_1+1, k_1+2, \dots, k_2\},\\  
& \vdots & \\  
& \vdots & \\  
Linia 25: Linia 45:
\end{matrix}</math></center>
\end{matrix}</math></center>
<br/>
<br/>
:Przyjmujemy, że wynikiem dla listy pustej jest lista pusta.  
Przyjmujemy, że wynikiem dla listy pustej jest lista pusta.  
:Przykład: <math> \texttt{\mbox{podziel}} [2; 3; 1; 6; 5; 4; 7; 9; 10; 11; 8] = [[2; 3; 1]; [6; 5; 4]; [7]; [9; 10; 11; 8]]</math>.
 
:Rozwiązując to zadanie powinieneś skorzystać z rekurencji, ale wolno Ci korzystać wyłącznie z rekurencji ogonowej.
Przykład:  
<math>\texttt{\mbox{podziel}} [2; 3; 1; 6; 5; 4; 7; 9; 10; 11; 8] = [[2; 3; 1]; [6; 5; 4]; [7]; [9; 10; 11; 8]]</math>,
<math>\texttt{\mbox{podziel}} [3;4;1;2] = [[3;4;1;2]]</math>.
 
Rozwiązując to zadanie powinieneś skorzystać z rekurencji, ale wolno Ci korzystać wyłącznie z rekurencji ogonowej.
}}

Aktualna wersja na dzień 22:17, 11 wrz 2023

Praca domowa

  • Porównaj foldr i foldl. Która z nich jest ogonowa?
  • Zaimplementuj potęgowanie liczb -- ogonowo, raz o złożoności liniowej, a raz o złożoności logarytmicznej.

Ćwiczenia

Ćwiczenie [Złożoność rekurencji ogonowej]

Rozważ standardowe procedury przetwarzania list: length, map, append,rev. Czy w ich przypadku definicja ogonowa zmniejsza złożoność pamięciową?

Ćwiczenie [Potęgowanie funkcji]

Potęgowanie funkcji -- najpierw liniowe, potem logarytmiczne, ale obie wersje z rekurencją ogonową.

Rozrysuj w jaki sposób oblicza się:
iterate 2 (function x -> x * (x+1)) 2
iterate 3 (function x -> x * (x+1)) 1

(w zależności od wersji, cierpliwości i powierzchni tablic :-). W przypadku wersji logarytmicznej, procedura wynikowa jest obliczana w czasie logarytmicznym, ale ona sama działa w czasie liniowym.

Laboratorium

Ćwiczenie [Sześciany]

Napisz procedurę sześciany : int -> int list taką, że wynikiem sześciany n jest lista postaci [13;23;…;n3]. Rozwiązując to zadanie:

  • możesz korzystać wyłącznie z rekurencji ogonowej,
  • jedyne operacje na liczbach, z jakich możesz korzystać to: +, - oraz porównywanie
  • skorzystaj z tożsamości:
    • (n+1)3=n3+3n2+3n+1,
    • (n+1)2=n2+2n+1.

Twoje rozwiązanie powinno działać w czasie Θ(n).

Ćwiczenie [Podział permutacji]

Napisz procedurę podziel : int list -> int list list, która dla danej listy [a1;a2;…;an] zawierającej permutację zbioru {1,2,…,n} znajdzie jej podział na jak najliczniejszą listę list postaci:

[[a1;a2;…;ak1];[ak1+1;ak1+2;…;ak2];…;[akm−1+1;akm−1+2;…;akm]],

taką, że:

{a1,a2,…,ak1}={1,2,…,k1}(równość zbiorów),{ak1+1,ak1+2,…,ak2}={k1+1,k1+2,…,k2},⋮{akm−1+1,akm−1+2,…,akm}={km−1+1,km−1+2,…,km}


Przyjmujemy, że wynikiem dla listy pustej jest lista pusta.

Przykład: podziel[2;3;1;6;5;4;7;9;10;11;8]=[[2;3;1];[6;5;4];[7];[9;10;11;8]], podziel[3;4;1;2]=[[3;4;1;2]].

Rozwiązując to zadanie powinieneś skorzystać z rekurencji, ale wolno Ci korzystać wyłącznie z rekurencji ogonowej.

Źródło: „https://wazniak.mimuw.edu.pl/index.php?title=Programowanie_funkcyjne/Model_obliczeń/Ćwiczenia&oldid=82614”