Uniwersytet Warszawski - Centralny System UwierzytelnianiaNie jesteś zalogowany | zaloguj się
katalog przedmiotów - pomoc

Funkcje boolowskie i ekstraktory losowości

Informacje ogólne

Kod przedmiotu: 1000-2M13FBE Kod Erasmus / ISCED: 11.3 / (0612) Database and network design and administration
Nazwa przedmiotu: Funkcje boolowskie i ekstraktory losowości
Jednostka: Wydział Matematyki, Informatyki i Mechaniki
Grupy: Przedmioty monograficzne dla III - V roku informatyki
Przedmioty obieralne dla informatyki
Punkty ECTS i inne: (brak)
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.