Disciplina Curricular

Fundamentos da Computação FC

Mestrado Bolonha em Ciência Cognitiva - 1_MCCog 2020/21

Contextos

Grupo: 1_MCCog 2020/21 > 2º Ciclo > Parte Escolar

Período:

Peso

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