ementa

Prévia do material em texto

TRABALHO DE ALGORITMOS AVANÇADOS.
� NOTA PARA CONFECÇÃO DO TRABALHO:
Este trabalho é individual deverá ser entregue impreterivelmente até o dia da AV1. Serão 
considerados na avaliação além do conteúdo e respostas aos questionamentos que se 
seguem, a apresentação e a organização do trabalho.
� O trabalho deverá ser composto das seguintes tarefas:
1) INTRODUÇÃO TEÓRICA:
Nesta tarefa o aluno deverá pesquisar e ler sobre Complexidade de algoritmos e fazer com 
suas palavras uma introdução teórica sobre este tema e deverá nesta introdução destacar 
as respostas aos seguintes questionamentos.
a) O que é Complexidade de Algoritmos ?
b) Quais os tipos de complexidade de algoritmos que conhece?
c) Para que serve o estudo da complexidade de algoritmos?
d)Quais os principais classes de complexidades de algoritmos?
2) IMPLEMENTAÇÃO DE ALGORITMOS
Nesta tarefa o aluno deverá implementar e apresentar o código em C++ dos seguintes 
algoritmos:
a) Algoritmo de busca sequencial
b) Algoritmo de busca binária
c) Algoritmo de Ordenação bolha ou Bublesort
d) Algoritmo de Ordenação por Seleção ou SelectionSort
e) Algoritmo de Ordenação MergeSort
f) Algoritmo de Ordenação QuickSort
NOTA PARA IMPLEMENTAÇÃO DOS ALGORITMOS: Todas as implementações deverão ser 
apresentadas em forma de função onde um dos parâmetros de entrada deve ser o vetor a 
ser ordenado.
1
3) ANÁLISE TEÓRICA DAS COMPLEXIDADES DOS ALGORITMOS
Nesta tarefa o aluno deverá apresentar uma análise teórica da complexidade dos algoritmos 
implementados na tarefa 2. Entretanto, para esta tarefa o aluno poderá se valer de 
consultas e pesquisas para apresentação destas análises. Porém o aluno deve apresentar 
um relato comparativo entre os algoritmos que realizam a mesma tarefa sobre sua 
eficiência diante da análise realizada.
4) ANÁLISE PRÁTICA DAS COMPLEXIDADES DOS ALGORITMOS
Nesta tarefa o aluno deverá implementar um programa capaz de realizar medidas de tempo 
de execução das funções implementadas na tarefa 2. E uma vez implementado este 
programa o aluno deverá realizar um experimento onde seja possível a partir da variação do 
número de elementos do vetor levantar o seu comportamento no tempo e construir um 
gráfico mostrando que o comportamento da complexidade dos algoritmos estão de acordo 
com a análise teórica realizada na tarefa 3.
O gráfico deverá ser construído com auxílio do MS-Excel.
5) CONCLUSÃO.
Nesta parte do trabalho o aluno deverá apresentar suas conclusões ou considerações a 
respeito do trabalho realizado.
2