Informacje ogólne

Typ:monograficzny

Założenia i cele przedmiotu

Przedmiotem wykładu będzie wprowadzenie do teorii nierozstrzygalności z przeglądem zastosowań w informatyce teoretycznej.

Program

1. Intuicyjne pojęcie obliczalności i formalizacja pojęcia algorytmu. Modele algorytmów: system Posta, algorytmy Markowa, funkcje rekurencyjne, gramatyki struktur frazowych. Hipoteza Churcha.
2. Problemy nierozstrzygalne, przykłady w informatyce.
3. Pojecie redukowalności – typu jeden-do-jeden, jeden-do-wiele, tablicowej, Turinga. Stopnie nierozstrzygalności. Struktura stopni. Stopnie wybranych problemów nierozstrzygalnych.
4. Obliczenia z wyroczniami. Twierdzenie Friedberga-Mucznika o istnieniu zbiorów nieporównywalnych. Metoda priorytetu.

Sposób zaliczenia

egzamin

Umiejętności i kompetencje

Zakłada się, że student nabędzie intuicje związane z pojęciem obliczalności i umiejętność oceny, czy dany problem jest rozstrzygalny, czyli czy istnieje możliwość stworzenia algorytmu rozwiązującego problem

Literatura

Podstawowa:

• H. Rodgers – Theory of recursive functions and effective computability, MIT Press 1987
• J. E. Hopcroft, R. Motwani, J. D. Ullman, Introduction to Automata Theory, Languages, and Computation, Prentice Hall 2007
• http://infolab.stanford.edu/~ullman/ialc.html

Uzupelniajaca:
J. M. Brady – Informatyka teoretyczna w ujęciu programistycznym, WNT 1983