Marcus Ritt

Esta página é apenas de leitura. Pode ver a fonte, mas não alterá-la. Informe-se com o administrador deste Wiki se achar que isto não está correcto.
===== 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.

<html>
<!-- 
===== Trabalho 5 (Teste de primalidade) =====

Entrega: 21/08/2024

=== Objetivos ===

  * Implementar o teste de primalidade de Miller & Rabin.
  * Analisar a complexidade do algoritmo em função de log₂(n) experimentalmente.
  * Analisar a probabilidade de responder erradamente "sim" experimentalmente.

=== Casos de teste ===

  * Números inteiros positivos aleatórios.

=== Convenções ===

  * As implementações do algoritmo devem ler um número decimal com até 1000 dígitos da entrada padrão e imprimir "s" na saída padrão caso o número é considerado primo e "n" caso contrário.

=== Dicas ===

  * Um exemplo trabalhar com números grandes usando a biblioteca [[http://gmplib.org|GNU MP]] é disponível em {{https://github.com/mrpritt/Teste_de_Primalidade|aqui}}.

-->
</html>
Marcus Ritt

Ferramentas de Utilizador

Ferramentas de Site

Ferramentas de Página
