Sumários
Exercícios de decidibilidade
4 Dezembro 2020, 08:00 • André Souto
Resolução de exercícios sobre decibilididade.
Aula em regime alternado misto com transmissão via zoom.
Exercícios de decidibilidade
4 Dezembro 2020, 08:00 • Andreia Mordido
Resolução de exercícios sobre decibilididade.
Aula em regime misto alternado.Complexidade temporal
2 Dezembro 2020, 09:30 • André Souto
Noção de algoritmo eficiente.
Definição formal de tempo de execução numa máquina de Turing.
Notação O-grande.Exemplos.Definição da classe TIME(t(n)).
Complexidade da simulação dos modelos de máquinas de Turing na máquina original.
Noção de tempo de execução numa máquina de Turing não determinista.
Complexidade da simulação da máquina não determinista na máquina original.
Complexidade da simulação da máquina não determinista na máquina original.
Estudar a secção 7.1 do livro do Sipser.
A aula foi dada em regime síncrono não presencial com transmissão via Zoom.
Exercícios de decidibilidade
2 Dezembro 2020, 08:00 • Andreia Mordido
Resolução de exercícios sobre decibilididade.
Aula em regime misto alternado.