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ą

Projektowanie sieci: algorytmy oparte o programy liniowe

Nazwa angielska (title in English): LP-based algorithms for network design
Prowadzący (lecturer): Jarosław Byrka
Liczba punktów (ECTS): 6
Liczba punktów 2007 (ECTS since 2007): 9
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)

Bedziemy rozwazac problemy instalowania przepustowosci na krawedziach grafu celem umozliwienia przesylu danych zgodnie ze spodziewanym zapotrzebowaniem na transfer. Do tej kategorii mozna zaliczyc na przyklad problem minimalnego drzewa Steinera, w ktorym nalezy polaczyc w jedna spojna skladowa dany zbior wierzcholkow zwany terminalami. Zazwycazaj dazymy do minimalizacji lacznego kosztu zainstalowanych polaczen.

Problemy tago typu sa najczesciej NP-trudne, dlatego skupiamy sie na konstrukcji algorytmow aproksymacyjnych, czyli algorytmow, ktore w czasie wielomianowym dostarczaja rozwiazan nie wiele drozszych od optimum. Jako ograniczenia dolnego na koszt rozwiazania optymalnego najczesciej uzywamy rozwiazania ulamkowego odpowiedniego programu liniowego.

Program (program)

Problems:

LP-relaxations:

Related graph constructions:

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