Diferenças

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

--- inf05016:2013-2-trabalhos [2013/09/23 08:42]
marcus [Entregas]
+++ 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 270: / Linha 270: @@
 Os casos de teste, as convenções e o código para verificação são idênticos com o trabalho anterior.
+==== Trabalho 4 (Emparelhamentos) ====
+Entrega: 14/10/2013
+=== Objetivos ===
+  * 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). Em particular: estudar a variação de n e m independentemente e verificar as complexidades O(sqrt(n)) e O(m).
+=== Casos de teste ===
+  * Gerar grafos bi-partidos randômicas com probabilidade de uma aresta 0 <= p <= 1.
+=== Convenções ===
+  * As implementações do algoritmo devem aceitar um grafo bi-partido não-direcionado no formato [[http://prolland.free.fr/works/research/dsat/dimacs.html|DIMACS]] na entrada padrão (stdin) e imprimir a cardinalidade de um emparelhamento máximo na saída padrão (stdout).
+=== Códigos disponíveis ===
+  * Gerador de casos de teste no formato DIMACS + verificação.
+  * Para compilar: Usar C++ e Boost.
+<code c++>
+#include <iostream>
+#include <cassert>
+using namespace std;
+#include <boost/graph/adjacency_list.hpp>
+#include <boost/graph/max_cardinality_matching.hpp>
+using namespace boost;
+// graph element descriptors
+typedef adjacency_list_traits<vecS,vecS,undirectedS>::vertex_descriptor Node;
+typedef adjacency_list_traits<vecS,vecS,undirectedS>::edge_descriptor Edge;
+// information stored in vertices
+struct VertexInformation {
+  Node mate; // partner or graph_traits<Graph>::null_vertex()
+};
+// information stored in edges
+struct EdgeInformation {};
+// graph is an adjacency list represented by vectors
+typedef adjacency_list<vecS,vecS,undirectedS,VertexInformation,EdgeInformation> Graph;
+int main(int argc, char *argv[]) {
+  assert(argc == 3);
+  unsigned n = atoi(argv[1]);
+  double p = atof(argv[2]);
+  srand48(time(0));
+  // (1) generate random bi-partite graph
+  Graph g;
+  for(unsigned i=0; i<2*n; i++)
+    add_vertex(g);
+  for(unsigned i=0; i<n; i++)
+    for(unsigned j=n; j<2*n; j++)
+      if (drand48() < p) {
+        Edge e = add_edge(i,j,g).first;
+      }
+  // (2) get maximum matching
+  edmonds_maximum_cardinality_matching(g, get(&VertexInformation::mate,g));
+  unsigned card = 0;
+  graph_traits<Graph>::vertex_iterator vb, ve;
+  for ( tie(vb, ve)=vertices(g); vb != ve; vb++)
+    if (g[*vb].mate != graph_traits<Graph>::null_vertex())
+      card++;
+  //cout << "The cardinality of a maximum matching is " << card/2 << "." << endl;
+  // (3) print out in DIMACS format
+  cout << "c Bi-partite graph" << endl << endl;
+  cout << "p edge " << num_vertices(g) << " " << num_edges(g) << endl;
+  graph_traits<Graph>::edge_iterator eb, ee;
+  for ( tie(eb, ee)=edges(g); eb != ee; eb++)
+    cout << "e " << source(*eb,g)+1 << " " << target(*eb, g)+1 << endl;
+}
+</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