Analiza informacji niepewnej czyli jak dowiedzieć się prawdy od kłamców?

W dniu 19 września 2000 spotkaliśmy się na pierwszym odczycie sezonu 2000/2001, mianowicie na odczycie wygłoszonym przez prof. Andrzeja Pelca z Université du Québec à Hull zatytułowanym "Analiza informacji niepewnej czyli jak dowiedzieć się prawdy od kłamców?".

Ogólnie mówiąc, Prelegent mówił o zespole metod pozwalających wykonać zadanie (przesłanie informacji) pomimo wadliwych elementów środowiska informatycznego. Okazuje się bowiem, że w miarę rozwoju technologii, rosnąca złożoność systemów informatycznych i komunikacyjnych powoduje wzrost ich wrażliwości na wady komponentów. Otóż odporność na wady uzyskuje się kosztem redundancji, tzn. nadmiaru informacji lub komunikacji.

Do korekcji używa się kodów korygujących. Dobry kod musi być krótki (koszt) i musi chronić przed zniekształceniami przekazu. Te żądania są często sprzeczne. Wszyscy wiemy, że w informatyce wszystkie informacje są zapisane za pomocą kodów binarnych (jedynie cyfry 0 i 1). Przy odkodowywaniu zniekształconego przekazu stosuje się hipotezę najmniejszego przekłamania: przekaz bardziej prawdopodobny to ten, który spowodował mniej przekłamań. Prelegent pokazał parę przykładów odkodowywania przekłamanych informacji przekazanych w kodzie binarnym.

W drugiej części wykładu Prelegent opowiedział o metodach wyszukiwania błędów wśród przekazów z kłamliwymi odpowiedziami. Okazuje się bowiem, że do wyszukiwania błędów stosuje się strategię przesłuchań - zadaje się pewną liczbę pytań. Jest to wyżej wymieniona redundancja, czyli aby prawidłowo przekazać jedną informację, przekazuje się parę informacji, a nie jedną. Metodę tę można porównać do znanej gry w 20 pytań. Jedna osoba (przesłuchiwany lub Pinocchio) wybiera liczbę pomiędzy 1 i 1 000 000 (w rzeczywistości liczba ta jest informacją do przekazania zakodowaną w systemie binarnym). Śledczy (czyli osoba otrzymująca informację) musi ją znaleźć zadając pytania zaczynające się od "czy...?", tzn. takie, na które odpowiedź może być tylko TAK lub NIE. Występuje tu dodatkowe utrudnienie dla Śledczego - osoba wybierająca liczbę (przesłuchiwany lub Pinocchio) może skłamać, ale co najwyżej raz (tak jak to jest w rzeczywistym przekazie informacji z jednym błędem). Jak szybko można znaleźć nieznaną liczbę, czyli jak szybko można prawidłowo odczytać informację? Okazuje się, że bez kłamstw zawsze wystarczy zadać 20 pytań używając strategii połówkowej. Udowodniono, że wraz z jednym kłamstwem, zawsze wystarczy zadać 25 pytań i poprawić tego już nie można.

W podsumowaniu Prelegent zaznaczył, że odporność na wady systemu telekomunikacyjnego jest konieczna i jej znaczenie wzrasta wraz z rozwojem technologii. Nic nie jest jednak za darmo. Za odporność na wady trzeba płacić redundancją. Jednakowoż stosunkowo małym kosztem można uzyskać znakomity stopień odporności na wady.

Cały wykład był bardzo interesujący i przedstawiony w formie przystępnej nie tylko dla specjalisty informatyka, lecz także dla zwykłego użytkownika komputera, za co serdecznie Prelegentowi dziękujemy.

Odczyt zgromadził około 25 osób, a ożywiona dyskusja uczestników zakończyła wykład. Dalsze dyskusje potoczyły się przy zwyczajowym poczęstunku kawą i ciasteczkami.

Składamy serdeczne podziękowania Prelegentowi za bardzo interesujący wieczór.

Lidia Zielińska
19/09/2000

Początek strony


ZAPOWIEDŹ ODCZYTU:

W systemach informatycznych i w systemach komunikacyjnych w różnych sytuacjach mamy do czynienia z informacją, która może być przekłamana, albo z powodu niedoskonałości technicznych (przekłamana na łączach telekomunikacyjnych, informacja pochodząca z wadliwych procesów), albo wskutek czyjeś celowej działalności.
Prof. Andrzej Pelc mówić będzie o metodach pozwalających na "wyłuskiwanie prawdy" z takich niepewnych danych.

Początek strony