Co bylo na wykladzie ?

16. 02. 2005
Wprowadzenie - trudnosc obliczeniowa rozumiana empirycznie. Powszechnosc problemow trudnych obliczeniowo.
W miare przyspieszania dzialania komputerow znaczenie szybkich algorytmow rosnie - nie maleje.
Paradokslana natura pojecia zlozonosci: nadmiar struktury lub jej brak.
Podstatowe pojecia: problemy decyzyjne, zlozonosc czasowa i pamieciowa maszyny Turinga, zlozonosc problemu decyzyjnego.
Twierdzenie Sipsera o tym, ze maszyne Turinga dzialajaca w pamieci ograniczonej przez funkcje liczbowa S(n) mozna symulowac maszyna dzialajaca
w tej samej pamieci, ktora ponadto zatrzymuje sie dla kazdych danych.

23. 02. 2005
Przypomnienie: uniwersalna maszyna Turinga


2. 03. 2005


9. 03. 2005


16. 03. 2005