sexta-feira, 22 de maio de 2015

[P10] Programa = Estruturas de Dados + Algoritmos

     Uma definição interessante de programa relacionando o conceito à estruturas de dados e algoritmos foi proposta por Niklaus Wirth, em 1976: Algorithms + Data Structures = Programs. Trata-se de um livro de mesmo nome que discute sobre tópicos fundamentais de programação de computadores. Para maiores informações acesse este site da Wikipedia.

Considere o seguinte problema:
Um professor ministra aulas para uma turma de alunos e estes realizam três avaliações por semestre. A turma possui 30 alunos e cada aluno, além do nome e das notas das três avaliaçôes (valores entre 0 e 10 - assumindo que uma nota válida é sempre inserida para o aluno), possui um total de presenças no semestre. O professor guarda o total de encontros realizados em cada turma. O professor gostaria de calcular algumas estatísticas que julga interessantes, tais como a média das notas da turma, o número de alunos com notas abaixo da média (7,0) e o número de alunos com frequência tanto acima quanto abaixo de 75%. O professor também gostaria de buscar (procurar) alunos pelo nome do aluno e mostrar suas notas e o número de presenças em um relatório.

Modelagem

     Como modelar este problema?
     Sem considerar o paradigma de programação envolvido (orientado a objetos ou imperativo), quais são as estruturas de dados envolvidas e as funcionalidades que o professor deseja realizar? Como transformar esta especificação escrita em alto-nível em um código-fonte compilável e executável?

Estruturas de dados:
  1. Turma
    1. lista de alunos (uma estrutura homogênea que guarda um aluno (uma estrutura heterogênea, ou seja, um registro))
    2. total de encontros (provavelmente um valor inteiro)
  2. Aluno
    1. nome (um valor textual, ou seja, uma estrutura homogênea que trababalhe com caracteres)
    2. presenças (um valor inteiro)
    3. notas (de 1 a 3 valores reais, ou seja, números com ponto flutuante, sendo uma estrutura homogênea)
Funcionalidades desejadas:
  1. Cálculo de estatísticas
    1. Cálculo da média das notas da turma
    2. Cálculo do total de alunos com frequência acima de 75%
    3. Cálculo do total de alunos com frequência abaixo de 75%
  2. Criação de uma turma
    1. Associação do total de presenças em uma turma
  3. Criação de um aluno
    1. Associação das notas de um aluno
  4. Inserção de um aluno em uma turma
  5. Mostrar os dados dos alunos (todos, inclusive estatísticas) de uma turma
  6. Busca de um aluno em uma turma pelo nome
  7. Função principal main() necessária sempre em qualquer implementação de um programa
Programa:
  1. main.c (Linguagem C) e main.cpp (Linguagem C++) = contém a criação das turmas, alunos e associações necessárias (nome e notas a alunos, alunos a turmas, total de presenças à turmas)
  2. Estrutura de dados Aluno
  3. Estrutura de dados Turma
  4. Algoritmos para cálculos das estatísticas

OBSERVAÇÃO: antes de começar a mostrar alternativas de implementação, é importante que se mencione que existem muitas formas de modelar e implementar este problema, sendo a apresentada aqui apenas uma alternativa viável. É importante que você como programador implemente outras formas a fim de aprimorar sua própria técnica de programação.

Paradigma Imperativo, ou Estruturado

     A característica principal do paradigma imperativo (ou estruturado) é definir funções que operam sobre as estruturas de dados (que são passadas por parâmetro). Os acessos são públicos, ou seja, é possível alterar os valores de quaisquer estruturas de dados a qualquer momento (cabe ressaltar que estamos trabalhando com ponteiros, então os endereços de memória que são passados referem-se às estruturas de dados, ou seja, qualquer alteração é realizada diretamente sobre os dados).
     O paradigma foi e ainda é amplamente utilizado, necessitando um nível de experiência alto por parte dos programadores para acessar e operar de forma eficiente os algoritmos e os tratamentos com a memória.

Paradigma Orientado a Objetos

     Em orientação a objetos, as estruturas de dados são chamadas de classes. As instâncias de cada classe são chamadas de objetos. As classes possuem atributos (características dos objetos) e operações (métodos). Os objetos são instanciados a partir de classes, podendo existir muitos objetos (com estados diferentes) de uma mesma classe. No nosso exemplo, será criado um objeto da classe Turma e um aluno da classe Aluno. Cada objeto terá suas próprias características, ou seja, possuirá um estado diferente. Para o caso dos alunos, cada objeto terá um nome específico e uma listagem de notas.
     As classes no projeto são: Turma e Aluno, além do método main(), sempre necessário em qualquer implementação. A turma e o aluno, em termos de características são idênticas à forma imperativa anterior, mas agora possuem operações (métodos) que operam sobre seus atributos (variáveis internas - sempre privadas). Por exemplo, a turma trata com uma lista de alunos e cada aluno trata das suas notas, seu nome e seu total de presenças.
     O conceito chave em orientação a objetos é a proteção aos dados. A forma que é feita esta proteção é através dos modificadores de acesso aos atributos, ou seja, os modificadores public e private (OBS: o modificador protected será explicado em um outro momento pois não faz sentido sem o conceito de herança).
     Como sugestão (uma forte sugestão), todos os atributos de um objeto devem ser privados, ou seja, não deve ser permitido modificá-los exceto através de métodos públicos. Por exemplo, o nome do aluno: apenas a própria classe pode ter acesso irrestrito. Por isso que ao instanciar um aluno na função principal main(), não é permitido fazer a seguinte chamada: aluno->nome = "João da Silva"; - o que era permitido antes. As maneiras de se alterar o nome do aluno são duas: através do método especial construtor (método invocado quando um objeto é instanciado) ou através do método público chamado void setNome(string novo); definido na classe aluno (a chamada seria feita desta forma: aluno->setNome("João da Silva");, onde aluno é uma instância (um objeto), do tipo ponteiro, da classe Aluno).
     A implementação é bem parecida com o paradigma imperativo, exceto que agora, ao operar sobre a turma, não é mais necessário passar uma referência de turma por parâmetro, basta disparar o método do objeto turma.

Resumo das diferenças de definições e nomenclaturas

     A tabela a seguir mostra as principais diferenças entre as abordagens estruturada ou imperativa e orientada a objetos. Cabe ao programador escolher a melhor linguagem e paradigma para resolver seu problema. Idealmente, um programador sabe e domina diversos paradigmas e linguagens de programação (pelo menos o básico, depois é possível se aprofundar). Os conceitos inerentes à cada paradigma devem ser firmemente entendidos pelos programadores, auxiliando-os a resolver problemas e transformar especificações escritas por clientes em códigos-fonte consistentes, coerentes e lógicos.

Programação imperativa Programação orientada a objetos
Registros (structs) Classes (class)
Funções Métodos (operações)
Variáveis Atributos (características)
Instâncias de classes (objetos)
Acesso público Acesso público e privado
Referências e ponteiros Referências e ponteiros
Variáveis locais de funções Variáveis locais de métodos
Bibliotecas de funções Bibliotecas de classes (STL em C++)

Arquivos dos projetos

     Existem basicamente duas ideias principais utilizando a ferramenta (IDE - Integrated Development Environment) CodeBlocks:
  1. Um projeto utilizando o paradigma imperativo, ou estruturado: foi utilizado apenas um arquivo (main.c) para codificar a solução
  2. Dois projetos que utilizam modelagem orientada a objetos: foi criado um arquivo para cada classe e mais um arquivo para a função main (main.cpp). Estas soluções poderiam ter sido escritas utilizando-se outras linguagens de programação orientadas a objetos tais como Java ou C# - o que importa aqui é o paradigma, a forma de se modelar o problema em um código-fonte.
     Observe e compare ambas as soluções e entenda as principais diferenças e características de cada abordagem. Disseque o código-fonte. Entenda tudo que foi feito. Modifique o código-fonte para oferecer outras funcionalidades às classes.

Programando a função main antes

     Às vezes, é melhor pensar na função main() e como seriam instanciados os objetos ou criadas as variáveis que executarão o programa. Por exemplo:
int main() {

   Aluno* jorge = new Aluno();
   jorge->adicionaNotas(4.5, 5.0; 9.0);
   Aluno* joao = new Aluno("Joao");
   joao->adicionaNotas(6.0);
   joao->adicionaNotas(8.0);
   joao->adicionaNotas(4.0);
   Aluno* jonas= new Aluno("Jonas", 5.5, 6.5, 7.5);
   jonas->setFaltas(12);

   Turma* turma128 = new Turma("Turma 128");
   turma128->adicionaAluno(jorge);
   turma128->adicionaAluno(joao);
   turma128->adicionaAluno(jonas);

   float media = turma128->calculaMedia();
   cout << "Media da turma: " << media << endl;

   delete jorge;
   delete joao;
   delete jonas;   // realizar estas chamadas *apenas* 
                   //    se o método destrutor de turma 
                   //    não chamar o delete de alunos
   delete turma;
   return 0;
}
     O interessante desta abordagem é que ela auxilia a criar os métodos das classes necessários para o projeto, por exemplo, já é possível saber os construtores das classes Aluno e Turma, os métodos existentes na classe Turma (void adicionaAluno(Aluno* al);), alguns métodos presentes na classe Aluno (como void adicionaNota(float nota);, void adicionaNota(float* nota); e void setFaltas(int num);) e o método que retorna a média dos alunos da turma (float calculaMedia();). O mesmo procedimento é possível para o paradigma funcional. Claro que evidentemente ainda faltam diversos outros métodos, sendo esta apenas uma alternativa de programação.

Programando de forma mais geral

     O presente projeto definiu que seriam utilizadas apenas 3 notas para 30 alunos, com percentual de presenças igual a 75% e média 7,0. Entretanto, o professor pode solicitar que deseja realizar quatro avaliações ou cinco (ou mais) para 10 ou 50 alunos (validar que estes números encontram-se em limites razoáveis e possíveis). O professor pode também desejar que a média de uma turma seja definida em 5,0 ou 7,5. Também, para diferentes turmas, o percentual de faltas permitido pode ser 50% ou 90% (não permitir valores abaixo de 0% e acima de 100%). Ainda, o professor comunicou que alguns alunos faltam às provas (conforme o total de provas existentes), ou seja, suas médias devem ser computadas apenas para as avaliações que estavam presentes. Para implementar estes novos requisitos, quais alterações nas estruturas de dados e nos algoritmos devem ser implementadas para resolver estes problemas e possibilitar estas novas funcionalidades?

Dados

     Os dados a seguir mostram três projetos construídos a partir da problemática acima. Faça o download dos seguintes arquivos:
  1. Projeto implementado com paradigma imperativo na Linguagem C
  2. Projeto implementado com paradigma orientado a objetos na Linguagem C++, implementado com valores constantes para o total dos alunos, frequências permitidas, etc
  3. Projeto implementado com paradigma orientado a objetos na Linguagem C++, implementado com valores variáveis para os totais de alunos nas turmas, entre outras características gerais
Questões interessantes deste projeto
  1. Alguns alunos fazem todas as provas, outros fazem apenas algumas. Deve ser possível fazer a média apenas das provas que foram feitas pelos alunos e saber quantas provas ele faltou
  2. Ás vezes os alunos perguntam: "Professor, quantas faltas ainda posso ter para não reprovar por faltas?". Deve ser possível mostrar um relatório contendo o total de encontros e, para cada aluno, o total de faltas permitidas conforme as regras (o nível de frequências permitidas)
  3. Deve ser possível também, dada (n-1) notas dos alunos, indicar quanto é necessário que eles tirem para passar por média e dado que suas presenças estão dentro das regras de frequências permitidas
  4. Os alunos, além das provas, possuem notas de trabalhos realizados ao longo da disciplina. Deve ser possível configurar o total de trabalhos
  5. O professor pode decidir usar pesos para cada avaliação (de prova e de trabalho) e calcular a média final dados estes pesos para cada avaliação
  6. O professor pode querer ver as médias das provas e a média dos trabalhos
  7. Deve ser possível saber o melhor e o pior aluno da turma, ou seja, o aluno com maior média com menor número de faltas e o aluno com a menor média e maior número de faltas (nesta ordem de preferência - caso empatem na melhor ou pior nota, deve ser olhado as faltas, caso empatem novamente, retorna-se o aluno com mais notas abaixo da média, caso ainda empatem, retorna-se o aluno em ordem alfabética)
  8. Podem existir provas de recuperação para os alunos que faltaram a alguma prova (só podem recuperar as provas que faltaram)
  9. Implemente os vetores de alunos e de notas utilizando a classe da STL vector (mantenha o uso de ponteiros para alunos)
  10. Acrescente outros atributos (características) tais como: data de nascimento (string), número de matrícula (string), valor booleano indicando se é um bolsista de iniciação científica e filiação (nome do pai e nome da mãe - em uma classe separada). A seguir, faça métodos para retornar e configurar estes atributos, calcular a diferença de dias existente entre hoje e a data de nascimento de cada aluno da turma e um relatório contendo todos os dados de todos os alunos (de forma visualmente atraente)
  11. Implemente no aluno um índice que guarda sua vontade de aprender, variando de 0 até 1. Este índice, afeta suas notas de prova, sendo decrescidas conforme o índice em percentual, por exemplo, um aluno com índice de 0,10 este aluno teria suas notas (todas) decrescidas em 10% e assim sucessivamente. Mostre as notas de cada aluno e a média da turma antes e depois de aplicar o índice nas notas dos alunos
  12. Implemente que o índice de cada aluno é um valor sorteado entre 0 e 1 (utilize srand() e rand())
  13. Carregue um arquivo com os alunos chamado alunos.txt e salve o relatório completo (com tudo) em um arquivo chamado resultados.txt
  14. Implemente a criação de alunos de forma aleatória para todos os atributos (inclusive os nomes e filiação)

Nenhum comentário:

Postar um comentário