Sumários
16-02-2016
Apresentação do programa e objectivos do curso, bibliografia básica e regime de avaliação.
Linguagens Regulares. Autómatos finitos determinísticos e não determinísticos.
Course syllabus and objectives. Regular languages. Deterministic and non-deterministic finite automata.
Linguagens Regulares. Autómatos finitos determinísticos e não determinísticos.
Course syllabus and objectives. Regular languages. Deterministic and non-deterministic finite automata.
23-02-2016
Teorema de Myhill-Nerode. Lema da Repetição para linguagens regulares. Conversão de um autómato não determinístico num autómato determinístico.
Myhill-Nerode theorem. Pumping Lemma for regular languages. Conversion from a non-deterministic finite automaton in a deterministic finite automaton.
Myhill-Nerode theorem. Pumping Lemma for regular languages. Conversion from a non-deterministic finite automaton in a deterministic finite automaton.
26-02-2016
Operações para as quais a classes das linguagens regulares é fechada. Linguagens independentes de contexto. Noção de gramática independente de contexto. Derivação e árvore de derivação de uma palavra. Ambiguidade de gramáticas e de linguagens independentes de contexto.
Closed operations for the regular languages class. Context-free languages. Context-free grammars. Derivation and derivation tree of a word. Grammar and context-free language ambiguity.
Closed operations for the regular languages class. Context-free languages. Context-free grammars. Derivation and derivation tree of a word. Grammar and context-free language ambiguity.
1-03-2016
Linguagens não independentes de contexto. O lema da Repetição para linguagens independentes de contexto. Lema de Ogden.
Languages outside the class of Free Context Languages. Pumping Lemma for CFLs. The Ogden Lemma.
Languages outside the class of Free Context Languages. Pumping Lemma for CFLs. The Ogden Lemma.
4-03-2016
Aplicações do Lema da Repetição para CFLs. Operações para as quais a classe das CFL é fechada. Autómatos de pilha.
Examples of applications of the Pumping Lema for CFLs. Closed operations in CFL. Push-Down Automata.
Examples of applications of the Pumping Lema for CFLs. Closed operations in CFL. Push-Down Automata.
8-03-2016
Autómatos de pilha. Autómatos de pilha determinísticos e linguagens independentes de contexto determinísticas.
Push-Down Automata (PDA). Deterministic Push-Down Automata (DPDA) and Deterministic Context Free Languages (DCFL).
Push-Down Automata (PDA). Deterministic Push-Down Automata (DPDA) and Deterministic Context Free Languages (DCFL).
11-03-2016
Máquinas de Turing. Diversos modelos de Máquinas de Turing. Equivalência entre os modelos de Máquinas de Turing. Máquinas de Turing não determinísticas e a sua equivalência em termos de expressividade co o modelo determinístico. A tese de Church-Turing.
Turing Machines. Various versions of Turing Machines and its equivalence of power. Non-deterministic Turing Machines and its equivalence in terms of expressiveness to the deterministic model. The Church-Turing thesis.
Turing Machines. Various versions of Turing Machines and its equivalence of power. Non-deterministic Turing Machines and its equivalence in terms of expressiveness to the deterministic model. The Church-Turing thesis.
15-03-2016
Máquinas de Turing como reconhecedores e decisores. Linguagens Turing reconhecíveis (recursivamente enumeráveis). Linguagens decidíveis (recursivas). Enumeradores. Equivalência entre a potência dos enumeradores e dos reconhecedores. Exemplos de linguagens Turing reconhecíveis e decidíveis.
Turing Machines as recognisers and deciders. Turing recognisable languages (recursively enumerable). Decidable languages (recursive). Enumerators. Power equivalence between enumerators and recognisers. Examples of Turing recognisable languages and decidable languages.
Turing Machines as recognisers and deciders. Turing recognisable languages (recursively enumerable). Decidable languages (recursive). Enumerators. Power equivalence between enumerators and recognisers. Examples of Turing recognisable languages and decidable languages.
18-03-2016
Argumento diagonal de Cantor. Existência de linguagens não Turing reconhecíveis. O problema da aceitação em TM ($A_{TM}$) é não decidível.
Cantor’s diagonal argument. Existence of not Turing recognisable languages. The word problem form Turing Machines ($A_{TM}$) is undecidable.
Cantor’s diagonal argument. Existence of not Turing recognisable languages. The word problem form Turing Machines ($A_{TM}$) is undecidable.
29-03-2016
Exemplos e exercícios de revisão.
Examples and practical exercises.
Examples and practical exercises.
01-04-2016
Realização do teste de avaliação.
Midterm test.
Midterm test.
05-04-2016
O problema da paragem. Linguagens co-reconhecíveis. A linguagem $HALT_{TM}$ é indecidível e co-irreconhecível. As linguagens $E_{TM}$ e $REGULAR_{TM}$ são indecidíveis. O teorema de Rice. A linguagem $E_{TM}$ é indecidível.
The Halting problem. Co-Recognisable languages. The language $HALT_{TM}$ is undecidable and co-unrecognisable. Languages $E_{TM}$ and $REGULAR_{TM}$ are undecidable. Rice’s Theorem. The language $E_{TM}$ is undecidable.
The Halting problem. Co-Recognisable languages. The language $HALT_{TM}$ is undecidable and co-unrecognisable. Languages $E_{TM}$ and $REGULAR_{TM}$ are undecidable. Rice’s Theorem. The language $E_{TM}$ is undecidable.
08-04-2016
Exemplos e exercícios sobre linguagens não decidíveis.
Examples and exercises on non decidable languages.
Examples and exercises on non decidable languages.
12-04-2016
Maquinas de Turing com fitas limitadas ($LBA$). $A_{LBA}$ é decidível mas $E_{LBA}$ é indecidível. Noção de história de computação positiva de uma máquina de turing e um input. $ALL_{CGF}$ é indecidível.
Linear Bounded Turing Machines ($LBA$). $A_{LBA}$ is decidable but $E_{LBA}$ is undecidable. Notion of accepting history of computation of a $TM$ with a given input. $ALL_{CFG}$ is undecidable.
Linear Bounded Turing Machines ($LBA$). $A_{LBA}$ is decidable but $E_{LBA}$ is undecidable. Notion of accepting history of computation of a $TM$ with a given input. $ALL_{CFG}$ is undecidable.
15-04-2016
O Problema da Correspondência de Post e a sua indecidibilidade. Funções computáveis.
Post Correspondence Problem is undecidable. Computable functions.
Post Correspondence Problem is undecidable. Computable functions.
19-04-2016
O problema do “Busy Beaver” e a demonstração da sua incomputabilidade. Reduções por funções computáveis. $EQ_{TM}$ é irreconhecível e co-irreconhecível. O Teorema da Recursão.
Busy Beaver problem and the proof that it is uncomputable. Reductions through computable mappings. $EQ_{TM}$ is unrecognisable and co-unrecognisable. The Recursion Theorem.
Busy Beaver problem and the proof that it is uncomputable. Reductions through computable mappings. $EQ_{TM}$ is unrecognisable and co-unrecognisable. The Recursion Theorem.
22-04-2016
Exercícios com reduções por funções computáveis.
Resolution of problems with computational map reductions.
Resolution of problems with computational map reductions.
26-04-2016
Introdução à Complexidade Kolmogorov. O número Omega de Chaitin. Lemas de repetição alternativos usando Complexidade Kolmogorov.
Introduction to Kolmogorov Complexity. Chaitin’s Omega number. Alternative pumping lemmas using Kolmogorov Complexity.
Introduction to Kolmogorov Complexity. Chaitin’s Omega number. Alternative pumping lemmas using Kolmogorov Complexity.
29-04-2016
Exercícios usando o Teorema da Recursão.
Resolution of problems using Recursion Theorem.
Resolution of problems using Recursion Theorem.
10-05-2016
Complexidade computacional. A classe de complexidade P.
Computacional Complexity. The complexity class P.
Computacional Complexity. The complexity class P.
13-05-2016
Exercícios sobre linguagens P.
Resolution of problems languages P.
Resolution of problems languages P.
17-05-2016
A classe $\mathbf{NP}$. $HAMPATH\in\mathbf{NP}$. Noção de redução polinomial entre linguagens. Noção de uma linguagem $\mathbf{NP}$-completa. Teorema de Cook-Levin ($SAT$ é $\mathbf{NP}$-completa).
The $\mathbf{NP}$ class. $HAMPATH\in\mathbf{NP}$. Notion of polynomial reduction of a language to another. Notion of $\mathbf{NP}$-completness. Cook-Levin Theorem ($SAT$ is $\mathbf{NP}$-complete).
The $\mathbf{NP}$ class. $HAMPATH\in\mathbf{NP}$. Notion of polynomial reduction of a language to another. Notion of $\mathbf{NP}$-completness. Cook-Levin Theorem ($SAT$ is $\mathbf{NP}$-complete).
20-05-2016
Exercícios sobre linguagens NP.
Resolution of problems languages NP.
Resolution of problems languages NP.
24-05-2016
$VERTEXCOVER$, $HAMPATH$, $UHAMPATH$ e $SUBSETSUM$ são NP-completos.
$VERTEXCOVER$, $HAMPATH$, $UHAMPATH$ e $SUBSETSUM$ are NP-complete.
$VERTEXCOVER$, $HAMPATH$, $UHAMPATH$ e $SUBSETSUM$ are NP-complete.
27-05-2016
Exercícios sobre linguagens NP-completas
Resolution of problems on NP-complete languages.
Resolution of problems on NP-complete languages.
31-05-2016
Classe $PSPACE$ .Teorema de Savitch. Linguagens $PSPACE$-completas. As classes $L$ e $NL$. Reduções logarítmicas.
$PSPACE$ class. Savitch Theorem. $PSPACE$-comple languages. $L$ and $NL$ classes. Logarithmic reductions.
$PSPACE$ class. Savitch Theorem. $PSPACE$-comple languages. $L$ and $NL$ classes. Logarithmic reductions.
03-06-2016
Exercícios sobre linguagens NP-completas
Resolution of problems on NP-complete languages.
Resolution of problems on NP-complete languages.