Dręczy mnie mały problem matematyczny - nie wiem czy trudny (jak bym znał rozwiązanie to bym wiedział, ale wtedy bym nie pytał). Zgaduje, że jest znany w folklorze matematycznym. Prześladuje na tyle natrętnie, że przeszkadza mi trochę w pracy, więc postanowiłem się chociaż cześciowo uwolnić dzieląc się nim.
Zatem:
Na płaszczyźnie euklidesowej, dla zbioru ograniczonego S przez szerokość S w kierunku X gdzie X jest dowolną prosta, rozumiem kres dolny odległości prostych prostopadłych do X takich, że S mieści się w pasie między nimi. Oznaczmy go W(S,X).
Ograniczę się do zbiorów S będących homeomorficznymi obrazami okręgu - krzywych zamkniętych bez samoprzecięć. Dla S1 , S2 równość funkcji W(S1 , _) ≡ W(S2, _) na ogół nie oznacza, że S1 jest przystające do S2 . Najprostsze kontrprzykłady to krzywe niewypukłe, np brzeg kwadratu z małym wcięciem “do środka” na jednym z boków. Ale wypukłość też nie daje gwarancji - przykładem okrąg i trójkąt Roleaux (ten od silnika Wankla) o szerokości równej średnicy okręgu.
Pytanie jakie mnie nurtuje: A co jeżeli założmy, że krzywa jest wypukła (ogranicza obszar wypukły) i gładka (tzn. jest gładkim włożeniem okręgu) ? Czy wtedy W(S1 , _) ≡ W(S2, _) gwarantuje przystawanie S1 i S2 ?
2010-06-29
2010-06-10
Świeżo po lekturze
Po świetnym doświadczeniu jakim była lektura książki Fefermanów "Tarski", postanowiłem kontynuować w tym duchu, tj. wziąć na warsztat kolejną biografię. Kandydatka miętosiła się na półce od kilku ładnych lat (bodaj od 2003 roku) i niepokoiła trochę moje sumienie, dostałem ją bowiem w prezencie od żony i zamiast od razu przeczytać zakisiłem.
Rzecz nosi tytuł "Pan Bóg jest wyrafinowany. Nauka i życie Alberta Einsteina" i jest autorstwa Abrahama Pais i jest jak sam tytuł wskazuje biografią Einsteina.
Bez przeciągania powiem: rzecz jest świetna, trudna i wymagająca. Słowo biografia właściwie nie do końca do niej pasuje. Gdyby wypreparować treść jakiej się zwykle spodziewamy po biografiach - zostało by nam ok 30 procent objętości książki. Od razu powiem, że nie wynika to z braku drobiazgowości autora (choć zestawiając z biografią Tarskiego, Pais bardzo zadbał o prywatność Einsteina) - widać wyraźnie, że starał się nie pominąć żadnego z ważnych w życiu Einsteina wydarzeń ani żadnej z ważnych osób, poświecając każdej z nich i jej relacjom z Einsteinem stosownej miary miejsce w książce. Niewątpliwie jednak to na czym skupił się najbardziej to dzieło naukowe Einsteina: jego miejsce i rola w nauce. Odbija się to wyraźnie w organizacji książki. Podstawowym planem jest podział na wielkie zagadnienia jakim się uczony zajmował i ponieważ taki podział częściowo kłóci się z chronologią samego życiorysu, poświęcona została ona właśnie - stąd pewne przeploty i powtórzenia. Dołączono jednak na końcu kalendarium ktore znakomicie pozwala po przeczytaniu uporządkować sobie wszystko
Najciekawsze jest owe 70 procent stanowiące detaliczny opis fizyki jaką uprawiał Einstein. Welkie tamaty ujęte są z w następującej kolejności: mechanika statystyczna i ugruntowanie atomowej teorii budowy materii, szczególna teoria względności, ogólna teoria względności, jednolita teoria pola i teoria kwantów.
W każdym z "działów" podano stan wiedzy aktualny w czasach bezpośrednio poprzedzających Einsteina, wkład jego samego, omówienie specyfiki jego akurat pracy, konsekwencje i rozwój danej dziedziny po Einsteinie często do czasów mniej więcej pierwszego wydania książki (tj. do lat 80 -tych). Pisząc o stanie wiedzy nie mówię o popularnym omówieniu. Tu tkwi trudność ale i piękno książki: omawia się konkretne eksperymenty i równania wraz z krótkimi wyprowadzeniami. Podobnie prezentuje się dokonania samego Einsteina. Omawia się szczegółowo współzależność prac - co pozwala lepiej zoorientować się w kwestiach dość kontrowersyjnych. Należą do nich np. kwestionowanie pierszeństwa Einsteina w odkryciu szczególnej teorii względności na rzecz Lorentza lub Poincare (o czym czasem słychać), czy rewolucyjna rola uczonego w tzw. pierwszej teorii kwantów. Omawiając prace Einsteina autor nie stroni od opisywania błędnych ścieżek kiedy Einstein czasem się zapędza, czasem wycofuje, zwyczajnie błądzi a czasem błyska zupełnie zaskakującą intuicją.
Naukowe życie Einsteina pełne jest dramatycznch zupełnie napięć. Po słynnym anno mirabilis (1905) kiedy z dziecinną niemal łatwością produkuje Einstein kilka rewolucyjnych zupełnie prac w tym tą o szczególnej teorii względności następuje kilka lat wytężonej pracy by skleić zasadę względności z dynamiką. Einstein - obdarzony zupełnie niesamowitą intuicją fizyczną odnajduje matematykę, a konkretniej geometrię Riemanna (właściwie w jego kontekście Minkowskiego-Riemanna) w którą nareszcie jest w stanie ubrać swoje intuicje tworząc ogólną teorię względności.
Podobnie dramatycznie wygląda sprawa teorii kwantów, której podwaliny tworzy zajmując się oddziaływaniem promieniowania i materii a potem wyjaśniając np. niewytłumaczalne na bazie klasycznej fizyki anomalie związane z ciepłem właściwym ciał stałych czy w końcu postulując kwantową naturę światła i wyjaśniając efekt fotoelektryczny. Otóż w ciągu dekady rodzi się zupełnie nowa fizyka - druga teoria kwantów czyli mechanika kwantowa w dzisiejszym rozumieniu - na którą z powodów filozoficznych nigdy nie godzi się jako na teorię fundamentalną, ze względu na wyróżnioną i podstawową w niej rolę przypadku i prawdopodobieństwa. Mamy więc Einsteina który przeorał fizykę stanowiąc cezurę między XIX i XX wiekiem, zostawiając fizyków starej daty osłupiałych i nie mogących się pogodzić z nowym obrazem świata i Einsteina który w tej jednej dziedzinie stoi w ich roli kiedy obraz świata po raz wtóry zostaje obrócony na nice. Fascynujące.
Również trzydziestoletnia bez mała walka o jednolitą teorię pola - wyrosłą albo przynajmniej podsycana przez ową niezgodę - którą prowadził samotnie oddalając się od mainstreamu do samej śmierci. Wielkie i heroiczne - szczególnie w świetle tego co osiągnął wcześniej.
Ksiązka, jako się rzekło, jest bardzo trudna dla kogoś kto nie zna się na fizyce albo zna się tak powierzchownie jak ja. Nie wszystkie argumenty zrozumiałem, większości wyprowadzeń w ogóle albo bardzo prymitywnie, od strony formalnej jeno, nie łapiąc do końca treści fizycznej. W sumie nic dziwnego. To nie podręcznik przecież. Trud brnięcia przez tą treść bardzo się jednak opłaca, bo na kilka spraw oczy mi się otworzyły i jednak z tego mozołu może jakiś pożytek będzie. W każdym razie walczyłem twardo. Polska redakcja zawiera błędy we wzorach. Wyłapałem kilka - tam gdzie coś rozumiałem, albo gdzie bił po oczach.
Bezcenną rzeczą - że będę zmierzał do końca - jest podglądniecie tej wielkiej postaci przy pracy. Zobaczenie pewnych chwytów które stosuje, rozumowań. Dla mnie było to szczególnie ciekawe, bo nigdy nie miałem jakoś szczególnie rozwiniętej intuicji fizycznej a mogłem zobaczyć ją w działaniu. Np. piękne fragmenty dotyczące pierwszych przyczynków do ogólnej teorii względności, małe modele myślowe które buduje a w które nie są jeszcze tak nieprawdziwe by odbiegały znacząco od rzeczywistości opisywanej znaną już teorią a w których mogłyby się już ujawnić nowe szukane jej aspekty. Zresztą wiele innych temu podobnych miejsc.
Jeszcze jedno - czuję trochę niedosyt jeśli chodzi o omówienie patentów i technicznych innowacji uzyskanych przez Einsteina i współpracowników. Jest trochę, ale chciałoby się o niektórych tych zabawkach wiedzieć więcej.
Słowem: z czystym sumieniem polecam książkę. Ale niekoniecznie na wakacjach...
P.S. Parę lat temu w jakimś supermarkecie widziałem egzemplarz tej książki za jedną dziesiątą ceny jaką zapłaciła moja żona. Był to chyba jedyny raz kiedy książka w której pojawiają się równania Einsteina pojawiła się w takim miejscu...
Rzecz nosi tytuł "Pan Bóg jest wyrafinowany. Nauka i życie Alberta Einsteina" i jest autorstwa Abrahama Pais i jest jak sam tytuł wskazuje biografią Einsteina.
Bez przeciągania powiem: rzecz jest świetna, trudna i wymagająca. Słowo biografia właściwie nie do końca do niej pasuje. Gdyby wypreparować treść jakiej się zwykle spodziewamy po biografiach - zostało by nam ok 30 procent objętości książki. Od razu powiem, że nie wynika to z braku drobiazgowości autora (choć zestawiając z biografią Tarskiego, Pais bardzo zadbał o prywatność Einsteina) - widać wyraźnie, że starał się nie pominąć żadnego z ważnych w życiu Einsteina wydarzeń ani żadnej z ważnych osób, poświecając każdej z nich i jej relacjom z Einsteinem stosownej miary miejsce w książce. Niewątpliwie jednak to na czym skupił się najbardziej to dzieło naukowe Einsteina: jego miejsce i rola w nauce. Odbija się to wyraźnie w organizacji książki. Podstawowym planem jest podział na wielkie zagadnienia jakim się uczony zajmował i ponieważ taki podział częściowo kłóci się z chronologią samego życiorysu, poświęcona została ona właśnie - stąd pewne przeploty i powtórzenia. Dołączono jednak na końcu kalendarium ktore znakomicie pozwala po przeczytaniu uporządkować sobie wszystko
Najciekawsze jest owe 70 procent stanowiące detaliczny opis fizyki jaką uprawiał Einstein. Welkie tamaty ujęte są z w następującej kolejności: mechanika statystyczna i ugruntowanie atomowej teorii budowy materii, szczególna teoria względności, ogólna teoria względności, jednolita teoria pola i teoria kwantów.
W każdym z "działów" podano stan wiedzy aktualny w czasach bezpośrednio poprzedzających Einsteina, wkład jego samego, omówienie specyfiki jego akurat pracy, konsekwencje i rozwój danej dziedziny po Einsteinie często do czasów mniej więcej pierwszego wydania książki (tj. do lat 80 -tych). Pisząc o stanie wiedzy nie mówię o popularnym omówieniu. Tu tkwi trudność ale i piękno książki: omawia się konkretne eksperymenty i równania wraz z krótkimi wyprowadzeniami. Podobnie prezentuje się dokonania samego Einsteina. Omawia się szczegółowo współzależność prac - co pozwala lepiej zoorientować się w kwestiach dość kontrowersyjnych. Należą do nich np. kwestionowanie pierszeństwa Einsteina w odkryciu szczególnej teorii względności na rzecz Lorentza lub Poincare (o czym czasem słychać), czy rewolucyjna rola uczonego w tzw. pierwszej teorii kwantów. Omawiając prace Einsteina autor nie stroni od opisywania błędnych ścieżek kiedy Einstein czasem się zapędza, czasem wycofuje, zwyczajnie błądzi a czasem błyska zupełnie zaskakującą intuicją.
Naukowe życie Einsteina pełne jest dramatycznch zupełnie napięć. Po słynnym anno mirabilis (1905) kiedy z dziecinną niemal łatwością produkuje Einstein kilka rewolucyjnych zupełnie prac w tym tą o szczególnej teorii względności następuje kilka lat wytężonej pracy by skleić zasadę względności z dynamiką. Einstein - obdarzony zupełnie niesamowitą intuicją fizyczną odnajduje matematykę, a konkretniej geometrię Riemanna (właściwie w jego kontekście Minkowskiego-Riemanna) w którą nareszcie jest w stanie ubrać swoje intuicje tworząc ogólną teorię względności.
Podobnie dramatycznie wygląda sprawa teorii kwantów, której podwaliny tworzy zajmując się oddziaływaniem promieniowania i materii a potem wyjaśniając np. niewytłumaczalne na bazie klasycznej fizyki anomalie związane z ciepłem właściwym ciał stałych czy w końcu postulując kwantową naturę światła i wyjaśniając efekt fotoelektryczny. Otóż w ciągu dekady rodzi się zupełnie nowa fizyka - druga teoria kwantów czyli mechanika kwantowa w dzisiejszym rozumieniu - na którą z powodów filozoficznych nigdy nie godzi się jako na teorię fundamentalną, ze względu na wyróżnioną i podstawową w niej rolę przypadku i prawdopodobieństwa. Mamy więc Einsteina który przeorał fizykę stanowiąc cezurę między XIX i XX wiekiem, zostawiając fizyków starej daty osłupiałych i nie mogących się pogodzić z nowym obrazem świata i Einsteina który w tej jednej dziedzinie stoi w ich roli kiedy obraz świata po raz wtóry zostaje obrócony na nice. Fascynujące.
Również trzydziestoletnia bez mała walka o jednolitą teorię pola - wyrosłą albo przynajmniej podsycana przez ową niezgodę - którą prowadził samotnie oddalając się od mainstreamu do samej śmierci. Wielkie i heroiczne - szczególnie w świetle tego co osiągnął wcześniej.
Ksiązka, jako się rzekło, jest bardzo trudna dla kogoś kto nie zna się na fizyce albo zna się tak powierzchownie jak ja. Nie wszystkie argumenty zrozumiałem, większości wyprowadzeń w ogóle albo bardzo prymitywnie, od strony formalnej jeno, nie łapiąc do końca treści fizycznej. W sumie nic dziwnego. To nie podręcznik przecież. Trud brnięcia przez tą treść bardzo się jednak opłaca, bo na kilka spraw oczy mi się otworzyły i jednak z tego mozołu może jakiś pożytek będzie. W każdym razie walczyłem twardo. Polska redakcja zawiera błędy we wzorach. Wyłapałem kilka - tam gdzie coś rozumiałem, albo gdzie bił po oczach.
Bezcenną rzeczą - że będę zmierzał do końca - jest podglądniecie tej wielkiej postaci przy pracy. Zobaczenie pewnych chwytów które stosuje, rozumowań. Dla mnie było to szczególnie ciekawe, bo nigdy nie miałem jakoś szczególnie rozwiniętej intuicji fizycznej a mogłem zobaczyć ją w działaniu. Np. piękne fragmenty dotyczące pierwszych przyczynków do ogólnej teorii względności, małe modele myślowe które buduje a w które nie są jeszcze tak nieprawdziwe by odbiegały znacząco od rzeczywistości opisywanej znaną już teorią a w których mogłyby się już ujawnić nowe szukane jej aspekty. Zresztą wiele innych temu podobnych miejsc.
Jeszcze jedno - czuję trochę niedosyt jeśli chodzi o omówienie patentów i technicznych innowacji uzyskanych przez Einsteina i współpracowników. Jest trochę, ale chciałoby się o niektórych tych zabawkach wiedzieć więcej.
Słowem: z czystym sumieniem polecam książkę. Ale niekoniecznie na wakacjach...
P.S. Parę lat temu w jakimś supermarkecie widziałem egzemplarz tej książki za jedną dziesiątą ceny jaką zapłaciła moja żona. Był to chyba jedyny raz kiedy książka w której pojawiają się równania Einsteina pojawiła się w takim miejscu...
2010-06-02
Newton, Pascal i hermeneutyka - witajcie w świecie 4G
Mimo, że skończyłem szkołę w odległych i coraz szybciej, niestety, oddalających się czasach, pojęcie lektury obowiązkowej nie stało mi się obce. Tak więc, poza rzeczami które czytam z ciekawości, z chęci wzbogacenia poglądów, dla nauki, dla przyjemności, ze snobizmu etc. etc. zdarza mi się czytać rzeczy po prostu z obowiązku. Ostatnia lektura, która poczatkowo wydawała mi się koszmarnie nudna ale ciekawość moja rosła i wciąż rośnie oraz pojawiają się pewne oznaki satysfakcji z niej, to pewne fragmenty dokumentu o wiele mówiącym oznaczeniu 3GPP TS 36.213 V8.8.0 (2009-09) .
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ć...
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ć...
Subskrybuj:
Posty (Atom)
Posty
