PDF de programación - Capítulo 1 - Problemas, programas, estructuras y algoritmos

Capítulo 1

Problemas, programas, estructuras y
algoritmos

El proceso de resolución de problemas, en programación, está compuesto por una
serie de pasos que se aplican de forma metódica. Empieza con el análisis de las carac-
terísticas del problema, continúa con el diseño de una solución, la implementación
del diseño y termina con la verificación y evaluación del programa resultante. Los dos
ejes básicos en los que se articula el desarrollo de un programa son las estructuras de
datos y los algoritmos. Las estructuras de datos determinan la forma de almacenar
la información necesaria para resolver el problema. Los algoritmos manipulan esa
información, para producir unos datos de salida a partir de unos datos de entrada.
El objetivo último de la algorítmica es encontrar la mejor forma de resolver los
problemas, en términos de eficiencia y de calidad del software.

Objetivos del capítulo:

Entender el desarrollo de programas como un proceso metódico e ingenieril, formado por
una serie de etapas con distintos niveles de abstracción, frente a la idea de la programación
como arte.

Tomar conciencia de la importancia de realizar siempre un análisis y diseño previos del
problema, como pasos anteriores a la implementación en un lenguaje de programación.

Motivar el estudio de los algoritmos y las estructuras de datos, como una disciplina fun-
damental de la informática.

Repasar algunos de los principales conceptos de programación, que el alumno debe conocer
de cursos previos como: tipos de datos, estructuras de datos, tipos abstractos, algoritmos,
complejidad algorítmica y eficiencia.

Entender la importancia del análisis de algoritmos, el objetivo del análisis, los factores
que influyen y el tipo de notaciones utilizadas para su estudio.

Distinguir entre algoritmos y esquemas algorítmicos, presentando brevemente los princi-
pales esquemas algorítmicos que serán estudiados.

1

2

Capítulo 1. Problemas, programas, estructuras y algoritmos

Contenido del capítulo:

1.2. Tipos de datos

1.1. Resolución de problemas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.1.1. Análisis de requisitos del problema . . . . . . . . . . . . . . . . . . . . . .
1.1.2. Modelado del problema y algoritmos abstractos . . . . . . . . . . . . . . .
1.1.3. Diseño de la solución . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.1.4.
Implementación del diseño . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.1.5. Verificación y evaluación de la solución . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.2.1. Definición de tipo de datos, tipo abstracto y estructura . . . . . . . . . .
1.2.2. Tipos de tipos
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.2.3. Repaso de tipos y pseudolenguaje de definición . . . . . . . . . . . . . . .
1.3. Algoritmos y algorítmica . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.3.1. Definición y propiedades de algoritmo . . . . . . . . . . . . . . . . . . . .
1.3.2. Análisis de algoritmos . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.3.3. Diseño de algoritmos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.3.4. Descripción del pseudocódigo utilizado . . . . . . . . . . . . . . . . . . . .
1.4. Consejos para una buena programación . . . . . . . . . . . . . . . . . . . . . . .
1.4.1.
Importancia del análisis y diseño previos . . . . . . . . . . . . . . . . . . .
1.4.2. Modularidad: encapsulación y ocultamiento . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.4.3. Otros consejos
Ejercicios propuestos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Cuestiones de autoevaluación . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Referencias bibliográficas
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

3
3
4
5
6
7
7
8
10
12
14
15
17
21
25
26
26
28
29
31
31
32

1.1. Resolución de problemas

3

1.1. Resolución de problemas

La habilidad de programar ordenadores constituye una de las bases necesarias de to-
do informático. Pero, por encima del nivel de programación, la característica fundamental
de un informático es su capacidad para resolver problemas. La resolución de problemas
informáticos en la vida real implica otras muchas más habilidades que únicamente saber
programar –habilidades que distinguen a un ingeniero de un simple programador. Implica
comprender y analizar las necesidades de los problemas, saber modelarlos de forma abs-
tracta diferenciando lo importante de lo irrelevante, disponer de una variada batería de
herramientas conceptuales que se puedan aplicar en su resolución, trasladar un diseño abs-
tracto a un lenguaje y entorno concretos y, finalmente, ser capaz de evaluar la corrección,
prestaciones y posibles inconvenientes de la solución planteada.

Las herramientas que surgen en el desarrollo de programas son esencialmente de
dos clases: estructuras de datos y algoritmos. Las estructuras de datos representan la
parte estática de la solución al problema, el componente almacenado, donde se encuentran
los datos de entrada, de salida y los necesarios para posibles cálculos intermedios. Los
algoritmos representan la parte dinámica del sistema, el componente que manipula los
datos para obtener la solución. Algoritmos y estructuras de datos se relacionan de forma
muy estrecha: las estructuras de datos son manipuladas mediante algoritmos que añaden o
modifican valores en las mismas; y cualquier algoritmo necesita manejar datos que estarán
almacenados en cierta estructura. La idea se puede resumir en la fórmula magistral de
Niklaus Wirth: Algoritmos + Estructuras de datos = Programas.

En ciertos ámbitos de aplicación predominará la componente algorítmica –como,
por ejemplo, en problemas de optimización y cálculo numérico– y en otros la componente
de estructuras –como en entornos de bases de datos y sistemas de información–, pero
cualquier aplicación requerirá siempre de ambos. Esta dualidad aparece en el nivel abs-
tracto: un tipo abstracto está formado por un dominio de valores (estructura abstracta) y
un conjunto de operaciones (algoritmos abstractos). Y la dualidad se refleja también en el
nivel de implementación: un módulo (en lenguajes estructurados) o una clase (en lengua-
jes orientados a objetos) están compuestos por una estructura de atributos o variables, y
una serie de procedimientos de manipulación de los anteriores.

Antes de entrar de lleno en el estudio de los algoritmos y las estructuras de datos,

vamos a analizar los pasos que constituyen el proceso de resolución de problemas.

1.1.1. Análisis de requisitos del problema

El proceso de resolución de problemas parte siempre de un problema, de un enun-
ciado más o menos claro que alguien plantea porque le vendría bien que estuviera resuelto1.
El primer paso es la comprensión del problema, entender las características y peculiari-
dades de lo que se necesita. Este análisis de los requisitos del problema puede ser,
de por sí, una de las grandes dificultades; sobre todo en grandes aplicaciones, donde los
documentos de requisitos son ambiguos, incompletos y contradictorios.

1Esta afirmación puede parecer irrelevante por lo obvia. Pero no debemos perder de vista el objetivo

último de la utilidad práctica, en el estudio de los algoritmos y las estructuras de datos.

4

Capítulo 1. Problemas, programas, estructuras y algoritmos

El análisis debe producir como resultado un modelo abstracto del problema. El
modelo abstracto es un modelo conceptual, una abstracción del problema, que reside
exclusivamente en la mente del individuo y donde se desechan todas las cuestiones irre-
levantes para la resolución del problema. Supongamos, por ejemplo, los dos siguientes
problemas, con los cuales trabajaremos en el resto de los puntos.

Ejemplo 1.1 El problema de las cifras. Dado un conjunto de seis números enteros,
que pueden ser del 1 al 10, ó 25, 50, 75 ó 100, encontrar la forma de conseguir otro entero
dado entre 100 y 999, combinando los números de partida con las operaciones de suma,
resta, producto y división entera. Cada uno de los seis números iniciales sólo se puede
usar una vez.

Ejemplo 1.2 El problema de detección de caras humanas. Dada una imagen en
color en un formato cualquiera (por ejemplo, bmp, jpeg o gif) encontrar el número de
caras humanas presentes en la misma y la posición de cada una de ellas.

Figura 1.1: Ejemplos del problema de las cifras (izquierda) y detección de caras (derecha).

Ambos enunciados representan categorías de problemas muy distintas. El proble-
ma 1.1 tiene un enunciado más o menos claro, aunque cabrían algunas dudas. Es de
tipo matemático, se puede modelar formalmente y es previsible que exista un algoritmo
adecuado. El problema 1.2 tiene un enunciado más corto pero mucho más ambiguo, no
está claro exactamente lo que se pide. Es más, incluso teniéndolo bien claro, el problema
parece más adecuado para ser resuelto de cabeza por un humano, pero difícil de imple-
mentar en un ordenador. Aun así, ambos problemas tienen algo en común: son de interés,
así que necesitamos resolverlos de la mejor forma que podamos.

1.1.2. Modelado del problema y algoritmos abstractos

El primer paso sería crear un modelo abstracto, en el que nos quedamos con lo
esencial del problema. Normalmente, este modelo se crea a través de una analogía con
algo conocido previamente. Por ejemplo, para enseñar a un alumno inexperto lo que es un
algoritmo (concepto para él desconocido) se utiliza la analogía con una receta de cocina

1.1. Resolución de problemas

5

(concepto conocido, esperemos), y las estructuras de datos se asimilan con la disposición de
armarios, cajones y recipientes donde se guardan los ingredientes y el bizcocho resultant