Teoria da Computação (LEIC-Alameda)


Sumários das aulas teóricas

Turmas 10101, 10102, 10103

Docente: Paula Gouveia
Horário: 3a 10h-11h FA3; 4a 12h-13h FA3; 5a 10h-11h FA3


T01-27Set
Apresentação: conteúdo, bibliografia e avaliação


T02-28Set
Autómatos finitos deterministas (afd). Exemplos de aplicações (e.g. processadores de texto). Exemplos de afds (representação através de um grafo orientado e etiquetado).


T03-29Set
Mais exemplos de afds. Definição algébrica de afd. Função de transição total vs função de transição parcial. Exemplos.  (Algumas notas sobre AFDS)


T04-04Out
Fecho de Kleene dum conjunto. Palavra vazia, concatenação de palavras, comprimento duma palavra. Função de transição estendida de afd. Exemplos. Palavra aceite e linguagem reconhecida por afd. Linguagens regulares. Estados produtivos, acessíveis, úteis e inúteis.


5Out
Feriado


T05-06Out
Estados distinguíveis e esatdos equivalentes. Exemplos. Algoritmo de procura de estados distinguíveis - APED  (início).


T06-11Out
Algoritmo de procura de estados distinguíveis - APED  (conclusão). Exemplos. Mininização de afds: construção de MIN(D). Exemplo.


T07-12Out
Esboço de algoritmo para calcular estados acessíveis de um afd. Autómatos finitos não deterministas (afnds). Exemplos de afnds com e sem movimentos epsilon. Noção informal de sequência aceite e linguagem gerada por afnd. Exemplos. (Algumas notas sobre AFNDS)


T08-13Out
Afnds que reconhecem as sequências de 0s e 1s com 1 na penúltima posição e 1 na antepenúltima posição, respectivamente. Comparação com afds para as mesmas linguagens. Construção de afd equivalente a um afnd (sem movimentos epsilon) dado. Eliminação dos movimentos epsilon.


T09-18Out
Gramáticas: motivação, definição, gramáticas independentes do contexto e gramáticas regulares. Demonstração de sequência numa gramática. Linguagem gerada por gramática. Exemplos de gramáticas independentes do contexto e regulares. (Algumas notas sobre gramáticas)


T10-19Out
Mais exemlos de gramáticas. Construção de afnd para a linguagem gerada por gramática regular; construção de gramática regular que gera a linguagem reconhecida por afnd. Referência à existência de linguagens não regulares: a linguagem 0^n1^n. Autómato de pilha para a linguagem 0^n1^n.


T11-20Out
Conclusão da aula anterior: referência ao lema da bombagem. Expressões regulares: aplicações, conjunto das expressões regulares sobre um alfabeto. Linguagem denotada por expressão regular. Exemplos. (Algumas notas sobre expressões regulares)


T12-25Out
Conclusão da aula anterior: equivalência de expressões regulares, exemplos. FIM DA 1A PARTE DA MATÉRIA.


T13-26Out
Introdução à lógica. Motivação. Lógica de primeira ordem: alfabeto de 1a ordem. (Algumas notas sobre sintaxe e semântica da lógica de 1a ordem)


T14-27Out
Conjunto dos termos e conjunto das fórmulas sobre  alfabeto de 1a ordem. Semântica do fragmento proposicional: valoração, fórmulas possíveis, contraditórias e válidas, consequência semântica.


1Nov
Feriado


T15-2Nov
Conclusão da aula anterior: exemplos de  fórmulas proposicionais possíveis, contraditórias e válidas: consequência semântica.


T16-3Nov
Sistema dedutivo T (sistema de tableaux). Regras de inferência para o fragmento proposicional. Ramo fechado,  tableau fechado, conjunto confutado, teorema de T e consequência em T. Referência à relação entre teoremas de T e fórmulas válidas e entre consequência em T e consequência semântica.  Exemplos. (Algumas notas sobre o sistema T)


T17-8Nov
Semântica das fórmulas de primeira ordem: estrutura de interpretação, atribuição, satisfação de fórmula por estrutura de interpretação e atribuição (fórmulas sem quantificadores). Exemplos.


T18-9Nov
Realização do teste 2


T19-10Nov
Conclusão aula T17: satisfação de fórmula por estrutura de interpretação e atribuição (fórmulas com quantificadores). Exemplos.


T20-15Nov
Sistema T: regras relativas aos quantificadores universal e existencial. Exemplos.


T21-16Nov
Correcção das regras de inferência do sistema T. Prova da correcção do sistema T. Extracção de modelos de ramos abertos e esgotados. Referência à completude do sistema T e esboço da prova para o caso do fragamento proposicional.


T22-17Nov
Sistema R (fragmento proposicional): cláusulas, regra res, derivação em R, conjunto incorente, correcção da regra res, correcção do sistema R. Exemplos. (Algumas notas sobre o sistema R)


T23-22Nov
A linguagem de programação PROLOG. Exemplos.


T24-23Nov
Introdução ao estudo da computabilidade. Motivação e notas históricas. A máquina URM. Primeiro exemplo: soma de dois números naturais. 


T25-24Nov
A máquina URM: registos, comandos URM, programas URM. Exemplos de programas para a máquina URM: programas que calculam (i) a função binária que a x e y faz corresponder x+y e a função ternária que a x,y, z faz corresponder x+y-z se y>=z e não está definida caso contrário;  (ii) a função binária que a x e y faz corresponder max(x,y); (iii) a função característica do predicado "x<y". (Algumas notas sobre a máquina URM)


T26-29Nov
Exemplos de programas para a máquina URM: programas que calculam (i) a função binária que a x e y faz corresponder x-y se x>y e 0 caso contrário, com 2 ciclos; (ii) a mesma função mas com apenas  um ciclo). Função de 1 argumento calculada por programa URM. Generalização ao caso de k argumentos. Alguns detalhes relativos ao emulador da máquina URM disponibilizado. Utilização de oráculos. Utilização do oráculo SUM para construir programa que calcula a função binária que a x e y faz corresponder x.y.


T27-30Nov
Predicados decidíveis. Exemplos: (i) o predicado "x é primo" (usando o oráculo MOD);  (ii) reconhecimento de linguagens: a linguagem reconhecida por um autómato finito determinista sobre o alfabeto I como um predicado sobre os naturais, através da interpretação das palavras de I* como naturais (AFD que reconhece a linguagem sobre {a,b} constituída pelas sequências que têm um número ímpar de b's).


T28-6Dez
Conjuntos numeráveis. Exemplos. Conjunto dos programas URM (e também o dos programas em qualquer linguagem de programação) como conjunto numerável. O conjunto dos programas URM é efectivamente numerável (início): bijecções beta, pi e xi.  (Algumas notas sobre enumeração efectiva do conjunto dos programas URM)


T29-7Dez
Realização do teste 4. 


T30-13Dez
O conjunto dos programas URM é efectivamente numerável (início): bijecções tau e gamma.  Exemplos.


T31-14Dez
Enumeração das funções naturais unárias URM-computáveis. Referência ao argumento da diagonal de Cantor e sua utilização na prova de que o intervalo [0,1[ não é numerável. Construção de uma função natural unária não URM-computável.   (Algumas notas sobre predicados não decidíveis)


T32-15Dez
Prova de que o problema da paragem não é URM-decidível. Prova de que o predicado "n pertence ao contradomínio da função unária calculada pelo programa m" não decidível.


T33-20Dez
Realização do teste 5.