Saltar para:
Logótipo
Você está em: Início > CC3004
Mapa das Instalações
FC6 - Departamento de Ciência de Computadores FC5 - Edifício Central FC4 - Departamento de Biologia FC3 - Departamento de Física e Astronomia e Departamento GAOT FC2 - Departamento de Química e Bioquímica FC1 - Departamento de Matemática

Computabilidade e Complexidade

Código: CC3004     Sigla: CC3004     Nível: 300

Áreas Científicas
Classificação Área Científica
OFICIAL Ciência de Computadores

Ocorrência: 2017/2018 - 2S

Ativa? Sim
Página Web: http://www.dcc.fc.up.pt/~rvr/aulas/AC1718/CeC/
Unidade Responsável: Departamento de Ciência de Computadores
Curso/CE Responsável: Licenciatura em Ciência de Computadores

Ciclos de Estudo/Cursos

Sigla Nº de Estudantes Plano de Estudos Anos Curriculares Créditos UCN Créditos ECTS Horas de Contacto Horas Totais
L:B 2 Plano de Estudos Oficial 3 - 6 56 162
L:CC 47 Plano de estudos a partir de 2014 3 - 6 56 162
L:F 0 Plano de Estudos Oficial 2 - 6 56 162
3
L:G 0 Plano estudos a partir do ano letivo 2017/18 3 - 6 56 162
L:M 0 Plano de Estudos Oficial 2 - 6 56 162
3
L:Q 0 Plano estudos a partir do ano letivo 2016/17 3 - 6 56 162
MI:ERS 9 Plano Oficial desde ano letivo 2014 3 - 6 56 162

Docência - Responsabilidades

Docente Responsabilidade
Rogério Ventura Lages dos Santos Reis Regente

Docência - Horas

Teórica: 2,00
Práticas Laboratoriais: 2,00
Tipo Docente Turmas Horas
Teórica Totais 1 2,00
Rogério Ventura Lages dos Santos Reis 2,00
Práticas Laboratoriais Totais 2 4,00
Rogério Ventura Lages dos Santos Reis 4,00

Língua de trabalho

Português

Objetivos

Estudo e comparação de vários modelos de computação
(Turing-completos), do seu poder computacional e das suas limitações. Estudo das diversas classes de complexidade computacional.

Ao completar este curso espera-se que os alunos
- conheçam os modelos de computação clássicos utilizados no estudo da
computabilidade de diversos problemas;
- saibam provar a equivalência de vários modelos Turing-completos;
- conheçam os resultados e métodos mais importantes no estudo da
computabilidade e complexidade;
- saibam classificar exemplos concretos de problemas e provar a sua
(in)decidibilidade dentro das diversas classes de computabilidade.
- saibam classificar elemplos concretos pelas sua complexidade temporal e intrepertar essa classificação. 

Resultados de aprendizagem e competências

Os alunos são expostos a vários dos modelos de computação Turing-completos standard, como as máquinas de registo, máquinas de Turing e as funções recursivas. Para além da prova da equivalência dos diferentes modelos, estes são também utilizados para identificar diferentes problemas indecidíveis. São usadas diferentes técnicas, como o método da diagonalização e da redução entre linguagens. Para adquirirem experiência em identificar a complexidade computacional de problemas concretos, faz-se uma introdução às classes P e NP, completude NP e o teorema de Cook, voltando também à técnica da redução.

Modo de trabalho

Presencial

Pré-requisitos (conhecimentos prévios) e co-requisitos (conhecimentos simultâneos)

Conhecimentos de alguns modelos de computação como Autómatos finitos, Expressões regulares e Gramáticas independentes. Conhecimentos básicos de Lógica.

Programa

Noção de linguagem/problema (semi-)decidível. Revisão de alguns
modelos de computação (DFA's, NFA's, CFG's e PDA's) e do seu poder
computacional. Máquinas de registo. Tese de Church-Turing. Hierarquia
de Chomsky. Teorewma da Recursão de Kleene.
Introdução à Complexidade d Kolmogorov.
 Método da diagonalização e indecidibilidade do problema
da paragem. Redução "muitos para um" entre linguagens. Introdução à teoria de complexidade: classes P e NP; completude NP; teorema de Cook e outros problemas NP-completos. reduções polinomiais.
A classe dos problemas PSPACE.
A classe dos ploblemas LogSpace.

Bibliografia Obrigatória

Introduction to Automata Theory, Languages and Computation, Hopcroft, Motwani and Ullmann.
Recursion theory, Phillips, in Handbook of logic in computer science (vol. 1), Oxford University Press.

Bibliografia Complementar

Introduction to the Theory of Computation, Michael Sipser.
Models of Computation - An Introduction to Computability Theory, Maribel Fernández.
Oded Goldreich; P, NP, and NP-Completeness - The Basics of Computational Complexity, Cambridge University Press, 2010

Métodos de ensino e atividades de aprendizagem

Aulas teóricas de exposição dos conteúdos programáticos.
Aulas práticas de resolução de exercícios propostos semanalmente.

Tipo de avaliação

Avaliação distribuída com exame final

Componentes de Avaliação

Designação Peso (%)
Exame 50,00
Teste 50,00
Total: 100,00

Obtenção de frequência

Presença a 2/3 das aulas práticas

Fórmula de cálculo da classificação final

Classificação final corresponde à classificação obtida
- como média aritmética dos dois testes, o primeiro a realizar durante o semestre e o segundo na data do exame da época normal (cada um com nota mínima de 6 valores). Os dois testes incidem respectivamente sobre a matéria lecdionada durante a primeira e a segunda parte do semestre.
- o exame da época de recurso não contabiliza a nota obtida no primeiro teste e aborda toda a matéria leccionada durante o semestre.

Recomendar Página Voltar ao Topo
Copyright 1996-2022 © Faculdade de Ciências da Universidade do Porto  I Termos e Condições  I Acessibilidade  I Índice A-Z  I Livro de Visitas
Página gerada em: 2022-09-29 às 12:12:47 | Política de Utilização Aceitável | Política de Proteção de Dados Pessoais | Denúncias