TP1 Análise empírica, ALGUEM ME AJUDE

Prévia do material em texto

Credenciada pela Portaria Ministerial no 1.744 de 24/10/2006
 DOU 25/10/2006
Mantida pela Unibalsas Educacional Ltda
.
Trabalho Prático 1 – 1º BIMESTRE 2016.2
CURSO: Sistemas de Informação 
DISCIPLINA: Análise e Complexidade de Algoritmos
PROFESSOR: Me. Bruno Ramon de Almeida e Silva
Assunto: Análise empírica
Objetivo
Um tipo de algoritmo muito usado na resolução de problemas computacionais são os
algoritmos de ordenação, que servem para ordenar/organizar uma lista de números ou palavras
de acordo com a sua necessidade. As linguagens de programação já possuem métodos de
ordenação, mas é fundamental saber como funcionam os algoritmos, pois há casos de problemas
em que o algoritmo de ordenação genérico não resolve, às vezes é necessário modificá-lo.
Os algoritmos de ordenação mais populares são: ordenação por inserção (Insertionsort),
ordenação por seleção (Selectionsort), ordenação por flutuação(Bubblesort), ordenação rápida
(Quicksort) e ordenação por combinação (Mergesort).
O objetivo do trabalho é a implementação de alguns algoritmos de ordenação para análise
empírica de complexidade.
Equipe de desenvolvimento
O trabalho será feito em equipe, de no máximo, 2 componentes.
Atribuição da nota
O trabalho em questão poderá atingir pontuação máxima de 1,0 pontos a somar na AV3. 
Especificação do problema
Realizar um experimento que tem como objetivo verificar o comportamento dos algoritmos
em relação ao tempo (análise empírica).
Os dados de entrada serão três conjuntos de dados:
 Conjunto 1: lista ordenada em ordem crescente
Km 5 da BR 230, Fazenda Malidere 4 – 65800-000 Balsas – MA
PABX 99 3541 2194 - www.unibalsas.edu.br
Credenciada pela Portaria Ministerial no 1.744 de 24/10/2006
 DOU 25/10/2006
Mantida pela Unibalsas Educacional Ltda
.
 Conjunto 2: lista ordenada em ordem decrescente
 Conjunto 3: lista desordenada com números aleatórios
Os três conjuntos de entradas devem ser testados em quatro algoritmos: Insertion Sort,
Selection Sort, Bubble Sort e Quick Sort. O trabalho consiste em implementar os algoritmos na
linguagem Java (preferencialmente) e realizar o teste utilizando o conjunto de entrada acima
mencionado, em instâncias de tamanho 10000 (dez mil) elementos, 100000 (cem mil) e 1000000
(um milhão). Deve-se calcular o tempo gasto por cada algoritmo em cada conjunto de entrada.
A seguir, um resumo dos procedimentos a serem realizados:
 Para cada algoritmo, são submetidas 9 entradas, como segue:
o Lista ordenada em ordem crescente com 10 mil, 100 mil e 1 milhão de elementos
o Lista ordenada em ordem decrescente com 10 mil, 100 mil e 1 milhão de elementos
o Lista desordenada com 10 mil, 100 mil e 1 milhão de elementos
Ao final, devem-se montar tabelas com os valores encontrados no seguinte formato:
Algoritmo: InsertionSort
Qnt. elementos Tipo da entrada Tempo gasto (ms)
10.000 Ordenada ?
10.000 Desordenada ?
10.000 Aleatória ?
100.000 Ordenada ?
100.000 Desordenada ?
100.000 Aleatória ?
1.000.000 Ordenada ?
1.000.000 Desordenada ?
1.000.000 Aleatória ?
Uma tabela para cada algoritmo. Ao todo, serão 4 (quatro) tabelas.
Artefatos de entrega
Km 5 da BR 230, Fazenda Malidere 4 – 65800-000 Balsas – MA
PABX 99 3541 2194 - www.unibalsas.edu.br
Credenciada pela Portaria Ministerial no 1.744 de 24/10/2006
 DOU 25/10/2006
Mantida pela Unibalsas Educacional Ltda
.
 Relatório, cobrindo os pontos requeridos na especificação.
 Código-fonte desenvolvido na linguagem Java (Somente as classes, não o projeto inteiro).
 O código deve estar compactado nos formatos .ZIP ou .RAR
 Entregar via e-mail: brunoramon@unibalsas.edu.br, até as 23:59:59 do dia 22/09/16
 O assunto (título do e-mail) deve estar no formato: [AAC – TP1 – Fulano, Cicrano, etc].
 No corpo do e-mail deve ter obrigatoriamente os nomes dos membros do grupo juntamente
com sua matrícula. 
Observações
 Trabalhos entregues fora do prazo estabelecido serão decrementados na nota pela
metade, a cada dia de atraso. (Nota = Nota/2)
 Embora o trabalho sera desenvolvido em grupo, as notas serão atribuídas individualmente. 
 Por ocasião, o professor está facultado a realizar questionamentos a qualquer um dos
membros sobre o código-fonte da aplicação.
 Caso o título do e-mail não siga o padrão estabelecido, infração de 0,25 pts.
 Não serão aceitas alegações do tipo: “enviei o e-mail, mas não chegou”. Certifique-se de
que o e-mail realmente foi enviado (e recebido) pelo professor.
 Não serão aceitas alegações do tipo: “esqueci de colocar o nome de fulano”.
Km 5 da BR 230, Fazenda Malidere 4 – 65800-000 Balsas – MA
PABX 99 3541 2194 - www.unibalsas.edu.br