Actualizado el 21 de Marzo del 2018 (Publicado el 14 de Febrero del 2018)
1.095 visualizaciones desde el 14 de Febrero del 2018
959,0 KB
265 paginas
Creado hace 18a (28/09/2005)
Universidad de Alicante
Departamento de Lenguajes y Sistemas Inform´aticos
Curso de Algoritmia Avanzada
Rafael C. Carrasco
Instrucciones: Para seguir este curso es preciso utili-
zar un ordenador 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´on de cada ejercicio s´olo despu´es de
haber escrito tu respuesta; los problemas deben ser
entregados al profesor en la fecha estipulada.
Los enlaces se distinguen en color verde. Aprieta aqu´ı
si quieres ajustar el tama˜no del texto.
c(cid:13) 2005 RCC
Actualizado el 28 de septiembre de 2005
Versi´on 2.0
2
Presentaci´on
Este documento pretende servir de material b´asico para un curso de Algoritmia
Avanzada, por lo que presupone conocimientos elementales de programaci´on,
dise˜no y an´alisis de algoritmos, estructuras de datos y teor´ıa de la probabilidad.
Para conseguir un aprendizaje m´as efectivo, se ha incluido textos interacti-
vos durante cuya lectura el lector puede (y debe) tomar decisiones. Este dise˜no
est´a inspirado en la filosof´ıa constructivista desarrollada por Piaget y otros au-
tores (v´ease, por ejemplo, J. Novak: A Theory of education. Cornell University
Press, 1977.)
La ´ultima versi´on puede consultarse en:
http://www.dlsi.ua.es/ carrasco/aa/AA.pdf
Advertencias
3
Se ha optado por usar el punto para separar la man-
tisa y la parte entera de los n´umeros reales para faci-
litar la lectura de las listas de n´umeros (por ejemplo,
los argumentos de una funci´on) que se separan por
comas.
Algunas versiones del Acrobat ReaderTM 5.0 para Li-
nux no activan los formularios interactivos si el docu-
mento se abre directamente (por ejemplo, acroread
AA.pdf). Esto puede evitarse abriendo el documento
s´olo despu´es de tener el Reader en funcionamiento.
´Indice
Presentaci´on
0 Repaso de conceptos b´asicos
0.1 Definici´on de algoritmo . . . . . . . . . . . . . . . . . . . . . .
0.2 Complejidad temporal de los algoritmos
. . . . . . . . . . . .
0.3 Distribuciones de probabilidad . . . . . . . . . . . . . . . . . .
1 Programaci´on din´amica
1.1 Programaci´on din´amica recursiva . . . . . . . . . . . . . . . .
1.2 Programaci´on din´amica iterativa . . . . . . . . . . . . . . . . .
1.3 La mayor subsecuencia com´un . . . . . . . . . . . . . . . . . .
2 Ramificaci´on y poda
2.1 B´usqueda mediante ramificaci´on del dominio . . . . . . . . . .
2.2 Funciones de cota optimista . . . . . . . . . . . . . . . . . . .
2.3 Funciones de cota pesimista . . . . . . . . . . . . . . . . . . .
2.4 C´alculo expl´ıcito de la soluci´on . . . . . . . . . . . . . . . . .
2.5 Ramificaci´on mediante estrategias inteligentes . . . . . . . . .
. . . . . . . . . . . .
• Demostraci´on de ramificaci´on y poda
2
5
5
7
9
12
13
15
18
21
22
28
32
38
39
41
´Indice (cont.)
2.6 Minimizaci´on de funciones . . . . . . . . . . . . . . . . . . . .
2.7 Ramificaci´on y poda con restricciones . . . . . . . . . . . . . .
3 Simulaci´on computacional
3.1 Simulaci´on de una cola . . . . . . . . . . . . . . . . . . . . . .
3.2 Generaci´on de n´umeros aleatorios . . . . . . . . . . . . . . . .
3.3 Generaci´on de distribuciones de probabilidad . . . . . . . . . .
3.4 Margen de error en la simulaci´on . . . . . . . . . . . . . . . .
3.5 T´ecnicas de Monte Carlo . . . . . . . . . . . . . . . . . . . . .
4 Compresi´on
4.1 Compresi´on basada en diccionarios
. . . . . . . . . . . . . . .
• Demostraci´on del algoritmo de Ziv y Lempel
. . . . . . . .
4.2 Compresi´on de Huffman . . . . . . . . . . . . . . . . . . . . .
• Demostraci´on del algoritmo de Huffman . . . . . . . . . . .
5 Cifrado
5.1 Cifrado con clave sim´etrica . . . . . . . . . . . . . . . . . . . .
5.2 Cifrado con clave p´ublica . . . . . . . . . . . . . . . . . . . . .
• Demostraci´on del algoritmo RSA . . . . . . . . . . . . . . .
5.3 Firma digital
. . . . . . . . . . . . . . . . . . . . . . . . . . .
5.4 Certificados . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5
45
46
50
51
56
59
66
70
76
78
79
81
83
93
94
97
101
103
104
´Indice (cont.)
6 B´usqueda de texto
6.1 B´usqueda de texto sin preprocesamiento . . . . . . . . . . . .
. . . . . . .
6.2 B´usqueda de texto con preprocesamiento . . . . . . . . . . . .
• Demostraci´on del algoritmo de Boyer y Moore
A Dificultades t´ıpicas en el dise˜no de cotas
Soluciones de los ejercicios
• Demostraci´on de una cola . . . . . . . . . . . . . . . . . . .
Soluciones de los cuestionarios
6
107
108
116
118
128
130
182
224
Secci´on 0: Repaso de conceptos b´asicos
0. Repaso de conceptos b´asicos
0.1. Definici´on de algoritmo
Un algoritmo se define como un procedimiento com-
putable por una m´aquina de Turing. En la pr´actica,
un algoritmo es un conjunto ordenado y finito de ins-
trucciones que permite la resoluci´on de un problema.
.
7
Secci´on 0: Repaso de conceptos b´asicos
8
Adem´as, un procedimiennto computable satisface que:
1. Cada instrucci´on puede ser ejecutada en un tiempo finito.
2. La finalizaci´on del procedimiento est´a garantizada.
3. No se dan instrucciones cuyo resultado sea incierto (como “div´ıdase 3
por cero” o indefinido (como “t´omense tres o cuatro elementos”).
Secci´on 0: Repaso de conceptos b´asicos
8
Adem´as, un procedimiennto computable satisface que:
1. Cada instrucci´on puede ser ejecutada en un tiempo finito.
2. La finalizaci´on del procedimiento est´a garantizada.
3. No se dan instrucciones cuyo resultado sea incierto (como “div´ıdase 3
por cero” o indefinido (como “t´omense tres o cuatro elementos”).
Test ¿Es necesario que un algoritmo d´e siempre la soluci´on correcta?
(a) S´ı.
(b) No.
Secci´on 0: Repaso de conceptos b´asicos
9
0.2. Complejidad temporal de los algoritmos
Los problemas P pueden resolverse en tiempo polin´omico en funci´on del ta-
ma˜no de la entrada (p.ej., ordena una lista de enteros).
Secci´on 0: Repaso de conceptos b´asicos
9
0.2. Complejidad temporal de los algoritmos
Los problemas P pueden resolverse en tiempo polin´omico en funci´on del ta-
ma˜no de la entrada (p.ej., ordena una lista de enteros).
La soluci´on de un problema NP es verificable en tiempo polin´omico (p.ej. com-
probar si se amenazan 8 damas sobre un tablero).
Secci´on 0: Repaso de conceptos b´asicos
9
0.2. Complejidad temporal de los algoritmos
Los problemas P pueden resolverse en tiempo polin´omico en funci´on del ta-
ma˜no de la entrada (p.ej., ordena una lista de enteros).
La soluci´on de un problema NP es verificable en tiempo polin´omico (p.ej. com-
probar si se amenazan 8 damas sobre un tablero).
Los problemas NP dif´ıciles (NPH) son, al menos, tan dif´ıciles como SAT.
Secci´on 0: Repaso de conceptos b´asicos
9
0.2. Complejidad temporal de los algoritmos
Los problemas P pueden resolverse en tiempo polin´omico en funci´on del ta-
ma˜no de la entrada (p.ej., ordena una lista de enteros).
La soluci´on de un problema NP es verificable en tiempo polin´omico (p.ej. com-
probar si se amenazan 8 damas sobre un tablero).
Los problemas NP dif´ıciles (NPH) son, al menos, tan dif´ıciles como SAT.
Los problemas NPC (completos) son NP y NPH a la vez.
Figura 1: Disposici´on m´as veros´ımil de los distintos grupos de problemas.
PNPNPCNPH Secci´on 0: Repaso de conceptos b´asicos
10
Test ¿Cu´al es la complejidad temporal asint´otica de calcular el factorial de n?
(a) Lineal.
Puedes leer m´as sobre esta clasificaci´on aqu´ı y sobre la notaci´on O y Θ aqu´ı.
(c) Exponencial.
(b) Cuadr´atica.
Secci´on 0: Repaso de conceptos b´asicos
11
0.3. Distribuciones de probabilidad
Una funci´on de densidad de probabilidad es una funci´on f (x) : I → R definida
en un intervalo I = [xm´ın, xm´ax] ⊂ R que satisface:
2. R
1. f (x) ≥ 0 ∀x ∈ I
I dx f (x) = 1
Dada una funci´on de densidad f , la probabilidad de que la variable x tome un
valor comprendido entre a y b es:
p(a ≤ x < b) =
dx f (x)
Z b
a
Secci´on 0: Repaso de conceptos b´asicos
La esperanza o valor esperado de una funci´on ϕ : I → R es
12
La varianza de ϕ es una medida de dispersi´on definida por
Z
I
E[ϕ] =
dx f (x)ϕ(x)
Var[ϕ] = E(cid:2)(ϕ − E[ϕ])2(cid:3)
Secci´on 0: Repaso de conceptos b´asicos
13
Test ¿Es una buena medida de la dispersi´on de una variable o funci´on aleatoria
el valor esperado de las diferencias con respecto a la media, esto es, E[(ϕ −
E[ϕ])]?
(a) S´ı.
(b) No.
Ejercicio 0.1. Demuestra que
E(cid:2)(ϕ − E[ϕ])2(cid:3) = E[ϕ2] − E[ϕ]2.
Secci´on 1: Programaci´on din´amica
1. Programaci´on din´amica
14
La programaci´on din´amica debe su nombre a los
problemas de din´amica de sistemas a los que se
aplic´o originalmente. Su caracter´ıstica m´as destaca-
ble es que aumenta considerablemente la eficiencia
de numerosos procedimientos recursivos.
Secci´on 1: Programaci´on din´amica
1.1. Programaci´on din´amica recursiva
Ejercicio 1.1.
15
(a) En una variante del juego del Nim, cada jugador retira alternativamente
tres o cinco fichas de la mesa y pierde aquel jugador que no puede jugar en
su turno (esto es, encuentra menos de 3 fichas sobre la mesa). Dise˜na una
funci´on recursiva f (n) que calcule si existe una estrategia ganadora para
el jugador que encuentra n fichas sobre la mesa.
(b) Compara el tiempo de c´alculo de la funci´on anterior para n = 100 y para
n = 140. ¿Para qu´e valores de n es ´util el algoritmo?
(c) ¿Cu´al es la causa del crecimiento exponencial en funci´on de n del coste del
c´alculo? Ayuda: dibuja el ´arbol de llamadas recursivas que se genera para
n = 14.
(d) Modifica el algoritmo para evitar, en la medida de lo posible, el aumento
de llamadas a la funci´on f .
Secci´on 1: Programaci´on din´amica
16
La esencia de la programaci´on din´amica es utilizar
un almac´en para que el programa recursivo guarde
resultados intermedios que pueden ser reutilizados
para acelerar el c´omputo. A esta t´ecnica la llama-
remos programaci´on din´amica recursiva (en ingl´es,
“memoization”).
Secci´on 1: Programaci´on din´amica
16
La esenc
Comentarios de: Curso de Algoritmia Avanzada (0)
No hay comentarios