Teoria obliczeń i złożoności obliczeniowej 1

RSS

Cel przedmiotu

Zapoznanie studentów z formalnymi modelami obliczeń, metodami analizy złożoności czasowej i pamięciowej problemów obliczeniowych, wskazanie granic obliczalności.

Program wykładu

Języki oraz problemy decyzyjne. Maszyna Turinga (deterministyczna i niedeterministyczna, modyfikacje). Pojęcie obliczalności na maszynie Turinga. Inne modele obliczeń. Teza Turinga-Churcha. Problemy nierozstrzygalne. Problem stopu. Pojęcie redukcji między problemami obliczeniowymi. Wykorzystanie redukcji w dowodach nierozstrzygalności. Złożoność czasowa dla deterministycznej maszyny Turinga. Złożoność czasowa niedeterministycznej maszyny Turinga. Klasy P i NP. Pojęcie NP-zupełności. Problemy NP-zupełne. Przykłady algorytmów dla problemów NP-zupełnych. Pojęcie słabej NP-zupełności. Własności problemów NP-zupełnych oraz przykładowe próby rozwiązania problemu P versus NP. Klasa NPI oraz twierdzenie Ladnera.

Charakterystyka pozostałych zajęć

Prowadzone są ćwiczenia tablicowe, których celem jest ugruntowanie i poszerzenie wiedzy z wykładów. W trakcie ćwiczeń studenci rozwiązują zadania dotyczące teorii obliczeń oraz złożoności obliczeniowej (np. piszą ˛ programy maszyn Turinga, dowodzą nierozstrzygalności zadanych problemów, dowodzą własności modeli obliczeń i problemów obliczeniowych).

Bibliografia

1. M. Sipser: Introduction to the theory of computation. WNT, Warsaw 2009
2. C.H. Papadimitriou: Computational complexity. WNT, Warsaw 2002
3. DP Bovet, P. Crescenzi: Introduction to the Theory of Complexity. Prentice Hall, 1994
4. I. Wegener: Complexity Theory, Springer, 2005
5. Kościelski A.: Theory of computation. Publishing House of the University of Wroclaw, Wroclaw 1997

Wszelkie prawa zastrzeżone © 2010 Katedra Informatyki   |   Akademia Górniczno-Hutnicza   |   Realizacja Creative Bastards