PDF de programación - Programación II - Tema 4. Introducción a los Algoritmos

Programación II
Bloque temático 1. Lenguajes de programación
Bloque temático 2. Metodología de programación
Bloque temático 3. Esquemas algorítmicos
Tema 4. Introducción a los Algoritmos

Tema 5. Algoritmos voraces, heurísticos y aproximados
Tema 6. Divide y Vencerás
Tema 7. Ordenación
Tema 8. Programación dinámica
Tema 9. Vuelta atrás
Tema 10.Ramificación y poda
Tema 11.Introducción a los Algoritmos Genéticos
Tema 12.Elección del esquema algorítmico

Programación II

Tema 4. Introducción a los Algoritmos

© Mario Aldea Rivas

04/04/11

Tema 4. Introducción a los Algoritmos
4.1. ¿Qué es un algoritmo?
4.2. Eficiencia de los algoritmos
4.3. Un vistazo a la NP-completitud
4.4. Cálculo de tiempos de ejecución
4.5. Diseño de algoritmos
4.6. Bibliografía



1



Programación II

Tema 4. Introducción a los Algoritmos

4.1 ¿Qué es un algoritmo?

© Mario Aldea Rivas

04/04/11

2

4.1 ¿Qué es un algoritmo?

Un algoritmo (de al-Jwarizmi, matemático árabe del siglo
IX) es un conjunto finito de instrucciones o pasos que
sirven para ejecutar una tarea o resolver un problema
Un algoritmo debe ser:

• Preciso: cada paso a seguir tiene un orden
• Finito: tiene un determinado número de pasos, o sea, que tiene

un fin

• Definido: si se sigue el mismo proceso más de una vez

llegaremos al mismo resultado

El primer algoritmo escrito para computador fue el creado
en el siglo XIX por Ada Byron

• cálculo de los números de Bernouilli para la máquina

analítica de Charles Babbage

Programación II

© Mario Aldea Rivas

04/04/11

3

Clásico

Inglés

à la russe

Qué un algoritmo sea mejor que otro podría depender de:

• el número de operaciones que haya que realizar
• de lo compleja que sea cada operación (multiplicación de

números de una cifra, suma, división y multiplicación por 2, ...)

© Mario Aldea Rivas

04/04/11

4

Programación II

Tema 4. Introducción a los Algoritmos

4.1 ¿Qué es un algoritmo?

Problemas y ejemplares
Los algoritmos propuestos para el problema de la multiplicación
no sólo son aplicables al caso 357×27
• sino que constituyen una solución general
El producto 357×27 es un ejemplar (o caso) del problema de la
multiplicación de enteros positivos
• otros ejemplares serían: 12430×841 o 3×8
• cada ejemplar será más o menos difícil de resolver
Los productos 46×7.2 o -7×2 no son ejemplares del problema
• cuando especificamos un problema hay que definir su dominio
Un algoritmo que pretende resolver un problema es incorrecto si
• es posible encontrar un ejemplar dentro dominio para el que el

algoritmo no produce una solución correcta

© Mario Aldea Rivas

04/04/11

5

Programación II

Tema 4. Introducción a los Algoritmos

Tema 4. Introducción a los Algoritmos

Ejemplo de Algoritmos
Un problema se puede resolver utilizando diferentes algoritmos
Algoritmos para la multiplicación con lápiz y papel:

4.1 ¿Qué es un algoritmo?

357
×27
2499
714
9639

357
×27
714
2499
9639

27 357 357
13 714 714
6 1428
3 2856 2856
1 5712 5712
9639

4.2 Eficiencia de los algoritmos

4.2 Eficiencia de los algoritmos
Un algoritmo es más eficiente cuantos menos recursos consuma

• Eficiencia espacial: cantidad de memoria extra requerida
• Eficiencia temporal: tiempo consumido

La eficiencia de un algoritmo resolviendo un ejemplar depende de:

• las características del propio algoritmo
• las características ejemplar a resolver

- especialmente su tamaño
• la velocidad del computador

Normalmente nos importaran los tiempos de peor caso:
• T(n): tiempo de peor caso para un ejemplar de tamaño n
• Tavg(n): tiempo promedio para un ejemplar de tamaño n

Programación II

© Mario Aldea Rivas

04/04/11

6

Tema 4. Introducción a los Algoritmos

4.2 Eficiencia de los algoritmos

Tiempo de ejecución de un algoritmo
método busca(entero[1..n] a,entero e) retorna entero
desde i=1 hasta n hacer
si a[i] == e entonces
retorna i
fsi
fdesde
retorna -1
fmétodo
Suponemos que, en un ordenador dado, cada iteración del lazo
tarda t unidades de tiempo
El tiempo de cómputo total T será:
• mejor caso (e==a[1]) ⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯→ T=t
• caso promedio (e==a[n/2]) ⎯⎯⎯⎯⎯⎯⎯→ Tavg(n)=t·n/2
• peor caso (e==a[n] ∨ e≠a[i], i∈[1,n]) → T(n)=t·n

Programación II

Tema 4. Introducción a los Algoritmos

© Mario Aldea Rivas

04/04/11

7

4.2 Eficiencia de los algoritmos

Notación asintótica
En el análisis y diseño de algoritmos nos importa el ritmo de
crecimiento del tiempo de cómputo (no su valor exacto)
Para expresar los ritmos de crecimiento se usa la notación O(n):
• decimos que T(n) es O(f(n)) si existen constantes c y n0
tales que T(n)≤c·f(n) para todo n≥n0
La notación O(n) muestra una cota superior al
ritmo de crecimiento de un algoritmo
En el ejemplo anterior:
• T(n)=t·n, luego diremos que T(n) es O(n)
- ya que existen c=2t y n0=0 tales que
T(n)=t·n ≤ 2t·n para todo n≥0
• esto se cumple independientemente del valor de t (es decir,
independientemente de la velocidad del ordenador)

2t·n

T(n)=t·n

Programación II

Tema 4. Introducción a los Algoritmos

© Mario Aldea Rivas

04/04/11

8

4.2 Eficiencia de los algoritmos

Notación asintótica (cont.)

2t·n

La notación Ω(n) nos da una cota inferior al ritmo de crecimiento
• decimos que T(n) es Ω(f(n)) si existen constantes c y n0
tales que T(n)≥c·f(n) para todo n≥n0
Cuando el ritmo de crecimiento es a la vez
O(f(n)) y Ω(f(n)) se dice que es Θ(f(n))
En el ejemplo anterior:
• T(n)=t·n, luego podremos decir que T(n) es Ω(n)
- ya que existen c=t/2 y n0=0 tales que T(n)=t·n ≥ t/2·n
para todo n≥0
• por lo tanto en este ejemplo podemos decir que T(n) es Θ(n)
La notación asintótica sólo proporciona límites a la velocidad de
crecimiento, “ocultando” las posibles constantes multiplicativas:
• T1(n)=n y T2(n)=1000000·n son ambas Θ(n)

T(n)=t·n

t/2·n

Programación II

© Mario Aldea Rivas

04/04/11

9

Tema 4. Introducción a los Algoritmos

4.2 Eficiencia de los algoritmos

Ritmos de crecimiento más habituales
• O(1), o constante
• O(log(n)), o logarítmico
• O(n), o lineal
•O(n·log(n))
• O(n2), o cuadrático
• O(nx), o polinómico
• O(2n), o exponencial
n
constante
1
2
4
8
16
32

n2
1
4
16
64
256
1024
© Mario Aldea Rivas

0
2
8
24
64
160

n log n

0
1
2
3
4
5

1
1
1
1
1
1

log n

n3
1
8
64
512
4096
32768

04/04/11

Programación II

Tema 4. Introducción a los Algoritmos

2n
2
4
16
256
65536

4294967296

10

4.2 Eficiencia de los algoritmos

Importancia de encontrar un algoritmo eficiente
El ritmo de crecimiento se acaba imponiendo para valores de n
suficientemente grandes

n=10
0.1 seg
10 seg

n=20
T(n)
10-4·2n
105 seg
10-2·n3
80 seg
• En un día, un computador 100 veces más rápido utilizando el
algoritmo T(n)=10-4·2n
- ¡sólo podría resolver un ejemplar de tamaño n=37!

más que la edad del universo

n=30
un día

4.5 minutos

n=200

un día

10-4·2n

10-2·n3

T(n)

10

20

© Mario Aldea Rivas

04/04/11

n

11

Programación II

Tema 4. Introducción a los Algoritmos

4.3 Un vistazo a la NP-completitud

4.3 Un vistazo a la NP-completitud
Los problemas se pueden agrupar en conjuntos:
• NP problemas para los que la comprobación de que una
solución es correcta puede realizarse en tiempo polinómico
- p.e.: encontrar un subconjunto de suma 0 en un array
- comprobar que la solución es correcta es muy sencillo (O(n))

(5,-3,4,-2,6) (5,-3,-2)

• P problemas que pueden resolverse en tiempo polinómico

- p.e.: buscar el máximo en un array (O(n))
- ya que para comprobar que una solución es correcta
P NP⊆
basta con volver a ejecutar el algoritmo (tiempo polinómico)
• NP-completos problemas para los que “parece” que nunca se
encontrará un algoritmo que los resuelva en tiempo polinómico

- p.e.: encontrar un subconjunto de suma 0 en un array

Programación II

© Mario Aldea Rivas

04/04/11

12

Tema 4. Introducción a los Algoritmos

4.3 Un vistazo a la NP-completitud

Para los problemas NP-completos no se ha encontrado una
solución mejor que recorrer (más o menos inteligentemente) todas
las posibles soluciones

Cálculo de tiempos de ejecución (cont.)

• veremos muchos problemas NP-completos durante el curso:

- mochila, coloreado de grafos, problema del viajante, ...

Todo indica que la relación entre P, NP y NP-completos es:

NP

P

NP-completos

• La pregunta del millón de dólares [4] es: ¿P = NP?
• está demostrado que si se consigue resolver un problema NP-
completo en tiempo polinómico se podrían resolver todos

Programación II

Tema 4. Introducción a los Algoritmos

© Mario Aldea Rivas

04/04/11

13

4.4 Cálculo de tiempos de ejecución

4.4 Cálculo de tiempos de ejecución
• Regla de las sumas:
• si T1(n) es O(f(n)) y T2(n) es O(g(n)), entonces
• T1(n)+T2(n) es O(max(f(n),g(n)))
Es decir: la ejecución de dos algoritmos que se realizan
uno después del otro tiene un ritmo de crecimiento igual al del
máximo de los dos

• Regla de los productos:
• si T1(n) es O(f(n)) y T2(n) es O(g(n)), entonces
• T1(n)·T2(n) es O((f(n)·g(n)))
Es decir: la ejecución de dos algoritmos anidados uno dentro del
otro tiene un ritmo de crecimiento igual al producto de los ritmos
de crecimiento de ambos

Programación II

Tema 4. Introducción a los Algoritmos

© Mario Aldea Rivas

04/04/11

14

4.4 Cálculo de tiempos de ejecución
Cálculo de tiempos de ejecución (cont.)

• Instrucciones simples (asignación y op. aritméticas): O(1)
• Secuencia de instrucciones simples: O(max(1,1,1)) = O(1)
• Instrucción condicional:
• si es un “if” simple y no se conoce el valor de la condición, se
supone que la parte condicional se ejecuta siempre
• si es un “if” con parte “else” y no se conoce el valor de la
condición, se elige la que más tarde de las dos partes

• Lazo: número de veces, por lo que tarden sus instrucciones
• Procedimientos recursivos: número de veces que se llama a sí

mismo, por lo que tarda cada vez

Programación II

© Mario Aldea Rivas

04/04/11

15

Tema 4. Introducción a los Algoritmos

4.4 Cálculo de tiempos de ejecución

Ejemplos de calculo del ritmo de crecimiento