Programa

Teoria da Computação

Licenciatura Bolonha em Engenharia Informática e de Computadores - Taguspark

Licenciatura Bolonha em Engenharia de Telecomunicações e Informática

Programa

1. AUTÓMATOS FINITOS Autómatos finitos deterministas e não deterministas. Equivalência entre autómatos finitos deterministas e não deterministas. Linguagens regulares. Gramáticas regulares. Expressões regulares. Teorema da bombagem. 2. COMPUTABILIDADE As máquinas de Turing determinista e não determinista; o enumerador; equivalências. Conceito de função computável e de conjunto recursivamente enumerável. Conceito de oráculo. Conceito de redução. O problema da terminação (introdução à técnica da diagonalização). O Busy Beaver (como exemplo natural de função não computável). Teorema da recursão. Vírus. O teorema de Rice e suas aplicações. Postulado de Church-Turing (axioma da localidade). 3. AUTÓMATOS CELULARES Autómatos celulares. Ordens de magnitude. Grafos e grafos regulares. Circuitos booleanos. Regras locais e aplicações globais. Vizinhanças (Moore, von Neumann). Número de Wolfram de uma regra. Autómatos celulares lineares. Dinâmica linear. Autómatos semitotalistas. O Jogo VIDA de Conway. Universalidade computacional de VIDA. Diferença entre universalidade da computação e universalidade da construção. Auto-reprodução. Física e Biologia digitais. 4. COMPLEXIDADE Recursos computacionais: tempo, espaço, não determinismo, consultas. Teorema da contracção do espaço. Teorema da aceleração. Construtividade (espaço, tempo). Teorema de Savitch (introdução à técnica ''dividir para conquistar''). Teorema da hierarquia (espaço e tempo) (emprego da diagonalização). Classes computacionais: P, PSPACE, NP, EXPTIME, BPP. Conjuntos notáveis: SAT, #SAT, CVP, QBF, PRIMES. Relações estruturais (introdução do algoritmo de Dijkstra para a demonstração de que PSPACE está contido em EXPTIME; irrelevância do não determinismo em espaço superlogarítmico). Construção da hierarquia polinomial. BPP na hierarquia polinomial. Relações estruturais em aberto: a procura de novos métodos de prova. Malogro da relativização como técnica de prova: teoremas de Baker, Gill e Solovay.