Universidade Federal do Paraná
Setor de Ciências Exatas / Departamento de Informática – DInf
Algoritmos e Estruturas de Dados II – CI056 / 2o semestre de 2015
Professor: David Menotti
Trabalho Prático 1
Tipos Abstratos de Dados, Alocação Dinâmica &
Noções de Análise de Complexidade de Algoritmos
Polinômios
Avaliação: 10 pontos (10% do total da disciplina)
Data de divulgação: 15/09/2015
Data de entrega: 13/10/2015
Objetivos
Consiste em rever conceitos básicos de programação bem como explorar os conceitos
de Tipos Abstratos de Dados (TADs) e noções de Ordem de Complexidade. Além disso,
serão necessários conhecimentos em Matemática Básica e noções de Cálculo Diferencial
e Integral.
Descrição
Você deverá implementar um TAD TPolinomio para representar polinômios de ordem
n qualquer (n > 0), i.e.,
P (x) = an xn + an−1 xn−1 + an−2 xn−2 + ... + a2 x2 + a1 x1 + a0
(1)
em que an , an−1 , an−2 , ..., a2 , a1 e a0 são os n + 1 coeficientes do polinômio de ordem (ou
grau) n. Considere que a ordem do polinômio será determinada em tempo de execução
(alocação dinâmica). Este TAD deverá armazenar os coeficientes do polinômio e a sua
ordem n e implementar procedimentos (ou funções quando for o caso) para:
1. PCriar – Criar (e ler) um polinômio.
2. PObterValor(P,x) – Obter o valor de P (x) dado um valor qualquer de x.
3. PObterOrdem(P) – Obter a ordem (grau) de P (x), i.e., n.
4. PAdicao(P,Q) – Realizar a soma/adição de dois polinômios P e Q quaisquer. Um
novo polinômio deve ser criado e retornado neste caso.
5. PSubtracao(P,Q) – Realizar a subtração de dois polinômios P e Q quaisquer. Um
novo polinômio deve ser criado e retornado neste caso.
6. PProduto(P,Q) – Realizar o produto de dois polinômios P e Q quaisquer. Um novo
polinômio deve ser criado e retornado neste caso.
1
7. PDivisao(P,Q) – Realizar a divisão do polinômio P por Q (quando Q não for nulo,
i.e., n > 0). Devem ser criados e retornados dois polinômios, um para o resto e
outro para o quociente da divisão. A partir desta função, devem ser criadas duas
funções, uma para calcular o resto e outra para calcular o quociente. A otimização
de código destas três funções será objeto de avaliação em ponto extra.
O TAD deve implementar ainda uma função que calcule os extremos (máximos e/ou
mínimos) locais de P (x) para polinômios de ordem 3 ou inferior (PObterExtremos). Caso
a função calcule também os extremos para polinômios de ordem 4, um ponto extra (1%
do total da disciplina) será atribuído . Caso essa funcionalidade seja implementada e a
função também calcule os extremos para polinômios de ordem 5, um outro ponto extra
será atribuído. Sugere-se desenvolver uma função PDerivar(P).
Os valores extremos deverão ser armazenados em um outro TAD TExtremo que se
comporta como um vetor. Além dos valores e da quantidade de extremos, o TAD deve
ter um campo especial para indicar se cada extremo é de máximo ou de mínimo, ou ainda
se é um ponto de inflexão. Dica: aplicação da derivada segunda.
Implemente os TADs solicitados em arquivos separados do programa principal (sugestão: TPolinomio.c, TPolinomio.h, TExtremo.c, TExtremo.h e main.c). Apresente
sucintamente na documentação a forma usada para compilação de todo o “projeto”. Se
necessário, você pode criar outras funções auxiliares nos TADs.
Uma vez criado os TADs, você deverá também implementar um programa principal
(main) para manipular estes TADS de forma que seja possível avaliar\testar a consistência
das implementações.
O que deve ser entregue
• Código fonte dos programas em C (bem indentado e comentado).
• Documentação do trabalho.
Entre outros detalhes, a documentação deve conter:
1. Introdução: descrição dos problemas a serem resolvidos.
2. Implementação: descrição sobre as implementações. Deve ser detalhada a estrutura de dados utilizada (de preferência com diagramas e/ou figuras ilustrativos), o
funcionamento das principais funções e procedimentos utilizados, o formato de entrada e saída de dados, bem como decisões tomadas relativas aos casos e detalhes de
especificação que porventura estejam omissos no enunciado. Muito importante:
os códigos utilizados nas implementações devem ser inseridos na documentação.
3. Análise de Complexidade: estudo da complexidade de tempo e espaço das funções implementadas e do programa como um todo (notação O).
4. Listagem de testes executados: os testes executados devem ser apresentados,
analisados e discutidos, quando convier.
5. Conclusão: comentários gerais sobre o trabalho e as principais dificuldades encontradas em sua implementação.
2
6. Bibliografia: bibliografia utilizada para o desenvolvimento do trabalho, incluindo
sítio da Internet se for o caso. Uma referência bibliográfica deve ser citada no texto
onde é utilizada.
7. Em LATEX : Caso o trabalho seja elaborado/escrito em LATEX, ganha-se um ponto
extra. Veja modelo de como fazer o trabalho em LATEX:
http://web.inf.ufpr.br/menotti/ci056-2015-2-1/tps/modelo.zip
8. Formato final : mandatoriamente em PDF (http://www.pdf995.com/).
Como deve ser feita a entrega
A entrega DEVE ser feita via Moodle (http://moodle.c3sl.ufpr.br/) na forma
de um único arquivo compactado (.zip, .tar.gz, .tgz, .rar, etc), contendo o código fonte,
arquivos diversos e a documentação. Também deve ser entregue a documentação impressa
na próxima aula teórica após a data de entrega do trabalho.
Comentários Gerais
• Comece a fazer este trabalho logo, enquanto o prazo para terminá-lo está tão longe
quanto jamais poderá estar;
• Clareza, indentação e comentários no programa também serão alvos de avaliação.
• O trabalho é individual (grupo de UM aluno).
• Trabalhos plageados (e FONTE) terão nota zero. Além disso, os infratores terão
a maior nota de testes teóricos levada à zero, como forma de punição e coação ao
plágio acadêmico;
• Trabalhos entregues em atraso serão aceitos, todavia a nota zero será atribuída;
• Evite discussões inócuas com o professor em tentar postergar a data de entrega do
referido trabalho.
3