Código: | CC3004 | Sigla: | CC3004 | Nível: | 300 |
Áreas Científicas | |
---|---|
Classificação | Área Científica |
OFICIAL | Ciência de Computadores |
Ativa? | Sim |
Unidade Responsável: | Departamento de Ciência de Computadores |
Curso/CE Responsável: | Licenciatura em Ciência de Computadores |
Sigla | Nº de Estudantes | Plano de Estudos | Anos Curriculares | Créditos UCN | Créditos ECTS | Horas de Contacto | Horas Totais |
---|---|---|---|---|---|---|---|
L:B | 0 | Plano de Estudos Oficial | 3 | - | 6 | 56 | 162 |
L:CC | 64 | 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 | 3 | Plano estudos a partir do ano letivo 2017/18 | 2 | - | 6 | 56 | 162 |
3 | |||||||
L:M | 2 | 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 | 8 | Plano Oficial desde ano letivo 2014 | 2 | - | 6 | 56 | 162 |
3 |
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 interpretar essa classificação.
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.
Conhecimentos de alguns modelos de computação como Autómatos finitos, Expressões regulares e Gramáticas independentes. Conhecimentos básicos de Lógica.
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 Turing. Máquinas de registo. Funções Recursivas. Lambda Calculus. Tese de Church-Turing. Hierarquia
de Chomsky. Teorema da Recursão de Kleene. 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 em NP; teorema de Cook e outros problemas NP-completos. reduções polinomiais. Classes co-NP, etc.
A classe dos problemas PSPACE.
Aulas teóricas de exposição dos conteúdos programáticos.
Aulas práticas de resolução de exercícios propostos semanalmente.
Designação | Peso (%) |
---|---|
Exame | 100,00 |
Total: | 100,00 |
Designação | Tempo (Horas) |
---|---|
Estudo autónomo | 106,00 |
Frequência das aulas | 56,00 |
Total: | 162,00 |
Valorização obtida em exame.