AZ (algorytmika i złożoność obliczeniowa)NG (metody numeryczne i grafika komputerowa)
Opis przedmiotu:
Wklęsłość i wypukłość funkcji są jednymi z podstawowych własności, które pozwalają na efektywne znajdowanie ich minimów i maksimów. To dotyczy jednak tylko funkcji o ciągłej domenie, bo kiedy mamy już do czynienia z problemem kombinatorycznym, tj. funkcją o dyskretnych argumentach, to z pojęcia wklęsłości/wypukłości już siłą rzeczy niestety skorzystać nie możemy.
Istnieje jednak pewien analog wklęsłości/wypukłości w świecie funkcji dyskretnych, nazywany submodularnością, który pozwala na zbudowanie całkiem ładnej teorii pozwalającej na optymalizację bardzo nietrywialnych funkcji pochodzących z różnych kontekstów, a których jedynym wpólnym mianownikiem jest wyabstrahowana submodularność. Na dowód tej rożnorodności i potencji pojęcia zajawmy jedynie, że w gruncie rzeczy to dzięki submodularności właśnie jesteśmy w stanie rozwiązać zarówno problem maksymalnego przepływu jak i minimalnego drzewa rozpinającego w czasie wielomianowym.
Nie jest to więc powszechna wiedza, ale optymalizacja submodularna jest jedną z najstarszych dziedzin informatyki teoretycznej. Ostatnie lata tchnęły w tę dziedzinę drugie życie w związku z coraz większymi jej zastosowaniami w uczeniu maszynowym i sztucznej inteligencji. Pozwala to dopełnić piękne rozważania teoretyczne ich efektywną implementacją, co jest bardzo satysfakcjonujące.
Na dowód tego wystarczy spojrzeć, że co roku na ICML, czyli najważniejszej konferencji machine learningowej, pojawia się około 10 prac, które są poświęcone tej tematyce.
Proponowany przedmiot jest adresowany do studentów, którzy chcieliby poznać podstawy tej dziedziny, a być może nawet wykonać mniej lub bardziej śmiały atempt na spróbowanie swoich sił w badaniach, które w swoim założeniu mogłyby się zakończyć publikacją na konferencji takiej jak ICML właśnie.
