Listas de todos exercícios resolvidos de Teoria de Computação

Listas de todos exercícios resolvidos de Teoria de Computação

(Parte 1 de 2)

Professor: Luís Otávio Rigo

Alunos: André de Mattos Ferraz

Eliezer de Souza da Silva

Lucas Dias Serqueira Mateus Vieira Costa

Algoritmos e Fundamentos da Teoria de Computação Lista 01

1) Suponha que R = {(a; c), (c; e), (e; e), (e; b), (d; b), (d; d)}. Desenhe grafos orientados representando cada uma das seguintes relações:

2) Sejam R e S relações binárias sobre A = {1,,7} com as representações gráficas mostradas a

a) Indique se R e S são (i) simétricas, (i) reflexivas e (ii) transitivas; b) b) Repita (a) para a relação R união S.

Simétrico Não Sim Não Reflexivo Não Não Sim Transitivo Não Não Não

3) Desenhe gráficos orientados representando relações dos seguintes tipos: a) Reflexiva, transitiva e anti-simétrica.

b) Reflexiva, transitiva e nem simétrica nem anti-simétrica.

4) Seja A um conjunto não-vazio, e que seja o conjunto vazio. Quais são as propriedades de R?

Por definição (  

Reflexividade: R não é reflexiva. Prova (por contradição):

Transitividade: R é transitiva. Prova (por contradição):

Anti-Simetria: R é anti-simétrica. Prova (por contradição):

5) Seja f: A -> B. Demonstre que a seguinte relação R é de equivalência em A : (a; b) R, se, e somente se f(a) = f(b).

Transitiva: f(a) = f(b) e f(b) = f(c) f(a) = f(c) aRb e bRc aRc

6) Seja R A x A uma relação binária, conforme definida abaixo. Em que casos R é uma relação de ordem parcial? Em que casos R _e uma relação de ordem total? a) A = os inteiros positivos; (a, b) R se, e somente se, b é divisível por a. Não é ordem total por não apresentar a relação de totalidade sobre os inteiros: nem (2,3), nem (3,2) pertencem a R. (a,a) pertence a R, portanto é reflexiva. Se a é divisível por b, então a>b ou a=b, se temos aRb e bRa, significa que (a>b ou a=b) e (b>a ou b=a), ou seja a=b, portanto R é anti-simétrico. A transitividade neste caso é trivial. Portanto R é uma ordem parcial.

7) Sejam R1 e R2 duas relações de ordem parcial quaisquer sobre o mesmo conjunto A. Demonstre que R1 R2 é uma relação de ordem parcial.

Seja dois pares (x,y) e (y,x) pertencentes a . Comos eles pertencem a intersecção de dois que prova que é antissimétrico. - Transitividade:

1,  , hipotese
3, , simp 1
7, , transitividade de R1, 3, 5
8,  , transitividade de R2, 4, 6
9,  , conj, 7,8 (c.q.d.)

8) a) Prove que, se S for uma coleção qualquer de conjuntos, então RS = {(A;B) : A;B S, e A B} é uma relação de ordem parcial.

i) Reflexividade

A Rs A porque A%A i) Anti-Simétrica

Rs é uma relação de ordem parcial.

b) Seja S = &!',&,($. Desenhe um grafo orientado que represente a relação de ordem parcial RS definida em (a). Quais são os elementos mínimos de RS?

9) Em que circunstâncias um grafo orientado representa uma função?

Uma função pode ser definida como uma relação R com a seguinte propriedade. , , )* Ou seja, x só pode se relacionar (ou ser mapeado) a um e somente um elemento.

Em termos do dígrafo que representa esta relação quer dizer que o grau de saída de todos os nós do dígrafo é no máximo um.

10) Demonstre que qualquer função de um conjunto finito para ele próprio contém um ciclo.

Prova por indução no tamanho do conjunto. Seja A o conjunto e B = {f | f: A A} o conjunto das funções de A em A. i) A = {a}, card(A) = 1 Tem ciclo B={ {(a,a)} }

i) Suponha que card(A) = n e que B tenha n! funções de A em A, todas contendo ciclos. + !, ,, ,…,,.$ / !0 ,0 ,…,0.!$

Seja +2 + !,.3 $, 4,56 +2 781 E as funções de A’ em A’, pertencentes ao conjunto B’, são feitas estendendo as funções

2- Ou podemos trocar um elemento de f: tome ak A com f(ak) = aj, faremos a seguinte extensão. g: A’ A’ g(a) = f(a), se a A e a ak

Repare que só tenho estas duas opções para gerar as funções deA’ = A U !a.3$, caso contrário teríamos elementos de A’ que não seriam cobertos por estas

g(a) = aj , se a A e a a.3 , funções.

Prova: f: A -> A tem ciclos, e a construção (i) não alterou f, só adicionoug(a.3) = a.3.

Afirmação1: Na construção (i) temos ciclos

Afirmação2: Na construção (i) temos ciclos. Neste caso há dois casos a considerar.

a) Ak não pertence a um ciclo: o mesmo caso da afirmação 1. b) Ak pertence a um ciclo: neste caso aparentemente quebramos o ciclo, mas a transformação que fizemos mantém o ciclo adicionando um caminho indireto entra ak e aj.

Isto completa a prova por indução.

Algoritmos e Fundamentos da Teoria de Computação

Lista 02 1) Demonstre que os seguintes conjuntos são contáveis: a) União de três conjuntos contáveis quaisquer, não necessariamente finitos ou disjuntos. Prova:

A união de conjuntos é associativa. + / > + / > + / > Ou seja, só preciso mostrar que a união de dois conjuntos contáveis quaisquer é contável.

Um conjunto A é contável se ele é finito (i.e 0 0:!1,2,…,7$ +#0 é ABCDE)5, ), ou existe uma bijeção entre o conjunto A e F.

Fato: Se A e B são contáveis + / também é. Devemos dividir esta demonstração em três partes. i) A e B são finitos. Card(A)=n e card(B)=m, card(+ /) =n’

Seja G. !1,2,…,7$, 0:G. + e ::GH /, funções bijetivas respectivamente a A e B. Sem perda de generalidade supomos m>n e m-n>0.

Vamos criar a função g’ definida da seguinte forma :2:GHI.J /K+ / g’, é uma bijeção que mapeia os elementos da parte de B que não tem elementos em comum com A. É construida como uma restrição da função g, ou seja, continua sendo uma bijeção (o que prova que /K+ / também é finito). Iremos construir uma função que mapeia todos os elementos de + /, esta função mapeia inicialmente todos elementos de A, e depois inclui os elementos de B que não pertencem a A, usando a função g’.

Seja L:G.3HI.J + / L M0 ,ND O7:P K7 ,ND Q7R h é uma bijeção, pela própria construção, pois ela mapeia conjuntos disjuntos (A , B menos os elementos de A) usando funções bijeções. O fato de h ser uma bijeção completa a prova de A união B ser finito e portanto contável para o caso que consideramos.

Ii) A finitos e B infinitamente contável.

Seja :2:F /K+ / , g’ construido da mesma forma que no caso anterior, como uma restrição ao domínio de g, mas lembrando que este dominio é infinito, então uma restrição de um número finito (os elementos de A) não altera o domínio (ele continua sendo infinito) e a função g’ continua sendo uma bijeção, pois não acrescentou novos elementos, só retirou alguns.

Iremos construir a função h como um mapeamente entre os naturais e + /. L:F + / L M0 ,ND O7:P K7 ,ND Q7R h é uma bijeção, pela própria construção, como no item i). O fato de h ser uma bijeção completa a prova de A união B ser infinitamente contável.

i) A e B infinitamente contáveis. Sejam as bijeções 0:F + e ::F / Vamos construir mais uma vez g’ como uma restrição na imagem de g, tal que ela não contenha nenhum elemento que pertença a B e a A simultaneamente, função esta que é bijetora pelas mesmas razões dos itens anteriores.

Prossigamos para a construção de h. Seja: L:F + / L 27 0 7 L 27K1 :P 7 Ou seja, dividimos o dominio de F em números pares e ímpares, e fizemos cada um destes subconjuntos serem mapeados para A ou B\A. h é bijetora, pois cada par é mapeado em um de A, e cada ímpar em um elemento de B que não pertence a A. Ou seja, com h F cobre todo o conjunto + /. Portanto + / é infinitamente contável. Assim provamos que para três conjuntos contáveis quaisquer, a união dos três é contável, porque a união de dois deles é contável e o resultado deste união com o terceiro conjunto é contável também, ou seja, pela propriedade associativa a união dos três é contável sse a união de dois deles é.

b) União de todos os conjuntos finitos de F.

Seja X o conjunto de todos os subconjuntos finitos de F. S !+| 0:G. + e AVF$ Podemos visualizar X na seguinte tabela

Podemos facilmente verificar o seguinte fato: se SZ então !7$ SZ3 , para um n qualquer que não pertença a x.

Fato 1: S. é contável (para cada n pertencente aos naturais) Prova: por indução

- S[ é contável: trivial. - Suponha S. contável e seja 0:F S. Vamos construir uma função 0P:S.3 F F usando a função f.

Seja \ 0I ] , ou seja k é a ordem de um dado elemento (o k-ésimo) de S.. se SZ então !7$ SZ3

Podemos gerar os elementos de S.3 usando os elementos de S.. 02 ] !7$ 0I ] ,7 Reparem que f’ gera uma tabela F F, onde nenhum dos elementos são iguais (sem a diagonal principal), e portanto é bijetora, por existe uma bijeção entre F e F F. O prova que S.3 também é contável, terminando assim a prova por indução.

Como S SZ e como acabamos de mostrar que para cada i, SZ é contável, então união de vários conjuntos contável também é contável, ainda mais que estes são disjuntos.

2) Utilizando fórmulas que envolvam somente operações elementares apresente bijeções explícitas para os seguintes pares de conjuntos:

a. F e os números naturais ímpares. 0:F GX,5DN 0 7 27K1 b. F e conjunto de todos inteiros. 0:F _

Vamos construir uma função L:F F F bijetora.

Algoritmos e Fundamentos da Teoria de Computação Lista 03

1) Desenhe um fluxograma que corresponde a cada um dos seguintes programas: c) P2 = ({r1 : faça ; vá_para r2}; r1).

d) Composições enquanto e até, em um mesmo programa.

e) Programa sem instrução alguma.

Não existe tal programa. f) Programa sem instrução de parada.

2) Caracterize e diferencie computação e função computada.

Uma computação é um histórico do funcionamento de uma máquina específica para um determinado programa, de acordo com um valor inicial. Já uma função computada, é o resultado que foi obtido no final de uma computação sendo esta computação finita.

3) Defina computação de programas iterativos em uma máquina.

Seja M uma máquina e P um programa iterativo para a máquina M. Uma computação para o programa P em M é uma cadeia de pares do tipo:

(I0,V0)(I1,V1)(I2,V2)

Sendo uma cadeia finita ou infinita, onde I0 é o programa iterativo inicial e V0 é o valor inicial da memória. Para cada (Ik,Vk), onde k={0,1,2,...}, F sendo uma operação, T sendo um teste e V, V1, V2 programas iterativos, temos:

Caso: Ik = (se T então V senão V1);V2 (Condicional) Então: (Ik+1,Vk+1) = (V;V2,vk) se πt(vk) = verdadeiro = (V1;V2,vk) se πt(vk) = falso

Caso Ik = (enquanto T faça V);V1 Então (Ik+1,Vk+1) = (V;(enquanto T faça V);V1,vk) se πt(vk) = verdadeiro = (V1;até T faça V;V1,vk) se πt(vk) = falso

4) Defina computação finita para programas iterativos.

(I0,V0)(I1,V1)(I2,V2)(In,Vn) Sendo n o tamanho da cadeia.

Mesma definição do exercício anterior, porém considerando que a cadeia de pares é finita.

5) Escreva um programa iterativo onde a computação seja infinita.

enquanto( x = x ) faça V

6) Por que é possível afirmar que a computação de um programa monolítico em uma máquina, para um dado valor inicial da memória, é determinística?

Dado um valor inicial, para uma mesma máquina, a computação não muda, ou seja, a seqüência de instruções executadas e os valores intermediários de memória em várias execuções do programa não muda.

7) Traduza o programa recursivo definido abaixo em um programa iterativo.

P é R1 onde R1 def (se T então F; R2 senão R1),

R2 def G;(se T então F;R1 senão ∅;) até T faça V enquanto T faça (F;G(se T então (F;até T faça ∅) senão faça ∅))

8) Suponha que na definição de uma máquina, seja admitido funções parciais na especificação dos identificadores de operações e testes. Dê a definição apropriada da função computada por um programa em uma máquina em tal caso.

Como as operações e testes são funções parciais, estes não são definidos para alguns valores, fazendo-se necessário mapear estas funções em algum símbolo (Exemplo |). Caso a computação termine e as operações e testes estão definidos para todos os valores de memória, então: <P,M>(X) = πy(vn). Caso a computação entre em loop, a função computada deve ser mapeada em um símbolo

9) Verifique se W1 e W2 definidos a seguir, são equivalentes fortemente.

Programa Iterativo W1: enquanto T faça (F;(se T então faça ∅; senão faça G))

Programa Iterativo W2: enquanto T faça (F; enquanto T faça (F); G)

10) Qual a importância da relação de equivalência forte de programas?

A importância se dá pelo fato de podermos classificar programas diferentes em um mesmo conjunto de acordo com as funcionalidades. Além disso, abstraindo o significado de cada função ou teste, a mesma ordem de execução será observada.

Algoritmos e Fundamentos da Teoria de Computação Lista 04

1) Qual a importância do estudo da Máquina de Turing na Ciência da Computação?

Segundo a tese de Alonzo Church, percebemos que a Máquina de Turing é o dispositivo computacional mais genérico possível, capaz de processar qualquer função. Como a Ciência da Computação visa o estudo das funções computáveis, é imprescindível estudar a Máquina de Turing.

2) Sobre a Hipótese de Church: a) Qual seu signicado, implicações e importância na Teoria de Computação?

A hipótese permitiu fazer uma equivalência formal ao conceito informal de computação, ou seja, o conceito informal de computação pode ser formalizado utilizando a Máquina de Turing. Depois dessa formalização foi possível o desenvolvimento da Teoria de Computação.

b) Por que ela é chamada de Hipótese ao invés de Teorema de Church?

Pelo fato de não ser possível descrever matematicamente o conceito de computação, logo, não se pode ter uma prova formal.

3) Sobre não-determinismo: a) O que é e quais suas principais características?

Não-determinismo é a possibilidade de tomar alternativas diferentes para uma mesma entrada. No caso da Máquina de Turing, após a leitura de um símbolo, é permitido mais de um estado possível. O resultado obtido pela máquina é um conjunto de estados alternativos.

b) Qual o seu efeito, em termos de poder computacional, nas máquinas apresentadas?

O não-determinismo não acrescenta poder computacional, uma vez que uma Maquina de Turing não-determinística pode ser simulada como uma Máquina de Turing determinística.

4) Qual a diferença fundamental entre a Classe das Linguagens Recursivas e a das Linguagens Enumeráveis Recursivamente? Qual a importância de se distinguir essas duas classes?

As linguagens recursivas são aquelas onde existe uma Máquina de Turing que reconhece a linguagem e sempre para (aceitando ou rejeitando todas as entradas). Já uma linguagem enumerável recursivamente não necessita que a Máquina de Turing pare para todas as entradas, podendo entrar em loop para algumas.

5) Demonstre que a Classe de Linguagens Recursivas é fechada para as operações de união, intersecção e diferença. Demonstre inicialmente para a operação sobre duas linguagens recursivas. Após, amplie a demonstração para n linguagens recursivas (demonstre por indução em n).

Considerando as linguagens L1 e L2 que pertençam à Classe das Linguagens Recursivas e uma Máquina de Turing M definida como:

aceita(L) = L rejeita(L) = Σ* - L loop(L) = ∅ (vazio)

União:

Intersecção:

Diferença:

Para a demonstração para n linguagens, podemos usar o método da indução matemática onde a base para a indução é a própria demonstração para duas linguagens. A hipótese de indução é como se segue a seguir: (k = numero de linguagens)

aceita(L1) ∪∪ aceita(Lk) = aceita(L1 ∪ ... ∪ Lk)
rejeita(L1) ∪∪ rejeita(Lk) = rejeita (L1 ∪ ... ∪ Lk)
loop(L1) ∪∪ loop(Lk) = ∅
(aceita(L1) ∪∪ aceita(Lk)) ∪ aceita(Lk+1) = aceita (L1 ∪ ... ∪ Lk ∪ Lk+1)
(rejeita(L1) ∪∪ rejeita(Lk)) ∪ rejeita(Lk+1) = rejeita (L1 ∪ ... ∪ Lk ∪ Lk+1)
(loop(L1) ∪∪ loop(Lk)) ∪ Lk+1 = ∅

Considerando o elemento k+1:

Analogamente podemos demonstrar, por meio da indução matemática, a validade para a intersecção e a diferença. 6) Desenvolva Máquinas de Turing que aceitem as seguintes linguagens:

a) L1 = {w | w tem o mesmo número de símbolos a e b}

b) L2 = {w | w o décimo símbolo da direita para a esquerda é a} c) L4 = {w | w = anbn ou w = bnan}

d) L5 = {w | w = aibjck, onde ou i = j ou j = k}

7) Desenvolva Maquinas de Turing que processem as funções:

a) Subtração, definida por: m – n, se m > n; 0, caso contráro. b) Fatorial de n, para n Є N

8) Elabore uma Máquina de Turing M sobre o alfabeto {a; b} tal que:

ACEITA(M) = {w | w inicia com a e, após cada a, existe pelo menos um b} LOOP(M) = {w | w !Є ACEITA(M) e existe pelo menos um b entre dois a} REJEITA(M) = {a; b}* - (ACEITA(M) U LOOP(M))

(Parte 1 de 2)

Comentários