ПМТ/К1 2022

Овај рок није решен. Помозите SI Wiki тако што ћете га решити.

Први колоквијум 2022. године одржан је 5. новембра 2022. године и трајао је 2 сата.

Питање 1

Један извор емитује 6 симбола, Si, i=1,2,...6 са вероватноћама P(Si) датим у следећој табели. Нека је примењен алгоритам за компресију који симболима придружује кодне речи дате у трећој врсти табеле:

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. (2п) Нацртати кодно стабло које одговара овом коду.
2. (2п) Да ли је овај код тренутан? Да ли је овај код могао бити добијен Хафменовим поступком (објаснити зашто)?
3. (2п) Предоложити поступак компресије којим се постиже мања средња дужина кодне речи у односу на решење приказано у табели. Ако је то могуће, израчунати постигнуту средњу дужину кодне речи.

Питање 2

1. (3п) Објаснити шифру транспозиције и шифру моноалфабетске замене - како се конструишу и како се анализом криптограма може открити да ли је примењена нека од ових шифара.
2. (3п) У чему се огледа сигурност RSA алгоритма. Под којим условима је из јавног кључа тешко одредити тајни кључ?

Задатак 1

Извор информација без меморије емитује три симбола са следећим вероватноћама:

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

1. (1п) Одредити ентропију извора.
2. (2п) Одредити кодне речи добијене применог Хафменовог поступка, израчунати ефикасност тако добијеног кода и постигнут степен компресије.
3. (2п) Ако извор емитује секвенцу S3, S1, S2, S1, S3, примењен је код одређен у претходном делу задатка и канал греши при преносу трећег бита, одредити декодовану секвенцу.
4. (2п) Да ли се може постићи већи степен компресије уколико би се пре примене Хафменовог поступка обавило проширење овог извора? Ако је то могуће, колико он износи?

Задатак 2

1. (2п) Низ информационих бита 10100001 треба заштитити кодом са понављањем три пута. Као последица шума који делује у каналу, 2. 4. и 12. бит у послатој секвенци су неисправно примљени. Какви закључци се могу донети након процеса већинског декодовања?
2. (2п) Низ информационих бита 10100001 треба заштитити Хеминговим (7,4) кодом. Као последица шума који делује у каналу, 2. 4. и 12. бит у послатој секвенци су неисправно примљени. Какви закључци се могу донети након процеса декодовања?
3. (2п) Уколико се грешке у каналу појављују са вероватноћом p=10⁻³, колика је вероватноћа да декодер не исправи грешку у кодној речи ако је примењен код из првог дела задатка, а колика ако је примењен код из другог дела задатка? Навести предности и мане ова два заштитна кода.