COMPUTABILIDADE E COMPLEXIDADE DE ALGORITMOS

Semestre 2010

Turma 2 (horários 5CDE)

Professores Responsáveis:
João Batista Souza de Oliveira, Avelino Franciso Zorzo (Turma 1), Ney Laert Vilar Calazans

Aqui, encontra-se material relativo à parte de Teoria da Computabilidade e o cronograma para esta parte da disciplina. Para mais detalhes e material para Complexidade de Algoritmos e Otimização, siga o Link para parte do Prof. João Batista.

Novidades:

25/10/2010 - ATENÇÃO: Devido aos problemas de cadastramento da disciplina no Moodle, a entrega do Trabalho Prático de Computabilidade deve ser realizada via e-mail para o professor.
14/10/2010 - Correção no cronograma de aulas.
12/08/2010 - Novo cronograma sugerido, ainda sujeito a alterações.
03/08/2010 - Página em atualização para 2010.

Cronograma da Parte de Teoria de Computabilidade da disciplina:

Aula	Data	Conteúdo
01	12/agosto	Complexidade de Algoritmos e Otimização, sob responsabilidade do Prof. João Batista
02	19/agosto	1/2/3 - Pano de Fundo, Linguagens, Definições Recursivas
03	26/agosto	Complexidade de Algoritmos e Otimização, sob responsabilidade do Prof. João Batista
04	02/setembro	3/4/5 - Definições Recursivas, Expressões Regulares, Autômatos Finitos
05	09/setembro	Complexidade de Algoritmos e Otimização, sob responsabilidade do Prof. João Batista
06	16/setembro	5/6/7 - Autômatos Finitos, Grafos de Transição e o Teorema de Kleene
07	23/setembro	7 - Teorema de Kleene
08	30/setembro	8/9/10 - Autômatos Finitos com Saída, Linguagens Regulares, Linguagens Não-regulares
09	07/outubro	12 - Gramáticas Livres do Contexto e Exercícios para a Prova
10	14/outubro	Prova da parte de Computabilidade
11	21/outubro	Complexidade de Algoritmos e Otimização, sob responsabilidade do Prof. João Batista
12	28/outubro	14/19 - Gramáticas Livres do Contexto e Máquinas de Pilha, Máquinas de Post
13	04/novembro	20/21/23 - Máquinas de Turing, Teorema de Minsky
14	11/novembro	23/24 - Linguagens de Máquinas de Turing, e a Hierarquia de Chomsky
15	18/novembro	25 - Computadores
16	25/novembro	Complexidade de Algoritmos e Otimização, sob responsabilidade do Prof. João Batista (a confirmar)
17	02/dezembro	Data limite de entrega do Trabalho Prático 3 (T3), via E-Mail para o professor
18	09/dezembro	Reserva Técnica

Enunciado do Trabalho Prático 3 (T3):
    (1) Escolher uma máquina de Turing de complexidade razoável (15 a 20 estados, pode ter mais);
    (2) Propor esta ao professor, por e-mail;
    (3) Uma vez aprovada pelo professor, implementar a máquina usando um software livre tal como JFLAP (preferencialmente) ou Visual Turing;
    (4) Entregar uma versão simulando corretamente do funcionamento desta
    (5) Entregar também um documento seguindo as regras descrevendo o problema resolvido pela máquina, descrevendo a estrutura da implementação, os pressupostos sobre as entradas e o formato da saída gerada.

Regras do Jogo:

O trabalho deve ser desenvolvido em grupos de 2 ou 3 alunos.
A criatividade na escolha do trabalho conta na nota. Assim, evitem propor problemas como
- ordenação de vetores;
- operações aritméticas tradicionais;
- a "eterna" Série de Fibonacci;
- etc.
Proponham soluções problemas diferentes, inusitados se possível! Vejam um exemplo no link abaixo, do WACI (Wild and Crazy Ideas Wokshop), realizado durante uma das mais reconhecidas conferências de computação do mundo, o DAC (http://www.dac.com/46th/PDFs/46th_DAC_WACI_Submission_Guidelines.pdf).
Atentem para a data limite da entrega do trabalho. Não serão aceitos trabalhos após esta data!
Exemplo de documentação bem feita para o Trabalho: Trabalho-Turing_exemplo_doc.pdf

Avaliação da Disciplina:

        G1 = (T1+T2+P1+2*T3) / 5

Onde:
    · T1, T2 = trabalhos que abrangem avaliações correspondentes às Unidades 01 e 02, respectivamente (Sob responsabilidade do Prof. João Batista).
    · P1 é uma prova escrita, referente aos conteúdos da Unidade 03.
    · T3 é uma nota de trabalho prático 3 (T3), referente à Unidade 04.

Material para download

Programa da Disciplina Plano da Disciplina	Programa_da_Disciplina_2006.pdf Plano_da_Disciplina_2006.pdf
Transparências das Aulas	Transparencias_Comp_Compl_1.pdf (03/09/2009) Transparencias_Comp_Compl_2.pdf (25/11/2008)
BFC Automata V2.0 (Software de Apoio: Editor/Simulador textual de DFA/NFA/Máquinas de Turing, etc.)	atm264.exe (Arquivo original de distribuição, proveniente do site http://automata.borfig.com/)
Visual Turing V1.0 (Software de Apoio: Editor/Simulador gráfico de Máquinas de Turing)	vturing.exe (Arquivo original de distribuição, proveniente do site http://www.cheransoft.com/vturing/)
JFLAP (Software de Apoio: Editor/Simulador gráfico de Máquinas de Turing)	http://www.jflap.org/
Exemplo de Prova com solução para Unidade 03	p1_teocomp_04_A_gabarito.pdf
Exemplo de Exercícios com solução para Unidade 04	p2_teocomp_04_A_gabarito.pdf

Bibliografia

Daniel I. A. Cohen. Introduction to Computer Theory. Wiley and Sons, Inc. New York. Second Edition, 1997.
Marc Davio et al. Discrete and Switching Functions. Georgi Publishing Co. & McGraw-Hill, 1978.
J. E. Hopcroft. Introduction to Automata Theory Languages, and Computation. Addison-Wesley, 1979.
Zvi Kohavi. Switching and Finite Automata Theory, McGraw-Hill, 1978.
J. van Leeuwen. Handbook of Theoretical Computer Science, MIT Press, 1990.
H. R. Lewis, C. H. Papadimitriou. Elements of the Theory of Computation (2^nd Edition), Prentice-Hall, 1996.

This page was last updated on November, 25th, 2010.

If you find problems in this page, please send an e-mail to ney.calazans@pucrs.br.
We will fix it in the shortest possible delay. Thanks for any help!