Mostrando postagens com marcador ACH2002. Mostrar todas as postagens
Mostrando postagens com marcador ACH2002. Mostrar todas as postagens

quinta-feira, 22 de agosto de 2019

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

Postado por às 2 comentários:
Marcadores:

sábado, 3 de agosto de 2019

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.

Postado por às Nenhum comentário:
Marcadores:

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.

Postado por às Nenhum comentário:
Marcadores:

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.
Postado por às Nenhum comentário:
Marcadores:

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
Postado por às Nenhum comentário:
Marcadores:

quinta-feira, 1 de agosto de 2019

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
Postado por às Nenhum comentário:
Marcadores:

domingo, 6 de agosto de 2017

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
Postado por às Nenhum comentário:
Marcadores:

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
Postado por às Nenhum comentário:
Marcadores:

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
Postado por às Nenhum comentário:
Marcadores:

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
Postado por às Nenhum comentário:
Marcadores:

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
Postado por às Nenhum comentário:
Marcadores:

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
Postado por às Nenhum comentário:
Marcadores:

terça-feira, 1 de agosto de 2017

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.



Postado por às Nenhum comentário:
Marcadores:

domingo, 12 de março de 2017

Variáveis, tipos primitivos, operações, expressões

Variáveis

Tipos primitivos

Operações Aritméticas

Bases Numéricas

Operações Lógicas Bit a Bit

Operações e expressões relacionais






Postado por às Nenhum comentário:
Marcadores: ,

Comandos para navegar no sistema de arquivos

Sistema de Arquivos é onde os arquivos são armazenados. Simplificadamente, esse sistema é composto pelo dispositivo de armazenamento, hardware de comunicação e software para uso e visualização. Não precisa haver um único dispositivo de armazenamento, nem tipos de dispositivos iguais. Também não há necessidade do hardware de comunicação ser uniforme, muito menos o software (encrenca à vista). O Sistema de Arqivos faz parte do Sistema Operacional.

Dada a concentração de uso de sistemas operacionais em algumas marcas e em duas categorias:

  1. POSIX e Windows, acho suficiente mencionar os dois. POSIX é a norma que uniformiza todos os sistemas operacionais do tipo UNIX, entre eles LINUX, Android (que é uma variante de LINUX), BSD (Berkeley Software Distribution), iOS (uma variante de BSD) se aproximam do que está nessa norma. 
  2. Windows é o sistema operacional desenvolvido, mantido e comercializado pela Microsoft.
Os dois sistemas operacionais tratam a interface do sistema de arquivos com o usuário de forma similar. Em POSIX o sistema de arquivos é organizado como uma árvore (na sua definição em teoria de grafos) e em Windows como várias árvores (uma floresta). Em ambos os nós ou são diretórios (pastas) ou arquivos. POSIX tem outros tipos de nós que não serão abordados nesta postagem.

Trabalharemos em linha de comando e somente as operações básicas.

Sempre que abrimos o terminal (linha de comando) estamos operando sobre algum diretório.

se não tiver argumento de chamada então assume diretório corrente,

OperaçãoComando POSIXComando WindowsNota
Informa diretório correntepwdcd
Lista conteúdo do diretório indicadolsdir
Cria diretóriomkdirmd
Remove diretóriormdirrd
Vai para diretóriocdcd
Copia arquivocpcopy
Remove arquivormdel
Renomeia arquivomvren
Move arquivo arquivomvmove

Todos os comandos têm help.
Em LINUX use
  <comando> --help
em Windows
  <comando> /? 

Post de 2015/2016 sobre o assunto.
 
Postado por às Nenhum comentário:
Marcadores: ,

terça-feira, 11 de agosto de 2015

ACH2002 - Notas de Aula de outros professores ou de cursos semelhantes.



http://www.uspleste.usp.br/digiampietri/ACH2002/notasdeaula.html

http://www.ime.usp.br/~pf/analise_de_algoritmos/lectures.html
Postado por às Nenhum comentário:
Marcadores:

quinta-feira, 6 de agosto de 2015

ACH2002 - Introdução a Análise de Algoritmos - Assuntos

Diagrama:

-----
Postado por às Nenhum comentário:
Marcadores:
Assinar: Postagens (Atom)