daily pastebin goal
34%
SHARE
TWEET

Untitled

a guest Jul 11th, 2018 98 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. 1. Demostrar que el siguiente problema es NP completo: Tenemos N materias y M ayudantes. Cada ayudante es apto para dar solo un subconjunto determinado de las N materias. Se pueden asignar k < M ayudantes para dar las N materias? Pista: reducir a cobertura de vertices
  2.  
  3. 2. Definición de "casi-árbol": grafo conexo de N vértices con, a lo sumo, N+8 aristas. Dar un algoritmo lineal que dado un casi-árbol devuelva un árbol de tendido mínimo
  4.  
  5. 3. Resolver por division y conquista: hay N jugadores de un deporte, que juegan todos contra todos, los resultados son guardados en una matriz (M[i][j] = 1 significa que i le ganó a j). Dar un algoritmo que devuelva un array tal que el primer elemento le gane al segundo, el segundo al tercero, etc. Si M[2][1] = M[1][3] = 1, y los demás 0, sería [2, 1, 3].
  6.  
  7. 4. Resolver por programación dinámica: tenemos un grafo dirigido con V_i nodos, i de 1 a n. Se cumple las propiedades:
  8.   - Las aristas van solo de vértices menores a mayores, es decir v_1 -> v_2 puede ser, al revés no (1 -> 2)
  9.   - Todos los grados son mayores a cero excepto d(V_n) = 0
  10. Dar un algoritmo que de la longitud del camino más largo de v_1 a v_n en el grafo
  11.  
  12. 5. Resolver con un algoritmo greedy: Tenemos n ayudantes con disponibilidad horaria (intervalos). Tenemos que armar un comité de ayudantes, que estén a cargo de los demás. Cada ayudante puede estar a cargo del conjunto de ayudantes que se superpongan en horarios con sí mismo. Dar un algoritmo eficiente y óptimo que determine y minimice la cantidad de ayudantes a poner en el comité.
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top