Co jakiś czas wertując różne nowości i ciekawostki ze świata nauki natrafia się na coś, co pachnie technologią przyszłości. Nie takiej za 50 czy sto lat. Takiej za 5 albo 10. Ostatnio mój kandydat numer jeden to technika tzw. compressed sensing rozwijana przez różne grupy zajmujace się przetwarzaniem sygnałów, głównie w USA, wsparte matematycznie przez taką sławę jak Terence Tao.
Zastosowania compressed sensing, które autorzy najczęściej podają, wiążą sie głównie z akwizycją i kompresowaniem obrazów, choć zastosowania potencjalne idą znacznie dalej. Postaram się w trzech słowach objaśnić co na razie z tego rozumiem.
Compreessed sensing jak wszystko co ma w nazwie "compressed" opiera sie na pewnej redundancji, czyli nadmiarowości w sygnale jakim w naszym przykładzie jest obraz. W klasycznym kodowaniu stratnym proces z grubsza wygląda tak:
(1) najpierw zbieramy dość dokładną informację o sygnale. Dokładność przekłada się zwykle na częstość próbkowania - na przykład w przypadku obrazu w aparacie cyfrowym na ilość elementów czułych w matrycy. Dostajemy pewien wektor w bazie, której każdy element przedstawia jeden piksel. Taka baza to zbiór wektorów postaci:
em,n(t,k) = 1 gdy t = m, k = n i 0 w innym wypadku.
W tej bazie obraz ma M na N pikseli ma przedstawienie:
OBRAZ = a1,1 * e1,1+...+aM,N*eM,N
gdzie am,n oznacza poziom jasności piksela. W tej bazie zwykle większość ai,j jest sporych i nie możnaby łatwo ograniczyć się do części z nich by reprezentować obraz.
(2) Potem dokonujemy transformaty, czyli wyliczamy przedstawienie tego wektora w bazie transformaty.
W przypadku dyskretnej transformaty Fouriera będzie to baza postaci
Fm,n(t, k) = exp(2*pi*i*(t*m/M + n*k/N)).
W tej bazie, nasz wektor będzie miał przedstawienie:
OBRAZ = b1,1 * F1,1+...bM,N*FM,N.
Tu, zwykle okazuje się, że jest lepiej i pewna niewielka część współczynników dominuje 1. Oczywiście możemy używać innych baz: np falek (wavelet) itp.
(3) Dokonujemy pewnych uproszczeń na sygnale korzystając z tej jego miłej cechy po przedstawieniu w bazie transformaty o której wspomniałem powyżej i dostajemy
OBRAZ' = b1,1' * F1,1+ ...bM,N' *FM,N
gdzie współczynniki primowane są bliskie nieprimowanych ale wiele z nich jest po prostu zerem. Wektor OBRAZ' jest bliski wektorowi OBRAZ.
(4) Na drugą stronę linii trzeba więc przekazać (względnie schować do pliku) indeksy i ich wartości tych niezerowych współczynników primowanych
(5) Odtwarzający (odpakowujący) odtwarza z tego co zapisane w punkcie (4) OBRAZ'.
Na ile dobrze to działa (modulo szczegóły techniczne, konkretne transformaty itp. bo zasada jest ta sama) możemy oglądać codziennie przeglądając obrazki na stronach WWW czy oglądając film na DVD.
A teraz wyobraźmy sobie, że nie musimy martwić się przekazywaniem informacji o tym podzbiorze ani o wartościach współczynników. Że zamiast mierzyć wszystkie piksele w kroku 1 mierzymy jedynie ich niewielką ale znaną część, że w ogóle pomijamy krok 2 i krok 3, i przesyłamy tylko wyniki tego pomiaru. Najpierw zalety: postępując w ten sposób mamy:
- mierzenie z kroku 1 staje się tańsze (bo mniej mamy punktów pomiarowych - np. w aparacie zamiast 5 mpx mamy tylko 1 mpx).
- pomijamy niezbyt może kosztowny w epoce FFT, ale mimo wszystko niedarmowy krok 2
- przesyłamy tylko wyniki pomiarów a nie dbmy o przesyłanie indeksów
- wciąż mamy sygnał skompresowany, bo choć przesyłamy wymniki pierwotnego pomiaru, to jest ich istotnie mniej niż w oryginalnym problemie
No dobrze: ale tym sposobem przesłaliśmy znacznie mniej informacji. Mniej jej wydobyliśmy z sygnału (mniej próbek) i nie dokonaliśmy żadnej analizy by wydobyć najcenniejszą jej część. Co zatem zyskaliśmy powyżej tracimy w postaci istotnego zaniku informacji. Nie ma darmowych obiadów... A jednak...
Przy pewnych założeniach, które wkrótce ostrożnie wypowiem (pamiętajcie, piszę co na razie sam z tego rozumiem) taka magia może mieć miejsce. Otóż:
Pomysł compressed sensing polega na tym, że jeżeli wiemy coś o sygnale ponad to co przesyła nam nadawca to coś może nam dać ową brakującą informację, której nikt nam nie przesłał i pozwolić na lepszą rekonstrukcję sygnału2 Co to za magiczna wiedza ? Pisałem trochę wyżej, że kompresja się uda jeżeli sygnał będzie kombinacją liniową niewielu wektorów bazy transformaty. Zatem, jeżeli mamy dobrze dobraną do klasy sygnałów bazę i wiemy że sygnały z klasy którą rozważamy mają w niej przedstawienia rzadkie, możemy po stronie odbiorcy zapytać: jaki sygnał będący kombinacją liniową niewielu wektorów bazy transformaty da nam w bazie pomiarowej nasz wynik?
Okazuje się, że odpowiadając na to pytanie w wielu przypadkach jesteśmy w stanie zrekonstruować rzeczywisty sygnał, który tak niechlujnie pomierzyliśmy. W jeszcze większej ilości przypadków jesteśmy w stanie odtworzyć sygnał bliski temu wyjściowemu. Problem: jak to zrobić?
Sposób jest taki: sprowadzić zagadnienie do problemu optymalizacji. Więzy, czyli ograniczenia na sygnał zadane są przez początkowy pomiar. Jeżeli wektory pomiarowe oznaczymy przez e1,...,eK a wyniki naszego pomiaru (a więc współczynniki w rozkładzie rzutu wektora OBRAZ na podprzestrzeń generowaną zbiór pomiarowy) przez a1,...,aK ograniczenia na poszukiwany sygnał X dają się zapisać jako:
<e1|X>=a1, <e2|X>=a2,...<eK|X>=aK.
Teraz drugi warunek na X, który pozwoli nam wybrać jeden wektor z tej podprzestrzeni. Złym, choć naturalnie narzucającym się sposobem jest poszukiwać wprost wektora którego przedstawienie będzie najrzadsze w bazie transformaty. Złym bo prowadzącym do olbrzymiej, niewykonalnej w praktyce - ilości obliczeń. Pomysł wieć jest taki, żeby zminimalizować pewną normę na przstrzeni sygnału. Okazuje się jednak, że minimalizując (znowu narzucającą się) normę euklidesową | |2 na ogół dochodzimy do wektora, który nie ma przedstawienia rzadkiego w bazie transformaty. Rozsądnym kompromisem pomiędzy obydwoma podejściami jest minimalizacja normy | |1 powiązanej z bazą tranformaty
F1,1, ..., FM,N
tzn normy takiej, że:
|b1,1 * F1,1+ ...bM,N *FM,N|1 = |b1,1|+...+|bM,N|
Taki problem jest zagadnieniem klasycznej optymalizacji wypukłej i sposoby jego rozwiązywania są dobrze znane.
Są dwa wybory, których trzeba tu dokonać. Pierwszy to - i jak mawiają Niemcy: hier liegt der hund begraben - wybór bazy transformaty. To ona musi być dobrana do klasy sygnału.
Drugi to wybór zbioru pomiarowego. Okazuje się, że rozmieszczenie wektorów którymi mierzymy sygnał "większość" jest dobra, tzn. można owe wektory wybrać praktycznie losowo. Natomiast ich ilość - aby dostać dobrą rekonstrukcję sygnału musi być rzędu A*log(B) gdzie A to rzadkość sygnału (a więć ilość elementów o niezerowych współczynnikach w przedstawieniu sygnału w bazie) a B to rozmiar tej bazy.
Podobno przykłady pokazują, że teoretyczne ograniczenia w poprzednim paragrafie w praktyce można jeszcze proprawić. Czyli jeśli empiria pokazuje, że jeśli mamy dobrą bazę, to sygnały spotykane w codziennym życiu nawet przy mniejszej ilości pomiarów dają się nieźle zrekonstruować.
Wydaje się, że wielki jest potencjał tych metod. Zarówno do przesyłania i transmisji sygnałów, jak i do rekonstrukcji - np. w obrazowaniu medycznym (choćby tomografia), itd. Zasosowanie do innych sygnałów niż obrazy - np mowy też może być ciekawe. Znowu przesyłanie jest ok, ale jeszcze ciekawsza może być rekonstrukcja z bardzo słabego albo silnie zniekształconego sygnału. Wydaje się, że od specyficznych zastosowań, np. obrazy twarzy itd. itd. można dobrać doskonale pasujące bazy i ich zastosowanie może dać ogromne, nieosiągalne dziś poziomy kompresji. Wydaje się też, że metoda może dać niezwykle tanie i energooszczędne a dokładnie obrazujące czujniki, kamery itp.
Słowem - matematyka w służbie ludzkości. Tak, stanowczo - jeśli chcecie zostać guru telekomunikacji, przetwarzania sygnałów itd. za lat 5-10 uczcie się o compressed sensing już dziś.
1OK. W rzeczywistości wystarczy nam że sprowadzimy do takiego przedstawienia w bazie, które dobrze się pakuje kompresją bezstratną. "Rzadkość" przedstawienia (a więc duża ilość współczynników zerowych w przedstawieniu w bazie) daje możliwość dobrego upakowania. Dla dyskusji compressed sensing pozostanę przy tej cesze.
2Zupełnie jak paleontolog który z fragmentów kości dinozaura jest w
stanie zrekonstruować zwierzę, ponieważ wie, że rekonstruuje dinozaura.
Pokazywanie postów oznaczonych etykietą algorytmy. Pokaż wszystkie posty
Pokazywanie postów oznaczonych etykietą algorytmy. Pokaż wszystkie posty
2008-07-14
W słońcu i w deszczu
Raz za oknem żar. Rekordowe temperatury. Organizm traci wodę. Potem odmiana. Ulewa, burza. Potem 15 stopni za oknem. Klimat umiarkowany, nie ma co...
W takich okolicznościach przyrody zwolniłem z lekturami. Diogenes Laertios i jego plotkarskie opowiesci o greckich perwersjach umysłowych powędrował z porotem na półkę z zakładką włożoną gdzieś w jednej czwartej grubości książki. Prz łóżku wala się - bo wezbrał we mnie apetyt na jakiś wielki epicki kawałek - drugi już tom "Nędzników" Wiktora Hugo. Wielka literatura w starym dobrym stylu.
Poczta, z przygodami dostarczyła mi dwie książeczki, które korzystając z przyjemnego dla polskiego konsumenta kursu dolara kupiłem wysyłkowo w Amazonie. Bawię się językiem Haskell (jedna z nich jego m.in. dotyczy) odkrywając kolejne więzi między programowaniem, matematyką i resztą świata.
W moim prywatnym piekiełku, po lekturze kilku prac i wertując kolejną amazonową książkę, jakby się trochę przejaśnia. Ależ byłem głupi formułując w naprędce i na bazie słabej intuicji moje małe hipotezy (tu)! Sprawa jest, jak to w życiu bywa, znacznie bardziej tajemnicza i głęboka. Jak pozbieram myśli do kupy, i zsyntetyzuję to co dotychczas na ten temat przeczytałem, to pewnie coś na ten temat napiszę i na blogu. W każdym razie związkami między regularnościami i pewnymi formami "automatyzmu" w różnych typach przedstawień liczb matematycy zajmują się od dawna i sporo na ten temat wiadomo a jeszcze więcej, jak można się domyślić, nie wiadomo.
Przy okazji drobnych studiów nad tym tematem, wróciłem do powiązanych z nim spraw, którymi trochę zajmowałem się w zeszłym roku: koalgebry itd. Stąd już niedaleko do innych konstrukcji opartych na teorii kategorii w tym i monad więc z powrotem do Haskella i jego wysoce zmatematyzowanych abstrakcji. Takie to wiry, szumy zlepy i ciągi tego lata ...
Z innej, ale podobnej beczki: Ale się czasem trafia uroczy kawałek matematyki!
Kilka tygodni temu na arxiv pojawiła się praca australijskiego matematyka N.J.Wildbergera pt. "Pell's equation without irrational numbers". Praca jest krótka, elementarna (poza szkolną matematykę wychodzi chyba tylko pojęcie macierzy: ich mnożenia i wyznacznika, ale w superprostych przypadkach) i prosta, tj. dowody są bardzo klarowne. W sam raz na niecałą godzinę czytania.
Przypominam równanie Pella:
x^2-D*y^2 = 1
gdzie x i y to szukane a D > 0 jest liczbą naturalną niebędącą kwadratem. Chcemy równanie to rozwiązywać w liczbach naturalnych (>0).
Algorytm klasyczny (nie wiem kto go podał jako pierwszy: Lagrange ?) polega na rozwijaniu pierwiastka kwadratowego z D do ułamka łańcuchowego .Dowodzi się, że takie rozwinięcie jest okresowe i bierze się odpowiedni n-ty redukt gdzie n jest funkcją długości okresu. Jaką funkcją: szczerze mówiąc nie pamiętam teraz, ale to łatwo znaleźć na sieci.
Autor podaje algorytm rozwiązywania równania Pella odmienny od tego algorytmu. Postaram się tu pokrótce go przedstawić i mam nadzieję, że niczego nie pomieszam:
Oznaczenie: Przez X^T gdzie X jest macierzą, rozumiem macierz transponowaną do X (tj taką, której wiersze odpowiadają kolumnom X).
Wychodzimy od macierzy:
|1 0|
A = | |
|0 -D|
gdzie D to owo D z równania Pella. Rozważamy też macierz:
|1 1|
R = | |
|0 1|
Konstruujemy ciąg macierzy B_0, ... w taki sposób, że B_0 = R^T lub R, tak, by macierz B_0^T*A*B_0 miała własność: element w lewym górnym rogu był większy od zera a element w prawym dolnym rogu był mniejszy od zera. Dowodzi się, że można wybrać jednoznacznie między T i R^T.
Potem, indukcyjnie: mając zdefiniowane B_n, definiujemy B_(n+1) = B_n*R lub B_n*R^T, tak by B_(n+1)^T*A*B_(n+1) miała wspomnaną wyżej własność: element w lewym górnym rogu był większy od zera a element w prawym dolnym rogu był mniejszy od zera. Ponownie dowodzi się, że w każdym kroku można wybrać jednoznacznie między T i R^T.
Dowodzi się, że dla pewnego n, macierz B_n z tego ciągu ma własność B_n^T*A*B_n = A. Pierwsza kolumna macierzy B_n wyznacza wówczas rowziązanie równania Pella.
Niestety autor nie dowodzi, że wynikiem działania algorytmu jest najmniejsze rozwiązanie. Ja zamierzam się sprawdzić w ustaleniu tego.
Algorytm zaimplementuję, oczywiscie w Haskellu i obiecuję przedstawić tu program.
W ogóle do Haskella będę wracał, bo to naprawdę fascynujący język, zmuszający do zmiany sposobu myślenia. Poza tym jest bardzo sexy i gdybym nie był żonaty podrywał bym na niego dziewczyny.
W takich okolicznościach przyrody zwolniłem z lekturami. Diogenes Laertios i jego plotkarskie opowiesci o greckich perwersjach umysłowych powędrował z porotem na półkę z zakładką włożoną gdzieś w jednej czwartej grubości książki. Prz łóżku wala się - bo wezbrał we mnie apetyt na jakiś wielki epicki kawałek - drugi już tom "Nędzników" Wiktora Hugo. Wielka literatura w starym dobrym stylu.
Poczta, z przygodami dostarczyła mi dwie książeczki, które korzystając z przyjemnego dla polskiego konsumenta kursu dolara kupiłem wysyłkowo w Amazonie. Bawię się językiem Haskell (jedna z nich jego m.in. dotyczy) odkrywając kolejne więzi między programowaniem, matematyką i resztą świata.
W moim prywatnym piekiełku, po lekturze kilku prac i wertując kolejną amazonową książkę, jakby się trochę przejaśnia. Ależ byłem głupi formułując w naprędce i na bazie słabej intuicji moje małe hipotezy (tu)! Sprawa jest, jak to w życiu bywa, znacznie bardziej tajemnicza i głęboka. Jak pozbieram myśli do kupy, i zsyntetyzuję to co dotychczas na ten temat przeczytałem, to pewnie coś na ten temat napiszę i na blogu. W każdym razie związkami między regularnościami i pewnymi formami "automatyzmu" w różnych typach przedstawień liczb matematycy zajmują się od dawna i sporo na ten temat wiadomo a jeszcze więcej, jak można się domyślić, nie wiadomo.
Przy okazji drobnych studiów nad tym tematem, wróciłem do powiązanych z nim spraw, którymi trochę zajmowałem się w zeszłym roku: koalgebry itd. Stąd już niedaleko do innych konstrukcji opartych na teorii kategorii w tym i monad więc z powrotem do Haskella i jego wysoce zmatematyzowanych abstrakcji. Takie to wiry, szumy zlepy i ciągi tego lata ...
Z innej, ale podobnej beczki: Ale się czasem trafia uroczy kawałek matematyki!
Kilka tygodni temu na arxiv pojawiła się praca australijskiego matematyka N.J.Wildbergera pt. "Pell's equation without irrational numbers". Praca jest krótka, elementarna (poza szkolną matematykę wychodzi chyba tylko pojęcie macierzy: ich mnożenia i wyznacznika, ale w superprostych przypadkach) i prosta, tj. dowody są bardzo klarowne. W sam raz na niecałą godzinę czytania.
Przypominam równanie Pella:
x^2-D*y^2 = 1
gdzie x i y to szukane a D > 0 jest liczbą naturalną niebędącą kwadratem. Chcemy równanie to rozwiązywać w liczbach naturalnych (>0).
Algorytm klasyczny (nie wiem kto go podał jako pierwszy: Lagrange ?) polega na rozwijaniu pierwiastka kwadratowego z D do ułamka łańcuchowego .Dowodzi się, że takie rozwinięcie jest okresowe i bierze się odpowiedni n-ty redukt gdzie n jest funkcją długości okresu. Jaką funkcją: szczerze mówiąc nie pamiętam teraz, ale to łatwo znaleźć na sieci.
Autor podaje algorytm rozwiązywania równania Pella odmienny od tego algorytmu. Postaram się tu pokrótce go przedstawić i mam nadzieję, że niczego nie pomieszam:
Oznaczenie: Przez X^T gdzie X jest macierzą, rozumiem macierz transponowaną do X (tj taką, której wiersze odpowiadają kolumnom X).
Wychodzimy od macierzy:
|1 0|
A = | |
|0 -D|
gdzie D to owo D z równania Pella. Rozważamy też macierz:
|1 1|
R = | |
|0 1|
Konstruujemy ciąg macierzy B_0, ... w taki sposób, że B_0 = R^T lub R, tak, by macierz B_0^T*A*B_0 miała własność: element w lewym górnym rogu był większy od zera a element w prawym dolnym rogu był mniejszy od zera. Dowodzi się, że można wybrać jednoznacznie między T i R^T.
Potem, indukcyjnie: mając zdefiniowane B_n, definiujemy B_(n+1) = B_n*R lub B_n*R^T, tak by B_(n+1)^T*A*B_(n+1) miała wspomnaną wyżej własność: element w lewym górnym rogu był większy od zera a element w prawym dolnym rogu był mniejszy od zera. Ponownie dowodzi się, że w każdym kroku można wybrać jednoznacznie między T i R^T.
Dowodzi się, że dla pewnego n, macierz B_n z tego ciągu ma własność B_n^T*A*B_n = A. Pierwsza kolumna macierzy B_n wyznacza wówczas rowziązanie równania Pella.
Niestety autor nie dowodzi, że wynikiem działania algorytmu jest najmniejsze rozwiązanie. Ja zamierzam się sprawdzić w ustaleniu tego.
Algorytm zaimplementuję, oczywiscie w Haskellu i obiecuję przedstawić tu program.
W ogóle do Haskella będę wracał, bo to naprawdę fascynujący język, zmuszający do zmiany sposobu myślenia. Poza tym jest bardzo sexy i gdybym nie był żonaty podrywał bym na niego dziewczyny.
2008-03-03
Odkurzone, wygrzebane
Czasem zakopane w starych czasopismach, pożółkłych książkach czy innych tego typu zapomninych miejscach do których nikt nie zagląda leżą ciekawe, potencjalnie pożyteczne i eleganckie perełki. Bywa, że odkrywane po wielokroć na nowo stają się elementem folkloru i nikt w zasadzie już nie pamięta kiedy, jak i po co je odkryto po raz pierwszy.
Postanowiłem od czasu do czasu, kiedy natknę się na coś godnego uwagi zanotować to w tym blogu - żeby nacieszyć oko odkurzonym drobiażdżkiem i licząc, że może komuś się przyda...
Dziś następujący problem:
Niech A będzie nieskończonym podzbiorem zbioru liczb naturalnych N (bez 0 dla uniknięcia niepotrzebnych subtelności w rozważaniach o indeksach). Załóżmy, że mamy daną fukcję, COUNT: N->N która dla liczby naturlanej n daje informację ile liczb w zbiorze A jest mniejszych bądź równych n:
COUNT(n) = #{x \in A | x <= n}
poszukujemy algorytmu pozwalającego dla zadanej liczby m wyznaczyć m-ty element zbioru A.
Rozwiązanie jest następujące (użyję c-podobnego pseudokodu):
ORD(m)
{
retval = m;
x = COUNT(retval);
while(x != m)
{
retval += (m - x);
x = COUNT(retval);
}
return retval;
}
miłośnikom dobrej zabawy polecam udowodnienie poprawności algorytmu używając indukcji matematycznej.
"Intuicjonistom", którzy lubią czuć skąd się wziął pomysł, może spodoba się następujące rozumowanie:
Pierwszy strzał to najmniejsza liczba dla której fukcja COUNT ma w ogóle szansę równać się m czyli po prostu m.
Trafiony - świetnie, szukaną liczbą jest właśnie m. Jeżeli nie trafiony, to znaczy, że COUNT(m) < m. Kolejną najmniejszą liczbą m_2 dla której możliwe będzie, że COUNT(m_2)=m jest oczywiście liczba większa od m o tyle ile COUNT(m) zabrakło do m czyli (m-COUNT(m)). Zatem następny strzał to m_2=m+(m-COUNT(m)).
Sprawdzamy więc ile wynosi COUNT(m_2). Jeżeli m to mamy swoją liczbę. Jeżeli nie, to powtarzamy "strzelanie" opierając się na tym samym rozumowaniu i dostajemy m_3 = m_2+(m-COUNT(m_2)) itd. Aż do - murowanego - skutku (pamiętamy - A jest nieskończone!).
Postanowiłem od czasu do czasu, kiedy natknę się na coś godnego uwagi zanotować to w tym blogu - żeby nacieszyć oko odkurzonym drobiażdżkiem i licząc, że może komuś się przyda...
Dziś następujący problem:
Niech A będzie nieskończonym podzbiorem zbioru liczb naturalnych N (bez 0 dla uniknięcia niepotrzebnych subtelności w rozważaniach o indeksach). Załóżmy, że mamy daną fukcję, COUNT: N->N która dla liczby naturlanej n daje informację ile liczb w zbiorze A jest mniejszych bądź równych n:
COUNT(n) = #{x \in A | x <= n}
poszukujemy algorytmu pozwalającego dla zadanej liczby m wyznaczyć m-ty element zbioru A.
Rozwiązanie jest następujące (użyję c-podobnego pseudokodu):
ORD(m)
{
retval = m;
x = COUNT(retval);
while(x != m)
{
retval += (m - x);
x = COUNT(retval);
}
return retval;
}
miłośnikom dobrej zabawy polecam udowodnienie poprawności algorytmu używając indukcji matematycznej.
"Intuicjonistom", którzy lubią czuć skąd się wziął pomysł, może spodoba się następujące rozumowanie:
Pierwszy strzał to najmniejsza liczba dla której fukcja COUNT ma w ogóle szansę równać się m czyli po prostu m.
Trafiony - świetnie, szukaną liczbą jest właśnie m. Jeżeli nie trafiony, to znaczy, że COUNT(m) < m. Kolejną najmniejszą liczbą m_2 dla której możliwe będzie, że COUNT(m_2)=m jest oczywiście liczba większa od m o tyle ile COUNT(m) zabrakło do m czyli (m-COUNT(m)). Zatem następny strzał to m_2=m+(m-COUNT(m)).
Sprawdzamy więc ile wynosi COUNT(m_2). Jeżeli m to mamy swoją liczbę. Jeżeli nie, to powtarzamy "strzelanie" opierając się na tym samym rozumowaniu i dostajemy m_3 = m_2+(m-COUNT(m_2)) itd. Aż do - murowanego - skutku (pamiętamy - A jest nieskończone!).
Subskrybuj:
Posty (Atom)
Posty
