Obliczalność i nierozstrzygalność


Informacje ogólne

Typ:monograficzny
Kierunek:Informatyka studia drugiego stopnia
Semestr:letni
Wymiar zajęć:30h wykładu + 30h ćwiczeń
Punkty ECTS:5

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