Ao completar a unidade curricular, espera-se que os estudantes sejam capazes de:

– Nomear as contribuições significativas para a teoria da computação e os seus protagonistas;
– Identificar problemas tratáveis com autómatos finitos e exprimi-los com notação rigorosa;
– Comparar os autómatos finitos deterministas, não-deterministas e as expressões regulares no reconhecimento das linguagens regulares;
– Aplicar as propriedades das linguagens regulares em provas;
– Identificar problemas que se podem tratar com gramáticas sem contexto e usar notação rigorosa para os descrever;
– Comparar as gramáticas sem contexto e os autómatos de pilha no reconhecimento das linguagens sem contexto;
– Exprimir problemas de computação com recurso ao modelo da máquina de Turing;
– Relacionar os modelos de computação estudados com as suas aplicações na teoria da computabilidade e da complexidade.

Os conteúdos programáticos foram definidos de forma a permitir uma progressão que, partindo de conceitos básicos, possibilite a compreensão do edifício conceptual que sustenta os fundamentos teóricos da ciência dos computadores, especialmente no que respeita aos problemas de computabilidade e da complexidade espacial e temporal dos algoritmos.
A metodologia centrar-se-á na interatividade entre os vários agentes educativos, começando pelo docente e estendendo-se a todos os estudantes, envolvendo os estudantes no processo de ensino aprendizagem de forma crítica e ativa através dos fóruns. Com uma abordagem de debate e utilizando?os fóruns e documentos de apoio inerentes às temáticas abordadas, espera-se que exista uma forte motivação e participação por parte dos estudantes nas atividades a desenvolver. O aluno deverá ser capaz de perceber e usar a capacidade de computação das máquinas, assim como os seus limites teóricos, bem como de formalizar adequadamente e avaliar se determinados problemas têm solução computacional ou não. Deverá perceber e saber usar modelos, técnicas e algoritmos de computação simbólica introduzidos na resolução de problemas informáticos do dia-a-dia.
Deste modo procura-se estimular o trabalho?autónomo dos estudantes e desenvolver os seus sentidos e pensamentos críticos sobre as questões que o envolvem, direta ou indiretamente.