Teoria programowania liniowego i całkowitoliczbowego lato 2014/15
Język wykładowy | Angielski |
---|---|
Opiekun | Jarosław Byrka |
Liczba godzin | 30 (wyk.) 30 (ćw.) |
Rodzaj | I2.T - teoria inf. |
ECTS | 6 |
Polecany dla I roku | Nie |
Egzamin | Tak |
Tagi | AZ (algorytmika i złożoność obliczeniowa) |
Opis przedmiotu:
Układy nierowności liniowych można rozwiązywać wielomianowo. Na tych zajęciach spokojnie i dosc szczegolowo omowimy takie zagadnienia zwiazane z programami liniowymi jak: * LP duality * complementarity slackness * Farkas lemma * algorytm simplex * metode elipsoid * separation oracle * rozwiazywanie dużych (niewielomianowych) instancji * Hirsh conjecture Nastepnie omowily pewne aspekty programowania calkowitoliczbowego: * algorytm branch and bound * alg. branch and cut * algorytmy wielomianowe dla przypadku stalej liczby wymiarow * metody oparte o algebraiczne manipulacje na kracie punktow calkowitoliczbowych * algorytm LLL do redukcji bazy takiej kraty * problemy shortest latice vector i closest latice vector. Dodatkowo omowimy zastosowanie programowania liniowego do konstrukcji algorytmow aproksymacyjnych na przykladzie problemow Facility Location i min cost Steiner tree. W czesci kursu posluzymy sienotatkami: http://homepages.cwi.nl/~lex/files/dict.pdf Bedziemy rownież korzystać z książki: "Theory of Linear and Integer Programmin", Alexander Shrijver. Zajecia beda zakonczone egzaminem na oceneWykłady
ListaProwadzący | Termin zajęć | Limit | Zapisani | Kolejka |
---|---|---|---|---|
Jarosław Byrka
english |
śr 12:00-14:00 (s. 140) | 300 | 5 | 0 |
UWAGA! Wyższa liczba oznacza wyższy priorytet, po zapisaniu do grupy zostajemy usunięci z kolejek o niższym priorytecie.
Ćwiczenia
ListaProwadzący | Termin zajęć | Limit | Zapisani | Kolejka |
---|---|---|---|---|
Jarosław Byrka
english |
śr 14:00-16:00 (s. 140) | 20 | 5 | 0 |
UWAGA! Wyższa liczba oznacza wyższy priorytet, po zapisaniu do grupy zostajemy usunięci z kolejek o niższym priorytecie.
Konsultacje prowadzących:
Imię i nazwisko | Pokój | Konsultacje |
---|---|---|
Jarosław Byrka | 244 | Czwartek od 10 do 12 (prosze o kontakt przez e-mail dzien wczesniej) |