Prowadzący
Opis
Istnieje wiele ciekawych problemów w informatyce, których nie da się rozwiązać w czasie wielomianowym — są to tak zwane problemy NP-zupełne. Nie zawsze jednak jest potrzeba by uzyskać rozwiązanie absolutnie najlepsze — można wtedy posłużyć się jakimś algorytmem heurystycznym, który znajdzie nam rozwiązanie przybliżone.
Na warsztatach zajmiemy się w ogólności analizą algorytmów heurystycznych dla problemów NP-zupełnych, jednak szczególny nacisk położymy na algorytmy mrówkowe.
Algorytmy mrówkowe (Ant colony optimization, ACO) to klasa algorytmów heurystycznych pozwalających rozwiązywać wiele problemów NP-zupełnych, które da się zobrazować jako grafy. Oprócz tego, ACO są także przykładem inteligencji rojowej (swarm intelligence).
Pewnie słyszałaś/eś o algorytmach genetycznych albo sieciach neuronowych — one często też nadają się do tych problemów, jednak nie radzą sobie tak dobrze jak ACO ze zmianami grafu w trakcie rozwiązywania problemu.
Oprócz analizy grafowych problemów NP-zupełnych oraz różnych wariacji ACO zajmiemy się ich implementacją i zrobimy zawody mrówek: sprawdzimy która wersja ACO lepiej sobie radzi z którym problemem.
Program zajęć
- omówienie kilku problemów NP-zupełnych
- omówienie kilku algorytmów heurystycznych ogólnego zastosowania
- crash course z analizy matematycznej
- zapoznanie z frameworkiem do algorytmów mrówkowych
- implementacja mrówek w Javie
- przeprowadzenie Warsztatowego Turnieju Mrówek Pracujących
- analiza wyników
Wymagania
- podstawowa znajomość programowania obiektowego i Javy
- zainstalowane na komputerze środowisko Eclipse (tak, trzeba mieć swój komputer!)
- znajomość pojęć z analizy, jak np. pochodna
- wiara w to, że czasem wystarczą przybliżone rozwiązania danego problemu
Zadania kwalifikacyjne
22.05 - wrzucono zadanie Gniewne Ptaki
23.05 - poprawiono treść zadania Gniewne Ptaki
26.05 - wrzucono zadania matematyczne
17.06 - dodano hinta
FAQ
- Czy rozwiązania zadań matematycznych mogą być spisane na kartce i zeskanowane?
Tak, można, ale czytelnie. Niemniej jednak kto nie pisał nigdy w LaTeX-u, polecam spróbować. Bardzo wygodnym środowiskiem do pisania w LaTeX-u jest TeXmaker, natomiast świetny tutorial można znaleźć na Wikiksiążkach: http://en.wikibooks.org/wiki/LaTeX/
- Czy w zad. 2) trzeba po prostu pokazać, że potrafi się używać wzorów na np. pochodną iloczynu itd., czy należy również te wzory wyprowadzać?
Wystarczy umiejętność korzystania z pochodnych.
- Mały hint do zadania Gniewne Ptaki: jeżeli ktoś korzysta z algorytmu genetycznego/ewolucyjnego, może sprawdzić różne metody krzyżowania i mutacji (tutaj widać różnicę):
- Czy zadanie 4) wymaga użycia rekurencji?
Być może się da rekurencyjnie, ale lepiej użyć kombinatoryki. Poza tym, istnieje wiele różnych kombinatorycznych rozwiązań!
- Czy w zadaniu 5) można używać bignumów?
Można, o ile się je samemu zaimplementuje. Takie rozwiązanie nie będzie błędne, ale do zrobienia zadania wystarczą zwykłe double, ale żeby je efektywnie wykorzystać, warto poczytać o reprezentacji liczb zmiennoprzecinkowych oraz o przeprowadzanych na nich operacjach. Przy ocenianiu będę brał pod uwagę 20 cyfr po przecinku :>