JFLAP: http://www.jflap.org
[jflap.jar] 6.0, set 2006 (requer Java Runtime Environment)
Apresentação
Objetivos
Programa
Metodologia
Atividades
Semanais
Listas de exercícios
Avaliação
Bibliografia
Guiados por essas perguntas, apresentaremos a disciplina Autômatos e Computabilidade. A teoria aqui apresentada foi desenvolvida em busca de respostas a perguntas como estas. Essa busca produziu formalismos e métodos matemáticos cujas aplicações e desdobramentos levaram à informática de hoje.
- Quais são os fundamentos da computação? Esses fundamentos impõem limites à sua evolução?
- Em que se baseia a crença de que tais limites existem? Como e até que ponto se pode conhecer esses limites? E o seu impacto prático?
- Esses limites seriam outros se os fundamentos e o caminho trilhado na evolução da informática fossem outros? Por quê?
- Os profissionais da computação têm uma compreensão suficiente, ou adequada, dessas questões? Até que ponto devem ter?
Em particular, ela permitiu traçar o rumo em que a arquitetura de computadores e da engenharia na microeletrônica evoluiu, a derivação de sub-teorias e formalismos específicos -- modelos computacionais -- para o desenvolvimento dos modernos compiladores, interpretadores e otimizadores, e uma abordagem profícua ao aspecto operacional da inteligência humana.
E mais: as respostas encontradas desvelam um mistério da natureza cuja descoberta causou uma crise que produziu perda de inocência e uma profunda revolução nos fundamentos da matemática e na filosofia da ciência (vide seminário). Apertem os cintos.
Estudar os modelos computacionais mais relevantes, seu poder expressivo, as relações importantes entre estes e suas possíveis aplicações. Entender o papel desses modelos nos processos produtivos na microeletrônica e no desenvolvimento de softwares. Para isso, precisamos apreender um certo formalismo matemático, desenvolvido para permitir a formulação e aplicações de conceitos tais como:
- o de computabilidade, que descreve o poder expressivo dos possíveis dispositivos ou modelos computacionais;
- o de complexidade, que descreve métricas para se estimar custos médios ou máximos na operação desses dispositivos e modelos;
- o de decidibilidade, que descreve fronteiras para o alcance expressivo desses dispositivos e modelos;
- o de tratabilidade, que descreve limites práticos para solução computacional de problemas com representação simbólica.
A ementa oficial da disciplina é a seguinte
* Revisão
o Noções Matemáticas e Terminologia
o Definições, Teoremas e Provas
o Tipos de Provas
* Introdução
o Noções de Automata, Computabilidade e Complexidade
o Ferramentas de suporte à disciplina
* Automata e linguagens
o Linguagens Regulares e Autômato Finito
o Não determinismo
o Expressões regulares
o Propriedades das Linguagens Regulares
o Linguagens não regulares
o Gramáticas Livre de Contexto
o Autômato Pushdown
o Propriedades das Linguagens Livre de Contexto
o Além das Linguagens Livre de Contexto
* Computabilidade
o Máquina de Turing
+ Máquina com um número Ilimitado de Registradores
+ Funções Recursivas
+ Máquina Universal de Turing
+ Variantes das Máquinas de Turing
+ Definição de algoritmo
o Decidibilidade
+ Linguagens Decidíveis
+ Problema da Parada
o Redutibilidade
o Hierarquia de Chomsky
o Tese de Church-Turing
o Tópicos Avançados
+ O Teorema da Recursão
+ Decidibilidade de teorias lógicas
+ Reducibilidade de Turing
+ Definição de Informação
* Complexidade
o Medidas de Complexidade
o A classe P
o A classe NP
o NP-completude
o Problemas NP-completos
Metodologia
Será seguido, como bibliografia de referência, o livro de Hopcroft e Ullman, "Introduction to Automata, Languages and Computation" (capa 'Alice no país das maravilhas'). As aulas expositivas seguirão o texto referência mas, como ele é bastante amplo, o tempo e contexto da nossa disciplina não nos permite cobri-lo todo. Cobriremos o programa seqüencialmente até onde for possível. É importante que o aluno se dedique individualmente ao estudo do texto de referência, para bem assimilar os conceitos e para que a parte expositiva do curso lhe seja produtiva.
Serão disponibilizados textos complementares e ferramentas para auxiliar os alunos no treinamento do uso do formalismo e nos exercícios. Pressupondo esforço prévio do aluno para sanar eventual dúvida ou resolver determinado problema, o professor estará disponível em sua sala para atendimento, durante horário a ser posteriormente combinado. Nas páginas web correspondentes a este documento, serão registradas as atividades do curso, incluindo links para material didático complementar. Eventualmente usaremos também a página do curso “Automatos e Computabilidade” no Moodle em http://aprender.unb.br
1a. Semana
- Os alunos devem instalar em suas máquinas o software JFLAP disponível para download em http://www.jflap.org/
- Devem ler este documento e rever pré-requisitos fundamentais ao acompanhamento dos tópicos que serão abordados na disciplina. Devem estar familiarizados com o básico revisitado na primeira e segunda aulas, principalmente com a definição (matemática) e aplicações do conceito relação de equivalência. Para quem quiser uma apresentação detalhada, em pdf e com exemplos, desses requisitos básicos poderá encontrá-los, por exemplo, nos slides 81 a 94, 308 a 360 e 437 a 588 das notas do prof. Anton Setze. Da "lista1" (opcional) do professor Ralha, resolveremos dois problemas em sala de aula.
Listas de Exercício
Serão passadas tres ou quatro listas de exercício obrigatórias, e uma ou duas opcionais. A primeira lista obrigatória será corrigida antes da primeira prova, as demais conforme haja necessidade. As listas opcionais serão para efeito de arredondamento de menção, quando aplicável a critério do professor, e corrigidas conforme haja necessidade.
Lista de exercícios não obrigatória, não opcional para preparação à segunda prova
- Depois da 1a. prova, com quais modelos computacionais voce travou conhecimento através desta matéria?
- Desses modelos, quais admitem variantes, conforme esse conhecimento?
- Desses modelos, quais admitem mais de uma semântica (interpretação do funcionamento), quais não?
- Dos que admitem mais de uma semântica, como você as descreveria?
- Dos que admitem mais de uma variante, quais variantes alteram o poder expressivo do modelo, quais não?
- A menos de variantes equivalentes, quais modelos/semânticas guardam relação direta (p.ex., menor, maior, igual) com respeito ao poder expressivo, citando exemplos se possível?
- Como voce hierarquizaria essas relações, e como voce descreveria a hipótese metafísica que "fecharia" esta hierarquia no seu topo?
- O que é o "problema da parada", e como vc descreveria sua importância para a teoria da computação?
- O que são classes de complexidade computacional?
- Quais dessas classes voce considera mais importantes, e por que?
Aluno Lista 1 Lista 2
Clique
Lista 3 Prova 1 Prova 2 Pontos | Menção Inassiduidades | faltas
até 18/12 (35 chamadas)
03/27000 7.4
4,5 <7.5 5.0
5.3
< 58.5 | MM
02 | 00 : 9.4
03/84101 2.0
5,9 <10 5.5
8.4
< 70.3 | MS 10 | 05: 7.1
03/86740 --
4,8 0
4.2
2.4
< 35.1 | MI 12 | 06: 6.5 04/27951 7.2
6,2 <10 7.9
8.0
< 81.0 | MS 01 | 00: 9.7 04/80711 8.8
7,8 <7.5 5.8
6.4
< 66.9 | MM 11 | 09: 6.8
04/82081 7.4
0
7.5
4.5
49.2 < < 55.8 | 22 | 12: 3.7
04/86001 6.3
5,9 0
4.8
8.0
61.6 | MM 10 | 06: 7.1 04/87015 9.5
0
4.4
1.5
31.2 < < 37.8 | MI 22 | 12: 3.7
04/93902 7.9
6,2 <10 3.5
3.1
< 47.4 | MI 05 | 01: 8.5
04/94968 8.1
6,5 <10 5.2
7.8
< 73.0 | MS 05 | 04: 8.5
04/95107 9.7
5,6 0
3.5
2.8
37.9 | MI 14 | 11: 6.0
05/15710 8.5
9,2 <10
6.5
8.2
< 80.5 | MS 02 | 01: 9.4
05/19308 8.2
9,0 <10 5.2
3.7
< 55.6 | MM 10 | 08: 7.1
05/20667 7.5
6,9 <10 4.7
8.0
< 71.8 | MS 02 | 02: 9.4
05/20713 --
<10
7.6
08 | 07: 7.7
05/23101 7.2
5,9 <10 8.8
7.1
03 | 02: 9.1
05/24387 3.7
7,6 <10 7.3
9.3
03 | 00: 9.1
05/24557 7.6
6,9 <5.0 7.0
7.9
06 | 02: 8.2
05/24859 6.4
2,3 <7.5 6.9 6.8
04 | 04: 8.8
05/31758 5.5
6,5 <7.5 5.8
2.6
06 | 06: 8.2
05/37608 5.0
<7.5 3.8
3.4
14 | 07: 6.0
05/37861 8.9
9.5*
<10 8.5
9.5
00 | 00: 10.0
05/39643 5.7
<7.5 7.1
7.5
05 | 04: 8.5
05/41923 5.2
3,8 <10 4.2
6.9
17 | 07: 5.1
05/41940 9.0
6,3 <10 7.1
6.9
01 | 01: 9.7
05/99409 7.2
8.7*
<10 7.5
6.2
07 | 06: 8.0
OBS
* - Falha do professor / monitor no envio / tratamento de arquivo(s): Nota corrigida
Avisos
Cálculo final da menção a ser divulgado antes do horário de revisão.
Horário de Revisão: Dia 19 20/12/07 Das 11 às 12:30 h e das 14 às 15h
PROVAS -
Haverá duas provas escritas, em 22 de outubro e 11 18 de dezembro de 2007.
CRITÉRIOS-
Os elementos e pesos para a avaliação serão os seguintes.A chamada será feita no início da aula, eventualmente confirmada por uma segunda chamada ao final da aula. Atraso ocorre quando o aluno não estiver presente para responder à chamada no início da aula. Assiduidade ocorre nas aulas em que o aluno não falta, não se atrasa nem se ausenta por longo tempo da aula depois de responder à chamada.
- Pontualidade e assiduidade, peso 1 - calculada pela fórmula: Assiduidade / Aulas (com chamada)
- Média dos trabalhos obrigatórios, peso 2
- Prova 1, peso 3
- Prova 2, peso 4
Trabalhos serão aceitos com atraso mediante redução na nota máxima alcançável. Sob nenhuma hipótese haverá prova de reposição.
Após a segunda prova, a avaliação seguirá roteiro e prazos a serem definidos, para divulgação do resultado da avaliação e revisão final.
Livro texto de referência:
- John Hopcroft, Jeffrey Ullman & Motwani Rajeev: "Introduction to Automata Theory, Languages and Computation", Addison Wesley Longman Inc., Reading, Massachussetts, USA, 1st edition 1979*; 2nd edition 2001, 3rd edition 2006. (* usado pelo professor)
Leitura complementar:
- Menezes, Paulo Blauth: "Linguagens Formais e Autômatos". Instituto de Informática UFRGS, Série Livros Didáticos n. 3, 2a. ed. Editora Sagra Luzatto (Livraria Técnica, Brasília)
- Harry Lewys & Christos Papadimitriou: "Elementos de Teoria da Computação", Editora Bookman, Porto Alegre, 2a. ed., 2000. Disponível na distribuidora da editora em Brasília: Livraria Técnica, CLS 102 Bl. A Loja 17
- Michael Sispser: "Introduction to the Theory of Computation". PWS Publishing Company, Boston, 1997.
- Michael Harrison: "Introduction to Formal Language Theory", Addison Wesley, NY, 1978
Serão linkados aqui, ao longo do semestre, textos e ferramentas disponíveis na web que possam vir a ser de utilidade ao aluno. Sugestões são bem-vindas.