Disciplina Curricular

Teoria da Computação TCom

Licenciatura Bolonha em Engenharia Informática e de Computadores - Alameda - LEIC-A 2006

Contextos

Grupo: LEIC-A 2006 > 1º Ciclo > Ciências de Engenharia

Período:

Peso

4.5 (para cálculo da média)

Objectivos

Entender e saber utilizar os conceitos de máquina de Turing, computação e recurso computacional. Compreender e aprofundar os conceitos de "tarefa" algorítmica e de "tarefa" não algorítmica. Conhecer os limites para "tarefas" algorítmicas. Entender a computação como conceito físico-matemático e não como conceito puramente matemático. Experimentar conceitos e técnicas em ambientes computacionais interativos.

Programa

Computabilidade Máquinas de Turing determinísticas, não determinísticas e enumeradoras. Funções computáveis. Conjuntos recursivamente enumeráveis. Oráculos. Reduções. O problema da terminação (introdução à técnica da diagonalização). Teorema de Kleene. Vírus. O teorema de Rice e suas aplicações. O postulado de Church-Turing. Complexidade Recursos computacionais. Construtividade das funções. Teoremas de hierarquia (emprego da diagonalização). Teorema de Savitch. Classes computacionais: P, PSPACE, NP, EXPTIME, BPP. Relações estruturais. Conjuntos completos. Construção da hierarquia polinomial. Relativização.

Metodologia de avaliação

Avaliação contínua. Média dos 3 melhores de entre 4 testes.

Disciplinas Execução

2016/2017 - 2ºSemestre

2015/2016 - 2º Semestre

2014/2015 - 2º Semestre

2013/2014 - 2 Semestre

2012/2013 - 1 Semestre

2011/2012 - 1 Semestre

2010/2011 - 1 Semestre

2009/2010 - 1 Semestre

2008/2009 - 1 Semestre

2007/2008 - 1 Semestre

2007/2008 - 1 Semestre

2006/2007 - 1 Semestre