Optymalizacja kombinatoryczna

Treści kształcenia

Algorytmy programowania dynamicznego dla problemów: plecakowego, podziału zbioru o złożoności pseudowielomianowej. Złożoność obliczeniowa problemów optymalizacyjnych. Algorytmy aproksymacyjne i trudność problemów aproksymacji. Algorytmy do wyznaczania najkrótszych dróg w grafie. Przepływy w sieciach. Wyznaczanie maksymalnego skojarzenia. Minimalne drzewo rozpinające. Problem kolorowania grafu. Pojęcie matroidu. Wybrane problemy szeregowania zadań.

Efekty kształcenia - umiejętności i kompetencje

Student zna wybrane problemy optymalizacji kombinatorycznej, algorytmy rozwiązujące te problemy oraz potrafi zastosować te algorytmy do rozwiązania bardziej złożonych problemów rzeczywistych. Potrafi skonstruować algorytm przybliżony (heurystyczny) dla problemu trudnego obliczeniowo.