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.