Download Examen de Análisis y Diseño de Algoritmos 1.

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 a n 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
[email protected]