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

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

Introdução à Análise de Algoritmos - planejamento e referências.

Na figura a bibliografia, tópicos principais e datas importantes.

O semestre é dividido em dois períodos. O primeiro período corresponde é o de aulas, o segundo período ao de recuperação. O calendário USP 2017 contém as datas de referência.

Segundo o Regimento Geral artigo 84 (consultado em 07.03.2017), Artigo 84 – Será aprovado, com direito aos créditos correspondentes, o aluno que obtiver nota final igual ou superior a cinco e tenha, no mínimo, setenta por cento de freqüência na disciplina.

No primeiro período haverá duas provas. O estudante que deixar de fazer uma delas pode fazer a prova substitutiva sem necessidade de justificativa adicional (critério estabelecido pelo docente).

P1: 15.09.2017
P2: 24.11.2017 adiantado para 21.11.2017 devido a prova de Cálculo

PSUB: 01.12.2017
PREC: 22.01.2018 (segunda-feira)

A média das provas é calculada: MP=0.4P1+0.6*P2

No primeiro período haverá 2 Exercícios-programa (EP). Tarefas realizadas em casa, entregues através do Tidia*

* Este é o Tidia 4, até o ano passado eu usava o Tidia 3.

             divulgação                 entrega                     tema
EP1           31.08                   02.10 (22h)              backtracking
EP2           08.11                   08.12 (22h)              hashing


A média dos EP é calculada MEP=(EP1+EP2)/2

A média no primeiro período é calculada: M1=0.8*MP+0.2*MEP

Tem nota para aprovação quem obtiver M1>=5.0 (obs.: 4,95<5.0)

No segundo período é realizada a avaliação de recuperação. Pode fazê-la quem tiver M1>=3.0

PREC: 22.01.2018 (segunda-feira)

A média no segundo período é calculada:

M2=(M1+PREC)/2

Tem nota para aprovação quem obtiver M2>=5.0 (obs.: 4,95<5.0)

A frequência mínima é de 70%, comprovada por assinatura em lista de presença. O abono de faltas é regulamentado por portaria da Comissão de Graduação.