Teoria da Computação
Profa. Sandra de Amo
Bacharelado em CC
Mestrado em CC
2008 – 1
Roteiro
• Informações gerais
• Conteúdo do Curso
• Critério de Avaliação
– BCC
– Mestrado
• Bibliografia
Conteúdo do Curso
• Eh possivel resolver ?
– Para qualquer problema existe um algoritmo que o
resolve ?
– Quando vale a pena tentar encontrar um algoritmo
para resolver um problema ?
– Técnicas para decidir se um problema tem ou não
solução algoritmica.
• Eh possivel resolver de forma eficiente ?
– Para problemas que tem solução, será que sempre é
possivel encontrar uma solução viável ?
– O que é, afinal de contas, uma “solução viável” ?
– Tecnicas para decidir se um problema tem ou não
uma solução viável.
Informações Gerais
• Página do curso
– http://www.deamo.prof.ufu.br/CursoDM2008.
html
• E-mail
– [email protected]
• Horário de Atendimento – Sala 1B77
– Segunda-feira
– Terça-feira
14:00 – 15:00
14:00 – 15:00
Conteúdo do Curso
Parte I – Preliminares
• Conjuntos Infinitos –
– enumeráveis
– não-enumeráveis
• Linguagens
• Revisão de Autômatos
• Revisão de Gramáticas livres do contexto
Conteúdo do Curso
• Problemas e Linguagens
• O que significa um ”problema solúvel“?
• Máquinas de Turing
• Variantes de Máquina de Turing
• Tese de Church
• Problemas decidiveis e indecidiveis
• Exemplos
Conteúdo do Curso
Parte II – DECIDIBILIDADE
• Problemas decidiveis envolvendo
Autômatos
• Problemas decidiveis envolvendo
gramáticas livres do contexto
Conteúdo do Curso
Parte III – Indecidibilidade
• Como mostrar que um problema é
indecidivel ?
• Método da Redução
• Problema da Parada da Máquina de Turing
e indecidivel
• Problema de Correspondência de Post –
um problema simples que é indecidivel
Conteudo do Curso
Parte IV – Complexidade
• Notação O (crescimento assintótico)
• Classe P (polinomial)
• Classe NP
• Questao P = NP
• Problemas NP- Completos
Conteúdo do Curso –
Problemas NP completos
• Teorema de Cook – problema SAT eh NPcompleto
• Problema
• Problema
• Problema
• Problema
• Problema
do Caixeiro Viajante
Clique
do Vertex Cover
da Mochila
do Circuito Hamiltoniano
Aulas de Exercicios
• Listas 1,2,3,4,5 a cada 15 dias
– Grupo Bacharelado
– Grupo Mestrado
• Aulas separadas para graduação e
mestrado.
Bibliografia
• SIPSER, Michael : Introduction to the Theory of Computation. Brooks/Cole
Pub Co, 1a Edição, 1996; 2a Edição 2005 (Livro Texto)
Edição em português:
INTRODUÇAO A TEORIA DA COMPUTAÇAO, 2007
SIPSER, Michael - Editora: THOMSON PIONEIRA
• Cláudio L. Lucchesi, Imre Simon, Istvan Simon, Janos Simon, Tomasz
Kowaltowski Aspectos Teóricos da Computação - Projeto Euclides, Instituto
de MatemáticaAplicada 1979. Eh possivel carregar uma cópia deste livro no
formato DjVu.
• 3. LEWIS, H., PAPADIMITRIOU, C. : Elements of the Theory of
Computation. Prentice Hall. 2a Edição. 1997.
• 4. GAREY, M. R.; JOHNSON, D. S. Computers and intractability: a guide to
NP-completeness. New York: H. Freeman, 1979. (Livro Texto)
• 5. HAREL, David : Algorithmics – The Spirit of Computing. Addison-Wesley,
2a Edição, 1993.
Criterio de Avaliação
Critério
Bacharelado Ciência da Computação
• Prova 1 – Partes I – II – III
Preliminares - Decidibidade - Indecidibilidade
• Prova 2 – Parte IV – Complexidade
• Prova Substitutiva
• Trabalho escrito
• Trabalho oral
• Exercicios
• Trabalhos em grupos de 4
Critério de Avaliação
Mestrado Ciência da Computação
• Prova 1 – Partes I – II – III
Preliminares - Decidibidade – Indecidibilidade
(inclui demonstrações)
• Prova 2 – Parte IV – Complexidade
•
•
•
•
•
(inclui demonstrações)
Prova Substitutiva
Trabalho escrito – em forma de artigo cientifico
Trabalho oral – temas mais aprofundados
Exercicios
Trabalhos em grupos de 2
Critério de Avaliação
•
•
•
•
•
Prova 1 = 35 pontos
Prova 2 = 35 pontos
Apresentacao oral = 10 pontos
Monografia = 10 pontos
Exercicios = 10 pontos
• NF = P1 + P2 + AO + Mo + Ex
Prova Substitutiva = somente se NF < 60
Nota final com sub no maximo = 60
Calendário das Avaliações
•
•
•
•
•
Prova 1 : 29 de Abril
Prova 2 : 1 de Julho
Prova Substitutiva : 15 de Julho
Apresentação oral dos trabalhos
- a ser marcado oportunamente
Entrega do trabalho escrito :
– Bacharelado : 17 de Julho
– Mestrado : 11 de Julho