Cap 16 - Algoritmos Gulosos_Andrws

Prévia do material em texto

<p>ALGORITMOS GULOSOS</p><p>ANÁLISE E PROJETO DE ALGORITMOS</p><p>PROF. ANDRWS VIEIRA</p><p>Recapitulando</p><p>▪Programação Dinâmica: extremamente útil em problemas de</p><p>otimização com subproblemas sobrepostos</p><p>▪Recursão + Tabelas (memoização)</p><p>▪Passos:</p><p>1. Caracterizar a estrutura de uma solução ótima</p><p>2. Definir recursivamente o valor de uma solução ótima</p><p>3. Calcular o valor de uma solução ótima de baixo pra cima</p><p>4. Construir uma solução ótima com as informações calculadas</p><p>Introdução</p><p>▪ A Programação Dinâmica consiste em sempre encontrar a solução ótima</p><p>de um subproblema dividindo ele em problemas menores e mantendo os</p><p>resultados em memória para economizar tempo</p><p>▪ A memória também serve para que a solução ótima seja construída ou</p><p>atualizada com base no que já foi feito no passado</p><p>▪ No entanto, nem sempre nos preocupamos com a melhor solução</p><p>▪ Ou ainda: a melhor solução de um problema maior pode ser encontrada</p><p>tomando a melhor decisão sem pensar no resultados de subproblemas</p><p>Introdução</p><p>▪ Com base nessas premissas, surgiram os algoritmos gulosos</p><p>▪ Esses algoritmos consistem em sempre fazer a melhor escolha com base</p><p>no contexto atual, também chamada escolha localmente ótima</p><p>▪ A expectativa é que se alcance uma solução globalmente ótima com base</p><p>em diversas decisões localmente ótimas</p><p>▪ Mas se isso não for possível, nem sempre representa um problema!</p><p>Algoritmos Gulosos</p><p>▪ Alguns algoritmos importantes que usam a estratégia gulosa:</p><p>▪ Seleção de Atividades</p><p>▪ Codificação de Huffman</p><p>▪ Algoritmo de Dijkstra</p><p>▪ Árvore Geradora Mínima</p><p>Algoritmos Gulosos</p><p>▪ Passos da estratégia gulosa:</p><p>1. Determinar uma subestrutura ótima para o problema</p><p>2. Provar que, se fizermos a escolha gulosa, restará somente um</p><p>subproblema</p><p>3. Provar que é seguro fazer a escolha gulosa (quando queremos uma</p><p>solução ótima)</p><p>4. Desenvolver um algoritmo que implemente a estratégia definida</p><p>O Problema de Seleção de Atividades</p><p>▪ A tarefa consiste em programar várias atividades que requerem o uso</p><p>exclusivo de um recurso comum, com o objetivo de selecionar um</p><p>conjunto de tamanho máximo de atividades que não se sobrepõem.</p><p>▪ Exemplo: Uma secretária atrapalhada fez vários agendamentos para o</p><p>consultório de um dentista, marcando mais de um cliente no mesmo</p><p>horário.</p><p>▪ Temos N agendamentos: a1, ..., an</p><p>▪ Cada agendamento tem horário de ínicio: s1, ..., sn</p><p>▪ E de fim: f1, ..., fn</p><p>O Problema de Seleção de Atividades</p><p>ai 1 2 3 4 5 6 7 8 9 10 11</p><p>Si 1 3 0 5 3 5 6 8 8 2 12</p><p>fi 4 5 6 7 9 9 10 11 12 14 16</p><p>a3</p><p>a7</p><p>a11</p><p>Possível</p><p>Solução</p><p>a1</p><p>a4</p><p>a8</p><p>a11</p><p>t</p><p>Solução</p><p>Ótima</p><p>0. 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. 15. 16</p><p>O Problema de Seleção de Atividades</p><p>▪ Temos aqui uma subestrutura ótima:</p><p>▪ Dado um conjunto Sij de atividades que começam após uma atividade ai e</p><p>terminam antes de uma atividade aj</p><p>▪ Vamos supor que esse conjunto não é vazio, portanto existe uma atividade</p><p>ak no conjunto Sij</p><p>▪ As atividades em Sij que vêm depois de i e antes de k podem ser</p><p>representadas por Sik. Analogamente, as que vêm depois de i e antes de j</p><p>são Skj, isto é:</p><p>𝑆𝑖𝑗 = 𝑆𝑖𝑘 ∪ 𝑎𝑘 ∪ 𝑆𝑘𝑗</p><p>O Problema de Seleção de Atividades</p><p>▪ Essa relação de recorrência mostra que poderíamos resolver uma solução</p><p>para o problema usando PD</p><p>▪ Supondo uma tabela de memoização C, teríamos que:</p><p>▪ No entanto, estamos ignorando uma coisa importante que facilita nossa</p><p>vida: e se tentarmos uma escolha gulosa?</p><p>𝐶 𝑖, 𝑗 = ቐ</p><p>0 , 𝑠𝑒 𝑆𝑖𝑗 = ∅</p><p>max</p><p>𝑎𝑘∈𝑆𝑖𝑗</p><p>(𝑐 𝑖, 𝑘 + 𝑐 𝑘, 𝑗 + 1) , 𝑐. 𝑐.</p><p>O Problema de Seleção de Atividades</p><p>▪ Intuitivamente, pensamos que a melhor forma de maximizar as atividades</p><p>é pegar aquela que deixa mais tempo livre para as demais</p><p>▪ Dentre as tarefas que temos, uma delas deve ser a primeira a começar e</p><p>terminar</p><p>▪ Faz sentido que se escolhermos a tarefa que termina mais cedo, vamos</p><p>deixar mais tempo para alocar as demais</p><p>▪ Portanto, a escolhe gulosa desse algoritmo é sempre escolher a próxima</p><p>tarefa que começa depois da anterior e que termina mais cedo</p><p>O Problema de Seleção de Atividades</p><p>▪ Voltando à nossa tabela (note que já está ordenada por hora de término):</p><p>ai 1 2 3 4 5 6 7 8 9 10 11</p><p>Si 1 3 0 5 3 5 6 8 8 2 12</p><p>fi 4 5 6 7 9 9 10 11 12 14 16</p><p>S = {}</p><p>O Problema de Seleção de Atividades</p><p>▪ Voltando à nossa tabela (note que já está ordenada por hora de término):</p><p>▪ Por estratégia gulosa, vamos escolher a1 como primeira tarefa</p><p>ai 1 2 3 4 5 6 7 8 9 10 11</p><p>Si 1 3 0 5 3 5 6 8 8 2 12</p><p>fi 4 5 6 7 9 9 10 11 12 14 16</p><p>S = {a1}</p><p>O Problema de Seleção de Atividades</p><p>▪ Voltando à nossa tabela (note que já está ordenada por hora de término):</p><p>▪ Por estratégia gulosa, vamos escolher a1 como primeira tarefa</p><p>▪ a1 termina às 4, então não podemos pegar a2 nem a3</p><p>ai 1 2 3 4 5 6 7 8 9 10 11</p><p>Si 1 3 0 5 3 5 6 8 8 2 12</p><p>fi 4 5 6 7 9 9 10 11 12 14 16</p><p>S = {a1}</p><p>O Problema de Seleção de Atividades</p><p>▪ Voltando à nossa tabela (note que já está ordenada por hora de término):</p><p>▪ Por estratégia gulosa, vamos escolher a4 como segunda tarefa</p><p>ai 1 2 3 4 5 6 7 8 9 10 11</p><p>Si 1 3 0 5 3 5 6 8 8 2 12</p><p>fi 4 5 6 7 9 9 10 11 12 14 16</p><p>S = {a1, a4}</p><p>O Problema de Seleção de Atividades</p><p>▪ Voltando à nossa tabela (note que já está ordenada por hora de término):</p><p>▪ Por estratégia gulosa, vamos escolher a4 como segunda tarefa</p><p>▪ Agora a5, a6 e a7 estão fora das possibilidades</p><p>ai 1 2 3 4 5 6 7 8 9 10 11</p><p>Si 1 3 0 5 3 5 6 8 8 2 12</p><p>fi 4 5 6 7 9 9 10 11 12 14 16</p><p>S = {a1, a4}</p><p>O Problema de Seleção de Atividades</p><p>▪ Voltando à nossa tabela (note que já está ordenada por hora de término):</p><p>▪ Por estratégia gulosa, vamos escolher a8 como terceira tarefa</p><p>ai 1 2 3 4 5 6 7 8 9 10 11</p><p>Si 1 3 0 5 3 5 6 8 8 2 12</p><p>fi 4 5 6 7 9 9 10 11 12 14 16</p><p>S = {a1, a4, a8}</p><p>O Problema de Seleção de Atividades</p><p>▪ Voltando à nossa tabela (note que já está ordenada por hora de término):</p><p>▪ Por estratégia gulosa, vamos escolher a8 como terceira tarefa</p><p>▪ Agora a9 e a10 estão de fora</p><p>ai 1 2 3 4 5 6 7 8 9 10 11</p><p>Si 1 3 0 5 3 5 6 8 8 2 12</p><p>fi 4 5 6 7 9 9 10 11 12 14 16</p><p>S = {a1, a4, a8}</p><p>O Problema de Seleção de Atividades</p><p>▪ Voltando à nossa tabela (note que já está ordenada por hora de término):</p><p>▪ Por fim, escolhemos a11 e terminamos o algoritmo com 4 tarefas</p><p>concluídas!</p><p>ai 1 2 3 4 5 6 7 8 9 10 11</p><p>Si 1 3 0 5 3 5 6 8 8 2 12</p><p>fi 4 5 6 7 9 9 10 11 12 14 16</p><p>S = {a1, a4, a8, a11}</p><p>O Problema de Seleção de Atividades</p><p>▪ Implementação iterativa:</p><p>O Problema de Seleção de Atividades</p><p>▪ Implementação iterativa:</p><p>A primeira tarefa é sempre parte</p><p>da solução, pois termina primeiro</p><p>A variável k armazena o índice da última</p><p>tarefa adicionada ao conjunto solução</p><p>O Problema de Seleção de Atividades</p><p>▪ Implementação iterativa:</p><p>Aqui vamos percorrer as N tarefas para</p><p>encontrar as que podem ser adicionadas</p><p>A primeira tarefa que começa depois da última tarefa</p><p>adicionada na solução é adicionada ao conjunto</p><p>O Problema de Seleção de Atividades</p><p>▪ Implementação iterativa:</p><p>Atualizamos a variável k com a posição</p><p>da nova tarefa.</p><p>O Problema de Sele��ão de Atividades</p><p>▪ Implementação iterativa:</p><p>Complexidade Computacional:</p><p>𝚯(n)</p><p>O Problema de Seleção de Atividades</p><p>▪ Implementação em Python</p><p>Estratégia Gulosa x PD</p><p>▪ As duas estratégias exploram a subestrutura ótima da solução</p><p>▪ A estratégia gulosa normalmente aborda a solução de cima pra baixo,</p><p>enquanto que PD normalmente é implementada de baixo pra cima</p><p>▪ Por vezes utiliza-se PD quando a estratégia gulosa é suficiente</p><p>▪ Outras vezes opta-se pela estratégia gulosa quando na verdade a solução</p><p>ótima só pode ser resolvida com PD</p><p>▪ Muitas vezes a única forma de identificar isso é na prática</p><p>O Problema da Mochila (Knapsack Problem)</p><p>▪ Esse é um dos problemas mais clássicos e importantes da</p><p>computação</p><p>▪ É um problema NP-completo, como mostrado por Richard</p><p>Karp em 1972</p><p>▪ Problema: Você tem vários objetos de pesos e valores</p><p>diferentes e uma mochila que suporta no máximo N quilos.</p><p>Como maximizar o valor carregado na mochila usando</p><p>no</p><p>máximo N quilos?</p><p>▪ Vamos analisar uma variante chamada Problema da</p><p>Mochila 0-1, na qual os objetos só podem ser colocados</p><p>zero ou uma vez na mochila (sem repetição)</p><p>O Problema da Mochila 0-1</p><p>▪ O problema da mochila apresenta subestrutura ótima:</p><p>▪ Consideremos uma solução ótima (mais valiosa) com no máximo N quilos.</p><p>Se retirarmos um item j dessa solução, a solução restante contém a</p><p>solução ótima com no máximo N-pesoj quilos</p><p>▪ É um problema de PD ou podemos usar estratégia gulosa?</p><p>O Problema da Mochila 0-1</p><p>▪ Vamos pensar na seguinte instância do problema:</p><p>▪ Temos 3 itens e uma mochila que suporta no máximo 50 quilos</p><p>▪ Item 1: custa R$ 60, pesa 10</p><p>▪ Item 2: custa R$ 100, pesa 20</p><p>▪ Item 3: custa R$ 120, pesa 30</p><p>▪ Queremos maximizar a relação custo/peso</p><p>O Problema da Mochila 0-1</p><p>▪ Vamos pensar na seguinte instância do problema:</p><p>▪ Temos 3 itens e uma mochila que suporta no máximo 50 quilos</p><p>▪ Item 1: custa R$ 60, pesa 10 -> custo/peso : 6</p><p>▪ Item 2: custa R$ 100, pesa 20 -> custo/peso : 5</p><p>▪ Item 3: custa R$ 120, pesa 30 -> custo/peso : 4</p><p>▪ Queremos maximizar a relação custo/peso</p><p>O Problema da Mochila 0-1</p><p>▪ Estratégia Gulosa: vamos pegar sempre o item com maior valor</p><p>custo/peso</p><p>10</p><p>20</p><p>30</p><p>50 Mochila</p><p>R$ 60</p><p>R$ 100</p><p>R$ 120</p><p>O Problema da Mochila 0-1</p><p>▪ Estratégia Gulosa: vamos pegar sempre o item com maior valor</p><p>custo/peso</p><p>10</p><p>20</p><p>30</p><p>40 Mochila</p><p>R$ 60</p><p>R$ 100</p><p>R$ 120</p><p>Inserimos o primeiro item</p><p>com custo/peso = 6</p><p>Restaram 40</p><p>quilos na mochila</p><p>O Problema da Mochila 0-1</p><p>▪ Estratégia Gulosa: vamos pegar sempre o item com maior valor</p><p>custo/peso</p><p>10</p><p>20</p><p>30</p><p>20</p><p>Mochila</p><p>R$ 60</p><p>R$ 120</p><p>Inserimos o segunda item</p><p>com custo/peso = 5</p><p>Restaram 20</p><p>quilos na mochila</p><p>R$ 100</p><p>O Problema da Mochila 0-1</p><p>▪ Estratégia Gulosa: vamos pegar sempre o item com maior valor</p><p>custo/peso</p><p>10</p><p>20</p><p>30</p><p>20</p><p>Mochila</p><p>R$ 60</p><p>R$ 100</p><p>R$ 120</p><p>O terceiro item não cabe,</p><p>portanto nosso lucro</p><p>máximo é R$ 160 pela</p><p>estratégia gulosa</p><p>O Problema da Mochila 0-1</p><p>▪ Estratégia Gulosa: vamos pegar sempre o item com maior valor</p><p>custo/peso</p><p>20</p><p>30</p><p>Mochila</p><p>R$ 120</p><p>R$ 100</p><p>Porém solução ótima</p><p>rende R$ 220 de lucro!</p><p>10</p><p>R$ 60</p><p>O Problema da Mochila 0-1</p><p>▪ Estratégia Gulosa: vamos pegar sempre o item com maior valor</p><p>custo/peso</p><p>20</p><p>30</p><p>Mochila</p><p>R$ 120</p><p>R$ 100</p><p>Porém solução ótima</p><p>rende R$ 220 de lucro!</p><p>10</p><p>R$ 60</p><p>Uma forma de encontrar</p><p>uma solução ótima é</p><p>com PD!</p><p>Códigos de Huffman</p><p>▪ Códigos de Huffman são utilizados para comprimir dados</p><p>▪ São a base de diversos algoritmos conhecidos como ZIP</p><p>▪ São muito eficientes: compressão entre 20% e 90% são</p><p>típicas</p><p>▪ Ele mapeia caracteres para códigos binários de comprimento</p><p>variável</p><p>▪ Exemplo: a – “0”</p><p>b – “100”</p><p>c – “101</p><p>Códigos de Huffman</p><p>▪ Dado um texto de 100.000 caracteres, onde o caractere “a” se repete</p><p>45.000 vezes e todos os demais 55.000</p><p>▪ Se queremos reduzir o espaço no disco desse texto, faz sentido que temos</p><p>que reduzir ao máximo o tamanho de “a”</p><p>▪ Portanto temos que considerar sempre os caracteres pela sua frequência</p><p>no texto</p><p>Códigos de Huffman</p><p>▪ Huffman criou um algoritmo guloso capaz de gerar o menor código</p><p>possível usando essa abordagem dado um conjunto de nodos C:</p><p>freq</p><p>rightleft</p><p>Nodo</p><p>Códigos de Huffman</p><p>▪ Huffman criou um algoritmo guloso capaz de gerar o menor código</p><p>possível usando essa abordagem dado um conjunto de nodos C:</p><p>freq</p><p>rightleft</p><p>Nodo</p><p>Q é uma lista de nodos que</p><p>inicialmente estão soltos</p><p>Códigos de Huffman</p><p>▪ Huffman criou um algoritmo guloso capaz de gerar o menor código</p><p>possível usando essa abordagem dado um conjunto de nodos C:</p><p>freq</p><p>rightleft</p><p>Nodo</p><p>Vamos retirar dessa lista os dois</p><p>nodos de menor frequência</p><p>Códigos de Huffman</p><p>▪ Huffman criou um algoritmo guloso capaz de gerar o menor código</p><p>possível usando essa abordagem dado um conjunto de nodos C:</p><p>freq</p><p>rightleft</p><p>Nodo</p><p>Criamos um novo nodo com a</p><p>soma da frequência dos dois</p><p>nodos e o inserimos na lista Q</p><p>Códigos de Huffman</p><p>▪ Huffman criou um algoritmo guloso capaz de gerar o menor código</p><p>possível usando essa abordagem dado um conjunto de nodos C:</p><p>freq</p><p>rightleft</p><p>Nodo</p><p>No final da execução todos os nodos</p><p>estarão na mesma árvore Q. Aqui</p><p>retornamos a raiz dessa árvore</p><p>Códigos de Huffman – Passo a Passo</p><p>char a b c d e f</p><p>Freq. 45 13 12 16 9 5</p><p>Q =</p><p>Códigos de Huffman – Passo a Passo</p><p>char a b c d e f</p><p>Freq. 45 13 12 16 9 5</p><p>Q =</p><p>Códigos de Huffman – Passo a Passo</p><p>char a b c d e f</p><p>Freq. 45 13 12 16 9 5</p><p>Q =</p><p>Códigos de Huffman – Passo a Passo</p><p>char a b c d e f</p><p>Freq. 45 13 12 16 9 5</p><p>Q =</p><p>Códigos de Huffman – Passo a Passo</p><p>char a b c d e f</p><p>Freq. 45 13 12 16 9 5</p><p>Q =</p><p>Códigos de Huffman – Passo a Passo</p><p>char a b c d e f</p><p>Freq. 45 13 12 16 9 5</p><p>Q =</p><p>Códigos de Huffman – Passo a Passo</p><p>char a b c d e f</p><p>Freq. 45 13 12 16 9 5</p><p>Q = Q =</p><p>Códigos de Huffman – Passo a Passo</p><p>char a b c d e f</p><p>Freq. 45 13 12 16 9 5</p><p>Map. 0 101 100 111 1101 1100</p><p>Q = Q =</p><p>▪ Exemplo utilizando a árvore de Huffman:</p><p>▪ Comprimir a sequência de caracteres: AAAAAABBBBBCCCCDDDEEF</p><p>▪ Se usarmos a forma padrão onde o tamanho da representação de cada caractere</p><p>é fixo, a menor codificação que podemos utilizar para representá-la em binário é</p><p>de três bits por caractere:</p><p>▪ 000000000000000000001001001001001010010010010011011011100100101</p><p>▪ Isso dá 63 bits de comprimento.</p><p>Códigos de Huffman</p><p>▪ Exemplo utilizando a a árvore de Huffman:</p><p>▪ Comprimir a sequência de caracteres: AAAAAABBBBBCCCCDDDEEF</p><p>▪ Se usarmos a forma padrão onde o tamanho da representação de cada caractere</p><p>é fixo, a menor codificação que podemos utilizar para representá-la em binário é</p><p>de três bits por caractere:</p><p>▪ 000000000000000000001001001001001010010010010011011011100100101</p><p>▪ Isso dá 63 bits de comprimento.</p><p>Códigos de Huffman</p><p>Exercício:</p><p>Construam a árvore binária de Huffman</p><p>▪ Utilizando o algoritmo de Huffman para comprimir a sequência</p><p>AAAAAABBBBBCCCCDDDEEF chegamos na seguinte árvore:</p><p>Códigos de Huffman</p><p>char a b c d e f</p><p>Freq. 6 5 4 3 2 1</p><p>Map.</p><p>▪ Utilizando o algoritmo de Huffman para comprimir a sequência</p><p>AAAAAABBBBBCCCCDDDEEF chegamos na seguinte árvore:</p><p>Códigos de Huffman</p><p>21</p><p>9</p><p>0</p><p>12</p><p>1</p><p>C:4 B:5</p><p>0 1</p><p>A:6 6</p><p>D:6 3</p><p>F:1 E:2</p><p>1</p><p>0 1</p><p>1</p><p>0</p><p>char a b c d e f</p><p>Freq. 6 5 4 3 2 1</p><p>Map. 10 01 00 110 1111 1110</p><p>0</p><p>▪ Utilizando o algoritmo de Huffman para comprimir a sequência</p><p>AAAAAABBBBBCCCCDDDEEF chegamos na seguinte árvore:</p><p>Códigos de Huffman</p><p>21</p><p>9</p><p>0</p><p>12</p><p>1</p><p>C:4 B:5</p><p>0 1</p><p>A:6 6</p><p>D:6 3</p><p>F:1 E:2</p><p>1</p><p>0 1</p><p>1</p><p>0</p><p>char a b c d e f</p><p>Freq. 6 5 4 3 2 1</p><p>Map. 10 01 00 110 1111 1110</p><p>0</p><p>▪ Ao codificarmos a sequência original temos:</p><p>101010101010010101010100000000110110</p><p>110111111111110</p><p>▪ Totalizando apenas 51 bits. A nossa</p><p>compressão foi de 12 bits, ou cerca de 20%.</p><p>Códigos de Huffman</p><p>▪ Qual a complexidade computacional do código de Huffman?</p><p>Códigos de Huffman</p><p>▪ Qual a complexidade computacional do código de Huffman?</p><p>• Vai depender da estrutura usada para Q!</p><p>• Vamos supor um Heap Binário:</p><p>• Criação: O(n)</p><p>• Extract-Min: O(lg n)</p><p>• Insert: O(lg n)</p><p>Códigos de Huffman</p><p>▪ Qual a complexidade computacional do código de Huffman?</p><p>• Vai depender da estrutura usada para Q!</p><p>• Vamos supor um Heap Binário:</p><p>• Criação: O(n)</p><p>• Extract-Min: O(lg n)</p><p>• Insert: O(lg n)</p><p>Complexidade:</p><p>O (n lg n)</p><p>Atividade – Trabalho Final</p><p>▪Formar grupos de 3 a 4 integrantes</p><p>▪Escolher um problema clássico que possa ser</p><p>resolvido por um Algoritmo Guloso e</p><p>Programação Dinâmica</p><p>▪Postar no fórum (acrescentar tópico) com o</p><p>grupo e seus integrantes no seguinte formato:</p><p>Assunto: Grupo <Nome do Problema></p><p>Mensagem: Integrantes</p><p>PS: Um grupo não pode repetir um problema, ou seja,</p><p>escolher um problema já foi postado no fórum.</p><p>Slide 1: ALGORITMOS GULOSOS</p><p>Slide 2: Recapitulando</p><p>Slide 3: Introdução</p><p>Slide 4: Introdução</p><p>Slide 5: Algoritmos Gulosos</p><p>Slide 6: Algoritmos Gulosos</p><p>Slide 7: O Problema de Seleção de Atividades</p><p>Slide 8: O Problema de Seleção de Atividades</p><p>Slide 9: O Problema de Seleção de Atividades</p><p>Slide 10: O Problema de Seleção</p><p>de Atividades</p><p>Slide 11: O Problema de Seleção de Atividades</p><p>Slide 12: O Problema de Seleção de Atividades</p><p>Slide 13: O Problema de Seleção de Atividades</p><p>Slide 14: O Problema de Seleção de Atividades</p><p>Slide 15: O Problema de Seleção de Atividades</p><p>Slide 16: O Problema de Seleção de Atividades</p><p>Slide 17: O Problema de Seleção de Atividades</p><p>Slide 18: O Problema de Seleção de Atividades</p><p>Slide 19: O Problema de Seleção de Atividades</p><p>Slide 20: O Problema de Seleção de Atividades</p><p>Slide 21: O Problema de Seleção de Atividades</p><p>Slide 22: O Problema de Seleção de Atividades</p><p>Slide 23: O Problema de Seleção de Atividades</p><p>Slide 24: O Problema de Seleção de Atividades</p><p>Slide 25: O Problema de Seleção de Atividades</p><p>Slide 26: Estratégia Gulosa x PD</p><p>Slide 27: O Problema da Mochila (Knapsack Problem)</p><p>Slide 28: O Problema da Mochila 0-1</p><p>Slide 29: O Problema da Mochila 0-1</p><p>Slide 30: O Problema da Mochila 0-1</p><p>Slide 31: O Problema da Mochila 0-1</p><p>Slide 32: O Problema da Mochila 0-1</p><p>Slide 33: O Problema da Mochila 0-1</p><p>Slide 34: O Problema da Mochila 0-1</p><p>Slide 35: O Problema da Mochila 0-1</p><p>Slide 36: O Problema da Mochila 0-1</p><p>Slide 37: Códigos de Huffman</p><p>Slide 38: Códigos de Huffman</p><p>Slide 39: Códigos de Huffman</p><p>Slide 40: Códigos de Huffman</p><p>Slide 41: Códigos de Huffman</p><p>Slide 42: Códigos de Huffman</p><p>Slide 43: Códigos de Huffman</p><p>Slide 44: Códigos de Huffman – Passo a Passo</p><p>Slide 45: Códigos de Huffman – Passo a Passo</p><p>Slide 46: Códigos de Huffman – Passo a Passo</p><p>Slide 47: Códigos de Huffman – Passo a Passo</p><p>Slide 48: Códigos de Huffman – Passo a Passo</p><p>Slide 49: Códigos de Huffman – Passo a Passo</p><p>Slide 50: Códigos de Huffman – Passo a Passo</p><p>Slide 51: Códigos de Huffman – Passo a Passo</p><p>Slide 52: Códigos de Huffman</p><p>Slide 53: Códigos de Huffman</p><p>Slide 54: Códigos de Huffman</p><p>Slide 55: Códigos de Huffman</p><p>Slide 56: Códigos de Huffman</p><p>Slide 57: Códigos de Huffman</p><p>Slide 58: Códigos de Huffman</p><p>Slide 59: Códigos de Huffman</p><p>Slide 60: Atividade – Trabalho Final</p>