PDF de programación - PROGRAMACIÓN (PRG). EUI. Curso 2001/2002 - Tema 1. INTRODUCCIÓN

PROGRAMACI ÓN (PRG). EUI. Curso 2001/2002

T ema 1. INTRODUCCI ÓN

DSIC.- F. Marqués y N. Prieto

Índice General

1 Problemas, algoritmos y programas

2 Programas y la actividad de la programación

3 Lenguajes y modelos de programación

4 La programación orientada a objetos. El lenguaje Java

5 Ejemplos

1

4

5

7

8

1 Problemas, algoritmos y programas

Los conceptos que se desarrollarán a continuación son fundamentales en la mecanización
del cálculo, objetivo de gran importancia en el desarrollo cultural humano pero que ha
adquirido una relevancia extraordinaria con la aparición, y posterior universalización de
los computadores. Problemas, algoritmos y programas forman el tronco principal en
que se fundamentan los estudios de computación.

Dado un problema P , un algoritmo A es un conjunto de reglas, o instrucciones, que

definen cómo resolver P en un tiempo finito.

Aunque ”cambiar una rueda pinchada a un coche” es un problema que incluso puede
estudiarse y resolverse en el ámbito informático, no es el tipo de problema que habi-
tualmente se resuelve utilizando un computador. Por su misma estructura, y por las
unidades de entrada/salida que utilizan, los ordenadores están especializados en el trata-
miento de secuencias de información (codificada), como por ejemplo series de números,
de caracteres, de puntos de una imagen, muestras de una señal, etc.

Ejemplos más habituales de las clases de problemas que se plantearán se pueden
encontrar en el ámbito del cálculo numérico, del tratamiento de palabras, y de la repre-
sentación gráfica. Así, algunos ejemplos de problemas son:

• Determinar el producto de dos números multidígito a y b
• Determinar la raíz cuadrada positiva del número 2

1

1 PROBLEMAS, ALGORITMOS Y PROGRAMAS

2

• Determinar la raíz cuadrada positiva de un número n cualquiera
• Determinar si el número n, entero mayor que uno, es primo
• Dada la lista de palabras l, determinar las palabras repetidas
• Determinar si la palabra p es del idioma castellano
• Separar silábicamente la palabra p
• Ordenar y listar alfabéticamente todas las palabras del castellano
• Dibujar en la pantalla del ordenador un círculo de radio r

Como se puede observar, en la mayoría de las ocasiones, los problemas se definen de
forma general, haciendo uso de identificadores o parámetros (en los ejemplos esto es así
excepto en el segundo problema, que es un caso particular del tercero). Las soluciones
proporcionadas a esos problemas (algoritmos) tendrán también esa característica.

A veces los problemas están definidos de forma imprecisa puesto que los seres huma-
nos podemos, o bien recabar nueva información sobre ellos, o bien realizar presunciones
sobre los mismos. Cuando un problema se encuentra definido de forma imprecisa intro-
duce una ambig¨uedad indeseable, por ello, siempre que esto ocurra, se deberá precisar
el problema, eliminando en lo posible su ambig¨uedad. Así, por ejemplo, cuando en el
problema tercero se desea determinar la raíz cuadrada positiva de un número n, se puede
presuponer que dicho número n es real y no negativo, por ello redefinimos el problema
del modo siguiente: determinar la raíz cuadrada positiva de un número n, entero no
negativo, cualquiera.

Ejemplos de algoritmos pueden encontrarse en las secuencias de reglas aprendidas
en nuestra niñez y mediante las cuales realizamos operaciones básicas de números mul-
tidígito, como por ejemplo sumas, restas, productos y divisiones. Son algoritmos ya que
definen de forma precisa la resolución en tiempo finito de un problema de índole general.
En lo siguiente se introducen otros ejemplos de algoritmos:

Ejemplo de algoritmo: considérese el problema enunciado en el listado anterior: ¿es

n, entero mayor que uno, un número primo?

Como se recordará un número primo es aquel que sólo es divisible por el mismo o

por la unidad. Los siguientes son posibles algoritmos:

Algoritmo 1.-
Considerar todos los números comprendidos entre 2 y n (excluido)
para cada número de dicha sucesión comprobar si ese
número divide al número n.
Si ningún número divide a n, entonces n es primo.

El algoritmo siguiente es similar al anterior, ya que la secuencia de cálculos que
define para resolver el problema es idéntica a la definida por el algoritmo primero; sin
embargo, se ha expresado utilizando una notación diferente.

1 PROBLEMAS, ALGORITMOS Y PROGRAMAS

3

Algoritmo 2.- Seguir los pasos siguientes en orden ascendente:
Paso 1 - Sea i un número entero de valor igual a 2.
Paso 2 - Si i es igual a n parar, n es primo
Paso 3 - Comprobar si i divide a n, entonces parar, n no es primo
Paso 4 - Reemplazar el valor de i por i+1, volver al Paso 2

El tercer algoritmo para resolver el problema mantiene una estrategia similar a la
utilizada por los dos primeros: comprobaciones sucesivas de divisibilidad por números
anteriores; sin embargo, haciendo uso de propiedades básicas de los números, mejora a
los algoritmos anteriores al reducir mucho la cantidad de comprobaciones de divisibilidad
efectuadas.

Algoritmo 3.- Seguir los pasos siguientes en orden ascendente:
Paso 1 - Si n vale 2 entonces parar, n es primo
Paso 2 - Si n es múltiplo de 2 (acaba en 2,4,6,8) acabar, n no es primo
Paso 3 - Sea i un número entero de valor igual a 3
Paso 4 - Si i es mayor que la raíz cuadrada positiva de n

parar, n es primo

Paso 5 - Comprobar si i divide a n, entonces parar, n no es primo
Paso 6 - Reemplazar el valor de i por i+2, volver al Paso 4

Ejemplo de algoritmos: Palabras repetidas de la lista l

Algoritmo 1.-
- Ordenar la lista alfabéticamente,
- Recorrer la lista,

si dos elementos consecutivos son iguales,
entonces estaban repetidos, escribirlos

Algoritmo 2.-
- Recorrer la lista,

para cada elemento comprobar (recorriendo de nuevo la lista)
si está repetido y entonces escribirlo

Como es fácil ver, la descripción o nivel de detalle de la solución de un problema en
términos algorítmicos depende de qué o quién debe entenderlo, resolverlo e interpretarlo.
Para facilitar la discusión se introduce el término genérico procesador. Se denomina
procesador a cualquier entidad capaz de interpretar y ejecutar un cierto repertorio de
instrucciones.

Un programa es un algoritmo escrito con una notación precisa para que pueda ser
ejecutado por un procesador. Habitualmente, los procesadores que se utilizarán serán
computadores con otros programas para facilitar el manejo de la máquina subyacente.
Cada instrucción al ejecutarse en el procesador supone cierto cambio o transfor-
mación, de duración finita, y de resultados definidos y predecibles. Dicho cambio se

2 PROGRAMAS Y LA ACTIVIDAD DE LA PROGRAMACI ÓN

4

produce en los valores de los elementos que manipula el programa. En un instante dado
el conjunto de dichos valores se denomina el estado del programa.

Denominamos cómputo a la transformación de estado que tiene lugar al ejecutarse

una o varias instrucciones de un programa.

2 Programas y la actividad de la programación

Como se ve, un programa es la definición precisa de una tarea de computación; siendo el
propósito de un programa su ejecución en un procesador; y suponiendo dicha ejecución
cierto cómputo o transformación.

Para poder escribir programas de forma precisa y no ambigua es necesario definir
reglas que determinen tanto lo que se puede escribir en un programa (y el procesador
podrá interpretar) como el resultado de la ejecución de dicho programa por el procesador.
Dicha notación, conjunto de reglas y definiciones, es lo que se denomina un lenguaje de
programación. Más adelante se estudiarán las características de algunos de ellos.

Como es lógico, el propósito principal de la programación consiste en describir la
solución computacional (eficiente) de clases de problemas. Aunque hay que destacar
que se ha demostrado la existencia de problemas para los que no puede existir solución
computacional alguna, lo que implica una limitación importante a las posibilidades de
la mecanización del cálculo.

Adicionalmente, los programas son objetos complejos que habitualmente necesitan
modificaciones y adaptaciones. De esta complejidad es posible hacerse una idea si se
piensa que algunos programas (la iniciativa de defensa estratégica de los EEUU, por ej.)
pueden contener millones de lineas y que, por otro lado, un error en un único carácter
de una sola linea puede suponer el malfuncionamiento de un programa (así, por ej. el
Apollo XIII tuvo que cancelar, durante el trayecto, una misión a la luna debido a que
en un programa se había sustituido erróneamente una coma por un punto decimal).

Debido a la complejidad mencionada, se considera que los programas tienen un ciclo

de existencia que está formado, a grandes rasgos, por las dos etapas siguientes:

• Desarrollo: creación inicial y validación del programa
• Mantenimiento: correciones y cambios posteriores al desarrollo

También se puede establecer la siguiente subdivisión en función de la envergadura

del problema a resolver (y del tamaño del programa necesario para resolverlo)

• Programación a pequeña escala: número reducido de lineas de programa, inter-

vención de una sola persona, por ejemplo: un programa de ordenación.

• Programación a gran escala: muchas lineas de programa, equipo de programadores,

por ejemplo: desarrollo de un sistema operativo

3 LENGUAJES Y MODELOS DE PROGRAMACI ÓN

5

3 Lenguajes y modelos de programación

Los orígenes de los lenguajes de programación se encuentran en las máquinas. La llamada
máquina original de Von Neumann se diseñó a finales de los años 40 en Princeton(aunque
su diseño coincide en gran medida con el de la máquina de Charles Babbagge y Ada
Byron de 1880). Los mayoría de los ordenadores modernos tienen tanto en común con
la máquina original que se les denomina máquinas con arquitectura ”Von Neumann”.

La característica fundamental de dicha arquitectura es la