PDF de programación - Curso de Algoritmia Avanzada

Universidad de Alicante

Departamento de Lenguajes y Sistemas Informáticos

Curso de Algoritmia Avanzada

Rafael C. Carrasco

c 2006 RCC
Actualizado el 26 de septiembre de 2006

Version 2.0

2

Presentación

Este documento pretende servir de material básico para un curso de Algoritmia
Avanzada, por lo que presupone conocimientos elementales de programación,
diseño y análisis de algoritmos, estructuras de datos y teoría de la probabilidad.
Para conseguir un aprendizaje más efectivo, se ha incluido textos inter-
activos durante cuya lectura el lector puede (y debe) tomar decisiones. Este
diseño está inspirado en la filosofía constructivista desarrollada por Piaget y
otros autores (véase, por ejemplo, J. Novak: A Theory of education. Cornell
University Press, 1977.)

Advertencias

3

Para seguir este curso es preciso utilizar un ordena-
dor personal con Acrobat ReaderTM 5.0 (o superior)
y un compilador de Java o C++.
El documento contiene ejercicios y problemas: con-
sulta la solución de cada ejercicio sólo después de
haber escrito tu respuesta; los problemas deben ser
revisados por el profesor.
Los enlaces se distinguen en color verde. Aprieta aquí
si quieres ajustar el tamaño del texto.

Se ha optado por usar el punto para separar la man-
tisa y la parte entera de los números reales para faci-
litar la lectura de las listas de números (por ejemplo,
los argumentos de una función) que se separan me-
diante comas.

Índice

Presentación

1 Programación dinámica

1.1 Programación dinámica recursiva . . . . . . . . . . . . . . . .
1.2 Programación dinámica iterativa . . . . . . . . . . . . . . . . .
1.3 La mayor subsecuencia común . . . . . . . . . . . . . . . . . .

2 Ramificación y poda

2.1 Búsqueda mediante ramificación del dominio . . . . . . . . . .
2.2 Funciones de cota optimista . . . . . . . . . . . . . . . . . . .
2.3 Funciones de cota pesimista . . . . . . . . . . . . . . . . . . .
2.4 Cálculo explícito de la solución . . . . . . . . . . . . . . . . .
2.5 Ramificación mediante estrategias inteligentes . . . . . . . . .
. . . . . . . . . . . .
2.6 Minimización de funciones . . . . . . . . . . . . . . . . . . . .
2.7 Ramificación y poda con restricciones . . . . . . . . . . . . . .

• Demostración de ramificación y poda

3 Búsqueda de texto

3.1 Búsqueda de texto sin preprocesamiento . . . . . . . . . . . .

2

7
8
10
13

17
18
24
28
34
35
37
41
42

46
47

Índice (cont.)

• Demostración del algoritmo de Boyer y Moore

. . . . . . .
3.2 Búsqueda de texto con preprocesamiento . . . . . . . . . . . .

4 Compresión

4.1 Compresión basada en diccionarios

. . . . . . . . . . . . . . .
• Demostración del algoritmo de Ziv y Lempel
. . . . . . . .
4.2 Compresión de Huffman . . . . . . . . . . . . . . . . . . . . .
• Demostración del algoritmo de Huffman . . . . . . . . . . .

5 Cifrado

5.1 Cifrado con clave simétrica . . . . . . . . . . . . . . . . . . . .
5.2 Cifrado con clave pública . . . . . . . . . . . . . . . . . . . . .
• Demostración del algoritmo RSA . . . . . . . . . . . . . . .
5.3 Firma digital
. . . . . . . . . . . . . . . . . . . . . . . . . . .
5.4 Certificados . . . . . . . . . . . . . . . . . . . . . . . . . . . .

6 Simulación computacional

6.1 Simulación de una cola . . . . . . . . . . . . . . . . . . . . . .
6.2 Generación de números alatorios . . . . . . . . . . . . . . . . .
6.3 Generación de distribuciones de probabilidad . . . . . . . . . .
6.4 Margen de error en la simulación . . . . . . . . . . . . . . . .
6.5 Técnicas de Monte Carlo . . . . . . . . . . . . . . . . . . . . .

5
56
57

66
68
69
71
73

83
84
87
91
93
94

97
98
103
106
112
115

Índice (cont.)
A Dificultades típicas en el diseño de cotas

Soluciones de los Ejercicios

• Demostración de una cola . . . . . . . . . . . . . . . . . . .

Soluciones de los Tests

6
119

122
193

207

Sección 1: Programación dinámica

1. Programación dinámica

7

La programación dinámica debe su nombre a los
problemas de dinámica de sistemas a los que se
aplicó originalmente. Su característica más destaca-
ble es que aumenta considerablemente la eficiencia
de numerosos procedimientos recursivos.

Sección 1: Programación dinámica

1.1. Programación dinámica recursiva
Ejercicio 1.

8

(a) El Nim es un juego de estrategia en el que cada jugador debe retirar
alternativamente entre una y N fichas de la mesa. Pierde el jugador que
no tiene opciones válidas en su turno, bien porque no quedan fichas o bien
porque encuentra una pero el jugador anterior retiró también una. Diseña
una función recursiva f (m, n) para el Nim de dos jugadores y N = 3 que
sea positiva si existe una estrategia ganadora para el jugador que encuentra
m fichas sobre la mesa si el jugador anterior retiró n fichas (y negativa en
caso contario).

(b) Compara el tiempo de cálculo de la función anterior para m = 40 y para

m = 50. ¿Para qué valores de n es útil el algoritmo?

(c) ¿Cuál es la causa del crecimiento exponencial en función de m del coste
del cálculo? Ayuda: dibuja el árbol de llamadas recursivas que se genera
para f (6, 0).

(d) Modifica el algoritmo para evitar, en la medida de lo posible, el aumento

de llamadas a la función f .

Sección 1: Programación dinámica

9

La esencia de la programación dinámica es utilizar
un almacén para que el programa recursivo guarde
resultados intermedios que pueden ser reutilizados
para acelerar el cómputo. A esta técnica la llama-
remos programación dinámica recursiva (en inglés,
“memoization”).

Ejercicio 2.

(a) ¿Cuál es el valor límite de m para el que se puede calcular f con la nueva

versión del algoritmo?

(b) Justifica que el programa (4) no ejecuta más de O(M ) pasos.

Problema 1. Implementa en Java un programa que juegue al Nim. Para ello,
modifica la función para que el valor de retorno sea el número de fichas que
debe retirarse para ganar o un valor negativo si no existe estrategia ganadora.

Sección 1: Programación dinámica

1.2. Programación dinámica iterativa

10

La programación dinámica iterativa suele resultar
más rápida y además evita el coste de memoria aso-
ciado a las llamadas recursivas. Por contra, a veces
calcula más posiciones del almacén de las necesarias,
por lo que no es siempre más rápida que la progra-
mación dinámica recursiva.

Ejercicio 3. Implementa una versión iterativa que evite el desbordamiento
de la pila recursiva en el algoritmo (4) y compara la velocidad y el número de
elementos del almacén calculados.

Sección 1: Programación dinámica
Ejercicio 4. ¿Cómo podemos evitar que un algoritmo de programación dinámi-
ca iterativa calcule más elementos de los que necesita la versión recursiva?

11

Sección 1: Programación dinámica

12

Problema 2. Generaliza el porgrama para que `ermita jugar a varios jugado-
res. Diseña un formulario en HTML similar al siguiente que utilice el programa
en Java implementado anteriormente (con las modificaciones que sean nece-
sarias).

Número de fichas inicial
Substracción máxima permitida
Elige tu jugada:

ADELANTE

Partida nueva

Sección 1: Programación dinámica

1.3. La mayor subsecuencia común

13

La orden diff de Unix compara las líneas de dos ficheros A y B e informa
sobre las diferencias encontradas entre ambos. Para ello aplica una función de
dispersión (“hashing”) que transforma cada línea en un único entero. Poste-
riormente busca la mayor subsecuencia común a las secuencias obtenidas, esto
es, qué líneas deben borrarse de cada uno para obtener dos ficheros idénticos.

Sección 1: Programación dinámica
Ejercicio 5.

14

(a) ¿Qué operaciones deben realizarse para transformar la secuencia “nuclear”

en “unclear”? ¿Cuál es la longitud de la mayor subsecuencia común?

(b) ¿Cuál el la m.s.c. de las cadenas “algoritmia” y “avanzada”? Une mediante

líneas cada par de letras iguales que forma parte de la m.s.c.

(c) Analiza en qué casos es trivial comparar dos ficheros por líneas. Escribe
una fórmula recursiva para los casos más complejos pensando en qué po-
sibilidades hay 1) cuando las dos últimas líneas son distintas y 2) cuando
son iguales.

(d) Calcula la mayor subsecuencia común de las dos cadenas siguientes:

01001100011100001111 y 11110011011000100011.

(e) ¿Cuántas casillas de la tabla se calculan cuando se aplica programación

dinámica recursiva al ejemplo anterior? ¿Y en el caso iterativo?

(f) ¿Cuál es el coste temporal (en el peor caso) de computar la mayor subse-
cuencia común de dos cadenas A y B usando programación dinámica? ¿Y
el de obtener la de tres cadenas A, B y C?

Sección 1: Programación dinámica

15

El problema de la mochila discreto se plantea de la siguiente forma: dados
N objetos de pesos w1, . . . , wN y valores v1, . . . , vN , calcúlese el valor máximo
de los objetos que se pueden transportar en una mochila de capacidad M .
Ejercicio 6.

(a) Escribe una fórmula recursiva para el valor máximo f (n, m) que se puede
transportar en la mochila sin sobrepasar el peso m tomando sólo objetos
entre los n primeros.

(b) El problema de la mochila discreto es un ejemplo de problema de comple-
jidad asintótica exponencial al que se puede aplicar programación dinámi-
ca. Si los pesos son enteros, el coste temporal está en O(N M ) siendo N
el número de objetos y M la capacidad de la mochila. ¿Significa lo an-
terior que hemos encontrado un algoritmo polinómico para un problema
exponencial?

(c) Calcula una solución óptima y dibuja las posiciones de la tabla calculadas
en el caso con N = 10, M = 40 en el que pesos y valores coinciden y son
los siguientes: 23, 6, 17, 35, 33, 15, 26, 12, 9 y 21.

(d) Explica cómo evitar el coste proporcional a N M cuando 2N M .

Sección 1: Programación dinámica

Problema 3. Diseña un programa que:

16

• Extraiga de una colección de textos las frecuencias de las palabras que

en ellos aparecen.

• Calcule para una secuen