Descrição:

Pretende-se que o aluno compreenda: como se podem representar problemas reais utilizando modelos computacionais abstratos; as capacidades e limitações relativas dos vários modelos; as relações entre linguagens e modelos; o conceito "ser reconhecível" (uma dada linguagem é ou não é reconhecível por um determinado modelo); o conceito de "ser derivável"; o conceito de parsing; que há linguagens que são indecidíveis; o conceito de complexidade de um problema, conseguindo determinar a complexidade de alguns problemas; e, finalmente, a diferença entre tratável e intratável.