Diferenças

Esta página mostra as diferenças entre as duas revisões da página.

--- inf05016:2013-2-trabalhos [2013/09/25 10:23]
marcus [Trabalho 3 (Fluxo s-t máximo)]
+++ inf05016:2013-2-trabalhos [2013/12/09 09:36] (Actual)
marcus [Entregas]
@@ Linha 2: / Linha 2: @@
 ==== Entregas ====
-Atualizado: 23/09/2013
+Atualizado: 9/12/2013
+^ Cartão ^ T1 ^ T2 ^ T3 ^ T4 ^ T5 ^ T6 ^
+|  23333  | P | P | P | P | P | P |
+|  106962 | P | P |   | P | P |   |
+|  118775 |   |   |   |   |   |   |
+|  136465 |   |   |   |   |   |   |
+|  143287 | P | P | P | P | P |   |
+|  145608 | P | P | P | P | P |   |
+|  158921 | P | P |   | P | P | P |
+|  159033 | P | P | P | P | P |   |
+|  173897 | P | P | P | P | P | P |
+|  180190 |   |   |   |   |   |   |
+|  191935 | P | P | P | P | P | P |
+|  195836 | P | P | P | P | P |   |
+|  205978 | P | P | P | P |   |   |
+|  208669 | P | P | P | P | P |   |
+|  236521 | P | P | P | P | P | P |
+|  237015 |   |   |   |   |   |   |
-^ Cartão ^ T1 ^ T2 ^ T3 ^
-| 23333  | P | P | R |
-| 106962 | P | P |   |
-| 118775 |   |   |   |
-| 136465 |   |   |   |
-| 143287 | P | P | R |
-| 145608 | P | P | R |
-| 158921 | P | P |   |
-| 159033 | P | P | R |
-| 173897 | P | P | R |
-| 180190 |   |   |   |
-| 191935 | P | P | R |
-| 195836 | P | P | R |
-| 205978 | P | P |   |
-| 208669 | P | P | R |
-| 236521 | P | P | R |
-| 237015 |   |   |   |
 R = recebido
 P = avaliado e publicado
@@ Linha 159: / Linha 159: @@
 === Objetivos ===
   * Implementar o algoritmo de Edmonds-Karp (estratégia do "caminho mais curto" s-t).
-  * Verificar a complexidade do algoritmo experimentalmente e comparar com a complexidade teorica O(m(m+n))=O(m^2n).
+  * Verificar a complexidade do algoritmo experimentalmente e comparar com a complexidade teorica O(mn(m+n))=O(m^2n).
 === Casos de teste ===
@@ Linha 279: / Linha 279: @@
   * Implementar o algoritmo de Hopcroft/Karp que resolve o problema do emparelhamento máximo em grafos bi-partidos.
   * 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(sqrt(n)m).
+  * Conduzir testes, que demonstram que a complexidade do algoritmo é O(sqrt(n)m). Em particular: estudar a variação de n e m independentemente e verificar as complexidades O(sqrt(n)) e O(m).
 === Casos de teste ===
@@ Linha 350: / Linha 350: @@
 </code>
+==== Trabalho 5 (Hashing) ====
+Entrega: 08/11/2013
+=== Objetivos ===
+  * Implementar tabelas hash com endereçamento aberto e com cuco hashing.
+  * Escolher funções hash adequadas.
+  * Conduzir testes, que determinam a complexidade média (amortizada) das operações insert e lookup para diferentes fatores de ocupação.
+  * Comparar o desempenho com i) o acesso simples à memoria e ii) com uma implementação padrão (e.g. unordered_set em C++).
+=== Casos de teste ===
+  * Conjuntos de chaves aleatórias.
+=== Convenções ===
+  * As implementações do algoritmo devem aceitar um arquivo na entrada padrão (stdin) que informa na primeira linha
+<code>
+n m
+</code>
+o número de inserções n e o número de consultas m, seguido por n linhas que contém um número inteiro que
+representa uma chave a inserir e m linhas que contém um número inteiro que representa uma consulta. O algoritmo deve imprimir na saida padrão (stdout) m linhas que contém o resultado dos m lookups: 0 para uma chave que não pertence a tabela hash, e 1 caso contrário.
+==== Trabalho 6 (Teste de primalidade) ====
+Entrega: 04/12/2013
+=== Objetivos ===
+  * Implementar o teste de primalidade de Miller & Rabin
+  * Analisar a complexidade do algoritmo em função de log_2(n) experimentalmente.
+  * Analisar a probabilidade de responder erradamente "sim" experimentalmente.
+  * Observação: o trabalho é opcional (i.e. só contam os cinco melhores trabalhos entregues).
+=== 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 ===
+  * Usa a biblioteca {{http://gmplib.org|GNU MP}} para representar números grandes. Ela tem interfaces para {{http://en.wikipedia.org/wiki/GNU_Multiple_Precision_Arithmetic_Library#Language_bindings|diversas linguagens}} de programação. Um exemplo em C++:
+  <code c++>
+#include <iostream>
+using namespace std;
+#include <gmpxx.h>
+int main(int argc, char *argv[]) {
+  mpz_class a;
+  cin >> a;
+  cout << "O quadrado de " << a << " é " << a*a << endl;
+}
+</code>

Marcus Ritt

Ferramentas de Utilizador

Ferramentas de Site

Diferenças

Ferramentas de Página