Sumários
Aula Prática 7
10 novembro 2011, 08:30 • Maria Paula Antunes Abrantes Gouveia
Exercício 2.1 g) 2.2 c) d) e) f), 2.3 a), 2.4 a) e) e 2.6 c) da lista de exercícios para as aulas práticas 6/7. TPC: exercício 2.8 a).
Aula Prática 7
9 novembro 2011, 08:30 • Maria Paula Antunes Abrantes Gouveia
Exercício 2.2 b) c) d) e) f), 2.3 a), 2.4 a) e) e 2.6 c) da
lista de exercícios para as aulas práticas 6/7. TPC: exercício 2.8 a).
Aula Prática 7
8 novembro 2011, 12:00 • Maria Paula Antunes Abrantes Gouveia
Exercício 2.2 b) c) d) e) f), 2.3 a), 2.4 a) e) e 2.6 c) da lista de exercícios para as aulas práticas 6/7. TPC: exercício 2.8 a).
Aula Teórica 12
8 novembro 2011, 10:00 • Maria Paula Antunes Abrantes Gouveia
Computabilidade: motivação. Postulado de Church-Turing. Conjuntos equipotentes, conjuntos numeráveis. Proposição: os conjuntos N, Z e Q são numeráveis. (a prova foi realizada na 1a aula prática). Proposição: o conjunto {0,1}^* é numerável. Prova da proposição. Extensão ao caso de um alfabeto Sigma qualquer. Proposição: Seja Sigma um alfabeto e seja A um subconjunto infinito de Sigma^*. O conjunto A é numerável. Prova da proposição. Teorema de Cantor (enunciado e prova).
Aula Teórica 12
8 novembro 2011, 08:30 • Maria Paula Antunes Abrantes Gouveia
Computabilidade: motivação. Postulado de Church-Turing. Conjuntos equipotentes, conjuntos numeráveis. Proposição: os conjuntos N, Z e Q são numeráveis. Prova dos dois primeiros casos. Proposição: o conjunto {0,1}^* é numerável. Prova da proposição. Extensão ao caso de um alfabeto Sigma qualquer. Proposição: Seja Sigma um alfabeto e seja A um subconjunto infinito de Sigma^*. O conjunto A é numerável. Prova da proposição. Teorema de Cantor (enunciado e prova).