Plano de Estudos
Fundamentos da Computação FC
Contextos
Groupo: 1_MCCog 2020/21 > 2º Ciclo > Parte Escolar
ECTS
6.0 (para cálculo da média)
Objectivos
Adquirir conceitos e métodos base da teoria da computação – modelos de computação, computabilidade e complexidade. Entender as especificidades e diferenças de vários modelos de computação, de crescente poder computacional, concluindo que não é conhecido nenhum modelo que tenha mais poder computacional que a máquina de (Tese de Church-Turing). Perceber os limites da computabilidade através de problemas que não são computáveis, ou seja, que não podem ser resolvidos por um computador, por mais recursos de tempo e espaço que se tenham ao dispor. Abordar questões de complexidade, onde os problemas computacionais são classificados de acordo com os recursos de tempo e espaço necessários para os resolver. Perceber que existem problemas que, embora sejam computáveis, são impossíveis de resolver devido à enorme quantidade de recursos necessários.
Programa
Linguagens e modelos de computação: • Linguagens regulares o Autómatos finitos deterministas (AFD) e não deterministas (AFN) o Expressões regulares o O lema de pumping • Linguagens livres de contexto. o Gramáticas livres de contexto. o Autómatos de pilha • Linguagens computáveis o Máquinas de Turing. o Variantes de máquinas de Turing e equivalência o Máquina de Turing universal o A tese de Church-Turing Decidibilidade: • Linguagens computáveis (decidíveis) e semi-decidíveis. Redução por mapeamento entre linguagens e o seu uso para provar (in)decidibilidade. o Existência de linguagens não-decidíveis. o O problema da paragem (Halting problem). o O teorema de Rice. Complexidade temporal: • Classes de complexidade P e NP. • Completude-NP. • Usar redução em tempo polinomial para provar completude-NP
Método de Avaliação
Quatro testes durante o semestre; exame escrito final.
Carga Horária
Carga Horária de Contacto -
Trabalho Autónomo - 88.0
Carga Total -
Bibliografia
Principal
- Introduction to the Theory of Computation, third edition: Sipser, Michael 2013 Cengage Learning, isbn-13: 978-1-133-18779-0.
- Introdução à Teoria da Computação: Sipser, Michael 2007 São Paulo: Thomson, isbn 978-85-221-0499-4. tradução portuguesa de: Sipser, Michael, 2004, Introduction to the Theory of Computation, 2ª edição, Boston: Thomson, isbn 978-0-6192-1764-8.
Secundária
- Introduction to the Theory of Computation, third edition: Sipser, Michael 2013 Cengage Learning, isbn-13: 978-1-133-18779-0.
- Introdução à Teoria da Computação: Sipser, Michael 2007 São Paulo: Thomson, isbn 978-85-221-0499-4. tradução portuguesa de: Sipser, Michael, 2004, Introduction to the Theory of Computation, 2ª edição, Boston: Thomson, isbn 978-0-6192-1764-8.