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 Definição formal e representação diagramática. o Definição formal de computação. o A linguagem reconhecida por um autómato finito. o Equivalência AFD e AFN. o Expressões regulares. o Operações sobre expressões regulares: união, concatenação e estrela. o Expressões regulares e linguagens regulares. o O lema de pumping. • Linguagens livres de context. o Gramáticas livres de contexto. o derivação; Árvore de parsing; A linguagem da gramática; Ambiguidade. 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: • Definição. • Classes de complexidade P e NP. • Completude-NP. • Usar redução em tempo polynomial para provar completude-NP
Métodos de ensino e avaliação
Aulas teóricas de exposição da matéria e aulas teórico-práticas de resolução de exercícios. Avaliação: quatro testes durante o semestre (5 valores); exame escrito final (15 valores).