Examen prop (2014)

Examen Español
Universidad Universidad Politécnica de Cataluña (UPC)
Grado Ingeniería Informática - 2º curso
Asignatura prop
Año del apunte 2014
Páginas 5
Fecha de subida 31/05/2014
Descargas 8
Subido por

Descripción

Examen parcial de prop corregido.

Vista previa del texto

EXAMEN PPRO  Dimecres 28 de març de 2012    1) (3 punts; 30 minuts)  Volem construir a partir d’un graf G que té de l’ordre de 1.000 nodes,  un subgraf G’ aleatori i estudiar la seva connectivitat (el que és conegut com a tècnica de  percolació). El procediment serà el següent:    1‐ Generem el subgraf amb tots el nodes del graf   2‐ Demanem quin percentatge d’arestes volem en el subgraf  3‐ Mentre no tinguem el nombre d’arestes demanat  a. Escollim una parella de nodes a l’atzar al graf G  b. Si  els  nodes  estan  connectats  a  G  i  l’aresta  no  hi  era  ja  en  el  subgraf  G’,   afegim l’aresta al subgraf G’ i en comptem una aresta més afegida  4‐ Calculem el nombre de parts connexes del subgraf  Es  demana  que  discutiu  quin  mecanisme  de  representació  del  graf  (llistes  d’adjacència  o  matriu  d’adjacència)  és  el  més  adequat  per  aquest  problema  des  del  punt  de  vista  de  memòria i de temps d’execució.    SOLUCIÓ:  Des del punt de vista de memòria, sabem que la matriu d’adjacència té un cost O(n2), i  les llistes d’adjacència tenen un cost O(n+a). No sabem si els grafs són esparsos o no i  per tant no tenint criteri per decidir‐nos del tot. En tot cas un graf no ponderat de 1.000  nodes  requereix  1Mbit  (125  Kbytes)  de  memòria  per  representar‐lo  en  el  cas  de  la  matriu d’adjacència, que no és exagerat.   Des del punt de vista de temps d’execució, del procediment de creació del graf, l’acció  que més es farà servir amb diferència és consultar si existeix una aresta entre dos nodes.  En  aquest  cas  la  millor  opció  es  fer  servir  matrius  d’adjacència  doncs  el  seu  cost  és  constant.  Per tant l’elecció hauria de ser matrius d’adjacència.              2) (3 punts; 40 minuts)  Un graf bipartit és un graf en què els seus nodes es poden dividir en  dos conjunts de manera que cada node només està connectat a nodes de l’altre conjunt.  En el graf de la figura es pot constatar que és bipartit doncs podem generar dos conjunts  (els  nodes  de  dalt  i  els  nodes  de  baix)  que  només  es  comuniquen  amb  nodes  de  l’altre  conjunt. Es demana que dissenyeu un algorisme en temps polinòmic que determini si un  graf és bipartit o no, o be demostreu que és un problema NP‐complet. Es demana també  que  justifiqueu  quina  representació  del  graf  seria  més  eficient  per  implementar  l’algorísme.                SOLUCIÓ:  Per saber si el graf és bipartit o no, només cal fixar‐nos que tota exploració a partir d’un node  ha de donar com a veïns nodes del conjunt contrari, el veïns del veïns nodes del conjunt propi,  els  veïns  dels  veïns  dels  veïns  nodes  del  conjunt  contrari,  etc.  Per  tant  intentarem  fer  una  exploració a partir d’un node pintant amb dos color tal com hem dit. Si arribem a un node que  hauríem de pintar d’un color i ja està pintat amb un altre, llavors podrem deduir el graf no és  bipartit.                  /* Funció auxiliar per canviar de color */  int contrari (color c){      si color==1 llavors color=2 sinó color=1      fsi      retorna color  }    /***  PROGRAMA PRINCIPAL  ***/  /* Inicialitzem els color a no pintat. Farem servir el color 1 i 2 */  per tot node i dins nodes(G) fer     pintat[i]=0  fper    per tot node i dins nodes(G) fer      /* La iteració només cal si el graf no és connex */      si pintat[i]==0  llavors                      /* Si no hem vist prèviament el node... */           pintat[i] = 1                                   /* ... el pintem amb un color ... */           b = continua(i, contrari(1))        /* ... i pintarem els successors amb l’altre color */      fsi      si (no b) llavors retorna Fals      fsi  fper  retorna Cert  /***  FI PROGRAMA PRINCIPAL  ***/      /*** Funció que continua l’exploració ***/  bool  continua (node i, color c){      per tot node j dins successors(G,i) fer   /* Per cada successor del node i */            si pintat[j]==0  llavors                         /* Si no està pintat */                pintat[j]=c                                                  /* El pintem amb el color ...*/                b = continua(j, contrari(c))                     /* ... i els seus succs. amb l’altre color */            sinó  si pintat[j]!=c                             /* Si estava ja pintat amb un altre color */                         llavors retorna Fals               /* Llavors no es bipartit !!!!!! */                     fsi      fper      retorna Cert  }      L’algorisme funciona per grafs dirigits. Si canviem successors per veïns, funciona per grafs no  dirigits.    L’algorisme  serviria  per  comprovar  si  un  graf  és  2‐colorable.  En  general  k‐colorable  és  NPc  (amb k genèric), però el cas particular de k=2 (2‐colorable) es pot resoldre en temps polinòmic.           3) (4  punts;  30  minuts)  En  aquests  temps  de  crisi  no  us  toca  més  remei  que  acceptar  una  feina de becari d’una escola universitària ben coneguda. La primera feina que us demanen  és  planificar  els  exàmens  finals  de  l’escola  de  manera  que  tots  els  estudiants  puguin  fer  tots els exàmens que els hi pertoca (sense solapaments). Per altra banda, per les dates dels  finals, l’escola ha de cedir espais per fer els exàmens de selectivitat, de manera que es vol  saber si amb k dies es podrien fer tots els exàmens finals sense que hi hagi solapaments  d’exàmens  en  els  que  hi  hagi  alumnes  afectats.  Es  considera  un  solapament  quan  un  estudiant ha de fer dos o més exàmens diferents el mateix dia. Per resoldre aquesta tasca  us donen una llista de l assignatures i una llista de n estudiants amb les assignatures que  cursa  cadascú.  Escriu  un  programa  amb  temps  polinòmic  solucioni  el  problema  o  prova  que el problema és NP‐complet (NPc).     SOLUCIÓ:  Representarem el problema com  un graf G. Cada examen serà un node. Si dos exàmens tenen  un estudiant en comú hi posem una aresta (representarà la incompatibilitat de fer l’examen al  mateix temps). La solució a un problema serà un nombre associat entre 1 i k (que serà el dia de  l’examen) per a cada node de manera que dos nodes amb el mateix color NO comparteixin una  aresta. Si no existeix una solució tal, no es podrà fer els exàmens en k dies sense solapaments.  Per demostrar que el problema és NPc demostrarem primer (a) que és NP fent un programa  indeterminista que el soluciona, i després (b) demostrarem que és més complex o igual que un  altre problema NPc fent una reducció.  a)  Programa indeterminista pel problema:    /* Fase de hipòtesi. Construïm una solució */  /* Per cada examen (n’hi ha n) diem quin dia el farem */  per i de 1 a n fer    e[i] = dia    /* Selecció indeterminista del dia de l’examen */  fper  /* A e tenim la solució hipòtesi */    /* Fase de test de la hipòtesi:  */  /* Mirem que no hi hagi dos exàmens el mateix dia amb estudiants en comú */  per i  de 1 a n fer        per j de 1 a n fer              si   (<i,j>   G)  i  (e[i]==e[j])                     llavors retorna Fals        fsi  fper  fper  retorna Cert  El programa té un cost O(n2), llavors es pot resoldre en temps polinòmic per una màquina  no determinista. Llavors és un problema NP.    b)  Reducció  d’un  problema  NPc  a  al  nostre  problema.  Si  ens  hi  fixem,  el  nostre  problema  s’assembla molt a l’acolorit d’un graf.  En concret, si  diem  que el  graf dels exàmens és  el  graf  que  volem  acolorir  i  els  k  colors  són  els  k  dies  en  que  fer  l’examen,  veurem  que  els  problemes són idèntics.  La funció de reducció seria:  ‐ ‐ ‐ Cada node del graf és un examen  Cada color (k=1..n) és un dia en que fer l’examen  Les  arestes  que  indiquen  incompatibilitat  entre  colors  ara  en  el  nou  graf  d’exàmens indiquen incompatibilitat per un estudiant comú  La construcció del nou graf es fa en temps polinòmic.  Amb  aquesta  nova  representació  és  clar  que  si  EXAMENS  amb  k  dies  té  solució,  llavors  immediatament k‐acolorit té color. Si no en té, el graf original no es pot acolorir.  k‐acolorit  ≤p EXAMENS‐k‐dies      Amb els dos apartats ja hem arribat a demostrar que el problema dels exàmens és NPc.      ...

Tags: