Optymalizacja dyskretna

Opis

Bardzo często zdarza się tak, że pomimo ogromnego postępu, jaki cywilizacja poczyniłA dzięki komputerom, wciąż jesteśmy w pewnych dziedzinach bezsilni. Dla przykładu: policzenie prostego problemu znalezienia najkrótszego cyklu łączącego największe 50 miast w Polsce (cyklu Hamiltona) okazuje się nieosiągalne. Musimy sobie radzić w inny sposób. Jedną z metod są algorytmy aproksymacyjne, które dają nam przybliżone rozwiązanie, zwykle gorsze o optymalnego o co najwyżej pewną stałą. Inną metodą są heurystyki, które dają nam przybliżone rozwiązania, które zwykle są dopuszczalne przez aktualne standardy (dużej firmie kurierskiej mimo, że bardzo zależy na optymalnym rozwiązaniu, to zwykle pogodzi się z rozwiązaniem wystarczająco bliskim optymalnemu).

Warsztaty będą stanowiły przegląd wybranych metod używanych w optymalizacji dyskretnej. Opowiemy sobie (i zaimplementujemy, aby zobaczyć jak działają na wybranych przykładach z prawdziwego życia) co najmniej o następujących algorytmach: A*, ALT, IDA*, beam search, hill climbing, simulated annealing, taboo search (można sobie wygooglować te rzeczy). Zmierzymy także się z kilkoma zadaniami optymalizacyjnymi z konkursów typu Deadline24. 

Wymagania i przydatne rzeczy

• Umiejętność programowania w jednym z nowoczesnych języków programowania. Warsztaty będa miały część implementacyjną. Większość kodów przykładowych będzie w C++ i/lub Pythonie, ale nie powinno to być żadnym problemem.
• Jakieś podstawowe obycie z algorytmiką (szczególnie warto wiedzieć jak działa np. BFS czy Dijkstra).
• Warto wiedzieć co nieco o rachunku prawdopodobieństwa i statystyce (aczkolwiek możemy to używać jako czarne pudełko, więc nie jest to wymagane).​