Teoria da Computação (LEIC-Alameda)

Sumários das aulas teóricas

Turmas 10104, 10105, 10106

Docente: Pedro Resende
Horário: 2a 12h-13h GA1; 3a 9h-10h FA1; 5a 8h-9h GA4

26Set
Não houve aula: sessão de recepção aos alunos organizada pela coordenação da licenciatura.

T01-27Set
Apresentação: contactos, programa, bibliografia, avaliação, horários de esclarecimento de dúvidas. Descrição geral do programa: motivações e exemplos genéricos. Introdução à definição e reconhecimento de linguagens: autómatos finitos deterministas, sequência aceite e linguagem reconhecida. 

T02-29Set
Exemplos de autómatos finitos deterministas (afds). Afds parciais e totais. Definição algébrica de afd. Fecho de Kleene dum conjunto. Palavra vazia, concatenação de palavras, comprimento duma palavra. Função de transição estendida (ou iterada): definição preliminar para afds totais.  (Algumas notas sobre AFDS)

T03-03Out
Função de transição estendida (conclusão). Estados acessíveis, produtivos, úteis e inúteis. Remoção de estados inúteis dum afd D: o afd UT(D). Pares de estados equivalentes e pares de estados distinguíveis. 

T04-04Out
Critérios de detecção de pares de estados distinguíveis. O algoritmo de procura de estados distinguíveis (APED), ilustrado por meio de dois exemplos.

T05-06Out
O algoritmo de procura de estados distinguíveis (APED). Equivalência de afds. Utilização do APED para determinar se dois afds são equivalentes. Minimização de afds (início). 

T06-10Out
Minimização de afds (conclusão), definição de MIN(D) para um afd D. Isomorfismo e equivalência de afds. Autómatos finitos não deterministas e autómatos finitos não deterministas com movimentos-epsilon. Primeiros dois exemplos: 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. (Algumas notas sobre AFNDS)

T07-11Out
Autómatos finitos não deterministas. Sequências aceites e linguagem reconhecida. Exemplos com e sem movimentos-epsilon. Eliminação de movimentos-epsilon. 

T08-13Out
Transformação de AFNDs em AFDs. Comentários sobre matrizes e AFNDs: função de transição estendida através de multiplicação de matrizes. Introdução às gramáticas. Exemplos de linguagens não regulares. Definição geral de gramática. Gramáticas independentes do contexto e gramáticas regulares. (Algumas notas sobre gramáticas)

T09-17Out
Exemplos de gramáticas independentes do contexto. Demonstrações. Linguagem gerada por uma gramática. Construção, a partir dum autómato finito A, duma gramática regular que gera a linguagem L_A. 

T10-18Out
Construção, a partir duma gramática regular G, dum autómato finito que reconhece a linguagem L(G). Demonstração de que a linguagem 0^n1^n não é regular. Breve referência ao lema da bombagem. Autómatos de pilha (não deterministas) para reconhecer linguagens independentes do contexto: definição e exemplo para a linguagem 0^n1^n. 

T11-20Out
Algumas operações sobre linguagens: concatenação, união e fecho de Kleene. Expressões regulares e linguagem denotada por uma expressão regular. Leis algébricas das expressões regulares. Exemplos.  (Algumas notas sobre expressões regulares)

T12-24Out
Equivalência entre autómatos finitos e expressões regulares: passagem canónica de expressões regulares para autómatos finitos não deterministas. Introdução à lógica.

T13-25Out
Os três aspectos fundamentais da lógica: linguagem (sintaxe), significado (semântica) e dedução (teoria da prova). A linguagem da lógica de primeira ordem. Exemplos: os números reais; base de dados duma empresa. (Algumas notas sobre sintaxe e semântica da lógica de 1a ordem)

T14-27Out
O fragmento proposicional da lógica de primeira ordem. Semântica da lógica proposicional: valorações; fórmulas e conjuntos possíveis, válidos e contraditórios; consequência semântica. Teoria da prova em lógica proposicional: introdução ao método dos tableaux. Tableaux esgotados, fechados, conjuntos confutados. Exemplos. (Algumas notas sobre o sistema T)

T15-31Out
Semântica da lógica de primeira ordem: estruturas de interpretação; atribuições às variáveis; fórmulas possíveis, válidas ou contraditórias; consequência semântica. Exemplos. 

1Nov
Feriado 

T16-3Nov
Recapitulação de noções da aula de 31/10. Ilustração por meio da resolução no quadro de alguns exercícios: 1.6(a), 1.6(c), 1.7(a), 1.8(a)(i) e 1.9(a)(iii). 

T17-7Nov
Breve revisão do sistema de tableaux para a lógica proposicional. Sistema de tableaux para a lógica de primeira ordem. Cuidados a ter nas substituições de variáveis: variáveis livres, variáveis mudas, termos livres para variáveis em fórmulas. Exemplos.

T18-8Nov
Continuação da aula anterior. Correcção do sistema de tableaux

T19-10Nov
Realização do teste 2.

T20-14Nov
Extracção de valorações a partir de ramos abertos e esgotados de
tableaux proposicionais. Completude e decidibilidade do sistema T proposicional.

T21-15Nov
Extracção de modelos a partir de ramos abertos e esgotados de tableaux de
primeira ordem. Introdução ao estudo da resolução: a linguagem de programação
PROLOG, exemplos; literais e cláusulas proposicionais.

T22-17Nov
 A regra de inferência res (resolução) e a sua correcção. Derivações. Exemplos. Conversão de fórmulas proposicionais para a forma normal conjuntiva e aplicação da resolução a conjuntos finitos de fórmulas proposicionais quaisquer.  (Algumas notas sobre o sistema R)

T23-21Nov
Introdução ao estudo da computabilidade. Motivação e notas históricas. A máquina URM. Primeiro exemplo: soma de dois números naturais. (Algumas notas sobre a máquina URM)

T24-22Nov
Fluxogramas. Exemplos de funções e predicados calculados com a máquina URM: predicado "n é par"; predicado "m é maior ou igual do que n"; subtracção natural, com dois ciclos, recorrendo ao predicado anterior. 

T25-24Nov
Algumas definições formais: função computável, predicado decidível. Exemplo 1: subtracção de naturais como função (parcial) computável, através dum programa com apenas um ciclo. Exemplo 2: multiplicação, recorrendo ao programa da soma da aula anterior. Exemplo 3: 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 representados em base |I|+1; exemplo de programa para calcular a linguagem reconhecida por um afd com I={a,b,c} (início). 

T26-28Nov
Conclusão do exemplo da aula anterior. Representação em geral de afds por programas URM. Referência à representação de processadores digitais (arquitectura de Von Neumann) por programas URM. Início do estudo do problema da paragem. Exemplos de enumerações de N_0xN_0. A bijecção pi : N_0 x N_0 -> N_0 definida por pi(m,n)=2^m(2n+1)-1. 

T27-29Nov
Conjuntos numeráveis. Exemplos. Conjunto dos programas URM (e também o dos programas em qualquer linguagem de programação) como conjunto numerável. Demonstração pelo argumento diagonal de Cantor de que existem funções não computáveis. Indecidibilidade do problema da paragem. Aplicações práticas. 

T28-5Dez
Programas URM universais. Justificação da sua existência pelo postulado de Church-Turing: necessidade duma enumeração efectiva do conjunto dos programas. Enumeração efectiva do conjunto dos comandos: a função beta. (Algumas notas sobre enumeração efectiva do conjunto dos programas URM)

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

T30-12Dez
Números de Godel de programas URM (conclusão). Discussão sobre a inevitabilidade do problema da paragem: hierarquia de máquinas "super-URM" com oráculos de paragem e respectivos problemas da paragem; referência à relação com a aritmética de Peano e o primeiro teorema de incompletude de Godel. Outros exemplos de conjuntos indecidíveis: domínio e contradomínio duma função computável. (Algumas notas sobre predicados não decidíveis)

T31-13Dez
Teorema da parametrização (s-m-n). Exemplos de problemas indecidíveis: saber se uma função computável é identicamente nula; saber se dois programas calculam a mesma função. Teorema de Rice. FIM DAS AULAS TEÓRICAS DAS TURMAS 4, 5 E 6. 

15Dez
Não houve aula 

19Dez
Não houve aula 

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