Projeto Projeto de Algoritmos

  • Published on
    12-Dec-2015

  • View
    3

  • Download
    1

DESCRIPTION

Proposta de Projeto para a disciplina

Transcript

  • Universidade Federal de Viosa UFVCampus de Rio Paranaba

    SIN 213 Projeto de Algoritmos / 2013.02 Turma 01Professor: Tcito Trindade de Arajo Tiburtino Neves

    Projeto Final (20 pontos)

    Data de entrega: 14/02/2013

    Especificaes: O trabalho INDIVIDUAL. Trabalhos copiados sero penalizados com nota zero. Para certificar que seu cdigo est correto teste em compiladores do Windows e do Linux. Enviar o cdigo-fonte devidamente comentado, um relatrio em PDF (obrigatrio) e osexecutveis em um arquivo compactado via PVAnet.

    Descrio:

    Parte 1:

    Criar um programa que gera arquivos de texto com as seguintes propriedades:

    O programa deve ser executado via linha de comando da seguinte forma: C:\> instancia

    instancia : nome do programa

    : nome do arquivo em que a instncia ser armazenada.

    : define a disposio dos nmeros no arquivo. Pode ser:

    r : Randmico c : Crescente d : Decrescente

    : um nmero inteiro e define o tamanho da instncia do problema.

    A primeira linha do arquivo contm o nmero total de valores da instncia. Cada uma das demais linhas armazena um dos valores da instncia. Exemplo: C\> instancia prob1.txt r 4 gera o seguinte arquivo:

    465401002

    1

  • Parte 2:

    O trabalho consiste em codificar e testar quatro algoritmos de ordenao de sua escolha.Os algoritmos devero ordenar vetores de nmero inteiros aleatrios.

    Deve-se armazenar o tempo gasto para ordenar os dados em cada teste. Ao final de cadabateria de teste para uma determinada dimenso, calcule a mdia e a varincia para cadamtodo de ordenao. Salve todos os dados em arquivos de texto. As dimenses que devemser usadas no trabalho so: 1:000, 5:000, 10:000, 20:000, 50:000, 100:000 e 1:000:000. O nmero detestes (experimentos) para cada dimenso 30.

    Quando um teste for realizado feche todas as outras aplicaes possveis do sistema opera-cional1. Isto diminui a influencia de fatores externos no experimento e facilita o entendimentodos resultados.

    Importante: a contagem do tempo no deve incluir a leitura e gravao dos valores emarquivos.

    Relatrio:

    Construa o relatrio contendo uma capa com a identificao do trabalho, uma seo des-crevendo o que o problema a ser resolvido, uma seo descrevendo os experimentos realiza-dos, uma seo descrevendo e analisando os resultados obtidos utilizando tabelas e grficos,e uma seo concluindo o trabalho.

    Seguir rigorosamente o formato da SBC. Explicar o contexto do trabalho, motivo e contribuies do trabalho. Explicar e analisar teoricamente (Funes de complexidade, notao til, Big-Oh, Big-Theta e Big-Omega) dos mtodos escolhidos.

    Expor os resultados dos testes empricos. Comparar o algoritmo selecionado, teoricamente e empiricamente, com os algoritmosestudados em aula.

    Um pequeno manual de como utilizar os programas que vocs desenvolveram. Incluir as referncias bibliogrficas consultadas para a realizao do trabalho.

    Livros, artigos, pginas da internet, etc.

    No mnimo trs referncias que no sejam pgina da internet.

    1Principalmente aquelas que demandam muito processamento, como navegadores, editores, players, etc.

    2