Oferta dydaktyczna Instytutu Informatyki

Poniższa lista przedstawia przedmioty, które są uczone w Instytucie Informatyki, niektóre z nich co roku, niektóre z mniejszą częstotliwością Każdy student Instytutu Informatyki studiuje wg indywidualnego toku studiów, wybierając (zgodnie z pewnymi zasadami) z tej listy swoje przedmioty.

Jeżeli zastanawiasz się nad studiami u nas, jeżeli chcesz wiedzieć, czy na Uniwersytecie można zostać inżynierem, jeżeli interesuje Cię 1000 zł stypendium miesięcznie - zapraszamy na naszą stronę główną

Algorytmy aproksymacyjne

Nazwa angielska (title in English): Approximation algorithms
Prowadzący (lecturer): Katarzyna Paluch
Liczba punktów (ECTS): 9
Liczba punktów 2007 (ECTS since 2007): 6
Rodzaj (type): zaawansowany
Rodzaj od 2007 (type since 2007): informatyczny.I2
Liczba godzin (hours in semester):
wykład:30
ćwiczenia:30
Egzamin (exam): tak
Możliwe zajęcia w języku angielskim (can be taught in English): tak
Przedmiot zostal uaktualniony na biezacy rok (updated): nie
Semestr (semester): letni

Wymagania (prerequisites)

Opis (description)

Mnóstwo problemów na jakie można łatwo natknąć się w rzeczywistości jest NP-trudnych. Dla nich nie istnieją algorytmy działające w sensownym (wielomianowym) czasie i podające optymalne rozwiązania. Jakieś rozwiązania tych problemów są jednak potrzebne (a często wręcz niezbędne). Można a) napisać algorytm, który oblicza problem dokładnie, zaimplementować go i uruchomić na potrzebnych danych i czekać na odpowiedź, która w najgorszym razie pojawi się za np. 10 lat, a w najlepszym za np. rok. (To zależy od problemu, danych, algorytmu.) b) znaleźć szybko jakiekolwiek rozwiązanie, być może 1000 razy gorsze od optymalnego. c) skonstruować algorytm, który działa w miarę szybko (ale może wolniej niż metoda z b)) i który oblicza rozw. kt. jest co najwyżej np. 2 razy gorsze niż optymalne.

Program (program)

1. Algorytmy aproksymacyjne kombinatoryczne m.in. dla problemów -set cover, -komiwojażera, -najkrótszego superstringu, -pokrycia wierczhołkowego, -bin packing, -schedulingu.

2. Algorytmy aproksymacyjne oparte na różne sposoby o programowanie liniowe. (Programowania liniowego nie trzeba znać przychodząc na wykł.)

3. Nieaproksymowalność niektórych problemów.

Literatura (references)

Jeżeli jesteś zainteresowany studiowaniem w naszym instytucie, zapraszamy na stronę poświęconą tegorocznej rekrutacji.

Nazwa użytkownika (user name):
Hasło (password):