Análisis de algoritmos
Tercer examen parcial
Pregunta 1 (4 puntos): Sean S =
{s1, s2, ..., sp} y T = {t1,
t2, ..., tq} dos conjuntos de enteros tomados del
conjunto {1, 2, ..., n}. Diseñe y analice un algoritmo para
determinar si S = T en tiempo O(p+q). Nota:
Observe que p y q pueden
ser diferentes y aún así S = T debido a que sus elementos
pueden aparecer repetidos.
Pregunta
2 (6 puntos): Dada una gráfica G = (V, E) un ciclo de G de longitud k es una
sucesión de vértices y aristas v1, e1,
v2, e2, ..., vk, ek, vk+1
= v1 tal que v1, v2, ..., vk
son todos distintos y ei es la arista que une a vi
con vi+1 para toda 1 <= i <= k. Considere los
siguientes tres problemas:
- HAMILTON: Dada una gráfica G = (V, E),
¿tendrá G un ciclo que pase por todos sus vértices?
- CICLO: Dada una gráfica G = (V, E) y un número
entero k, ¿tendrá G un ciclo de longitud al menos k?
- AGENTE: Dada una gráfica G = (V, E), un costo positivo
para cada arista de G y un número real c, ¿tendrá
G un ciclo que pase por todos sus vértices y que la suma de los
costos de sus aristas sea a lo más c?
Suponga que HAMILTON es NP completo. Demuestre que (a) CICLO es NP
completo y que (b) AGENTE es NP completo. Nota: No olvide que cada una de
estas dos demostraciones consta de dos partes.
Deben entregarlo el lunes 11 de diciembre en mi oficina antes de las
6pm.