COMUM AREA_Analise de Algoritmos_APS

Prévia do material em texto

ATIVIDADE PRÁTICA SUPERVISIONADA Implantação 20181 
ANÁLISE DE ALGORITMOS 
 
 
OBJETIVOS DE APRENDIZAGEM COMPETÊNCIAS RELACIONADAS 
1. Calcular a complexidade dos algoritmos e das funções através dos métodos 
de substituição, árvore de recursão e teorema mestre. 
2. Analisar a eficiência dos algoritmos através da sua complexidade. 
3. Determinar qual algoritmo é mais eficiente para uma determinada classe de 
problemas. 
III 
V 
VII 
VIII 
IX 
XVIII 
 
 
 
 
ATIVIDADES A SEREM DESENVOLVIDAS 
As Atividades Práticas Supervisionadas - APS têm deu detalhamento publicado no ambiente virtual de aprendizagem (Blackboard) 
da disciplina. São publicadas na primeira quinzena de aulas e devem ser realizadas pelos estudantes até o limite do prazo da N1, 
em conformidade com o calendário acadêmico. 
As APS devem ser realizadas pelos estudantes no próprio ambiente virtual de aprendizagem (Blackboard) ou ter seu upload 
realizado lá, onde também serão corrigidas pelo docente, ficando registradas em sua integralidade. 
 
 
(i) Ler a seção do livro “TAMASSIA, Roberto; GOODRICH, Michael T., Estruturas de Dados e Algoritmos em Java [recurso 
eletrônico, Minha Biblioteca]. Porto Alegre: Grupo A, 2011.”, que explica o funcionamento do Selection Sort. Você 
deverá mostrar detalhadamente o cálculo da sua complexidade para o melhor e para o pior caso, além de mostrar a 
quantidade de vezes que cada linha de código é executada. 
(ii) Ler o site em inglês https://www.programiz.com/dsa/heap-sort, que explica o funcionamento do Heap Sort. Você 
deverá, além de mostrar detalhadamente o cálculo da sua complexidade para o melhor e para o pior caso, 
implementar o algoritmo e fazer testes, medindo o tempo de execução, para uma entrada com 20000 elementos. Os 
testes deverão mostrar o tempo de execução para o melhor e para o pior caso do algoritmo. 
 
 
AVALIAÇÃO 
A avaliação das APS será baseada em um padrão de correção conhecido como rubrica, que confere transparência às expectativas 
em relação à performance do estudante. São esses padrões que o professor utilizará ao corrigir sua APS (peso 1) que, é um dos 
instrumentos avaliativos que compõem a N2. 
 
RUBRICA DE AVALIAÇÃO 
 
 
Critérios 
avaliados 
0 - 3 4-5 6-7 8-9 10 
1
. 
 
Ex
p
lic
aç
ão
 d
o
 
fu
n
ci
o
n
am
en
to
 d
o
 
al
go
ri
tm
o
 (
P
es
o
 1
) 
Nenhum algoritmo 
foi explicado. 
Explicou apenas um 
algoritmo de maneira 
parcialmente correta. 
Explicou os dois 
algoritmos de 
maneira 
parcialmente correta. 
Explicou um 
algoritmo de maneira 
correta e o outro 
algoritmo está 
parcialmente correto. 
Explicou os dois 
algoritmos 
corretamente. 
2
. C
ál
cu
lo
 d
a 
co
m
p
le
xi
d
ad
e 
d
o
 a
lg
o
ri
tm
o
 (
P
es
o
 3
) 
Não calculou a 
complexidade dos 
algoritmos. 
Apenas o cálculo do 
complexidade do 
melhor ou do pior 
caso de um algoritmo 
está correto. 
O cálculo da 
complexidade do 
melhor e do pior caso 
de um algoritmo está 
correto. O cálculo da 
complexidade do 
outro algoritmo está 
incorreto. 
Falta calcular 
corretamente 
somente a 
complexidade do 
melhor ou do pior 
caso de um 
algoritmo. O restante 
está correto. 
O cálculo da 
complexidade dos 
dois algoritmos 
está correto. 
https://www.programiz.com/dsa/heap-sort
3
. I
m
p
le
m
en
ta
çã
o
 e
 t
es
te
s 
d
o
 
al
go
ri
tm
o
 (
P
es
o
 2
) 
– 
so
m
en
te
 p
ar
a 
a 
o
p
çã
o
 ii
 
Os algoritmos não 
foram 
implementados. 
Os algoritmos estão 
implementados de 
maneira 
parcialmente correta. 
Os testes não foram 
realizados. 
Os algoritmos estão 
implementados 
corretamente. Os 
testes foram 
realizados, mas sem 
mostrar o tempo de 
processamento para 
as entradas do pior e 
do melhor caso dos 
dois algoritmos. 
Os algoritmos estão 
implementados 
corretamente. Os 
testes foram 
realizados, mas para 
um ou dois casos de 
teste, os valores ou o 
tempo de 
processamento estão 
errados. 
Os algoritmos 
estão 
implementados 
corretamente. Os 
testes foram 
realizados de 
maneira correta e 
os tempos de 
processamento 
estão certos.