Resolução de exercícios folha 7

3 Dezembro 2021, 08:00 • André Souto

Resolução de exercícios sobre decidibilidade. 

Turing decidibilidade e Turing reconhecibilidade

3 Dezembro 2021, 08:00 • Paulo Jorge Cunha Vaz Dias Urbano

Resolução de Exercícios

Resolução de exercícios folha 7

30 Novembro 2021, 10:30 • André Souto

Resolução de exercícios sobre decidibilidade. 

Complexidade temporal e a classe P

30 Novembro 2021, 09:30 • André Souto

Noção de algoritmo eficiente.

Definição formal de tempo de execução numa máquina de Turing.

Relembrar a 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.

A classe de complexidade P e a sua importância.

Exemplos de problemas em P.

Turing decidibilidade e Turing reconhecibilidade

29 Novembro 2021, 08:00 • Paulo Jorge Cunha Vaz Dias Urbano

Exercícios