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 | 4 | Plano de Estudos Oficial | 3 | - | 6 | 56 | 162 |
L:CC | 65 | 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 | 3 | Plano estudos a partir do ano letivo 2016/17 | 3 | - | 6 | 56 | 162 |
MI:ERS | 4 | 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 intrepertar 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 NP; teorema de Cook e outros problemas NP-completos. reduções polinomiais.
A classe dos problemas PSPACE. A classe dos ploblemas LogSpace.
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 | 50,00 |
Participação presencial | 0,00 |
Teste | 50,00 |
Total: | 100,00 |
Designação | Tempo (Horas) |
---|---|
Estudo autónomo | 106,00 |
Frequência das aulas | 56,00 |
Total: | 162,00 |
Teste intercalar (50% de peso na nota final).
Exame final (50% de peso na nota final).
Sendo TI a classificação obtida no teste intercalar e EF a
classificação obtida no exame final, então a nota final é dada por:
F = TI*(0.5) + EF*(0.5)
TI,EF >= 6 e F >= 9.5
Não obterão aprovação na avaliação distribuída, os alunos que não obtiverem um mínimo de 6 valores (em 20), em ambos os testes e um mínimo de 9.5 valores de nota final.
Para os alunos que não obtiverem aprovação, haverá um exame de recurso. O exame de recurso terá duas componentes (claramente indicadas) correspondendo aos tópicos avaliados no teste e no exame final respectivamente, permitindo dois cenários possíveis de determinação da nota final: