2017-Examen

Vista previa del material en texto

Examen de Análisis y Diseño de Algoritmos 
1.- Sea an el número de palabras de longitud n formadas con los dígitos {0, 1}, que no tienen 
dos ceros consecutivos. Encuentra una relación de recurrencia para calcular an y resuélvela. 
2.- Halla una relación de recurrencia para el número de formas en que una persona puede 
subir n escalones si puede subir uno o dos peldaños en cada paso. 
3.- Determine para qué tamaños de entrada, en la misma máquina, es más rápido un algoritmo 
con función de costo 100n2 que otro con función de costo 2n. 
4.- Un número natural n ≥ 1es triangular si es la suma de una sucesión ascendente no nula de 
naturales consecutivos que comienza en 1. Por tanto, los cinco primeros números triangulares 
son 1, 3 = 1+2, 6 = 1+2+3, 10 = 1+2+3+4 y 15 = 1+2+3+4+5. 
a) Escriba un algoritmo que, dado un entero positivo n ≥ 1, decida si éste es un número 
triangular. 
b) Analice su algoritmo, determinando su complejidad. 
5.- Usando la definición de notación asintótica Θ, demuestre con detalle que 
1024n2 +5n ∈ Θ(n2). 
6.- Clara, Luisa, María y Nélida son cuatro mujeres que aman sus trabajos. Ellas trabajan 
como diseñadora de moda, florista, jardinera y directora de orquesta. Cada mujer tiene un 
solo trabajo, y cada trabajo es ocupado por una sola mujer. Con las siguientes pistas, 
encontrar el trabajo realizado por cada mujer: 
(a) Clara es violentamente alérgica a las plantas. 
(b) Luisa y la florista comparten el departamento 
(c) A María y Luisa les gusta solamente la música rock 
(d) La jardinera, la diseñadora de modas y Nélida no se conocen entre sí. 
Programrlo en Prolog. 
7.- Una persona piensa un número entero positivo W. Escribe un algoritmo para que otra persona 
lo adivine realizándole preguntas con la relaciones de orden: <, >, =. El número de preguntas debe 
ser O(W). 
8.- Un acertijo consiste en dados 4 números y un resultado determinar las operaciones de suma o 
resta que hay que realizar sobre los números para obtener ese resultado. Por ejemplo: 
 Números: 1,4,3,2 
 Resultado: 0 
 Solución: 4 - 3 -2 + 1 
Suponiendo que resolvemos el acertijo como un problema de búsqueda, responde las siguientes 
cuestiones: 
1. Propón una representación de los estados y explica cómo se generarían los estados 
sucesores. 
2. ¿Cuál sería el tamaño del espacio de estados. ¿Y si el acertijo en lugar de ser con 4 números 
es con 5? Propón una fórmula general. ¿Cuántos nodos generaría el algoritmo de amplitud 
si buscara tosas las posibles soluciones? 
3. ¿Qué tipo de algoritmo de búsqueda no informada sería mejor utilizar? ¿Por qué? 
4. Define heurísticas para este problema. ¿qué otros mecanismos podríamos incluir para hacer 
la búsqueda más eficiente? 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
Nota: El examen resuelto debe enviarse a más tardar el día 12 de marzo de 2017 al correo 
fzflores@yahoo.com.mx 
mailto:fzflores@yahoo.com.mx