Rozważmy portal randkowy (nie tinder), w którym są 44 tysiące kobiet i 44 tysiące mężczyzn. Portal zarabia na miesięcznej subskrypcji, a jego zadaniem jest proponowanie użytkownikom randek. Portal używając danych użytkowników (np. z ankiet na temat cech charakteru, ulubionych filmów i muzyki itd) jest w stanie całkiem nieźle wyestymować dla każdej pary użytkowników prawdopodobieństwo, że dana para się sobie wzajemnie spodoba, o ile tylko pójdzie na randkę.
Pytanie jednak jest następujące: w jaki sposób portal powinien proponować randki, aby zmaksymalizować średnią (lub też totalną w ciągu roku) liczbę szczęśliwie skojarzonych par? Nie możemy przecież wysłać żadnego użytkownika na 100 nieudanych randek, bo do tego czasu zrezygnuje z subskrypcji. Musimy więc robić to ostrożnie. Co więcej dana para, jeśli tylko się sobie spodoba, to natychmiast opuszcza portal (a przynajmniej takie jest sensowne założenie).
Gdyby nie było tutaj żadnej niepewności i a priori byśmy wiedzieli, które pary się sobie spodobają, a które nie, to naszym zadaniem byłoby obliczenie po prostu maksymalnego skojarzenia w grafie, które możemy zrobić całkiem sprawnie w czasie wielomianowym.
Ale gdy uwzględnimy stochastyczną naturę, czyli że randki mogą się udać albo się nie udać, to problem --- mimo że cały czas dotyczy skojarzeń w grafach --- staje się nagle zgoła inny. Co więcej, teraz nawet nie tyle, co nie znamy wielomianowego algorytmu, ale nawet nie wiemy, czy ten problem należy do klasy NP. Mimo wszystko na wykładzie zobaczymy 2-aproksymacyjny algorytm dla tego problemu.
Istotą tego przydługiego wstępu była ilustracja faktu, że bardzo często prawdziwie praktyczne problemy mają pewien aspekt niepewności w sobie, a ten z kolei wymusza zupełnie inne podejście do problemu niż w przypadku jego deterministycznego odpowiednika.
Na wykładzie przedstawię kilka klasycznych modeli niepewności: stochastyczne próbkowanie (przykład portalu randkowego), problem sekretarki (https://en.wikipedia.org/wiki/Secretary_problem), nierówność Proroka (https://en.wikipedia.org/wiki/Prophet_inequality) i algorytmy online oraz jak w tych modelach rozważać struktury kombinatoryczne takie jak skojarzenia lub matroidy (na wykładzie wytłumaczę co to).
Przedmiot będzie mocno matematyczny, a nawet mocno probabilistyczny, jednak nie będziemy potrzebować żadnego zaawansowanego aparatu --- znajomość warunkowej wartości oczekiwanej w zupełności wystarczy.
