Tu dygresja: studiowanie dokumentów opisujących standardy telekomunikacyjne ma w sobie coś z sztuki walki, coś z rozwiązywania rebusa i coś ze studiowania świętej księgi. Zatem: Środki retoryczne jakimi posługują się autorzy owych dzieł ograniczają się zwykle do nadużywania trybu rozkazującego ("X shall Y..." - "Zaprawdę powiadam Ci, X będzie Y..." ). Powtarzalność schematów zdań ukrywa nagłe zwroty akcji. Jakakolwiek motywacja działań bohaterów jest szczelnie zakryta przed czytelnikiem. Zrozumienie wymaga długotrwałych medytacji i skomplikowanych egzegez. Wrogiem jest montonia, nuda, nieuwaga. Piszący owe standardy, w końcu, często nadzwyczaj jednostronnie biorą sobie do serca uwagę Gaussa o "zwiezłości, cesze którą należy brać pod rozwagę tak bardzo jak to możliwe".
Szczególnym gatunkiem owej literatury, do których przynależy i przywołany przeze mnie dokument, są opisy standardów komunikacji bezprzewodowej. Kapryśna i ograniczona natura medium i nieustający głód szybkości, pojemności i niezawodności prowadzi do tworzenia skomplikowanych piętrowych konstrukcji, nad którymi władzę absolutną sprawują Oszczędność, Zapobiegliwość i Kompromis.
Wracając do mojej lektury, okazuje się, że aby zadość uczynić surowym prawom owych trzech władców nadzwyczaj często należy uciec się do fortelu a pomocnikiem jest matematyka. O jednym fortelu , na który się natknąłem opowiem, bo to proste, ciekawe i - przynajmniej dla mnie - zaskakujące. Istotę tego fortelu należy jednak dopiero wyłuskać z opisu. Rzecz podana została bowiem do wierzenia.
Pomedytujmy, nad następującymi wersetami (przy okazji będącymi typową próbką stylu):
Co się za tym kryje. Otóż, chodzi o metodę pozwalającą w możliwie najzwięźlejszy sposób przekazać informację o wybranym M-elementowym podzbiorze w uporządkowanym zbiorze N - elementowym. Zakładamy przy tym, że obie strony znają N i M.
Uwaga - w dalszym ciągu na oznaczenie symbolu Newtona przyjmę (NM) - oznacza "N po M". Stosuję też konwencję jak w artykule (tj. dla N <>NM) = 0).
Jak możnaby to zrobić? Pierwszy pomysł to wziąć N bitów i zapalić odpwiednie M z nich (stworzyć mapę bitową), następnie przesłać taką liczbę binarną. Ale, N może być duże i przesłać musielibyśmy wiele liczb. Ba, ten sposób pomija zupełnie informację, że M jest ustalone i potrzebuje więc zwykle [log2N]+1 (czasem tylko log2N) bitów ale wykorzystuje tylko (NM)/2N część owej przestrzeni możliwych map bitowych. Z punktu widzenia królowej Oszczędności sytuacja niedopuszczalna.
Możnaby z drugiej strony - korzystając z faktu, że jest (N M) kombinacji N elementów z M elementów - wymyślić jakąkolwiek funkcję przypisującą liczbom od 0 do (N M) -1 stosowny zbiór, umówić obie strony zeby ją znały i używały. Musielibyśmy wówczas jednak wymyślić bardzo wiele takich funkcji dla różnych par N i M - Zapobiegliwość nie byłaby z nas zadowolona.
Kompromisu w takich sytuacjach nakazuje s: znajdźmy uniwersalny sposób kodowania. Fortel - i mamy metodę opisaną w standardzie. Poniżej zajmę się jej objaśnieniem:
Po pierwsze, przypomnijmy sobie wzór dotyczący symbolu Newtona - nb. kluczowy dla konstrukcji trójkąta Pascala:
(n k) + (n k-1) = (n+1 k) (*)
Po drugie zauważmy, że jezeli n > m to
(n k) >= (m k) (**)
To łatwo udowodnić indukcją (zadanie licealne) albo zobaczyć od razu (stosując indukcję niejako niejawnie) z (*). Po prostu
(n k) = (n-1 k) + (n-1k-1) = (n-2 k) + (n-2 k-1) + (n-1 k-1) = [powtarzamy rozwinięcie pierwszego składnika] = (m k) + C
które to C jest >=0 (> 0 jeśli n > k).
Po trzecie zauważmy, że:
(N-1 M) + (N-2 M-1) +... + (N-M 1) = (N M) -1 (***)
Tym razem: szybka ale trochę fikuśna indukcja:
Oznaczmy F(n,m) = (n-1 m) + ... + (n-m 1)
Wtedy:
F(n,1) = (n-1 1) = n = (n 1) -1
Załóżmy, że dla ustalonego n i m F(n-1,m-1) = (n-1 m-1) -1
Wtedy F(n,m) = (n-1 m) + F(n-1, m-1) = (n-1 m) + (n-1 m-1) - 1 = (n m) -1
(ponownie z (*) )
Teraz prosto do tajemnicy naszego indeksu.
Weżmy jakiekolwiek r ∈ {0,..., (N M)-1}.
Weźmy największe K = K(r, N, M) t. że (K(r,N,M) M) <= r. Takie K(r, N, M) oczywiście istnieje i jest jedyne - z (**) Zauważmy, że r - (K(r, N, M) M) ≤ (K(r, N, M) M-1) - 1
to jasne bo w przeciwnym razie
r >= (K(r, N, M) M) + (K(r, N, M) M-1) = (K(r, N, M)+1 M)
co jest sprzecznością bo K(r, N, M) było największe
Zatem, dla r' = (r - (K(r, N, M) M)) ∈ {0,...,(K M-1)-1} czynność możemy powtórzyć wyliczając K':
K > K' = K((r - (K M)), K, M-1)
itd. dla M-2, M-3 itd i kolejnych r otrzymując ciąg M różnych wartości.
W ten sposób podaliśmy, algorytm który danego r w jednoznaczny sposób przypisuje ciąg {Ki} spełniający warunek Ki > Ki+1
Proponuję - jako ćwiczenie, żeby nie było nudno - sprawdzić, że opisany algorytm wykonuje operację dokładnie odwrotną do tej opisanej w naszym cytacie. Dodam, że zdaje się, że by to stwierdzić nie trzeba już nic liczyć...
Posty
