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ą

Optymalizacja kombinatoryczna

Nazwa angielska (title in English):
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): tak
Semestr (semester): zimowy

Wymagania (prerequisites)

Opis (description)

Sporo o matchingach (i ich uogolnieniach) (polska nazwa: skojarzenia). Matchingi w roznych postaciach wystepuja w bardzo wielu dziedzinach i maja zastosowania w szeregu praktycznych i teoretycznych problemow takich jak:

- przydzial zadan maszynom, - przydzial studentow szkolom, - znalezienie najciezszego/ najlzejszego pokrycia cyklowego w grafie, gdzie pokrycie cyklowe to taki zbior cykli, ze kazdy wierzcholek nalezy do dokladnie jednego cyklu, - obliczenie optymalnej drogi komiwojazera, - konstrukcja aukcji, - konstrukcja systemow glosowania, - znalezienie podgrafu, w ktorym kazdy wierzcholek ma zadany stopien.

Matchingi same w sobie przejawiaja bardzo ciekawa i ladna strukture, co doprowadzilo do powstania bogatej teorii (ktora wciaz sie rozwija, ostatnio najprezniej w zwiazku z zastosowaniami w ekonomii i teorii gier.)

Matroidy. (Przykładami matroidów sa: drzewa rozpinające, zbiory liniowo niezależnych kolumn macierzy, minimalny/maksymalny wagowo rozpinajacy podgraf, ktory zawiera dokladnie jeden cykl.)

T-joiny. Za pomocą T-joinów można np. sprawdzać, czy graf zawiera cykle o ujemnej wadze, co jak wiadomo przydaje się przy obliczaniu najkrótszych ścieżek.

Trochę programowania liniowego.

Parę innych problemów kombinatoryczno-optymalizacyjnych takich jak problem znalezienia 2 rozłacznych ścieżek łączących s i t.

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):