Diferenças

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

--- inf05504:2011-2-trabalhos [2011/08/24 15:19]
marcus [Trabalho 1 (Heaps binários)]
+++ inf05504:2011-2-trabalhos [2011/12/13 23:39] (Actual)
marcus [Entregas]
@@ Linha 3: / Linha 3: @@
   * Ver também a página com [[dicas]] gerais.
   * D. S. Johnson: {{http://www.research.att.com/~dsj/papers/experguide.pdf|A Theoretician's Guide to the Experimental Analysis of Algorithms}}
+==== Entregas ====
+Atualizado: 13/12/2011
+^ No. ^ T1 ^ T2 ^ T3 ^ T4 ^ T5 ^
+| 152985 | - | - | - | - | - |
+| 159011 | - | - | - | - | - |
+| 159098 | P | P | P | P | R |
+| 171359 | P | P | P | P | R |
+| 172072 | P | P | P | P | - |
+| 173256 | P | P | P | - | - |
+| 173361 | P | P | P | P | - |
+| 180658 | P | P | P | P | - |
+| 180689 | P | P | - | - | - |
+R = recebido
+P = avaliado e publicado
@@ Linha 108: / Linha 127: @@
 === Objetivos ===
   * Implementar um heap de Fibonacci e verificar a complexidade das operações experimentalmente.
-  * Verificar a complexidade do algoritmo de Dijkstra usando um heap binomial experimentalmente.
+  * Verificar a complexidade do algoritmo de Dijkstra usando um heap de Fibonacci experimentalmente.
   * Comparar as complexidades experimentais dos heaps binários e Fibonacci.
   * Comparar as complexidades experimentais do algoritmo de Dijkstra com os dois heaps.
@@ Linha 117: / Linha 136: @@
 === Convenções ===
     * As implementações do algoritmo de Dijsktra 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".
+==== Trabalho 3 (Fluxo s-t máximo) ====
+Entrega: 26/09/2011
+=== Objetivos ===
+  * Implementar o algoritmo de Ford-Fulkerson com a estratégia do "caminho mais gordo" (fattest path) s-t.
+  * Verificar a complexidade do algoritmo experimentalmente.
+=== Casos de teste ===
+  * Um gerador de casos de teste em formato DIMACS em C é disponível {{http://www.inf.ufrgs.br/~mrpritt/washington.c|aqui}}.
+  * Documentação:
+<code>
+             To use:  cc washington.c -o gengraph
+                      gengraph function arg1 arg2 arg3
+             Command line arguments have the following meanings:
+                      function:           index of desired graph type
+                      arg1, arg2, arg3:   meanings depend on graph type
+                                          (briefly listed below: see code
+                                           comments for more info)
+                 Mesh Graph:          1 rows  cols  maxcapacity
+                 Random Level Graph:  2 rows  cols  maxcapacity
+                 Random 2-Level Graph:3 rows  cols  maxcapacity
+                 Matching Graph:      4 vertices  degree
+                 Square Mesh:         5 side  degree  maxcapacity
+                 Basic Line:          6 rows  cols  degree
+                 Exponential Line:    7 rows  cols  degree
+                 Double Exponential   8 rows  cols  degree
+                 DinicBadCase:        9 vertices
+                      (causes n augmentation phases)
+                 GoldBadCase         10 vertices
+                 Cheryian            11 dim1 dim2  range
+                      (last 2 are bad for goldberg's algorithm)
+</code>
+^ No. ^ Nome ^ Parâmetros ^ Descrição ^ n ^ m ^
+|   1 | Mesh | r,c | Grade, 3 viz. 1 direita | rc+2 | 3r(c-1) |
+|   2 | Random level | r,c | Grade, 3 viz. rand. 1 direita | rc+2 | 3r(c-1) |
+|   3 | Random 2-level | r,c | Grade, 3 viz. rand. 2 direita | rc+2 | 3r(c-1) |
+|   4 | Matching | n,d | Bipart. n-n, d viz. rand. | 2n+2 | n(d+2) |
+|   5 | Square Mesh | d,D | Quadr. mesh dxd, grau D | d*d+2 | (d-1)dD+2d |
+|   6 | BasicLine | n,m,D | Linha, grau D| nm+2 | nmD+2m |
+|   7 | ExpLine | n,m,D | Linha, grau D | nm+2 | nmD+2m |
+|   8 | DExpLine | n,m,D | Linha, grau D | nm+2 | nmD+2m |
+|   9 | DinicBad | n | Linha | n | 2n-3|
+|  10 | GoldBad | n | | 3n+3 | 4n+1 |
+=== 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).
+=== Verificação  ===
+  * O seguinte código determina o fluxo máximo. Para compilar: Usar C++ e {{http://www.boost.org|Boost}}.
+<code c++>
+/**
+ * \file maxflow.cpp
+ *   \author Marcus Ritt <mrpritt@inf.ufrgs.br>
+ *   \version $Id: emacs 2872 2009-01-31 01:46:50Z ritt $
+ *   \date Time-stamp: <2009-03-23 17:52:25 ritt>
+ *
+ * Read a maximum flow problem in DIMACS format and output the maximum flow.
+ *
+ */
+#include <iostream>
+#include <cstring>
+using namespace std;
+#include <boost/graph/adjacency_list.hpp>
+#include <boost/graph/read_dimacs.hpp>
+#include <boost/graph/edmunds_karp_max_flow.hpp>
+using namespace boost;
+// a directed graph with reverse edges
+struct VertexInformation {};
+struct EdgeInformation;
+typedef adjacency_list<vecS,vecS,directedS,VertexInformation,EdgeInformation> DiGraph;
+typedef graph_traits<DiGraph>::edge_descriptor Edge;
+typedef graph_traits<DiGraph>::vertex_descriptor DiNode;
+typedef unsigned Capacity;
+struct EdgeInformation {
+  Capacity edge_capacity;
+  Capacity edge_residual_capacity;
+  Edge reverse_edge;
+};
+int main(int argc, char *argv[]) {
+  // (0) read graph
+  DiGraph g;
+  DiNode s,t;
+  read_dimacs_max_flow(g,
+                       get(&EdgeInformation::edge_capacity,g),
+                       get(&EdgeInformation::reverse_edge,g),
+                       s, t);
+  // (1) determine maximum flow
+  cout << edmonds_karp_max_flow(g, s, t,
+                                capacity_map(get(&EdgeInformation::edge_capacity,g)).
+                                residual_capacity_map(get(&EdgeInformation::edge_residual_capacity,g)).
+                                reverse_edge_map(get(&EdgeInformation::reverse_edge,g))) << endl;
+}
+</code>
+==== Trabalho 4 (Segmentação de imagens) ====
+Entrega: 10/10/2011
+=== Objetivos ===
+  * Implementar um algoritmo de segmentação de imagens como vista em aula.
+  * Usar a própria implementação do fluxo máximo na solução.
+  * Segmentar uma imagem em pele/não-pele com pesos de separação diferentes.
+=== Casos de teste ===
+  * O caso de teste é uma imagem de si mesmo.
+=== Convenções ===
+  * As implementações do algoritmo devem aceitar uma imagem no formata PPM plain na entrada padrão (stdin) e imprimir uma imagem no mesmo formato (com todos pixels não-pelo em preto) na saída padrão (stdout).
+=== Códigos disponíveis ===
+  * Ler uma imagem PPM plain
+<code c++>
+// image data structure
+enum { R = 0, G, B };
+typedef unsigned short Color;
+typedef multi_array<Color,3> Image;
+// read an image im PPM (plain) format
+void read_ppm(Image& im, istream& in) {
+  unsigned w,h,maxcolor;
+  string magic;
+  in >> magic >> w >> h >> maxcolor;
+  assert(magic == "P3");
+  im.resize(extents[h][w][3]);
+  for(unsigned i=0; i<h; i++)
+    for(unsigned j=0; j<w; j++)
+      in >> im[i][j][R] >> im[i][j][G] >> im[i][j][B];
+}
+</code>
+  * Imprimir uma imagem PPM plain
+<code c++>
+  cout << "P3 " << w << " " << h << " 255 " << endl;
+  for(unsigned i=0; i<h; i++) {
+    for(unsigned j=0; j<w; j++)
+      cout << im[i][j][R] << " " << im[i][j][G] << " " << im[i][j][B] << " ";
+      cout << endl;
+  }
+</code>
+  * Converter qualquer imagem para PPM plain (usando {{http://www.imagemagick.org|Image Magick}})
+<code>
+  convert -compress none myimage.ext myimage.ppm
+</code>
+  * Determinar a probabilidade de pele ou não-pele (para obter valores inteiros multiplicar com p.ex. 10.000.000.000)
+<code c++>
+// mixture of Gaussians, according to Jones, Regh
+const unsigned nG = 16;
+const unsigned nV = 7;
+double skin[nG][nV] = {
+ { 73.53, 29.94, 17.76,  765.40, 121.44, 112.80, 0.0294 },
+ { 249.71, 233.94, 217.49,  39.94, 154.44, 396.05, 0.0331 },
+ { 161.68, 116.25, 96.95,  291.03, 60.48, 162.85, 0.0654 },
+ { 186.07, 136.62, 114.40,  274.95, 64.60, 198.27, 0.0756 },
+ { 189.26, 98.37, 51.18,  633.18, 222.40, 250.69, 0.0554 },
+ { 247.00, 152.20, 90.84,  65.23, 691.53, 609.92, 0.0314 },
+ { 150.10, 72.66, 37.76,  408.63, 200.77, 257.57, 0.0454 },
+ { 206.85, 171.09, 156.34,  530.08, 155.08, 572.79, 0.0469 },
+ { 212.78, 152.82, 120.04,  160.57, 84.52, 243.90, 0.0956 },
+ { 234.87, 175.43, 138.94,  163.80, 121.57, 279.22, 0.0763 },
+ { 151.19, 97.74, 74.59,  425.40, 73.56, 175.11, 0.1100 },
+ { 120.52, 77.55, 59.82,  330.45, 70.34, 151.82, 0.0676 },
+ { 192.20, 119.62, 82.32,  152.76, 92.14, 259.15, 0.0755 },
+ { 214.29, 136.08, 87.24,  204.90, 140.17, 270.19, 0.0500 },
+ { 99.57, 54.33, 38.06,  448.13, 90.18, 151.29, 0.0667 },
+ { 238.88, 203.08, 176.91,  178.38, 156.27, 404.99, 0.0749 }
+};
+double noskin[nG][nV] = {
+ { 254.37, 254.41, 253.82,  2.77, 2.81, 5.46, 0.0637 },
+ { 9.39, 8.09, 8.52,  46.84, 33.59, 32.48, 0.0516 },
+ { 96.57, 96.95, 91.53,  280.69, 156.79, 436.58, 0.0864 },
+ { 160.44, 162.49, 159.06,  355.98, 115.89, 591.24, 0.0636 },
+ { 74.98, 63.23, 46.33,  414.84, 245.95, 361.27, 0.0747 },
+ { 121.83, 60.88, 18.31,  2502.24, 1383.53, 237.18, 0.0365 },
+ { 202.18, 154.88, 91.04,  957.42, 1766.94, 1582.52, 0.0349 },
+ { 193.06, 201.93, 206.55,  562.88, 190.23, 447.28, 0.0649 },
+ { 51.88, 57.14, 61.55,  344.11, 191.77, 433.40, 0.0656 },
+ { 30.88, 26.84, 25.32,  222.07, 118.65, 182.41, 0.1189 },
+ { 44.97, 85.96, 131.95,  651.32, 840.52, 963.67, 0.0362 },
+ { 236.02, 236.27, 230.70,  225.03, 117.29, 331.95, 0.0849 },
+ { 207.86, 191.20, 164.12,  494.04, 237.69, 533.52, 0.0368 },
+ { 99.83, 148.11, 188.17,  955.88, 654.95, 916.70, 0.0389 },
+ { 135.06, 131.92, 123.10,  350.35, 130.30, 388.43, 0.0943 },
+ { 135.96, 103.89, 66.88,  806.44, 642.20, 350.36, 0.0477 }
+};
+double skin_value(Color R, Color G, Color B) {
+  double r = 0;
+  for(unsigned i=0; i<nG; i++) {
+    double t;
+    t = pow(double(R)-skin[i][0],2)/skin[i][3] + pow(double(G)-skin[i][1],2)/skin[i][4] + pow(double(B)-skin[i][2],2)/skin[i][5];
+    t = skin[i][6]*exp(-t/2) / (pow(2*M_PI,1.5) * sqrt(skin[i][3]*skin[i][4]*skin[i][5]));
+    r += t;
+  }
+  return r;
+}
+double noskin_value(Color R, Color G, Color B) {
+  double r = 0;
+  for(unsigned i=0; i<nG; i++) {
+    double t;
+    t = pow(double(R)-noskin[i][0],2)/noskin[i][3] + pow(double(G)-noskin[i][1],2)/noskin[i][4] + pow(double(B)-noskin[i][2],2)/noskin[i][5];
+    t = noskin[i][6]*exp(-t/2) / (pow(2*M_PI,1.5) * sqrt(noskin[i][3]*noskin[i][4]*noskin[i][5]));
+    r += t;
+  }
+  return r;
+}
+</code>
+==== Trabalho 5 (Sequenciamento de tarefas) ====
+Entrega: 12/12/2011
+=== Objetivos ===
+  * Resolver o problema P||C_max com algoritmos de aproximação.
+  * Implementar o sequenciamento em lista (2-aproximação)
+  * Implementar o sequenciamento em lista em ordem não-crescente (4/3-aproximação)
+  * Implementar o esquema de aproximação em tempo polinomial
+  * Comparar a qualidade dos algoritmos com a solução ótima
+  * Compara o tempo de execução dos algoritmos com os limites teóricos e entre si.
+=== Casos de teste ===
+  * Disponíveis em [[http://www.or.deis.unibo.it/research_pages/ORinstances/PCmax.htm]]
+=== Convenções ===
+  * As implementações do algoritmo devem aceitar uma instância na entrada padrão (stdin) e o tempo de término obtido na saída padrão (stdout).
+  * Para o esquema de aproximação, o primeiro argumento na linha de comando deve ser o parâmetro de qualidade epsilon.

Marcus Ritt

Ferramentas de Utilizador

Ferramentas de Site

Diferenças

Ferramentas de Página