A análise comparativa de algoritmos de ordenação desempenha um papel fundamental na ciência da computação e engenharia de software. Algoritmos de ordenação são uma parte essencial do repertório de qualquer programador, e a escolha do algoritmo certo pode afetar drasticamente o desempenho de um programa. Este projeto tem como objetivo explorar e aplicar conceitos de inferência estatística para determinar qual dos algoritmos de ordenação - Bubble Sort, Merge Sort ou Quick Sort - é o mais eficiente em termos de tempo de processamento. Além disso, os alunos terão a oportunidade de aprimorar suas habilidades de programação em C e adquirir experiência em coleta e análise de dados, utilizando Python, Pandas e NumPy.
O objetivo principal deste projeto é realizar uma análise estatística rigorosa para determinar qual dos algoritmos de ordenação é o mais eficaz em uma variedade de cenários. Os objetivos específicos incluem:
- Implementar os algoritmos de ordenação (Bubble Sort, Merge Sort e Quick Sort) em linguagem C.
- Coletar dados de desempenho dos algoritmos para diferentes tamanhos de amostra e perfis de hardware.
- Armazenar os dados coletados em um banco de dados para posterior análise.
- Utilizar técnicas de estatística descritiva para resumir os dados e identificar tendências.
- Realizar testes de hipótese para comparar o desempenho dos algoritmos e determinar se existem diferenças significativas.
- Calcular intervalos de confiança para avaliar a precisão das medições.
- Preparar relatórios e apresentações que descrevem os resultados e conclusões do estudo.
Este projeto proporcionará aos alunos a oportunidade de desenvolver várias competências, incluindo:
- Programação em C: Aprimorar as habilidades de programação em C, implementando os algoritmos de ordenação e coletando dados de desempenho.
- Gerenciamento de Dados: Coletar e armazenar dados em um banco de dados, adquirindo conhecimentos em estruturas de dados e manipulação de dados.
- Estatística: Habilidades em análise estatística, incluindo cálculos de médias, desvios padrão, testes de hipótese e intervalos de confiança.
- Pandas e NumPy em Python: Experiência no uso de bibliotecas Python, como Pandas e NumPy, para análise de dados e cálculos estatísticos.
- Compreensão de Algoritmos: compreender melhor a importância da escolha do algoritmo apropriado em termos de eficiência e desempenho.
- Comunicação e Apresentação: Oportunidade de aprimorar suas habilidades de comunicação, preparando relatórios e apresentando resultados de maneira clara e eficaz.
- Definição do Escopo do Projeto: A equipe deve verificar os tamanhos de amostra a serem considerados e os perfis de hardware que serão testados.
- Implementação dos Algoritmos em C: A equipe deve implementar os algoritmos de ordenação (Bubble Sort, Merge Sort e Quick Sort) em linguagem C. Certifique-se de que os algoritmos estejam funcionando corretamente.
- Coleta de Dados de Desempenho: Execute os algoritmos para diferentes tamanhos de amostra (por exemplo, 100, 1000, 10000 elementos) e registre o tempo de processamento (em microsegundos) para cada execução. Registre informações detalhadas sobre o hardware, incluindo o tipo de processador, quantidade de RAM e sistema operacional.
- Armazenamento dos Dados em um Banco de Dados: Configure um banco de dados para armazenar os dados coletados. Crie tabelas para armazenar os resultados do tempo de processamento e as informações do hardware. Garanta que os registros tenham um identificador único.
- Análise Inicial dos Dados: Utilize a linguagem Python para importar os dados do banco de dados em um DataFrame do Pandas. Realize uma análise inicial dos dados, calculando médias, desvios padrão e outras estatísticas descritivas para cada algoritmo e tamanho de amostra.
- Testes de Hipótese: Realize testes de hipótese para comparar o desempenho dos algoritmos. Registre os resultados dos testes de hipótese.
- Cálculo de Intervalos de Confiança: Calcule intervalos de confiança para os tempos de processamento de cada algoritmo. Isso ajudará a determinar a precisão das medições e permitirá que você faça afirmações sobre a variabilidade dos resultados.
- Preparação de Relatórios e Apresentações: A equipe deve preparar relatórios detalhados que descrevem os resultados, análises estatísticas e conclusões. A equipe deve fazer uma apresentação para compartilhar seus resultados com a turma, explicando suas descobertas.
O projeto será desenvolvido em equipes de até quatro pessoas e deve ser entregue um repositório no github contendo os seguintes itens:
- Um README contendo o contexto do projeto, seu objetivo, um relatório apresentando e discutindo os resultados e os integrantes da equipe.
- Os códigos desenvolvidos em C.
- Os códigos desenvolvidos em Python.
- Os dados do banco de dados.
A apresentação dos resultados será no dia 30/11 durante as aulas Probabilidade Estatística e Banco de Dados.