Modelowanie matematyczne - złożoność obliczeniowa, teoria a praktyka
Wykładowca: dr inż. Krzysztof Bryś
Wydział Matematyki i Nauk Informacyjnych
Termin i miejsce: 12 stycznia 2015 r. g. 16:15-17:30, budynek CZIiTT, sala 4.01
W trakcie wykładu omówione zostaną teoretyczne aspekty złożoności obliczeniowej, zarówno czasowej, jak i pamięciowej. Przedstawione zostaną metody wyznaczania i porównywania złożoności obliczeniowej algorytmów. Omówione zostaną podstawowe klasy złożoności obliczeniowej, aktualny stan wiedzy dotyczący zależności zachodzących między nimi oraz ograniczenia z tego wynikające. Zaprezentowany będzie problem milenijny „P vs NP” oraz przedstawione zostaną teoretyczne i praktyczne skutki pozytywnej odpowiedzi na pytanie „Czy P=NP ?”. Omówione zostaną przykłady ważnych problemów obliczeniowych, dla których nie jest możliwe, według obecnego stanu wiedzy, znalezienie szybkich z punktu widzenia teoretycznego algorytmów je rozwiązujących. Teoretyczne aspekty złożoności obliczeniowej zostaną przeciwstawione praktyce. Posłużą do tego pewne charakterystyczne przykłady problemów obliczeniowych, do rozwiązywania których wykorzystuje się teoretycznie gorsze algorytmy niż teoretycznie najlepsze znane.
