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ą

Seminarium: trudność aproksymacji

Nazwa angielska (title in English): hardness of approximation
Prowadzący (lecturer): Jarosław Byrka
Liczba punktów (ECTS): 4
Liczba punktów 2007 (ECTS since 2007): 3
Rodzaj (type): seminarium
Rodzaj od 2007 (type since 2007): seminarium
Liczba godzin (hours in semester):
seminarium:30
Egzamin (exam): nie
Możliwe zajęcia w języku angielskim (can be taught in English): tak
Przedmiot zostal uaktualniony na biezacy rok (updated): tak
Semestr (semester): letni

Wymagania (prerequisites)

Opis (description)

O niektorych problemach od dawna wiadomo, ze sa NP-trudne, natomiast calkiem niedawno pokazano iz rownie trudno jest znalezc ich przyblizone rozwiazania. Dobrym przykladem jest 3-SAT, a dokladniej jego wersja optymalizacyjna MAX-3-Sat, ktora pyta o wartosciowanie spelniajace mozliwie najwieksza liczbe klauzul. Podczas gdy losowe wartosciowanie spelnia mniej wiecej 7/8 sposrod nich, okazuje sie, ze rozroznienie pomiedzy formulami spelnialnymi oraz takimi gdzie spelnic mozna jedynie 7/8 sposrod klauzul jest NP-trudne. To odkrycie ma rowniez ciekawe konsekwencje wykraczajace poza teorie aproksymacji.

Omawiane wyniki z pewnoscia nie beda latwe i oczywiste, ale postaramy sie powoli i systematycznie omowic najwazniejsze zagadnienia w tym temacie.

Program (program)

Lagodne wprowadzenie:

A potem juz bardzo konkretnie:

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

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