Algoritmo tentativa e erro (incompleto) escrito na aula de 11.08.2017

/** INCOMPLETO: completar! */ public class MyClass {     static int[] valor={6,5,4,3,2,1};//Maior valor primeiro     static int[] peso={3,7,8,9,12,1};     static int pesoMax=20;//kg     static boolean[] solucao = new boolean[valor.length];     static int p=0; // massa na bolsa     static int value=0; // valor na bolsa     static int i =0;     public static void guloso(int i){              //Enquanto cabe itens na mochila e houver elementos a serem testados         while (p<pesoMax && i<valor.length){             if(p + peso[i]<=pesoMax){                 p+=peso[i];                 solucao[i]= true;                 value+= valor[i];                 if(p != pesoMax){                     guloso(i+1);                     p-=peso[i];                     solucao[i] = false;                     value-=valor[i];                 }                              }             i++;         }         for (int j=0; j<solucao.length; j++){             System.out.print(peso[j] + "\t ");             System.out.print(valor[j] + "\t ");             System.out.print(solucao[j]+ "\t \n");         }         System.out.println("Peso na Mochila: " + p);         System.out.println("Valor na Mochila: " + value);     }          public static void main(String args[]) {        guloso(0);     } }

Java2html

Algoritmo guloso escrito na aula de 11.08.2017

public class MyClass {     static int[] valor={6,5,4,3,2,1};//Maior valor primeiro     static int[] peso={3,7,8,9,12,1};     static int pesoMax=20;//kg     static boolean[] solucao = new boolean[valor.length];     public static void guloso(){         int p=0; // massa na bolsa         int value=0; // valor na bolsa         int i=0;         //Enquanto cabe itens na mochila e houver elementos a serem testados         while (p<pesoMax && i<valor.length){             if(p + peso[i]<pesoMax){                 p+=peso[i];                 solucao[i]= true;                 value+= valor[i];             }             i++;         }         for (int j=0; j<solucao.length; j++){             System.out.print(peso[j] + "\t ");             System.out.print(valor[j] + "\t ");             System.out.print(solucao[j]+ "\t \n");         }         System.out.println("Peso na Mochila: " + p);         System.out.println("Valor na Mochila: " + value);     }          public static void main(String args[]) {        guloso();     } }

Java2html

Pseudo-código de algoritmo de tentativa e erro (backtracking) - slide do livro do Ziviani baixado da Web - Aula de 08.08.2017

Em linhas gerais um método guloso tem os passos descritos no slide abaixo:

Desafio 1: Compare os pseudo-códigos do algoritmo guloso e do tentativa e erro. Aponte semelhanças e diferenças.


Desafio 2: Use o algoritmo de tentativa e erro para tentar resolver um problema que conhece, por exemplo o problema da mochila. Procure saber o que é árvore de execução. Simule a execução (ou: faça o teste de mesa) do algoritmo de tentativa e erro representando a simulação em uma árvore de execução.

Desafio 3: Analise o código que escreveu a fim de saber que variável ṕode ser usada como "tamanho do problema" e como o tempo de execução (ou quantidade de operações executadas, ou quantidade de comparações executadas) evolui em função do tamanho do problema.

Desafio 4: Escreva o programa, meça os tempos de execução de diferentes conjuntos de dados para o problema da mochila e construa o gráfico do tempo de execução em função do tamanho do problema. O resultado coincide com o que intuiu no desafio 1?

Problemas muito usados para exemplificar tentativa e erro:

• Passeio do cavalo;
• 8 rainhas;
• n rainhas;
• Problema da mochila;
• Problema do circuito Hamiltoniano.

Próximos assuntos em ordem cronológica (previsto em 06.08.2017):

• combinatória;
• crescimento de funções;
• divisão e conquista (exemplos: busca binária e MergeSort);
• sequências e séries, fórmulas de recorrência e fórmulas fechadas;
• demonstração por indução;
• indução fraca/forte;
• Notação Assintótica;
• Teorema Mestre;
• HeapSort;
• QuickSort;
• Cota Inferior para algoritmos de ordenação, aproximação de Stirling;
• Ordenação em tempo linear;
• Espalhamento (hashing);

Pseudo-código de algoritmo guloso - slide do livro do Ziviani baixado da Web - Aula de 04.08.2017

Em linhas gerais um método guloso tem os passos descritos no slide abaixo:

Desafio 1: Use o algoritmo guloso para tentar resolver um problema que conhece, por exemplo o problema da mochila. Analise o código que escreveu a fim de saber que variável ṕode ser usada como "tamanho do problema" e como o tempo de execução (ou quantidade de operações executadas, ou quantidade de comparações executadas) evolui em função do tamanho do problema.

Desafio 2: Escreva o programa, meça os tempos de execução e construa o gráfico do tempo de execução em função do tamanho do problema. O resultado coincide com o que intuiu no desafio 1?

Parada4 - 01.08.2017

01 /** Tentativas para fazer a sequência de invocações 02     terminar (artifícios que tentamos, mas geralmente 03     não funcionam do jeito que gostaríamos...) 04     DESAFIO: entender o que o método faz, atenção 05     especial em como ele é "terminado" e qual a  06     consequência disso sobre os métodos que o 07     invocam. 08     TENTATIVA 4 (Este já é bom!): 09 */ 10  11 public class Parada4 { 12     //int i=10; 13     public void soma (int i) { 14         //int i=10; 15         if (i<=0) return; 16         //i--; 17         soma(i-1);  /* A diferença com Parada3 é que este 18                        não modifica o valor de i no método 19                        chamador (o que pode ter consequências 20                        dependendo do que codificarmos depois. */ 21         System.out.println ("somei - " + i); 22     } 23     public static void main(String args[]) { 24         Parada4 m = new Parada4(); 25         m.soma(10); 26     } 27 }

Java2html

Parada3 - 01.08.2017

01 /** Tentativas para fazer a sequência de invocações 02     terminar (artifícios que tentamos, mas geralmente 03     não funcionam do jeito que gostaríamos...) 04     DESAFIO: entender o que o método faz, atenção 05     especial em como ele é "terminado" e qual a  06     consequência disso sobre os métodos que o 07     invocam. 08     TENTATIVA 3 (Este já é bom!): 09 */ 10  11 public class Parada3 { 12     //int i=10; 13     public void soma (int i) { 14         //int i=10; 15         if (i<=0) return; 16         System.out.println ("somei"); 17         i--;        /*Assim é mais seguro que soma(--i),  18                       que deve ter o mesmo efeito. */ 19         soma(i);    /* soma(i--) tem efeito diferente,  20                        de acordo com a norma pois 21                        --i e i-- tem precedências diferentes.*/ 22     } 23     public static void main(String args[]) { 24         Parada3 m = new Parada3(); 25         m.soma(10); 26     } 27 }

Java2html

Parada2 - 01.08.2017

01 /** Tentativas para fazer a sequência de invocações 02     terminar (artifícios que tentamos, mas geralmente 03     não funcionam do jeito que gostaríamos...) 04     DESAFIO: entender o que o método faz, atenção 05     especial em como ele é "terminado" e qual a  06     consequência disso sobre os métodos que o 07     invocam. 08     TENTATIVA 2 (Para, em determinadas condições 09     até faz o que gostaríamos, em outras condições 10     não faz... a questão é o escopo de i: a variável 11     i não foi declarada no escopo usual para métodos 12     recursivos): 13 */ 14  15 public class Parada2 { 16     int i=10; 17     public void soma () { 18         //int i=10; 19         if (i<=0) return; 20         i--; 21         System.out.println ("somei"); 22         soma(); 23     } 24     public static void main(String args[]) { 25         Parada2 m = new Parada2(); 26         m.soma(); 27     } 28 }

Java2html