1 Jak optymalnie wybrać partnera na całe życie?Małgorzata Sulkowska Politechnika Wrocławska Instytut Matematyki i Informatyki

2 Założenia gry Główny bohater: Melman.Melman wie, że jest mu dane spotkać w życiu 8 kobiet. Pojawiają się w jego życiu kolejno, a może oświadczyć się tylko tej, z którą obecnie jest. Dotychczas poznane dziewczęta jest w stanie uporządkować – np. ocenić, która była najlepsza, a która najgorsza. Do raz porzuconej dziewczyny nie wolno mu już wrócić. Cel: oświadczyć się w takiej chwili, by zmaksymalizować prawdopodobieństwo wyboru najlepszej z 8 dziewcząt.

3 (zwany również algorytmem wyboru najlepszej sekretarki)Algorytm optymalny (zwany również algorytmem wyboru najlepszej sekretarki) Niech n oznacza liczbę kandydatek. Melman powinien poczekać do chwili T takiej, że i w tym lub po tym czasie wybrać pierwszą z dziewcząt, która jest lepsza od spotkanych dotychczas (ewentualnie ostatnią). Sprawdźmy, czy mu się uda…

4 Kandydatka nr 1: ARIEL Algorytm mówi: SZUKAJ DALEJ! Ranking bieżący:

5 Kandydatka nr 2: BUNIA Algorytm mówi: SZUKAJ DALEJ! Ranking bieżący:1. Ariel 2. Bunia

6 Kandydatka nr 3: POCAHONTASAlgorytm mówi: SZUKAJ DALEJ! Ranking bieżący: 1. Pocahontas 2. Ariel 3. Bunia

7 Kandydatka nr 4: SMERFETKARanking bieżący: 1. Pocahontas 2. Ariel 3. Smerfetka 4. Bunia Algorytm mówi: POLUJ NA LEPSZĄ OD SPOTKANYCH DOTYCHCZAS!

8 Kandydatka nr 5: FIONA Ranking bieżący: Algorytm mówi: POLUJ NA LEPSZĄ1. Pocahontas 2. Ariel 3. Smerfetka 4. Bunia 5. Fiona Algorytm mówi: POLUJ NA LEPSZĄ OD SPOTKANYCH DOTYCHCZAS!

9 Kandydatka nr 6: GLORIA Algorytm mówi: WYBIERZ GLORIĘ!!!Ranking bieżący: 1. Gloria 2. Pocahontas 3. Ariel 4. Smerfetka 5. Bunia 6. Fiona

10 Czy Melmanowi udało się wybrać najlepszą?Oto wszystkie kandydatki, jakie były mu pisane (od najlepszej): 1. Gloria 4. Tygrysica 6. Mała Mi 8. Fiona 5. Smerfetka 2. Pocahontas 7. Bunia 3. Ariel Melmanowi udało się wygrać!

11 Jakie jest prawdopodobieństwo sukcesu?Niech n oznacza liczbę kandydatek. Niech oznacza chwilę, w której każe się zatrzymać algorytm optymalny. Niech p oznacza prawdopodobieństwo sukcesu naszego algorytmu. Dostajemy Okazuje się, że , gdzie (liczba Nepera). Zatem przy dużej liczbie kandydatów nasza szansa trafienia w partnera najlepszego wynosi mniej więcej 1/3.

12 Uogólnienia i zastosowanie algorytmuPrzedstawiony algorytm doczekał się wielu uogólnień. Za sukces można np. uznać wybór jednej z dwóch, czy trzech najlepszych kandydatek. Można tez zmieniać założenia, np. uznać, iż nie wszystkie kandydatki są porównywalne. ? == Opisane algorytmy znajdują zastosowanie w życiu i zagadnieniach związanych z sieciami komputerowymi.

13 Dziękujemy za uwagę… … i wracamy z powrotem do Instytutu Matematyki i Informatyki. Czekamy na Ciebie!!!