Előfordulhat-e olyan a^i + b^j = c^k összeg, ahol a és b sokkal kevesebb biten ábrázolható, mint c?

Olvass Shannont és Neumannt. A kérdés az, hogy hány féle számot akarsz megkülönböztetni? A számosság és a számábrázolás egymástól független dolog. Ha te akarod az összes egyész számot ábrázolni egytől egy jó nagy N számíg akkor ahhoz akár,hogy csűröd csavarod log2(N) bitre lesz szükséged, számábrázolástól függetlenül. Ugyanis a számábrázolás itt nem jelent mást, hogy van egy halmazod ami tartalmazza 1-től N-ig az egész számokat (legyen ez az "A" halmaz), és kell alkossál egy kölcsönösen egyértelmű függvényt ami megmondja, hogy az "A" halmaz melyik eleméhez a "B" (ez lesz a kódszó) halmaz melyik eleme tartozik. Elég gyorsan belátató, hogy ez csak akkor tud kölcsönösen egyértelmű lenni ha az A halmazban lévő elemek száma és a B halmazban lévő elemek száma megegyezik. Tehát bármilyen kódolás kitalálható ha a kiindulási halmazod nagy akkor a kódszó halmazod is nagy lesz.

Ha szűkíted az "A" halmazt pl. azt mondod, hogy csak azokat a számokat akarod kódolni, amelyekre igaz, hogy valamelyin prim szám "n"-ik hatványa (ld. bevezető kérdésben) c^k alakban felírható, és c^k<N (hiszen a jó nagy N-ünket nem változtatjuk) akkor látható csa azt kell megvizsgálni, hogy a c^k (ahol c prím és k +egész) alakú számból kevesebb van-e mint N, és ez elég gyorsan belátható, hogy az össszetett számok közül elég sok nem fogja ezt teljesíteni. Hiszen pl. a 6 ami 2*3 prímtényezős felbontásban írható fel arra nem igaz, hogy felírható c^k (ahol c prím és k egész) alakban. Ebből látható lesz, hogy annak a halmaznak az elemeinek száma amelyikben azok a pozítiv egész számok vannak amelyek felírhatóak c^k (ahol c prím és k +egész) és c^k<N elem száma kisebb lesz mint N. Tehát található lesz olyan kódolás amelyben a kódszó hossza kisebb lesz mint log2(N). A kérdés az lehet, hogy tudunk-e becslést adni (vagy konkrét értéket arra), hogy hány darab számra lesz igaz, hogy felírható c^k (ahol c prím és k +egész) és c^k<N ekkor azt is megtudjuk mondani, hogy hány bit kell hozzá (minimálisan). Hogy itt a hozzárendelésnek mi lesz a szabálya az ezen a szinten mindegy. Mert itt most arra keresünk választ, hogy hány bit kell egy adott szám tárolására. Remélem érthető voltam.

Bocs még 1x elolvastam és kicsit kusza lett az eleje. Ha van egy olyan halmazod amiben van N darab elem (bármilyen halmaz), és ezt valamilyen bináris kóddal akarod leírni akkor N darab különböző kódszóra lesz szükséged. (ld. Shannon és Neumann munkássága, de főleg Shannon). Itt kell egy kölcsönösen egyértelmű hozzárendelés mert ha nem kölcsönösen egyértelmű akkor veszett fejsze nyele. N darab kódszó bináris kódolásához legkevesebb log2(N) bitre van szükséged. Lehet több, de kevesebb nem.

Ha a kódolandó halmaz az egész számok halmazának egy részhalmaza pl. az M-nél kisebb egész számok akkor az egy M-1 elemű halmaz, tehát M-1 db. kódszóra lesz szükséged, és ehhez legkevesebb log2(M-1) bitre lesz szükséged.

Ha szűkíted az "alaphalmazt" pl. csak azokat a számokat akarod leírni amelyekre igaz, hogy y=c^k és y<M és c prímszám, k pozítiv egész akkor ennek a halmaznak az elemszáma biztosan kisebb lesz mint M, így biztosan kevesebb bit fog kelleni.

Az meg egy eztől független, hogy a kódszavak hogyan néznek ki. Hogy most súlyozott, BCD (ehhez még több bitre lesz szükség), gray kód vagy bármi egyéb az teljesen független, hogy hány darab eltérő kódszóra van szükség.

8: Nem nyernél vele semmit. Pont erről ír hosszasan Shannon több helyen, ír erről Neumann és mindenki akik utána jönnek. Ugyanis OK, hogy leírod, hogy milyen számok vannak, de a műveleti jelet is le kell hozzá írnod. Máris ugyanott tartasz. Pont azon van a lényeg, hogy a kódszó halmaz elemeinek a száma pontosan ugyannyi kell legyen mint az a halmaz amit kódolsz. És ez teljesen független továbbra is a kódolástól. Nézzünk egy példát: 0-10-ig akarod kódolni a számokat, egyértelműen. Ehhez 11 darab különböző kódszó kell, mert nem lesz egyértelmű, hogy mire gondolsz. Ezek a kódszavak bármilyenek lehetnek, pl. "nulla" "egy" "kettő" "három" "négy" "öt" "hat" "hét" "nyolc" "kilenc" "tíz". De mehetünk még tovább is. Pl. nézzük ugyanezt pl. a 12 esetén ez magyar nyelven "tizenkettő" azaz kb. a "10+2" alak, angolban erre külön szó áll rendelkezésre ez a twelve de ha a kódszavak számát nézzük ugyanúgy "önálló". De pl. már a 25 esetén magyarul úgy mondjuk huszonöt angolul twenty five mindkét nyelven 20+5 alakban mondjuk. De ettől nem lett kevesebb a kódszavunk. Mert valahogy el kell majd különítsünk a 20-at "húsz" a "huszon..." formától.

Nagyjából ezekből a megfontolásokból tették le Shannonék az információ elmélet és a kódolás alapjait, amit utána nagyon sokan fejlesztettek. De nagy csodát nem tudsz csinálni. Egyedül a beszélt nyelvben lehet valamit "spórolni" de figyelni kell, hogy egyértelmű marad-e a közlés. ISmert példa: "A királynőt megölni nem kell félnetek jó lesz" példa mondat. Attól függően, hogy hova teszünk be plusz (nem jelölt) vesszőket egészen mást fog jelenteni. Ezt el kell kerülni. Ezért említettem korábban pl. az 5 bites Baudot kódot, ahol volt a betű váltó és a számváltó karakter. Ha betűváltó jött azt jelentette innen kezdve betűként, ha számváltó akkor azt, hogy innen kezdve számként kell értelmezni a következő váltó karakterig. De ha vétel hiba volt akkor márs borult a történet.