Informacje
  Wiw.pl   Na bieżąco:  Informacje   Co nowego   Matematyka i przyroda:  Astronomia   Biologia   Fizyka   Matematyka   Modelowanie rzeczywistości   Humanistyka:  Filozofia   Historia   Kultura antyczna   Literatura   Sztuka   Czytaj:  Biblioteka   Delta   Wielcy i więksi   Przydatne:  Słowniki   Co i gdzie studiować   Wszechświat w obrazkach    
  Jesteś tutaj:  Wirtualny Wszechświat > Informacje > Nowinki 2000-2002 > Matematyka > Nowinka z dn. 20-11-2000  
 Jesteś tutaj
nowinka:
Pakowanie kul i korekcja błędów
autor:
Paweł Strzelecki
z dnia:
20-11-2000





Pakowanie kul i korekcja błędów
Listopadowy i grudniowy numer "Notices of the American Mathematical Society" przynoszą duży, dwuodcinkowy artykuł Noama Elkiesa o upakowaniach sfer i liniowych kodach korekcji błędów, dziedzinach na pozór bardzo odległych. O upakowaniach sfer można w Wirtualnym Wszechświecie przeczytać w nowince o hipotezie Keplera. Generalnie jest to (żywa) dziedzina geometrii, zmagająca się z próbami odpowiedzi na pytanie: jak gęsto da się układać rozłączne kule w przestrzeni. Korekcja błędów natomiast pojawia się wszędzie tam, gdzie mamy do czynienia z magazynowaniem, przesyłaniem lub odczytywaniem informacji. Surfującemu po Internecie Czytelnikowi nie trzeba tłumaczyć, że to ważna sprawa.

Co ma jednak piernik do wiatraka?

W języku polskim zmiana jednej litery na inną może zmienić sens słowa. Kilkakrotna zmiana litery - może przekręcić słowo nie do poznania: dama, data, rata, rota, kota. Co gorsza, takiej pomyłki (bez analizy kontekstu) nie wychwyci żaden genialny spell-checker. Podobnie rzecz się ma z ciągami zer i jedynek oraz ze wszystkimi słowami, które można zbudować, posługując się jakimkolwiek ustalonym alfabetem. Jak zapobiegać niezbyt wielkim przekłamaniom? Otóż, można się umówić, że przesyłamy tylko określone słowa określonej długości: np. ze wszystkich 256 "słów", które można napisać za pomocą ośmiu symboli 0 i 1, wybieramy tylko dwa, mianowicie 00000000 i 11111111. Jedno, dwa, czy nawet trzy przekłamania niezdarnej maszynistki piszącej tylko te dwa słowa wychwycimy i poprawimy natychmiast: słowo z przewagą jedynek na 11111111, a słowo z przewagą zer na 00000000. Jeśli więc nasza hipotetyczna maszynistka myli się co najwyżej trzy razy w jednym słowie, to jej błędami nie musimy się przejmować.

Język złożony z dwóch słów jest jednak, co tu kryć, piekielnie ubogi. (Niektóre dwulatki mówią tylko "mama" i "nie" - i nie zawsze jest łatwo zrozumieć, o co im chodzi). Powstają więc pytania: jeśli chcemy używać słów złożonych z ośmiu zer i jedynek i móc zawsze wychwycić trzy błędy maszynistki, to iloma słowami możemy się posłużyć? Które z wychwyconych błędów można poprawić bez namysłu, automatycznie? Ogólniej i poważniej: jak wybrać długość słów n (kto powiedział, że ma być akurat osiem?), żeby język optymalny, odporny na ustaloną z góry ilość przekłamań w jednym słowie, zawierał możliwie duży odsetek wszystkich możliwych słów długości n? Jakie znaczenie ma tu liczba symboli w alfabecie? Okazuje się, że ostatnie dwa pytania są piekielnie trudne. Żadne dokładne i ostateczne odpowiedzi nie są znane.

A gdzie obiecywane upakowania kul, niecierpliwi się Czytelnik, nerwowo wodząc myszą po podkładce? Otóż, słowa długości n można utożsamiać z punktami przestrzeni n-wymiarowej; n znaków to n współrzędnych pojedynczego punktu. Odległość dwóch słów mierzymy liczbą pojedynczych przekłamań, których trzeba dokonać, żeby jedno słowo zmienić w drugie. Zatem, odległość słów "dama" i "data" jest równa 1, a słów "dama" i "rata" - równa 2. Wszystkie słowa odległe od danego nie więcej niż o, powiedzmy, 3 (przekłamania), tworzą wokół niego "kulę o promieniu 3". Optymalny, odporny na przekłamania język powinien się składać ze słów odległych. Najlepiej wybranych tak, żeby wspomniane kule wokół nich były rozłączne: wtedy liczbę błędów, nie przekraczającą promienia kul, da się automatycznie porawić. Wychwycić będzie można taką liczbę błędów (w jednym słowie), która jest mniejsza od minimalnej odległości dwóch słów. (W przykładzie wspomnianym na początku 00000000 i 11111111 są odległe o 8; nie więcej niż 7 błędów w jednym słowie, oczywiście, wychwycimy, choć gdy przyjmiemy, że maszynistka może w jednym słowie nasadzić aż tyle byków, to o automatycznej korekcie nie ma mowy).

Jak wybierać długość słów, liczbę n? Ano tak, by w przestrzeni n-wymiarowej istniały stosunkowo gęste upakowania kul: wtedy optymalny język będzie dość bogaty, a przesyłanie informacji - w miarę oszczędne. Kłopot polega na tym, że - dla n większych od 3 - optymalnych upakowań kul nie znamy. Są liczne poszlaki, że bardzo gęste upakowania kul istnieją w przestrzeni
24-wymiarowej, ale dowodów brakuje. Matematycy odkryli tu ostatnio przedziwne tropy, wiodące w bardzo różne strony: do teorii grup, do geometrii algebraicznej, do teorii liczb, do analizy zespolonej. Ot, skrzyżowanie wielu ścieżek, spowite częściowo we mgle. Przykład matematyki, która jest jednocześnie abstrakcyjna, arcytrudna i nieoczekiwanie bliska praktycznym zastosowaniom.

A zaciekawionych i bardzo ambitnych Czytelników odsyłamy do obu części artykułu Noama Elkiesa:
http://www.ams.org/ notices/ 200010/200010-toc.html
http://www.ams.org/ notices/ 200011/200011-toc.html

Paweł Strzelecki
[  góra strony  ]

Wiw.pl  |  Na bieżąco  |  Informacje  |  Co nowego  |  Matematyka i przyroda  |  Astronomia  |  Biologia  |  Fizyka  |  Matematyka  |  Modelowanie rzeczywistości  |  Humanistyka  |  Filozofia  |  Historia  |  Kultura antyczna  |  Literatura  |  Sztuka  |  Czytaj  |  Biblioteka  |  Delta  |  Wielcy i więksi  |  Przydatne  |  Słowniki  |  Co i gdzie studiować  |  Wszechświat w obrazkach