Komunikacja, informacja i losowość

Informacje ogólne

Kod przedmiotu:	1000-2M13KIL
Kod Erasmus / ISCED:	11.3 Kod klasyfikacyjny przedmiotu składa się z trzech do pięciu cyfr, przy czym trzy pierwsze oznaczają klasyfikację dziedziny wg. Listy kodów dziedzin obowiązującej w programie Socrates/Erasmus, czwarta (dotąd na ogół 0) – ewentualne uszczegółowienie informacji o dyscyplinie, piąta – stopień zaawansowania przedmiotu ustalony na podstawie roku studiów, dla którego przedmiot jest przeznaczony. / (0612) Database and network design and administration Kod ISCED - Międzynarodowa Standardowa Klasyfikacja Kształcenia (International Standard Classification of Education) została opracowana przez UNESCO.
Nazwa przedmiotu:	Komunikacja, informacja i losowość
Jednostka:	Wydział Matematyki, Informatyki i Mechaniki
Grupy:	Przedmioty obieralne dla informatyki Przedmioty obieralne na studiach drugiego stopnia na kierunku bioinformatyka
Punkty ECTS i inne:	(brak) Podstawowe informacje o zasadach przyporządkowania punktów ECTS: roczny wymiar godzinowy nakładu pracy studenta konieczny do osiągnięcia zakładanych efektów uczenia się dla danego etapu studiów wynosi 1500-1800 h, co odpowiada 60 ECTS; tygodniowy wymiar godzinowy nakładu pracy studenta wynosi 45 h; 1 punkt ECTS odpowiada 25-30 godzinom pracy studenta potrzebnej do osiągnięcia zakładanych efektów uczenia się; tygodniowy nakład pracy studenta konieczny do osiągnięcia zakładanych efektów uczenia się pozwala uzyskać 1,5 ECTS; nakład pracy potrzebny do zaliczenia przedmiotu, któremu przypisano 3 ECTS, stanowi 10% semestralnego obciążenia studenta. zobacz reguły punktacji
Język prowadzenia:	angielski
Rodzaj przedmiotu:	monograficzne
Założenia (opisowo):	Znajomość podstaw rachunku prawdopodobieństwa i analizy matematycznej.
Skrócony opis:	Przedmiot zawiera wprowadzenie do najważniejszych metod teorio-informacyjnych używanych w informatyce. Pochodzić one będą z różnych gałęzi wiedzy (teoria kodów, teoria złożoności komunikacyjnej i ekstraktory losowości), a ich wspólną cechą jest to, że podstawowym narzędziem używanym w ich analizie jest rachunek prawdopodobieństwa. Narzędzia prezentowane na wykładzie znalazły szereg zastosowań w telekomunikacji, konstrukcji nośników danych i układów VLSI oraz kryptografii. Te ostatnie omówimy dokładniej pod koniec kursu.
Pełny opis:	1. Pojęcia entropii Shannona, entropii Renyi'ego, entropii warunkowej, informacji wzajemnej; reguła łańcuchowa, nierówność Fano (1 wykład) 2. Łańcuchy Markowa (1 wykład) 3. Kompresja danych: nierówność Krafta i kody Huffmana. (1 wykład) 4. Kody korygujące błędy: kody liniowe, Hamminga, Walsha-Hadamarda, Reeda-Mullera, Reeda Solomona, kody list-decodable (3 wykłady) 5. Złożoność komunikacyjna: wprowadzenie do dziedziny i przykłady dolnych granic (2 wykłady) 6. Ekstraktory losowości: min-entropia, niekonstruktywny dowód istnienia ekstraktorów, związek z ekspanderami, leftover hash lemma, ekstraktor Trevisana, ekstraktory dwu-źródłowe (3 wykłady) 7. Zastosowania teorii informacji w kryptografii: twierdzenie Shannona, szyfr Vernama, teorio-informacyjna autentykacja, kryptografia w modelu z ograniczoną pamięcią, kryptografia odporna na wycieki. (2 wykłady)
Literatura:	J H Van Lint Introduction to Coding Theory Thomas M. Cover, Joy A. Thomas Elements of Information Theory Sanjeev Arora, Boaz Barak Computational Complexity: A Modern Approach a także materiały dostępne w internecie
Efekty uczenia się:	Wiedza 1. Ma uporządkowaną wiedzę w zakresie teorii informacji, teorii kodów, teorii złożoności komunikacyjnej i teorii ekstraktorów losowości. 2. Zna najważniejsze własności entropii Shannona. 3. Ma podstawową wiedzę w zakresie metod kompresji informacji. 4. Ma ogólną wiedzę na temat różnych zastosowań teorii informacji w kryptografii. 5. Zna ograniczenia stosowalności powyższych teorii. Umiejętności 1. Potrafi stosować metody teorii informacji i teorii kodów w praktyce i w badaniach naukowych. 2. Potrafi używać metod teorii złożoności komunikacyjnej oraz teorii ektraktorów losowości w pracy badawczej. Kompetencje 1. Zna ograniczenia własnej wiedzy i rozumie potrzebę dalszego kształcenia, w tym zdobywania wiedzy pozadziedzinowej. 2. Potrafi precyzyjnie formułować pytania, służące pogłębieniu własnego zrozumienia danego tematu lub odnalezieniu brakujących elementów rozumowania.
Metody i kryteria oceniania:	Egzamin pisemny z zadań i z teorii.

Przedmiot nie jest oferowany w żadnym z aktualnych cykli dydaktycznych.

Opisy przedmiotów w USOS i USOSweb są chronione prawem autorskim.
Właścicielem praw autorskich jest Uniwersytet Warszawski.