docs/informe_v0.01.rtf

   1 {\rtf1\ansi\ansicpg1252\deff0\deflang3082\deflangfe3082\deftab708{\fonttbl{\f0\froman\fprq2\fcharset0 Times New Roman;}{\f1\fswiss\fprq2\fcharset0 Arial;}{\f2\fnil\fcharset0 CMSSBX10;}{\f3\fswiss\fcharset0 Arial;}{\f4\fmodern\fprq1\fcharset0 Courier New;}}\r
   2 {\colortbl ;\red0\green0\blue255;\red192\green192\blue192;}\r
   3 {\*\generator Msftedit 5.41.15.1507;}\viewkind4\uc1\pard\qc\f0\fs52 Teor\'eda de algoritmos 1 \endash  75.29\par\r
   4 \fs24\par\r
   5 Trabajo Pr\'e1ctico N\'ba: 2\par\r
   6 \pard\par\r
   7 Integrantes:\par\r
   8 \trowd\trgaph70\trleft-70\trbrdrl\brdrs\brdrw10 \trbrdrt\brdrs\brdrw10 \trbrdrr\brdrs\brdrw10 \trbrdrb\brdrs\brdrw10 \trpaddl70\trpaddr70\trpaddfl3\trpaddfr3\r
   9 \clbrdrl\brdrw10\brdrs\clbrdrt\brdrw10\brdrs\clbrdrr\brdrw10\brdrs\clbrdrb\brdrw10\brdrs \cellx2856\clbrdrl\brdrw10\brdrs\clbrdrt\brdrw10\brdrs\clbrdrr\brdrw10\brdrs\clbrdrb\brdrw10\brdrs \cellx5783\clbrdrl\brdrw10\brdrs\clbrdrt\brdrw10\brdrs\clbrdrr\brdrw10\brdrs\clbrdrb\brdrw10\brdrs \cellx8710\pard\intbl Padr\'f3n\cell Nombre y Apellido\cell Email\cell\row\trowd\trgaph70\trleft-70\trbrdrl\brdrs\brdrw10 \trbrdrt\brdrs\brdrw10 \trbrdrr\brdrs\brdrw10 \trbrdrb\brdrs\brdrw10 \trpaddl70\trpaddr70\trpaddfl3\trpaddfr3\r
  10 \clbrdrl\brdrw10\brdrs\clbrdrt\brdrw10\brdrs\clbrdrr\brdrw10\brdrs\clbrdrb\brdrw10\brdrs \cellx2856\clbrdrl\brdrw10\brdrs\clbrdrt\brdrw10\brdrs\clbrdrr\brdrw10\brdrs\clbrdrb\brdrw10\brdrs \cellx5783\clbrdrl\brdrw10\brdrs\clbrdrt\brdrw10\brdrs\clbrdrr\brdrw10\brdrs\clbrdrb\brdrw10\brdrs \cellx8710\pard\intbl\qc 77891\cell\pard\intbl Leandro Lucarella\cell\pard\intbl\qc{\field{\*\fldinst{HYPERLINK "mailto:luca@llucax.hn.org" }}{\fldrslt{\cf1\ul luca@llucax.hn.org}}}\cf0\ulnone\f0\fs24\cell\row\trowd\trgaph70\trleft-70\trbrdrl\brdrs\brdrw10 \trbrdrt\brdrs\brdrw10 \trbrdrr\brdrs\brdrw10 \trbrdrb\brdrs\brdrw10 \trpaddl70\trpaddr70\trpaddfl3\trpaddfr3\r
  11 \clbrdrl\brdrw10\brdrs\clbrdrt\brdrw10\brdrs\clbrdrr\brdrw10\brdrs\clbrdrb\brdrw10\brdrs \cellx2856\clbrdrl\brdrw10\brdrs\clbrdrt\brdrw10\brdrs\clbrdrr\brdrw10\brdrs\clbrdrb\brdrw10\brdrs \cellx5783\clbrdrl\brdrw10\brdrs\clbrdrt\brdrw10\brdrs\clbrdrr\brdrw10\brdrs\clbrdrb\brdrw10\brdrs \cellx8710\pard\intbl\qc 84107\cell\pard\intbl Alberto Bertogli\cell\pard\intbl\qc{\field{\*\fldinst{HYPERLINK "mailto:albertogli@telpin.com.ar" }}{\fldrslt{\cf1\ul albertogli@telpin.com.ar}}}\cf0\ulnone\f0\fs24\cell\row\trowd\trgaph70\trleft-70\trbrdrl\brdrs\brdrw10 \trbrdrt\brdrs\brdrw10 \trbrdrr\brdrs\brdrw10 \trbrdrb\brdrs\brdrw10 \trpaddl70\trpaddr70\trpaddfl3\trpaddfr3\r
  12 \clbrdrl\brdrw10\brdrs\clbrdrt\brdrw10\brdrs\clbrdrr\brdrw10\brdrs\clbrdrb\brdrw10\brdrs \cellx2856\clbrdrl\brdrw10\brdrs\clbrdrt\brdrw10\brdrs\clbrdrr\brdrw10\brdrs\clbrdrb\brdrw10\brdrs \cellx5783\clbrdrl\brdrw10\brdrs\clbrdrt\brdrw10\brdrs\clbrdrr\brdrw10\brdrs\clbrdrb\brdrw10\brdrs \cellx8710\pard\intbl\qc 79872\cell\pard\intbl Ezequiel Mart\'edn Gonz\'e1lez\cell\pard\intbl\qc{\field{\*\fldinst{HYPERLINK "mailto:egbusquin@gmail.com" }}{\fldrslt{\cf1\ul egbusquin@gmail.com}}}\cf0\ulnone\f0\fs24\cell\row\pard\par\r
  13 \par\r
  14 \trowd\trgaph70\trleft-70\trbrdrl\brdrs\brdrw10 \trbrdrt\brdrs\brdrw10 \trbrdrr\brdrs\brdrw10 \trbrdrb\brdrs\brdrw10 \trpaddl70\trpaddr70\trpaddfl3\trpaddfr3\r
  15 \clbrdrl\brdrw10\brdrs\clbrdrt\brdrw10\brdrs\clbrdrr\brdrw10\brdrs\clbrdrb\brdrw10\brdrs \cellx8710\pard\intbl Para uso de la c\'e1tedra\cell\row\trowd\trgaph70\trleft-70\trbrdrl\brdrs\brdrw10 \trbrdrt\brdrs\brdrw10 \trbrdrr\brdrs\brdrw10 \trbrdrb\brdrs\brdrw10 \trpaddl70\trpaddr70\trpaddfl3\trpaddfr3\r
  16 \clbrdrl\brdrw10\brdrs\clbrdrt\brdrw10\brdrs\clbrdrr\brdrw10\brdrs\clbrdrb\brdrw10\brdrs \cellx8710\pard\intbl Primera entrega\cell\row\trowd\trgaph70\trleft-70\trbrdrl\brdrs\brdrw10 \trbrdrt\brdrs\brdrw10 \trbrdrr\brdrs\brdrw10 \trbrdrb\brdrs\brdrw10 \trpaddl70\trpaddr70\trpaddfl3\trpaddfr3\r
  17 \clbrdrl\brdrw10\brdrs\clbrdrt\brdrw10\brdrs\clbrdrr\brdrw10\brdrs\clbrdrb\brdrw10\brdrs \cellx8710\pard\intbl Corrector\cell\row\trowd\trgaph70\trleft-70\trbrdrl\brdrs\brdrw10 \trbrdrt\brdrs\brdrw10 \trbrdrr\brdrs\brdrw10 \trbrdrb\brdrs\brdrw10 \trpaddl70\trpaddr70\trpaddfl3\trpaddfr3\r
  18 \clbrdrl\brdrw10\brdrs\clbrdrt\brdrw10\brdrs\clbrdrr\brdrw10\brdrs\clbrdrb\brdrw10\brdrs \cellx8710\pard\intbl Observaciones\par\r
  19 \par\r
  20 \par\r
  21 \par\r
  22 \par\r
  23 \par\r
  24 \par\r
  25 \par\r
  26 \par\r
  27 \par\r
  28 \par\r
  29 \par\r
  30 \cell\row\trowd\trgaph70\trleft-70\trbrdrl\brdrs\brdrw10 \trbrdrt\brdrs\brdrw10 \trbrdrr\brdrs\brdrw10 \trbrdrb\brdrs\brdrw10 \trpaddl70\trpaddr70\trpaddfl3\trpaddfr3\r
  31 \clbrdrl\brdrw10\brdrs\clbrdrt\brdrw10\brdrs\clbrdrr\brdrw10\brdrs\clbrdrb\brdrw10\brdrs \cellx8710\pard\intbl\cf2\cell\row\trowd\trgaph70\trleft-70\trbrdrl\brdrs\brdrw10 \trbrdrt\brdrs\brdrw10 \trbrdrr\brdrs\brdrw10 \trbrdrb\brdrs\brdrw10 \trpaddl70\trpaddr70\trpaddfl3\trpaddfr3\r
  32 \clbrdrl\brdrw10\brdrs\clbrdrt\brdrw10\brdrs\clbrdrr\brdrw10\brdrs\clbrdrb\brdrw10\brdrs \cellx8710\pard\intbl\cf0 Segunda entrega\cell\row\trowd\trgaph70\trleft-70\trbrdrl\brdrs\brdrw10 \trbrdrt\brdrs\brdrw10 \trbrdrr\brdrs\brdrw10 \trbrdrb\brdrs\brdrw10 \trpaddl70\trpaddr70\trpaddfl3\trpaddfr3\r
  33 \clbrdrl\brdrw10\brdrs\clbrdrt\brdrw10\brdrs\clbrdrr\brdrw10\brdrs\clbrdrb\brdrw10\brdrs \cellx8710\pard\intbl Corrector\cell\row\trowd\trgaph70\trleft-70\trbrdrl\brdrs\brdrw10 \trbrdrt\brdrs\brdrw10 \trbrdrr\brdrs\brdrw10 \trbrdrb\brdrs\brdrw10 \trpaddl70\trpaddr70\trpaddfl3\trpaddfr3\r
  34 \clbrdrl\brdrw10\brdrs\clbrdrt\brdrw10\brdrs\clbrdrr\brdrw10\brdrs\clbrdrb\brdrw10\brdrs \cellx8710\pard\intbl Observaciones\par\r
  35 \par\r
  36 \par\r
  37 \par\r
  38 \par\r
  39 \par\r
  40 \par\r
  41 \par\r
  42 \par\r
  43 \par\r
  44 \par\r
  45 \par\r
  46 \par\r
  47 \cell\row\pard\par\r
  48 \par\r
  49 \lang11274\f1\fs20 Se pide:\par\r
  50 1. Resolver el problema por backtracking.\par\r
  51 \i\tab a\i0 ) Calcular el orden.\par\r
  52 2. Programar el algoritmo de Gale & Shapley para resolver el problema.\par\r
  53 \i\tab a\i0 ) Calcular el orden.\par\r
  54 \i\tab b\i0 ) Justificar que la asignaci\'f3n es completa y estable, es decir que el algoritmo no deja personas solteras y la asignaci\'f3n realizada es estable.\par\r
  55 \i\tab c\i0 ) Justificar que el algoritmo termina siempre.\par\r
  56 \i\tab d\i0 ) \'bfEl algoritmo es sim\'e9trico? Justificar.\par\r
  57 \i\tab e\i0 ) Si se les permitiera a las mujeres cambiar la lista de de preferencia durante la ejecuci\'f3n del algoritmo, como podr\'eda hacer una mujer dada, para conseguir el hombre \'f3ptimo. Explicar.\par\r
  58 \i\tab f \i0 ) De que estrategia algor\'edtmica se trata. Justificar.\f2\par\r
  59 \b\f3\par\r
  60 1)\par\r
  61 \tab a) Orden del Backtracking para un problema de NxN\b0\par\r
  62 \par\r
  63 El algoritmo de backtracking en principio "recorre" de forma recursiva la lista de hombres hasta llegar a formar pareja con el \'faltimo de ellos. Esto nos aporta un O(N).\par\r
  64 \par\r
  65 Dentro de cada iteraci\'f3n del backtracking se recorre la lista de preferencia de mujeres que el hombre tiene, lo cual eleva el orden a O(N^2). \par\r
  66 \par\r
  67 \f4 void BackTracking::Ensayar(Candidato) \par\r
  68 \{\par\r
  69 \tab /* Recorro todas las mujeres de este hombre */\par\r
  70 \tab for (\tab Candidata = Candidato.preferencias.inicio(); \par\r
  71 \tab\tab Candidata != Candidato.preferencias.fin(); \par\r
  72 \tab\tab ++Candidata)\par\r
  73 \tab\{\par\r
  74 \tab\tab if (Candidata.soltera() && ParejaEstable(Candidato, Candidata))\par\r
  75 \tab\tab\{\par\r
  76 \tab\tab\tab Comprometer(Candidato, Candidata);\tab\tab\tab\par\r
  77 \par\r
  78 \tab\tab\tab if (!UltimoHombreSoltero(Candidato))\par\r
  79 \tab\tab\tab\{\par\r
  80 \tab\tab\tab\tab /* Llamada recursiva: quedan hombres sin pareja */\par\r
  81 \tab\tab\tab\tab Ensayar(Proximo(Candidato));\par\r
  82 \tab\tab\tab\}\par\r
  83 \tab\tab\tab else\par\r
  84 \tab\tab\tab\{\par\r
  85 \tab\tab\tab\tab /* Es el \'faltimo hombre, tengo configuraci\'f3n estable */\par\r
  86 \tab\tab\tab\tab MostrarParejas();\tab\tab\tab\tab\par\r
  87 \tab\tab\tab\}\par\r
  88 \tab\tab\tab\par\r
  89 \tab\tab\tab RomperCompromiso(Candidato, Candidata);\par\r
  90 \tab\tab\}\par\r
  91 \tab\}\par\r
  92 \}\f3\par\r
  93 \par\r
  94 Al recorrer esta lista, el algoritmo verifica si la pareja "candidata" es estable. Para verificar que la pareja sea estable si :\par\r
  95 \par\r
  96 Para todas las mujeres que el candidato prefiere m\'e1s que a la candidata (y que est\'e1n comprometidas, puesto que sino el candidato ya las hubiera elegido), no prefieren al candidato por sobre su pareja actual.\par\r
  97 \par\r
  98 An\'e1logamente, para todos los hombres que la canidata prefiere m\'e1s que al candidato (y que est\'e1n comprometidos, puesto que sino la candidata ya los hubiera elegido), no prefieren la candidata por sobre su pareja actual.\par\r
  99 \par\r
 100 Esta verificaci\'f3n es sim\'e9trica sobre las listas de preferencias del hombre y la mujer candidatos.\par\r
 101 \par\r
 102 \f4 bool ParejaEstable(Candidato, Candidata)\par\r
 103 \{\par\r
 104 \tab ParejaEstable = verdadero;\par\r
 105 \par\r
 106 \tab iM = Candidato.preferencias.inicio();\par\r
 107 \tab\tab\par\r
 108 \tab /* Recorro todas las mujeres mejor posicionadas que la candidata */\par\r
 109 \tab mientras ((iM<Candidata) && ParejaEstable)\par\r
 110 \tab\{\par\r
 111 \tab\tab /* Si la mujer no est\'e1 soltera */\par\r
 112 \tab\tab si (iM->soltera())\par\r
 113 \tab\tab\{\par\r
 114 \tab\tab\tab /* Me fijo si me prefiere m\'e1s que al que tiene ahora */\par\r
 115 \tab\tab\tab RankingCandidato = iM.preferencias.indice_de(Candidato);\par\r
 116 \tab\par\r
 117 \tab\tab\tab RankingParejaActual = iM.preferencias.indice_de(iM.pareja());\par\r
 118 \tab\par\r
 119 \tab\tab\tab ParejaEstable = RankingCandidato > RankingParejaActual;\par\r
 120 \tab\tab\}\par\r
 121 \tab\par\r
 122 \tab\tab iM++;\par\r
 123 \tab\}\par\r
 124 \par\r
 125 \tab /* Sim\'e9trico para los preferidos de la Candidata */\par\r
 126 \tab ...\tab\par\r
 127 \}\par\r
 128 \par\r
 129 \f3 Recorrer la lista de candidatos es O(N). Y encontrar los \'edndices del candidato y de la pareja actual resultan ser O(N) cada una, con lo cual suman entre ambas O(2*N). El anidamiento hace multiplicar los \'f3rdenes, que resultan en O(N * 2*N) ~= O(N^2).\par\r
 130 \par\r
 131 Como es an\'e1loga la b\'fasqueda de esta condici\'f3n para los hombres que prefiere la candidata, el orden es tambi\'e9n O(N^2), que sumado al reci\'e9n calculado resulta en O(N^2 + N^2) = O(2*N^2) ~= O(N^2).\par\r
 132 \par\r
 133 Tal como se hab\'eda dicho, esta operaci\'f3n de verificaci\'f3n se hace al momento de ver si una pareja es estable o no mientras se recorre la lista de preferencias de un candidato. Esa operaci\'f3n ya tra\'eda consigo un orden de O(N^2), y al anidar el orden de la verificaci\'f3n resulta que el orden total del algoritmo de backtracking se eleva a un O(N^4).\par\r
 134 \par\r
 135 \b 2)\par\r
 136 \tab e) \'bfC\'f3mo conseguir al hombre deseado cambiando la lista de preferencias?\par\r
 137 \par\r
 138 \b0 Supongamos que Eva quiere conseguir a Ad\'e1n y puede mentir cuando se le pregunta por sus preferencias. Lo que Eva puede hacer tomar registro de todos los hombres que se le propusieron. Supongamos que en la primer vuelta se le propusieron Pedro y Segundo y ella se qued\'f3 comprometida con Pedro dado que \'e9l la prefer\'eda m\'e1s que Segundo y ella m\'e1s que a Segundo. Entonces Eva en la segunda vuelta mueve a Segundo al tope de su lista de preferencias, con lo cual en la segunda vuelta pasa a quedar comprometida con Segundo y esto hace que la mujer con quien Segundo  estaba comprometida quede libre y que Pedro tome a otra mujer, que no necesariamente van a ser la misma. En este caso despu\'e9s de la segunda vuelta, cuando Eva qued\'f3 comprometida con Segundo, ella otra vez tom\'f3 nota de todos los candidatos que se le propusieron. A la pr\'f3xima vuelta, elige a un candidato de \'e9stos y va de esta forma buscando lograr que se le proponga Ad\'e1n repitiendo su estrategia. Puede pasar que de esta forma Ad\'e1n no llegue a declar\'e1rsele, pero es una forma posible que Eva tiene de lograr su objetivo.\par\r
 139 \par\r
 140 \tab\b f) \'bfDe qu\'e9 estrategia algor\'edtmica se trata?\par\r
 141 \par\r
 142 \b0 El algortmo de \f1 Gale & Shapley se trata de una heur\'edstica. Es un algoritmo goloso, donde se busca una configuraci\'f3n aceptable y simple que luego por sucesivas iteraciones se va mejorando hasta lograr obtener una soluci\'f3n v\'e1lida.\f3\par\r
 143 \lang3082\f0\fs24\par\r
 144 \par\r
 145 }\r
 146 \0