Bit informacji

Permutacje. Kombinacje. Wariacje. Rozmieszczanie kul w urnach. Silnie i symbole Newtona. Przeliczanie zbiorów. Funkcje tworzące. Teoria grafów.
hutsalo
Użytkownik
Użytkownik
Posty: 141
Rejestracja: 14 sty 2022, o 19:44
Płeć: Mężczyzna
Podziękował: 59 razy

Bit informacji

Post autor: hutsalo »

Mamy 16 szufladek. Do jednej z nich wkładamy przedmiot. Ile bitów informacji potrzeba(minimalnie) aby powiedzieć, w której szufladce jest przedmiot?

Dodano po 1 godzinie 8 minutach 39 sekundach:
Myślałem żeby móc wykorzystać tutaj być może silnie. Ale pewności nie mam.
Awatar użytkownika
Janusz Tracz
Użytkownik
Użytkownik
Posty: 4060
Rejestracja: 13 sie 2016, o 15:01
Płeć: Mężczyzna
Lokalizacja: hrubielowo
Podziękował: 79 razy
Pomógł: 1391 razy

Re: Bit informacji

Post autor: Janusz Tracz »

Nie myśl kategoriami silnia się przyda bądź nie. Silnia to tylko matematyczna notacja upraszająca szczególne mnożenie. Staraj się myśleć raczej kategoriami idei algorytmów które ciągi bitów zamieniają na jednoznaczną odpowiedź w której szufladzie jest przedmiot. Przykładowo cztery bity wystarczą. Bo istnieje algorytm który \(\displaystyle{ 4}\) bitową informację przekształci na odpowiedź. Taką \(\displaystyle{ 4}\) bitową informacją może być ciąg \(\displaystyle{ \leftarrow \leftarrow \rightarrow \leftarrow }\) lub każdy inny układ czterech strzałek prawo/lewo np: \(\displaystyle{ \leftarrow \leftarrow \leftarrow \leftarrow }\). Algorytm działa tak, że pierwsza strzałka określa czy przedmiot jest w szufladzie od \(\displaystyle{ 1}\) do \(\displaystyle{ 8}\) albo od \(\displaystyle{ 9}\) do \(\displaystyle{ 16}\). To znaczy rząd \(\displaystyle{ 16}\) szuflad dzielisz na dwa i strzałka mówi Ci którą połowę wybrać. Kolejna strzałka wskazuje połowę wcześniejszej połowy więc na tym kroku wiesz, że przedmiot jest w jednej z \(\displaystyle{ 4}\) wskazanych szuflad. Kolejna strzałka kolejna połowa. Teraz zasłały już tylko dwie szuflady, ale masz jeszcze ostatnią strzałkę która mówi czy wybrać prawą czy lewą. To samo rozumowanie można rozbić bez strzałek. Wystarczy zauważyć, że binarnie \(\displaystyle{ 16}\) wartości przypiszemy ciągom zer i jedynej długości \(\displaystyle{ 4}\). Na koniec trzeba jeszcze pokazać, że \(\displaystyle{ 3}\) bity to za mało. Na \(\displaystyle{ 3}\) bitach można zakodować \(\displaystyle{ 8}\) wartości. To jednak za mało po potrzebujemy \(\displaystyle{ 16}\) jako, że przedmiot może być w jednej z \(\displaystyle{ 16}\) szuflad.
hutsalo
Użytkownik
Użytkownik
Posty: 141
Rejestracja: 14 sty 2022, o 19:44
Płeć: Mężczyzna
Podziękował: 59 razy

Re: Bit informacji

Post autor: hutsalo »

Ok. To co napisałeś też w rozważałem i to nawet przed silnią lecz odrzuciłem z uwagi na to że jak np. zrobić taki algorytm gdyby jakiś przedmiot wylądował w 1 albo w 16 szufladzie. Mam przedmiot w 1 szufladzie. I co teraz. Myślałem też żeby ułożyć jakiś wzór ciągu, który pozwoliłby coś takiego w miare prosty sposób obliczyć.
janusz47
Użytkownik
Użytkownik
Posty: 7910
Rejestracja: 18 mar 2009, o 16:24
Płeć: Mężczyzna
Podziękował: 30 razy
Pomógł: 1670 razy

Re: Bit informacji

Post autor: janusz47 »

Jeśli masz Teorię Informacji, to skorzystaj ze wzoru Claude Shannona na ilość bitowej informacji:

\(\displaystyle{ H(x) = - \sum_{i=1}^{n} p(x_{i})\cdot \log_{2}[p(x_{i})]. }\)
hutsalo
Użytkownik
Użytkownik
Posty: 141
Rejestracja: 14 sty 2022, o 19:44
Płeć: Mężczyzna
Podziękował: 59 razy

Re: Bit informacji

Post autor: hutsalo »

Zrobiłem to tak:
\(\displaystyle{
\sum_{1}^{16} \frac{1}{16} \cdot \log_{2} \frac{1}{16} = - \frac{1}{16} \cdot \left( -4\right) = \left( \frac{1}{4} \right)^{-1} = 4
}\)
ODPOWIEDZ