Kodowanie, kompresja, kryptografia 0800-M-KODKOK

http://www.fizyka.umk.pl/~milosz/KKK/index.htm

1. Pojęcie i podstawowe własności entropii
2. Teoria kodowania w przypadku kanałów bezszumowych
a. Kody bezprefiksowe
b. Nierówności Krafta i McMilliana
c. Twierdzenie Shannona o kodowaniu dla kanałów bezszumowych
d. Kodowanie optymalne: kody Shannona-Fano
3. Kompresja danych
a. Kody blokowe
b. Ograniczenia wynikające z twierdzenia Shannona
c. Kod Huffmanna
d. Kod arytmetyczny
e. Kody słownikowe — algorytm LZW
f. Entropia języka naturalnego
g. Kompresja z utratą informacji: JPEG, MPEG
4. Kanały z szumem
a. Dekodowanie w obecności szumu
b. Bity kontrolne, odległość i kody Hamminga
c. Kody korygujące błędy
d. Oszacowania niezbędnej liczby bitów
5. Pojemność informacyjna kanału
a. Wzajemna informacja i jej własności
b. Nierówność Fano
c. Twierdzenie Shannona o kodowaniu w obecności szumów
6. Konstrukcja kodów korygujących
a. Kody liniowe
b. Kody cykliczne
c. Kody Bosego–Chaudhuriego–Hocquenghema (BCH)
7. Kryptografia
a. Podstawowe pojęcia: wieloznaczność (equivocation) i jedyność (unicity) szyfru
b. Szyfry symetryczne i asymetryczne
c. Elementy arytmetyki modularnej
d. Szyfry z publicznym kluczem (RSA, kod Rabina)
e. Protokół Diffiego–Hellmana, kod Elgamala
f. Podpis elektroniczny
8. Kryptografia klasyczna a kwantowa

W cyklu 2021/22L:

por. informacje na stronie głownej przedmiotu

W cyklu 2022/23L:

por. informacje na stronie głownej przedmiotu

W cyklu 2024/25L:

por. informacje na stronie głownej przedmiotu

Całkowity nakład pracy studenta

Godziny realizowane z udziałem nauczycieli (38 godz.): - udział w wykładach – 30 godz. - konsultacje z nauczycielem akademickim – 8 godz. Czas poświęcony na pracę indywidualną studenta (40 godz.): np. - przygotowanie do wykładu – 20 godz. - przygotowanie do egzaminu- 20 godz. Łącznie: 78godz. (3 ECTS)

Efekty uczenia się - wiedza

W01: posiada podstawową wiedzę w zakresie teorii informacji przydatną do formułowania i rozwiązywania prostych zadań związanych z kodowaniem, transmisją, kompresją i szyfrowaniem danych. W02: Zna teoretyczne ograniczenia na efektywność transmisji i kompresji danych. W03: Zna podstawowe metody i algorytmy stosowane w ww. zastosowa¬niach. Przypisanie do kierunkowych efektów kształcenia: K_W01, K_W02 dla ISs2 K_W01 dla Fizykis2

Efekty uczenia się - umiejętności

U01: potrafi wykorzystać nabytą wiedzę teoretyczną do tworzenia i analizy systemów transmisji, kompresji lub szyfrowania danych, U02: zna poszczególne metody stosowane w ww. zagadnieniach, potrafi ocenić ich przydatność i skuteczność w konkretnych sytuacjach. U03: Rozumie potrzebę ciągłego dokształcania powodowanego pojawianiem się nowych osiągnięć, nowych technologii. Przypisanie do kierunkowych efektów kształcenia: K_U01, K_U04 dla ISs2 K_U01, K_U04, K_U05, K_U11 dla Fizyki s2

Efekty uczenia się - kompetencje społeczne

K01 rozumie potrzebę wymiany informacji w grupach osób zajmujących się informatyką, rozumie możliwości jakie daje edukacja akademicka. K02: Ma świadomość skutków wadliwie działających systemów informatycznych prowadzących do naruszenia poufności i prywatności określonych danych. Przypisanie do kierunkowych efektów kształcenia: K_K01, K_K05 dla ISs2

Metody dydaktyczne

wykład informacyjny (konwencjonalny)

Metody dydaktyczne podające

- wykład informacyjny (konwencjonalny)

Metody dydaktyczne poszukujące

- ćwiczeniowa

Rodzaj przedmiotu

przedmiot fakultatywny

Wymagania wstępne

Elementy matematyki dyskretnej, rachunku prawdopodobieństwa i algebry liniowej

Koordynatorzy przedmiotu

Miłosz Michalski

Kryteria oceniania

egzamin ustny – W01, W02, W06, U01, U02, U03

Kryteria oceniania:
Student losuje 3 pytania i po kilkuminutowym przygotowaniu omawia przy tablicy wylosowane zagadnienia. Odpowiedzi oceniane są wg następujących kryteriów:
- znajomość teoretycznych podstaw przedmiotu – 0-5 pkt
- zrozumienie omawianych zagadnień – 0-5 pkt
- umiejętność powiązania teoretycznej wiedzy z praktycznymi problemami z zakresu kodowania, kompresji i szyfrowania danych – 0-5 pkt.
Ocena ostateczna:
Ndst – 0-50% pkt.
Dst – 51-62% pkt.
Dst plus – 63-69% pkt.
Db – 70-81% pkt.
Db plus – 82-87% pkt
Bdb – 88-100% pkt.

Praktyki zawodowe

nnie dotyczy

Literatura

1. T. K. Carne, Codes and Cryptography, lecture notes, Cambridge University 2015
2. T. M. Cover, Elements of Information Theory, John Wiley 2006
3. A. Drozdek, Wprowadzenie do kompresji danych, WNT 1999

W cyklu 2021/22L:

por. informacje na stronie głownej przedmiotu

W cyklu 2022/23L:

por. informacje na stronie głownej przedmiotu

W cyklu 2024/25L:

por. informacje na stronie głownej przedmiotu

Więcej informacji

Dodatkowe informacje (np. o kalendarzu rejestracji, prowadzących zajęcia, lokalizacji i terminach zajęć) mogą być dostępne w serwisie USOSweb:

Strona przedmiotu 0800-M-KODKOK w USOSweb