Funkcje boolowskie i ekstraktory losowości

Informacje ogólne

Kod przedmiotu:	1000-2M13FBE
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:	Funkcje boolowskie i ekstraktory losowości
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):	Podstawowa znajomość rachunku prawdopodobieństwa i matematyki dyskretnej
Skrócony opis:	Przedmiot obejmować będzie metody ciągłej analizy harmonicznej zastosowane do funkcji na skończonych grupach abelowych. Zaskakująco, uzyskane w ten sposób wyniki są dużo silniejsze niż w przypadku ciągłym. Metody te są szeroko stosowane w kryptografii i teorii ekstraktorów. Ta ostatnia, nieformalnie mówiąc, zajmuje się uzyskiwaniem idealnie losowych ciągów bitów z ciągów "słabo-losowych" Przełomowe wyniki ostatnich lat w teorii ekstraktorów oparte są właśnie na dyskretnej analizie Fouriera. Wszystkie metody i twierdzenia zostaną wyprowadzone "od zera", w szczególności nie będę bazował na wynikach z ciągłej analizy Fouriera.
Pełny opis:	-Wprowadzenie podstawowych pojęć i twierdzeń analizy harmonicznej -Liniowość funkcji boolowskich -Bent functions - czyli jak uzyskać funkcje jak najdalsze od liniowych -Niedeterminizm - czyli o tym, że nic nie działa jak powinno -Probabilistyczne testowanie własności -Funkcja charakterystyczna i jej własności, XOR-lemma -Entropia i min-entropia wektora boolowskiego - czyli jak mierzyć ile jest losowości w losowości -Wprowadzenie do ekstraktorów -Ekstraktory dwu-zródłowe, słabe, silne, twierdzenie Barak'a -Ekstraktor Bourgain'a - ekstraktor-rekordzista
Literatura:	http://www.cs.cmu.edu/ódonnell/aobf12/
Efekty uczenia się:	Student: -zna podstawowe metody analizy harmonicznej -potrafi policzyć transformatę funkcji boolowskiej oraz funkcje charakterystyczną zmiennej losowej -potrafi z transformaty odczytać czy funkcja jest liniowa -zna podstawowe metody testowania własności -rozumie pojęcie entropii i min-entropii -zna przykłady ekstraktorów dwu-źródłowych -rozumie różnicę między ekstraktorami słabymi a silnymi
Metody i kryteria oceniania:	Zadania domowe, egzamin

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.