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.