ACH2043 - Introdução à Teoria da Computação

2º semestre/2019

Prof. Marcelo de Souza Lauretto

Bibliografia:

1. SIPSER, M. Introdução à Teoria da Computação. Thomson Learning, 2007.

Programa:

1. Cap 1: Autômatos Finitos / Linguagens Regulares

2. Cap 2: Autômatos a Pilha / Gramáticas Livres do Contexto

3. Cap. 3: Máquinas de Turing

4. Cap. 4: Computabilidade

5. Cap. 5: Redutibilidade

6. Cap. 7: Complexidade

Atendimento de dúvidas:

· 3as e 5as feiras das 17:30 às 18:30 em minha sala (320B)
Enviar e-mail com antecedência mínima de um dia

Avaliação:

· Quadro de notas e frequências

· 4 provas
- Provas com consulta (anotações manuscritas em caderno ou folhas avulsas)

· Datas:
- P1: 15/09
- P2: 22/10 – Capítulo 2 + Seção 7.2 (Algoritmo CYK para parsing de GLCs)
- P3: 12/11 – Capítulo 3
- P4: 03/12 (20h) – Seções 4.1, 4.2, 7.1, 7.2 e 7.3
- Prova substitutiva: 10/12 (20h)

· Cálculo da média semestral:
MF = [2N(1) + 2N(2) + 2N(3) + N(4)] / 7
onde N(i) corresponde à i-ésima maior nota entre as 4 provas

· Cálculo da média final (para os alunos que fizerem a REC):
a) Se REC <= MF: MFR = MF;
b) Se MF < REC < 5.0: MFR = (MF + REC)/2
c) Se REC > 5.0: MFR = máx(5.0, (MF + REC)/2)
Onde:
- REC = nota da prova de recuperação
- MF = média final do semestre sem a REC (1ª avaliação)
- MFR = média final semestral com a prova REC (2ª avaliação)

Material de Apoio:

Aula introdutória sobre a disciplina.
(Conteúdo adaptado dos slides gentilmente cedidos pela Profa. Ariane Machado Lima)

Capítulo 1:

- Linguagens Regulares
(Conteúdo adaptado dos slides gentilmente cedidos pela Profa. Ariane Machado Lima)

- Minimização de estados de AFDs

Capítulo 2:

- Conceitos básicos de Gramáticas
(Conteúdo adaptado dos slides gentilmente cedidos pela Profa. Ariane Machado Lima)

- Linguagens Livres-do-Contexto

- Autômatos com Pilha: Parte 1 – Parte 2
(slides gentilmente cedidos pela Profa. Ariane Machado Lima)

Capítulo 3:

- 3.1 Máquinas de Turing
(slides gentilmente cedidos pela Profa. Ariane Machado Lima)

- 3.2 Variantes de Máquinas de Turing: multi-fitas e não determinística
(slides gentilmente cedidos pela Profa. Ariane Machado Lima)

- 3.3 A Definição de Algoritmo
(slides gentilmente cedidos pela Profa. Ariane Machado Lima)

Capítulo 4:

- 4.1 Linguagens Decidíveis
(slides gentilmente cedidos pela Profa. Ariane Machado Lima)

- 4.2 O Problema da Parada
(slides gentilmente cedidos pela Profa. Ariane Machado Lima)

- Sensacional animação com uma elegante demonstração do Problema da Parada, por Udi Aharoni.
(Agradecimentos ao Thomas Akira Ueda pela indicação)

Capítulo 7:

- 7.1 Medindo Complexidade
(slides gentilmente cedidos pela Profa. Ariane Machado Lima)

- 7.2 A Classe P
(slides gentilmente cedidos pela Profa. Ariane Machado Lima)

- 7.3 A Classe NP
(slides gentilmente cedidos pela Profa. Ariane Machado Lima)

- 7.4 NP-Completude
(slides gentilmente cedidos pela Profa. Ariane Machado Lima)

Exercícios Recomendados:

1. Livro Sipser:

1. Cap. 1: 1.1 – 1.12; 1.14; 1.16-1.31
Exercícios complementares sobre expressões regulares e linguagens não regulares

2. Cap. 2: 2.1, 2.3, 2.4, 2.5, 2.6, 2.7, 2.8, 2.9, 2.10, 2.11, 2.12, 2.14, 2.15, 2.16, 2.17

3. Cap. 3: 3.1, 3.2, 3.4, 3.5, 3.6, 3.7, 3.8, 3.11, 3.15, 3.16
Exercícios complementares

4. Cap. 4: 4.2, 4.3, 4.4, 4.6, 4.9, 4.11, 4.12, 4.13, 4.15, 4.22

5. Cap. 5: 5.1, 5.2, 5.4, 5.5, 5.6, 5.7, 5.9
Exercícios complementares

6. Cap. 7: Inclui dicas e exercícios adicionais.
Exercícios recomendados do livro: 7.1, 7.2, 7.3, 7.6, 7.7, 7.8, 7.9, 7.10, 7.20.

2. Exercícios compilados pela Mälardalen University Sweden:

1. Context-free languages: Pags 2-3: Problems 1 – 13; Pags 4-7: Problems 1-3, examples 1-7; Pag. 8: todos

2. Recursively enumerable languages.

Leitura Complementar:

Hing Leung, Regular Languages and Finite Automata
http://www.cs.nmsu.edu/historical-projects/Projects/pr12.pdf

McCulloch and Pitts (1943), A Logical Calculus of the Ideas Immanent in Nervous Activity
http://www.cs.chalmers.se/~coquand/AUTOMATA/mcp.pdf

S.C.Kleene, Representation of Events in Nerve Nets and Finite Automata
http://www.soe.ucsc.edu/classes/cmps130/Spring09/Papers/kleene_1956.pdf

Chomsky, Noam (1956). "Three models for the description of language". IRE Transactions on Information Theory (2): 113–124.
http://www.chomsky.info/articles/195609--.pdf.

Notas de aula Profa Sandra Maria Aluisio:
http://coteia.icmc.usp.br/mostra.php?ident=580.5