Kolejne wpisy dopiero po Świętach – zatem już dziś Wszystkim życzę wesołych Świąt! W ramach cyklu „Matematyka w obrazkach” przygotowałem fraktalną kartkę świąteczną – Choinkę Sierpińskiego – na którą składają się:

  1. Trójkąt Sierpińskiego
  2. Dywan Sierpińskiego
  3. Płatki śniegu Kocha (gwiazda, śnieg, zaspy)
  4. Zbiory Julii (niebo)
  5. Ozdoby – inny wariant dywanu Sierpińskiego

🙂

Choinka Sierpińskiego

Matematyka w obrazkach - Choinka Sierpińskiego

Pozdrowienia,

Mariusz Gromada

Poza Liczbami: Inne Twórcze Przestrzenie

Matematyka i muzyka są ściśle powiązane przez rytm, harmonię i struktury

Matematyka i muzyka są ściśle powiązane przez rytm, harmonię i struktury, które wykorzystują matematyczne wzory i proporcje do tworzenia estetycznych i emocjonalnych doznań. Z nieśmiałą ekscytacją przedstawiam moją pierwszą poważniejszą kompozycję, w której starałem się uchwycić te połączenia.

I Am Here – RELEARN – Mariusz Gromada (2024)
I Am Here – RELEARN – Mariusz Gromada (2024)
Deep Under – RELEARN – Mariusz Gromada (2024)
Deep Under – RELEARN – Mariusz Gromada (2024)

Scalar – zaawansowana aplikacja mobilna z silnikiem matematycznym mojego autorstwa

Przekształcenie stereograficzne (rzut stereograficzny) okręgu na prostą oraz sfery na płaszczyznę – czyli równoliczność odcinka / okręgu z całą prostą oraz sfery z płaszczyzną.

Rzut stereograficzny okręgu na prostą

Rzut stereograficzny okręgu na prostą

Rzut stereograficzny sfery na płaszczyznę

Rzut stereograficzny sfery na płaszczyznę

Pozdrowienia,

Mariusz Gromada

Poza Liczbami: Inne Twórcze Przestrzenie

Matematyka i muzyka są ściśle powiązane przez rytm, harmonię i struktury

Matematyka i muzyka są ściśle powiązane przez rytm, harmonię i struktury, które wykorzystują matematyczne wzory i proporcje do tworzenia estetycznych i emocjonalnych doznań. Z nieśmiałą ekscytacją przedstawiam moją pierwszą poważniejszą kompozycję, w której starałem się uchwycić te połączenia.

I Am Here – RELEARN – Mariusz Gromada (2024)
I Am Here – RELEARN – Mariusz Gromada (2024)
Deep Under – RELEARN – Mariusz Gromada (2024)
Deep Under – RELEARN – Mariusz Gromada (2024)

Scalar – zaawansowana aplikacja mobilna z silnikiem matematycznym mojego autorstwa

Geometryczny dowód twierdzenia Pitagorasa – sam obrazek nie stanowi formalnego dowodu, ale co tam 🙂 .

Matematyka w obrazkach - Twierdzenie Pitagorasa

Pozdrowienia,

Mariusz Gromada

Poza Liczbami: Inne Twórcze Przestrzenie

Matematyka i muzyka są ściśle powiązane przez rytm, harmonię i struktury

Matematyka i muzyka są ściśle powiązane przez rytm, harmonię i struktury, które wykorzystują matematyczne wzory i proporcje do tworzenia estetycznych i emocjonalnych doznań. Z nieśmiałą ekscytacją przedstawiam moją pierwszą poważniejszą kompozycję, w której starałem się uchwycić te połączenia.

I Am Here – RELEARN – Mariusz Gromada (2024)
I Am Here – RELEARN – Mariusz Gromada (2024)
Deep Under – RELEARN – Mariusz Gromada (2024)
Deep Under – RELEARN – Mariusz Gromada (2024)

Scalar – zaawansowana aplikacja mobilna z silnikiem matematycznym mojego autorstwa

W pierwszych trzech częściach „Zabaw z rekurencją” skupialiśmy się na rekurencji bezpośredniej, tzn. na sytuacji, kiedy w ciele funkcji dochodzi do wywołania „siebie samej”. Przebieg rekurencji bezpośredniej jest dość oczywisty, struktura wywołania, argumenty, jak też warunek stopu, są takie same dla wszystkich odwołań.

Rekurencja pośrednia

O rekurencji pośredniej mówimy w sytuacji „łańcucha wywołań”. Przykładowo funkcja f(.) wywołuje funkcję g(.), następnie funkcja g(.) wywołuje f(.), zatem ponowne wywołanie funkcji f(.) realizowane jest bezpośrednio przez funkcję g(.), jednak pośrednio przez f(.), gdyż to f(.) wywołała g(.).

Typy rekurencji

Długość łańcucha nie musi być ograniczona, w rzeczywistości wywołania pośrednie mogą mieć nietrywialną strukturę, mogą „cofać się” do poprzednich elementów, „iść na skróty”, „rozdzielać się”, a w szczególności może dochodzić do wariantów mieszanych – tzn. wywołań bezpośrednich i pośrednich (różnego typu) w ramach jednej procedury. Dobrze to obrazuje poniższy schemat.

Rekurencja pośrednia

Aproksymacja funkcji sin(x) oraz cos(x) przy wykorzystaniu połączenia rekurencji bezpośredniej i rekurencji pośredniej

Przypomnijmy podstawowe tożsamości trygonometryczne dla wielokrotności kątów.

$$\sin(2x)=2\sin(x)\cos(x)$$

$$\cos(2x)=\cos^2(x)-\sin^2(x)$$

Równoważnie powyższe można zapisać jako

$$\sin(x)=2\sin\big(\frac{x}{2}\big)\cos\big(\frac{x}{2}\big)$$

$$\cos(x)=\cos^2\big(\frac{x}{2}\big)-\sin^2\big(\frac{x}{2}\big)$$

Zwróćmy uwagę, że znając rozwiązanie dla argumentu mniejszego $\frac{x}{2}$ możemy podać rozwiązanie dla $x$ – zatem tożsamości trygonometryczne są w istocie rekurencją z odwołaniami bezpośrednimi i pośrednimi! Funkcję $\sin(x)$ w otoczeniu $0$ można przybliżyć przez $x$, natomiast funkcję $\cos(x)$ przez stałą wartość $1$. Im mniejsze otoczenie $0$ wybierzemy tym lepsza aproksymacja w zadanym przedziale, a w konsekwencji mniejszy błąd oszacowania w całości. Przyjęte wartości w otoczeniu $0$ dają również pewny warunek stopu! Mamy więc wszystko co niezbędne do zastosowania strategii rekurencyjnej w aproksymacji.

Ustalmy stałą $a>0$ (reprezentującą otoczenie $0$), następnie definiujemy dwie funkcje rekurencyjne

$$\text{s}(x)=\begin{cases}x&\text{dla}\quad |x|<a\\2\text{s}\big(\frac{x}{2}\big)\text{c}\big(\frac{x}{2}\big)&\text{dla}\quad |x|\geq a\end{cases}$$

$$\text{c}(x)=\begin{cases}1&\text{dla}\quad |x|<a\\\text{c}^2\big(\frac{x}{2}\big)-\text{s}^2\big(\frac{x}{2}\big)&\text{dla}\quad |x|\geq a\end{cases}$$

Podkreślmy ponownie, że funkcja $\text{s}(x)$ wywołuje siebie bezpośrednio oraz wskazuje na funkcję $\text{c}(x)$, która, oprócz bezpośredniego wywołania siebie samej, wskazuje ponownie na $\text{s}(x)$. Jest to zatem ciekawa kombinacja rekurencji bezpośredniej z rekurencją pośrednią. Zapiszmy to w MathParser.org-mXparser.

/* Definicja funkcji rekurencyjncyh */
Constant a = new Constant(&quot;a = 0.1&quot;);
Function s = new Function(&quot;s(x) =&amp;amp;nbsp; if( abs(x) &amp;amp;lt; a, x, 2*s(x/2)*c(x/2) )&quot;, a);
Function c = new Function(&quot;c(x) =&amp;amp;nbsp; if( abs(x) &amp;amp;lt; a, 1, c(x/2)^2-s(x/2)^2 )&quot;, a);

/* Wskazanie, ze 's' korzysta z 'c', a 'c' korzysta z 's' */
s.addDefinitions(c);
c.addDefinitions(s);

Oczekujemy, że im mniejszy parametr $a>0$ tym lepsza aproksymacja funkcji $\sin(x)$ oraz $\cos(x)$ przez odpowiednio $\text{s}(x)$ oraz $\text{c}(x)$. Poniżej wykresy dla $a=0.5$ oraz $a=0.01$.

Rekurencja pośrednia i bezpośrednia - aproksymacja funkcji sin(x) oraz cos(x)

Rekurencja pośrednia i bezpośrednia - aproksymacja funkcji sin(x) oraz cos(x)

Wniosek – proste zapisy rekurencyjne dają złożone wyniki! 🙂

Rekurencja pośrednia i bezpośrednia – animacja

Pozdrowienia,

Mariusz Gromada

Zobacz również:

  1. Polowanie na czarownice – czyli zabawy z rekurencją (część 1)
  2. Prędkość ucieczki do nieskończoności – czyli zabawy z rekurencją (część 2)
  3. Naiwny test pierwszości – czyli zabawy z rekurencją (część 3)

Poza Liczbami: Inne Twórcze Przestrzenie

Matematyka i muzyka są ściśle powiązane przez rytm, harmonię i struktury

Matematyka i muzyka są ściśle powiązane przez rytm, harmonię i struktury, które wykorzystują matematyczne wzory i proporcje do tworzenia estetycznych i emocjonalnych doznań. Z nieśmiałą ekscytacją przedstawiam moją pierwszą poważniejszą kompozycję, w której starałem się uchwycić te połączenia.

I Am Here – RELEARN – Mariusz Gromada (2024)
I Am Here – RELEARN – Mariusz Gromada (2024)
Deep Under – RELEARN – Mariusz Gromada (2024)
Deep Under – RELEARN – Mariusz Gromada (2024)

Scalar – zaawansowana aplikacja mobilna z silnikiem matematycznym mojego autorstwa

Liczby pierwsze

Jednym z najprostszych testów pierwszości jest weryfikacja czy dana liczba $n$ posiada dzielnik z przedziału $(2, \sqrt{n})$ – takie podejście nazywane jest metodą naiwną – i niestety charakteryzuje się dużą złożonością obliczeniową. Nawet przy wykorzystaniu Sita Eratostenesa złożoność obliczeniowa sięga $\frac{\sqrt{n}}{\log{n}}$. Jednak w cyklu „Zabawy z rekurencją” nie bardzo zwracamy uwagę na złożoność 🙂 , bardziej chodzi o zobrazowanie jak całe algorytmy mogą być łatwo zapisane w postaci krótkich matematycznych funkcji rekurencyjnych – zatem do dzieła 🙂

Rekurencyjne poszukiwanie dzielników

Naszym zadaniem będzie zdefiniowanie funkcji zwracającej $1$ jeśli podana liczba $n$ jest liczbą pierwszą oraz $0$ w przeciwnym wypadku. Zacznijmy jednak od podania funkcji weryfikującej czy liczba posiada dzielniki.

$${\small\text{CzyDzielnik}(n, a, b)=}$$

$${\small=\begin{cases}0&\text{dla}\quad a>b\\1&\text{dla}\quad n \mod a=0\\ \text{CzyDzielnik}(n, a+1, b)&\text{w inn. przyp.}\end{cases}}$$

Powyższa funkcja zwraca $1$ jeśli liczba $n$ posiada dzielnik z przedziału $(a,b)$, oraz $0$ w przeciwnym wypadku. Następnie definiujemy wyrażenie reprezentujące naiwny test pierwszości.

$${\small\text{CzyPierwsza}(n)=}$$

$${\small=\begin{cases}0&\text{dla}\quad n<2\\ \neg\text{CzyDzielnik}(n,2,\sqrt{n})&\text{dla}\quad n>=2\end{cases}}$$

Rolą funkcji „CzyPierwsza” jest jedynie „wprawienie algorytmu w ruch” oraz zwrócenie negacji wyniki funkcji „CzyDzielnik”. Proste prawda? 🙂 Sprawdźmy więc w mXparser czy to faktycznie działa.

/* Definicja funkcji rekurencyjnych */
Function CzyDzielnik = new Function(&quot;CzyDzielnik(n, a, b) = if( a&amp;amp;gt;b, 0, if( n%a = 0, 1, CzyDzielnik(n, a+1, b) ) )&quot;);
Function CzyPierwsza = new Function(&quot;CzyPierwsza(n) = if( n&amp;amp;lt;2, 0, ~CzyDzielnik(n, 2, sqrt(n)) )&quot;, CzyDzielnik);

/* Obliczenie i wyświetlenie wartości */
mXparser.consolePrintln( &quot;CzyPierwsza(1) = &quot; + CzyPierwsza.calculate(1) + &quot;, czas oblicz. = &quot; + CzyPierwsza.getComputingTime() + &quot; s.&quot; );
mXparser.consolePrintln( &quot;CzyPierwsza(2) = &quot; + CzyPierwsza.calculate(2) + &quot;, czas oblicz. = &quot; + CzyPierwsza.getComputingTime() + &quot; s.&quot; );
mXparser.consolePrintln( &quot;CzyPierwsza(3) = &quot; + CzyPierwsza.calculate(3) + &quot;, czas oblicz. = &quot; + CzyPierwsza.getComputingTime() + &quot; s.&quot; );
mXparser.consolePrintln( &quot;CzyPierwsza(4) = &quot; + CzyPierwsza.calculate(4) + &quot;, czas oblicz. = &quot; + CzyPierwsza.getComputingTime() + &quot; s.&quot; );
mXparser.consolePrintln( &quot;CzyPierwsza(5) = &quot; + CzyPierwsza.calculate(5) + &quot;, czas oblicz. = &quot; + CzyPierwsza.getComputingTime() + &quot; s.&quot; );
mXparser.consolePrintln( &quot;CzyPierwsza(6) = &quot; + CzyPierwsza.calculate(6) + &quot;, czas oblicz. = &quot; + CzyPierwsza.getComputingTime() + &quot; s.&quot; );
mXparser.consolePrintln( &quot;CzyPierwsza(7) = &quot; + CzyPierwsza.calculate(7) + &quot;, czas oblicz. = &quot; + CzyPierwsza.getComputingTime() + &quot; s.&quot; );
mXparser.consolePrintln( &quot;CzyPierwsza(8) = &quot; + CzyPierwsza.calculate(8) + &quot;, czas oblicz. = &quot; + CzyPierwsza.getComputingTime() + &quot; s.&quot; );
mXparser.consolePrintln( &quot;CzyPierwsza(9) = &quot; + CzyPierwsza.calculate(9) + &quot;, czas oblicz. = &quot; + CzyPierwsza.getComputingTime() + &quot; s.&quot; );
mXparser.consolePrintln( &quot;CzyPierwsza(10) = &quot; + CzyPierwsza.calculate(10) + &quot;, czas oblicz. = &quot; + CzyPierwsza.getComputingTime() + &quot; s.&quot; );

+ wynik

CzyPierwsza(1) = 0.0, czas oblicz. = 0.08 s.
CzyPierwsza(2) = 1.0, czas oblicz. = 0.03 s.
CzyPierwsza(3) = 1.0, czas oblicz. = 0.026 s.
CzyPierwsza(4) = 0.0, czas oblicz. = 0.022 s.
CzyPierwsza(5) = 1.0, czas oblicz. = 0.038 s.
CzyPierwsza(6) = 0.0, czas oblicz. = 0.015 s.
CzyPierwsza(7) = 1.0, czas oblicz. = 0.028 s.
CzyPierwsza(8) = 0.0, czas oblicz. = 0.015 s.
CzyPierwsza(9) = 0.0, czas oblicz. = 0.053 s.
CzyPierwsza(10) = 0.0, czas oblicz. = 0.011 s.

Wygląda na to, że obliczenia są poprawne! Teraz możemy zweryfikować ile jest liczb pierwszych w podanym przedziale, definiując

$$\pi(n)=\sum_{i=1}^n \text{CzyPierwsza}(i)$$

/* Definicja wyrażenia sumującego wynik funkcji CzyPierwsza */
Expression pi100 = new Expression(&quot;sum(i, 1, 100, CzyPierwsza(i) )&quot;);
pi100.addFunctions(CzyPierwsza);

/* Obliczenie i wyświetlenie wyniku */
mXparser.consolePrintln( &quot;Liczba liczb pierwszych w przedziale (1,100) = &quot; + pi100.calculate());

+ wynik

Liczba liczb pierwszych w przedziale (1,100) = 25.0

Pozdrowienia,

Mariusz Gromada

Pamiętajcie, że uruchamiając kody mXparsera należy dodać w nagłówku:

import org.mariuszgromada.math.mxparser.*;

Kod:

Zobacz również:

  1. Polowanie na czarownice – czyli zabawy z rekurencją (część 1)
  2. Prędkość ucieczki do nieskończoności – czyli zabawy z rekurencją (część 2)
  3. Rekurencja pośrednia – czyli zabawy z rekurencją (część 4)

Poza Liczbami: Inne Twórcze Przestrzenie

Matematyka i muzyka są ściśle powiązane przez rytm, harmonię i struktury

Matematyka i muzyka są ściśle powiązane przez rytm, harmonię i struktury, które wykorzystują matematyczne wzory i proporcje do tworzenia estetycznych i emocjonalnych doznań. Z nieśmiałą ekscytacją przedstawiam moją pierwszą poważniejszą kompozycję, w której starałem się uchwycić te połączenia.

I Am Here – RELEARN – Mariusz Gromada (2024)
I Am Here – RELEARN – Mariusz Gromada (2024)
Deep Under – RELEARN – Mariusz Gromada (2024)
Deep Under – RELEARN – Mariusz Gromada (2024)

Scalar – zaawansowana aplikacja mobilna z silnikiem matematycznym mojego autorstwa

Dziś ciekawostka w nawiązaniu do wpisu z dnia 20 października 2015 roku „Liczba PI ukryta w zbiorze Mandelbrota”, ujawniająca nietrywialne powiązanie liczby $\pi$ z prędkością ucieczki do nieskończoności przy zbliżaniu się punktu startu iteracji do „ostrza” zbioru Mandelbrota. Brzmi trochę skomplikowanie? Poniżej wyjaśnienie 🙂

Zbliżanie się do „ostrza” zbioru Mandelbrota

Rozważmy równanie rekurencyjne dla liczb rzeczywistych

$$x_n=\begin{cases}x_{n-1}^2+\frac{1}{4}+\epsilon&\text{dla}\quad n>0\\0&\text{dla}\quad n=0\end{cases}$$

Powyższe wyrażenie powstaje na bazie równania (w liczbach zespolonych) opisującego zbiór Mandelbrota

$$z_n=z_{n-1}^2+c$$

Mandelbrot - Ostrze

Ograniczając się do prostej rzeczywistej (dlatego użyłem zapisu $x_n$) przeanalizujmy zachowanie $x_n$ przy zbliżaniu się elementu $x_1=\frac{1}{4}+\epsilon$ do „ostrza” (ang. „cusp”) zbioru – ostrze to punkt o współrzędnych $(\frac{1}{4},0)$.

Szybkość ucieczki do nieskończoności

Ustalając odpowiednio małe $\epsilon>0$ decydujemy jak bardzo chcemy się zbliżyć do „ostrza”. Teraz zadanie polega na znalezieniu pierwszego $n$, dla którego $x_n>=2$. Takie minimalne $n$ jest dobrą miarą prędkości ucieczki $x_n$ do nieskończoności w zależności od wybranego $\epsilon$. Na marginesie dodam, że zbiór Juli dla równania Mandelbrota (na powyższym obrazku oznaczony kolorem czarnym), reprezentuje punkty „nieuciekające” do nieskończoności w trakcie nieskończonej iteracji . Ta tematyka jest sama w sobie bardzo ciekawa i zapewne kiedyś coś napiszę o atraktorach.

$$x_n=\begin{cases}x_{n-1}^2+\frac{1}{4}+\epsilon&\text{dla}\quad n>0\\0&\text{dla}\quad n=0\end{cases}$$

$$N_\epsilon=\min\big\{n~|~x_n\ge2\big\}$$

Rekurencja na rekurencji

W celu poszukiwania rozwiązania zapisujemy zadanie wykorzystując rekurencję

$$N(n,\epsilon)=\begin{cases}N(n+1,\epsilon)&\text{dla}\quad x_n<2\\n&\text{dla}\quad x_n>=2\end{cases}$$

Nietrudno zauważyć, że zdefiniowaliśmy rekurencję na rekurencji. To zły znak dla wydajności.

Test w MathParser.org-mXparser

/* Definicja funkcji rekurencyjnej */
Function x = new Function(&quot;x(n, eps) = if( n &amp;amp;gt; 0, x(n-1, eps)^2 + 0.25 + eps, 0 )&quot;);
Function N = new Function(&quot;N(n, eps) = if( x(n, eps) &amp;amp;gt;= 2, n, N(n+1, eps) )&quot;, x);

/* Obliczenia i wyświetlenie wyniku */
mXparser.consolePrintln( &quot;eps = 0.01&quot; + &quot;, N(0, eps) = &quot; + N.calculate(0, 0.01) + &quot;, czas = &quot; + N.getComputingTime() + &quot; s&quot; );
mXparser.consolePrintln( &quot;eps = 0.0001&quot; + &quot;, N(0, eps) = &quot; + N.calculate(0, 0.0001) + &quot;, czas = &quot; + N.getComputingTime() + &quot; s&quot; );
mXparser.consolePrintln( &quot;eps = 0.000001&quot; + &quot;, N(0, eps) = &quot; + N.calculate(0, 0.000001) + &quot;, czas = &quot; + N.getComputingTime() + &quot; s&quot; );
mXparser.consolePrintln( &quot;eps = 0.00000001&quot; + &quot;, N(0, eps) = &quot; + N.calculate(0, 0.00000001) + &quot;, czas = &quot; + N.getComputingTime() + &quot; s&quot; );

+ wyczekiwany wynik

eps = 0.01, N(0, eps) = 30.0, czas = 0.224 s
eps = 0.0001, N(0, eps) = 312.0, czas = 1.532 s
eps = 0.000001, N(0, eps) = 3140.0, czas = 37.343 s
eps = 0.00000001, N(0, eps) = 31414.0, czas = 4068.338 s

Wzorzec prędkości ucieczki

$$\epsilon=\frac{1}{10}\Rightarrow N_\epsilon=30$$

$$\epsilon=\frac{1}{1000}\Rightarrow N_\epsilon=312$$

$$\epsilon=\frac{1}{100000}\Rightarrow N_\epsilon=3140$$

$$\epsilon=\frac{1}{10000000}\Rightarrow N_\epsilon=31414$$

WOW! Jaki super wzorzec liczby wymaganych iteracji, aby przekroczyć 2! Dostajemy coś, co przypomina $\pi$, jednak wymaga postawienia „przecinka” w odpowiednim miejscu! Można również zauważyć, że 100-krotne zmniejszenie $\epsilon$ zwiększa niezbędną liczbę iteracji około 10-krotnie. Zmniejszając $\epsilon$ otrzymujemy liczbę coraz bardziej „przypominającą” $\pi$ 🙂

Zbiór Mandelbrota

Pozdrowienia,

Mariusz Gromada

Zobacz również:

  1. Polowanie na czarownice – czyli zabawy z rekurencją (część 1)
  2. Naiwny test pierwszości – czyli zabawy z rekurencją (część 3)
  3. Rekurencja pośrednia – czyli zabawy z rekurencją (część 4)
  4. Liczba PI ukryta w zbiorze Mandelbrota

Poza Liczbami: Inne Twórcze Przestrzenie

Matematyka i muzyka są ściśle powiązane przez rytm, harmonię i struktury

Matematyka i muzyka są ściśle powiązane przez rytm, harmonię i struktury, które wykorzystują matematyczne wzory i proporcje do tworzenia estetycznych i emocjonalnych doznań. Z nieśmiałą ekscytacją przedstawiam moją pierwszą poważniejszą kompozycję, w której starałem się uchwycić te połączenia.

I Am Here – RELEARN – Mariusz Gromada (2024)
I Am Here – RELEARN – Mariusz Gromada (2024)
Deep Under – RELEARN – Mariusz Gromada (2024)
Deep Under – RELEARN – Mariusz Gromada (2024)

Scalar – zaawansowana aplikacja mobilna z silnikiem matematycznym mojego autorstwa

Okres średniowiecza, kobieta winna uprawiania magii, kara straszna – spalenie na stosie! Nadszedł dzień, tłum gawiedzi, czarownica na stosie, płomienie, wiedźma krzyczy – więcej drewna! Więcej drewna! Tłum zdziwiony, mimo wszystko spełnia ostatnie życzenie opętanej. Wiedźma nie przerywa – jeszcze więcej drewna! Więcej drewna! Z oddali dobiega nagły i stanowczy sprzeciw – STOP! Czarownica chce przepełnić stos!

🙂

Czarownica na stosie

Czym jest rekurencja?

Zazwyczaj o rekurencji myślimy jako o procesie podziału zadania na mniejsze, następnie podziału na jeszcze mniejsze, i jeszcze mniejsze … dochodząc do zadań, dla których rozwiązanie jest znane. Od tego momentu zaczyna się składanie „mniejszych” rozwiązań w „większe”, następnie tych większych w jeszcze większe, … i w jeszcze większe … kończąc na rozwiązaniu zadania początkowego. Dla przykładu zapiszmy funkcję n! w postaci rekurencyjnej.

$$n!=\begin{cases}n\cdot(n-1)!&\text{dla}\quad n>0\\1,&\text{dla}\quad n=0\end{cases}$$

W celu zobrazowania reprezentacja powyższego podana w mXparser:

/* Definicja funkcji rekurencyjnej */
Function silnia = new Function(&quot;s(n) = if( n&amp;amp;gt;0, n*s(n-1), 1 )&quot;);

/* Obliczenia i wyświetlenie wyniku */
System.out.println( &quot;n = 0, s(n) = &quot; + silnia.calculate(0) );
System.out.println( &quot;n = 1, s(n) = &quot; + silnia.calculate(1) );
System.out.println( &quot;n = 2, s(n) = &quot; + silnia.calculate(2) );
System.out.println( &quot;n = 3, s(n) = &quot; + silnia.calculate(3) );
System.out.println( &quot;n = 4, s(n) = &quot; + silnia.calculate(4) );
System.out.println( &quot;n = 5, s(n) = &quot; + silnia.calculate(5) );

+ wynik:

n = 0, s(n) = 1.0
n = 1, s(n) = 1.0
n = 2, s(n) = 2.0
n = 3, s(n) = 6.0
n = 4, s(n) = 24.0
n = 5, s(n) = 120.0

Wynik jest zgodny z oczekiwanym. Innym przykład rekurencji to iterowany operator sumowania, niech

$$A_n=a_1+a_2+\ldots+a_n=\sum_{i=1}^n a_i$$

Łatwo zauważyć, że

$$A_n=\begin{cases}a_n+A_{n-1},&\text{dla}\quad n>1\\a_1,&\text{dla}\quad n=1\end{cases}$$

Jak widać, rekurencja jest powszechna, często będąc nieco innym sposobem patrzenia na iteracje.

Formalna definicja rekurencji

O rekurencji mówimy jeśli metoda (funkcja, zachowanie, obiekt) może być opisana przez:

  1. elementy bazowe / rozwiązania bazowe;
  2. zestaw reguł, które redukuję (sprowadzają) każdy inny przypadek do (w kierunku) elementów bazowych.

Rekurencja
Powyższe określenie jest szerokie, ale takie być musi, bo i typów rekurencji jest wiele.

Rekurencja jako złożenie funkcji

Jednym (ale nie jedynym) sposobem zapisu ogólnych równań rekurencyjnych jest złożenie funkcji:

$$f_n=\begin{cases}F\big(f_{n-1},f_{n-2},\ldots,f_{n-k}\big)&\text{dla}\quad n>k\\f_1,f_2,\ldots,f_k&\text{el. baz. dla}\quad n<=k\end{cases}$$

Dobrą ilustracją powyższego jest ciąg Fibonacciego:

$$f_n=\begin{cases}0&\text{dla}\quad n=0\\1&\text{dla}\quad n=1\\f_{n-1}+f_{n-2}&\text{dla}\quad n>1\end{cases}$$

Zapiszmy ciąg Fibonacciego w mXparser:

/* Definicja funkcji rekurencyjnej */
Function fib = new Function(&quot;fib(n) = if( n&amp;amp;gt;1, fib(n-1)+fib(n-2), if(n=1,1,0) )&quot;);

/* Obliczenia i wyświetlenie wyniku */
System.out.println( &quot;fib(0) = &quot; + fib.calculate(0) );
System.out.println( &quot;fib(1) = &quot; + fib.calculate(1) );
System.out.println( &quot;fib(2) = &quot; + fib.calculate(2) );
System.out.println( &quot;fib(3) = &quot; + fib.calculate(3) );
System.out.println( &quot;fib(4) = &quot; + fib.calculate(4) );
System.out.println( &quot;fib(5) = &quot; + fib.calculate(5) );

+ rezultat:

fib(0) = 0.0
fib(1) = 1.0
fib(2) = 1.0
fib(3) = 2.0
fib(4) = 3.0
fib(5) = 5.0

Rekurencja w roli pętli „For”

Podane wyżej przykłady zapisów rekurencyjnych (n!, suma n-pierwszych wyrazów ciągu, ciąg Fibonacciego) są tak naprawdę rekurencyjną realizacją pętli „for” – znamy przecież dokładnie liczbę niezbędnych operacji do wykonania, a i same operacje są raczej łatwe oraz czytelne – zatem zagnieżdżenie ich w pętli „for” nie powinno spowodować utraty przejrzystości kodu.

Poszukiwanie rozwiązania – czyli rekurencja w roli pętli „While/Until”

W metodach numerycznych często stosuje się strategie rekurencyjne – w takiej sytuacji, będąc w kroku $n$, weryfikujemy czy propozycja rozwiązania $n$ spełnia kryterium stopu (np. jakość oszacowania), jeśli tak – kończymy z rozwiązaniem $n$, jeśli nie – przechodzimy do badania propozycji rozwiązania $n+1$. Procedurę rozpoczynamy od kroku 0 (zerowego).

Przykład: znając definicję silni chcemy znaleźć pierwsze $n$, dla którego $n! >= 100$ – takie zadanie formalnie możemy zapisać jako:

$$S_n=\begin{cases}S_{n+1},&\text{dla}\quad n!<100\\n,&\text{dla}\quad n!>=100\end{cases}$$

$$n_{100} = S(0)$$

Reprezentacja w mXparser:

/* Definicja funkcji rekurencyjnej */
Function S = new Function(&quot;S(n) = if( n! &amp;amp;lt; 100, S(n+1), n )&quot;); /* Obliczenia i wyświetlenie wyniku */ System.out.println( &quot;Pierwsze n, że n! &amp;amp;gt;= 100 to n = &quot; + S.calculate(0) );

+ wynik:

Pierwsze n, że n! &amp;amp;gt;= 100 to n = 5.0

Rekurencja bezpośrednia

Wszystkie omawiane wyżej typy rekurencji polegają na wywołaniu z ciała funkcji „siebie samej”, dlatego należą do bardziej ogólnej klasy nazywanej rekurencją bezpośrednią.

Wydajność

Implementacje na bazie rekurencji są bardzo czytelne, o często minimalnym rozmiarze kodu. Jednak coś za coś – tracimy bardzo dużo na złożoności obliczeniowej (powtarzane operacje, dzielenie zadań, operacje na stosie) oraz wymogach pamięci (głównie struktura stosu) – to właśnie dlatego czarownica błagała o drewno – licząc na przerwanie procesu z tytułu przepełnienia stosu 🙂

Cdn 🙂

Pozdrowienia,

Mariusz Gromada

Zobacz również:

  1. Prędkość ucieczki do nieskończoności – czyli zabawy z rekurencją (część 2)
  2. Naiwny test pierwszości – czyli zabawy z rekurencją (część 3)
  3. Rekurencja pośrednia – czyli zabawy z rekurencją (część 4)

Poza Liczbami: Inne Twórcze Przestrzenie

Matematyka i muzyka są ściśle powiązane przez rytm, harmonię i struktury

Matematyka i muzyka są ściśle powiązane przez rytm, harmonię i struktury, które wykorzystują matematyczne wzory i proporcje do tworzenia estetycznych i emocjonalnych doznań. Z nieśmiałą ekscytacją przedstawiam moją pierwszą poważniejszą kompozycję, w której starałem się uchwycić te połączenia.

I Am Here – RELEARN – Mariusz Gromada (2024)
I Am Here – RELEARN – Mariusz Gromada (2024)
Deep Under – RELEARN – Mariusz Gromada (2024)
Deep Under – RELEARN – Mariusz Gromada (2024)

Scalar – zaawansowana aplikacja mobilna z silnikiem matematycznym mojego autorstwa

mXparser – wysoce elastyczny parser (interpreter) wyrażeń matematycznych dla JAVA oraz C# .NET

mXparser - parser matematyczny

mXparser – wersja 1.0.2 dostępna do pobrania

Zmiana w stosunku do 1.0.1 to poprawa kontroli składni w funkcji definiowanej przez użytkownika. Do wersji 1.0.1 użycie argumentu rekurencyjnego w funkcji definiowanej przez użytkownika powodowało zwiększenie liczby oczekiwanych parametrów wywołania funkcji. Wartość argumentu rekurencyjnego jest wyznaczana automatycznie, stąd w kontroli składni (weryfikując liczbę podanych parametrów) taki argument należy pominąć. Od wersji 1.0.2 liczba parametrów funkcji definiowanej przez użytkownika opiera się na bazie liczby argumentów pomniejszonej o argumenty rekurencyjne.

Przykład

Poniżej przykład demonstrujący działanie wprowadzonej zmiany – proszę przesunąć tekst w celu uwidocznienia komentarzy.

</p>
<p>import org.mariuszgromada.math.mxparser.*;</p>
<p>public class mXparserTests {<br />
  public static void main(String[] args) {<br />
    RecursiveArgument z = new RecursiveArgument(&quot;z&quot;,&quot;z(n-1)^2+c&quot;, &quot;n&quot;); /* Definicja argumentu rekurencyjnego */<br />
    z.addBaseCase(0, 0);                                                /* Definicja elementu początkowego */<br />
    Constant c = new Constant(&quot;c&quot;, 0.3);                                /* Deklaracja stałej występującej w równaniu rekurencyjnym */<br />
    z.addConstants(c);                                                  /* Wskazanie argumentowi oczekiwanej stałej 'c' */<br />
    Function diff1 = new Function(&quot;diff1&quot;, &quot;z(n) - z(n-1)&quot;, &quot;n&quot;);       /* Definicja funkcji o parametrze n opartej również na argumencie rekurencyjnym */<br />
    diff1.addArguments(z);                                              /* Wskazanie funkcji oczekiwanego argumentu 'z' */<br />
    System.out.println(diff1.calculate(10));                            /* Obliczenie wartości funkcji + wyświetlenie wyniku */<br />
  }<br />
}</p>
<p>

Rezultat

</p>
<p>0.17863353779409574</p>
<p>

 

Pozdrowienia,

Mariusz Gromada

Poza Liczbami: Inne Twórcze Przestrzenie

Matematyka i muzyka są ściśle powiązane przez rytm, harmonię i struktury

Matematyka i muzyka są ściśle powiązane przez rytm, harmonię i struktury, które wykorzystują matematyczne wzory i proporcje do tworzenia estetycznych i emocjonalnych doznań. Z nieśmiałą ekscytacją przedstawiam moją pierwszą poważniejszą kompozycję, w której starałem się uchwycić te połączenia.

I Am Here – RELEARN – Mariusz Gromada (2024)
I Am Here – RELEARN – Mariusz Gromada (2024)
Deep Under – RELEARN – Mariusz Gromada (2024)
Deep Under – RELEARN – Mariusz Gromada (2024)

Scalar – zaawansowana aplikacja mobilna z silnikiem matematycznym mojego autorstwa

Wiek i rozmiar Wszechświata

Wpis z dnia 6 listopad 2015 „Precyzja liczby Pi a obwód obserwowalnego Wszechświata” zawierał nieco zaskakującą informację na temat rozmiaru Obserwowalnego Wszechświata – tzn. podałem, że promień Obserwowalnego Wszechświata wynosi obecnie około 46 miliardów lat świetlnych, co się wydaje być w niezgodzie z wiekiem Wszechświata szacowanym na 13,8 miliarda lat. Pokusiłem się wtedy o kilkuzdaniowe wyjaśnienie różnicy, teraz wracam do tematu prezentując materiał z serwisu YouTube, który w jasny i przejrzysty sposób ilustruje zagadnienia: rozmiaru Wszechświata (nie tylko w odniesieniu do jego obserwowalnej części), centrum Wszechświata oraz stożków świetlnych. Gorąco polecam!

„How Big is the Universe?” od MinutePhysics

„Radius of Observable Universe” (+ polskie napisy) od Khan Academy

Pozdrowienia,

Mariusz Gromada

Poza Liczbami: Inne Twórcze Przestrzenie

Matematyka i muzyka są ściśle powiązane przez rytm, harmonię i struktury

Matematyka i muzyka są ściśle powiązane przez rytm, harmonię i struktury, które wykorzystują matematyczne wzory i proporcje do tworzenia estetycznych i emocjonalnych doznań. Z nieśmiałą ekscytacją przedstawiam moją pierwszą poważniejszą kompozycję, w której starałem się uchwycić te połączenia.

I Am Here – RELEARN – Mariusz Gromada (2024)
I Am Here – RELEARN – Mariusz Gromada (2024)
Deep Under – RELEARN – Mariusz Gromada (2024)
Deep Under – RELEARN – Mariusz Gromada (2024)

Scalar – zaawansowana aplikacja mobilna z silnikiem matematycznym mojego autorstwa

W poprzednich częściach omówiliśmy sposób tworzenia macierzy błędu oraz podstawowe miary oceny jakości klasyfikacji: czułość (TPR), specyficzność (TNR), precyzję przewidywania pozytywnego (PPV), precyzję przewidywania negatywnego (NPV). Opisane miary określone są dla klasyfikatora binarnego (klasyfikacja pozytywna bądź negatywna), jednak w praktyce najczęściej stosuje się modele predykcyjne z ciągłą zmienną odpowiedzi (np. estymator prawdopodobieństwa skorzystania z produktu, gdzie wynikiem działania modelu jest wartość z przedziału [0, 1] interpretowana właśnie jako wspomniane prawdopodobieństwo określane również skłonnością).

Model predykcyjny

Dla lepszego zrozumienia załóżmy, że analizujemy bazę $n$-klientów oznaczonych odpowiednio $x_1, x_2, \ldots, x_n$. Model predykcyjny to np. funkcja (estymator) zwracająca dla każdego klienta właściwe dla niego prawdopodobieństwo zakupienia produktu – oznaczmy więc fakt zakupienia produktu klasą pozytywną „1”. Teraz możemy podać bardziej formalne określenie – zatem model predykcyjny to estymator prawdopodobieństwa warunkowego $p(1|x_i)$, że wystąpi zakup produktu (klasa „1”), pod warunkiem, że zaobserwujemy cechy klienta $x_i$.

$$p(1| \cdot ) : \{x_1, x_2, \ldots, x_n\} \to [0;1]$$

$$x_i\mapsto p(1| x_i ) \in [0;1]$$

Obserwacja cech klienta, a nie samego klienta, jest tu niezwykle istotna. Mianowicie danego klienta mamy dokładnie jednego, natomiast klientów o tych samych / podobnych cechach (np. miejsce zamieszkania, wiek, itp.) możemy posiadać wielu, co dalej umożliwia wnioskowanie indukcyjne, a w wyniku otrzymanie upragnionego modelu 🙂 .

Segment wysokiej skłonności

Typowo mniejszość klientów charakteryzuje się „wysoką” skłonnością, natomiast „średnia” i „niska” skłonność jest przypisywana do znacznie większej części bazy. Łatwo to uzasadnić – zazwyczaj w określonym okresie czasu produkt kupuje maksymalnie kilka procent bazy klientów. Jeśli model predykcyjny posiada faktyczną wartość predykcyjną, wysokie prawdopodobieństwo przypisze do relatywnie niewielkiej części klientów. Idąc dalej – im lepszy model, tym segment o wysokiej skłonności jest mniejszy i bliższy rozmiarem do oszacowania pochodzącego ze średniej sprzedaży mierzonej dla całej analizowanej bazy klientów (tzw. oszacowanie a-priori).

Model predykcyjny i punkt odcięcia

Punkt odcięcia (cut-off point)

Zadaniem punktu odcięcia jest stworzenie na bazie ciągłej zmiennej odpowiedzi (np. szacowanego prawdopodobieństwa) segmentów (klas) – dla uproszczenia załóżmy, że dwóch (jeden punkt odcięcia). Oznaczmy przez $p_0 \in [0;1]$ punkt rozgraniczający segment wysokiej skłonności od segmentów średniej i niskiej skłonności. Jeśli szacowane prawdopodobieństwo $p(1|x_i) \geq p_0$ klientowi $x_i$ przypiszemy klasę pozytywną „1”, w przeciwnym wypadku klientowi przypisujemy klasę negatywną „0”.

W powyższy sposób z „ciągłego” modelu predykcyjnego otrzymaliśmy klasyfikator binarny – co, w zestawieniu z faktycznymi zdarzeniami zakupu, umożliwia utworzenie macierzy błędu i wyznaczenie wszystkich istotnych miar oceny jakości dokonanej klasyfikacji.

Ale jak dobrać punkt odcięcia? O tym w następnej części 🙂

Pozdrowienia,

Mariusz Gromada

Poza Liczbami: Inne Twórcze Przestrzenie

Matematyka i muzyka są ściśle powiązane przez rytm, harmonię i struktury

Matematyka i muzyka są ściśle powiązane przez rytm, harmonię i struktury, które wykorzystują matematyczne wzory i proporcje do tworzenia estetycznych i emocjonalnych doznań. Z nieśmiałą ekscytacją przedstawiam moją pierwszą poważniejszą kompozycję, w której starałem się uchwycić te połączenia.

I Am Here – RELEARN – Mariusz Gromada (2024)
I Am Here – RELEARN – Mariusz Gromada (2024)
Deep Under – RELEARN – Mariusz Gromada (2024)
Deep Under – RELEARN – Mariusz Gromada (2024)

Scalar – zaawansowana aplikacja mobilna z silnikiem matematycznym mojego autorstwa