Rogério Reis


Err and err and err again, but less and less and less.


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.
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.
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.
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.
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.
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).
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.
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.
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.
29-03-2016
Exemplos e exercícios de revisão.

Examples and practical exercises.
01-04-2016
Realização do teste de avaliação.

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.
08-04-2016
Exemplos e exercícios sobre linguagens não decidíveis.

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.
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.
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.
22-04-2016
Exercícios com reduções por funções computáveis.

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.
29-04-2016
Exercícios usando o Teorema da Recursão.

Resolution of problems using Recursion Theorem.
10-05-2016
Complexidade computacional. A classe de complexidade P.

Computacional Complexity. The complexity class P.
13-05-2016
Exercícios sobre linguagens 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).
20-05-2016
Exercícios sobre linguagens 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.
27-05-2016
Exercícios sobre linguagens NP-completas

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.
03-06-2016
Exercícios sobre linguagens NP-completas

Resolution of problems on NP-complete languages.