ACH2002 - Algoritmos Gulosos

http://www2.dcc.ufmg.br/livros/algoritmos/cap2/slides/c/completo1/cap2.pdf

https://pt.wikipedia.org/wiki/Algoritmo_de_Kruskal

https://pt.wikipedia.org/wiki/Algoritmo_de_Prim

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

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

Diagrama:

-----

Ler arquivo texto com e sem definição do conjunto de caracteres

01 import java.io.*; 02 import java.nio.charset.*; 03  04 public class Dump { 05    public static void main (String[] args) throws IOException { 06       FileInputStream fis; 07       try { 08          fis = new FileInputStream("t.txt"); 09       } catch (FileNotFoundException e) { 10          System.out.println ("Arquivo t.txt nao encontrado."); 11          // se não encontrou então não abriu. 12          return; 13       } 14       InputStreamReader input = new InputStreamReader (fis, StandardCharsets.UTF_8); // decodifica para utf-8 15       //InputStreamReader input = new InputStreamReader (fis); 16       /*https://docs.oracle.com/javase/7/docs/api/java/nio/charset/StandardCharsets.html*/ 17       /*http://en.wikipedia.org/wiki/UTF-8*/ 18       int c; 19       try { 20          do { 21             c=input.read(); 22             System.out.println (c); 23          } while (c>=0); 24       } catch (IOException e) { 25          System.out.println (e.getMessage()); 26       } finally { 27          input.close(); 28       } 29    } 30 } /*para ver o Ã§ e o Ã£*/

Java2html

Lista ligada

Uma lista ligada é uma coleção de nós (ou registros) em que cada um aponta (referencia) o próximo.
As operações que geralmente são executadas sobre uma lista ligada são inserção, remoção e busca. São as operações de dicionário.
Listas ligadas tem comprimento variável.
Sua tarefa é entender os métodos que inserem, removem e buscam.
Aqui está o código fonte:
https://drive.google.com/file/d/0B2aucTjhMlIVQWV6MDFLUHEwV2c/view?usp=sharing

Segue a listagem:

01 package Lista; 02 class No { 03    protected String chave, conteudo; 04    protected No prox; 05    No () { 06       chave=null; 07       conteudo=null; 08    } 09    No (String chave, String conteudo) { 10       this.chave= new String (chave); 11       this.conteudo= new String (conteudo); 12    } 13    String getChave () { 14       return new String (chave); 15    } 16    String getConteudo () { 17       return new String (conteudo); 18    } 19    No getProx () { 20       return prox; 21    } 22    void setChave (String chave) { 23       this.chave=new String (chave); 24    } 25    void setConteudo (String conteudo) { 26       this.conteudo=new String (conteudo); 27    } 28    void setProx (No prox) { 29       this.prox=prox; 30    } 31 }

Java2html

01 package Lista; 02 public class Lista { 03    protected No inicio; 04    public Lista () { 05       inicio=null; 06    } 07    public void insereNoInicio (String chave, String conteudo) { 08       No novoInicio=new No (chave, conteudo); 09       novoInicio.setProx (inicio); 10       inicio=novoInicio; 11    } 12    public void insereNoFinal (String chave, String conteudo) { 13       No aux=inicio; 14       if (aux==null) { 15          inicio=new No (chave, conteudo); 16       } else { 17          while (aux.getProx()!=null) 18             aux=aux.getProx(); 19          aux.setProx (new No (chave, conteudo)); 20       } 21    } 22    public String busca (String chave) { 23       // retorna o conteúdo 24       No aux=inicio; 25       while ((aux!=null) && (!chave.equals(aux.getChave()))) 26          aux=aux.getProx(); 27       if (aux!=null) return aux.getConteudo(); 28       return null; 29    } 30    public boolean remove (String chave) { 31       No aux=inicio; 32       if (aux==null) { 33          //throw EmptyListException(); 34          System.out.println ("Erro: tentou remover de lista vazia"); 35       } else { 36          if (chave.equals(aux.getChave())) { 37             // eh o primeiro que tem que ser removido. 38             inicio=inicio.getProx(); 39             return true; 40          } 41          while ((aux.getProx()!=null) && (!chave.equals(aux.getProx().getChave()))) 42             aux=aux.getProx(); 43          if (aux.getProx()!=null) { 44             aux.setProx(aux.getProx().getProx()); 45             return true; 46          } 47       } 48       return false; 49    } 50    public boolean isEmpty () { 51       return inicio==null; 52    } 53    public void imprime () { 54       No aux=inicio; 55       if (isEmpty()) { 56          System.out.println ("Lista Vazia"); 57       } else { 58          System.out.println ("{"); 59          while (aux!=null) { 60             System.out.println ("    {" + aux.getChave() + "," + aux.getConteudo () + "}"); 61             aux=aux.getProx(); 62          } 63          System.out.println ("}"); 64       } 65    } 66 } 67  68 /* 69 class EmptyListException () { 70 } 71 */

Java2html

Leitura e escrita

A leitura e escrita de arquivos é implementada por classes no pacote Java.io. Com essas classes pode-se usar pipes (são arquivos criados em memória para que processos executados no mesmo computador comuniquem-se - o sistema operacional pode ou não dar suporte a pipes).

Caso o sistema operacional emule arquivos de rede como arquivos locais (por exemplo o compartilhamento de drives do Windows e o Network File System no Linux), esse pacote pode também ser usado, reforçando, porque o sistema operacional apresenta um arquivo remoto como se fosse local.

Há diversos outros pacotes que tratam outros tipos de entrada e saída:

• HTTP o pacote é javax.swing.text.html
• imagens o pacote é javax.imageio.stream
• rede e sockets o pacote é java.nio.channels

A hierarquia de classes de java.io é grande. Uma parte dela é apresentada no diagrama abaixo:

Observe o padrão decorator:

• InputStream é o componente, FileInputStream é a implementação e ObjectInputStream é o decorador;
• Reader é o componente, InputStreamReader é a implementação e BufferedReader é o decorador.

Tarefa:
    Crie um programa que lê um arquivo texto e o imprime na tela.

Exemplo - decorator

código fonte zipado aqui.

01 /** Esta Ã© a classe (abstrata) básica. 02     Escolhi este porque creio ser o caso mais simples. 03 */ 04 interface Basico { 05    /** Nas classes concretas descreve o modelo,  06        nos decoradores acrescenta algo. 07    */ 08    public String getDescription(); 09    /** Nas classes concretas retorna o custo, 10        nos decoradores, inclui o custo da decoração 11       e retorna o custo. 12    */ 13    public double getCost(); 14 }

Java2html

01 /** Primeiro dos dois modelos básicos que pretendo implementar. 02 */ 03 public class Modelo1 implements Basico { 04    /** Nas classes concretas descreve o modelo,  05        nos decoradores acrescenta algo. 06    */ 07    public String getDescription() { 08       return "Carroceria"; 09    } 10    /** Nas classes concretas retorna o custo, 11        nos decoradores, inclui o custo da decoração 12       e retorna o custo. Caso valores precisem ser 13       exatos, sem truncar nem arredondar, Ã© melhor 14       usar int e codificá-los em centavos. 15    */ 16    public double getCost() { 17       return 10000.00; 18    } 19 }

Java2html

01 /** Decorador. 02 */ 03 public class Ar implements Basico { 04    /** Nas classes concretas descreve o modelo,  05        nos decoradores acrescenta algo. 06    */ 07    Basico b; 08    Ar (Basico b) { 09       this.b=b; 10    } 11    public String getDescription() { 12       return b.getDescription() + " Ar-condicionado"; 13    } 14    /** Nas classes concretas retorna o custo, 15        nos decoradores, inclui o custo da decoração 16       e retorna o custo. Caso valores precisem ser 17       exatos, sem truncar nem arredondar, Ã© melhor 18       usar int e codificá-los em centavos. 19    */ 20    public double getCost() { 21       return b.getCost() + 3500.00; 22    } 23 }

Java2html

01 /** Decorador. 02 */ 03 public class Direcao implements Basico { 04    /** Nas classes concretas descreve o modelo,  05        nos decoradores acrescenta algo. 06    */ 07    Basico b; 08    Direcao (Basico b) { 09       this.b=b; 10    } 11    public String getDescription() { 12       return b.getDescription() + " Direção Eletro-assistida"; 13    } 14    /** Nas classes concretas retorna o custo, 15        nos decoradores, inclui o custo da decoração 16       e retorna o custo. Caso valores precisem ser 17       exatos, sem truncar nem arredondar, Ã© melhor 18       usar int e codificá-los em centavos. 19    */ 20    public double getCost() { 21       return b.getCost() + 2000.00; 22    } 23 }

Java2html

01 /** Decorador. 02 */ 03 public class DVDplayer implements Basico { 04    /** Nas classes concretas descreve o modelo,  05        nos decoradores acrescenta algo. 06    */ 07    Basico b; 08    DVDplayer (Basico b) { 09       this.b=b; 10    } 11    public String getDescription() { 12       return b.getDescription() + " DVD player"; 13    } 14    /** Nas classes concretas retorna o custo, 15        nos decoradores, inclui o custo da decoração 16       e retorna o custo. Caso valores precisem ser 17       exatos, sem truncar nem arredondar, Ã© melhor 18       usar int e codificá-los em centavos. 19    */ 20    public double getCost() { 21       return b.getCost() + 800.00; 22    } 23 }

Java2html

01 class TestaDecorador { 02    public static void main (String[] args) { 03       Basico b = new Modelo1(); 04       System.out.println (b.getCost()); 05       Basico c = new Ar(new Modelo1()); 06       System.out.println (c.getDescription()); 07       Basico d = new Direcao(new Ar(new Modelo1())); 08       System.out.println (d.getDescription()); 09    } 10 }

Java2html

Decorator

Decorator é um "padrão de projeto" (design pattern). Não tem nada a ver com uma norma, é uma forma de arranjar classes de forma a obter certa funcionalidade.

Este padrão permite estender (ampliar ou modificar) funcionalidades em tempo de execução. Em comparação com herança, reduz o número de subclasses para implementar as mesmas variações de funcionalidades.

É extensivamente usado no pacote java.io.

Decorator é construído a partir de uma classe (em geral interface ou classe abstrata) que define os métodos que existem tanto nas classes concretas quanto nos decoradores. As classes concretas implementam a funcionalidade básica que ainda não o foram na superclasse. Os decoradores contém (em geral como atributo), instâncias das classes concretas e estendem a funcionalidade invocando os métodos da classe concreta e acrescentando algo quando necessário. A relação básica entre as classes é ilustrada abaixo.

 Exemplos deixarão isto mais claro.

Bancada e fonte de energia

Esta é uma nova linha de trabalho baseada em hardware, arduíno e Linux, começando pela construção da bancada. Já vou avisando desde já que caso você se aventure por aqui, será por sua própria conta e risco - não deve me culpar caso o que você construiu (mesmo seguindo minhas instruções) não serviu para o que você quer, causou ou foi implicado em algum acidente envolvendo você ou terceiros,... enfim, não me responsabilize por danos de qualquer natureza.

...voltando à bancada....

Na minha opinião deve ser firme, suportar um bom peso (o seu, por exemplo), ter o tampo claro (ajuda a achar os componentes menores) e aceitar ser suja, manchada, queimada,... sem que você ou quem quer que seja ressinta-se por isso.

Qualquer mesa que estiver sem uso serve, desde que você tenha os devidos cuidados com cada uma:

1-) mesa de plástico (daquelas de bar) derretem - às vezes precisaremos de ferro de solda, ou simplesmente algo esquenta. Em geral não são muito firmes;
2-) mesa de metal (daquelas de bar) - conduzem eletricidade, sofrem corrosão (talvez usemos percloreto de ferro);
3-) mesa de vidro (geralmente o tampo) - ruim de enxergar o que está em cima, fácil de quebrar com certos impactos;

Pensando nisso, eu escolheria uma de madeira com fórmica branca, mas como você verá, uso uma de plástico. As de metal e vidro eu não usaria, na minha opinião é mais arriscado usá-las.

É bom que o local de trabalho esteja bem iluminado e tenha tomadas por perto.

Protótipos iniciais com arduíno podem aproveitar-se da energia da USB do computador mas se quisermos fazer algo que requeira mais energia (por exemplo use motores) uma boa fonte de alimentação é necessária.

Decidi usar uma fonte de computador pois é barata, fornece várias tensões, fornece muita corrente e tem proteção contra curtos. A que comprei por R$50 em janeiro/2015 tem na etiqueta:

3.3V x 28A
5V x 45A
12V x 18A
5V x 2.5A (pelo pino de stand by)
-12V x 1A

A idéia é fazer algo que funciona, assim, a montagem final ficou:

Eu não quis cortar os fios do conector da fonte (ATX de 20 pinos), então procurei um conector ATX fêmea. Problema: não achei o conector para comprar, assim, recuperei de uma placa-mãe velha que uma alma caridosa vendeu por R$10.

Deu um trabalhão para dessoldar o conector, e outro para montar o circuito pois ligar uma fonte ATX tem lá sua sofisticação. Para os componentes não ficarem "voando", usei uma placa de circuito impresso "padrão" (compra pronta em loja).

Fontes ATX são as que tem circuitos para ligar por soft button e permitem que seu computador fique em estado de suspensão. Para fazer isso, tem uma linha que fornece energia sem interrupção, geralmente codificada VSB (V stand-by) - pino 9 do conector, fio cor roxa. Ela fornece a energia para sustentar o computador em stand-by. Liguei um led nela.

A fonte liga as saídas 3.3V-laranja, 5V-vermelho, 12V-amarelo, -12V azul quando o pino PWR_ON (pino 14 do conector, fio cor verde) for ligado em 0V (qualquer pino COM - fio preto). Liguei um interruptor para fazer isso.

Pela especificação, quando a energia estabiliza nas saídas, o sinal PWR_OK (pino 8 fio cinza) vai de 0 para 5V. (Há considerações sobre fontes de boa ou má qualidade, mas ficarei fora disto). Liguei um led nela.

Pretendo usar mais as linhas de 5 e 12V, que podem ser usadas pelos conectores dos periféricos, apenas a linha de 3,3V está somente no conector da placa mãe.

Nota1: se fosse fazer outra fonte, eu cortaria PWR_ON, VSB, PWR_OK e um fio COM.
Nota2: no pino 11 são ligados dois fios - um é 3,3V, outro é um sensor de 3,3V (mede sobrecarga). Não testei, mas acho que se desconectar a fonte desliga.

informação sobre o padrão ATX e pinagem do conector em http://en.wikipedia.org/wiki/ATX

Exceções - criando a sua própria e "repassando"

01 /** 02    Lancando uma excecao criada por mim mesmo. 03    Aproveitei para mostrar como "repassar a excecao". 04    Ela eh lancada em c(), repassada (por isso o throws) 05    e depois main repassa para a JVM (por isso o throws) 06    Note que se retirar o throws, usando a assinatura como 07    nos comentarios das linhas 13 e 17, ocorre erro de 08    compilacao. 09 */ 10  11 class MinhaExcecao { 12    public static void main (String[] args) throws Exception {    13    //public static void main (String[] args){ 14       MinhaExcecao m=new MinhaExcecao(); 15       m.c(); 16    } 17    //void c() { 18    void c() throws Exception { 19       System.out.println ("lançando"); 20       throw (new ExException()); 21    } 22    // Esta eh otima: Java permite definir classes dentro de classes. 23    // Aqui usei apenas para mostrar que eh possivel. 24    class ExException extends Exception { 25       public String getMessage () {  // Sobrescreve getMessage 26          return toString(); 27       } 28       public String toString (){   // Sobrescreve toString 29          return "ExException Rules!"; 30       } 31    } 32 }

Java2html

Exceções - explicações

Java provê um mecanismo especifico para gerenciar eventos inesperados durante o ciclo de codificação e execução de programas. Neste mecanismo, a ocorrência desses eventos é transmitida através de objetos. A hierarquia de classes é apresentada abaixo:

Os objetos para gerenciar os eventos inesperados são Error e Exception. RunTimeException é subclasse de Exception. Todos são subclasse de Throwable (algo como Lançável). Nesta superclasse está implementada a maioria dos métodos.(https://docs.oracle.com/javase/8/docs/api/java/lang/RuntimeException.html)

As instâncias de Throwable, ou de suas subclasses, são lançadas pelo comando throw. Caso seja necessário marcar que determinado método lança exceções, sua assinatura é seguida pela declaração throws Exception. Exception requer essa marcação, ou seja, se um método lança (throw) uma instância de Exception então ele e todos os métodos que o invocam (numa sequência de chamadas) devem ou ser marcados (com isso eles repassam a exceção para o método que o invocou), ou tratar a exceção. O tratamento de uma exceção consiste em tentar executar o método que lança a exceção (para "tentar", coloca-se a invocação do método dentro de um bloco try), caso alguma exceção seja lançada, capturá-la (com o comando catch), tratá-la (num bloco de comandos associado ao comando catch) e fazer uma "limpeza" com o comando finally.

Exceção - código 9

01 /** Testando... 02 tratamento de exceção com todos os elementos (try catch finally). 03 O que motivou este teste Ã© verificar que elementos são executados mesmo 04 Qual a ordem de execução quando ocorre exceção e finally não tem return? 05 Neste código, o que vem depois do tratamento não Ã© executado por causa 06 do return dentro do try. 07 Este Ã© curioso - quando lança a exceção, executa o catch, antes do return salta para o finally, salta de volta para o finally e executa o return do catch. 08 Quando não lança, executa o finally e continua depois do try... 09  10 Para que serve finally? 11 O bloco finally existe para agregar todas as instruções que "precisam ser executadas para encerrar o método limpamente". Em geral contém comandos que liberam recursos compartilhados, por exemplo, fecham arquivos, pipes, sockets, liberam acesso a variáveis compartilhadas, ...  12  13 um exemplo do que acontece quando isso não Ã© feito direito: 14 Quando estamos editando um arquivo armazenado num pendrive e o editor aborta com o arquivo aberto, em geral não Ã© possível ejetar o pendrive. Explicação: o funcionamento normal do SO não permite ejetar o pendrive enquanto o arquivo estiver em uso - isso evita perda de dados. Quando abrimos o arquivo no editor de texto, este informa ao sistema operacional que o arquivo está em uso. Quando o editor aborta, não informa ao sistema operacional para fechar (e liberar) o arquivo, logo para o SO, o arquivo continua em uso. O que vemos Ã© o editor fechado e o pendrive que não ejeta.  15 */ 16 public class DivZero6 { 17    public static void main (String[] args) { 18       int a, b; 19       a=5; 20       b=0; 21       try { 22          a=a/b; 23          System.out.println ("depois do erro, dentro do try."); 24       } catch (Exception e) { 25          System.out.println ("catch " + e.getMessage()); 26          return; 27       } finally { 28          System.out.println ("finally"); 29       } 30       System.out.println ("continuou...depois do try, fora do catch e do finally"); 31    } 32 }

Java2html

Exceção - código 8

01 /** Testando... 02 tratamento de exceção com todos os elementos (try catch finally). 03 O que motivou este teste Ã© verificar que elementos são executados mesmo 04 Qual a ordem de execução quando ocorre exceção e finally não tem return? 05 Neste código, o que vem depois do tratamento não Ã© executado por causa 06 do return dentro do try. 07 */ 08 public class DivZero5 { 09    public static void main (String[] args) { 10       int a, b; 11       a=5; 12       b=0; 13       try { 14          a=a/b; 15          System.out.println ("depois do erro."); 16          return; 17       } catch (Exception e) { 18          System.out.println ("catch " + e.getMessage()); 19          return; 20       } finally { 21          System.out.println ("finally"); 22       } 23       System.out.println ("continuou..."); 24    } 25 }

Java2html