PDF de programación - Lenguaje de Diseño - Resolución de problemas de algoritmos

Lenguaje de Diseño

Resolución de Problemas y Algoritmos

Ingeniería en Computación
Ingeniería en Informática

Universidad Nacional de San Luis

Departamento de Informática

Año 2015

Índice general

1. Lenguaje de Diseño de Algoritmos

1.1.
Introducción . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.2. Facilidades Provistas por un Lenguaje de Diseño . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.3. Formalización de Algoritmos
1.3.1. Formalización del Ambiente de un Problema . . . . . . . . . . . . . . . . . . .
1.3.2. Prueba de Algoritmos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.3.3. Precisiones acerca de los Objetos . . . . . . . . . . . . . . . . . . . . . . . . . .
1.4. Expresiones . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.4.1. Expresiones Aritméticas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.4.2. Expresión Relacional . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.4.3. Expresiones Lógicas
1.4.4. Asignación Carácter . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.5. Acciones Primitivas de Entrada - Salida de Datos . . . . . . . . . . . . . . . . . . . . .
1.5.1. Entrada de Datos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.5.2. Salida de Datos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.6. Estructuras de Control . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Introducción . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.6.1.
. . . . . . . . . . . . . . . . . . . . . . . .
1.6.2. La Estructura de Control Secuencial
1.6.3. La Estructura de Control Condicional
. . . . . . . . . . . . . . . . . . . . . . .
1.6.4. Estructura de Control de Repetición . . . . . . . . . . . . . . . . . . . . . . . .

2. Estructuración de Datos

2.1.
Introducción . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.2. Arreglo Lineal . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.2.1. Operaciones con arreglos: Asignación y recuperación de valores . . . . . . . . .

3. Subalgoritmos

3.1.
Introducción . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.2. Definición de Subalgoritmos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.3.
. . . . . . . . . . . . . . . . . . . . . . . . . .
3.4. Anexo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Invocación y Retorno de Subalgoritmos

2
2
2
3
3
6
7
8
8
13
16
17
17
17
17
19
19
19
19
26

31
31
31
36

40
40
41
42
57

1

Capítulo 1

Lenguaje de Diseño de Algoritmos

1.1.

Introducción

Un programa es un modelo de resolución de un problema escrito en un lenguaje de programación.

De la definición anterior se desprende que escribir un programa implica:

1. Obtener una solución de un problema.
2. Expresar esta solución en un lenguaje de programación.

En general se puede decir que existe una distancia o diferencia entre lo que se podría denominar
el lenguaje del problema y el lenguaje de programación, en el sentido que el primero resulta
menos rígido y con más posibilidades de expresión que el segundo.

El objetivo fundamental de un lenguaje de diseño es ser comprensible para las personas que van
a interpretar los algoritmos escritos en él, mientras que el fin último de un lenguaje de programación
es ser comprensible por la computadora que va a ejecutar el programa.

La finalidad de un lenguaje de diseño es brindar una herramienta que sirva de apoyo para el
desarrollo de algoritmos. La idea es no sumar, a la complejidad del problema, las limitaciones impuestas
por una notación estricta. Además, en muchas aplicaciones, es importante conseguir un algoritmo
independiente del lenguaje de programación o lenguaje de implementación.

En general, cada programador, de acuerdo con su experiencia y habilidad, encontrará más expresiva
una notación u otra. Imponer una notación específica, si bien, en parte implica contradecir los objetivos
iniciales que justificaron el uso de los lenguajes de diseño, con la finalidad de comunicarnos, durante
lo que resta del desarrollo del curso, necesitamos establecer algunas pautas para el lenguaje de diseño
de algoritmos que usaremos.

1.2. Facilidades Provistas por un Lenguaje de Diseño

Los objetivos básicos de un lenguaje de diseño son:

1. Servir de apoyo durante el proceso de resolución de un problema.

2. Servir como etapa previa al proceso de codificación. La tarea de traducción del lenguaje de

diseño a cualquier lenguaje de programación no debería ser muy complicada.

2

Lenguaje de Diseño

3. En los proyectos de desarrollo de software, en los que intervienen varias personas, el lenguaje de
diseño debería permitir que cada una de ellas pueda tener una visión global del trabajo de los
demás, difícil de conseguir analizando directamente los programas del resto del grupo.

4. Como los lenguajes de programación proveen diferentes conjuntos de primitivas y la traducción
al lenguaje de programación es posterior al diseño, podemos elegir el lenguaje de programación
apropiado según el conjunto de primitivas requerido.

Nuestra intención será, entonces, proponer un lenguaje de diseño de algoritmos que sirva
de apoyo para la resolución de problemas y pueda ser traducido, en forma sistemática, a un programa.

1.3. Formalización de Algoritmos

Previo a la definición de nuestro lenguaje de diseño, necesitaremos precisar algunos conceptos. De
ahora en adelante, el (procesador), como lo hemos definido en nuestro contexto, es equivalente a una
computadora. La construcción del algoritmo es la etapa más dificultosa y, en éste y los próximos
capítulos, daremos las herramientas básicas necesarias.

Las computadoras, como ya fue indicado, no pueden ejecutar directamente los algoritmos en forma
literal como los venimos tratando. Es necesario codificarlos en un lenguaje de programación. En la ma-
yor de los casos, la codificación no presenta grandes dificultades ya que, los lenguajes de programación
tienden, cada vez más, a la formalización que se propone, cambiando esencialmente su sintaxis.

1.3.1. Formalización del Ambiente de un Problema

Lo primero a considerar en el proceso de resolución de problemas es la formalización de su ambien-
te. Vamos a definir un conjunto de reglas que nos permitirán describir, con precisión y sin ambig¨uedad,
los objetos del universo de un problema.

Una característica que diferencia entre sí a los objetos, es que cada uno tiene un nombre que lo
identifica unívocamente, o sea, si queremos citar diferentes objetos, damos una lista de sus nombres o
identificadores.

Además, cada objeto tiene un uso específico que no se puede intercambiar. En el ejemplo de la
calculadora, dado anteriormente, las teclas <dig> y <C>, tienen usos completamente diferentes; sin
embargo las teclas <1>, <2>,...., <0> si bien su uso es diferente (no es lo mismo oprimir la tecla
<1> que la tecla <2>), tienen una utilidad similar (sirven para oprimir dígitos).

Podemos decir que cada objeto tiene un tipo particular que indica características comunes a todos

los estados posibles del objeto.

Los objetos más simples con los cuales nosotros trabajaremos durante el curso
son los objetos numéricos: enteros y reales; los lógicos y los caracteres.

Otra característica importante de los objetos es su valor.
En cada instante, todo objeto del ambiente tiene un valor, para algunos objetos, este valor puede

cambiar luego de la ejecución de una acción.

Continuando con el ejemplo de la calculadora, en la versión 1 del algoritmo, en la acción “oprimir
número”, el objeto “número” toma el valor 124 la primera vez que la acción es ejecutada, el valor 59
la segunda vez y, la última vez, el valor 3. También existen objetos cuyos valores nunca cambian, por
ejemplo, “oprimir <9>” el objeto 9 nunca cambia su valor.

2015 - Departamento de Informática - Universidad Nacional de San Luis

3

Lenguaje de Diseño

Para resumir, podemos imaginarnos a los objetos de un ambiente como celdas rotuladas (por el
nombre), donde además las celdas tienen un tamaño determinado (según el tipo) y contienen una
información (un valor posible del conjunto de valores de un tipo dado)

128

a

NUMERO LETRA

Veamos un ejemplo para mostrar las características o atributos de los objetos del ambiente de un
problema.

Enunciado: Se tiene un objeto de nombre NUMERO, de tipo numérico, tal que su valor puede
ser un número entero positivo. Se quiere encontrar un algoritmo que determine el producto de los n
primeros números enteros positivos (es decir, el factorial de n = n!).
Las acciones primitivas que puede ejecutar el procesador son:

1. Dar un valor a un objeto.
2. Calcular la suma de dos números.
3. Calcular el producto de dos números.

El procesador además interpreta la condición: “un número es menor o igual que otro” y un esquema
repetitivo condicionado del tipo MIENTRAS <condición> HACER <acciones primitivas>
FINMIENTRAS la cual significa que el procesador ejecutará las acciones primitivas siempre que la
condición se cumpla.

Una vez planteado el problema y conociendo las acciones primitivas que puede reconocer el proce-

sador deberemos describir el ambiente sobre el cual trabajará.

El ambiente consiste del objeto ya descripto NUMERO. El valor inicial de este objeto ha sido
determinado (en algún momento) y va a servir para la realización del cálculo (establece hasta que
número deberé realizar los productos):

Si el valor inicial es 4, se calculará: 1 x 2 x 3 x 4 = 24 = 4!
Si el valor inicial es 5, se calculará: 1 x 2 x 3 x 4 x 5 = 1