Examen

FIEC – ESPOL
Análisis de Algoritmos
Deber Nº 3
Diciembre/09

Warshal
Sea G un grafo sencillo, dirigido y conexo. Escriba un programa para determinar si entre cada par de vértices de G existe por lo menos un camino. Utilice programación dinámica (una variación del algoritmo de Floyd). Calcule la matriz Z, cuyos elementos zij son verdaderos si existe por lo menos un camino entre los vérticesi y j, y falsos en caso contrario.
* Muestre con claridad que la estrategia que aplica el algoritmo es programación dinámica. Muestre también como se divide el problema en subproblemas, cuales son los subproblemas mas pequeños, y como se calcula la solución de un problema a partir de las soluciones de los subproblemas (ecuación de recurrencia).
* Calcule el tiempo de ejecución de sualgoritmo.
* Implemente el algoritmo de Warshal y pruebelo con dos casos por lo menos.

Vuelto
La empresa XYZ esta diseñando una nueva maquina vendedora de colas y requiere un programa para calcular el numero mínimo de monedas para entregar el vuelto B de una transacción, y determinar cuales son dichas monedas. Suponga que la maquina tiene un número ilimitado de monedas de cada una de lassiguientes denominaciones: 1, 5, 10, 25, y 50 centavos.

* Encuentre una solucion por división y conquista, por programacion dinámica, y por algoritmos voraces.
* Compare los tiempos de ejeccucion de estas soluciones (teoricamente)
* Implemente estas soluciones y pruébelas con dos casos por lo menos. Compare los resultados.

Planificación
Suponga que un estudiante decide durante lasemana de registros cambiar de especialidad, de Computación a Caos Aplicado. En la Facultad de Caos Aplicado todos los cursos se dictan un mismo día de la semana al que los estudiantes llaman el “superdía”. Cada curso tiene una hora de inicio y otra de terminación, distintas a las de los demás cursos; por ejemplo, “Arquitectura del Paisaje con Papel” empieza a las 10:27 y termina a las 11:51,mientras que “Macateta” empieza a las 4:18 y termina a las 7:06, etc. Como el estudiante quiere graduarse rápido, quisiera poder tomar el mayor número de cursos posible. El sistema académico de la universidad no le permite registrarse en cursos cuyos horarios se traslapen, y ningún funcionario tiene autoridad para pasar por alto esta característica del sistema. Encuentre los cursos en que deberegistrarse.

Mas formalmente, sea L una lista de los n cursos ofrecidos por la facultad de Caos Aplicado; con cada curso tenemos el par (sk, fk), donde sk es la hora de inicio y fk es la hora de terminación del curso k-ésimo; entonces, para cada par de cursos i, j, si > fj o sj > fi.
1. Encuentre una solución voraz a este problema, y demuestre que esta solución es correcta.
2.Instrumente su solución mediante una función que tiene por parámetro L y retorna el conjunto S de los cursos en que el estudiante debe registrarse.
3. Pruebe esta función con 2 casos de prueba cuando menos.

La distancia de Levenshtein (Minimum Edit Distance)
Cuando se levantan textos es normal cometer errores; por lo tanto, es de gran ayuda que el procesador que usamos tenga una función que liste unconjunto de palabras parecidas o próximas a la palabra mal escrita o cuya ortografía es cuestionable.
A fin de medir cuantitativamente la similitud entre dos palabras (secuencias de símbolos tomados de un alfabeto) se ha definido el concepto de distancia de Levenshtein. Obviamente, si dos palabras son idénticas, la distancia de Levenshtein entre ellas es 0; también, mientras mayor sea elparecido entre dos palabras menor sera la distancia entre ellas. Por supuesto, la similitud a la que nos referimos no es en sentido semántico o de significado, sino en sentido morfológico (la forma de la palabra).
La distancia de levenshtein entre las palabras w1 y w2 se define como el numero mínimo de cambios u operaciones de edición que deben efectuarse para transformar w1 en w2. Estas operaciones...