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

Parada1 - 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 1 (não para): 09 */ 10  11 public class Parada1 { 12     public void soma () { 13         int i=10; 14         if (i<=0) return; 15         i--; 16         System.out.println ("somei"); 17         soma(); 18     } 19     public static void main(String args[]) { 20         Parada1 m = new Parada1(); 21         m.soma(); 22     } 23 }

Java2html

Métodos e pilha de execução - Aula de 01.08.2017

01 /** A construção de um método recursivo em partes. 02     Parte 1: um método que "invoca a si mesmo". 03     O que acontece quando o programa abaixo é 04     executado? 05      06     A invocação e o retorno de métodos é implementada 07     na máquina virtual Java (JVM) com a ajuda da pilha de 08     execução. Nela são armazenados o endereço de retorno 09     e os parâmetros (cabe refletir sobre o tipo dos  10     parâmetros e conectar os conceitos). 11     Note que em java, quando executamos a JVM esta, sem  12     nossa intervenção direta, invoca o método main do 13     arquivo .class que passamos como argumento de linha de 14     comando.  15      16     Na execução de qualquer método (no exemplo usaremos 17     main), quando INVOCAMOS um método (que pode ser outro 18     ou pode ser o mesmo), antes de executar o código que 19     você escreveu, são escritos na pilha o endereço de memória 20     do próximo comando no método "invocador" (main), a que  21     chamamos endereço de retorno, e copiados  22     os valores que devem ser armazenados nos parâmetros. Então 23     passa-se a executar o método invocado. 24      25     Ainda antes de executar o código que você escreveu,  26     os parâmetros (mais precisamente as  27     variáveis locais ao método que têm os identificadores 28     que correspondem aos parâmetros no código-fonte)  29     são alocados e os 30     valores desempilhados e armazenados nessas variáveis. 31      32     Note que na pilha restou somente o endereço de retorno. 33     O código que você escreveu passa a ser executado e  34     quando atingir um return ou o fim do método, o endereço 35     de retorno é desempilhado e usado para voltar a executar 36     o método "invocador".  37      38     O que também é importante observar é que se invocamos 39     métodos que não "retornam", os endereços de retorno 40     acumulam na pilha de execução e esta tem tamanho  41     limitado. Quando ultrapassa-se esse limite ocorre um 42     "transbordamento de pilha" (chamado também estouro de 43     pilha), em inglês: stack overflow. Que é a exceção  44     informada na execução do programa abaixo. 45      46 */ 47  48 public class MyClass { 49     public void soma () { 50         System.out.println ("somei"); 51         soma(); 52     } 53     public static void main(String args[]) { 54         MyClass m = new MyClass(); 55         m.soma(); 56     } 57 }

Java2html

Parâmetros - Aula de 01.08.2017

01 /** passagem de parâmetros 02     Em Java, o que é armazenado em  03     variáveis de tipo primitivo? 04     O que é armazenado em variáveis  05     de tipo abstrato (objetos)? 06     Como isso influencia a passagem de 07     parâmetros e a modificação de 08     variáveis dentro e fora do escopo 09     do método?  10     O exemplo abaixo ilustra esses 11     processos. Atenção especial sobre 12     que variáveis são modificadas pelo 13     método soma e como isso repercute 14     no método main. 15  16 */ 17  18 public class MyClass { 19     static int[] a = {1,2,3,4,5,6}; 20     public int soma (int[] a, int b) { 21         b=33; 22         a[0]=a[0]+b; 23         System.out.println (a[0]); 24         System.out.println (b); 25         return a[0]; 26     } 27     public static void main(String args[]) { 28         int x=10; 29         int y=25; 30         MyClass m = new MyClass(); 31         System.out.println("Sum of x+y = " + m.soma (a,y)); 32         System.out.println (a[0]); 33         System.out.println (y); 34     } 35 }

Java2html