PDF de programación - Parte II: Estructuras de datos y algoritmos - 1. Introducción al análisis y diseño de algoritmos.

Parte II: Estructuras de datos y
algoritmos

UNIVERSIDAD DE CANTABRIA

1. Introducción al análisis y diseño de algoritmos.
2. Tipos abstractos de datos.
3. Métodos de ordenación.

GRUPO DE COMPUTADORES Y TIEMPO REAL
FACULTAD DE CIENCIAS

4

© Javier Gutiérrez, Michael González

6/nov/08

1

Notas:

UNIVERSIDAD DE CANTABRIA

1. Introducción al análisis y diseño de algoritmos.

• Introducción. Diseño de un Programa. Concepto de algoritmo. Descripción de

algoritmos: el pseudolenguaje y diagramas de flujo. Tiempo de ejecución. La notación
O(n). Ejemplos de análisis.

2. Tipos abstractos de datos.

• Conceptos básicos. Listas. Pilas. Colas. Vectores. Conjuntos. Mapas. Árboles. Árboles

binarios.

3. Métodos de ordenación.

• El modelo de ordenación interna. Esquemas simples de ordenación. Ordenación rápida.

Ordenación por cajas. Ordenación por base.

GRUPO DE COMPUTADORES Y TIEMPO REAL
FACULTAD DE CIENCIAS

© Javier Gutiérrez, Michael González

6/nov/08

2

1. Diseño de un programa

UNIVERSIDAD DE CANTABRIA

Requerimientos

Informales

Documento de
Requerimientos

Documento de
Especificaciones

Arquitectura
del Programa

Análisis de

Requerimientos

Análisis de

Especificaciones

Diseño de la
Arquitectura

Integración y
Pruebas de

Sistema

Pruebas
de Módulo

Codificación

Diseño
Detallado

Programa

Final

Módulos de
Programa
Probados

Módulos de
Programa

Diseño de cada

Módulo (pseudocódigo)

GRUPO DE COMPUTADORES Y TIEMPO REAL
FACULTAD DE CIENCIAS

© Javier Gutiérrez, Michael González

6/nov/08

3

Notas:

UNIVERSIDAD DE CANTABRIA

Los pasos que se siguen generalmente a la hora de desarrollar un programa son los siguientes:
• Análisis de requerimientos: Se define el problema a resolver y todos los objetivos que se

pretenden, pero sin indicar la forma en la que se resuelve.

• Especificación: Se determina la forma en la que se resolverá el problema, pero sin entrar aún

en su implementación informática. Se determina asimismo la interfaz con el usuario.

• Diseño del programa: Se divide el problema en módulos, se especifica lo que hace cada

módulo, así como las interfaces de cada uno de ellos.

• Diseño detallado de los módulos: Para cada módulo se diseñan detalladamente las estructuras

de datos y los algoritmos a emplear, normalmente descritos mediante pseudocódigo.

• Codificación: Se escribe el programa en el lenguaje de programación elegido.
• Pruebas de módulos: Se prueban los módulos del programa aisladamente y se corrigen los

fallos hasta conseguir un funcionamiento correcto.

• Integración y Prueba de sistema: Se unen todos los módulos, y se prueba el funcionamiento

del programa completo.

GRUPO DE COMPUTADORES Y TIEMPO REAL
FACULTAD DE CIENCIAS

© Javier Gutiérrez, Michael González

6/nov/08

4

Distribución del Esfuerzo

UNIVERSIDAD DE CANTABRIA

análisis y diseño

codificación

pruebas e
integración

GRUPO DE COMPUTADORES Y TIEMPO REAL
FACULTAD DE CIENCIAS

© Javier Gutiérrez, Michael González

6/nov/08

5

Notas:

UNIVERSIDAD DE CANTABRIA

Los siguientes datos se han obtenido del estudio de muchos proyectos software reales.

Distribución del esfuerzo de la actividad software (sin tener en cuenta el mantenimiento):

- Análisis y Diseño : 38%
- Codificación : 20%
- Pruebas e integración: 42%.

GRUPO DE COMPUTADORES Y TIEMPO REAL
FACULTAD DE CIENCIAS

© Javier Gutiérrez, Michael González

6/nov/08

6

2. Concepto de algoritmo

UNIVERSIDAD DE CANTABRIA

Un algoritmo es:
• una secuencia finita de instrucciones,
• cada una de ellas con un claro significado,
• que puede ser realizada con un esfuerzo finito
• y en un tiempo finito

El algoritmo se diseña en la etapa de diseño detallado y se
corresponde habitualmente con el nivel de subprograma

Algoritmo heurístico: suministra una solución buena, pero no
necesariamente óptima

GRUPO DE COMPUTADORES Y TIEMPO REAL
FACULTAD DE CIENCIAS

© Javier Gutiérrez, Michael González

6/nov/08

7

Notas:

UNIVERSIDAD DE CANTABRIA

El algoritmo se diseña durante la etapa de diseño detallado dentro del ciclo de vida del programa.
Habitualmente se corresponde con el nivel de subprograma, es decir, cada subprograma
implementa un algoritmo.

Un algoritmo es una secuencia finita de instrucciones, cada una de ellas con un claro significado,
que puede ser realizada con un esfuerzo y un tiempo finitos. Por ejemplo, una asignación como
x:=y+z es una instrucción con estas características

Un algoritmo que suministra una solución buena, pero no necesariamente óptima, se le denomina
algoritmo heurístico y suele utilizarse en aquellos problemas denominados “NP-completos” y cuya
solución óptima pasa por “intentar todas las posibilidades”, donde el número de posibilidades es una
función exponencial del tamaño del problema.

GRUPO DE COMPUTADORES Y TIEMPO REAL
FACULTAD DE CIENCIAS

© Javier Gutiérrez, Michael González

6/nov/08

8

Algoritmos recursivos

UNIVERSIDAD DE CANTABRIA

Algoritmo recursivo: se define en términos de sí mismo
• requiere que las referencias a sí mismo sean finitas

n!

⎧=
⎨
⎩

Ejemplo:
• forma iterativa del algoritmo
,

⋅

n

n 1–(

n
2–(
• forma recursiva del algoritmo
si
1
n 1–(
)!
,

⎧=
⎨
⎩

n!

n

,

⋅

1
)
⋅

n

si
0=
) …2 1⋅
⋅
,

si

n

0>

n
si

0=
n

0>

GRUPO DE COMPUTADORES Y TIEMPO REAL
FACULTAD DE CIENCIAS

© Javier Gutiérrez, Michael González

6/nov/08

9

Notas:

UNIVERSIDAD DE CANTABRIA

Un algoritmo recursivo es aquel que se define en términos de sí mismo.

Por ejemplo, podemos definir el factorial de un número como:
0=
n

1 si
,
n
1–(

)! si
,

n!

=

n

n

⋅

0>

En el caso del factorial existe también la solución iterativa

• es más eficiente la iterativa, ya que si el algoritmo se implementa con un subprograma, la

llamada al mismo es más costosa que una operación normal; además, ocupa más memoria,
porque cada sucesiva llamada a un procedimiento ocupa nuevo lugar en el stack
• pero hay muchos casos en los que no existe o es muy difícil la solución iterativa

GRUPO DE COMPUTADORES Y TIEMPO REAL
FACULTAD DE CIENCIAS

© Javier Gutiérrez, Michael González

6/nov/08

10

3. Descripción de algoritmos

UNIVERSIDAD DE CANTABRIA

Un algoritmo se puede especificar mediante la utilización de
un lenguaje de programación.

Sin embargo, generalmente se suelen utilizar técnicas de
descripción de algoritmos más o menos independientes del
lenguaje de programación:
• diagrama de flujo

- es un gráfico que muestra el orden en el que se van

ejecutando las diferentes instrucciones

• pseudolenguaje o pseudocódigo

- utiliza instrucciones de control y lenguaje natural

GRUPO DE COMPUTADORES Y TIEMPO REAL
FACULTAD DE CIENCIAS

© Javier Gutiérrez, Michael González

6/nov/08

11

Notas:

UNIVERSIDAD DE CANTABRIA

Un algoritmo se puede especificar mediante la utilización de un lenguaje de programación. En este
caso el algoritmo se describe en términos del conjunto de instrucciones del lenguaje.

Sin embargo, generalmente se suelen utilizar técnicas de descripción de algoritmos más o menos
independientes del lenguaje de programación en el que se codifican. Tal es el caso de los
diagramas de flujo o del pseudolenguaje.

El diagrama de flujo es un gráfico en el que se representa el orden en el que se van ejecutando las
diferentes instrucciones que forma el algoritmo.

El pseudolenguaje se puede considerar como un método para la descripción de algoritmos en el
que se utiliza una combinación de instrucciones informales escritas en lenguaje natural y de órdenes
de control estructuradas.

GRUPO DE COMPUTADORES Y TIEMPO REAL
FACULTAD DE CIENCIAS

© Javier Gutiérrez, Michael González

6/nov/08

12

Ejemplos

UNIVERSIDAD DE CANTABRIA

Comienzo

Factorial:=1

i:=N

SI

i=0?

NO

Fin

Factorial:=Factorial*i

i:=i-1

Diagrama de flujo

algoritmo factorial
(N : Natural)

factorial=1
lazo para i desde 1 hasta N

factorial=

factorial*i

fin lazo

Pseudocódigo

GRUPO DE COMPUTADORES Y TIEMPO REAL
FACULTAD DE CIENCIAS

© Javier Gutiérrez, Michael González

6/nov/08

13

Notas:

UNIVERSIDAD DE CANTABRIA

Puede observarse en estos ejemplos que el diagrama de flujo es más voluminoso que el
pseudocódigo. También es más difícil de modificar.

Por otro lado el pseudocódigo se puede escribir con un editor de texto, mientras que el
pseudocódigo necesita un editor gráfico. Por estos motivos, es normalmente más recomendable el
pseudocódigo, aunque hay algunos problemas cuya naturaleza se expresa mejor mediante
diagrama de flujo.

Cuando se describe un algoritmo tanto mediante diagrama de flujo como mediante pseudolenguaje,
se suele comenzar con una descripción a nivel alto, con instrucciones generales que es preciso
desarrollar en conjuntos de instrucciones más simples y precisas. Por tanto, en estos casos, se
suele realizar un proceso de refinamiento paso a paso, en el que el algoritmo se describe con un
nivel de detalle cada vez mayor. Las transparencias siguientes muestran un ejemplo de esto.

GRUPO DE COMPUTADORES Y TIEMPO REAL
FACULTAD DE CIENCIAS

© Javier Gutiérrez, Michael González

6/nov/08

14

Ejemplo de refinamiento paso
a paso

UNIVERSIDAD DE CANTABRIA

Problema de 'coloreado' de un grafo de forma que:
• dos vértices contiguos no sean del mismo color
• se minimice el número de colores

1

5

3

4

Una solución:

Rojo => 1,3,4
Verde => 5,2

2

La solución óptima sólo se consigue probando todas las
posibilidades

Existen algoritmos heurísticos para buscar una solución
buena

GRUPO DE COMPUTADORES Y TIEMPO REAL
FACULTAD DE CIENCIAS

© Javier Gutiérrez, Michael González

6/nov/08

15

Notas:

UNIVERSIDAD DE CANTABRIA

El problema del coloreado de grafos tiene muchas aplicaciones. Por ejemplo, se puede usar para
diseñar un sistema de semáforos en el que el objetivo es obtener un conjunto, lo más pequeño
posible, de giros permitidos para asociar una fase de los semáforos a cada grupo.

GRUPO DE COMPUTADORES Y TIEMPO REAL
FACULTAD DE CIENCIAS

© Javier Gutiérrez, Michael González

6/nov/08

16

Algoritmo Voraz

U