Mówca
Opis
W matematyce oraz informatyce bada się różne rodzaje problemów optymalizacyjnych. Dla wielu z nich udało się opracować efektywne algorytmy, które zawsze pozwalają znaleźć optymalne rozwiązanie. Są jednak i takie, dla których nie znamy algorytmów o zadowalającym czasie działania. Co więcej, mamy poważne powody, żeby przypuszczać, że dla niektórych problemów takie algorytmy w ogóle nie istnieją. Na szczęście okazuje się, że nawet w przypadku bardzo trudnych obliczeniowo problemów nie wszystko jest stracone. Mogą bowiem istnieć dla nich szybkie algorytmy, które zawsze dają rozwiązanie w pewnym określonym sensie bliskie optymalnemu. Są to tak zwane algorytmy aproksymacyjne. W moim referacie chciałbym opowiedzieć o tej fascynującej dziedzinie algorytmiki. Przyjrzymy kilku klasycznym problemom optymalizacji dyskretnej, takim jak problem plecakowy, problem komiwojażera czy problem pokrycia wierzchołkowego. Zastanowimy się, dla których z nich istnieją algorytmy aproksymacyjne, przeanalizujemy ich działanie oraz udowodnimy ich poprawność. Przekonamy się, że są problemy, które można aproksymować z dowolną dokładnością, oraz takie, dla których prawdopodobnie wcale nie jest to możliwe. Przy okazji zetkniemy się z tym, co algorytmicy lubią najbardziej – analizą algorytmów, teorią grafów i złożonością obliczeniową.
