PMT/K1 2022

Ovaj rok nije rešen. Pomozite SI Wiki tako što ćete ga rešiti.

Prvi kolokvijum 2022. godine održan je 5. novembra 2022. godine i trajao je 2 sata.

Pitanje 1

Jedan izvor emituje 6 simbola, Si, i=1,2,...6 sa verovatnoćama P(Si) datim u sledećoj tabeli. Neka je primenjen algoritam za kompresiju koji simbolima pridružuje kodne reči date u trećoj vrsti tabele:

Si	S₁	S₂	S₃	S₄	S₅	S₆
P(Si)	0.65	0.15	0.08	0.05	0.04	0.04
kodne reči	0	10	1100	1101	1110	1111

1. (2p) Nacrtati kodno stablo koje odgovara ovom kodu.
2. (2p) Da li je ovaj kod trenutan? Da li je ovaj kod mogao biti dobijen Hafmenovim postupkom (objasniti zašto)?
3. (2p) Predoložiti postupak kompresije kojim se postiže manja srednja dužina kodne reči u odnosu na rešenje prikazano u tabeli. Ako je to moguće, izračunati postignutu srednju dužinu kodne reči.

Pitanje 2

1. (3p) Objasniti šifru transpozicije i šifru monoalfabetske zamene - kako se konstruišu i kako se analizom kriptograma može otkriti da li je primenjena neka od ovih šifara.
2. (3p) U čemu se ogleda sigurnost RSA algoritma. Pod kojim uslovima je iz javnog ključa teško odrediti tajni ključ?

Zadatak 1

Izvor informacija bez memorije emituje tri simbola sa sledećim verovatnoćama:

Si	S₁	S₂	S₃
P(Si)	0.5	0.25	0.25

1. (1p) Odrediti entropiju izvora.
2. (2p) Odrediti kodne reči dobijene primenog Hafmenovog postupka, izračunati efikasnost tako dobijenog koda i postignut stepen kompresije.
3. (2p) Ako izvor emituje sekvencu S3, S1, S2, S1, S3, primenjen je kod određen u prethodnom delu zadatka i kanal greši pri prenosu trećeg bita, odrediti dekodovanu sekvencu.
4. (2p) Da li se može postići veći stepen kompresije ukoliko bi se pre primene Hafmenovog postupka obavilo proširenje ovog izvora? Ako je to moguće, koliko on iznosi?

Zadatak 2

1. (2p) Niz informacionih bita 10100001 treba zaštititi kodom sa ponavljanjem tri puta. Kao posledica šuma koji deluje u kanalu, 2. 4. i 12. bit u poslatoj sekvenci su neispravno primljeni. Kakvi zaključci se mogu doneti nakon procesa većinskog dekodovanja?
2. (2p) Niz informacionih bita 10100001 treba zaštititi Hemingovim (7,4) kodom. Kao posledica šuma koji deluje u kanalu, 2. 4. i 12. bit u poslatoj sekvenci su neispravno primljeni. Kakvi zaključci se mogu doneti nakon procesa dekodovanja?
3. (2p) Ukoliko se greške u kanalu pojavljuju sa verovatnoćom p=10⁻³, kolika je verovatnoća da dekoder ne ispravi grešku u kodnoj reči ako je primenjen kod iz prvog dela zadatka, a kolika ako je primenjen kod iz drugog dela zadatka? Navesti prednosti i mane ova dva zaštitna koda.