Sumários

28 Maio 2024, 10:00 • Isabel Gama Nunes

The class NP. Examples of problems in NP.

The P versus NP question.

Polinomial time reducibility.

NP-completeness. Examples of NP-complete problems.

(Sipser's book, Sections 7.1 to 7.4)

21 Maio 2024, 10:00 • Isabel Gama Nunes

Undecidability (cont.). Some exercises.

Rice's theorem.

(Sipser book, Chapter 5)

Variants of Turing machines. The class of languages these variants recognize is the same as the original, deterministic, uni-tape model does.

(Sipser book, Sections 7.1, 7.2)

Temporal complexity. Measuring complexity. Assymptotic analysis; the Big-O notation.

The class P.

(Sipser book, Sections 7.1, 7.2)

14 Maio 2024, 10:00 • Isabel Gama Nunes

Undecidability

Reducibility.

(Sipser's book, Chapter 5)

7 Maio 2024, 10:00 • Isabel Gama Nunes

Closure of the class of decidable languages and of recognizable languages under the union operation.

Universal Turing machines.

(Sipser's book, Section 4.1)

Third individual evaluation test.

30 Abril 2024, 10:00 • Isabel Gama Nunes

Turing-decidable and Turing-recognizable languages.

Three formats for describing Turing machines: formal, implementation and high-level.

Examples of decidable languages.

Algorithms and Turing machines.

Operations with decidable languages.

(Sipser's book, Sections 3.1, 3.3 and 4.1)