===== Status ===== ^ Nome ^ T1 ^ T2 ^ T3 ^ T4 ^ T5 ^ | Carlos | ✅📝 | ✅📝 | ✅📝 | ✅📝 | ✅📝 | | Diego | ✅📝 | ✅📝 | ✅📝 | ✅📝 | ✅📝 | | Eduardo | ✅📝 | ✅📝 | ✅📝 | ✅📝 | ✅📝 | | Gabriel | ✅📝 | ✅📝 | ✅📝 | | | | Guilherme | ✅📝 | ✅(C) | ✅📝 | ✅📝 | ✅📝 | | Gustavo | ✅📝 | ✅📝 | ✅📝 | ✅📝 | ✅📝 | | Henrique | ✅📝 | | ✅📝 | ✅. | ✅📝 | | João | ✅📝 | | ✅📝 | ✅📝 | ✅📝 | | Leonardo | ✅📝 | ✅📝 | ✅📝 | ✅📝 | ✅📝 | | Lucas | ✅📝 | ✅📝 | ✅📝 | ✅📝 | ✅📝 | | Matheus | ✅📝 | ✅📝 | ✅📝 | ✅📝 | ✅📝 | | Maximus | ✅📝 | ✅📝 | ✅📝 | ✅📝 | | | Miguel | | | | | ✅📝 | | Nicolas | ✅📝 | ✅📝 | ✅📝 | ✅📝 | ✅📝 | ✅: recebido. 📝 : avaliado. 🧠 : intenção. ==== Entregáveis (todos trabalhos) ==== * Um relatorio explicando a) possíveis detalhes relevantes da implementação, b) o ambiente de teste, c) o resultado dos experimentos, e d) uma análise dos resultados * O código fonte da implementação * Arquivos CSV com todos dados experimentais ===== Trabalho 1 (Heaps k-ários e algoritmo de Dijkstra) ===== Entrega: 26 de março 2024. === Objetivos === * Implementar um heap k-ário. * Implementar o algoritmo de Dijkstra usando o heap implementado. * Determinar o valor de k tal que o algoritmo de Dijkstra com um heap k-ário tem o melhor desempenho. * Comparar a complexidade teórica pessimista com a complexidade real. Em particular verificar que a complexidade real respeita o limite teórico. * Avaliar o escalonamento do algoritmo Dijkstra. === Casos de teste === * Verificação da complexidade do Dijkstra: usar o gerador de casos de testes abaixo. * Verificação do escalonamento: o caso de teste é o rede de trânsito de New York e dos EUA (distance), que pode ser baixado na [[http://www.dis.uniroma1.it/~challenge9/download.shtml|página do DIMACS challenge]]. * Para testar em geral: Gerar um número suficiente (>30) de pares aleatórias de vértices origem e destino e medir o tempo de execução e o número de operações "insert", "deletemin" e "decreasekey". * Exemplo de um {{:inf05016:testplan20241.pdf|plano de teste}}. === Observações === * Como o grafo possui 23,947,347 vértices é necessário usar uma representação esparsa. Uma matriz de adjacência, em particular, não serve. === Convenções === * As implementações do algoritmo de Dijkstra devem aceitar um grafo no formato da DIMACS challenge na entrada padrão (stdin), os índices de dois vértices origem e destino na linha de comando e imprimir o valor do caminho mais curto na saída padrão (stdout). Caso não existo caminho entre os dois vértices imprimir "inf". Exemplo (em UNIX) > ./dijkstra 1 2 < NY.gr 803 === Materiais === * {{https://github.com/mrpritt/Caminho_Mais_Curto|Repositório com alguns códigos de suporte}}. ===== Trabalho 2 (Fluxo s-t máximo) ===== Entrega: 23 de abril de 2025. === Objetivos === * Implementar a família de algoritmos do tipo Ford-Fulkerson para encontrar o fluxo máximo s-t. - Estratégias de encontrar caminhos: maior gargalo (fattest path), caminho mais curto (BFS), DFS randomizado * Verificar a complexidade do algoritmo experimentalmente em termos - Número de iterações. - Número de operações (i.e.~número de vértices e arcos "tocados"). - Tempo. * Analisar a deficiência das iterações e do custo por iteração com a complexidade pessimista. === Casos de teste === * Um gerador de casos de teste em formato DIMACS em C é disponível {{https://github.com/mrpritt/Fluxo_Maximo|aqui}}. * Exemplo de um {{:inf05016:testplan-flows20251.pdf|plano de teste}}. === Convenções === * As implementações do algoritmo devem aceitar uma instância no formato {{http://lpsolve.sourceforge.net/5.5/DIMACS_maxf.htm|DIMACS}} na entrada padrão (stdin) e imprimir o valor do fluxo máximo na saída padrão (stdout). ==== Gerador de casos de teste ==== * O {{https://github.com/mrpritt/Fluxo_Maximo|código maxflow.cpp}} calcula o fluxo máximo. Para compilar: Usar C++ e {{http://www.boost.org|Boost}}. * {{https://github.com/mrpritt/Fluxo_Maximo|Repositório com alguns códigos de suporte}}. ===== Trabalho 3 (Vencendo um torneio) ===== Entrega: 7 de maio de 2025. === Objetivos === * Resolver o problema de vencer um torneio via redução para um problema de fluxo (ver Notas de Aula). * Conduzir experimentos que determinam - O tempo em função do número de equipes - a probabilidade de vencer o torneio em função do viés da 1a equipe ganhar e o fração de jogos que já aconteceram. === Casos de teste === * Um gerador de casos de teste C é disponível {{https://github.com/mrpritt/Vencendo_Torneios|aqui}}. === Convenções === * As implementações do algoritmo devem aceitar uma instância no formato do gerador na entrada padrão (stdin) e imprimir "sim" caso é possível vencer, ou "não" caso contrário na saída padrão (stdout). ===== Trabalho 4 (Emparelhamentos) ===== Entrega: 21 de maio de 2025. === Objetivos === * Implementar o algoritmo Húngaro que resolve o problema do emparelhamento de maior peso em grafos bi-partidos ponderados. * Documentar a implementação, em particular as estruturas de dados para a representação do problema. * Conduzir testes, que demonstram que a complexidade do algoritmo é O(n(m+n log n)), usando o algoritmo de Johnson para busca de caminhos aumentantes. === Casos de teste === * Gerar grafos bi-partidos completos com pesos aleatórios escolhidos uniformemente no intervalo [0,n^2]. * Para comparar com emparelhamento perfeito máximo: multiplicar os valores por -1. * Um plano de teste razoável pode conter, por exemplo: i) uma avaliação nível do laço principal, ii) uma avaliação do defeito no nível da busca do caminha M-aumentante, iii) uma avalição da escalonabilidade do algoritmo. === Convenções === * As implementações do algoritmo devem aceitar um grafo bi-partido não-direcionado completo na entrada padrão (stdin) e imprimir (somente!) o valor de um emparelhamento perfeito de peso mínimo na saída padrão (stdout). === Entregáveis === * Um relatorio explicando a) possíveis detalhes relevantes da implementação, b) o ambiente de teste, c) o resultado dos experimentos, e d) uma análise dos resultados. * O código fonte da implementação. * Arquivos csv com todos dados experimentais. === Material auxiliar == * [[https://github.com/mrpritt/epm_bipartido|Gerador de instâncias, casos de teste, e documentação adicional]]. ===== Trabalho 5 (Algoritmos rápidas para o problema da mochila) ===== Entrega: 11/06/2025 === Objetivos === * Implementar o Algoritmo 1 de [[https://epubs.siam.org/doi/10.1137/1.9781611977936.6|He e Xu]]. * Conduzir testes para analisar o desempenho empirico em comparação com a programação dinâmica tradicional do problema da mochila. * Conduzir testes para analisar a probabilidade de sucesso em diferentes instâncias. * Bonus: comparar a probabilidade empírica com a probabilidade obtida pela desigualdade de Hoeffding. === Convenções === * As implementações do algoritmo devem aceitar uma instância da problema da mochila na entrada padrão (stdin) e imprimir (somente!) o valor da melhor solução na saída padrão (stdout). Uma instância é descrito por "n W" na primeira linha, valores p1,...,pn na segunda linha, e pesos w1,...,wn na terceira linha. === Entregáveis === * Um relatorio explicando a) possíveis detalhes relevantes da implementação, b) o ambiente de teste, c) o resultado dos experimentos, e d) uma análise dos resultados. * O código fonte da implementação * Arquivos csv com todos dados experimentais.