Mudanças entre as edições de "PRG2-2017-2"

De MediaWiki do Campus São José
Ir para navegação Ir para pesquisar
Linha 809: Linha 809:
 
== Atividade ==
 
== Atividade ==
  
−
# 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. <syntaxhighlight lang=c>
+
# 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: <syntaxhighlight lang=c>
 
struct IDHM {
 
struct IDHM {
 
   string municipio;
 
   string municipio;
Linha 818: Linha 818:
 
   float idhm_l;
 
   float idhm_l;
 
   float idhm_r;
 
   float idhm_r;
 +
};
 +
</syntaxhighlight> ... ou: <syntaxhighlight lang=c>
 +
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) {
 +
  }
 
};
 
};
 
</syntaxhighlight>
 
</syntaxhighlight>

Edição das 14h08min de 24 de agosto de 2017

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

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

Cursos e videos online

Avaliações

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

  1. Projetos: feitos em equipes de até dois alunos, são desenvolvidos ao longo da disciplina.
  2. 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).
  3. Relatórios técnicos: são feitos individualmente ao final de cada capítulo da disciplina, e podem confirmar o conceito final, aumentá-lo ou decrementá-lo em um nível.


Aluno Projeto 1 Projeto 2 Prova 1 Projeto3 Projeto 4 Prova 2 Proj. Lib Prova3 FINAL Faltas até 20/12
(máx: 18/semestre)

Obs:

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

Softwares

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


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:

  1. 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.
  2. 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.


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.


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:

  1. 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)
$
  2. 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.
  3. Faça o download do instalador do Netbeans:
  4. 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
  5. 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:

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

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

Jogo da Forca


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.

Prg2-forca.gif


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++


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


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.

PRG2-20162-Localizador.jpg


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:

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:

  1. Descompacte o arquivo de projeto
  2. Entre no diretório do projeto. Ex: 
    cd Enumerador
  3. Compile o programa exemplo: 
    make
  4. 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

  1. Use a classe Diretorio para listar um diretório qualquer. Mostre os nomes dos arquivos e subdiretórios ali existentes.
  2. Modifique o programa anterior para listar cada um dos subdiretórios encontrados.
  3. Modifique o programa para identificar os arquivos que possuem um determinado nome.
  4. 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.

Prg2-20162-Dirtree.gif

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


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

Prg-queue.png


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

  1. 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		 Prg-pilha.jpg


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

  1. 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

  1. Implemente os algoritmos de busca em largura e em profundidade
  2. 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;
}

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:


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:


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

  1. 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() {}

  // construtor que inicializa os campos com os valores contidos na linha do tipo CSV
  IDHM(const string & linha) {
  }
};
  2. 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.

Listas encadeadas


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:

Prg2-2016-2-Lista1.jpg


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 
template <typename T> class lista : public std::list<T> {
    
 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".
  std::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
  void inicia();
  void iniciaPeloFim();
  bool fim() const;
  bool inicio() const;
  T & proximo();
  T & anterior();
  
  // inverte a ordem dos dados da 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

  1. Faça os exercícios sobre listas que estão no Moodle, para se familiarizar com listas
Disponível em “https://wiki.sj.ifsc.edu.br/index.php?title=PRG2-2017-2&oldid=134894”