Celem seminarium jest zapoznanie się z niedawno powstałą dziedziną łączącą uczenie maszynowe z algorytmiką, tzw. algorytmy z predykcjami.
Ogólny schemat algorytmu z predykcjami jest następujący: zakładamy, że mamy wyrocznię, która potrafi nam powiedzieć coś ciekawego nt. instancji naszego problemu (np. oszacowanie gdzie znajduje się obiekt, którego szukamy). Chcemy zaprojektować algorytm, który będzie działał lepiej (szybciej, z lepszym współczynnikiem aproksymacji, itp.) jeśli przewidywania wyroczni są trafne, ale nie będzie działał gorzej niż standardowy algorytm (nie używający predykcji) jeśli przewidywania wyroczni są fałszywe.
W przypadku wielu problemów tego typu wyrocznie mogą zostać zaimplementowane z użyciem narzędzi uczenia maszynowego, na seminarium będziemy wyrocznię traktować jako czarną skrzynkę i skupimy się na części algorytmicznej.
Pierwsze artykuły nt. algorytmów z predykcjami ukazały się w 2018 r., do dzisiaj ukazało się około 130 artykułów w tej działce (listę wszystkich można obejrzeć na stronie https://algorithms-with-predictions.github.io). Oznacza to, że w trakcie seminarium poznamy około 10% całej dziedziny!
Aby zrozumieć treści poruszane na tym przedmiocie przydatne będzie ogólne obycie z algorytmiką oraz znajomość rachunku prawdopodobieństwa.
