Planeamento

Aulas Teóricas

Aula Teórica 1

Apresentação da disciplina: método de avaliação, programa e bibliografia.

Aula Teórica 2

Computabilidade: motivação. Tese de Church-Turing. Alfabeto, palavra sobre alfabeto, palavra vazia, comprimento de palavra, linguagem sobre um alfabeto. Descrição informal de uma Máquina de Turing.

Aula Teórica 3

Exemplos de máquinas de Turing: (i) máquina cuja linguagem é o conjunto das palavras sobre  \(\{0,1\}\) que terminam em 1, (ii) máquina cuja linguagem é o conjunto das palavras sobre \(\{a,b\}\) do tipo \(a^nb^n\), (iii) máquina cuja linguagem é o conjunto das palavras sobre \(\{a,b,c\}\) do tipo \(a^nb^mc^{n+m}\) (certificados da soma).

Aula Teórica 4

Especificação algébrica de Máquina de Turing. Exemplo. Classificador. Linguagem decidida por máquina de Turing. Linguagens semidecidíveis e decidíveis. Máquina de Turing como calculadora de funções. Exemplo: máquina de Turing que calcula a soma de naturais (representação unária dos naturais).

Aula Teórica 5

Máquina de Turing com fita ilimitada à esquerda e à direita. Máquina de Turing com transições S. Máquina de Turing multifita. Exemplo: máquina de Turing com duas fitas que reconhece a linguagem das palavras do tipo \(a^nb^n\) com \(n\in\mathbb{N}_0\). Esboço da equivalência entre estas variantes e a noção de máquina de Turing definida anteriormente.

Aula Teórica 6

Conclusão da aula anterior: esboço da conversão de uma máquina de Turing multifita numa máquina de Turing com uma fita.  Máquina de Turing não determinista. Exemplo. Referência à equivalência entre máquinas de Turing deterministas e não deterministas.

Aula Teórica 7

Função injetiva, sobrejetiva e bijetiva. Conjuntos com o mesmo cardinal e conjunto com cardinal inferior ao de outro conjunto. Transitividade da equipotência de conjuntos. Conjunto numerável. Demonstração de que os conjuntos \(\mathbb{P}\) (dos números pares não negativos), \(\mathbb{N}\), \(\mathbb{Z}\), \(\mathbb{Q}\) e \(\{0,1\}^*\) são numeráveis.

Aula Teórica 8

Conjuntos numeráveis (conclusão): qualquer subconjunto infinito de \(\mathbb{N}_0\) é numerável. Método da diagonalização: aplicação à prova de que o conjuntos dos reais não é numerável.

Aula Teórica 9

O cardinal do conjunto dos naturais é menor que o do conjunto \({\cal B}\) das palavras binárias infinitas . O conjunto \({\cal B}\) é equipotente ao conjunto das linguagens sobre um qualquer alfabeto. O conjunto das máquinas de Turing é numerável. Prova da existência de linguagens não reconhecidas por nenhuma máquina de Turing usando argumentos de cardinalidade.

Aula Teórica 10

Conclusão da aula anterior.  Prova da existência de funções totais de \(\{0,1\}^*\) para \(\{0,1\}^*\) não computáveis usando argumentos de cardinalidade.

Aula Teórica 11

Máquina de Turing Universal.  Linguagem \(A_{TM}\).

Aula Teórica 12

Demonstração de que a linguagem \(A_{TM}\) é semi-decidível mas não é decidível. Demonstração de que a linguagem complementar de \(A_{TM}\) não é semi-decidível.

Aula Teórica 13

Sequências de hailstone e conjectura de Collatz.  Demonstração de que a linguagem \(HALT_{TM}\) (problema da paragem) não é decidível. Demonstração que  a linguagem \(EQ_{TM}\) (problema da igualdade de linguagens) não é decidível, assumindo como provado que o problema \(E_{TM}\) (problema da linguagem vazia) não é decidível.

Aula Teórica 14

Demonstração de que a linguagem \(E_{TM}\) (problema da linguagem vazia) não é decidível. Noção de redução de uma linguagem a outra linguagem.

Aula Teórica 15

Revisões e esclarecimento de dúvidas.

Aula Teórica 16

Propriedades da noção de redução \(L_1\leq_m L_2\) entre linguagens sobre um mesmo alfabeto.

Aula Teórica 17

Teorema de Rice: demonstração e exemplos de aplicação.

 

Aula Teórica 18

Teorema da recursão: demonstração e exemplo de aplicação (existência de vírus).

Aula Teórica 19

Complexidade computacional: computabilidade com recursos limitados. Tempo de uma máquina de Turing e espaço de uma máquina de Turing. Exemplo. Notação assimptótica O e notação assimptótica \(\Theta\). Exemplos. Propriedades.

Aula Teórica 20

Conclusão da aula anterior.

Aula Teórica 21

Classes de linguagens  TIME(t) e SPACE(s), P, EXPTIME, PSPACE. Exemplos de linguagens em P e de linguagens que não estão em P. Problemas em aberto (decomposição em factores primos). Demonstração de que P\(\subseteq\) PSPACE.

Aula Teórica  22

Classes de funções PF e PSPACEF. Redução polinomial. Fecho de P, SPACE e NP para a redução polinomial. Demonstração do caso PSPACE.

Aula Teórica 23

Tese de Cobham e versão forte do postulado de Church-Turing. Referência à conversão de máquinas de Turing multifita em máquinas de Turing com uma fita equivalentes com incremento polinomial no tempo. Breve referência à conversão de outros modelos de computação deterministicos a uma máquina de Turing. Máquina de Turing não determinística: palavras aceites e linguagem reconhecida. Classificador não determinístico. Exemplo. As classes NTIME(t), NSPACE(s), NP e NPSPACE. Referência às inclusões P\(\subseteq\) NP\(\subseteq\) PSPACE=NPSPACE\(\subseteq\) EXPTIME e aos problemas em aberto relativos às inclusões estritas.

Aula Teórica 24

Referência à conversão de máquinas de Turing não determinísticas em máquinas de Turing determinísticas com incremento exponencial no tempo. Referência ao teorema de Savitch. Linguagens C-difíceis e  C-completas. Relevância das linguagens NP-completas. Exemplos de linguagens NP-completas (SAT e existencia de caminhos hamiltonianos num grafo). Funções construtíveis no espaço. Teoema de hierarquia no espaço.

Aula Teórica 25

Demonstração de que a função \(f:\mathbb{N}\to \mathbb{N}\) dada por \(f(n)=n\) é construtível no espaço. Funções construtíveis no tempo. Teorema de hierarquia no tempo. Demonstração de que a conversão de máquinas de Turing multifita em máquinas de Turing com uma fita equivalentes se pode fazer com custo quadrático.

Aula Teórica 26

Conclusão da aula anterior.

Aula Teórica 27

Esclarecimento de dúvidas sobre a matéria em avaliação no teste 2. Resolução de alguma das perguntas do teste 2 tipo.

Aula Teórica 28

Realização do teste 2.