ПМТ/К1 2022 — разлика између измена
< ПМТ
Пређи на навигацију
Пређи на претрагу
(Нова страница: {{tocright}} {{нерешено}}<!-- Ово ставити уколико НИЈЕДАН задатак није решен, док уколико само неки з…) |
м (Uvod) |
||
| Ред 1: | Ред 1: | ||
{{tocright}} | {{tocright}} | ||
{{нерешено}} | {{нерешено}} | ||
'''Први колоквијум 2022. године''' одржан је 5. новембра 2022. године и трајао је 2 сата. | |||
== Питање 1 == | == Питање 1 == | ||
| Ред 69: | Ред 70: | ||
# '''(2п)''' Уколико се грешке у каналу појављују са вероватноћом p=10⁻³, колика је вероватноћа да декодер не исправи грешку у кодној речи ако је примењен код из првог дела задатка, а колика ако је примењен код из другог дела задатка? Навести предности и мане ова два заштитна кода. | # '''(2п)''' Уколико се грешке у каналу појављују са вероватноћом p=10⁻³, колика је вероватноћа да декодер не исправи грешку у кодној речи ако је примењен код из првог дела задатка, а колика ако је примењен код из другог дела задатка? Навести предности и мане ова два заштитна кода. | ||
</div> | </div> | ||
[[Категорија:Рокови]] | [[Категорија:Рокови]] | ||
[[Категорија:ПМТ]] | [[Категорија:ПМТ]] | ||
Тренутна верзија на датум 6. новембар 2022. у 19:42
- Овај рок није решен. Помозите 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 |
- (2п) Нацртати кодно стабло које одговара овом коду.
- (2п) Да ли је овај код тренутан? Да ли је овај код могао бити добијен Хафменовим поступком (објаснити зашто)?
- (2п) Предоложити поступак компресије којим се постиже мања средња дужина кодне речи у односу на решење приказано у табели. Ако је то могуће, израчунати постигнуту средњу дужину кодне речи.
Питање 2
- (3п) Објаснити шифру транспозиције и шифру моноалфабетске замене - како се конструишу и како се анализом криптограма може открити да ли је примењена нека од ових шифара.
- (3п) У чему се огледа сигурност RSA алгоритма. Под којим условима је из јавног кључа тешко одредити тајни кључ?
Задатак 1
Извор информација без меморије емитује три симбола са следећим вероватноћама:
| Si | S₁ | S₂ | S₃ |
|---|---|---|---|
| P(Si) | 0.5 | 0.25 | 0.25 |
- (1п) Одредити ентропију извора.
- (2п) Одредити кодне речи добијене применог Хафменовог поступка, израчунати ефикасност тако добијеног кода и постигнут степен компресије.
- (2п) Ако извор емитује секвенцу S3, S1, S2, S1, S3, примењен је код одређен у претходном делу задатка и канал греши при преносу трећег бита, одредити декодовану секвенцу.
- (2п) Да ли се може постићи већи степен компресије уколико би се пре примене Хафменовог поступка обавило проширење овог извора? Ако је то могуће, колико он износи?
Задатак 2
- (2п) Низ информационих бита 10100001 треба заштитити кодом са понављањем три пута. Као последица шума који делује у каналу, 2. 4. и 12. бит у послатој секвенци су неисправно примљени. Какви закључци се могу донети након процеса већинског декодовања?
- (2п) Низ информационих бита 10100001 треба заштитити Хеминговим (7,4) кодом. Као последица шума који делује у каналу, 2. 4. и 12. бит у послатој секвенци су неисправно примљени. Какви закључци се могу донети након процеса декодовања?
- (2п) Уколико се грешке у каналу појављују са вероватноћом p=10⁻³, колика је вероватноћа да декодер не исправи грешку у кодној речи ако је примењен код из првог дела задатка, а колика ако је примењен код из другог дела задатка? Навести предности и мане ова два заштитна кода.