PDF de programación - Curso de Algoritmia Avanzada

Imágen de pdf Curso de Algoritmia Avanzada

Curso de Algoritmia Avanzadagráfica de visualizaciones

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
  • Links de descarga
http://lwp-l.com/pdf8777

Comentarios de: Curso de Algoritmia Avanzada (0)


No hay comentarios
 

Comentar...

Nombre
Correo (no se visualiza en la web)
Valoración
Comentarios...
CerrarCerrar
CerrarCerrar
Cerrar

Tienes que ser un usuario registrado para poder insertar imágenes, archivos y/o videos.

Puedes registrarte o validarte desde aquí.

Codigo
Negrita
Subrayado
Tachado
Cursiva
Insertar enlace
Imagen externa
Emoticon
Tabular
Centrar
Titulo
Linea
Disminuir
Aumentar
Vista preliminar
sonreir
dientes
lengua
guiño
enfadado
confundido
llorar
avergonzado
sorprendido
triste
sol
estrella
jarra
camara
taza de cafe
email
beso
bombilla
amor
mal
bien
Es necesario revisar y aceptar las políticas de privacidad