Dywan Sierpińskiego

Dywan Sierpińskiego – to fraktal otrzymany z kwadratu za pomocą podzielenia go na dziewięć (3x3) mniejszych kwadratów, usunięcia środkowego kwadratu i ponownego rekurencyjnego zastosowania tej samej procedury do każdego z pozostałych ośmiu kwadratów. Nazwa pochodzi od nazwiska Wacława Sierpińskiego.

Co to dla nas oznacza? Jak się to ma do zbioru Cantora?

Zapewne widzicie, że taki dywan to coś do zbioru Cantora bardzo podobnego, tyle że dwuwymiarowego. Zamiast wycinać odcinek o długości ⅓ wycinamy kwadrat o boku ⅓ .

Odpowiednio do tego musimy więc zmodyfikować nasze procedury:

W programie brakuje kilku wywołań rekurencyjnych (od linii 28), ale myślę, że już sobie z tym poradzicie.

Ponieważ procedura rect() robi trochę roboty za nas, obliczenia są nieco prostsze niż dla poprzedniego ćwiczenia. Warto jednak przyjrzeć się, czy aby znowu nie jesteśmy trochę oszukiwani przez grafikę rastrową, zwłaszcza przy bardzo małych wartościach limitu.

Pośrednim etapem uzupełniania wywołań mogą być takie “ułomne” dywany jak poniżej:

Zbiór Cantora

Zbiór Cantora – podzbiór prostej rzeczywistej opisany w 1883^[1] przez niemieckiego matematyka Georga Cantora. Zbiór ten odkrył w 1875 Henry John Stephen Smith.

Zbiór Cantora jest najprostszym przykładem fraktala.

Z Wikipedii

Klasyczny zbiór Cantora (zwany także trójkowym zbiorem Cantora) to podzbiór przedziału domkniętego [0,1]. Jego konstrukcja polega na usuwaniu z odcinka jego środkowej 1/3 i aplikowaniu tej samej zasady rekurencyjnie do dwu pozostałych pod-odcinków. W świecie idealnym, po nieskończonej liczbie iteracji ;-) powstaje nam bardzo rozproszony podzbiór punktów z zadanego zakresu. W świecie grafiki komputerowej nie ma oczywiście sensu zajmować się czymś co jest poniżej rozdzielczości ekranu, musimy więc konstrukcję naszego zbioru zatrzymać na rozmiarze pojedynczego piksela.

Organizacja programu jest podobna do poprzedniego (testującego rekurencyjną procedurę rysowania linii kropkowanej) . Procedura setup() ustawia parametry okna i wywołuje testowaną procedurę rekurencyjną. Tyle że w tym wypadku dwie nieco odmienne.

Pokazana procedura cantorSetHor1() każdą iterację zbioru rysuje na innej linii ekranu, posługując się wartością d czyli długością odcinka dzielonego na danym etapie. Zbiór jest zdefiniowany w zakresie liczb rzeczywistych, więc posługujemy się ich przybliżeniem - typem float. Będziemy mieć z tym pewien problem, bo całość mapujemy na CAŁKOWITE współrzędne pikseli okna. Do tego dochodzi "skłonność" procedury line() do włączania końcowych punktów, co przy granicznych długościach powodowałoby asymetryczne nakładanie się rysowanych linii. Stąd jawnie zabieramy obu bocznym liniom punkty graniczące z linią środkową, czyli ta formalnie wycinaną, a praktycznie kolorowaną na zielono. Na wszelki wypadek kolorujemy też punkt środkowy odcinka. Będzie to widoczne tylko wtedy gdy linia zrobi się bardzo, bardzo krótka ;-)

Po wykonaniu rysowania (linie 26-33) wywołujemy znowu funkcję cantorSetHor1() dla prawego i lewego pod-odcinka (linia 35).

Alternatywna procedura cantorSetHor2() zbudowana jest niemal identycznie. Jedyna różnica to współrzędna Y okna używana w rysowaniu. Zawsze jest to height/2 , co powoduje że wszystkie efekty rysowania trafiają w tą samą linie. No i kolory zielony został zamieniony na 'cyan', a 'magenta' na czerwony.

Możemy się temu lepiej przyjrzeć, jeśli zmienimy w setup'ie grubość linii np. na 5. MUSIMY TEŻ WTEDY ZMIENIĆ  SPOSÓB KOŃCZENIA LINI!

strokeWeight(5); strokeCap(SQUARE);

Rekurencja

"Rekurencja, zwana także rekursją (ang. recursion, z łac. recurrere, przybiec z powrotem) – odwoływanie się np. funkcji lub definicji do samej siebie.

W logice wnioskowanie rekurencyjne opiera się na założeniu istnienia pewnego stanu początkowego oraz zdania (lub zdań) stanowiącego podstawę wnioskowania (przy czym, aby cały dowód był poprawny, zarówno reguła, jak i stan początkowy muszą być prawdziwe). Istotą rekurencji jest tożsamość dziedziny i przeciwdziedziny reguły wnioskowania, wskutek czego wynik wnioskowania może podlegać tej samej regule zastosowanej ponownie."
"Rekurencja jest podstawową techniką wykorzystywaną w funkcyjnych językach programowania. Należy jednak zachować ostrożność przy używaniu rekurencji w rzeczywistych programach. Ryzyko istnieje szczególnie przy przetwarzaniu dużej ilości głęboko zagnieżdżonych danych."

Z Wikipedii

W praktyce rekurencja sprowadza się do wielokrotnego wywoływania funkcji przez samą siebie, coraz bardziej "w głąb stosu", dla coraz mniej skomplikowanego zadania, aż dochodzimy do trywialnej jego wersji i dalsze zagłębianie się nie ma już sensu. 

Rekurencja jest przez teoretyków programowania uznawana za samo sedno inteligencji algorytmicznej. Wg. nich nie jest programistą ten kto rekurencji nie rozumie ;-)
Ja nie byłbym tak ortodoksyjny, ale jednak uważam, że warto tą ideę wytłumaczyć, bo bez tego trudno o zrozumienie grafik fraktalnych, które są po prostu ładne :-)

Temat rekurencji wprowadza się zwykle za pomocą funkcji silni czy jakiś ciągów - np. Fibbonacciego. Ale to czysta matematyka, a ja w tym kursie staram się używać raczej grafiki, jako trafiającej do większej liczby odbiorców.
W grafice komputerowej raczej unika się algorytmów rekurencyjnych, jako mało efektywnych, ale istnieje jeden, historycznie istotny. To "wypełnianie przez sianie" czy też, wg. bardziej popularnej nazwy angielskiej "flood fill".
Niestety algorytm ten wymaga możliwości odczytania koloru punktu, który już jest na ekranie (czy w oknie), której jednak w Processingu nie znalazłem. Jest taka, która pozwala czytać kolor punktu załadowanego obrazka, co może kiedyś jeszcze wykorzystamy.

Dla ilustracji prostej graficznej procedury rekurencyjnej użyjemy procedury rysującej linię przerywaną. Jest ona oczywiście bardzo nieefektywna i do wymagających obliczeniowo zadań się nie nadaje, ale dydaktycznie powinna być wystarczająca.

Wynikiem działania programu będą czarne kropki naniesione wzdłuż dowolnego odcinka prostej. Ich gęstość może być różna. Na obrazki limit gęstości wynosi 10. Żółte tło pod kropkami stanowi "kontrolę" narysowaną zwykłą funkcją line()  Processingu.

Moglibyśmy te kropki oczywiście narysować też za pomocą pętli. Większość algorytmów rekurencyjnych da się zmienić na klasyczne, choć zapis rekurencyjny jest zazwyczaj dużo prostszy.
Oto kompletny program:


Funkcja setup() służy nam jak zwykle do ustawień, oraz do pierwszego wywołania naszej rekurencyjnej funkcji bline() (linia 12.) i narysowania kontrolnej linii klasycznym algorytmem (linia 11.). Funkcji draw() nie implementujemy bo jest w tym teście niepotrzebna.

Sama funkcja jest dosyć prosta. Najpierw sprawdzamy czy zadany odcinek jest wystarczająco długi żebyśmy chcieli postawić w nim kropkę (linie 17-20). Długość liczymy po prostu jako odległość Euklidesa między punktami.
Potem obliczamy współrzędne punktu leżącego pośrodku odcinka wyznaczonego przez parametry wywołania. Kolejność dalszych operacji jest dowolna. U mnie najpierw następują rekurencyjne wywołania dla obu połówek odcinka, a potem dopiero zaznaczenie punktu środkowego za pomocą point(), ale równie dobrze można zrobić odwrotnie.
Każde zatem wywołanie rysuje jeden punkt i próbuje narysować kolejne używając wywołania tej samej funkcji. Za zakończenie tego procesu odpowiada zmienna limit (linia 4.)

Jeśli zrozumiecie jak to działa, kolejne programy, rysujące znane fraktale będą dla was dużo bardziej zrozumiałe.

Implementacja komórkowa modelu SIR

 Zaczniemy od NAJPROSTSZEJ WERSJI MODELU gdzie CHOROBA JEST BARDZO KRÓTKA i BARDZO MAŁO ZARAŹLIWA. Formalnie będzie to dwuwymiarowy, probabilistyczny (kroki MC) automat komórkowy z regułą SIR.

Setup odpowiada za zasiewanie tablicy z zadaną gęstością początkową zdrowymi komórkami, oraz jedną pojedynczą komórką zarażoną na środku.

Procedura draw() odpowiada za wizualizacje, i za zmianę stanu modelu. Zaczynamy od wizualizacji bo jest ona po prostu odziedziczona po poprzednich automatach komórkowych.

...

Ciąg dalszy w postaci PDF bo kopiowanie z Google docs na Google blogera okazuje się całkiem nie działać :-D 

Udostępnienie pierwszych rozdziałów książki o processingu na okoliczność epidemii koronawirusa

Zdecydowałem się udostępnić on line pierwszą część przygotowywanego skryptu (plik PDF), wraz z wcześniej już dostępnymi przykładami.
Jest to materiał przeznaczony dla osób, które jeszcze nigdy nie miały styczności z Processingiem, a może nawet nigdy jeszcze nie programowały.

Tak się śmiesznie złożyło, że to akurat 50 post na tym blogu 😋







Materiały dostępne są pod tym adresem:
https://github.com/borkowsk/sym4processing/tree/master/SimpleEdu

Skok do początku bloga! 

Skąd wziąć Processing?

SIR - Podstawowy model epidemii

Nazwa tego modelu to skrót od trzech stanów osoby zarażonej. S oznacza “susceptible” czyli „podatny”, I to “infected” czyli „zainfekowany/chory”, wreszcie R to “recovered” czyli “wyleczony” (i chwilowo odporny). Tą odporność możemy uznać za trwałą lub nietrwałą, przy czym z biologicznego punktu widzenia może to oznaczać dwie rzeczy:

1.     Zanik “pamięci immunologicznej” dla danego drobnoustroju, co raczej zdarza się w normalnych warunkach rzadko (choć niektóre “czynniki zakaźne” wymagają kilku kolejnych szczepień, żeby odporność była trwała)
2.     Mutacje drobnoustroju, powodującą że jego nowe szczepy uciekają przed odpornością nabytą już przez żywicieli. To znacznie częstszy przypadek, gdyż ewolucja bakterii, a zwłaszcza wirusów przebiega o kilka rzędów wielkości szybciej niż ewolucja człowieka.

Dla naszego prostego modelu mechanizm tego zaniku nie będzie jednak istotny. Bardzo ważne będą natomiast prawdopodobieństwa zarażenia (Infection), sposób wychodzenia zarażonych z populacji (wyzdrowienie, śmierć), i prawdopodobieństwo lub czas utraty odporności - o ile będziemy chcieli się tym zająć.

Ponieważ stany SIR możemy zakodować jako liczby całkowite, nasz model może być wykonany w konwencji probabilistycznego automatu komórkowego. Poniżej przedstawiłem bardzo ogólny algorytm. Występuje tam słowo “sieć”, ale nie przejmujcie się tym. Automat komórkowy to też rodzaj sieci - bardzo regularnej.

Zwróćcie uwagę że jeśli zamiast automatu synchronicznego użyjecie wersji Monte Carlo to krok uaktualnienia stanów automatu nie będzie poza wewnętrzną pętlą, tylko uaktualnienie będzie zachodzić po prostu w trakcie wykonywania pętli po losowych agentach. Pytanie też kiedy kończymy. Można do tego użyć jakiejś statystyki - np. Liczby chorych. Ale w Processingu możemy też kończyć po prostu gdy uznamy że już nic ciekawego się nie dzieje.

Macie wybór, jeśli chodzi o sposób uaktualniania modelu. Sugeruję jednak, żeby komórki wybierać metodą Monte Carlo. To bardziej realistyczne. Istoty żywe rzadko działają synchronicznie, a jeśli to robią, to dużym nakładem sił, używając odpowiednich mechanizmów synchronizacyjnych.

Liczba interakcji z sąsiadami komórki automatu może być różna - to dobry parametr modelu. Interakcja polega na „przekazaniu wirusa”, co jest możliwe tylko między aktualnie chorym, a aktualnie zdrowym osobnikiem. Reszta interakcji z punktu widzenia modelu jest „bezpłodna”.
Początkowy przyjmiemy dla ułatwienia że choroba trwa około jeden dzień, czyli do następnego wylosowania agenta.
Musimy mieć jednak “z tyłu głowy”, że czas trwania infekcji może być bardzo różny, więc powinniśmy mieć możliwość odliczania upływu czasu od początku infekcji agenta.

Upływ czasu może polegać na zmianie stanu komórki na liczbę dni od początku choroby i wreszcie zmianie stanu komórki chorej na stan odporności, po upływie zadanej liczby dni. To zgodnie z zasadą, że “katar leczony trwa siedem dni, a nie leczony tydzień”.

Alternatywnie możemy też przyjąć, nieco nierealistycznie, że w każdym dniu choroby mamy pewne prawdopodobieństwo wyleczenia (albo śmierci!) i wtedy czas trwania choroby będzie zmienny.

Teraz pomyślcie sami…

Może uda wam się zaimplementować model, zanim opublikuje moje rozwiązanie.

CDN

Wstęp do modelu epidemii

“W języku potocznym termin epidemia używany jest jako synonim masowych zachorowań wywołanych chorobami zakaźnymi. Często definiuje się ją jako wystąpienie na danym obszarze zakażeń lub zachorowań na chorobę zakaźną w liczbie wyraźnie większej niż we wcześniejszym okresie albo wystąpienie zakażeń lub chorób zakaźnych dotychczas niewystępujących. Przypadki globalnych epidemii nazywa się pandemią.”

Oto kilka przykłady najważniejszych chorób epidemicznych (i pandemicznych):

• grypy
• grypa hiszpanka (1918-1919) – ponad 50 mln ofiar śmiertelnych na całym świecie
• grypa azjatycka (1957) – ok. 1 mln ofiar śmiertelnych na całym świecie
• grypa Hong-Kong (1968) – ok. 1 mln ofiar śmiertelnych na całym świecie
• Pandemia grypy A/H1N1 (od 11 czerwca 2009) - ok. 12799 ofiar na całym świecie

• AIDS – masowe zachorowania; zwłaszcza na kontynencie afrykańskim (wszystko od początku rozdziału do tego miejsca zaczerpnięte z tekstu “Modele epidemii“ ). Epidemia ta jest o tyle nietypowa, że wirus HIV bezpośrednio atakuje komórki układu odporności człowieka, upośledzające jego odpowiedź immunologiczną, a co więcej jest tzw. “retrowirusem”, co oznacza, że kopia jego kodu genetycznego jest włączana do DNA komórki, więc wirus ginie tylko wraz z zakażoną komórką, a jego produkcja może być tak niewielka, że zakażone komórki są dla układu immunologicznego nieodróżnialne od zdrowych.
• Koronawirusy - SARS, MERS, SARS-2 czyli COVID-19
• Stare choroby epidemiczne dorosłych, w większości zwalczone już higieną, szczepionkami i/lub antybiotykami: dżuma, czarna ospa (ostatni raz w Polsce w 1963 we Wrocławiu), cholera, kiła, gruźlica i trąd 
• Opanowane choroby epidemiczne dzieci: polio, płonica (szkarlatyna), błonica (krup), krztusiec (koklusz), oraz jeszcze nie opanowane, mimo istnienia szczepionki: odra, świnka i różyczka.
• Ospa wietrzna - jedna z bardziej zaraźliwych chorób wirusowych, ale na szczęście nie obarczona śmiertelnością. Chorują zarówno dzieci jak i dorośli, przy czym dorośli ciężej.
• Chorobami epidemicznymi są też “katary”, czyli “nieżyty nosa” zwane też “przeziębieniami”. Wywołuje je wiele szczepów wirusów, które ze względu na długą koewolucję z człowiekiem nie są już niebezpieczne dla ludzi z normalnym systemem odpornościowym. W większości przypadków za powstanie kataru wirusowego odpowiadają rhinowirusy, wirusy paragrypy, wirus grypy i adenowirusy. Wielość wirusów wywołujących “przeziębienie”, ich względna nieszkodliwość i szybkie mutacje powodują, że przygotowanie szczepionek przeciw nim jest uznawane za nieopłacalne czy wręcz niewykonalne.

Różnorodne modele epidemii to jedna z ważniejszych użytkowo klas modeli matematycznych i komputerowych modeli symulacyjnych. Różnorodne modele epidemii chorób zakaźnych stosowane od lat w epidemiologii - niekiedy z niezłymi skutkami. Ostatnio coraz częściej są to modele oparte na sieciach społecznych – istotne szczególnie dla epidemii grypy, AIDS czy SARS (tym tematem zajmiemy się później). Zdarzają się także bardzo złożone, przypominające gry w SIMSy, modele epidemii w konkretnych miastach (np. Model grypy w Los Angeles), coś nieco zbliżonego możemy jeszcze zrobić ćwicząc w następnym rozdziale model epidemii w konwencji ABM.

EPIDEMIA jest także głównym modelem rozprzestrzeniania się informacji i innowacji w społeczeństwie, chociaż to nie do końca słuszne, i do czego też powinniśmy kiedyś wrócić.

CD w następnym wpisie.