01. Wstęp do matematyki - zajęcia wstępne

Treści kształcenia. Podczas tych zajęć student zapoznaje się z przeglądem tematów oraz zagadnień, z którymi będzie się stykał podczas zajęć z przedmiotu.

Efekty kształcenia. Zapoznanie się z przykładowymi problemami matematycznymi, które mają związek z informatyką. Student zapoznaje się z metodą problemową pracy nad zagadnieniami matematycznymi w informatyce.

Wstęp¶

Niniejszy plik jest pierwszym z trzydziestu scenariuszy zajęć przygotowanych na przedmiot Wstęp do matematyki na kierunku Informatyka na studiach inżynierskich.

Celem tego przedmiotu jest przekazanie studentom fundamentalnych pojęć z zakresu matematyki, które mają swoje odzwierciedlenie w pracy informatyka. Tematy te obejmują zagadnienia takie jak

• podstawy języka matematyki, w tym wysławianie pojęć matematycznych i ich właściwości w formie definicji oraz twierdzeń; przeprowadzanie formalnych rozumowań matematycznych (dowód)

• podstawy teorii zbiorów, operowania funkcjami

• arytmetyka liczb, w tym liczby całkowite, wymierne, rzeczywiste i zespolone

• pojęcie indukcji matematycznej, rekurencji i rekursji

• odwzorowania w matematyce - funkcje

• podstawowe zagadnienia z geometrii analitycznej

• ciągi liczbowe

• wielomiany

• metryki

Aby przybliżyć styl pracy na zajęciach i sposób wprowadzania zagadnień, poniżej został przygotowany wybór pięciu krótkich ćwiczeń do omówienia w ramach zajęć wstępnych.

1. O pierwiastku kwadratowym

2. Liczby Fibonacciego

3. Zagadka Hanoi

4. Tajemnicze obrazki

5. Gra w monety

O pierwiastku kwadratowym¶

W jaki sposób wyznaczyć 10 cyfr dziesiętnych liczby $\sqrt{2}$? A 100, 1000, 10000? Czy da się to zrobić szybko, np. w ciągu 1/10 sekundy?

Algorytm I:

$2,0 = 200/100$

$14^2 = 196<200<225=15^2$

$14^2/10^2 < 2,0<15^2/10^2$

$1,4<\sqrt{2}<1,5$

Jak znaleźć największy kwadrat niewiększy od 20000? Będzie to liczba niemniejsza niż 140 i niewiększa niż 150.

Zatem przeszukujemy zbiór liczb całkowitych $\{141,142,143,144,145,146,147,148,149\}$.

Jak? Najlepiej binarnie, czyli zaczynając w połowie, w tym przypadku

$145^2=21025$ (za dużo!)

Wybieramy więc element w połowie zbioru $\{141,142,143,144\}$

$142^2=20164$ (za dużo)

Ostatecznie

$141^2=19881$

Potrzeba zatem przeszukać w każdej iteracji następujące zbiory:

1. $\{11,\ldots 19\} \rightarrow 14$

2. $\{141,\ldots 149\} \rightarrow 141$

3. $\{1411,\ldots 1419\} \rightarrow 1414$

4. ...

Do przygotowania algorytmu potrzebujemy jeszcze procedurę, która dla zadanej liczby naturalnej $n$ znajduje największą liczbę $k$, której kwadrat $k^2$ jest niewiększy od $n$.

$k\leftarrow 1$

$sq\leftarrow 1$

while ($sq\leq n$)

$sq\leftarrow sq+2k+1$

$k\leftarrow k+1$

return $k-1$

Zauważmy, że w powyższej procedurze nie podnosimy żadnego elementu do kwadratu!

Możemy zatem przystąpić do zapisania procedury obliczania pierwiastka kwadratowego z wybranej liczby $x$. Procedura zwraca generator a=SzukPierw(x), który przy wywołaniu next(a) oblicza kolejne przybliżenie $\sqrt{x}$ przybliżone o kolejną cyfrę dziesiętną. Komenda zwraca liczby całkowite (cyfry liczby $\sqrt{x}$).

Interesujące pierwiastki¶

Wyznacz kilka przybliżeń pierwiastka kwadratowego z liczb

$99,9999,999999,99999999,\ldots$

Czy zauważasz interesującą regularność?

Podobnie przeanalizuj przybliżenia dziesiętne pierwiastków kwadratowych z liczb

• $1,123,12345,1234567,123456789,1234567891011,\ldots$

• $1,101,10001,1000001,100000001,\ldots$

Zastanów się, jakie interesujące ciągi liczbowe odpowiadałyby podanym powyżej, gdybyśmy obliczali pierwiastek kwadratowy w innej bazie pozycyjnej, np. binarnej.

Liczby Fibonacciego¶

Jednym z najczęściej wykorzystywanych algorytmów w obliczeniach na liczbach całkowitych jest obliczanie największego wspólnego dzielnika dwóch liczb całkowitych $m$ i $n$, oznaczanego jako $NWD(m,n)$ (ang. $GCD(m,n)$).

Największy wspólny dzielnik spełnia kilka prostych własności:

1. $NWD(0,n) = |n|$, gdy $n\neq0$.

2. $NWD(m,n)=NWD(n,m)$.

3. $NWD(m,n)=NWD(|m|,|n|)$.

oraz kluczową własność Euklidesa $NWD(m,n)=NWD(m,n-q\cdot m)$ dla dowolnej liczby całkowitej $q$.

Własności $1-3$ oraz własność Euklidesa pozwalają obliczyć największy wspólny dzielnik bez korzystania z faktoryzacji liczb na czynniki pierwsze!

W praktyce zatem otrzymujemy prosty program.

Traktując algorytm dzielenia z resztą jako jedną operację (sprawdź, że taki algorytm istotnie istnieje!), możemy obliczyć, ile kroków wymaganych jest do obliczenia NWD dwóch liczb. W szczególności interesuje nas najgorszy przypadek przebiegu tego algorytmu.

Wygenerujemy tablicę par liczb całkowitych $0 < a < b$ i zaobserwujemy, dla jakich najmniejszych par liczb $(a,b)$ po raz pierwszy algorytm wykonuje się w $k$ krokach.

Zatem najmniejsza para liczb $(a_k,b_k)$, dla której wykonanie algorytmu Euklidesa zajmuje $k$ kroków, spełnia (hipotetycznie) pewną ciekawą własność

$a_{k+1}=b_{k}$ oraz $a_{k}+b_{k} = b_{k+1}$

Łącząc obie równości, otrzymujemy relacje

$a_{k}+a_{k+1} = a_{k+2}$

oraz

$b_{k-1}+b_{k} = b_{k+1}$.

Dla pary $(0,1)$ algorytm wykonuje się w zero krokach (z definicji). Dla pary $(1,1)$ algorytm kończy się po 1 kroku. W ten sposób otrzymujemy zależność

$a_{0}=0$, $a_{1}=1$

oraz

$a_{k}+a_{k+1} = a_{k+2}$.

Zadanie

Sprawdź, że $NWD(a_{k},a_{k+1}) = 1$ dla dowolnego indeksu $k$. Ponadto uzasadnij, że algorytm Euklidesa potrzebuje $k$ kroków do obliczenia $NWD(a_{k},a_{k+1})$.

Jak szybko rosną liczby $a_k$ zadane powyższym wzorem?

Wykres przypomina szybko rosnącą funkcję. Czy jest to funkcja mniej więcej postaci $a^n$ dla pewnego $a>1$?

Ilorazy kolejnych wyrazów ciągu $a_k$ zdają się stabilizować na liczbie mniej więcej $1,6180339...$.

Ryzykowna hipoteza¶

Zatem ciąg liczb $a_k$ jest bardzo bliski ciągowi $0,447214\cdot (1,618034)^k$.

Co to znaczy bliski?

Hipoteza robocza:

Jeśli element $a_k$ byłby postaci $A\cdot b^k$, to wówczas, aby spełniać równanie $a_{k+2} = a_{k+1}+a_{k}$, potrzebowalibyśmy

Zakładając, że $A\neq 0$ oraz $b\neq 0$, otrzymujemy

Jakie są rozwiązania równania kwadratowego $b^2=b+1$?

Liczba $1/2\sqrt{5}+1/2$ to mniej więcej $1,618033...$. Z kolei liczba $-1/2\sqrt{5}+1/2$ to około $-0,61803...$. Wygląda na to, że nasza hipoteza nie jest pozbawiona sensu. Ale ile wynosi stała $A$?

Zauważ, że liczby $a_k$ są całkowite. Czy istnieje stała $A$ spełniająca dokładnie równość $A(1/2\sqrt{5} + 1/2)^k = a_k$? (odpowiedź: sprawdź, że nie może tak być!)

Zatem pozostaje inna opcja. Istnieją dwie stałe $A_1, A_2$ takie, że

$a_k = A_1 (1/2\sqrt{5} + 1/2)^k+A_2(-1/2\sqrt{5} + 1/2)^k$.

Zadanie:

Uzasadnij, że stała $A_1=-A_2=1/\sqrt{5}$ i równość powyżej zachodzi wówczas dla dowolnego $k\geq 0$.

Komentarz¶

Ciąg liczbowy $(a_k)$ określony wzorem powyżej nosi nazwę ciągu Fibonacciego od nazwiska Leonarda z Pizy zwanego Fibonaccim, który jako pierwszy omawiał własności tego ciągu w księdze Liber abaci w 1202 roku.

Formuła

nosi nazwę formuły Bineta od nazwiska Jacques’a Bineta, który podał ją w 1843 roku. Najwcześniejsza wzmianka tej formuły pochodzi z pracy Abrahama de Moivre’a z 1722 roku i była wielokrotnie odkrywana przez innych autorów.

Literatura:

• Binet, J. P. (1843). Mémoire sur l’intégration des équations linéaires aux différences finies, d’un ordre quelconque, à coefficients variables. Comptes Rendus hebdomadaires des séances de l’Académie des Sciences (Paris), 17, 559-567.

• Bernoulli, D. (1728). Comment. Acad. Sci. Petrop., 3, 85-100.

• Euler, L. (1765). Observationes analyticae. Novi commentarii academiae scientiarum imperialis Petropolitanae, 11, 124-143.

• de Moivre, A. (1730). Miscellanea analytica de seriebus et quadraturis. London.

• de Moivre, A. (1722). Philos. Trans., 32, 162-178.

Link do ciekawej dyskusji na ten temat.

Zagadka Hanoi¶

Matematyka to nauka o rozkładaniu skomplikowanych problemów na trywialne kroki. Tak mógłby wyglądać wstęp do każdego podręcznika matematycznego. Dla laika wydaje się to niemożliwym, patrząc na skomplikowane gmachy wiedzy abstrakcyjnej zbudowane przez matematyków. Z drugiej strony budowa katedry polega tak jak budowa wieży z kart na konsekwentnym łączeniu prostych elementów, aż do powstania finalnego dzieła.

W informatyce podejście do problemów polegające na ich rozłożeniu na prostsze podproblemy nosi nazwę ,,dziel i rządź’’ (ang. divide and conquer). Podejście to zaowocowało budową wspaniałych algorytmów takich jak algorytm Strassena do mnożenia macierzy czy algorytm Karacuby do mnożenia dowolnie dużych liczb całkowitych na komputerze, algorytmów sortowania, np. quicksort lub mergesort czy wreszcie rozwiązywania skomplikowanych łamigłówek matematycznych, np. problem wież Hanoi. Każdy z tych algorytmów ma pewien związek z zasadą indukcji matematycznej, o której będziemy się uczyli na jednych z kolejnych zajęć. W tym przykładzie przyjrzymy się w uproszczony sposób problemowi wież Hanoi i jak go rozwiązać metodą dziel i rządź.

Problem wież Hanoi¶

Wyobraźmy sobie, że mamy do dyspozycji trzy drewniane paliki. Na każdy z nich możemy nałożyć jeden z $n$ dostępnych klocków (o $n$ różnych szerokościach). Klocki możemy przekładać między palikami, ale tylko w ten sposób, aby klocek węższy był nakładany na klocek szerszy. Zakładamy, że na pusty palik można nałożyć klocek dowolnej szerokości.

Zadanie polega na zgodnym z regułami przełożeniu wszystkich $n$ klocków ułożonych od najszerszego do najwęższego z palika pierwszego na palik trzeci. Numerujemy paliki: 1 - palik lewy, 2 - palik środkowy oraz 3 - palik prawy.

Pytanie: w ilu krokach i czy w ogóle można rozwiązać to zadanie?

Idea dziel i rządź dla tego zadania polega na tym, aby zastanowić się, czy problem można rozwiązać, odwołując się do jego mniejszej wersji.

W przypadku, gdy mamy $n=1$ klocek, wówczas przełożenie go z pierwszego palika na trzeci odbywa się jednym legalnym ruchem.

Gdy liczba klocków wzrasta do $n=2$, wówczas najprostszy sposób rozwiązania polega na przełożeniu klocka z góry na palik środkowy, klocka z dołu na palik prawy, w końcu przekładamy klocek mniejszy z palika 2 na palik 3. I gotowe, w trzech krokach osiągnęliśmy cel.

Co dzieje się, gdy mamy $n=3$ klocki? Zastosujemy podejście abstrakcyjne. Wyobrażamy sobie, że klocek środkowy i górny stanowią całość, jeden superklocek, nazwijmy go $\alpha$. Klocek dolny oznaczmy $\beta$. Sprowadzamy zatem, zgodnie z zasadą dziel i rządź, zadanie do problemu dwóch klocków, $\alpha$ i $\beta$. Taki algorytm już znamy z poprzedniego kroku! Zatem odpowiednio:

1. Przekładamy $\alpha$ na palik 2.

2. Przekładamy $\beta$ na palik 3.

3. Przekładamy $\alpha$ na palik 3.

W jaki sposób przekładamy $\alpha$ na inny palik? Wykonujemy ciąg operacji podobny do algorytmu dla dwóch rzeczywistych klocków, traktując klocek $\beta$, jakby był elementem podłoża. I gotowe!

W ten sposób rozwiązujemy nasze zadanie dla $n=3$ w 7 krokach. Ile kroków zajmie nam rozwiązanie zadania dla $n=4$? A ile w ogólności?

Zobaczmy efekty wykonywania instrukcji przekładania klocków wież Hanoi na przykładzie wieży złożonej z czterech krążków.

Aplet graficzny - sprawdź samodzielnie, czy dobrze rozumiesz algorytm

Tajemnicze obrazki¶

Wyobraźmy sobie grę, w której podajemy dwie liczby, np. $\{0,1\}$ i następnie generujemy dla tych liczb przekształcenie, np. $x\mapsto x/2$, którym działamy na każdy element ze zbioru.

Następnie łączymy oryginalny zbiór z nowym zbiorem, w tym przypadku $\{0,1/2,1\}$.

W kolejnym kroku powtarzamy operację, ale już na nowym zbiorze. W efekcie w kolejnych krokach otrzymamy zbiory

$\{0,1\}$

$\{0,1/2,1\}$

$\{0,1/4,1/2,1\}$

$\ldots$

Czy istnieje ,,koniec’’ takiej gry? Jeśli tak, to jakie własności ma taki zbiór?

Przypadek powyżej sugeruje następującą odpowiedź:

$\{0,1,1/2,1/4,1/8,1/16,\ldots\}$

czyli 0 wraz z kolejnymi potęgami liczby $1/2$. Operacja, którą wykonywaliśmy na zbiorach, może być opisana następująco

$W(A) = A\cup f(A)$

gdzie $f(A)$ oznacza zbiór elementów z $A$ pomnożonych przez $1/2$. Symbol $\cup$ to połączenie (suma) dwóch zbiorów.

Jeśli przez $A_0$ oznaczymy zbiór $\{0,1\}$ oraz $A_i = W(A_{i-1})$, to zbiór, który otrzymujemy ``na końcu’', możemy oznaczyć $A_\infty = \{0,1,1/2,1/4,\ldots\}$. Jego własnością jest $A_\infty = W(A_\infty)$.

UWAGA: w pewnym ścisłym sensie (związanym np. z metryką Hausdorffa, czyli miarą odległości zbiorów) odwzorowanie $W$ ma punkt stały $A_\infty$, do którego nasz proces zbiega. Własności zbiorów podobnych do $A_\infty$ są tematem bardzo ciekawych badań, a odwzorowania podobne do $W$ (tzw. operatory Hutchinsona) są tematem badań w zakresie tzw. iterowanych systemów funkcji. Zbiór $A_\infty$ jest samopodobny (tutaj: przeskalowanie zbioru $A_\infty$ o połowę daje ten sam zbiór bez punktu 1 - $f(A_\infty) = A_\infty\setminus\{1\}$ ).

W niektórych zastosowaniach zbiory podobne do $A_\infty$ nazywamy fraktalami. W poniżej podanych kilku prostych przykładach zapoznasz się z przykładami fraktali, które powstają w wyniku zastosowania bardzo prostych operacji na płaszczyźnie.

Najpierw przygotujemy sobie kod do generowania naszych zbiorów punktów. Elementem startowym dla każdego przykładu będzie punkt $(0,0)$ na płaszczyźnie $\mathbb{R}^{2}$. Ten punkt stanowi zbiór $A_{0}$. Następnie podana będzie lista odwzorowań $f_i:\mathbb{R}^{2}\rightarrow\mathbb{R}^2$, które będą połączeniem obrotów ze skalowaniem i translacjami (patrz: operacje afiniczne ). Ważnym warunkiem jest, aby odwzorowania $f_i$ były kontrakcjami (co to znaczy - zobacz do wykładów o metrykach!). Nasza gra opierać się będzie na rysowaniu zbiorów

$W(A) = f_1(A)\cup \ldots f_i(A)\cup\ldots$

i odpowiednio $A_1=W(A_0), A_2=W(A_1),\ldots$

Zobaczymy na kilku przykładach, że kształt zbiorów $A_i$ ma interesujące własności, m.in. zobaczymy słynny trójkąt Sierpińskiego czy paproć Barnsley’a.

Literatura:

• Peitgen, Jurgens, Saupe, Chaos and Fractals. New Frontiers of Science, Second Edition, Springer 2004: Rozdział 5: ‘‘Encoding Images by Simple Transformations’’

• Barnsley, M. F. Fractals Everywhere, Academic Press, 1988

• Hutchinson, J. Fractals and self-similarity, Indiana University Mathematics Journal 30 (1981) 713-747

Hasła:

1. IFS = Iterated Function System (Barnsley); some nice examples here

2. MRCM = Multiple Reduction Copy Machine

Przykład 1: Trójkąt Sierpińskiego¶

Przykład bazuje na trzech odwzorowaniach. Jedno to podzielenie obu współrzędnych na pół, odwzorowanie $f_1(x,y) = (x/2,y/2)$ i dwóch pozostałych, które przesuwają punkt $f_1(x,y)$ o $(1/2,0)$ (operacja $f_2$) lub $(0,1/2)$ (operacja $f_3$).

Przykład 2: zmodyfikowany trójkąt Sierpińskiego¶

W tym przykładzie zmieniamy skalowanie do $1/3$. Efekt daje zbiór podobny do poprzedniego, ale pojawiają się łuki, których do tej pory nie było.

Przykład 3: liść klonowy¶

Kolejny przykład opiera się na czterech odwzorowaniach. Dla uwidocznienia skomplikowanej dynamicznej natury obrazka dodana została zmiana kolorów dla kolejnych narostów oraz zmiana wielkości punktów (najstarsze punkty są największe).

Przykład 4: paproć Barnsley’a¶

W ostatnim przykładzie zobaczymy obraz, który do złudzenia przypomina liść rośliny, np. paproci.

Gra w monety¶

Mamy grę: pierwszy gracz układa w rzędzie 5 monet 1 zł i 2 zł (wzorzec $x$) tak, aby drugi gracz nie widział tego wzorca. Drugi układa swój wzorzec (nazwijmy go $y$) 5 takich monet. Jeśli są takie same łańcuchy monet, to gracz drugi wygrywa, jeśli nie, to gracz pierwszy przekazuje informację o liczbie miejsc w obu łańcuchach, które się różnią $d(x,y)$ (liczymy w tym samym kierunku). Oczywiście liczba zero oznacza takie same łańcuchy.

• Czy zamiana ról graczy jest możliwa, tzn. d(x,y) = d(y,x)?

W pojedynczym ruchu gracz drugi może wymienić w swoim wzorcu dowolną monetę 1 zł na 2 zł lub odwrotnie. Ma więc 5 możliwości! Jeśli wymieni różniącą się monetę we wzorcach na poprawną, to liczba zmaleje o 1, a jeśli nie trafi i wprowadzi kolejną różnicę, to wzrośnie o 1.

1. Określić, ile maksymalnie ruchów powinno wystarczyć do wyrównania różnic pomiędzy wzorcami dla każdej z liczby k różnic pozycji (dla k ∈ {1,2,3,4, 5}).

2. Zaproponuj taką zmianę reguły podawania wartości d(x,y) (ale to nadal ma być liczba) tak, aby zwiększyć ilość przekazywanych informacji i przyspieszyć grę!

Komentarz:

Metryka Hamminga stosowana przy porównywaniu łańcuchów binarnych w informatyce. Proponowane ulepszenie polega na uwzględnieniu w liczbie pozycji, na której łańcuchy się różnią. Np. zamiast 1 przy różnicy na dowolnej pozycji liczyć $1/2^n$, gdzie $n$ jest numerem pozycji. Rozkładając wynik na potęgi dwójki, uzyskamy numery pozycji, w których są różnice (oczywiście inne propozycje też są możliwe...). Wymiana jest więc ograniczona do $k$ ruchów, gdzie $k$ jest liczbą różniących się pozycji.

Gdzie znajdzie zastosowanie? Np. porównywanie grafik bitowych, detekcja błędów itp.

Wykrywanie pozycji pięciu monet¶

W trakcie gry masz za zadanie odkrycie układu pięciu monet (nominały 1 i 2). Monety ułożone są w kolejności od lewej do prawej i mogą występować w dowolnej liczbie.

Program w każdym kroku podaje odległość Hamminga do sekretnego układu. W ilu krokach na pewno możesz zakończyć rozgrywkę?

Modyfikacja gry¶

W tym wariancie gry otrzymujesz w każdym kroku listę ustawień, które są w zadanej odległości od tajnego układu. Czy podpowiedzi skracają Twoją rozgrywkę?

Wariant z ważoną metryką Hamminga¶

W tej rozgrywce uzyskujesz informację o odległości od tajnego układu, która jest zadana ważoną metryką. Wagi rozróżniają pozycje. Jak szybko możesz zakończyć rozgrywkę, mając daną tak dokładną informację? Jak zmieni się sytuacja, gdy niektóre wagi będą równe?