RnW4kuzDbDbdX
Ilustracja przedstawia spirale fraktali.

Rekurencja. Fraktale. Ciekawostki matematyczne

Źródło: dostępny w internecie: www.pixabay, domena publiczna.

Cały świat jawi nam się jako zbiór fraktalifraktalfraktali. Nie znajdujemy w nim idealnych geometrycznych kształtów, takich jak koła, prostokąty, sześciany, stożki, które moglibyśmy obliczyć przy pomocy prostych wzorów matematycznych.

Czy istnieje metoda, by zmierzyć coś tak nieregularnego jak fraktale? Czy umiemy odzwierciedlić matematycznie te skomplikowane kształty?

Istnieje rozwiązanie, które jest odpowiedzią na te pytania i brzmi: równania rekurencyjnerekurencyjnyrekurencyjne.

  1. Interaktywna treść merytorycznaInteraktywna treść merytoryczna

  2. MultimediumMultimedium

  3. Zestaw ćwiczeń interaktywnychZestaw ćwiczeń interaktywnych

  4. SłownikSłownik

  5. BibliografiaBibliografia

Twoje cele

  • Dowiesz się, czym jest i do czego służy rekurencja.

  • Zrozumiesz, czym są fraktale i w jaki sposób powstają.

  • Przeanalizujesz związek, który istnieje między rekurencją a fraktalami.

1

Rekurencja

RekurencjarekurencjaRekurencja w informatyce oznacza program, który odwołuje się sam do siebie. Aby zastosować rekurencję w programowaniu, musimy wiedzieć, jak ją zdefiniować. Robimy to w dwóch krokach:

  1. Pierwszy krok nazywamy warunkiem początkowym. Musimy mieć wyliczone wszystkie elementy, w tym podstawowe, które stanowią części składowe zbioru.

  2. Krok drugi nazywamy krokiem indukcyjnymindukcjaindukcyjnym. Musimy podać regułę, która pozwoli skonstruować nowy obiekt z elementów podstawowych lub z obiektów, które zbudowaliśmy wcześniej. Takich reguł możemy używać wielokrotnie, by budować kolejne nowe obiekty.

RjQDMkjYgbplD
Ilustracja przedstawia schody biegnące po nieboskłonie. Pod zdjęciem jest tekst: Wyobraź sobie, że mamy zaprojektować nieskończenie wysokie schody. Na początek musimy określić, jak mają wyglądać nasze schody (warunek podstawowy). Następnie używamy reguły, by skonstruować pierwszy stopień, a potem kolejny i kolejny, bo przecież na naszych nieskończonych schodach muszą istnieć kolejne stopnie (krok indukcyjny).Rekurencja polega na uproszczeniu skomplikowanego problemu (np. podzieleniu nieskończonych schodów na mniejsze części – stopnie). W celu rozwiązania problemu używamy tego samego algorytmu do rozwiązania części problemu i jego całości.
Wyobraź sobie, że mamy zaprojektować nieskończenie wysokie schody. Na początek musimy określić, jak mają wyglądać nasze schody (warunek podstawowy). Następnie używamy reguły, by skonstruować pierwszy stopień, a potem kolejny i kolejny, bo przecież na naszych nieskończonych schodach muszą istnieć kolejne stopnie (krok indukcyjny).

Rekurencja polega na uproszczeniu skomplikowanego problemu (np. podzieleniu nieskończonych schodów na mniejsze części – stopnie). W celu rozwiązania problemu używamy tego samego algorytmu do rozwiązania części problemu i jego całości.
Źródło: dostępny w internecie: pixabay.com, domena publiczna.
Ważne!

Wszystkie algorytmy rekurencyjne muszą być zbudowane z kolejnych kroków:

  1. mają określony warunek początkowy (który mówi nam, kiedy zadanie jest ukończone i należy ukończyć pracę);

  2. przeprowadzają działania w celu wypełnienia warunku początkowego;

  3. stosują rekurencję, czyli odwołują się do samych siebie.

Fraktale

ROuFNFk82Ktq71
Ilustracja przedstawia zdjęcia kalafiora, którego różyczki mają kształ fraktali.
Kalafior rzymski jest przykładem występowania struktur fraktalnych w przyrodzie.
Źródło: Ivar Leidus, dostępny w internecie: wikipedia.org, licencja: CC BY-SA 4.0.

Dzięki stosowaniu rekurencji możemy konstruować fraktalefraktalfraktale, ponieważ jesteśmy w stanie rozwiązać problem w oparciu o rozwiązania tego samego problemu dla danych o mniejszym rozmiarze.

FraktalefraktalFraktale są bardzo złożonymi figurami geometrycznymi, których nie możemy zaliczyć ani do brył, ani do krzywych, ani do powierzchni. Nad fraktalami pracowano już na początku XX wieku, ale dopiero powstanie komputerów pozwoliło na ich badanie. Wielu badaczy twierdzi, że fraktale ukazują geometrię przyrody.

Fraktale powstają w wyniku dowolnej liczby powtórzeń określonej operacji matematycznej. Najłatwiej je stworzyć, dzieląc figurę na podobne do całości mniejsze części, używając w tym celu komputera i przepisu rekurencyjnego.

Fraktale posiadają odmienne cechy niż znane nam dotąd figury geometryczne:

RSe1azgJCPTih1
Grafika przedstawia powtórzony wielokrotnie wzór fraktali o różnych wielkościach.
Zbiór Julii
Źródło: Solkoll, domena publiczna.

  • nie są określone wzorem matematycznym i można je tworzyć dzięki zastosowaniu algorytmów rekurencyjnych;

  • ich wymiar nigdy nie jest liczbą całkowitą;

  • można je przybliżać w nieskończoność.

Notatnik

R1dTC6w8nHW3Z
Miejsce na Twoje notatki: (Uzupełnij).
Źródło: GroMar Sp. z o.o., licencja: CC BY 3.0.
2

Film edukacyjny

R1QQ3mGLCGUSC1
Film nawiązujący do treści materiału

Film dostępny pod adresem /preview/resource/R1QQ3mGLCGUSC

Film nawiązujący do treści materiału

Prezentacja multimedialna

Polecenie 1

Zapoznaj się z prezentacją i odpowiedz na pytanie, dlaczego uważa się, że świat naturalny ma budowę fraktalną. Wymień przykłady trzech rzeczy w naturze, które charakteryzują się taką budową i uzasadnij swoją odpowiedź.

R1QTiG311TfZd
(Uzupełnij).
RV9RwmqwV87Eh
1. Fraktalny świat opis alternatywny{audio}źródło: pixabay.com, domena publiczna

W świecie, który widzimy, trudno jest odnaleźć idealne kształty znane nam z lekcji geometrii. Jeśli spojrzymy na morze, góry, łąkę, futro naszego zwierzaka czy pióro ptaka, raczej nie znajdziemy nic idealnie kulistego czy sześciennego. Trudno nam będzie nawet odnaleźć idealną linię prostą. Wszystko, co widzimy w naturze, ma nieregularny kształt. Mimo tego możemy opisać te struktury prostymi wzorami matematycznymi opartymi na rekurencji., 2. Naturalna geometria opis alternatywny{audio}źródło: pixabay.com, domena publiczna

Wielu badaczy uważa, że cały wszechświat ma budowę fraktalną. Opisywanie fraktali polega na tym, by rzeczy, które widzimy w naturze i które wydają nam się skomplikowane, opisać z użyciem prostych reguł. Francuski matematyk Benoît Mandelbrot twierdzi, że właśnie od takiej geometrii powinniśmy zaczynać naukę w szkołach, a nie od abstrakcyjnych brył i figur.
Źródło: pasja1000, dostępny w internecie: www.pixabay.com, domena publiczna.
RsRAuTAxR196G
1. Linia brzegowa Wielkiej Brytanii {audio}Odkrycie fraktali jest związane z próbą zmierzenia długości obwodu Wielkiej Brytanii. Podczas prób wykonania tego zadania zauważono, że im bardziej dokładna jest mapa, tym większa staje się długość obwodu wyspy. Działo się tak, ponieważ powiększanie mapy ukazywało coraz bardziej skomplikowaną linię brzegową.

, 2. Paradoks linii brzegowej opis alternatywny{audio}Paradoks linii brzegowej to sprzeczna z intuicją obserwacja, że linia brzegowa lądu nie ma dobrze określonej długości. Wynika to z fraktalnych właściwości linii brzegowych, czyli z faktu, że linia brzegowa ma zazwyczaj wymiar fraktalny. Pierwszej takiej obserwacji dokonał angielski matematyk Lewis Fry Richardson.
źródło: wikipedia.org, licencja: CC BY-SA 3.0
Źródło: dostępny w internecie: pixabay.com, domena publiczna.
R1N0Y4k4P4kuf
1. Samopodobieństwo fraktali {audio}Jedną z cech charakterystycznych fraktala jest samopodobieństwo, to znaczy podobieństwo całości do jego części. Zbiory fraktalne mogą być samopodobne w ten sposób, że część zbioru może być obrazem całości. opis alternatywnyZbiór Mandelbrota – jeden z najbardziej znanych fraktali.
źródło: wikipedia.org, CC BY-SA 3.0, 2. abc }{audioFraktal podobny do liścia paproci.
Każdy z liści jest związany z pozostałymi i może zostać przetransformowany. Np. czerwony liść można przetransformować w liść niebieski poprzez odbicia, obroty, skalowanie.
źródło: wikipedia.org, domena publiczna
Źródło: dostępny w internecie: wikipedia.org, licencja: CC BY 4.0.
RmsRwRHY3ZEZN
RX71GjPDZe3t7
Gif przedstawia sześciany. Po zbliżeniu widzimy, że sześciany złożone są z innych wyglądających tak samo sześcianów.
W ten sposób wygląda odpowiednik zbioru Cantora przedstawiony w przestrzeni trójwymiarowej.
Źródło: Mattcomm, dostępny w internecie: wikipedia.org, licencja: CC BY-SA 4.0.
RnAIpShz39gos
Filmik przedstawia zbliżenie na sześciany, które składają się z mniejszych sześcianów, złożonych z sześcianów.
Aby stworzyć kostkę Mengera bierzemy sześcian i tniemy go na 27 sześcianów o równej wielkości. Następnie usuwamy sześcian znajdujący się w środku naszego pierwszego sześcianu i wszystkie sześciany przyległe do środków ścian. Kroki te możemy powtarzać w nieskończoność.
Źródło: pixabay.com, W roku 1927 austriacki matematyk Karl Menger przedstawił bryłę fraktalną, która została nazwana kostką lub gąbką Mengera., domena publiczna. Cytat za: pixabay.com.

Film dostępny pod adresem /preview/resource/RnAIpShz39gos

Aby stworzyć kostkę Mengera bierzemy sześcian i tniemy go na 27 sześcianów o równej wielkości. Następnie usuwamy sześcian znajdujący się w środku naszego pierwszego sześcianu i wszystkie sześciany przyległe do środków ścian. Kroki te możemy powtarzać w nieskończoność.
Źródło: pixabay.com, W roku 1927 austriacki matematyk Karl Menger przedstawił bryłę fraktalną, która została nazwana kostką lub gąbką Mengera., domena publiczna. Cytat za: pixabay.com.

Filmik przedstawia zbliżenie na sześciany, które składają się z mniejszych sześcianów, złożonych z sześcianów.

R9xlFduxZUpCW
1. Fraktalność ludzkiego organizmu {audio}Niektórzy szukają fraktalnych kształtów w ludzkim organizmie, np. w wyglądzie naczyń krwionośnych lub płuc, a nawet w elektrycznej aktywności mózgu. Inni starają się to wykorzystać w medycynie. Zostały przeprowadzone badania rytmu bicia serca. Okazało się, że ci, u których struktura uderzeń serca miała postać fraktalną (uderzenia serca miały podobny rytm w krótkich i w dłuższych odstępach czasu), mieli ten organ zdrowy. Zaś u tych, u których struktura uderzeń nie miała postaci fraktalnej, często znajdowano choroby serca.
opis alternatywnyźródło: pixabay.com, domena publiczna, 2. Dlaczego podobają nam się fraktale? {audio}Nasze naturalne, złożone środowisko obfituje w najrozmaitsze fraktale. Nasz umysł jest skonstruowany w ten sposób, że podoba mu się to, co jest znajome.opis alternatywnyźródło: pixabay.com, domena publiczna
Źródło: PublicDomainPictures, dostępny w internecie: www.pixabay.com, domena publiczna.
Polecenie 2

Przedstaw w szkicowniku sposób tworzenia zbioru Cantora.

RyEw001KTapNx
Plansza interaktywna. Można na niej rysować, tworzyć kształty w różnych kolorach.
Źródło: GroMar Sp. z o.o., licencja: CC BY 3.0.
RsJxEXv2ZObx5
Ćwiczenie 1
Zaznacz poprawną odpowiedź. Co to jest zbiór Cantona?
Źródło: GroMar Sp. z o.o., licencja: CC BY 3.0.
3
Polecenie 3

Przedstaw własnymi słowami, na czym polega samopodobieństwo fraktali.

R1NNnFWX5uVri
(Uzupełnij).
Źródło: GroMar Sp. z o.o., licencja: CC BY 3.0.

Zestaw ćwiczeń interaktywnych

RFfEkSojpiXO5
Ćwiczenie 1
Zaznacz poprawną odpowiedź.
Co oznacza rekurencja w programowaniu? Możliwe odpowiedzi: 1. Rekurencja w programowaniu oznacza taki program, który odwołuje się sam do siebie., 2. Rekurencja w programowaniu oznacza taki program, który działa w nieskończoność., 3. Rekurencja w programowaniu oznacza taki program, który jest zbudowany z wielu różnych algorytmów.
Źródło: Anna Sarosiek, licencja: CC BY 3.0.
RWYVq9QObNliY1
Ćwiczenie 2
Uzupełnij tekst tak, by wyjaśniał, czym jest fraktal. Fraktal oznacza zwykle obiekt 1. powiększać, 2. matematyka, 3. interpretować, 4. architektury, 5. porządkowania figur, 6. wielobarwny, 7. natura, 8. wszechświata, 9. algorytmu rekurencyjnego, 10. strukturę, 11. ludzkich płuc, 12. samopodobny, 13. całości obiektu i nieskończenie złożony. Każdy z elementów, z których składa się fraktal, jest podobny w budowie do 1. powiększać, 2. matematyka, 3. interpretować, 4. architektury, 5. porządkowania figur, 6. wielobarwny, 7. natura, 8. wszechświata, 9. algorytmu rekurencyjnego, 10. strukturę, 11. ludzkich płuc, 12. samopodobny, 13. całości obiektu. Fraktale możemy dowolnie 1. powiększać, 2. matematyka, 3. interpretować, 4. architektury, 5. porządkowania figur, 6. wielobarwny, 7. natura, 8. wszechświata, 9. algorytmu rekurencyjnego, 10. strukturę, 11. ludzkich płuc, 12. samopodobny, 13. całości obiektu i wciąż odkrywać tę samą powtarzającą się 1. powiększać, 2. matematyka, 3. interpretować, 4. architektury, 5. porządkowania figur, 6. wielobarwny, 7. natura, 8. wszechświata, 9. algorytmu rekurencyjnego, 10. strukturę, 11. ludzkich płuc, 12. samopodobny, 13. całości obiektu. Mimo że wyglądają na złożone z chaotycznych elementów, mogą być konstruowane przy pomocy 1. powiększać, 2. matematyka, 3. interpretować, 4. architektury, 5. porządkowania figur, 6. wielobarwny, 7. natura, 8. wszechświata, 9. algorytmu rekurencyjnego, 10. strukturę, 11. ludzkich płuc, 12. samopodobny, 13. całości obiektu. Niektórzy twierdzą, że wszędzie spotkamy się z fraktalami, ponieważ 1. powiększać, 2. matematyka, 3. interpretować, 4. architektury, 5. porządkowania figur, 6. wielobarwny, 7. natura, 8. wszechświata, 9. algorytmu rekurencyjnego, 10. strukturę, 11. ludzkich płuc, 12. samopodobny, 13. całości obiektu jest zbudowana z fraktali. Dostrzegamy je w strukturach 1. powiększać, 2. matematyka, 3. interpretować, 4. architektury, 5. porządkowania figur, 6. wielobarwny, 7. natura, 8. wszechświata, 9. algorytmu rekurencyjnego, 10. strukturę, 11. ludzkich płuc, 12. samopodobny, 13. całości obiektu, kryształów, piór, galaktyk.
Źródło: Anna Sarosiek, licencja: CC BY 3.0.
R6XTvTNV7SZBE1
Ćwiczenie 3
Wskaż ilustracje, które przedstawiają fraktalną budowę figury.
Źródło: Anna Sarosiek, licencja: CC BY 3.0.
RFPGJA089g7YU1
Ćwiczenie 3
Zaznacz odpowiedź.
Która z postaci w 1883 roku przedstawiła swój pomysł opisu najprostszego fraktala?
Źródło: GroMar Sp. z o.o., licencja: CC BY 3.0.
RYtI8zkcuYZmf2
Ćwiczenie 4
Określ, czym różni się zbiór Cantora od kostki Mengera. zbiór Cantora Możliwe odpowiedzi: 1. tworzenie tego zbioru polega na dzieleniu odcinków, 2. tworzenie tego zbioru polega na dzieleniu sześcianów kostka Mengera Możliwe odpowiedzi: 1. tworzenie tego zbioru polega na dzieleniu odcinków, 2. tworzenie tego zbioru polega na dzieleniu sześcianów
Źródło: Anna Sarosiek, licencja: CC BY 3.0.
R11BZNMKwRC7p2
Ćwiczenie 5
Zaznacz poprawne odpowiedzi.
Które z poniższych cech charakteryzują fraktale? Możliwe odpowiedzi: 1. skończoność figur, 2. możliwość tworzenia przy pomocy algorytmów rekurencyjnych, 3. wymiar, który nie jest liczbą całkowitą, 4. niemożliwość przeprowadzenia transformacji części figury
Źródło: Anna Sarosiek, licencja: CC BY 3.0.
RmAyGN1D34rpP
Ćwiczenie 6
Zaznacz kolorem zielonym działania, które są związane z podstawowymi elementami algorytmu rekurencyjnego a kolorem czerwonym te, które nie są. Określenie warunku początkowego. Sumowanie ilości działań. Przeprowadzenie działań w celu wypełnienia warunku początkowego. Tworzenie fraktali przy pomocy wzorów matematycznych. Zmierzanie do nieskończoności. Stosowanie odwołań do samych siebie.
Źródło: Anna Sarosiek, licencja: CC BY 3.0.
RhNCXB6MuxNGS
Ćwiczenie 6
Źródło: GroMar Sp. z o.o., licencja: CC BY 3.0.
31
Ćwiczenie 7

Opisz własnymi słowami, jaki związek ma rekurencja z fraktalami.

RxkwRpMCViBz5
(Uzupełnij).
Źródło: GroMar Sp. z o.o., licencja: CC BY 3.0.
31
Ćwiczenie 8

Wymyśl problem, który mógłby zostać opisany przy pomocy rekurencji i przedstaw kolejne kroki zmierzające do rozwiązania go.

R1dxOFq7JJXOZ
(Uzupełnij).
Źródło: GroMar Sp. z o.o., licencja: CC BY 3.0.
4

Słownik

fraktal
fraktal

(łac. fractus – złamany, cząstkowy, ułamkowy) obiekt samopodobny, czyli taki, którego części są podobne do całości

indukcja
indukcja

(łac. inductio – wyprowadzenie) wyprowadzanie wniosków ogólnych z przesłanek będących szczególnymi przypadkami tych wniosków

rekurencja
rekurencja

(ang. recursion, z łac. recurrere, przybiec z powrotem) inaczej rekursja; w matematyce i w informatyce (np. w programowaniu) działanie polegające na odwoływaniu się do samego siebie, np. do własnej definicji, funkcji lub procedury

rekurencyjny
rekurencyjny

dający się przedstawić za pomocą już znanych wielkości; np. wzór rekurencyjny – można obliczyć wyrazy ciągu na podstawie jednego lub kilku wyrazów, które były już w tym ciągu użyte

5

Bibliografia

  • Jorasz U., Piękno w nauce, Scripta Neophilologica Posnaniensia 12 (2012), s. 23‑30

  • Winnicki I., Fraktale wokół nas i kilka słów o chaosie, Zeszyty Naukowe Warszawskiej Wyższej Szkoły Informatyki, Warszawa 2011, s. 169‑184