links aula 22 de agosto

aula de 22.08: http://www.each.usp.br/digiampietri/SIN5013/04-inducaoII.pdf
aula de 23.08: http://www.each.usp.br/digiampietri/SIN5013/02-complexidadeAssintotica.pdf
vocabulário para argumentação matemática: http://www.comp.uems.br/~fhna/ca/180613/Alguns%20termos.pdf

Exemplo 3 de algoritmo recursivo - "quebrando" o problema em dois, fazendo duas chamadas recursivas.

import java.lang.Exception; class Produto3 {     static Exception e = new Exception();     static int prod (int a, int b) {         System.out.println ("a="+a+" b="+b);         int retVal=0;         e = new Exception();         e.printStackTrace();         if (b==1) {             return a;                 }         retVal=prod(a,b/2);         e = new Exception();         e.printStackTrace();         retVal+=prod(a,b/2);         if ((b%2)==1) {             // b é impar             retVal+=a;         }         System.out.println ("a="+a+" b="+b);         e = new Exception();         e.printStackTrace();         return retVal;     }          public static void main (String[] args) {         System.out.println (prod (3, 5));         System.out.println ("fim do main");     } }

Java2html

O aspecto mais relevante, neste momento da disciplina, é a sequência de invocações e retornos dos métodos. Neste exemplo particular é uma árvore binária.

Nesta solução, fazer duas invocações (chamadas) recursivas é uma possibilidade, idéia que pode ser notada como: prod(a,b)= prod (a,b/2) + prod (a,b/2) + ((b%2)==1)?a:0. Como notado em aula, esta solução é menos eficiente que a do exemplo 2. Através do cálculo da complexidade assintótica (assunto das próximas aulas) é possível mostrar que a função de complexidade de tempo desta solução pertence à mesma classe da função de complexidade da solução 1.

Exemplo 2 de algoritmo recursivo - "quebrando" o problema em dois.

import java.lang.Exception; class Produto22 {     static Exception e = new Exception();     static int prod (int a, int b) {         int retVal=0;         if (b==1) {             return a;                 }         retVal=2*prod(a,b/2);         if ((b%2)==1) {             // b é impar             retVal+=a;         }         return retVal;     }          public static void main (String[] args) {         System.out.println (prod (3, 5));         System.out.println ("fim do main");     } }

Java2html

O cálculo do produto pode ser feito "diminuindo o tamanho do problema de uma unidade" ié: prod(a,b) = a + prod (a, b-1), ou "diminuindo o tamanho do problema pela metade (e dobrando o valor)" ié: prod(a,b) = 2*prod(a,b/2) + ((b%2)==1)?a:0. O tempo de execução da primeira solução é proporcional ao valor de b, o da segunda é proporcional ao log de b na base 2.

Exemplo de recursão com impressão da pilha de execução

import java.lang.Exception; class Produto1 {     static Exception e = new Exception();     static int prod (int a, int b) {         System.out.println ("a="+a+" b="+b);         int retVal=0;         e = new Exception();         e.printStackTrace();         if (b==1) {             return a;                 }         retVal= a + prod (a, b-1);         System.out.println ("a="+a+" b="+b);         e = new Exception();         e.printStackTrace();         return retVal;     }          public static void main (String[] args) {         System.out.println (prod (3, 5));         System.out.println ("fim do main");     } }

Java2html

O objeto Exception e armazena uma representação da pilha de execução no momento em que é instanciado. Aproveito isso para imprimir a pilha de execução antes e depois de cada invocação (chamada) recursiva. Isto traz informação que permite "ver" a pilha de execução crescendo à medida em que as invocações são feitas e diminuindo à medida que as invocações retornam.

Exemplo de algoritmo recursivo: Cálculo de produto usando somas.

import java.lang.Exception; class Produto11 {     static Exception e = new Exception();     static int prod (int a, int b) {         int retVal=0;         if (b==1) {             return a;                 }         retVal= a + prod (a, b-1);         return retVal;     }          public static void main (String[] args) {         System.out.println (prod (3, 5));         System.out.println ("fim do main");     } }

Java2html

ACH2002 - Detalhamento da ementa em formato de mapa mental

Mapa mental em formato svg (gráfico escalável)
Mapa mental em formato graphML para yEd

link para yEd live
link para descrição do yEd