PDF de programación - Parte I: El computador y el proceso de programación - 2. Introducción al análisis y diseño de algoritmos

Parte I: El computador y el proceso de
programación
• 1.Introducción a los computadores y su programación
• 2. Introducción al análisis y diseño de algoritmos
• 3. Introducción al análisis y diseño de programas
• 4. Verificación de programas

UNIVERSIDAD
DE CANTABRIA

DEPARTAMENTO DE MATEMÁTICAS,
ESTADÍSTICA Y COMPUTACIÓN
4

© Michael González Harbour

19/ma/09

1

Notas:

UNIVERSIDAD
DE CANTABRIA

1. Introducción a los computadores y su programación

• Arquitectura básica de un computador.El software del sistema. Lenguajes de Alto Nivel. El proceso de

compilación. El ciclo de vida del software.

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

• Diseño de un programa. Concepto de algoritmo. Descripción de algoritmos: el pseudolenguaje.

Tiempo de ejecución de algoritmos. La notación O(n). Ejemplos de análisis.

3. Introducción al análisis y diseño de programas

• Actividades del ciclo de vida del software. Paradigmas de desarrollo de programas. Análisis y

especificación. Diseño arquitectónico. Técnicas de diseño detallado.

4. Verificación de programas

• Importancia de la verificación. Estrategias de prueba. Depuración. Elección de datos para la prueba.

DEPARTAMENTO DE MATEMÁTICAS,
ESTADÍSTICA Y COMPUTACIÓN

© Michael González Harbour

19/ma/09

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

Programa

final

Pruebas

e Integración

Codificación

Diseño
Detallado

Módulos de
Programa

Diseño de cada

Módulo (pseudocódigo)

DEPARTAMENTO DE MATEMÁTICAS,
ESTADÍSTICA Y COMPUTACIÓN

© Michael González Harbour

19/ma/09

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.

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

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

DEPARTAMENTO DE MATEMÁTICAS,
ESTADÍSTICA Y COMPUTACIÓN

© Michael González Harbour

19/ma/09

4

UNIVERSIDAD
DE CANTABRIA

2. Concepto de algoritmo
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
A un algoritmo que suministra una solución buena, pero no
necesariamente óptima, se le denomina algoritmo heurístico
Un algoritmo recursivo es aquel definido en términos de sí mismo

DEPARTAMENTO DE MATEMÁTICAS,
ESTADÍSTICA Y COMPUTACIÓN

© Michael González Harbour

19/ma/09

5

Notas:

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 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.

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:

n!

=

1 si
,
1–(
n

n

⋅

)! si

,

n

0=
n

0>

DEPARTAMENTO DE MATEMÁTICAS,
ESTADÍSTICA Y COMPUTACIÓN

© Michael González Harbour

19/ma/09

6

3. Descripción de algoritmos
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

UNIVERSIDAD
DE CANTABRIA

- 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

DEPARTAMENTO DE MATEMÁTICAS,
ESTADÍSTICA Y COMPUTACIÓN

© Michael González Harbour

19/ma/09

7

Notas:

UNIVERSIDAD
DE CANTABRIA

Un algoritmo se puede especificar mediante la utilización de un lenguajes 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.

DEPARTAMENTO DE MATEMÁTICAS,
ESTADÍSTICA Y COMPUTACIÓN

© Michael González Harbour

19/ma/09

8

Ejemplos

UNIVERSIDAD
DE CANTABRIA

factorial=1;
para i desde 1 hasta N lazo

factorial=

factorial*i;

fin de lazo;

Pseudocódigo

Comienzo

Factorial=1

i=1

SI

i>N?

NO

Fin

Factorial=Factorial*i

i=i+1

Diagrama de flujo

DEPARTAMENTO DE MATEMÁTICAS,
ESTADÍSTICA Y COMPUTACIÓN

© Michael González Harbour

19/ma/09

9

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.

DEPARTAMENTO DE MATEMÁTICAS,
ESTADÍSTICA Y COMPUTACIÓN

© Michael González Harbour

19/ma/09

10

Ejemplo de refinamiento paso a paso
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

UNIVERSIDAD
DE CANTABRIA

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

DEPARTAMENTO DE MATEMÁTICAS,
ESTADÍSTICA Y COMPUTACIÓN

© Michael González Harbour

19/ma/09

11

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 mas pequeño posible, de giros
permitidos para asociar una fase de los semáforos a cada grupo.

Un posible algoritmo heurístico es el conocido como algoritmo voraz, que se puede describir en una primera
instancia mediante lenguaje natural:

1. Seleccionar un vértice no coloreado aún, y asignarle un color
2. Recorrer la lista de vértices sin colorear. Para cada uno de ellos determinar si tiene un arco

conectándolo con cualquier otro vértice coloreado con el nuevo color. Si no existe tal arco, colorear
ese vértice con el nuevo color

Este algoritmo voraz, por ejemplo, no encontraría la solución indicada arriba si se recorren los vértices
según el orden de su numeración, sino que asignaría:

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

Que es una solución peor.

DEPARTAMENTO DE MATEMÁTICAS,
ESTADÍSTICA Y COMPUTACIÓN

© Michael González Harbour

19/ma/09

12

Ejemplo de refinamiento (cont.)
Se muestra aquí la primera aproximación del pseudocódigo:

UNIVERSIDAD
DE CANTABRIA

método Voraz (Grafo G, Lista nuevo_color) es

-- Asigna a la lista de vértices nuevo_color, los vértices
-- del grafo G a los que se les puede dar el mismo color

comienzo

nuevo_color = vacío;
para cada vértice v no coloreado en G lazo

si v no es adyacente a ningún vértice en nuevo_color entonces



colorea v;
añade v a nuevo_color;

fin si;
fin lazo;

fin Voraz;

DEPARTAMENTO DE MATEMÁTICAS,
ESTADÍSTICA Y COMPUTACIÓN

© Michael González Harbour

19/ma/09

13

Notas:

UNIVERSIDAD
DE CANTABRIA

Segunda aproximación del pseudocódigo:
método Voraz (Grafo G, Lista nuevo_color) es

-- Asigna a la lista de vértices nuevo_color, los vértices
-- del grafo G a los que se les puede dar el mismo color

comienzo

nuevo_color = vacío;
para cada vértice v no coloreado en G lazo

encontrado = falso;
para cada vértice w en nuevo_color lazo

si h