PEP 1 2008 2

UNIVERSIDAD DE SANTIAGO DE CHILE
FACULTAD DE INGENIERIA
DEPARTAMENTO DE INGENIERIA INFORMATICA

ALGORITMOS AVANZADOS
PEP 1
27 - octubre – 2008
Prof. Mónica Villanueva

Instrucciones:
Tiempo máximo:1,5 hr.
Puede usar resumen personal original, sin libros ni cuaderno. Lea cuidadosamente cada problema y responda lo preguntado.
En cada problema utilice algún método estudiado en el curso durante estesemestre. Debe hacer todo el desarrollo de cada
pregunta en las hojas, no se considerará si se escribe solo el resultado final del problema. Responda cada pregunta en forma
conjunta sin mezclar conla respuesta de otros problemas. Trabaje en la forma mas clara, ordenada y legible, que le sea
posible, con letra y lápiz legible. Apagar teléfonos celulares.

Problema 1 (1 punto):

Suponga que laentrada de un cierto problema ∏ tiene tamaño n, para resolverlo se encuentra en la literatura las
siguientes alternativas:
Alternativa A: algoritmo de tiempo O(n log( n2) ) + O( n2) + O( log( n! )) + O(n2 log( n ))
Alternativa B: transformarlo en otro problema para el cual se conoce un algoritmo de tiempo
O(n2), la transformación demora O(n).
Alternativa C: se descompone en 3 subproblemas similaresde tamaño n-3, el tiempo para combinar
las soluciones de los subproblemas es O( n).
Alternativa D: se descompone en 3 subproblemas similares de tamaño n/3, el tiempo para combinar
las soluciones delos subproblemas es O( n).
¿Qué alternativa escoge Ud.? Justifique.

Problema 2 (2 puntos):
Para aprobar el curso de Algoritmos Avanzados se debe aprobar cátedra y laboratorio. En Cátedra hay trespruebas parciales (pepi), tres controles de lectura rendidos en clases de ayudantía (ci), y Prueba Optativa de
Reemplazo (POR) que reemplaza la nota mas baja de pep si es mas alta que alguna de ellas. Elpromedio de los
controles equivale a una pep. En Laboratorio se realizan trabajos en clase (25%), tareas (25%) y trabajos de
laboratorio (50%). Si el alumno aprueba el curso, la nota final se calcula...