Teoria da Computação

Disciplina: Teoria da Computação.

Professor: Joelson Nogueira de Carvalho

Período: 2019-1

Lista de Exercícios I

Aluno(a): _____________________________________     Matrícula:___________

1. Conceitue conjuntos e indique como podemos defini-los; exemplifique.

Conjunto é uma coleção de elementos, onde podem ser finitos ou infinitos.

1. O que é um conjunto não-enumerável? Exemplifique.

Um conjunto X é dito não-enumerável quando não é possível obter uma bijeção de X com o conjunto dos números naturais.

Exemplo: conjunto dos números Reais é não-enumerável, um exemplo bem simples é o intervalor entre (-1, 1).

1. Conjuntos infinitos são enumeráveis? Explique.

Sim, O conjunto P = {2, 4, 6, . . .} dos números pares também é enumerável. Neste caso, é fácil ver que a função f : N → P dada por f(n) = 2n é bijetora.

1. O que são conjuntos contáveis?
2. Quem desenvolveu o Método da Diagonalização e em que consiste tal método? Exemplifique seu uso.

O método da diagonalização foi desenvolvido por Cantor, é utilizado para contar os conjuntos dos números

1. Você poderia escrever um programa para identificar os n primeiros números complexos? Justifique a sua resposta.
2. Indique a classificação de programas quanto às suas estruturas de controle, caracterizando cada uma dessas estruturas.
3. Qual a definição formal de programa, para cada uma das estruturas de controle vistas?
4. Identifique numa linguagem de programação qualquer (C, JAVA, Pascal, etc) construções análogas as usadas nas definições do item anterior.
5. Defina Máquina, informalmente (em suas palavras) e formalmente.
6. Como se define a computação de uma máquina para cada estrutura de controle de programa vista?
7. Defina uma máquina de 4 registradores, de maneira que rode os programas elaborados para a máquina 2-Reg.
8. Defina uma máquina e um programa para multiplicar, dividir, somar e subtrair dois números reais.
9. Construa uma máquina e escreva um programa recursivo para a mesma, que calcule o fatorial de um número dado na entrada.
10. Escreva um programa Interativo onde a programação seja infinita. Faça o mesmo para um programa Recursivo; utilize a máquina 2-Reg ou alguma das máquinas definidas neste trabalho.
11. Defina função computada finita e a infinita.
12. Defina e diferencie os termos “computação” e “função computada”.
13. O que é uma função computada total?

...