PDF de programación - Capitulo 3 - Diseño de algoritmos iterativos

Diseño de algoritmos iterativos1

Capítulo 3

Cada cosa tiene su belleza, pero no todos pueden
verla.
Confucio

Resumen: En este tema se introducen los conceptos de verificación y derivación de
algoritmos como métodos que nos permiten razonar sobre la corrección de un algoritmo
y su correcta construcción respectivamente.

1.

Introducción

En el capítulo anterior se ha visto la posibilidad de utilizar predicados para definir
conjuntos de estados y cómo es posible especificar un algoritmo mediante dos predicados
llamados precondición y postcondición. El primero describe el conjunto de estados válidos
al comienzo del algoritmo y el segundo el conjunto de estados alcanzables con la ejecución
del algoritmo.

En este capítulo representaremos los estados intermedios de un algoritmo mientras se
ejecuta utilizando predicados, generalmente denominados aserciones o asertos. Escribiendo
asertos entre cada dos instrucciones tenemos un modo de razonar sobre la corrección de
un programa imperativo.

2. Reglas prácticas para el cálculo de la eficiencia

1. Las instrucciones de asignación, de entrada-salida, los accesos a elementos de un
vector y las expresiones aritméticas y lógicas (siempre que no involucren variables
cuyos tamaños dependan del tamaño del problema) tendrán un coste constante, ⇥(1).
No se cuentan los return.

2. Para calcular el coste de una composición secuencial de instrucciones, S1; S2 se suma
los costes de S1 y S2. Si el coste de S1 está en ⇥(f1(n)) y el de S2 está en ⇥(f2(n)),
entonces: ⇥(f1(n) + f2(n)) = ⇥(max(f1(n), f2(n))).

3. Para calcular el coste de una instrucción condicional:
1Ramón González del Campo es el autor principal de este tema.

25

26

Capítulo 3. Diseño de algoritmos iterativos

if (B) {S1} else {S2}

Si el coste de S1 está en O(f1(n)), el de S2 está en O(f2(n)) y el de B en O(fB(n)),
podemos señalar dos casos para el condicional:
Caso peor: O(max(fB(n), f1(n), f2(n)).
Caso promedio: O(max(fB(n), f(n)) donde f(n) es el promedio de f1(n) y
f2(n).

Se pueden encontrar expresiones análogas a éstas para la clase Omega.

4. Bucles con la forma:

while (B)

{S
}

Para calcular el coste de tal bucle hay que calcular primero el coste de cada pasada
y después sumar los costes de todas las pasadas que se hagan en el bucle. El número
de iteraciones dependerá de lo que tarde en hacerse falso B, teniendo en cuenta los
datos concretos sobre los que se ejecute el programa y lo grandes que sean.

2.1. Ejemplos de cálculo de complejidad de algoritmos iterativos

De manera práctica, se analizará el código de los algoritmos presentados de arriba hacia

abajo y de dentro hacia fuera.

Búsqueda secuencial

1 bool buscaSec( int v[], int num, int x ) {
2

int j;
bool encontrado;

j = 0;
encontrado = false;
while ( (j < num) && ! encontrado ) {

encontrado = ( v[j] == x );
j++;

}
return encontrado;

3

4

5

6

7

8

9

10

11
12 }

• Caso peor: el elemento buscado x no está en el vector

+

) +

j=0..n1

n|{z}

Cuerpo del bucle while: 4 (3 en la línea 8 y 1 en la línea 9)
= 7n + 3
Bucle while:
Total: 7n + 3 + 2(inicializaciones) = 7n + 5
se entra una vez en el bucle while
Cuerpo del bucle while: 4

⇤ ( 4|{z}

3|{z}

3|{z}

cuerpo

condicion

condicion

• Caso mejor: el elemento buscado x está en la primera posición del vector; sólo

Estructura de Datos y Algoritmos

2. Reglas prácticas para el cálculo de la eficiencia

27

Bucle while: (4 + 3) + 3 = 10
Total: 10 + 2 = 12

Búsqueda binaria

1 int buscaBin( int v[], int num, int x ) {
2

int izq, der, centro;

3

4

5

6

7

8

9

10

11

12

13
14 }

izq = -1;
der = num;
while ( der != izq+1 ) {
centro = (izq+der) / 2;
if ( v[centro] <= x )

izq = centro;

else

der = centro;

}
return izq;

• En esta ocasión no hay caso mejor ni peor, el bucle se ejecuta el mismo número
de veces independientemente de la posición de x en el vector o incluso si x no
aparece en el vector. Aunque el elemento buscado esté en el centro, el bucle
sigue ejecutándose hasta acotar un subvector de longitud 1.
Cuerpo del bucle while:
Bucle while:
| {z }
Total: (8 log(n) + 2) + 2(inicializaciones) = 8 log(n) + 4

+ 3|{z}if
2|{z}

2|{z}

linea 7

3|{z}
⇤ ( 6|{z}

= 8 log(n) + 2

vueltas while

log(n)

condicion

condicion

= 6

+

) +

cuerpo

En caso de que el elemento buscado estuviese repetido, ¿qué posición se devolvería?

Ordenación por inserción

1 void ordenaIns ( int v[], int num ) {
2

int i, j, x;

3

4

5

6

7

8

9

10

11

for ( i = 1; i < num; i++ ) {

x = v[i];
j = i-1;
while ( (j >= 0 ) && (v[j] > x) ){

v[j+1] = v[j];
j = j-1;

}
v[j+1] = x;

}

12
13 }

• Caso peor: el vector está ordenado a la inversa; la segunda parte de la condición

del while se cumple siempre
Cuerpo del bucle while: 6 (4 de la línea 8 y 2 de la línea 9)
= 10i + 4
Bucle while:

) +

+

condicion

condicion

j=0..i1

i|{z}

⇤ ( 6|{z}

cuerpo

4|{z}

4|{z}

Facultad de Informática - UCM

28

Capítulo 3. Diseño de algoritmos iterativos

= 10i + 12

i++

while

((10i + 12)

Cuerpo del bucle for: (10i + 4)
|
{z
}
Bucle for:
n1Xi=1
1|{z}
|
n1Xi=1

+ 3|{z}l11
+ 1|{z}
+ 2|{z}l6
+ 2|{z}l5
n1Xi=1
+ 1|{z}ini
1|{z}
+ 13(n 1) + 2 =

{z
}
n1Xi=1
= 5n2 5n + 13n 13 + 2 = 5n2 + 8n 11

13 + 2 = 10 n(n 1)

= 10

condicion

condicion

) +

cuerpo

i +

=

+

2

(10i + 13) + 2 =

• Caso mejor: el vector está ordenado; la segunda parte de la condición del while

no se cumple nunca
Bucle while: 4(condicion)
Cuerpo del bucle for: 4 + 2 + 2 + 3 + 1 = 12
Bucle for:
n1Xi=1

(12 + 1) + 1 + 1 =

n1Xi=1

13 + 2 = 13(n 1) + 2 = 13n 11

Ordenación por selección

1 void ordenaSel ( int v[], int num ) {
2

int i, j, menor, aux;

3

4

5

6

7

8

9

10

11

12

13

for ( i = 0; i < num; i++ ) {

menor = i;
for ( j = i+1; j < num; j++ )

if ( v[j] < v[menor] )

menor = j;

if ( i != menor ) {

aux = v[i];
v[i] = v[menor];
v[menor] = aux;

}

}

14
15 }

• Caso peor: vector desordenado

= 5

condicion

+

j++

|

cuerpo

+ 1|{z}
Cuerpo del for interno: 3|{z}if
+ 1|{z}l8
1|{z}
( 5|{z}
Bucle for interno: (n i 1)
}
{z
j=i+1..n1
+ (6n 6i 3)
Cuerpo del for externo: 1|{z}l5
}
|
{z
= 6n 6i + 7
Bucle for externo:
n1Xi=0
((6n 6i + 7)
+ 1|{z}ini
)+ 1|{z}
+
|
}

1|{z}

{z

condicion

condicion

cuerpo

f or

Estructura de Datos y Algoritmos

= 6n6i3

condicion

)+ 1|{z}
+ 2|{z}l10
+ 1|{z}if
n1Xi=0

+ 2|{z}ini
+ 3|{z}l11
n1Xi=0

n6

= 6

+ 2|{z}l12
n1Xi=0

i+

8+2 =

+ 1|{z}

i++

2. Reglas prácticas para el cálculo de la eficiencia

29

= 6n2 6 n(n 1)

6
2 n + 8n + 2 = 3n2 + 11n + 2
• Caso mejor: vector ordenado; la condición del if más interno no se cumple

+ 8n + 2 = 6n2

6
2 n2 +

2

nunca, y como consecuencia la del más externo tampoco:
Cuerpo del for interno: 4
Bucle for interno: (n i 1)(4 + 1) + 1 + 2 = 5n 5i 2
Cuerpo del for externo: 1 + (5n 5i 2) + 1 + 1 = 5n 5i + 1
Bucle for externo:
n1Xi=0
n 5
5
5
2 n2 +
2 n + 2n + 2 =

n1Xi=0
((5n 5i + 1) + 1) + 1 + 1 = 5
5
2 n2 +

= 5n2 5 n(n 1)

n1Xi=0

n1Xi=0

i +

2

2 + 2 =

9
2 n + 2

+ 2n + 2 = 5n2
¿Qué sucede si el vector está ordenado al revés?
Ordenación por el método de la burbuja modificado

1 void ordenaBur ( int v[], int num ) {
2

int i, j, aux;
bool modificado;

3

4

5

6

7

8

9

10

11

12

13

14

15

16

i = 0;
modificado = true;
while ( (i < num-1) && modificado ) {

modificado = false;
for ( j = num-1; j > i; j-- )

if ( v[j] < v[j-1] ) {

aux = v[j];
v[j] = v[j-1];
v[j-1] = aux;
modificado = true;

}

i++;

}

17
18 }

cuerpo

+

) +

• Caso peor: El vector está ordenado al revés; se entra siempre en el if :
= 15

condicion

condicion

+ 1|{z}
+ 1|{z}l14
+ 3|{z}l13
+ 4|{z}l12
+ 2|{z}l11
Cuerpo del bucle for: 4|{z}if
1|{z}
+ 2|{z}ini
1|{z}
( 15|{z}
Bucle for: (n i 1)
}
{z
|
j=i+1..n1
+ 1|{z}
+ 16n 16i 13
Cuerpo del bucle while: 1|{z}l8
}
|
{z
Bucle while:
n2Xi=0
n2Xi=0
n2Xi=0
)+ 3|{z}
3|{z}
{z
8(n 1) + 3 =
= 16n(n 1) 16
= 16n2 16n 8n2 + 24n 16 8n + 8 + 3 = 8n2 5

((16n 16i 11)
|
}

(n 2)(n 1)

n16

= 16

condicion

condicion

f or

i++

cuerpo

+

2

j
= 16n 16i 13

= 16n 16i 11

i

n2Xi=0

8+3 =

Facultad de Informática - UCM

30

Capítulo 3. Diseño de algoritmos iterativos

Total: 8n2 5
| {z }

while

= 8n2 3

+ 2|{z}ini

• Caso mejor: El vector está ordenado; nunca se entra en el if y sólo se da una

vuelta al while:
Cuerpo del bucle for: 4 + 1 = 5
Bucle for: (n 1)(5 + 1) + 1 + 2 = 6n 3
Cuerpo del bucle while: 1 + (6n 3) + 1 = 6n 1
Bucle while:
((6n 1) + 3) + 3 = 6n + 5

Total: 6n + 5 + 2 = 6n + 7

3. Verificación

3.1. Semántica de un lenguaje imperativo

Especificar un algoritmo: encontrar dos predicados P y Q tales que: {P } A {Q }.

Verificar: introducir predicados intermedios entre cada par de instrucciones elemen-
tales:

{P ⌘ R0}A1{R1}; ...;{Rn1}An{Rn ⌘ Q}

Si se satisface {Rk1}Ak{Rk}8 k entonces se satisface {P}A{Q}.
Buscaremos reglas para determinar si se satisface {Rk1}Ak{Rk} (reglas de verifica-
ción).

Conocer dichas reglas para cada instrucción del lenguaje es equivalente a conocer la
semántica de éste.

Todas las instrucciones que se definen más adelante cumplen las siguientes reglas generales:

Si se cumple {P}A{Q} podemos conocer otras especificaciones de A. Si P 0 ) P
entonces se cumple {P 0}A{Q}:

P 0 ) P {P}A{Q}

{P 0}A{Q}

(fortalecimiento de la precondición)

Si Q ) Q0 entonces se cumple {P}A{Q0}:

{P}A{Q} Q ) Q0

{P}A{Q0}

Conjunción en la postcondición:

(debilitamiento de la postcondición)

{P}A{Q1} {P}A{Q2}

{P}A{Q1 ^ Q2}

Disyunción en la precondición:

Estructura de Datos y Algoritmos

3. Verificación

31

{P1}A{Q}

{P2}A{Q}

{P1 _ P2}A{Q}

Acabamos de ver que la precondición de una especificación correcta se puede fortalecer.
Esto implica que para demostrar la corrección de {P}A{Q} es suficiente con demostrar
{R}A{Q} (donde R es la condición más débil de A con respecto a Q, pmd(A, Q), que
verifica la postcondición) y ver que P ) R:

P ) pmd(A, Q)