Programação 2: Diário de Aula 2017-2

Lista de presença

Professor: Marcelo Maia Sobral
Encontros: 5a feira/13:30, 6a feira/15:40
Atendimento paralelo: 6a de 8:30 às 9:30 h / 6a de 13:30 às 14:30 h

Referências complementares

Introdução C++
Modularização em programas C/C++ (arquivos de cabeçalho e implementação
Apostila sobre listas encadeadas (Unicamp)
Estruturas de dados disponíveis dentro do kernel Linux (cap. 6 do livro Linux Kernel Development, 3rd ed., de Robert Love, 2010)
Curso de linguagem C da UFMG
Slides sobre linguagem C do prof. Emerson R. Mello
Guia básico do depurador GDB
Misra-C: diretrizes para uso da linguagem C em sistemas críticos
"Variáveis globais são ruins" ...
- Uma discussão sobre isso em um forum de programadores
Separation of Concerns (Separação de interesses): uma boa introdução sobre decomposição de problemas em partes e modularidade em software.
Dicionário de Algoritmos e Estruturas de Dados
Um interessante texto sobre linguagens de programação
Controle do terminal de texto

Cursos e videos online

Avaliações

As avaliações são de três tipos:

Projetos: feitos em equipes de até dois alunos, são desenvolvidos ao longo da disciplina.
Provas práticas: feitas individualmente, são realizadas em laboratório. Os resultados dessas provas ajustam os conceitos dos projetos (podem confirmá-los, aumentá-los, reduzi-los ou mesmo anulá-los).

Aluno	Projeto 1	Projeto 2	Prova 1
Ameliza	5	7	-2
Ana Paula	8	9	-2
Andre Luiz	0*	0*	anula
Diego	9	10	+2
Felipe	10	10	mantém
Gabriel	9	10	anula
Gustavo	9	10	+2
Guilherme	5	7	-2
João Pedro	0*	0*	anula
Luiza	6	7	mantém
Renan	8	9	+2
Stefanie	5	7	anula
Yara	9	10	+2

Obs:

0* = não fez a avaliação.
(?) = a confirmar
(--) = nota reduzida em 1 ponto por atraso

Softwares

g++: o compilador da linguagem C++ que usaremos
gdb: um debugger para ajudar a encontrar erros em programas
make: um programa para automatizar a compilação de programas
Netbeans IDE (versão C/C++)
- Cópia do instalador no servidor do Ifsc
- OBS: instale o Netbeans executando este comando em um terminal:
```
bash netbeans-8.2-cpp-linux-x64.sh
```
- OBS 2: você precisará ter a máquina virtual Java instalada em seu computador. Você pode obtê-la aqui.
Code::Blocks - outro IDE C/C++

27/07: Apresentação e introdução ao projeto

Introdução C++

Programas precisam armazenar e organizar dados de forma eficiente, o que depende do tipo de problema a ser resolvido, da quantidade de dados a serem manipulados, e da forma com que dados são representados. Para isso existe o conceito de estruturas de dados, que são justamente formas de armazenar e organizar dados. Algumas estruturas de dados corriqueiras são:

Filas
Pilhas
Listas
Tabelas de dispersão (hash)
Árvores

... porém há muitas outras (faça uma pesquisa se ficou curioso).

Em PRG2 serão estudadas as estruturas de dados acima listadas, as quais são de uso comum em programas em geral. O estudo será orientado a pequenos projetos, com a intenção de mostrar possíveis usos dessas estruturas.

Projeto 1: (fila e pilha)
Projeto 2: (lista)
Projeto 3: (árvore)
Projeto 4: (tabela hash)

O estudo dessas estruturas será dividido em duas etapas:

Uso das estruturas de dados: as estruturas de dados são apresentadas, destacando-se suas características, operações e aplicações. Os projetos serão desenvolvidos usando estruturas de dados já existentes.
Implementação das estruturas de dados: As estruturas de dados serão implementadas, de forma a funcionarem como as estruturas usadas na etapa 1. Como resultado, cada equipe terá ao final criado uma biblioteca de programação contendo suas estruturas de dados. Os projetos criados na etapa 1 devem ser compilados e funcionar usando essa biblioteca, sem necessitar qualquer modificação.

Introdução a C++

A linguagem de programação a ser usada se chama C++. Como indica o nome, essa linguagem é uma extensão à linguagem C, de forma a aderir ao paradigma de orientação a objetos. Como esse assunto será visto em profundidade na 4a fase, na disciplina de POO (Programação Orientada a Objetos), faremos um uso mais superficial dessa linguagem. Quer dizer, usaremos algumas de suas construções, mas não nos deteremos em seus aspectos teóricos. O objetivo de usar C++ é introduzir essa linguagem, que será usada em próximas disciplinas.

Uma breve apresentação da linguagem C++

Mas o que tem de especial a linguagem C++ ? Muita coisa, se comparada à linguagem C. Veja este exemplo sobre string em ambas linguagens:

Linguagem C

Linguagem C++

#include <stdio.h>
#include <string.h>

int main() {
  char nome[32], sobrenome[32];
  char nomeCompleto[64];

  printf("Nome: ");
  scanf("%32s", nome);
  printf("Sobrenome: ");
  scanf("%32s", sobrenome);
  
  strcpy(nomeCompleto, nome);
  strcat(nomeCompleto, " ");
  strcat(nomeCompleto, sobrenome);

  printf("Nome completo: %s\n", nomeCompleto);

  return 0;
}

#include <iostream>
#include <string>

using namespace std;

int main() {
  string nome, sobrenome, nomeCompleto;

  cout << "Nome: ";
  cin >> nome;
  cout << "Sobrenome: ";
  cin >> sobrenome;

  nomeCompleto = nome + " " + sobrenome;

  cout << "Nome completo: " << nomeCompleto << endl;
}

Obs: para compilar o programa C++, grave-o em um arquivo com extensão .cpp ou .cc e compile-o assim (supondo que o arquivo se chame main.cpp):

g++ -std=c++11 -o exemplo main.cpp

Esse exemplo mostra algumas diferenças entre as linguagens:

strings em C++ são representadas por variáveis do tipo string. Valores string podem ser concatenados com o operador +.
A leitura de dados do console (entrada padrão) se faz por meio da variável predefinida cin (console input). Essa variável cin funciona como um arquivo somente leitura, e é similar a stdin da biblioteca C padrão. No exemplo, a leitura formatada se faz por meio do operador >> (operador leitura). Outras formas de ler dados serão vistas mais adiante na disciplina.
A escrita de dados no console (saída padrão) se faz por meio da variável predefinida cout (console output). Essa variável também funciona como um arquivo, porém somente escrita, e é similar a stdout da biblioteca C padrão. A escrita formatada de dados se faz por meio do operador << (operador escrita). Outras formas de escrever dados serão vistas mais adiante.

Esses e outros detalhes diferem entre as linguagens C e C++, mas a principal diferença entre elas reside no paradigma de programação com que foram concebidas. A linguagem C segue o paradigma de programação estruturada, e C++ segue o paradigma de orientação a objetos. Em C++, um programa é pensado como um conjunto de objetos que se relacionam com o objetivo de apresentar a solução imaginada.

Mais sobre objetos

Para ter um primeiro contato com classes e objetos, vamos criar alguns pequenos programas.

Um exemplo com números complexos

Números complexos são compostos por uma parte real e outra imaginária. Eles possuem grande aplicação na Física e Engenharias, incluindo em Telecomunicações (como vocês verão). No entanto, as linguagens de programação não costumam definir um tipo de dados para números complexos (Python é uma exceção !).

O primeiro exemplo sobre classes e objetos visa criar números complexos. Para o propósito do exemplo, um número complexo tem partes real e imaginária do tipo double, e apresenta operações para calcular o módulo e ângulo para forma polar.

Linguagem C

Linguagem C++

#include <math.h>

struct Complexo {
  double r, i;
};

double modulo(struct Complexo * z) {
  return sqrt(z->r*z->r + z->i*z->i);
}

double angulo(struct Complexo * z) {
  return atan(z->i / z->r);
}

#include <math.h>

class Complexo {
 // os atributos de um número complexo: suas partes real e imaginária
 private:
  double r, i; // partes real e imaginária

 public:
  // construtor: método para criação de um número complexo
  Complexo(double rr, double ii) {
    r = rr;
    i = ii;
  }

  // métodos para obter cópias dos valores dos atributos do número complexo
  double real() const { return r;}
  double imaginario() const { return i;}

  // métodos para obter módulo e ângulo da forma polar
  double modulo() const {
    return sqrt(r*r + i*i);
  }

  double angulo() const {
    return atan(i/r);
  }
};

Uma vez tendo declarado a classe Complexo, podem-se criar objetos dessa classe e usá-los em programas:

Linguagem C

Linguagem C++

#include <stdio.h>
#include "complexo.h"

int main() {
  struct Complexo z = {1, 1};

  printf("Parte real: %lg\n", z.r);
  printf("Parte imaginaria: %lg\n", z.i);
  printf("Forma polar: modulo=%lg, angulo=%lg\n", modulo(&z), angulo(&z));
}

#include <iostream>
#include "complexo.h"

using namespace std;

int main() {
  Complexo z(1,1); // "z" é um objeto da classe Complexo

  cout << "Parte real: " << z.real() << endl;
  cout << "Parte imaginaria: " << z.imaginario() << endl;
  cout << "Forma polar: modulo=" << z.modulo();
  cout << ", angulo=" << z.angulo() << endl;
}

Compile os exemplos e execute-os para vê-los em funcionamento. Em seguida, experimente fazer pequenas modificações na versão em C++. Por exemplo, tente acessar diretamente os atributos do objeto z (tente acessar z.r ou z.i).

O exemplo é muito simples, e pode-se questionar o que se ganha escrevendo-o usando classe e objetos. Essa questão poderá ser retomada quando os programas forem um pouco maiores ou mais complexos ... O próximo exemplo também é simples, mas possui alguns requisitos a mais. Afinal, ele faz alguma coisa aparentemente útil ;-)

Uso do NetBeans

Na disciplina recomenda-se usar o ambiente integrado de desenvolvimento (IDE - Integrated Development Environment) NetBeans. Esse software auxilia na escrita de programas, pois integra um editor de texto, um gerenciador de projetos, compilador e depurador, além de ajuda on-line e outras facilidades. Os exemplos durante a disciplina serão disponibilizados como projetos do NetBeans, mas não é obrigado utilizá-lo - pode-se trabalhar diretamente com um editor de textos (ex: gedit) e o compilador C++ (g++) e depurador (gdb), porém isso é um pouco mais trabalhoso ...

Para instalar o NetBeans siga estes passos:

Certifique-se de que possui a máquina virtual Java instalada. Execute este comando em um terminal:

$ java -version
java version "1.8.0_121"
Java(TM) SE Runtime Environment (build 1.8.0_121-b16)
Java HotSpot(TM) 64-Bit Server VM (build 25.51-b03, mixed mode)
$

Se não tiver o Java instalado, faça o seguinte:
- Faça o download do instalador, escolhendo a versão adequada para o seu Linux (deve ser um arquivo .tar.gz para a versão do seu sistema operacional, se 32 ou 64 bits).
- Descompacte o arquivo do instalador dentro do seu diretório pessoal. Note que deve aparecer uma pasta chamada jre1.8.0.121 ou algo parecido).
- Inclua esta linha ao arquivo .profile que existe em sua pasta pessoal, substituindo a versão do Java se necessário (use um editor de texto, como o gedit):
```
export PATH=${PATH}:${HOME}/jre1.8.0.121/bin
```
- Saia da sua conta (encerre a sessão), e em seguida entre novamente.
Faça o download do instalador do Netbeans:
- Instalador do Netbeans 8.2 no servidor de Tele
- Instalador do Netbeans 8.2 no site oficial
Execute o instalador em um terminal de texto. Supondo que o download foi realizado na pasta Download:
```
$ bash Download/netbeans-8.2-cpp-linux-x64.sh
```
Siga as instruções de instalação.

Exercícios

Resolva os três primeiros exercícios existentes na página da disciplina do Moodle.

OBS: para se inscrever no Moodle, faça o login com seu usuário e senha do Portal do Aluno. Em seguida, solicite a autoinscrição, fornecendo a chave de inscrição mr.robot quando pedida.

O que foi usado da C e C++ para resolver os exercícios:

classe string, e seus métodos:
- size para saber seu comprimento
- [/ operador []] para acessar um caractere de uma certa posição.
- front: para acessar o primeiro caractere
- back: para acessar o último caractere
- pop_back: para remover o último caractere
- erase: para remover caracteres a partir de uma certa posição
função toupper (para converter caractere para maiúsculo)
argumentos de linha de comando: parâmetros argc e argv da função main

28/07: Introdução a C++

Introdução a C++

Hoje continua-se a introdução a linguagem C++ de forma a explorar classes e objetos.

Jogo da Forca

Jogo da Forca (wikipedia)

O jogo da Forca é um jogo em que se tenta adivinhar uma palavra letra a letra. Um jogador escolhe uma palavra, e informa quantas letras ela possui. Outro jogador tenta descobrir a palavra, informando sucessivamente letras que imagina pertencer à palavra. Cada letra que não exista na palavra implica uma penalidade, acrescentando uma parte do corpo à forca, como ilustrado na figura a seguir. Se o corpo na forca ficar completo, o desafiador perde a partida.

Esse jogo pode ser facilmente implementado como um programa. Basicamente ele trata de manipulação de string e caracteres.

O jogo da Forca em linguagem C++

Introdução a string em C++

A tarefa desta aula anterior envolve implementar o jogo da Forca em linguagem C++. A versão em C++ pode explorar os recursos dessa linguagem, tais como classes e objetos (principalmente string). Um bom ponto de partida é primeiro definir um protótipo que seja o mais simples posśivel, porém que contenha as características essenciais do jogo.

#include <iostream>
#include <string>

using namespace std;

int main() {
    string palavra = "abacaxi"; // a palavra a ser descoberta
    string incompleta = "_______"; // a parte da palavra que já está revelada
    int tentativas = 7; // a quantidade de erros que podem ser cometidos

    // abaixo deve-se escrever o algoritmo do jogo ...
}

Um início de implementação do jogo da Forca em C++

Uma solução para o jogo da Forca

TAREFA para dia 03/08

Implemente o jogo da Forca em linguagem C++. Sua implementação pode ser testada nesta atividade no Moodle.

03/08: Introdução a C++: exercícios

Introdução a C++

Continuação dos exercícios da aula anterior. E mais alguns ... ver no Moodle.

04/08: Projeto 1: um enumerador de arquivos

Os discos de um computador contêm usualmente milhares de arquivos, contando arquivos de sistema e de usuários. Por exemplo, o diretório pessoal do professor em seu computador no IFSC têm pouco mais de 254 mil arquivos, e o seu computador como um todo possui 636274 arquivos. Essa grande quantidade de arquivos está distribuída em muitos subdiretórios (??? no caso do computador pessoal do professor). A listagem ou enumeração de arquivos a partir de um dado subdiretório pode ser útil em algumas situações, tais como backups e buscas de arquivos, e para isso tornam-se necessários programas utilitários especializados.

O projeto 1 tem como objetivo a criação de um programa enumerador de arquivos. Esse programa deve listar os arquivos abaixo de um dado subdiretório de acordo com alguns critérios:

extensão (ex: pdf, doc, txt, html, ...)
tipo (arquivo regular, programa, diretório, link simbólico, ...)

A listagem deve ser feita a partir de um subdiretório, sendo realizada de forma recursiva. Isso significa que a busca deve ser feita também dentro dos subdiretórios ali contidos, independente da quantidade de resultados.

O enumerador de arquivos deve ser implementado usando a classe Diretorio. Objetos dessa classe possibilitam listar diretórios, obtendo descrições dos arquivos e subdiretórios ali contidos. A declaração dessa classe pode ser vista a seguir:

A classe Diretório

#ifndef DIRETORIO_H
#define	DIRETORIO_H

#include <sys/types.h>
#include <dirent.h>

#include "tipos.h"


// classe que representa diretórios
class Diretorio {
public:
    // construtores
    
    // cria um diretório associado ao diretório atual
    Diretorio();
    
    // cria um diretório com caminho "pathname". Se caminho
    // não existir, ou não puder ser acessado, dispara uma
    // exceção de valor inteiro
    Diretorio(const string & pathname);
    
    // cria um diretório com caminho "pathname". Se caminho
    // não existir ou não puder ser acessado, e block for false, 
    // dispara uma exceção de valor inteiro.
    // se block for true, tenta criar o diretório (se não
    // conseguir, dispara a exceção)
    Diretorio(const string & pathname, bool criar);
    Diretorio(const Diretorio& orig);
    
    // destrutor
    virtual ~Diretorio();
    
    // operador de atribuição
    Diretorio& operator=(const Diretorio & orig);
    
    // muda de diretório
    void muda(const string & pathname);
    
    // retorna a quantidade de entradas neste diretório
    unsigned int entradas() const;
    
    // retorna o caminho deste diretório
    string caminho() const { return path;}
    
    // retorna o caminho absoluto deste diretório
    string caminho_absoluto() const;

    // métodos para listar um diretório
    // inicia a listagem: deve ser invocado em primeiro lugar
    // se diretório não existir, ou não puder ser acessado,
    // dispara uma exceção de valor inteiro    
    void inicia_listagem();
    
    // obtém próxima entrada de diretório
    // se não houver iniciado a listagem, ou listagem 
    // chegou ao fim, dispara uma exceção de valor inteiro
    Entrada proximo();
    
    // testa se listagem chegou ao fim
    bool fim_listagem() const;
        
private:
    // atributos da classe: cada objeto desta classe
    // possui estes três atributos
    string path;
    DIR * dir;
    dirent * dent;
};

arquivo Diretorio.h

A estrutura do enumerador pode ser visualizada nesta figura. Ela mostra que o programa pode ser entendido como uma composição de quatro partes (ou módulos). Cada módulo é responsável por uma funcionalidade específica, e isso foi pensado para simplificar a resolução do projeto. Os módulos Diretorio e Prglib já foram fornecidos. O primeiro fornece a classe Diretorio, necessária para listar e navegar por diretórios. A segunda oferece uma implementação de algumas estruturas de dados que podem ser úteis na solução.

Os arquivos contendo as declarações e implementações desses módulos, incluindo exemplos de como utilizá-los, estão disponíveis em um arquivo de projeto Netbeans:

Arquivo de projeto Netbeans para o Enumerador

Pode-se importar esse arquivo de projeto no Netbeans por meio do ítem de menu Arqivo->Importar. De forma alternativa, podem-se compilá-los diretamente na linha de comando:

Descompacte o arquivo de projeto
Entre no diretório do projeto. Ex:
```
cd Enumerador
```
Compile o programa exemplo:
```
make
```
Execute o programa exemplo, que está em dist/Debug/GNU-Linux/. Ex:
```
dist/Debug/GNU-Linux/enumerador
```

O início do projeto 1 começa com uma demonstração dos módulos que já estão prontos.

Atividade

Use a classe Diretorio para listar um diretório qualquer. Mostre os nomes dos arquivos e subdiretórios ali existentes.
Modifique o programa anterior para listar cada um dos subdiretórios encontrados.
Modifique o programa para identificar os arquivos que possuem um determinado nome.
Modifique o programa para identificar os arquivos que possuem uma determinada extensão.

A localização de arquivos e subdiretórios

A enumeração de arquivos implica percorrer todos os subdiretórios abaixo do diretório inicial. Os subdiretórios se relacionam em uma estrutura chamada árvore, como mostrado na figura a seguir. A busca por arquivos em um subdiretório deve ser feita por algum algoritmo que consiga visitar cada subdiretório e conferir se ali tem o arquivo procurado. Essa busca pode ser feita um nível por vez (busca em largura), ou visistando uma ramificação por completo a cada vez (busca em profundidade). Por exemplo, na figura a seguir, a busca em largura a partir do subdiretório /home implica visitar esses subdiretórios: /home, /home/jane, /home/will, /home/zeb, /home/will/work, /home/will/play. A busca em profundidade seguiria esta ordem: /home, /home/jane, /home/will, /home/will/work, /home/will/play, /home/zeb.

Sendo assim:

Como se poderia implementar um algoritmo de busca em largura ?
Como se poderia implementar um algoritmo de busca em profundidade ?

10 e 11/08: Projeto 1: uso de filas e pilhas para percorrer os diretórios

A busca de arquivos pelos subdiretórios pode ser feita usando algoritmos de busca em profundidade e busca em largura. O primeiro tipo pode ser implementado usando uma fila, e o segundo usando uma pilha. A aula de hoje introduz essas estruturas de dados.

Filas

Uma aplicação de filas em roteadores

De forma geral, uma fila é uma estrutura de dados que funciona como mostrado na figura abaixo:

A declaração da Fila na biblioteca Prglib é esta:

template <typename T> class fila : public std::queue<T> {
public:
    fila(unsigned int N);
    fila(const fila<T>& orig);
    virtual ~fila();
    fila<T>& operator=(const fila<T> & outra);
    void enfileira(const T & algo);
    T desenfileira();
    const T & frente() const;
    bool vazia() const;
    bool cheia() const;
    unsigned int comprimento() const;
    unsigned int capacidade() const;
private:
    unsigned int N;
};

Arquivo libs/fila.h

... e um exemplo de uso é mostrado a seguir:

#include <iostream>
#include <string>
#include "prglib.h"

using namespace std;

int main() {
  // uma fila com capacidade de armazenar 20 inteiros
  prglib::fila<int> numeros(20);

  // uma fila com capacidade de armazenar 20 string
  prglib::fila<string> coisas(20);

  numeros.enfileira(6);
  numeros.enfileira(8);
  numeros.enfileira(10);
  numeros.enfileira(12);

  coisas.enfileira("banana");
  coisas.enfileira("graviola");
  coisas.enfileira("sapoti");
  coisas.enfileira("siriguela");
  coisas.enfileira("caju");

  cout << "Fila de numeros tem comprimento=" << numeros.comprimento() << endl;
  cout << "Fila de string tem comprimento=" << coisas.comprimento() << endl;

  while (not numeros.vazia()) {
    cout << "Numero: " << numeros.desenfileira() << endl;
  }

  while (not coisas.vazia()) {
    cout << "String: " << coisas.desenfileira() << endl;
  }
}

Exercícios

Resolva os seguintes exercícios sobre filas:

Pilhas

Pilhas são estruturas do tipo LIFO (Last In First Out - último a entrar, primeiro a sair). Apenas duas operações são possíveis de modificar pilhas:

* Push: empilha um novo dado (acrescenta-o ao topo da pilha).
* Pop: desempilha um dado (retira-o do topo da pilha)
*Top: acessa o dado do topo da pilha

A declaração da Pilha na biblioteca Prglib é esta:

template <typename T> class pilha : public std::stack<T> {
 public:
  // construtor: deve-se informar a capacidade da pilha
  pilha(unsigned int umaCapacidade);
 
  // construtor de cópia: cria uma pilha que é cópia de outra
  pilha(const pilha<T>& outra);
 
  // destrutor da pilha
  ~pilha();
 
  // operador de atribuição: torna esta pilha uma cópia de outra pilha
  pilha<T> & operator=(const pilha<T> & outra);
 
  // operações da pilha
 
  virtual void push(const T & dado); // empilha um dado
 
  T pop(); // desempilha um dado
 
  virtual const T& top() const; // retorna o dado do topo da pilha, sem retirá-lo
 
  bool vazia() const;
  bool cheia() const;
  unsigned int comprimento() const;
  void esvazia();
  unsigned int capacidade() const;
  
 private:
  unsigned int N;
};

Arquivo libs/pilha.h

... e um exemplo de uso é mostrado a seguir:

#include <iostream>
#include <string>
#include "prglib.h"

using namespace std;

int main() {
  // uma pilha com capacidade de armazenar 20 inteiros
  prglib::pilha<int> numeros(20);

  numeros.push(6);
  numeros.push(8);
  numeros.push(10);
  numeros.push(12);

  cout << "Pilha de numeros tem comprimento=" << numeros.comprimento() << endl;

  while (not numeros.vazia()) {
    cout << "Topo da pilha: " << numeros.top() << endl;
    cout << "... desempilhou: " << numeros.pop() << endl;
  }

}

Atividade

Resolva os exercícios sobre uso de pilhas e filas que estão no tópico Etapa 1 no Moodle.

Dica para o exercício sobre linhas de um arquivo

#include <fstream>
#include <string>

using namespace std;

int main(int argc, char * argv[]) {
    // abre o arquivo cujo nome é dado por argv[1]
    ifstream arq(argv[1]);
    
    // se arquivo não foi aberto (algum erro ?)
    // mostra um alerta e termina o programa
    if (not arq.is_open()) {
        cout << "arquivo invalido" << endl;
        return 0;
    }
    
    // Este laço lê todas as linhas do arquivo
    // Cada repetição do laço  corresponde a uma nova linha lida
    string linha;
    while (getline(arq, linha)) {
        // faz algo com a linha
    }
    
    return 0;
}

17/08: Projeto 1: Algoritmos de busca do localizador

Na aula anterior se apresentaram os algoritmos de busca em largura e de busca em profundidade. O localizador deve ser implementado usando ambos algoritmos, para investigar se existe diferença em seus desempenhos (ex: o tempo total de busca).

Algoritmo para busca em largura

parâmetros de entrada: 
  caminho: caminho do subdiretório onde se inicia a busca
  nome: nome ou parte do nome a serem procurados
resultado:
  conjunto de arquivos ou subdiretório que satisfazem o critério de busca
Início:
  Cria uma fila "q" capaz de armazenar string
  enfileira "caminho" em "q"
  enquanto fila "q" não estiver vazia faça
    desenfileira um caminho de "q"
    para cada entrada existente no caminho desenfileirado faça
      se entrada for um subdiretório, enfileire-o em "q"
      se entrada contiver "nome", acrescente-a ao resultado
    fimPara
  fimEnquanto
  devolva o resultado contendo as entradas que satisfizeram o critério de busca
Fim

Algoritmo para busca em profundidade

parâmetros de entrada: 
  caminho: caminho do subdiretório onde se inicia a busca
  nome: nome ou parte do nome a serem procurados
resultado:
  conjunto de arquivos ou subdiretório que satisfazem o critério de busca
Início:
  Cria uma pilha "p" capaz de armazenar string
  empilha "caminho" em "p"
  enquanto pilha "p" não estiver vazia faça
    desempilhe um caminho de "p"
    para cada entrada existente no caminho desempilhado faça
      se entrada for um subdiretório, empilhe-a em "p"
      se entrada contiver "nome", acrescente-a ao resultado
    fimPara
  fimEnquanto
  devolva o resultado contendo as entradas que satisfizeram o critério de busca
Fim

Atividade

Implemente os algoritmos de busca em largura e em profundidade
Compare os tempos de execução de suas implementações desses algoritmos. DICA: execute seu programa com o utilitário time. Ex (se estiver usando o Netbeans):
```
time dist/Debug/GNU-Linux/enumerador
```

18/08: Projeto 1: conclusão

A aula de hoje está à disposição para esclarecimento de dúvidas sobre o projeto 1.

Exemplo de uso de argumentos de linha de comando

#include <iostream>

using namespace std;

int main(int argc, char * argv[]) {
  cout << "Quantidade de argumentos: " << argc << endl;

  for (int i=0; i < argc; i++) {
    cout << "argv[" << i << "]=" << argv[i] << endl;
  }

  return 0;
}

Processamento dos argumentos de linha de comando

O processamento dos argumentos de linha de comando precisou ser implementado por cada equipe. Deve ter ficado evidente que esse tipo de processamento pode ser necessário em diferentes programas, e que boa parte dele pode ser generalizada. De fato existem bibliotecas que oferecem recursos para realizar o processamento dos argumentos:

getopt: função da biblioteca C padrão
Biblioteca Program_options: biblioteca composta por classes e funções (parte da suite C++ boost)
- Um tutorial sobre como usar o processamento de argumentos com a biblioteca boost
- Uma comparação entre getopt e boost (com exemplos)

Ambas opções acima são bastante utilizadas e completas. No entanto, por se pretenderem genéricas, apresentam alguns detalhes a serem bem compreendidos para que possam ser utilizadas (veja os manuais). Uma alternativa é esta pequena classe que processa os argumentos de forma simplificada:

Argparse

A classe Argparse é capaz de processar argumentos com opções curtas e longas, com ou sem valores complementares. Algumas definições podem esclarecer isso:

Opção curta: informada com uma única letra e precedida por um hífen. Ex: -f
Opção longa: informada com duas ou mais letras e precedida por dois hífens. Ex: --tipo
Opção com valor complementar: a opção pede um valor. Ex: -p /home, --tipo arquivo
Opção sem valor complementar: nenhum valor deve ser acrescentado à opção. Ex: -b, --path.

Valores complementares de opções são sempre do tipo string. Opções sem valor complementar, chamadas de flag, possuem valor bool (true se opção aparece na linha de comando, false caso contrário).

A classe Argparse possui esta interface:

class Argparse {
public:
    Argparse();
    Argparse(const Argparse& orig);
    virtual ~Argparse();

    // Métodos para adicionar uma opção do tipo flag. Tal tipo de opção
    // não requer um valor a ser informado na linha de comando.
    // Ela é do tipo bool: se aparece na linha de comando seu valor é true,    
    // e, caso não apareça, seu valor é false.
    void add_flag(char shortoption);
    void add_flag(const string & longoption);
    
    // Métodos para adicionar uma opção do tipo flag com um valor
    // predefinido
    void add_flag(char shortoption, bool defval);
    void add_flag(const string & longoption, bool defval);
    
    
    // Métodos para adicionar uma opção comum. Tal tipo de opção
    // requer um valor a ser informado na linha de comando.
    // Ela é do tipo string: se aparece na linha de comando, a string que a sucede
    // se torna seu valor. Caso essa opção não apareça, seu valor é uma string vazia.
    void add_option(char shortoption);
    void add_option(const string & longoption);
    
    // Métodos para adicionar uma opção comum com um valor
    // predefinido    
    void add_option(char shortoption, const string & defval);
    void add_option(const string & longoption, const string & defval);
    
    // Métodos para obter o valor de uma opção comum
    string get_option(char shortoption) const;
    string get_option(const string & longoption) const;
    string operator[](const string & longoption) const;
    string operator[](char shortoption) const;

    // Métodos para obter o valor de uma opção do tipo flag
    bool get_flag(char shortoption) const ;
    bool get_flag(const string & longoption) const;
    
    // Método para obter os argumentos que não foram processados como
    // opções.
    string get_extra() const { return extra;}
    
    // Método para analisar os argumentos de linha de comando e extrair
    // as opções e seus valores contidos nesses argumentos. O vetor argv
    // corresponde ao parâmetro argv da função main. A análise das opções
    // é efetuada a partir da segunda posição do vetor (argv[1]).
    int parse(char * argv[]);
};

O programa a seguir ilustra o uso de Argparse, supondo um programa que tenhas as opções sem valor complementar -L, -P, e as opções com valor complementar -e, -p, --type.

#include <cstdlib>
#include <iostream>
#include "Argparse.h"

using namespace std;

/*
 * 
 */
int main(int argc, char** argv) {
    Argparse args;
      
    /* Demonstração do analisador de argumentos de linha de comando
     
     As opções contidas nessa demonstração são:
     
     -e EXTENSÃO 
     --type TIPO
     -p CAMINHO
     -L
     -P
     * 
     * Assim, o programa pode ser executado com qualquer combinação dessas opções,
     * as quais podem aparecer em qualquer ordem na linha de comando.
     */

    args.add_option('e');
    args.add_flag('L');
    args.add_flag('P', true);
    args.add_option('p');
    args.add_option("type", "file");
    
    int n = args.parse(argv);
    
    cout << "Identificou " << n << " opções" << endl;

    cout << "ext=" << args['e'] << endl;
    cout << "alg: largura=" << args.get_flag('L');
    cout << ", profundidade=" << args.get_flag('P') << endl;    
    cout << "path=" << args['p'] << endl;
    cout << "tipo=" << args["type"] << endl;
    cout << "extra=" << args.get_extra() << endl;
          
    return 0;
}

Entrega do projeto

Prazo de entrega: 27/08/2017, 23:59 h
Entrega feita no Moodle
Pode ser feito por equipes de no máximo 03 alunos (ideal ser feito em dupla)
Os critérios de avaliação podem ser visto na descrição da tarefa no Moodle

24/08: Projeto 2: um programa para acessar dados de IDH

O Índice de Desenvolvimento Humano (IDH) é um indicador desenvolvido pela ONU para identificar condições de vida, bem-estar e desenvolvimento humano em países e suas regiões. Isso possibilita enumerar os países de acordo com esse índice, como pode ser visto aqui:

Lista de países por IDH

No caso do Brasil existe o IDHM, que adapta a metodologia de cálculo do IDH para os municípios. Os indicadores são:

IDHM: IDH do município
IDHM_E: IDH do município para educação
IDHM_L: IDH do município para longevidade
IDHM_R: IDH do município para renda

O projeto 2 propõe criar um programa que faça buscas de dados em uma tabela de IDHM. Essas buscas podem considerar diferentes dimensões, tais como ano de cálculo do IDHM, o IDHM em si ou seus subíndices, e inclusive a melhorias nesses índices ao longo do tempo. O programa deve usar como fonte de dados este arquivo CSV, que contém uma tabela de IDHM:

Tabela de IDHM (compactado com bzip2)

Nesse arquivo, cada linha corresponde aos dados de um município separados por vírgulas. As colunas representam, nesta ordem: ANO,UF,Codmun6,Codmun7,Município,IDHM,IDHM_E,IDHM_L,IDHM_R. Um exemplo de uma linha do arquivo é apresentada a seguir:

1991,11,110001,1100015,ALTA FLORESTA D'OESTE,0.329,0.112,0.617,0.516

As buscas no arquivo envolvem trabalhar com conjuntos de dados, os quais devem poder ser acessados de forma arbitrária. Assim, filas e pilhas não servem para armazená-los no programa. Uma nova estrutura de dados se faz necessária para tornar mais fácil essa tarefa. Mas antes de estudá-la, deve-se entender como os dados do arquivo CSV podem ser lidos.

Atividade

Arquivo de projeto do Netbeans para projeto 2

Modele a representação em software de cada registro do arquivo de IDHM. Um registro corresponde aos dados de um município contidos em uma linha. A representação em software pode ser um tipo de dados ou uma classe. Ex:

struct IDHM {
  string municipio;
  int ano;
  int uf;
  float idhm;
  float idhm_e;
  float idhm_l;
  float idhm_r;
};

... ou:

struct IDHM {
  string municipio;
  int ano;
  int uf;
  float idhm;
  float idhm_e;
  float idhm_l;
  float idhm_r;

  // construtor sem parâmetros: não inicializa os campos
  IDHM() {
    // aqui nada precisa ser feito ... fica assim vazio mesmo
  }

  // construtor que inicializa os campos com os valores contidos na linha do tipo CSV
  IDHM(const string & linha) {
    // aqui deve-se implementar o processamento da linha,
    // para extrair os valores nela contidos, convertê-los e copiá-los
    // para os campos correspondentes desta struct
  }
};

Escreva um programa capaz de ler as linhas do arquivo de IDHM e as transforme em valores do tipo de dados ou objetos da classe criados no ítem 1. Dica: você pode usar a função separa desenvolvida como exercício no Moodle.

25/08: Projeto 2: introdução a listas

Um video introdutório da Khan Academy

Uma lista encadeada é uma estrutura de dados em que os dados são armazenados dinamicamente em memória, de forma a se organizarem em uma sequência. Cada dado é armazenado em um elemento da lista denominado nodo, que funciona como uma caixa onde se guarda esse dado. Assim, para cada dado armazenado na lista existe um nodo. Cada nodo possui uma referência ao próximo nodo da lista, formando uma sequência parecida com os vagões de um trem. A figura abaixo ilustra uma lista encadeada:

Uma lista possui algumas características:

Os nodos são criados dinamicamente, à medida que for necessário. Assim, a quantidade total de memória usada para a lista depende da quantidade de dados nela armazenados (compare isso com um vetor ou matriz).
A lista não precisa ocupar uma área de memória contígua: como nodos são alocados dinamicamente, eles podem ocupar áreas de memória arbitrárias, e não há nenhuma relação entre a localização dos nodos em memória e sua ordem na lista (novamente compare isso com um vetor ou matriz).
Não é possível indexar os nodos, por isso para acessar um nodo deve-se obrigatoriamente procurá-lo a partir do início ou fim da lista, seguindo cada nodo até chegar àquele procurado.
Para adicionar um nodo, basta modificar a referência do nodo que o antecede na lista. Assim, não é necessário "empurrar" os nodos seguintes para frente (como seria o caso de um vetor).
Para remover um nodo é a mesma coisa: basta modificar a referência de seu nodo antecessor. Assim, não é necessário "deslocar pra trás" os nodos seguintes (como seria o caso de um vetor).

As operações elementares de uma lista definem como dados podem ser adicionados, obtidos e removidos da lista, e também que informações sobre a lista podem ser obtidas. São elas:

anexa: adiciona um dado ao final da lista
insere: adiciona um dado em uma determinada posição da lista
remove: remove um dado de uma determinada posição da lista
obtem: obtém um dado de uma determinada posição da lista
comprimento: obtém o comprimento da lista
esvazia: esvazia a lista (remove todos os dados)

A biblioteca Prglib possui uma lista,cuja declaração é apresentada a seguir:

A lista encadeada da biblioteca Prglib

/* 
 * File:   lista.h
 * Author: msobral
 *
 * Created on 11 de Agosto de 2016, 08:56
 */

#ifndef LISTA2_H
#define	LISTA2_H

#include <cstddef>
#include <ostream>
#include <string>
#include <list>
#include <algorithm>
#include <random>
#include <memory>

using std::shared_ptr;

namespace prglib {

template <typename T> class lista {
    
 public:
  //construtor: não precisa de parâmetros para criar uma nova lista
  lista();
  
  // construtor de cópia
  lista(const lista &outra);
  
  // destrutor
  virtual ~lista();
  
  // insere "algo" no inicio da lista
  void insere(const T & algo);

  // adiciona "algo" no final da lista
  void anexa(const T & algo);
  
  // insere "algo" em uma posição específica da lista  
  void insere(const T & algo, int posicao);
  void insereOrdenado(const T & algo);
  
  // remove o dado que está na "posicao" na lista, e retorna 
  // uma cópia desse dado
  virtual T remove(int posicao);
  
  // remove todos os dados que forem equivalentes a "algo"
  void retira(const T & algo);
  
  // estas duas operações são idênticas: retorna
  // uma referência ao dado que está na "posicao" na lista
  T& obtem(int posicao) const;
  T& operator[](int pos) const;
 
  // atribuição: torna esta lista idêntica à outra lista
  virtual lista& operator=(const lista<T> & outra);
  
  // compara duas listas: são iguais se tiverem mesmo comprimento
  // E todos os dados armazenados forem iguais e na mesma ordem
  bool operator==(const lista<T> & outra) const;
  
  // Retorna uma referência a um dado que seja equivalente a "algo"
  T& procura(const T &algo) const; 

  // Procura todos os dados equivalentes a "algo", e os
  // anexa a "lista". Retorna uma referência a "lista".
  shared_ptr<lista<T>> procuraMuitos(const T &algo) const;
  lista<T> & procuraMuitos(const T &algo, lista<T> & lista) const;

  // retorna a quantidade de dados armazenados na lista
  int comprimento() const;
  
  // retorna true se lista estiver vazia
  bool vazia() const;
  
  // Esvazia a lista
  void esvazia();

  // apresenta o conteúdo da lista no stream "out"
  void escrevaSe(std::ostream & out) const;
  void escrevaSe(std::ostream & out, const std::string & delim) const;
  
  // ordena a lista
  void ordena();
  
  // iteração do início pro fim
  void inicia();
  T & proximo();
  bool fim() const;

  // ... e do fim pro início
  void iniciaPeloFim();
  T & anterior();
  bool inicio() const;
  
  // inverte a ordem nos nodos na lista
  void inverte();
  
  // embaralha os dados de uma lista
  void embaralha();
  
  // obtém uma sublista
  lista<T> * sublista(unsigned int pos1, unsigned int pos2) const;
  lista<T> & sublista(unsigned int pos1, unsigned int pos2, lista<T> & outra) const;
};

Abaixo segue um exemplo de uso de algumas operações de uma lista:

/*
 * To change this license header, choose License Headers in Project Properties.
 * To change this template file, choose Tools | Templates
 * and open the template in the editor.
 */

/* 
 * File:   main.cpp
 * Author: msobral
 *
 * Created on 20 de Fevereiro de 2017, 17:32
 */

#include <cstdlib>
#include <prglib.h>
#include <iostream>
#include <string>

using namespace std;
using prglib::lista;

int main(int argc, char** argv) {
    // cria uma lista de string
    lista<string> nomes;
    
    // anexa três dados ao final da lista
    nomes.anexa("manuel");
    nomes.anexa("maria");
    nomes.anexa("bilica");
    
    // mostra comprimento e conteúdo da lista
    cout << "Comprimento: " << nomes.comprimento() << ", dados: ";
    nomes.escrevaSe(cout, ",");
    cout << endl;
    
    // insere dado no início da lista
    nomes.insere("maneca");
    cout << "Comprimento: " << nomes.comprimento() << ", dados: ";
    nomes.escrevaSe(cout, ",");
    cout << endl;

    // insere dado na posição 2 da lista
    nomes.insere("joaquim", 2);
    cout << "Comprimento: " << nomes.comprimento() << ", dados: ";
    nomes.escrevaSe(cout, ",");
    cout << endl;

    // remove dado do início da lista
    nomes.remove(0);
    cout << "Comprimento: " << nomes.comprimento() << ", dados: ";
    nomes.escrevaSe(cout, ",");
    cout << endl;
    
    // remove dado da posição 2 da lista
    nomes.remove(2);
    cout << "Comprimento: " << nomes.comprimento() << ", dados: ";
    nomes.escrevaSe(cout, ",");
    cout << endl;
    
    // esvazia a lista
    nomes.esvazia();
    cout << "Comprimento: " << nomes.comprimento() << ", dados: ";
    nomes.escrevaSe(cout, ",");
    cout << endl;
        
    // ao final, lista é automaticamente destruída, e a memória utilizada
    // é liberada
    return 0;
}

Atividade

Faça os exercícios sobre listas que estão no Moodle, para se familiarizar com listas

31/08: Projeto 2: outras operações da lista

A lista encadeada da Prglib ofere outras operações além daquelas para adicionar, obter e remover dados. Duas outras operações são de grande utilidade:

iteração: possibilita obter sucessivamente de forma eficiente os dados da lista;
ordenamento: ordena os dados de forma eficiente

Iteração

Quando se necessitam acessar em sequência todos (ou uma boa parte) dos dados de uma lista, a melhor forma é por meio da operação de iteração. A lista é capaz de ser iterada por meio dos métodos inicia, proximo e fim. Esses métodos são usados em conjunto para acessar cada dado da lista sucessivamente, a partir do início da lista. O exemplo a seguir mostra como usá-los:

#include <iostream>
#include <prglib.h>

using namespace std;
using prglib::lista;

int main() {
  lista<int> numeros;

  numeros.anexa(34);
  numeros.anexa(7);
  numeros.anexa(21);
  numeros.anexa(8);
  numeros.anexa(12);
  numeros.anexa(17);

  // inicia a iteração
  numeros.inicia();

  // enquanto não chegar ao fim da lista, continua a iteração
  while (not numeros.fim()) {
    // obtém o próximo dado da iteração 
    int algo = numeros.proximo();

    cout << "Numero: " << algo << endl;
  }
}

Essa forma de percorrer os dados de uma lista é muito mais eficiente do que acessar os dados a partir de suas posições (usando o método obtem ou o operador []). Para ter uma ideia, percorrer uma lista com 10 dados é 10 vezes mais rápido com iteração. Se a lista tiver 100 dados, a iteração é 100 vezes mais rápida. Se a lista tiver 1000 dados, a uteração é 1000 vezes mais rápida, e assim por diante. O tempo que se leva para percorrer todos os dados com iteração é proporcional à quantidade de dados, porém se for usado o método obtem (ou operador []), o tempo necessário é proporcional ao quadrado da quantidade de dados.

A iteração pode ser feita também em sentido contrário se forem usados os métodos iniciaPeloFim, anterior, e inicio:

#include <iostream>
#include <prglib.h>

using namespace std;
using prglib::lista;

int main() {
  lista<int> numeros;

  numeros.anexa(34);
  numeros.anexa(7);
  numeros.anexa(21);
  numeros.anexa(8);
  numeros.anexa(12);
  numeros.anexa(17);

  // inicia a iteração pelo fim da lista
  numeros.iniciaPeloFim();

  // enquanto não chegar ao início da lista, continua a iteração
  while (not numeros.inicio()) {
    // obtém o próximo dado da iteração 
    int algo = numeros.anterior();

    cout << "Numero: " << algo << endl;
  }
}

Ordenamento da lista

A lista possui o método ordena, que ordena seus dados. O ordenamento é feito por um algoritmo com razoável eficiência, e isso é importante porque esse tipo de operação tem custo computacional considerável (pode ser proporcional ao quadrado da quantidade de dados se não for bem feito). O único requisito para ordenar uma lista é que os dados armazenados possuam uma relação de precedência. Em outras palavras, que possam ser comparados com operador < (menor que). O exemplo a seguir mostra o ordenamento de uma lista:

#include <iostream>
#include <prglib.h>

using namespace std;
using prglib::lista;

int main() {
  lista<int> numeros;

  numeros.anexa(34);
  numeros.anexa(7);
  numeros.anexa(21);
  numeros.anexa(8);
  numeros.anexa(12);
  numeros.anexa(17);

  // ordena a lista
  numeros.ordena();

  numeros.escrevaSe(cout);

  cout << endl;
}

01/09: Projeto 2: conclusão

Na apresentação do projeto 2, modelou-se cada informação do IDHM na forma de um novo tipo de dados:

struct IDHM {
  string municipio;
  int ano;
  int uf;
  float idhm;
  float idhm_e;
  float idhm_l;
  float idhm_r;
 
  // construtor sem parâmetros: não inicializa os campos
  IDHM() {}
 
  // construtor que inicializa os campos com os valores contidos na linha do tipo CSV
  IDHM(const string & linha) {
    // coisas ...
  }
};

struct IDHM

Com base nessa struct IDHM, criou-se um pequeno programa para experimentar ler as linhas do arquivo com dados do Idhm. Cada linha foi convertida para um valor do tipo IDHM:

int main(int argc, char** argv) {
    ifstream arq(argv[1]);
    
    if (not arq.is_open()) {
        cout << "Erro: " << argv[1] << " não pode ser aberto" << endl;
        return 0;
    }
    
    string linha;
    while (getline(arq, linha)) {
        // processa linha
        try {
            IDHM dado(linha);

            // faz algo com esse valor IDHM        
        } catch (...) {
            cout << "+++ Erro: " << linha << endl;
        }
    }
    return 0;
}

O próximo passo é experimentar armazenar todos os valores IDHM em uma lista. Asism, as operações do analisador de IDHM podem ser mais facilmente realizadas, pois os dados estarão facilmente acessíveis em memória.

Atividade

Modifique seu programa para que, ao final da leitura do arquivo, todos os dados IDHM estejam armazenados em uma lista.

Ordenamento de tipos definidos pelo programador

Sobrecarga de operador

Novos tipos e classes podem ser definidos pelo programador por meio de declarações struct e class. Tais novos tipos não possuem uma relação de precedência predefinida. Se não é possível comparar valores de um tipo de dados, para saber quem vem antes de quem, não é possível também ordenar uma lista que contém esses valores. A solução envolve definir como valores de um novo tipo devem ser comparados para esse propósito, e isso implica definir o operador < para esse novo tipo.

Em C++ é possível definir operadores, o que se chama sobrecarga de operador. No caso de um novo tipo de dados, a definição do operador < pode ser feita assim:

struct Conta {
  string nome;
  int gastos;
 
  // Definição do operador < feita para comparar o valor gasto
  bool operator<(const Conta & outro) {
      return gastos < outro.gastos;
  }

  // construtor vazio ...
  Conta() {
    gastos = 0;
  }

  Conta(const string & umNome) {
    // implementação do construtor do tipo Conta
    nome = umNome;
    gastos = 0;
  }
};

Exemplo de um tipo Conta, que representa o total gasto por uma pessoa em um estabelecimento.

O exemplo a seguir mostra como dois valores Conta poderiam ser comparados com o operador <:

  Conta c1("Manuel Silva");
  Conta c2("Bilica Maria");

  c1.gastos = 100;
  c2.gastos = 200;
  
  if (c1 < c2) {
    cout << c1.nome << " gastou mais que " << c2.nome << endl;
  } else {
    cout << c2.nome << " gastou mais que " << c1.nome << endl;
  }

A comparação dos valores Conta usando o operador <, que no exemplo é feita desta forma:

  if (c1 < c2) {

... é equivalente a esta (feito implicitamente pelo compilador):

  if (c1.operator<(c2)) {

Assim, se o operador < for definido para o tipo Conta, uma lista de Conta pode ser ordenada.

Atividade

Resolva os exercícios sobre listas que estão no Moodle. Veja os exercícios que envolvem iteração e ordenamento.

Entrega do projeto

Prazo de entrega: 11/09/2017, 23:59 h
Entrega feita no Moodle
Pode ser feito por equipes de no máximo 03 alunos (ideal ser feito em dupla)
Os critérios de avaliação podem ser visto na descrição da tarefa no Moodle

14/09: Projeto 3: um programa para limpar dados redundantes

Leitura importantes:

Em aplicações que lidam com grandes quantidades de dados, informações redundantes não são aceitáveis. Considere-se o caso dos dados sobre IDHM do projeto 2, no qual o arquivo de dados que alimenta o sistema deve conter somente informações únicas. Se dados repetidos forem aceitos pelo sistema, os resultados de suas operações serão distorcidos ou mesmo incorretos. Sendo assim, a limpeza dos dados de entrada se torna uma função importante desse tipo de sistema.

Com o que foi estudado até o momento é possível limpar um arquivo de dados. Isso pode ser feito usando uma lista, porém há dúvida quanto à eficiência desse tipo de solução. O tempo para realizar uma limpeza pode ser muito alto, se comparado com a complexidade da tarefa.

Atividade

Seja este arquivo de dados:

Dados sobre IDHM com redundâncias

... escreva um programa que use listas para limpar os dados. Meça o tempo necessário para que seu programa complete a limpeza. O arquivo de projeto do Netbeans a seguir pode ser usado como ponto de partida:

Projeto 3

Tabela hash

Uma tabela hash é uma estrutura de dados feita para armazenar dados indexados. Ela é particularmente eficiente quando a quantidade de dados é muito menor que o espaço de índices, como mostrado na figura abaixo. Por dado indexado entende-se um dado que é associado a uma chave, a qual funciona como um índice para localizá-lo. Posto de outra forma, pode-se entender a tabela hash como um mapeamento entre chaves e dados. No exemplo do analisador, o dado é um log, e a chave pode ser a URL, o usuário, o IP, ou uma combinação deles. Além disso, a quantidade de dados, por maior que seja, é muito menor que todas as combinações de caracteres de URL, ou que a quantidade de possíveis endereços IP, e assim por diante. A ideia por trás da tabela hash é reduzir o espaço de índices, de forma que sua quantidade seja parecida com a dos dados indexados.

O espaço de chaves e a tabela hash (obtido do livro "Algoritmos, 2a. ed.", de T. Cormen et al)

Alguns exemplos de uso de tabelas hash na vida real:

A prglib possui uma implementação de tabela hash, mostrada a seguir:

template <typename T> class thash : public std::unordered_map<std::string,T> {
 public:
  // cria uma tabela hash com num_linhas linhas
  thash(int num_linhas);
 
  thash(const thash &outra); // construtor de copia
 
  // destrutor
  virtual ~thash();
 
  // adiciona um dado à tabela. Se já existir na tabela um par contendo a chave
  // "chave", o dado desse par deve ser substituído por "algo". Caso contrário,
  // um novo par deve ser adicionado à tabela.
  void adiciona(const std::string& chave, const T& algo);
 
  // remove a chave "chave" e o dado a ela associado.
  T remove(const std::string& chave);
 
  // retorna o dado associado a "chave"
  T& operator[](const std::string& chave);
  T& obtem(const std::string& chave);
 
  // retorna uma lista com as chaves existentes na tabela
  std::shared_ptr<lista<std::string>> chaves() const;
 
  // retorna uma lista com os dados existentes na tabela
  std::shared_ptr<lista<T>> valores() const;
 
  // retorna verdadeiro se "chave" existe na tabela
  bool existe(const std::string& chave) const;
 
  // esvazia a tabela
  void esvazia();
 
  // retorna a quantidade de dados (ou chaves) existentes na tabela
  unsigned int tamanho() const;
 
 private:
  unsigned int linhas; // a quantidade de linhas da tabela
};

A seguir há um exemplo de uso da tabela hash:

#include <iostream>
#include <prglib.h>

using namespace std;
using prglib::thash;
using prglib::lista;

/*
 * 
 */
int main(int argc, char** argv) {
    // cria uma tabela com 5 linhas
    thash<long> tab(5);
    
    // adiciona dados à tabela: primeiro parâmetro é a chave, e segundo é 
    // o valor a ela associado
    tab.adiciona("um", 1);
    tab.adiciona("dois", 2);
    tab.adiciona("tres",3);
    
    // mostra os valores armazenados
    cout << tab["um"] << endl;
    cout << tab["dois"] << endl;
    cout << tab["tres"] << endl;
    
    // obtém uma lista com as chaves contidas na tabela.
    // Notar o uso de std::shared_ptr (smart pointer), que é um ponteiro
    // que libera automaticamente a memória apontada quando não mais necessária.    
    auto chaves = tab.chaves();
    cout << "Chaves: ";
    chaves->escrevaSe(cout, ", ");
    
    // Obtém uma lista com os valores contidos na tabela
    cout << endl;
    auto valores = tab.valores();
    cout << "Valores: ";
    valores->escrevaSe(cout, ", ");

    cout << endl;
    
    // Testa se uma determinada chave existe na tabela
    if (tab.existe("dois")) cout << "Tabela contém a chave: dois" << endl;
    else cout << "Tabela NÃO contém a chave: dois" << endl;
    
    // remove uma chave da tabela e, por consequência, o valor a ela associado
    tab.remove("dois");
    cout << "Removeu a chave: dois" << endl;
    
    // Testa se a chave removida ainda existe na tabela
    if (tab.existe("dois")) cout << "Tabela contém a chave: dois" << endl;
    else cout << "Tabela NÃO contém a chave: dois" << endl;

    return 0;
}

Atividade

Escreva um programa que conte quantas palavras diferentes existem em um arquivo. Seu programa deve ignorar maiúsculas e minúsculas
Escreva um programa que extraia as palavras repetidas de um arquivo. Quer dizer, esse programa deve mostrar como resultado apenas a primeira ocorrência de cada palavra de um arquivo
Reescreva o limpador de dados redundantes usando uma tabela hash. Compare o tempo de execução desse novo programa com a versão feita inicialmente com listas.

15/09: Projeto 3: exercícios sobre tabela hash

Na aula de hoje alguns exercícios sobre tabela hash serão realizados.

Exercícios

Escreva um programa que conte quantas vezes cada palavra aparece em um arquivo
Escreva um programa que calcule o valor a ser pago por um cliente de um mercadinho em um determinado mês
Escreva uma classe cujos objetos verificam credenciais de usuários
Para cada uma das abordagens a seguir, escreva um programa que armazene os dados sobre IDHM em uma tabela hash:
- O programa possibilita consultas rápidas a municípios
- O programa possibilita consultas rápidas por estado (devem ser mostrados todos os municípios do estado)

ATENÇÃO: prova 1 !!!

A prova 1 deve ser realizada por meio do Moodle e INDIVIDUALMENTE. A descrição da prova está ao final da seção Etapa 1: Filas, Pilhas e Listas.

PRAZO: 24/09 23:59h

21/09: Projeto 3: o limpador de dados

Dicas sobre escritas em arquivos

O projeto 3 trata de implementar um programa para acessar dados de um arquivo contendo informações sobre IDHM. No entanto, as informações sobre IDHM podem conter redundâncias, tais como municípios repetidos. O programa deve primeiro limpar os dados, evitando informações redundantes ou inconsistentes. Feito isso, o programa deve possibilitar consultas aos dados.

No Projeto 2 escreveu-se um programa para acessar dados sobre IDHM. As informações foram lidas de um arquivo, cujas linhas possuem este formato: ANO,UF,Codmun6,Codmun7,Município,IDHM,IDHM_E,IDHM_L,IDHM_R. As colunas ANO, UF, C odmun6, Codmun7 e Município são únicas para cada descrição de IDHM de um município específico. Sendo assim, não podem existir duas ou mais linhas com os mesmos valores para essas colunas, ou com valores inconsistentes.

Uma inconsistência se manifesta pela discrepância entre códigos de município (colunas Codmun6 ou Codmun7) e UF e Município. Por exemplo, estas duas linhas são inconsistentes:

1991,11,110001,1100015,ALTA FLORESTA D'OESTE,0.329,0.112,0.617,0.516
1991,11,110001,1100015,FLORESTOPOLIS,0.329,0.112,0.617,0.516

... e estas duas também:

1991,11,110001,1100015,ALTA FLORESTA D'OESTE,0.329,0.112,0.617,0.516
1991,12,110001,1100015,ALTA FLORESTA D'OESTE,0.329,0.112,0.617,0.516

No caso de redundância, as linhas repetidas devem ser retiradas do arquivo de dados. No caso de inconsistência, TODAS as linhas envolvidas devem ser retiradas do arquivo de dados e gravadas num arquivo de log. Se ao menos um problema com inconsistência ocorrer, o programa deve terminar e avisar o usuário sobre o problema. Nesse caso, o programa deve ter processado completamente o arquivo de dados antes de terminar, para poder alertar o usuário sobre todos os dados com problemas. Cabe ao usuário analisar o arquivo de log e selecionar as linhas com os dados corretos, e ao final copiá-las para o arquivo de dados. Quando o arquivo de dados estiver correto, uma nova execução do programa deve possibilitar consultas aos dados carregados.

O arquivo contendo os dados a serem carregados é este:

Dados de IDHM com redundâncias e inconsistências

As consultas que podem ser feitas são:

Por Município: devem-se apresentar os dados de IDHM do município para todos os anos em que existem esses dados. Se existir mais de um município com mesmo nome, os dados de todos esses municípios devem ser apresentados.
Por Codmun6: devem-se apresentar os dados de IDHM do município associado com valor de Codmun6, para todos os anos em que existem esses dados.

OBS: podem-se usar uma ou mais tabelas hash para armazenar os dados.

O programa deve ter uma estrutura semelhante à do Projeto 2, sendo composto por um bloco Interface, um bloco Analisador, e a Prglib:

Atividade

Na aula de hoje pode-se trabalhar no desenvolvimento do projeto 3.

22/09: Projeto 3: conclusão

Leitura importantes:

A entrega do projeto deve ser feita por meio desta tarefa no Moodle.

Prazo: 2/10/2017
Equipes de até 3 pessoas

28/09: Projeto 4: um dicionário para auto-completar palavras

POG

Diversos programas possuem a função auto-completar para auxiliar usuários na digitação de dados. Essa função tenta adivinhar a palavra ou termo em digitação, oferecendo sugestões para o usuário. Editores de texto, aplicativos de celular (ex: Whatsapp), e até o shell possuem esse tipo de função. Um programa com tal função precisa possuir uma relação de palavras e termos, os quais são comparados com o que o usuário digita para oferecer sugestões. Essa busca deve ser prática e rápida, pois cada novo caractere digitado limita as possíveis palavras oferecidas.

As palavras conhecidas pelo programa precisam estar armazenadas de forma conveniente. Para uma determinada sequência inicial de caracteres digitados, todas as palavras por eles iniciadas devem ser procuradas e apresentadas. Por exemplo, se o usuário tiver digitado ban, possíveis sugestões são banco, banana e bandeira. Além disso, o usuário poderia ter controle sobre quando as sugestões seriam oferecidas. Uma abordagem usual é apresentá-las quando o usuário teclar TAB. No caso de uma interface de texto, isso seria mais prático do que buscar uma lista de palavras e apresentá-las a cada tecla digitada.

As estruturas de dados vistas até o momento não facilitam a realização dessa tarefa: listas possibilitam buscas somente na força bruta, e tabelas hash associam uma única chave a um valor. Porém uma nova estrutura de dados chamada árvore binária pode ser útil para armazenar as palavras e facilitar as buscas.

Árvores binárias

Árvores binárias

Uma nova estrutura de dados chamada árvore de pesquisa binária proporciona uma grande eficiência no tempo de busca de um dado. Ela também tem outras propriedades interessantes, e que são úteis para resolver diversos problemas. O projeto 4 deve se valer dessa estrutura de dados para armazenar os dados sobre a lista telefônica invertida.

Uma estrutura de dados que possibilita consultas rápidas se chama árvore. Tal estrutura mantém os dados organizados de forma hierárquica, o que reduz bastante a quantidade de comparações necessárias para se encontrar algum valor. Um exemplo é a árvore de diretórios, que organiza os arquivos em disco em diretórios que formam um diagrama hierarquizado. Esse tipo de estrutura é largamente utilizada em bancos de dados, e também possui diversas aplicações em muitas outras áreas de conhecimento (redes de computadores, análise combinatória, mapas digitais, sistemas de decisão, linguística, diagramas em geral).

Uma pequena árvore binária

Um exemplo de árvore é mostrado na figura acima. A hierarquia inicia em um nodo chamado de raiz. Os demais nodos são conectados de forma hierárquica, sem haver caminhos fechados. Cada nodo possui ramos que conectam os nodos um nível abaixo na árvore. Nodos que não possuem ramos são chamados de folhas. Uma árvore cujos nodos possuem no máximo dois ramos cada é chamada de árvore binária, sendo a árvore mais simples que se pode criar.

Árvore de Pesquisa Binária

Árvore de pesquisa binária na Wikipedia

Uma árvore de pesquisa binária é um tipo especial de árvore binária usada para armazenar valores ordenáveis. Nesse tipo de árvore a seguinte propriedade é verificada em todos os seus nodos:

valores anteriores àquele contido em um nodo ficam na árvore conectada ao ramo esquerdo.
valores sucessores àquele contido em um nodo ficam na árvore conectada ao ramo direito.

Dois exemplos de árvores de pesquisa binárias são mostrados abaixo. No exemplo 1 armazenam-se strings na árvore, e no exemplo 2 armazenam-se números. Em ambos os casos a propriedade da árvore de pesquisa binária é verificada. Note que os valores à esquerda de um nodo são sempre antecessores ao valor desse nodo, e do lado direito são sempre sucessores. Com isso, a estrutura da árvore de pesquisa binária implicitamente ordena os valores armazenados, o que é útil para diversas aplicações.

Exemplo 1	Exemplo 2

Mas por que essa estrutura de dados é eficiente para armazenar a lista telefônica invertida ? Basicamente porque, ao hierarquizar os valores, é possível facilmente guardá-los de forma ordenada. Se a árvore estiver bem balanceada (isso é, tem a mesma quantidade de nodos a partir de ambos os ramos de cada nodo), cada comparação da busca divide a quantidade de nodos restante pela metade. Assim, a quantidade de comparações até localizar o valor procurado é limitada superiormente pela altura da árvore (a quantidade de ramos entre o nodo raiz e o nodo folha mais distante da raiz).

Para fins de comparação, seja o projeto 4 implementado com lista encadeada e árvore de pesquisa binária. O custo computacional para localizar um telefone em uma lista é $O(n)$ , pois, no pior caso, cada telefone procurado pode ser comparado com todos os telefones existentes na lista. Se for usada uma árvore de pesquisa binária, esse custo pode ser $O(log_{2}n)$ , contanto que certas propriedades da árvore sejam verificadas (isso será discutido mais adiante).

A árvore de pesquisa binária da prglib

Arquivo de projeto do Netbeans

A biblioteca prglib possui uma árvore de pesquisa binária simplificada. Ela foi implementada como uma classe template, para que a árvore possa armazenar qualquer tipo de dado. No entanto, apenas tipos de dados ordenáveis podem ser armazenados (que possuem uma relação de precedência e implementem os operadores == e <). A árvore possui operações para adicionar, procurar e remover dados, para listar os dados em profundidade (in-order, pre-order e post-order) ou largura, para iterar os dados (apenas in-order), e para balanceamento AVL. A declaração dessa árvore está a seguir.

A árvore de pesquisa binária da prglib

template <typename T> class arvore {
 public:
  arvore();
  arvore(const T & dado);
  virtual ~arvore();

  // adiciona um dado à árvore
  void adiciona(const T& algo);

  // busca um dado na árvore
  T& obtem(const T & algo) const;

  // lista os dados da árvore na sequêcias in-order, pre-order, post-order
  // ou em largura
  void listeInOrder(lista<T> & result);
  void listePreOrder(lista<T> & result);
  void listePostOrder(lista<T> & result);
  void listeEmLargura(lista<T> & result);

  // retorna a quantidade de dados na árvore
  unsigned int tamanho() const;  
  
  // retorna a altura da folha mais profunda
  unsigned int altura() ;

  // retorna o fator de balanceamento
  int fatorB() ;

  // balanceia a árvore
  arvore<T> * balanceia();

  // balanceia a árvore até não poder mais reduzir sua altura
  arvore<T> * balanceia(bool otimo);
  
  // iterador da árvore (in-order)
  void inicia();
  bool fim();
  T& proximo();

  // iterador reverso da árvore (in-order)
  void iniciaPeloFim();
  bool inicio();
  T& anterior();
  
  // remove um dado
  T remove(const T & algo);

  // obtém uma referência ao menor dado
  T & obtemMenor() const;

  // obtém uma referência ao maior dado
  T & obtemMaior() const;
  
  // obtém uma lista com os dados menores ou maiores que algo
  void obtemMenoresQue(lista<T> & result, const T & algo);
  void obtemMaioresQue(lista<T> & result, const T & algo);

  // obtém todos valores entre "start" e "end" (inclusive)
  void obtemIntervalo(lista<T> & result, const T & start, const T & end);
};

arvore.h

Um exemplo de uso de uma pequena árvore binária é este:

#include <iostream>
#include <prglib.h>

using namespace std;

using prglib::arvore;
using prglib::lista;

/*
 * 
 */
int main(int argc, char** argv) {

    arvore<int> * a = new arvore<int>(10);
    
    a->adiciona(5);
    a->adiciona(7);
    a->adiciona(2);
    a->adiciona(13);
    a->adiciona(11);
    a->adiciona(15);
        
    lista<int> l;
    a->listeInOrder(l);
    
    cout << "In-order: ";
    l.escrevaSe(cout, ", ");
    cout << endl;

    return 0;
}

Atividade

Resolva estes exercícios:

Feito esse aquecimento:

Crie uma árvore de pesquisa binária contendo as palavras deste arquivo.
Procure cada uma das palavras contidas na árvore. Meça quanto tempo levou para encontrá-las (média, menor e maior valor)
1. Repita a medição, mas ao invés de guardar as palavras em uma árvore, guarde-as em uma lista.
2. Repita a medição, mas ao invés de guardar as palavras em uma árvore, guarde-as em uma tabela hash.
3. Compare os tempos gastos em cada caso ...

29/09: Projeto 4: ajustes finos

A eficiência das árvores de pesquisa binária para armazenar dados de forma que possam ser localizados rapidamente depende de como esses dados ficam distribuídos na árvore. Se a árvore estiver desequilibrada (desbalanceada), a eficiência nas buscas será reduzida. Hoje veremos alguns fatores relacionados ao balanceamento de árvores, e como garantir que uma árvore fique bem equilibrada.

Quão eficiente ficou sua árvore ?

Uma árvore fica mais eficiente se estiver balanceada. Isso significa que, para cada nodo da árvore, as alturas dos ramos esquerdo e direito diferem em no máximo uma unidade. Se uma árvore possuir essa propriedade, sua altura será minimizada e assim as buscas serão mais rápidas. Para entender porque, veja que uma árvore com altura h pode conter uma certa quantidade de nodos:

Altura	Nodos (máximo)	Exemplo
0	1
1	3
2	7
3	15

De forma geral, a quantidade máxima de nodos que cabem em uma árvore binária com altura h é dada por esta recorrência:

$N_{h}=1+2\cdot N_{h-1}$

... sendo que $N_{0}=1$ . A recorrência acima pode ser escrita mais diretamente como:

$N_{h}=2^{h+1}-1$

Usando esta relação, pode-se descobrir qual a menor altura possível para uma árvore que contenha N nodos:

$h=-1+\lceil log_{2}(1+N)\rceil$

Na prática, as árvores que criamos não estão otimizadas. Porém iremos comparar as alturas dessas árvores com a altura mínima possível para ter uma ideia de quão eficientes elas são.

O cálculo da altura de uma árvore A pode ser feito segundo esta recorrência:

$h(A)={\begin{cases}0,{\text{if }}A_{esq}=NULL\land A_{dir}=NULL\\1+max(h(A_{esq}),h(A_{dir})),{\text{caso contrario}}\\\end{cases}}$

Fator de balanceamento

O fator de balanceamento é a diferença entre as alturas das árvores esquerda e direita, e pode ser calculado assim:

$F_{b}=altura(esquerda)-altura(direita)$

Se para todos os nodos da árvore $\lVert F_{b}<=1\rVert$ , então a árvore está balanceada e nada precisa ser feito. Porém se para algum nodo $\lVert F_{b}>1\rVert$ , então existe um desequilíbrio (má distribuição de nodos), o qual pode ser corrigido.

Criação de árvores balanceadas

Para criar uma árvore balanceada, pode-se fazer o seguinte:

se a árvore for criada a partir de um conjunto de dados já disponível, uma boa técnica é embaralhar os dados e depois criar a árvore. Isso cria uma árvore aceitavelmente balanceada, se bem que não de forma otimizada. Um ajuste pode ser feito no balanceamento usando-se um algoritmo apropriado.
se os dados forem acrescentados gradualmente à árvore,correções em seu balanceamento devem ser feitas periodicamente usando-se um algoritmo apropriado.

Em ambos os casos, um algoritmo de balanceamento é útil para fazer com que a árvore fique bem equilibrada. Um desses algoritmos é apresentado a seguir.

Balanceamento

AVL Tree

Nos experimentos feitos até agora, as árvores de pesquisa binária apresentaram um bom desempenho tanto para serem criadas quanto para pesquisarem valores. Foi estudado que isso se deve a uma importante propriedade da árvore binária, que limita à altura da árvore a quantidade de operações de comparação em uma pesquisa qualquer. Como a altura é função do logaritmo da quantidade de nodos, ela tende a crescer muito lentamente com o aumento da quantidade de nodos da árvore (ex: uma árvore com pouco mais 2.3 milhões de nodos teria altura de pelo menos 21). Porém isso depende de os nodos estarem igualmente distribuídos dos dois lados da árvore. Em outras palavras, a árvore deve estar balanceada.

A árvore disponibilizada na prglib pode ser balanceada usando o algoritmo clássico AVL. Mas outras abordagens existem, tais como árvores vermelho-preto. A abordagem AVL é mais simples de implementar que RBT, porém a segunda funciona melhor para árvores que são frequentemente modificadas. Uma interessante comparação entre árvores AVL e Vermelho-Preto pode ser lida na Wikipedia:

Red–black trees offer worst-case guarantees for insertion time, deletion time, and search time. 
Not only does this make them valuable in time-sensitive applications such as real-time applications, 
but it makes them valuable building blocks in other data structures which provide worst-case 
guarantees; for example, many data structures used in computational geometry can be based on 
red–black trees, and the Completely Fair Scheduler used in current Linux kernels uses red–black 
trees.

The AVL tree is another structure supporting O(log n) search, insertion, and removal. It is more 
rigidly balanced than red–black trees, leading to slower insertion and removal but faster retrieval. 
This makes it attractive for data structures that may be built once and loaded without 
reconstruction, such as language dictionaries (or program dictionaries, such as the opcodes of an 
assembler or interpreter).

No caso da árvore da prglib, o balanceamento pode ser realizado por meio do método balanceia:

  // balanceia a arvore usando o algoritmo AVL. 
  // Retorna a raiz da nova arvore ... pois o algoritmo pode modificar a raiz.
  arvore<T> * balanceia();

  // Balanceia o melhor possivel a arvore. Executa o método ''balanceia()'' repetidas
  // vezes, até que a altura da árvore não mais reduza.
  arvore<T> * balanceia(bool otimo);

Um exemplo de como utilizá-lo é mostrado a seguir:

int main() {
  arvore<int> * arv = new arvore<int>(5);

  arv->adiciona(4);
  arv->adiciona(3);
  arv->adiciona(2);
  arv->adiciona(1);
  arv->adiciona(0);

  // a arvore "arv" está totalmente desbalanceada, tendo todos os nodos do lado esquerdo
  // Mostra seu fator de balanceamento e sua altura
  cout << "Altura: " << arv->altura() << endl;
  cout << "Fator de balanceamento: " << arv->fatorB() << endl;

  // balanceia a arvore
  arv = arv->balanceia();

  // Mostra novamente seu fator de balanceamento e sua altura
  cout << "Altura: " << arv->altura() << endl;
  cout << "Fator de balanceamento: " << arv->fatorB() << endl;

  // destroi a arvore
  delete arv;
}

Enumeração dos dados de uma árvore

Até o momento nos concentramos em operações básicas de árvores. Elas possibilitam criar e adicionar dados a uma árvore, e pesquisar por um dado em função de um dado específico. Porém outras formas de acessar os dados de uma árvore podem ser úteis, dentre elas o acesso sequencial de acordo com uma determinada ordem. Por exemplo, pode-se desejar acessar os dados de uma árvore de forma ordenada. Assim, devem-se conhecer as quatro ordens de visitação de nodos de uma árvore:

Tipo	Descrição	Exemplo
In order	visitam-se nodos na sequência esquerda, raiz, direita. O resultado é o acesso ordenado em função das chaves
Pre order	visitam-se nodos na sequência raiz, esquerda, direita. O resultado é uma ordem de acesso que revela a topologia da árvore
Post order	visitam-se nodos na sequência esquerda, direita, raiz. O resultado é uma ordem de acesso das folhas em direção à raiz
Level order	visitam-se nodos cada nível por vez, da esquerda pra direita

As três primeiras formas de acesso são do tipo busca em profundidade, pois implicam descer até as folhas de um lado antes de visitarem o outro lado da árvore. A última forma de acesso é do tipo busca em largura, pois os nodos são visitados por nível da árvore.

Cada uma das formas de acesso tem sua aplicações em algoritmos. Por exemplo, in order serve para ordenar os dados, pre order pode ser usada para copiar uma árvore, e post order pode ser usado para destruir uma árvore. Alguns algoritmos já criados usam algumas dessas formas de acesso (ex: escrevaSe é do tipo in order; o destrutor da árvore e altura são do tipo post order). Hoje será visto como implementar métodos genéricos que enumeram os dados de uma árvore segundo essas sequências de acesso.

  void listeInOrder(lista<T> & result);
  void listePreOrder(lista<T> & result);
  void listePostOrder(lista<T> & result);
  void listeEmLargura(lista<T> & result);

Os métodos de enumeração na classe arvore

Atividade

Crie a árvore que armazena as palavras contidas neste arquivo.
Investigue a altura e fator de balanceamento dessa árvore
Balanceie sua árvore, e verifique o novo fator de balanceamento e altura. Compare-os com a menor altura possível teoricamente.

05/10: Projeto 4: conclusão

Conclusão da função auto-completar. Hoje deve-se completar a modelagem da árvore de pesquisa binária usada para armazenar as palavras, e especificar o algoritmo de busca da lista de palavras que possuem um prefixo em comum. Finalmente, deve-se modelar o programa que demonstra a função auto-completar ... por exemplo, essa funcionalidade pode ser fornecida por objetos desta classe:

class Oraculo {
 public:
  // construtor: carrega as palavras contidas no arquivo
  Oraculo(const string & arquivo_de_palavras);

  // destrutor
  ~Oraculo();

  // adiciona mais palavras, as quais são lidas de um arquivo
  void adiciona_palavras(const string & arquivo_de_palavras);

  // adiciona mais palavras, as quais estão contidas em uma lista
  void adiciona_palavras(lista<string> & lista_de_palavras);

  // Busca todas as palavras que possuem o prefixo
  lista<string> busca(const string & prefixo);

 private:
  // atributos
 
};

Para ler caracteres do teclado à medida que são digitados (sem esperar pelo ENTER), baseiem-se neste exemplo:

int main(int argc, char** argv) {
    // configura o terminal para retornar imediatamente cada caractere digitado
    system("stty raw -echo icrnl opost");
    cout << "> ";
    while (true) {
        char caractere;
        
        cin.get(caractere);
        if (caractere == '\t') { // TAB
            cout << " !!!TAB!!! ";
        } else {
            if (caractere == 13 or caractere == 10) break;
            else cout << caractere;
        }
        cout.flush();
    }
    cout << endl;
    system("stty cooked echo");
}

A entrega do projeto 4 deve ser feita pelo Moodle:

Projeto 4 no Moodle

Curiosidade: Árvores de expressão binária

Árvores binárias podem ter outras aplicações além de armazenar dados de forma a possibilitar buscas eficientes. A representação de expressões aritméticas e algébricas é outro uso de árvores. Essas expressões também possuem uma hierarquia, dada pela precedência de operadores, o que as torna passíveis de serem representadas por árvores. Uma vez transformada em uma árvore binária, uma expressão pode ser facilmente avaliada, obtendo-se seu resultado. Esse tipo de árvore é chamado de árvore de expressão binária.

Uma árvore de expressão binária para a expressão (a+b)*c+7

Note-se que ness tipo de árvore as folhas são operandos (constantes ou variáveis), e demais nodos são operadores aritméticos. A topologia da árvore deve respeitar a precedência dos operadores, para que o resultado da expressão possa ser obtido (isso se faz ao percorrê-la segundo in-order).

Árvores de expressão binária são úteis para resolver expressões fornecidas em tempo de execução. Por exemplo, uma calculadora pode permitir que o usuário digite uma expressão a ser calculada, que é lida portanto como uma string. Para resolvê-la, pode-se transformá-la em uma árvore binária, e então calculá-la. Assim, qualquer programa que precise resolver expressões fornecidas pelo usuário pode usar essa técnica para avaliá-las.

Avaliando uma expressão contida em um árvore binária

Uma árvore de expressão binária devidamente construída pode ser facilmente avaliada se for percorrida in-order. O algoritmo basicamente funciona assim:

algoritmo resolveExpressao(arvore):
  Entrada: uma arvore de expressão binária
  Saída: o resultado da expressão após sua avaliação
  Variáveis locais: operador (tipo caractere), resultado (tipo ponto flutuante)

  se arvore for vazia: retorne 0

  se arvore for folha: retorne valor da folha

  operador = raiz da arvore
  Escolha (operador):
    caso '+': 
      resultado = resolveExpressao(arvore esquerda) + resolveExpressao(arvore direita)
    caso '-': 
      resultado = resolveExpressao(arvore esquerda) - resolveExpressao(arvore direita)
    caso '*': 
      resultado = resolveExpressao(arvore esquerda) * resolveExpressao(arvore direita)
    caso '/': 
      resultado = resolveExpressao(arvore esquerda) / resolveExpressao(arvore direita)
    caso '%': 
      resultado = resolveExpressao(arvore esquerda) % resolveExpressao(arvore direita)
    caso '^': 
      resultado = resolveExpressao(arvore esquerda) ^ resolveExpressao(arvore direita)
  fim Escolha
  retorne resultado
fim resolveExpressao

Construção de uma árvore de expressão binária

A construção automática da árvore inicia com um vetor ou lista composta por um nodo (árvore que possui somente a raiz) para cada token da expressão. Em seguida, agrupar sistematicamente os nodos em árvores cujas raízes sejam operadores. Isso deve ser feito respeitando a precedência dos operadores. O funcionamento desse algoritmo pode ser visualizado pela seguinte sequência de diagramas, que mostra o agrupamento dos nodos de acordo com a precedência de operadores, até que no final haja somente uma árvore:

... e então ? Será que é fácil escrever tal algoritmo ?

Curiosidade: Radix tree (trie)

Trie na Wikipedia

Um trie, ou radix tree, é um tipo de árvore em que as chaves não estão nos nodos e sim nas transições. A chave associada a cada nodo depende da posição do nodo em relação à raiz, tomando-se as transições necessárias para chegar a tal nodo. Valores podem estar associados a folhas e nodos de interesse. Esse tipo de árvore, que NÃO NECESSARIAMENTE É BINÁRIA, é útil para representar conjuntos de dados que podem ser pesquisados por seus prefixos. Exemplos de aplicações são tabelas de roteamento em roteadores e armazenamento de palavras de dicionário (em particular quando se desejam sugerir palavras a partir de suas letras iniciais).

A figura a seguir exemplifica um trie.

Exemplo de trie (obtido na Wikipedia)

Curiosidade: árvores binárias no kernel Linux

Estruturas de dados disponíveis dentro do kernel Linux (cap. 6 do livro Linux Kernel Development, 3rd ed., de Robert Love, 2010)

Algumas estruturas de dados estão disponíveis para uso dentro do kernel Linux. Há filas, listas, tabelas hash e árvores binárias para ajudar no desenvolvimento tanto do kernel quanto de módulos e device drivers. Elas não se destinam ao desenvolvedor de aplicações, e sim a desenvolvedores do kernel (esperem a disciplina de SOP para entender melhor isso).

Com respeito a árvores binárias, destaca-se este parágrafo ao final do capítulo do livro:

If you need to store a large amount of data and look it up efficiently, consider a red-
black tree. Red-black trees enable the searching in logarithmic time, while still providing
an efficient linear time in-order traversal.Although more complicated to implement than
the other data structures, their in-memory footprint isn’t significantly worse. If you are
not performing many time-critical look-up operations, a red-black tree probably isn’t
your best bet. In that case, favor a linked list.

06/10: Projeto 4: conclusão

19/10: Avaliação 2

A 2a avaliação individual será realizada presencialmente nesta aula por meio do Moodle. Ela será composta de 5 questões valendo 100 pontos cada. O resultado da avaliação ajusta os conceitos dos projetos 3 e 4 da seguinte forma:

3 ou mais questões 100% corretas: os conceitos dos projetos 3 e 4 são aumentados em 2 pontos
2 questões 100% corretas: os conceitos dos projetos 3 e 4 são mantidos
1 questão 100% correta e outra questão com nota >= 50: os conceitos dos projetos 3 e 4 são reduzidos em 2 pontos
demais resultados: os conceitos dos projetos 3 e 4 são anulados

PRG2-2017-2

Programação 2: Diário de Aula 2017-2

Referências complementares

Cursos e videos online

Avaliações

Softwares

27/07: Apresentação e introdução ao projeto

Introdução a C++

Um exemplo com números complexos

Uso do NetBeans

Exercícios

28/07: Introdução a C++

Jogo da Forca

O jogo da Forca em linguagem C++

TAREFA para dia 03/08

03/08: Introdução a C++: exercícios

04/08: Projeto 1: um enumerador de arquivos

Atividade

A localização de arquivos e subdiretórios

10 e 11/08: Projeto 1: uso de filas e pilhas para percorrer os diretórios

Filas

Exercícios

Pilhas

Atividade

17/08: Projeto 1: Algoritmos de busca do localizador

Atividade

18/08: Projeto 1: conclusão

Processamento dos argumentos de linha de comando

Entrega do projeto

24/08: Projeto 2: um programa para acessar dados de IDH

Atividade

25/08: Projeto 2: introdução a listas

Atividade

31/08: Projeto 2: outras operações da lista

Iteração

Ordenamento da lista

01/09: Projeto 2: conclusão

Atividade

Ordenamento de tipos definidos pelo programador

Atividade

Entrega do projeto

14/09: Projeto 3: um programa para limpar dados redundantes

Atividade

Tabela hash

Atividade

15/09: Projeto 3: exercícios sobre tabela hash

Exercícios

ATENÇÃO: prova 1 !!!

21/09: Projeto 3: o limpador de dados

Atividade

22/09: Projeto 3: conclusão

28/09: Projeto 4: um dicionário para auto-completar palavras

Árvores binárias

Árvore de Pesquisa Binária

A árvore de pesquisa binária da prglib

Atividade

29/09: Projeto 4: ajustes finos

Quão eficiente ficou sua árvore ?

Fator de balanceamento

Criação de árvores balanceadas

Balanceamento

Enumeração dos dados de uma árvore

Atividade

05/10: Projeto 4: conclusão

Curiosidade: Árvores de expressão binária

Avaliando uma expressão contida em um árvore binária

Construção de uma árvore de expressão binária

Curiosidade: Radix tree (trie)

Curiosidade: árvores binárias no kernel Linux

06/10: Projeto 4: conclusão

19/10: Avaliação 2

Menu de navegação

Pesquisa