Baixe o app para aproveitar ainda mais
Prévia do material em texto
Aplicações de recursividade Prof. Dr. Silvio do Lago Pereira Departamento de Tecnologia da Informação Faculdade de Tecnologia de São Paulo Prof. Dr. Silvio do Lago Pereira – DTI / FATEC-SP 2 Aplicações de recursividade Nesta aula, veremos algumas aplicações de recursividade em: Ordenação de dados Ordenação topológica Árvores de busca binária Código de Huffman 72 51 65 88 90 46 29 15 37 72 65 90 29 37 51 88 46 15 72 90 37 65 29 51 46 88 15 72 37 90 65 29 51 46 88 15 72 37 37 72 46 51 15 88 15 46 51 88 15 29 37 46 51 65 72 88 90 72 37 90 65 29 51 46 88 15 29 6537 72 90 29 37 65 72 90 lg n n 1 2 3 4 5 6 7 8 9 62 1 3 5 7 4 1 DDDD 1 EEEE 1 LLLL 1 RRRR 2 MMMM 3 AAAA 2 2 5 4 9 0 0 0 0 0 1 1 1 11 Ordenação de dados ordenação por geração e teste ordenação por trocas ordenação por inserção ordenação por intercalação ordenação por partição Prof. Dr. Silvio do Lago Pereira – DTI / FATEC-SP 4 Ordenação por geração e teste (permutation sort) A operação de geração (ou permutação)A operação de geração (ou permutação) Constrói uma permutação PPPP de uma lista LLLL.Constrói uma permutação PPPP de uma lista LLLL. Para ordenar LLLL por tentativa e erro: Gere uma permutação PPPP de LLLL. Teste se PPPP está ordenada. Complexidade de tempo: O(n!) Muito ineficiente para ser usada em aplicações práticas! A operação de testeA operação de teste Verifica se uma permutação PPPP está ordenada.Verifica se uma permutação PPPP está ordenada. 3 1 2L : 3 1 2P1 : 3 2 1 1 3 2 1 2 3 P2 : P3 : P4 : Prof. Dr. Silvio do Lago Pereira – DTI / FATEC-SP 5 Ordenação por geração e teste: implementação Exemplo 1. Ordenação por geração e testeExemplo 1. Ordenação por geração e teste pspspsps(L,P) :(L,P) :(L,P) :(L,P) :---- permuta(L,P), ordenada(P).permuta(L,P), ordenada(P).permuta(L,P), ordenada(P).permuta(L,P), ordenada(P). permutapermutapermutapermuta([],[]).([],[]).([],[]).([],[]). permutapermutapermutapermuta(L,[(L,[(L,[(L,[X|PX|PX|PX|P]) :]) :]) :]) :---- exclui(X,L,R), permuta(R,P).exclui(X,L,R), permuta(R,P).exclui(X,L,R), permuta(R,P).exclui(X,L,R), permuta(R,P). excluiexcluiexcluiexclui(X,L,R) :(X,L,R) :(X,L,R) :(X,L,R) :---- concatena(A,[X|B],L), concatena(A,B,R).concatena(A,[X|B],L), concatena(A,B,R).concatena(A,[X|B],L), concatena(A,B,R).concatena(A,[X|B],L), concatena(A,B,R). concatenaconcatenaconcatenaconcatena([],B,B).([],B,B).([],B,B).([],B,B). concatenaconcatenaconcatenaconcatena([X|A],B,[X|C]) :([X|A],B,[X|C]) :([X|A],B,[X|C]) :([X|A],B,[X|C]) :---- concatena(A,B,C).concatena(A,B,C).concatena(A,B,C).concatena(A,B,C). ordenadaordenadaordenadaordenada([]).([]).([]).([]). ordenadaordenadaordenadaordenada([_]).([_]).([_]).([_]). ordenadaordenadaordenadaordenada([X,([X,([X,([X,Y|RY|RY|RY|R]) :]) :]) :]) :---- X=<Y, ordenada([X=<Y, ordenada([X=<Y, ordenada([X=<Y, ordenada([Y|RY|RY|RY|R]). ]). ]). ]). pspspsps(L,P) :(L,P) :(L,P) :(L,P) :---- permuta(L,P), ordenada(P).permuta(L,P), ordenada(P).permuta(L,P), ordenada(P).permuta(L,P), ordenada(P). permutapermutapermutapermuta([],[]).([],[]).([],[]).([],[]). permutapermutapermutapermuta(L,[(L,[(L,[(L,[X|PX|PX|PX|P]) :]) :]) :]) :---- exclui(X,L,R), permuta(R,P).exclui(X,L,R), permuta(R,P).exclui(X,L,R), permuta(R,P).exclui(X,L,R), permuta(R,P). excluiexcluiexcluiexclui(X,L,R) :(X,L,R) :(X,L,R) :(X,L,R) :---- concatena(A,[X|B],L), concatena(A,B,R).concatena(A,[X|B],L), concatena(A,B,R).concatena(A,[X|B],L), concatena(A,B,R).concatena(A,[X|B],L), concatena(A,B,R). concatenaconcatenaconcatenaconcatena([],B,B).([],B,B).([],B,B).([],B,B). concatenaconcatenaconcatenaconcatena([X|A],B,[X|C]) :([X|A],B,[X|C]) :([X|A],B,[X|C]) :([X|A],B,[X|C]) :---- concatena(A,B,C).concatena(A,B,C).concatena(A,B,C).concatena(A,B,C). ordenadaordenadaordenadaordenada([]).([]).([]).([]). ordenadaordenadaordenadaordenada([_]).([_]).([_]).([_]). ordenadaordenadaordenadaordenada([X,([X,([X,([X,Y|RY|RY|RY|R]) :]) :]) :]) :---- X=<Y, ordenada([X=<Y, ordenada([X=<Y, ordenada([X=<Y, ordenada([Y|RY|RY|RY|R]). ]). ]). ]). Exercício 1. Ordenação por geração e testeExercício 1. Ordenação por geração e teste Digite e teste os predicados definidos no Exemplo 1.Digite e teste os predicados definidos no Exemplo 1. Prof. Dr. Silvio do Lago Pereira – DTI / FATEC-SP 6 Ordenação por trocas (bubble sort) A operação de trocaA operação de troca Troca as posições de dois elementos consecutivos que estejam fora de ordem.Troca as posições de dois elementos consecutivos que estejam fora de ordem. Para ordenar recursivamente uma lista LLLL usando trocas: Encontre um par de elementos consecutivos XXXX e YYYY em LLLL que estejam fora de ordem. Construa uma nova lista NNNN, idêntica a LLLL, exceto pelo fato de que em NNNN o elemento YYYY ocorre antes de XXXX. Ordene recursivamente a lista NNNN, obtendo a lista ordenada LoLoLoLo. 46 51 39 17 25 46 39 51 17 25 17 25 39 46 51 toque ordene L : N : Lo : Prof. Dr. Silvio do Lago Pereira – DTI / FATEC-SP 7 Ordenação por trocas: funcionamento/complexidade 46 17 51 39 25 17 46 51 39 25 toque 17 46 39 51 25 toque 17 39 46 51 25 toque 17 39 46 25 51 toque 17 39 25 46 51 toque 17 25 39 46 51 toque O(n2) Prof. Dr. Silvio do Lago Pereira – DTI / FATEC-SP 8 Ordenação por trocas: implementação Exemplo 2. Ordenação por trocasExemplo 2. Ordenação por trocas bsbsbsbs(L,Lo) :(L,Lo) :(L,Lo) :(L,Lo) :---- concatena(A,[X,concatena(A,[X,concatena(A,[X,concatena(A,[X,Y|BY|BY|BY|B],L),],L),],L),],L), X>Y, !,X>Y, !,X>Y, !,X>Y, !, concatena(A,[Y,X|B],N),concatena(A,[Y,X|B],N),concatena(A,[Y,X|B],N),concatena(A,[Y,X|B],N), bsbsbsbs(N,Lo).(N,Lo).(N,Lo).(N,Lo). bsbsbsbs(L,L).(L,L).(L,L).(L,L). concatenaconcatenaconcatenaconcatena([],B,B).([],B,B).([],B,B).([],B,B). concatenaconcatenaconcatenaconcatena([X|A],B,[X|C]) :([X|A],B,[X|C]) :([X|A],B,[X|C]) :([X|A],B,[X|C]) :---- concatena(A,B,C).concatena(A,B,C).concatena(A,B,C).concatena(A,B,C). bsbsbsbs(L,Lo) :(L,Lo) :(L,Lo) :(L,Lo) :---- concatena(A,[X,concatena(A,[X,concatena(A,[X,concatena(A,[X,Y|BY|BY|BY|B],L),],L),],L),],L), X>Y, !,X>Y, !,X>Y, !,X>Y, !, concatena(A,[Y,X|B],N),concatena(A,[Y,X|B],N),concatena(A,[Y,X|B],N),concatena(A,[Y,X|B],N), bsbsbsbs(N,Lo).(N,Lo).(N,Lo).(N,Lo). bsbsbsbs(L,L).(L,L).(L,L).(L,L). concatenaconcatenaconcatenaconcatena([],B,B).([],B,B).([],B,B).([],B,B). concatenaconcatenaconcatenaconcatena([X|A],B,[X|C]) :([X|A],B,[X|C]) :([X|A],B,[X|C]) :([X|A],B,[X|C]) :---- concatena(A,B,C).concatena(A,B,C).concatena(A,B,C).concatena(A,B,C). Exercício 2. Ordenação por trocasExercício 2. Ordenação por trocas Digite e teste os predicados definidos no Exemplo 2. Modifique o predicado bsbsbsbs/2/2/2/2 para que os estados da lista sejam exibidos no vídeo. Digite e teste os predicados definidos no Exemplo 2. Modifique o predicado bsbsbsbs/2/2/2/2 para que os estados da lista sejam exibidos no vídeo. Prof. Dr. Silvio do Lago Pereira – DTI / FATEC-SP 9 Ordenação por inserção (insertion sort) A operação de inserçãoA operação de inserção Insere um elemento XXXX numa lista ordenada LLLL, obtendo uma nova lista ordenada NNNN.Insere um elemento XXXX numa lista ordenada LLLL, obtendo uma nova lista ordenada NNNN. Para ordenar recursivamente uma lista LLLL usando inserção: Comece com uma lista auxiliar AAAA vazia. Insira o primeiro elemento de LLLL em AAAA, obtendo uma nova lista NNNN. Insira recursivamente os demais elementos de LLLL em NNNN, obtendo a lista ordenada LoLoLoLo. Complexidade: O(n2) 46 51 39 17 25 insere L : A : 4651 39 17 25L : A : insere 46 5139 17 25L : A : insere 46 513917 25L : A: insere 46 51391725L : A : insere 46 513917 25L : A : Prof. Dr. Silvio do Lago Pereira – DTI / FATEC-SP 10 Ordenação por inserção: implementação Exemplo 3. Ordenação por inserçãoExemplo 3. Ordenação por inserção isisisis([],A,A).([],A,A).([],A,A).([],A,A). isisisis([X|R],A,Lo) :([X|R],A,Lo) :([X|R],A,Lo) :([X|R],A,Lo) :---- insere(X,A,N), is(R,N,Lo).insere(X,A,N), is(R,N,Lo).insere(X,A,N), is(R,N,Lo).insere(X,A,N), is(R,N,Lo). insereinsereinsereinsere(X,[],[X]).(X,[],[X]).(X,[],[X]).(X,[],[X]). insereinsereinsereinsere(X,[(X,[(X,[(X,[Y|AY|AY|AY|A],[X,],[X,],[X,],[X,Y|AY|AY|AY|A]) :]) :]) :]) :---- X=<Y, !.X=<Y, !.X=<Y, !.X=<Y, !. insereinsereinsereinsere(X,[(X,[(X,[(X,[Y|AY|AY|AY|A],[],[],[],[Y|BY|BY|BY|B]) :]) :]) :]) :---- insere(X,A,B).insere(X,A,B).insere(X,A,B).insere(X,A,B). isisisis([],A,A).([],A,A).([],A,A).([],A,A). isisisis([X|R],A,Lo) :([X|R],A,Lo) :([X|R],A,Lo) :([X|R],A,Lo) :---- insere(X,A,N), is(R,N,Lo).insere(X,A,N), is(R,N,Lo).insere(X,A,N), is(R,N,Lo).insere(X,A,N), is(R,N,Lo). insereinsereinsereinsere(X,[],[X]).(X,[],[X]).(X,[],[X]).(X,[],[X]). insereinsereinsereinsere(X,[(X,[(X,[(X,[Y|AY|AY|AY|A],[X,],[X,],[X,],[X,Y|AY|AY|AY|A]) :]) :]) :]) :---- X=<Y, !.X=<Y, !.X=<Y, !.X=<Y, !. insereinsereinsereinsere(X,[(X,[(X,[(X,[Y|AY|AY|AY|A],[],[],[],[Y|BY|BY|BY|B]) :]) :]) :]) :---- insere(X,A,B).insere(X,A,B).insere(X,A,B).insere(X,A,B). Exercício 3. Ordenação por inserçãoExercício 3. Ordenação por inserção Digite os predicados definidos no Exemplo 2 e teste com a consulta: ????---- is([46,51,39,17,25],[],Lo).is([46,51,39,17,25],[],Lo).is([46,51,39,17,25],[],Lo).is([46,51,39,17,25],[],Lo). Modifique o predicado is/2is/2is/2is/2 de modo que os estados da lista AAAA sejam exibidos. Digite os predicados definidos no Exemplo 2 e teste com a consulta: ????---- is([46,51,39,17,25],[],Lo).is([46,51,39,17,25],[],Lo).is([46,51,39,17,25],[],Lo).is([46,51,39,17,25],[],Lo). Modifique o predicado is/2is/2is/2is/2 de modo que os estados da lista AAAA sejam exibidos. Prof. Dr. Silvio do Lago Pereira – DTI / FATEC-SP 11 Ordenação por intercalação (merge sort) A operação de intercalaçãoA operação de intercalação Dadas duas listas ordenadas AoAoAoAo e BoBoBoBo, a operação de intercalação constrói uma lista ordenada LoLoLoLo, com elementos de AoAoAoAo e BoBoBoBo, em tempo proporcional ao tamanho de LoLoLoLo. Dadas duas listas ordenadas AoAoAoAo e BoBoBoBo, a operação de intercalação constrói uma lista ordenada LoLoLoLo, com elementos de AoAoAoAo e BoBoBoBo, em tempo proporcional ao tamanho de LoLoLoLo. Para ordenar recursivamente uma lista LLLL usando intercalação: Separe os elementos de LLLL em duas listas AAAA e BBBB; com aproximadamente o mesmo número de elementos. Ordene recursivamente as listas AAAA e BBBB, obtendo as respectivas listas ordenadas AoAoAoAo e BoBoBoBo. Intercale as listas ordenadas AoAoAoAo e BoBoBoBo, obtendo a lista ordenada LoLoLoLo. 72 51 65 88 90 46 29 15 37 72 65 90 29 37 51 88 46 15 29 37 65 72 90 15 46 51 88 15 29 37 46 51 65 72 88 90 separe ordene intercale L : A : B : Ao : Bo : Lo : Prof. Dr. Silvio do Lago Pereira – DTI / FATEC-SP 12 Ordenação por intercalação: funcionamento/complexidade 72 51 65 88 90 46 29 15 37 72 65 90 29 37 51 88 46 15 72 90 37 65 29 51 46 88 15 72 37 90 65 29 51 46 88 15 72 37 37 72 46 51 15 88 15 46 51 88 15 29 37 46 51 65 72 88 90 72 37 90 65 29 51 46 88 15 29 6537 72 90 29 37 65 72 90 lg n n O(n lg n) Prof. Dr. Silvio do Lago Pereira – DTI / FATEC-SP 13 Ordenação por intercalação: implementação Exercício 4. Separação dos elementosExercício 4. Separação dos elementos Defina o predicado separa(L,A,B)separa(L,A,B)separa(L,A,B)separa(L,A,B), que separa os elementos da lista LLLL em duas listas AAAA e BBBB, cada uma delas com aproximadamente o mesmo número de elementos. Teste com a consulta: ????---- separa([72,51,65,88,90,46,29,15,37],A,B).separa([72,51,65,88,90,46,29,15,37],A,B).separa([72,51,65,88,90,46,29,15,37],A,B).separa([72,51,65,88,90,46,29,15,37],A,B). Defina o predicado separa(L,A,B)separa(L,A,B)separa(L,A,B)separa(L,A,B), que separa os elementos da lista LLLL em duas listas AAAA e BBBB, cada uma delas com aproximadamente o mesmo número de elementos. Teste com a consulta: ????---- separa([72,51,65,88,90,46,29,15,37],A,B).separa([72,51,65,88,90,46,29,15,37],A,B).separa([72,51,65,88,90,46,29,15,37],A,B).separa([72,51,65,88,90,46,29,15,37],A,B). Exercício 5. Intercalação dos elementosExercício 5. Intercalação dos elementos Defina o predicado intercala(Ao,Bo,Lo)intercala(Ao,Bo,Lo)intercala(Ao,Bo,Lo)intercala(Ao,Bo,Lo), que intercala os elementos das listas ordenadas AoAoAoAo e BoBoBoBo para construir uma única lista ordenada LoLoLoLo. Teste com a consulta: ????---- intercala([29,37,65,72,90],[15,46,51,88],Lo).intercala([29,37,65,72,90],[15,46,51,88],Lo).intercala([29,37,65,72,90],[15,46,51,88],Lo).intercala([29,37,65,72,90],[15,46,51,88],Lo). Defina o predicado intercala(Ao,Bo,Lo)intercala(Ao,Bo,Lo)intercala(Ao,Bo,Lo)intercala(Ao,Bo,Lo), que intercala os elementos das listas ordenadas AoAoAoAo e BoBoBoBo para construir uma única lista ordenada LoLoLoLo. Teste com a consulta: ????---- intercala([29,37,65,72,90],[15,46,51,88],Lo).intercala([29,37,65,72,90],[15,46,51,88],Lo).intercala([29,37,65,72,90],[15,46,51,88],Lo).intercala([29,37,65,72,90],[15,46,51,88],Lo). Exercício 6. Ordenação por intercalação (merge sort)Exercício 6. Ordenação por intercalação (merge sort) Defina o predicado msmsmsms(L,Lo)(L,Lo)(L,Lo)(L,Lo), que transforma a lista LLLL em uma lista ordenada correspondente LoLoLoLo, usando o método de ordenação por intercalação. Teste com a consulta: ????---- msmsmsms([72,51,65,88,90,46,29,15,37],Lo).([72,51,65,88,90,46,29,15,37],Lo).([72,51,65,88,90,46,29,15,37],Lo).([72,51,65,88,90,46,29,15,37],Lo). Defina o predicado msmsmsms(L,Lo)(L,Lo)(L,Lo)(L,Lo), que transforma a lista LLLL em uma lista ordenada correspondente LoLoLoLo, usando o método de ordenação por intercalação. Teste com a consulta: ????---- msmsmsms([72,51,65,88,90,46,29,15,37],Lo).([72,51,65,88,90,46,29,15,37],Lo).([72,51,65,88,90,46,29,15,37],Lo).([72,51,65,88,90,46,29,15,37],Lo). Prof. Dr. Silvio do Lago Pereira – DTI / FATEC-SP 14 Ordenação por partição (quick sort) A operação de partiçãoA operação de partição Dada uma lista L=[P|R]L=[P|R]L=[P|R]L=[P|R], a operação de partição distribui os elementos de RRRR em duas listas AAAA e BBBB tais que os elemento de AAAA sejam menores ou iguais a PPPP e os elementos de BBBB sejam maiores que PPPP. Dada uma lista L=[P|R]L=[P|R]L=[P|R]L=[P|R], a operação de partição distribui os elementos de RRRR em duas listas AAAA e BBBB tais que os elemento de AAAA sejam menores ou iguais a PPPP e os elementos de BBBB sejam maiores que PPPP. Para ordenar recursivamente uma lista L=[P|R]L=[P|R]L=[P|R]L=[P|R] usando partição: Particione os elementos de RRRR em duas listas AAAA e BBBB. Ordene recursivamente as listas AAAA e BBBB, obtendo as respectivas listas ordenadas AoAoAoAo e BoBoBoBo. Concatene as listas ordenadas AoAoAoAo e [[[[P|BoP|BoP|BoP|Bo]]]], obtendo a lista ordenada LoLoLoLo. L : Bo :Ao : B : 72 51 65 88 90 46 29 15 37 51 65 46 29 15 88 9037 15 29 37 46 51 88 9065 15 29 37 46 51 65 72 88 90 particione ordene concatene A : Lo : Prof. Dr. Silvio do Lago Pereira – DTI / FATEC-SP 15 Ordenação por partição: funcionamento/complexidade 72 51 65 88 90 46 29 15 37 51 65 46 29 15 37 88 90 46 29 15 37 65 90 15 37 88 90 15 29 37 46 51 65 72 88 90 15 37 65 29 15 37 15 29 37 15 29 37 46 15 29 37 46 51 65 90 n n Pior caso: O(n2) Melhor caso: O(n lg n) Prof. Dr. Silvio do Lago Pereira – DTI / FATEC-SP 16Ordenação por partição: implementação Exercício 7. Partição dos elementosExercício 7. Partição dos elementos Defina particiona(P,L,A,B)particiona(P,L,A,B)particiona(P,L,A,B)particiona(P,L,A,B), que particiona a lista LLLL em duas listas AAAA e BBBB tal que os elementos de A sejam menores ou iguais a PPPP e os de BBBB sejam maiores que PPPP. Teste com a consulta: ????---- particiona([72,51,65,88,90,46,29,15,37],A,B).particiona([72,51,65,88,90,46,29,15,37],A,B).particiona([72,51,65,88,90,46,29,15,37],A,B).particiona([72,51,65,88,90,46,29,15,37],A,B). Defina particiona(P,L,A,B)particiona(P,L,A,B)particiona(P,L,A,B)particiona(P,L,A,B), que particiona a lista LLLL em duas listas AAAA e BBBB tal que os elementos de A sejam menores ou iguais a PPPP e os de BBBB sejam maiores que PPPP. Teste com a consulta: ????---- particiona([72,51,65,88,90,46,29,15,37],A,B).particiona([72,51,65,88,90,46,29,15,37],A,B).particiona([72,51,65,88,90,46,29,15,37],A,B).particiona([72,51,65,88,90,46,29,15,37],A,B). Exercício 8. Concatenação de listasExercício 8. Concatenação de listas Defina concatena(A,B,L)concatena(A,B,L)concatena(A,B,L)concatena(A,B,L), que concatena as listas AAAA e BBBB para construir a lista LLLL. Teste com a consulta: ????---- concatena([15,29,37,46,51,65],[72,88,90],L).concatena([15,29,37,46,51,65],[72,88,90],L).concatena([15,29,37,46,51,65],[72,88,90],L).concatena([15,29,37,46,51,65],[72,88,90],L). Defina concatena(A,B,L)concatena(A,B,L)concatena(A,B,L)concatena(A,B,L), que concatena as listas AAAA e BBBB para construir a lista LLLL. Teste com a consulta: ????---- concatena([15,29,37,46,51,65],[72,88,90],L).concatena([15,29,37,46,51,65],[72,88,90],L).concatena([15,29,37,46,51,65],[72,88,90],L).concatena([15,29,37,46,51,65],[72,88,90],L). Exercício 9. Ordenação por partição (quick sort)Exercício 9. Ordenação por partição (quick sort) Defina o predicado qsqsqsqs(L,Lo)(L,Lo)(L,Lo)(L,Lo), que transforma a lista LLLL em uma lista ordenada correspondente LoLoLoLo, usando o método de ordenação por partição. Teste com a consulta: ????---- qsqsqsqs([72,51,65,88,90,46,29,15,37],Lo).([72,51,65,88,90,46,29,15,37],Lo).([72,51,65,88,90,46,29,15,37],Lo).([72,51,65,88,90,46,29,15,37],Lo). Defina o predicado qsqsqsqs(L,Lo)(L,Lo)(L,Lo)(L,Lo), que transforma a lista LLLL em uma lista ordenada correspondente LoLoLoLo, usando o método de ordenação por partição. Teste com a consulta: ????---- qsqsqsqs([72,51,65,88,90,46,29,15,37],Lo).([72,51,65,88,90,46,29,15,37],Lo).([72,51,65,88,90,46,29,15,37],Lo).([72,51,65,88,90,46,29,15,37],Lo). Ordenação topológica definição implementação Prof. Dr. Silvio do Lago Pereira – DTI / FATEC-SP 18 Ordenação topológica Ordenação topológicaOrdenação topológica Uma ordenação topológica de um grafo acíclico G=(V,A) é uma ordem total S dos elementos de V tal que se (vi,vj) ∈ A, então vi precede vj em S. Uma ordenação topológica de um grafo acíclico G=(V,A) é uma ordem total S dos elementos de V tal que se (vi,vj) ∈ A, então vi precede vj em S. Se G representa uma rede de tarefas, isto é: Os elementos de V denotam tarefas Os elementos de A denotam dependências entre tarefas (restrições de ordem) Então: Uma ordenação topológica de G indica uma ordem em que as tarefas podem ser realizadas, sem que as restrições de ordem entre elas sejam violadas gravata paletó cueca camisa cinto calça relógio meias sapatos 1 2 3 4 5 6 7 8 9 Prof. Dr. Silvio do Lago Pereira – DTI / FATEC-SP 19 Ordenação topológica: funcionamento 1 2 3 4 5 6 7 8 9 1 2 3 4 5 6 7 8 9 1 2 3 4 5 6 7 8 9 1 2 3 4 5 6 7 8 9 1 2 3 4 5 6 7 8 9 1 2 3 4 5 6 7 8 9 1 2 3 4 5 6 7 8 9 1 2 3 4 5 6 7 8 9 1 2 3 4 5 6 7 8 9 1 2 3 4 5 6 7 8 9 OrdenaOrdenaOrdenaOrdenaçççção topolão topolão topolão topolóóóógica: [3, 4, 1, 6, 5, 2, 7, 8, 9]gica: [3, 4, 1, 6, 5, 2, 7, 8, 9]gica: [3, 4, 1, 6, 5, 2, 7, 8, 9]gica: [3, 4, 1, 6, 5, 2, 7, 8, 9] Prof. Dr. Silvio do Lago Pereira – DTI / FATEC-SP 20 Ordenação topológica: implementação Exemplo 4. Ordenação topológicaExemplo 4. Ordenação topológica grafografografografo(1,[1, 2, 3, 4, 5, 6, 7, 8, 9],(1,[1, 2, 3, 4, 5, 6, 7, 8, 9],(1,[1, 2, 3, 4, 5, 6, 7, 8, 9],(1,[1, 2, 3, 4, 5, 6, 7, 8, 9], [1<2, 3<6, 4<1, 4<5, 5<2, 6<5, 6<9, 8<9]).[1<2, 3<6, 4<1, 4<5, 5<2, 6<5, 6<9, 8<9]).[1<2, 3<6, 4<1, 4<5, 5<2, 6<5, 6<9, 8<9]).[1<2, 3<6, 4<1, 4<5, 5<2, 6<5, 6<9, 8<9]). ordtopordtopordtopordtop(G,S) :(G,S) :(G,S) :(G,S) :---- grafo(G,grafo(G,grafo(G,grafo(G,VsVsVsVs,As),,As),,As),,As), ordtopordtopordtopordtop((((VsVsVsVs,As,S).,As,S).,As,S).,As,S). ordtopordtopordtopordtop([],_,[]).([],_,[]).([],_,[]).([],_,[]). ordtopordtopordtopordtop((((VsVsVsVs,As,[,As,[,As,[,As,[V|SV|SV|SV|S]) :]) :]) :]) :---- appendappendappendappend(E,[(E,[(E,[(E,[V|DV|DV|DV|D],],],],VsVsVsVs),),),), notnotnotnot((((membermembermembermember(_<V,As)),(_<V,As)),(_<V,As)),(_<V,As)), appendappendappendappend(E,D,(E,D,(E,D,(E,D,NVsNVsNVsNVs),),),), findallfindallfindallfindall(X<Y,(X<Y,(X<Y,(X<Y,((((membermembermembermember(X<Y,As),X(X<Y,As),X(X<Y,As),X(X<Y,As),X\\\\=V)=V)=V)=V),,,,NAsNAsNAsNAs),),),), ordtopordtopordtopordtop((((NVsNVsNVsNVs,,,,NAsNAsNAsNAs,S).,S).,S).,S). grafografografografo(1,[1, 2, 3, 4, 5, 6, 7, 8, 9],(1,[1, 2, 3, 4, 5, 6, 7, 8, 9],(1,[1, 2, 3, 4, 5, 6, 7, 8, 9],(1,[1, 2, 3, 4, 5, 6, 7, 8, 9], [1<2, 3<6, 4<1, 4<5, 5<2, 6<5, 6<9, 8<9]).[1<2, 3<6, 4<1, 4<5, 5<2, 6<5, 6<9, 8<9]).[1<2, 3<6, 4<1, 4<5, 5<2, 6<5, 6<9, 8<9]).[1<2, 3<6, 4<1, 4<5, 5<2, 6<5, 6<9, 8<9]). ordtopordtopordtopordtop(G,S) :(G,S) :(G,S) :(G,S) :---- grafo(G,grafo(G,grafo(G,grafo(G,VsVsVsVs,As),,As),,As),,As), ordtopordtopordtopordtop((((VsVsVsVs,As,S).,As,S).,As,S).,As,S). ordtopordtopordtopordtop([],_,[]).([],_,[]).([],_,[]).([],_,[]). ordtopordtopordtopordtop((((VsVsVsVs,As,[,As,[,As,[,As,[V|SV|SV|SV|S]) :]) :]) :]) :---- appendappendappendappend(E,[(E,[(E,[(E,[V|DV|DV|DV|D],],],],VsVsVsVs),),),), notnotnotnot((((membermembermembermember(_<V,As)),(_<V,As)),(_<V,As)),(_<V,As)), appendappendappendappend(E,D,(E,D,(E,D,(E,D,NVsNVsNVsNVs),),),), findallfindallfindallfindall(X<Y,(X<Y,(X<Y,(X<Y,((((membermembermembermember(X<Y,As),X(X<Y,As),X(X<Y,As),X(X<Y,As),X\\\\=V)=V)=V)=V),,,,NAsNAsNAsNAs),),),), ordtopordtopordtopordtop((((NVsNVsNVsNVs,,,,NAsNAsNAsNAs,S).,S).,S).,S). Exercício 10. Ordenação topológicaExercício 10. Ordenação topológica Digite o programa do Exemplo 4 e faça a consulta: ????---- ordtopordtopordtopordtop(1,S).(1,S).(1,S).(1,S). Digite o programa do Exemplo 4 e faça a consulta: ????---- ordtopordtopordtopordtop(1,S).(1,S).(1,S).(1,S). Prof. Dr. Silvio do Lago Pereira – DTI / FATEC-SP 21 Ordenação topológica Exercício 11. Exibição de todas as soluçõesExercício 11. Exibição de todas as soluções Represente o grafo a seguir e faça a consulta indicada. ????---- forallforallforallforall((((ordtopordtopordtopordtop(2,S)(2,S)(2,S)(2,S), , , , writelnwritelnwritelnwriteln(S)(S)(S)(S))))).... Represente o grafo a seguir e faça a consulta indicada. ????---- forallforallforallforall((((ordtopordtopordtopordtop(2,S)(2,S)(2,S)(2,S), , , , writelnwritelnwritelnwriteln(S)(S)(S)(S))))).... Exercício 12. Ordenação topológica versus permutaçãoExercício 12. Ordenação topológica versus permutação Quando não há restrições de ordem entre os vértices do grafo, a ordenação topológica funciona como permutação. Para verificar este fato, represente o grafo a seguir e faça a consulta indicada: ????---- forallforallforallforall((((ordtopordtopordtopordtop(3,S)(3,S)(3,S)(3,S), , , , writelnwritelnwritelnwriteln(S)(S)(S)(S))))).... Quando não há restrições de ordem entre os vértices do grafo, a ordenação topológica funciona como permutação. Para verificar este fato, represente o grafo a seguir e faça a consulta indicada: ????---- forallforallforallforall((((ordtopordtopordtopordtop(3,S)(3,S)(3,S)(3,S),, , , writelnwritelnwritelnwriteln(S)(S)(S)(S))))).... 1 2 3 1 2 3 4 Árvores de busca binária definição manipulação Prof. Dr. Silvio do Lago Pereira – DTI / FATEC-SP 23 Árvores de busca binária Uma árvore binária AAAAUma árvore binária AAAA é uma estrutura composta por n nós tal que se n=0, dizemos que A é vazia (representada por ####); caso contrário: existe um nó especial em AAAA denominado raiz os demais nós de AAAA são organizados em estruturas disjuntas: uma subárvore binária esquerda E uma subárvore binária direita D é uma estrutura composta por n nós tal que se n=0, dizemos que A é vazia (representada por ####); caso contrário: existe um nó especial em AAAA denominado raiz os demais nós de AAAA são organizados em estruturas disjuntas: uma subárvore binária esquerda E uma subárvore binária direita D RRRR EEEE DDDD Uma árvore de busca binária AAAAUma árvore de busca binária AAAA é uma árvore binária vazia ou uma estrutura nnnnóóóó(R,E,D)(R,E,D)(R,E,D)(R,E,D) tal que: • todo elemento em EEEE é menor ou igual a RRRR • todo elemento em DDDD é maior que RRRR é uma árvore binária vazia ou uma estrutura nnnnóóóó(R,E,D)(R,E,D)(R,E,D)(R,E,D) tal que: • todo elemento em EEEE é menor ou igual a RRRR • todo elemento em DDDD é maior que RRRR 62 1 3 5 7 4 Prof. Dr. Silvio do Lago Pereira – DTI / FATEC-SP 24 Árvore de busca binária Exemplo 5. Criação de árvore de busca bináriaExemplo 5. Criação de árvore de busca binária abbabbabbabb([],A,A).([],A,A).([],A,A).([],A,A). abbabbabbabb([([([([X|XsX|XsX|XsX|Xs],A,A2) :],A,A2) :],A,A2) :],A,A2) :---- ins(X,A,A1), abb(ins(X,A,A1), abb(ins(X,A,A1), abb(ins(X,A,A1), abb(XsXsXsXs,A1,A2).,A1,A2).,A1,A2).,A1,A2). insinsinsins(X,#,n(X,#,n(X,#,n(X,#,nóóóó(X,#,#)).(X,#,#)).(X,#,#)).(X,#,#)). insinsinsins(X,n(X,n(X,n(X,nóóóó(R,E,D),n(R,E,D),n(R,E,D),n(R,E,D),nóóóó(R,N,D)) :(R,N,D)) :(R,N,D)) :(R,N,D)) :---- X=<R, !, X=<R, !, X=<R, !, X=<R, !, insinsinsins(X,E,N).(X,E,N).(X,E,N).(X,E,N). insinsinsins(X,n(X,n(X,n(X,nóóóó(R,E,D),n(R,E,D),n(R,E,D),n(R,E,D),nóóóó(R,E,N)) :(R,E,N)) :(R,E,N)) :(R,E,N)) :---- insinsinsins(X,D,N).(X,D,N).(X,D,N).(X,D,N). abbabbabbabb([],A,A).([],A,A).([],A,A).([],A,A). abbabbabbabb([([([([X|XsX|XsX|XsX|Xs],A,A2) :],A,A2) :],A,A2) :],A,A2) :---- ins(X,A,A1), abb(ins(X,A,A1), abb(ins(X,A,A1), abb(ins(X,A,A1), abb(XsXsXsXs,A1,A2).,A1,A2).,A1,A2).,A1,A2). insinsinsins(X,#,n(X,#,n(X,#,n(X,#,nóóóó(X,#,#)).(X,#,#)).(X,#,#)).(X,#,#)). insinsinsins(X,n(X,n(X,n(X,nóóóó(R,E,D),n(R,E,D),n(R,E,D),n(R,E,D),nóóóó(R,N,D)) :(R,N,D)) :(R,N,D)) :(R,N,D)) :---- X=<R, !, X=<R, !, X=<R, !, X=<R, !, insinsinsins(X,E,N).(X,E,N).(X,E,N).(X,E,N). insinsinsins(X,n(X,n(X,n(X,nóóóó(R,E,D),n(R,E,D),n(R,E,D),n(R,E,D),nóóóó(R,E,N)) :(R,E,N)) :(R,E,N)) :(R,E,N)) :---- insinsinsins(X,D,N).(X,D,N).(X,D,N).(X,D,N). Exercício 13. Criação de árvore de busca bináriaExercício 13. Criação de árvore de busca binária Digite o programa do Exemplo 5, faça a consulta a seguir e desenhe a árvore obtida: ????---- abb([3,5,1,0,4,2],A).abb([3,5,1,0,4,2],A).abb([3,5,1,0,4,2],A).abb([3,5,1,0,4,2],A). Digite o programa do Exemplo 5, faça a consulta a seguir e desenhe a árvore obtida: ????---- abb([3,5,1,0,4,2],A).abb([3,5,1,0,4,2],A).abb([3,5,1,0,4,2],A).abb([3,5,1,0,4,2],A). Exercício 14. Exibição de árvore de busca bináriaExercício 14. Exibição de árvore de busca binária Complete o programa do Exemplo 5 com um predicado para exibir os elementos de uma árvore de busca binária em ordem crescente. Complete o programa do Exemplo 5 com um predicado para exibir os elementos de uma árvore de busca binária em ordem crescente. Código de Huffman definição implementação Prof. Dr. Silvio do Lago Pereira – DTI / FATEC-SP 26 Exemplo 6. Códigos de HuffmanExemplo 6. Códigos de Huffman Texto: MARMELADATexto: MARMELADA Código de Huffman O código de HuffmanO código de Huffman para um texto TTTT é uma atribuição de códigos binários aos caracteres de TTTT que minimiza o número médio de bits por caractere. para um texto TTTT é uma atribuição de códigos binários aos caracteres de TTTT que minimiza o número médio de bits por caractere. Para obter os códigos de Huffman para os caracteres de um texto TTTT: Obtenha as frequências dos caracteres em TTTT . Crie uma floresta contendo uma árvore unitária com a frequência de cada um dos caracteres. Juntes as árvores de menores frequências, duas a duas, até que seja obtida uma única árvore. Associe um bit 0000 às subárvores esquerdas e um bit 1 às subárvores direitas. 1 DDDD 1 EEEE 1 LLLL 1 RRRR 2 MMMM 3 AAAA 2 2 5 4 9 0 0 0 0 0 1 1 1 11 Prof. Dr. Silvio do Lago Pereira – DTI / FATEC-SP 27 Código de Huffman Exemplo 6. Frequência dos caracteresExemplo 6. Frequência dos caracteres freqfreqfreqfreq([],F1,F2) :([],F1,F2) :([],F1,F2) :([],F1,F2) :---- !, sort(F1,F2).!, sort(F1,F2).!, sort(F1,F2).!, sort(F1,F2). freqfreqfreqfreq([([([([S|SsS|SsS|SsS|Ss],F1,F3) :],F1,F3) :],F1,F3) :],F1,F3) :---- ins(S,F1,F2), freq(ins(S,F1,F2), freq(ins(S,F1,F2), freq(ins(S,F1,F2), freq(SsSsSsSs,F2,F3).,F2,F3).,F2,F3).,F2,F3). insinsinsins(X,[],[n(X,[],[n(X,[],[n(X,[],[nóóóó(1,X,#,#)]) :(1,X,#,#)]) :(1,X,#,#)]) :(1,X,#,#)]) :---- !.!.!.!. insinsinsins(X,[n(X,[n(X,[n(X,[nóóóó(F,X,#,#)|R],[n(F,X,#,#)|R],[n(F,X,#,#)|R],[n(F,X,#,#)|R],[nóóóó(G,X,#,#)|R]) :(G,X,#,#)|R]) :(G,X,#,#)|R]) :(G,X,#,#)|R]) :---- !, G is F+1.!, G is F+1.!, G is F+1.!, G is F+1. insinsinsins(X,[n(X,[n(X,[n(X,[nóóóó(F,Y,#,#)|R],[n(F,Y,#,#)|R],[n(F,Y,#,#)|R],[n(F,Y,#,#)|R],[nóóóó(F,Y,#,#)|N]) :(F,Y,#,#)|N]) :(F,Y,#,#)|N]) :(F,Y,#,#)|N]) :---- ins(X,R,N).ins(X,R,N).ins(X,R,N).ins(X,R,N). freqfreqfreqfreq([],F1,F2) :([],F1,F2) :([],F1,F2) :([],F1,F2) :---- !, sort(F1,F2).!, sort(F1,F2).!, sort(F1,F2).!, sort(F1,F2). freqfreqfreqfreq([([([([S|SsS|SsS|SsS|Ss],F1,F3) :],F1,F3) :],F1,F3) :],F1,F3) :---- ins(S,F1,F2), freq(ins(S,F1,F2), freq(ins(S,F1,F2), freq(ins(S,F1,F2), freq(SsSsSsSs,F2,F3).,F2,F3).,F2,F3).,F2,F3). insinsinsins(X,[],[n(X,[],[n(X,[],[n(X,[],[nóóóó(1,X,#,#)]) :(1,X,#,#)]) :(1,X,#,#)]) :(1,X,#,#)]) :---- !.!.!.!. insinsinsins(X,[n(X,[n(X,[n(X,[nóóóó(F,X,#,#)|R],[n(F,X,#,#)|R],[n(F,X,#,#)|R],[n(F,X,#,#)|R],[nóóóó(G,X,#,#)|R]) :(G,X,#,#)|R]) :(G,X,#,#)|R]) :(G,X,#,#)|R]) :---- !, G is F+1.!, G is F+1.!, G is F+1.!, G is F+1. insinsinsins(X,[n(X,[n(X,[n(X,[nóóóó(F,Y,#,#)|R],[n(F,Y,#,#)|R],[n(F,Y,#,#)|R],[n(F,Y,#,#)|R],[nóóóó(F,Y,#,#)|N]) :(F,Y,#,#)|N]) :(F,Y,#,#)|N]) :(F,Y,#,#)|N]) :---- ins(X,R,N).ins(X,R,N).ins(X,R,N).ins(X,R,N). Exercício 15. Frequência dos caracteresExercício 15. Frequência dos caracteres Digite o programa do Exemplo 6 e faça as consultas a seguir: ????---- atom_charsatom_charsatom_charsatom_chars(marmelada,S).(marmelada,S).(marmelada,S).(marmelada,S). ????---- atom_charsatom_charsatom_charsatom_chars(marmelada,S), (marmelada,S), (marmelada,S), (marmelada,S), freqfreqfreqfreq(S,[],F).(S,[],F).(S,[],F).(S,[],F). Digite o programa do Exemplo 6 e faça as consultas a seguir: ????---- atom_charsatom_charsatom_charsatom_chars(marmelada,S).(marmelada,S).(marmelada,S).(marmelada,S). ????---- atom_charsatom_charsatom_charsatom_chars(marmelada,S), (marmelada,S), (marmelada,S), (marmelada,S), freqfreqfreqfreq(S,[],F).(S,[],F).(S,[],F).(S,[],F). Note que a lista de frequências dos caracteres FFFF é uma floresta!Note que a lista de frequências dos caracteres FFFF é uma floresta! Prof. Dr. Silvio do Lago Pereira – DTI / FATEC-SP 28 Código de Huffman Exemplo 7. Construção da árvore de HuffmanExemplo 7. Construção da árvore de Huffman arvhufarvhufarvhufarvhuf([A],A) :([A],A) :([A],A) :([A],A) :---- !!!!.... arvhufarvhufarvhufarvhuf([A1,A2|A],B) :([A1,A2|A],B) :([A1,A2|A],B) :([A1,A2|A],B) :---- A1 = nA1 = nA1 = nA1 = nóóóó(F1,_,_,_),(F1,_,_,_),(F1,_,_,_),(F1,_,_,_),A2 = nA2 = nA2 = nA2 = nóóóó(F2,_,_,_),(F2,_,_,_),(F2,_,_,_),(F2,_,_,_), F3 is F1 + F2,F3 is F1 + F2,F3 is F1 + F2,F3 is F1 + F2, sortsortsortsort([n([n([n([nóóóó(F3,(F3,(F3,(F3,----,A1,A2)|A],As),,A1,A2)|A],As),,A1,A2)|A],As),,A1,A2)|A],As), arvhufarvhufarvhufarvhuf(As,B).(As,B).(As,B).(As,B). arvhufarvhufarvhufarvhuf([A],A) :([A],A) :([A],A) :([A],A) :---- !!!!.... arvhufarvhufarvhufarvhuf([A1,A2|A],B) :([A1,A2|A],B) :([A1,A2|A],B) :([A1,A2|A],B) :---- A1 = nA1 = nA1 = nA1 = nóóóó(F1,_,_,_),(F1,_,_,_),(F1,_,_,_),(F1,_,_,_), A2 = nA2 = nA2 = nA2 = nóóóó(F2,_,_,_),(F2,_,_,_),(F2,_,_,_),(F2,_,_,_), F3 is F1 + F2,F3 is F1 + F2,F3 is F1 + F2,F3 is F1 + F2, sortsortsortsort([n([n([n([nóóóó(F3,(F3,(F3,(F3,----,A1,A2)|A],As),,A1,A2)|A],As),,A1,A2)|A],As),,A1,A2)|A],As), arvhufarvhufarvhufarvhuf(As,B).(As,B).(As,B).(As,B). Exercício 15. Construção da árvore de HuffmanExercício 15. Construção da árvore de Huffman Digite o programa do Exemplo 7 e faça as consultas a seguir: ????---- atom_charsatom_charsatom_charsatom_chars(marmelada,S), (marmelada,S), (marmelada,S), (marmelada,S), freqfreqfreqfreq(S,[],F), arvhuf(F,A).(S,[],F), arvhuf(F,A).(S,[],F), arvhuf(F,A).(S,[],F), arvhuf(F,A). Digite o programa do Exemplo 7 e faça as consultas a seguir: ????---- atom_charsatom_charsatom_charsatom_chars(marmelada,S), (marmelada,S), (marmelada,S), (marmelada,S), freqfreqfreqfreq(S,[],F), arvhuf(F,A).(S,[],F), arvhuf(F,A).(S,[],F), arvhuf(F,A).(S,[],F), arvhuf(F,A). Prof. Dr. Silvio do Lago Pereira – DTI / FATEC-SP 29 Código de Huffman Exemplo 8. Exibição dos códigosExemplo 8. Exibição dos códigos ccccóóóódigosdigosdigosdigos(n(n(n(nóóóó(_,S,#,#),C) :(_,S,#,#),C) :(_,S,#,#),C) :(_,S,#,#),C) :---- !!!!, , , , reversereversereversereverse(C,R), (C,R), (C,R), (C,R), atom_charsatom_charsatom_charsatom_chars(A,R), (A,R), (A,R), (A,R), writelnwritelnwritelnwriteln(S : A).(S : A).(S : A).(S : A). ccccóóóódigosdigosdigosdigos(n(n(n(nóóóó(_,_,E,D),C) :(_,_,E,D),C) :(_,_,E,D),C) :(_,_,E,D),C) :---- ccccóóóódigos(E,['0'|C]), cdigos(E,['0'|C]), cdigos(E,['0'|C]), cdigos(E,['0'|C]), cóóóódigos(D,['1'|C]).digos(D,['1'|C]).digos(D,['1'|C]).digos(D,['1'|C]). ccccóóóódigosdigosdigosdigos(n(n(n(nóóóó(_,S,#,#),C) :(_,S,#,#),C) :(_,S,#,#),C) :(_,S,#,#),C) :---- !!!!, , , , reversereversereversereverse(C,R), (C,R), (C,R), (C,R), atom_charsatom_charsatom_charsatom_chars(A,R), (A,R), (A,R), (A,R), writelnwritelnwritelnwriteln(S : A).(S : A).(S : A).(S : A). ccccóóóódigosdigosdigosdigos(n(n(n(nóóóó(_,_,E,D),C) :(_,_,E,D),C) :(_,_,E,D),C) :(_,_,E,D),C) :---- ccccóóóódigos(E,['0'|C]), cdigos(E,['0'|C]), cdigos(E,['0'|C]), cdigos(E,['0'|C]), cóóóódigos(D,['1'|C]).digos(D,['1'|C]).digos(D,['1'|C]).digos(D,['1'|C]). Exercício 16. Exibição dos códigosExercício 16. Exibição dos códigos Digite o programa do Exemplo 8 e faça as consultas a seguir: ????---- atom_charsatom_charsatom_charsatom_chars(marmelada,S), (marmelada,S), (marmelada,S), (marmelada,S), freqfreqfreqfreq(S,[],(S,[],(S,[],(S,[],F), arvhuf(F,A), cF), arvhuf(F,A), cF), arvhuf(F,A), cF), arvhuf(F,A), cóóóódigos(A,[]).digos(A,[]).digos(A,[]).digos(A,[]). Digite o programa do Exemplo 8 e faça as consultas a seguir: ????---- atom_charsatom_charsatom_charsatom_chars(marmelada,S), (marmelada,S), (marmelada,S), (marmelada,S), freqfreqfreqfreq(S,[],(S,[],(S,[],(S,[],F), arvhuf(F,A), cF), arvhuf(F,A), cF), arvhuf(F,A), cF), arvhuf(F,A), cóóóódigos(A,[]).digos(A,[]).digos(A,[]).digos(A,[]). Exercício 17. Programa principalExercício 17. Programa principal Defina o predicado hufhufhufhuf(T)(T)(T)(T), que exibe os códigos de Huffman para o texto TTTT: ????---- huf(huf(huf(huf(‘‘‘‘MARMELADAMARMELADAMARMELADAMARMELADA'''').).).). Defina o predicado hufhufhufhuf(T)(T)(T)(T), que exibe os códigos de Huffman para o texto TTTT: ????---- huf(huf(huf(huf(‘‘‘‘MARMELADAMARMELADAMARMELADAMARMELADA'''').).).). Prof. Dr. Silvio do Lago Pereira – DTI / FATEC-SP 30 Bônus: interface gráfica ::::---- use_moduleuse_moduleuse_moduleuse_module((((librarylibrarylibrarylibrary(tabular)).(tabular)).(tabular)).(tabular)). hufhufhufhuf ::::---- newnewnewnew(F,frame('C(F,frame('C(F,frame('C(F,frame('Cóóóódigos de Huffman')),digos de Huffman')),digos de Huffman')),digos de Huffman')), sendsendsendsend(F,(F,(F,(F,appendappendappendappend,,,,newnewnewnew(D,(D,(D,(D,dialogdialogdialogdialog)),)),)),)), sendsendsendsend(D,(D,(D,(D,aboveaboveaboveabove,,,,newnewnewnew(P,(P,(P,(P,picturepicturepicturepicture)),)),)),)), sendsendsendsend(P,(P,(P,(P,sizesizesizesize,,,,sizesizesizesize(210,100)),(210,100)),(210,100)),(210,100)), sendsendsendsend(P,display,(P,display,(P,display,(P,display,newnewnewnew(T,tabular)), (T,tabular)), (T,tabular)), (T,tabular)), sendsendsendsend(T,(T,(T,(T,borderborderborderborder,1),,1),,1),,1), sendsendsendsend(T,(T,(T,(T,rulesrulesrulesrules,,,,allallallall),),),), sendsendsendsend(D,(D,(D,(D,appendappendappendappend,,,,newnewnewnew(I,(I,(I,(I,text_itemtext_itemtext_itemtext_item(texto))),(texto))),(texto))),(texto))), sendsendsendsend(D,(D,(D,(D,appendappendappendappend,,,,buttonbuttonbuttonbutton((((okokokok,,,,andandandand((((andandandand((((messagemessagemessagemessage(T,(T,(T,(T,clearclearclearclear),),),), messagemessagemessagemessage(@(@(@(@prologprologprologprolog,,,,hufhufhufhuf,T,I,T,I,T,I,T,I????selectionselectionselectionselection)),)),)),)), messagemessagemessagemessage(I,(I,(I,(I,clearclearclearclear)))),)))),)))),)))), sendsendsendsend(D,(D,(D,(D,appendappendappendappend,,,,buttonbuttonbuttonbutton(sair,(sair,(sair,(sair,messagemessagemessagemessage(F,(F,(F,(F,destroydestroydestroydestroy))),))),))),))), sendsendsendsend(F,open).(F,open).(F,open).(F,open). Prof. Dr. Silvio do Lago Pereira – DTI / FATEC-SP 31 Bônus: interface gráfica hufhufhufhuf(T,I) :(T,I) :(T,I) :(T,I) :---- atom_charsatom_charsatom_charsatom_chars(I,L),(I,L),(I,L),(I,L), freqfreqfreqfreq(L,[],F),(L,[],F),(L,[],F),(L,[],F), arvhufarvhufarvhufarvhuf(F,A),(F,A),(F,A),(F,A), ccccóóóódigos(T,A,[]).digos(T,A,[]).digos(T,A,[]).digos(T,A,[]). freqfreqfreqfreq([],F1,F2) :([],F1,F2) :([],F1,F2) :([],F1,F2) :---- !!!!, , , , sortsortsortsort(F1,F2).(F1,F2).(F1,F2).(F1,F2). freqfreqfreqfreq([([([([S|SsS|SsS|SsS|Ss],F1,F3) :],F1,F3) :],F1,F3) :],F1,F3) :---- insinsinsins(S,F1,F2),(S,F1,F2),(S,F1,F2),(S,F1,F2), freqfreqfreqfreq((((SsSsSsSs,F2,F3).,F2,F3).,F2,F3).,F2,F3). insinsinsins(X,[],[n(X,[],[n(X,[],[n(X,[],[nóóóó(1,X,#,#)]) :(1,X,#,#)]) :(1,X,#,#)]) :(1,X,#,#)]) :---- !.!.!.!. insinsinsins(X,[n(X,[n(X,[n(X,[nóóóó(F,X,#,#)|R],[n(F,X,#,#)|R],[n(F,X,#,#)|R],[n(F,X,#,#)|R],[nóóóó(G,X,#,#)|R]) :(G,X,#,#)|R]) :(G,X,#,#)|R]) :(G,X,#,#)|R]) :---- !, G is F+1.!, G is F+1.!, G is F+1.!, G is F+1. insinsinsins(X,[n(X,[n(X,[n(X,[nóóóó(F,Y,#,#)|R],[n(F,Y,#,#)|R],[n(F,Y,#,#)|R],[n(F,Y,#,#)|R],[nóóóó(F,Y,#,#)|N]) :(F,Y,#,#)|N]) :(F,Y,#,#)|N]) :(F,Y,#,#)|N]) :---- insinsinsins(X,R,N).(X,R,N).(X,R,N).(X,R,N). Prof. Dr. Silvio do Lago Pereira – DTI / FATEC-SP 32 Bônus: interface gráfica arvhufarvhufarvhufarvhuf([A],A) :([A],A) :([A],A) :([A],A) :---- !.!.!.!. arvhufarvhufarvhufarvhuf([A1,A2|A],B) :([A1,A2|A],B) :([A1,A2|A],B) :([A1,A2|A],B) :---- A1 = nA1 = nA1 = nA1 = nóóóó(F1,_,_,_),(F1,_,_,_),(F1,_,_,_),(F1,_,_,_), A2 = nA2 = nA2 = nA2 = nóóóó(F2,_,_,_),(F2,_,_,_),(F2,_,_,_),(F2,_,_,_), F3 F3 F3 F3 isisisis F1+F2,F1+F2,F1+F2,F1+F2, sortsortsortsort([n([n([n([nóóóó(F3,(F3,(F3,(F3,----,A1,A2)|A],As),,A1,A2)|A],As),,A1,A2)|A],As),,A1,A2)|A],As), arvhufarvhufarvhufarvhuf(As,B).(As,B).(As,B).(As,B). ccccóóóódigosdigosdigosdigos(T,n(T,n(T,n(T,nóóóó(_,S,#,#),C) :(_,S,#,#),C) :(_,S,#,#),C) :(_,S,#,#),C) :---- !, !, !, !, reversereversereversereverse(C,CR), (C,CR), (C,CR), (C,CR), atom_charsatom_charsatom_charsatom_chars(A,CR),(A,CR),(A,CR),(A,CR), sendsendsendsend(T,(T,(T,(T,appendappendappendappend,S,,S,,S,,S,boldboldboldbold,,,,leftleftleftleft,,,,colspancolspancolspancolspan:=:=:=:=1),1),1),1),sendsendsendsend(T,(T,(T,(T,appendappendappendappend,A,,A,,A,,A,boldboldboldbold,,,,leftleftleftleft,,,,colspancolspancolspancolspan:=:=:=:=1),1),1),1), sendsendsendsend(T,(T,(T,(T,next_rownext_rownext_rownext_row).).).). ccccóóóódigosdigosdigosdigos(T,n(T,n(T,n(T,nóóóó(_,_,E,D),C) :(_,_,E,D),C) :(_,_,E,D),C) :(_,_,E,D),C) :---- ccccóóóódigos(T,E,['0'|C]),digos(T,E,['0'|C]),digos(T,E,['0'|C]),digos(T,E,['0'|C]), ccccóóóódigos(T,D,['1'|C]).digos(T,D,['1'|C]).digos(T,D,['1'|C]).digos(T,D,['1'|C]). Fim
Compartilhar