Módulo 1 - docentes.uni.edu.nidocentes.uni.edu.ni/fec/Giovanni.Saenz/archivos/Algoritmos y... · • Ingeniería del software ... ¿cómo es nuestro personal?, ¿en qué ... cumple

Módulo 1:

ALGORITMOS Y LENGUAJES DE PROGRAMACIÓN

1-1

SUMARIO

ALGORITMOS Y LENGUAJES DE PROGRAMACIÓN___________________________________________________________________ 1

SUMARIO _________________________________________________________________2 1.1 INTRODUCCIÓN __________________________________________________4 1.2 ALGORITMO _____________________________________________________4

1.2.1 Utilización de los algoritmos_______________________________________________7 1.2.2 Nivel de abstracción de los algoritmos ______________________________________8 1.2.3 Del algoritmo al programa _______________________________________________10 1.2.4 Máquinas algorítmicas __________________________________________________12 1.2.4.1 Clasificación de las máquinas algorítmicas_____________________12 1.2.4.2 Arquitectura de las máquinas algorítmica_______________________14

1.4 LENGUAJES DE PROGRAMACIÓN __________________________________16 1.4.1 Lenguaje máquina ______________________________________________________16 1.4.2 Traductores____________________________________________________________18 1.4.2.1 Compiladores_____________________________________________________20 1.4.2.1 Intérpretes______________________________________________________23

J-M Romo Uriarte 1-2


1.1 INTRODUCCIÓN El género humano ha sentido desde siempre la necesidad de procesar la información, es por ello que la ciencia que conocemos como informática tiene antiquísimos predecesores.

El término informática fue inventado en Francia en el año 1962 de la unión de las palabras Información Automática y es ampliamente utilizado en los países de influencia francófona. Sin embargo, es prácticamente desconocido en el resto del mundo que utiliza en su lugar Ciencia de la Computación

Comencemos pues determinando el ámbito en el que se mueve la informática o ciencia de la computación, según definición muy utilizada la ciencia de la computación es el área del saber que se ocupa de todos los aspectos relativos al diseño de computadoras, su utilización y el tratamiento automático de la información. De esa definición de la ciencia de la computación destacaríamos un par de elementos. Por una parte, que el objeto de estudio es la información y propósito el procesamiento de esa información. Por otra parte, que el tratamiento de la información es automática, esto es que el tratamiento se realiza mediante máquinas que llamamos computadoras. Los campos de investigación asociados a la ciencia de la computación son, entre otros:

• Algoritmos y estructuras de datos • Arquitectura de computadoras • Inteligencia artificial • Robótica • Bases de datos • Comunicación hombre-máquina • Cálculo • Sistemas operativos • Lenguajes de programación • Ingeniería del software

Evidentemente no podremos abordar todos esos temas en un espacio tan escueto como el reservado a este texto. Nuestro objetivo es aprender los principios de la programación utilizando para ello el lenguaje Java, lo cual significa que el estudiante aprenderá a formular de manera formal el ejercicio propuesto y será capaz de escribir el programa que soluciona el problema planteado.

1.2 ALGORITMO Es el concepto fundamental de la Ciencia de la Computación. Antes de definir lo que se entiende por algoritmo hagamos una aproximación intuitiva a esta importante noción. La programación de computadoras es una tarea muy reciente. Pero puesto que la “programación“ implica buscar solución a los problemas, esto significa que la programación es tan antigua como la existencia de problemas, lo cual nos lleva a preguntarnos qué pasos se deben dar en la solución de un problema (independientemente de la utilización o no de computadoras). En esencia los pasos son cuatro, estos:

1. Comprensión del problema. El problema se debe describir con total precisión. Este paso de conocimiento del problema, a pesar de ser evidente, no siempre se ejecuta correctamente, lo cual posteriormente entraña grandes dificultades.


2. Planificación de la solución del problema. Cuando sabemos con seguridad qué es lo que tenemos que solucionar, podemos plantearnos otras preguntas que nos dan pistas del cómo debemos abordar su solución: ¿con qué recursos contamos?, ¿qué tipo de equipamiento tenemos?, ¿cómo es nuestro personal?, ¿en qué plazo se debe entregar?, ¿se deben subcontratar trabajos?, ¿cómo se combinan todos los recursos?, etc.

3. Ejecución del plan. Puesto que se cuenta con un plan detallado que responde a los requerimientos planteados y se ajusta a nuestras propias posibilidades, se está en condiciones de comenzar su ejecución. Esto es, cuando sabemos qué es lo que tenemos que hacer y hemos meditado el cómo hacerlo nos pondremos a trabajar.

4. Evaluación de la solución. La pregunta clave en este paso es ¿nuestro producto cumple las especificaciones del cliente?.

En la búsqueda de la solución según esos cuatro pasos no se ha indicado que la problemática a tratar deba girar en torno a la Ciencia de la Computación, esos cuatro pasos constituyen una forma de actuar que es un esquema absolutamente general. Dando el salto al mundo de computación, para obtener el programa que soluciona un determinado problema informático los cuatro pasos se formularían así:

1. Definición del problema 2. Invención del algoritmo 3. Convertir el algoritmo en programa 4. Evaluar la solución

Por tanto, y esto es importantísimo, antes de escribir un programa hay que concebir un algoritmo. Pero, ¿qué es un algoritmo? Comencemos dando la definición formal de algoritmo pero adelantando que no nos importa demasiado dicha definición y sí su adecuada comprensión intuitiva.

Algoritmo es un conjunto finito de instrucciones, las instrucciones son ejecutables y no existe ambigüedad entre ellas, además la tarea llevada a cabo por las instrucciones tiene fin

Los ejemplos más clásicos que ilustran el concepto de algoritmo son las recetas. Por ejemplo, hemos traducido este algoritmo del libro Denok Sukaldari (la traducción del título sería: Todos Cocineros) escrito por el afamado chef Pedro Subijana:

CREMA DE PORRUSALDA CON BACALAO

Ingredientes para 4 personas puerros: 375 gr cebolla: 180 gr patata: 470 gr bacalao: 200 gr dos dientes de ajo aceite Modo de actuar 1. Cortar los puerros y apartar los trozos más suaves para

utilizarlos en la presentación del plato

2. Cocer el resto de trozos en una cazuela


3. Añadir la cebolla troceada y las patatas peladas, rociar con aceite y dejar a fuego lento hasta que comience a hervir hierba (aproximadamente unos 40 minutos).

4. Mientras tanto, desmigar el bacalao desalado pasarlo por la sartén junto con el ajo desmigado y un poco de aceite, sacar de la sartén cuando evapore toda el agua.

5. Cuando la porrusalda esté hecha pasarla por un colador hasta que quede bien fina y añadir el bacalao.

6. Para finalizar, pasar vuelta y vuelta por la sartén los trozos de puerro apartados al principio, extender los puerros encima de la crema.

Dado que los algoritmos sirven para transmitir ideas, pueden ser gráficos. Por ejemplo, las hojas que indican la forma en que se monta este juguete es un algoritmo:


1.2.1 Utilización de los algoritmos Los algoritmos se han utilizado desde siempre. Existen algoritmos para preparar comidas los cuales denominamos recetas, otros algoritmos serían lo que conocemos como partituras de música, los procedimientos para cuidar las plantas domésticas también son algoritmos, los libros de magia son libros que compilan algoritmos (puesto que los trucos se explican paso a paso), los itinerarios de muchos libros de montaña están expresados algorít-micamente. Hay constancia de que en la antigua Mesopotamia se utilizaban algoritmos, en la Grecia clásica el matemático Euklides formuló un algoritmo que ha llegado hasta nuestros días, el algoritmo de Euklides sirve para calcular el m.c.d. (máximo común divisor) de dos números, y dice así:: Problema general:

Obtener el máximo común divisor de dos números. Datos de entrada

Dos cantidades enteras y positivas. Proceso:

El algoritmo tiene tres pasos, el primero es una inicialización y los otros dos se pueden repetir varias veces.

1. De los datos llamaremos M al mayor de los valores, el menos de los dos valores será N.

2. Se calcula la división de M entre N, llamaremos R al resto de la división de M entre N

3. Cuando R no es cero: asignar a M el valor de N asignar a N el valor de R volver al segundo paso, si R es cero, el valor del m.c.d. está contenido en N

Ejemplo:

M N R Cociente 36 16 4 2 16 4 0 4

m.c.d. 4

Datos 36 y 16

Una vez inventado el algoritmo, para obtener el m.c.d. de dos números es suficiente aplicar dicho algoritmo sin necesidad de “entender” el significado de cada paso. Por ejemplo para calcular el máximo común divisor de 7 y 11, nos limitaríamos a completar la siguiente tabla sin pensar demasiado de la razón última de cada columna:

M N R Cociente 11 7 4 1 7 4 3 1 4 3 1 1 1 1 0 1

m.c.d. 1

Datos 11 y 7


Por decirlo de alguna forma sencilla de entender, el conocimiento necesario para el cálculo del m.c.d. está prendido en el algoritmo y quien lo tenga que aplicar no tiene por qué ser un gran matemático, es más, es posible que una máquina autómata sea la que construya la tabla y nos dé la solución. Formulando esta idea de forma inversa, dado un problema si no somos capaces de generar un algoritmo será imposible que una computadora halle la solución al problema planteado. Para entender mejor los algoritmos se acostumbra a representar los pasos mediante un diagrama de flujo, para el ejemplo que nos ocupa el esquema sería:

SI

NO

m.c.d. =

En M el valor de N

En N el valor de

¿R vale cero?

Calcular la división entre M y N llamando R

al resto

El dato mayor M El dato menor N

1.2.2 Nivel de abstracción de los algoritmos Continuando con el algoritmo de Euklides, en el diagrama de flujo se ha escrito en negrita el paso según el cual se calcula la división entre dos números enteros. En este caso se ha supuesto que el usuario conozca el procedimiento para hallar el cociente y el resto de dos números enteros.

De igual manera en el quinto paso de la receta para preparar la crema de puerros con bacalao se dice:

5. Cuando la porrusalda esté hecha pasarla por un colador hasta

que quede bien fina y añadir el bacalao.

Como nos e ha especificado nada más, quien ha escrito la receta da por hecho que el encargado de aplicar el algoritmo sabrá cómo hacer que la crema quede bien fina. Quien escribe un algoritmo determina hasta qué nivel de detalle desea descender, suponiendo para ello con que el usuario del algoritmo deberá contar con ciertos conocimientos. ¿Cómo modificaríamos el algoritmo de Euklides para detallar la operación de dividir?. Supuesto que el usuario sea capaz de restar dos números y de comparar cuál de ellos es el mayor, es posible descomponer la división en un conjunto de restas sucesivas. El lector ya estará dándose cuenta de que la forma de calcular la división sobre la base de restas es en sí mismo un algoritmo. Pues bien, y esta es la esencia de este apartado, este segundo algoritmo puede ser insertado en el de Euklides sin modificarlo, se trata únicamente de detallar paso a paso una de las operaciones del algoritmo original.


Este es el algoritmo que resuelve la división y que incluiremos en el de Euklides:

SI

NO

R = M

Cálculo de M – N

y guardar en M

¿ N > M ?

Fijar M y N Abstrayendo que el usuario del algoritmo tiene capacidad para calcular restas y comparaciones entre números, el algoritmo completo de Euklides queda:

N

SI

NO

m.c.d. =

En M el valor de N

En N el valor de

¿R vale cero?

El dato mayor M El dato menor N

SI

NO

R = M

Cálculo de M – N y guardar en M

¿N > M?

Fijar M y N

Tener el algoritmo es la condición necesaria para que una computadora pueda resolver el problema, pero no es la condición suficiente. Las computadoras únicamente comprenden instrucciones muy elementales, lo cual significa que las computadoras no “entienden” los algoritmos creados según la representación habitual de los humanos, por tanto habrá que transcribir el algoritmo en algo entendible por la computadora. Habrá que rescribir el algoritmo utilizando un lenguaje de programación para obtener lo que llamaremos programa.


1.2.3 Del algoritmo al programa Como ya se ha dicho para que la computadora pueda solucionar el problema planteado se debe convertir el algoritmo (la idea expresada en téminos de la comprensión humana) a un programa utilizando para ello un lenguaje de programación. Los lenguajes de programación son subconjuntos de los lenguajes naturales, es un minilenguaje con un reducido diccionario y una reglas muy precisas. Por ejemplo, para que una computadora calcule el m.c.d. (máximo común divisor) de dos números programaremos el conocido algoritmo de Euklides empleando para ello alguno de los lenguajes de programación existentes. Partimos del algoritmo que siempre será el mismo y obtenemos el programa que dependerá de la sintaxis y características del lenguaje. A título de ilustración, seguidamente mostramos el programa Java que implementa el algoritmo de Euklides, y, un poco más adelante se presenta el programa Pascal que también implementa el mismo algoritmo. public class Euklides

{ public static void main(String[] args) { int m, n, r; n = (int)(Math.random()*100 + 1); // Obtener n, valor entre 1 y 100 m = n + (int)(Math.random()*100); // Obtener m, valor mayor que n System.out.println("m = " + m); // Mostrar contenido de m System.out.println("n = " + n); // Mostrar contenido de n do // Repetir mientras que ... { r = m % n; // Calcular r, resto de la division if (r != 0) { m = n; // Asignar a la variable m el valor de n n = r; // Asignar a la variable n el valor de r } } while (r != 0); // ... mientras que r no valga cero System.out.println("m.c.d = " + n); // La solucion esta en la variable n } }

Al ejecutar el programa hemos obtenido los siguientes resultados:


El programa Pascal correspondiente al algoritmo de Euklides es el siguiente donde el paralelismo con el anterior programa Java es evidente:

{ EUKLIDES.PAS } PROGRAM Euklides ; VAR M, N, R : Integer ; BEGIN Randomize ; { Semilla de numeros aleatorios } N := Random(100) + 1 ; { Obtener N, valor entre 1 y 100 } M := N + Random(100) ; { Obtener M, valor mayor que N } WriteLn ('M = ', M) ; { Mostrar contenido de M } WriteLn ('N = ', N) ; { Mostrar contenido de N } REPEAT { Repetir hasta que ... } R := M MOD N ; { Calcular R, resto de la division } IF R <> 0 THEN BEGIN M := N ; { Asignar a M el valor de N } N := R ; { Asignar a N el valor de R } END ; UNTIL R = 0 ; { ... hasta que R valga cero } WriteLn ('m.c.d. = ', N) ; { La solucion esta en N } END.

Salvo el modo de presentación que depende del propio sistema de desarrollo, la ejecución del programa Pascal produce iguales resultados que los obtenidos por el programa Java. Por ejemplo:

El estudiante no tiene por qué entender ahora mismo ninguno de los dos programas, lo importante es comparar sus sentencias entre sí, y más importante aún emparejar ambos programas con el algoritmo de Euklides ya conocido. Uno de los objetivos de este curso será, precisamente, aprender a dar el salto desde los algoritmos a los correspondientes programas, es decir, utilizando los formalismos del lenguaje Java escribir los algoritmos que resuelven situaciones dadas. Demos por sentado que si, utilizando un lenguaje de computadora, un algoritmo se expresa como un programa la máquina será capaz de ejecutarlo. Por tanto, el “conocimiento” que hayamos incluido en el algoritmo será absorbido por la computadora a través del programa.


1.2.4 Máquinas algorítmicas Llamaremos máquina algorítmica al aparato capaz de ejecutar un algoritmo. Puesto que a la computadora se le indica lo que debe hacer mediante un programa se tendrá que emplear necesariamente un algoritmo que guíe su funcionamiento, es por ello que las computadoras son un tipo de máquinas algorítmicas. Dado que el concepto de algoritmo es más viejo que la Ciencia de la Computación, las máquinas algorítmicas son también invenciones antiguas entendiendo como máquina algorítmica aquella que funciona siguiendo los pasos marcados en su algoritmo.

1.2.4.1 Clasificación de las máquinas algorítmicas

Una máquina es un aparato o un sistema que funciona desarrollando cierta tarea. Las máquinas pueden funcionar de forma más o menos autónoma, o por el contrario pueden necesitar ser comandadas por un operario. Atendiendo al modo en que se controlan las máquinas se pueden clasificar en:

1. Máquinas no-automáticas 2. Máquinas automáticas 3. Máquinas programables

Expliquémoslas separadamente: 1. Máquinas no-automáticas El usuario debe manejar el aparato en todo momento, para

que el trabajo se ejecute la presencia del operario es imprescindible. Es cierto que la mayoría de estas máquinas suelen realizar de forma autónoma ciertas funciones pero no son suficientes como para conferirles la categoría de sistemas automáticos.

2. Máquinas automáticas El operador de la máquina no deben supervisar su funcionamiento

continuamente. Las máquinas que pueden ser consideradas automáticas completan su cometido de forma autónoma una vez de recibir del exterior las órdenes apropiadas.

La automatización es un grado y el abanico de máquinas más o menos automáticas es muy amplio, todas admiten una interre-lación con el usuario y funcionan de forma autónoma.

Cuando se diseña una máquina automática se decide cuál será su comportamiento futuro y su nivel de automatismo se implementa en sus componentes de una manera fija, es decir el algoritmo está integrado en la misma máquina. Si se quiere alterar las presta-ciones del aparato se debe desmontar máquina para aislar y cambiar el algoritmo que la gobierna.

Utilizamos el siguiente esquema para representar a los aparatos automáticos donde el algoritmo es parte integrante de la propia máquina:


respuesta de

salida (funcionamiento

)

excitaciones

de entrada Máquina

+ Algoritmo

Máquina

automática

Cambiar el algoritmo de las máquinas automáticas no es trivial, por tanto su funcionamiento es autónomo pero poco flexible.

3. Máquina programable Las máquinas programables son máquinas automáticas muy

sofisticadas. También recibirán los requerimientos del usuario, pero al contrario que las máquinas automáticas normales su comportamiento es ciertamente flexible.

Para garantizar que su funcionamiento sea flexible las máquinas programables se diseñan distinguiendo en ellas dos partes bien diferenciadas. Por un lado, se tiene lo que llamaremos máquina base se puede admitir que este componente es difícil de alterar para el usuario, y , por otra parte se tiene el otro componente que llamaremos programa que además de establer el comportamiento de la máquina posee la característica de ser fácil de cambiar:

programa

programa

máquina máquina base base

Componentes de la

máquina programable Máquina programable

El comportamiento de la máquina programable está determinado por la intervención de los dos componentes, como el programa es fácil de cambiar según las ocasiones la consecuencia es que el funcionamiento de la máquina programable es extremadamente flexible y adaptativo.

Recordando la clasificación hecha al principio de este apartado, y utilizando un ejemplo clásico, tenemos:

1. Piano: máquina no-automática para producir música, a medida que el pianista pulsa las teclas se oye la música.

2. Caja de música: máquina automática, al abrir su tapa se oirá la melodía. La música se toca automáticamente pero siempre es la misma pieza.

3. Tocadiscos: máquina programable, cambiando de disco se pueden tener diferentes conciertos, puede pasar fácilmente de aparentar un concierto de folk a oírse un concierto barroco. Además de sonar la música de forma automática, se puede cambiar muy fácilmente.

Diremos que la computadora es una máquina programable, pues se distinguen en su estructura los dos compontes de dicho tipo de máquinas. Además de la máquina base (en el


mundo de la computación se le conoce como hardware) la computadora dispone de un catálogo de programas que son fáciles de cargar. El conjunto hace que la computadora sea un aparato verdaderamente versátil, por ejemplo con el mismo hardware pero atendiendo al software cargado la computadora puede aparentar una máquina de escribir si en ese momento se está ejecutando un procesador de textos,o puede ser la mesa de diseño donde se dibujan los planos de un proyecto si tenemos un programa de CAD, o puede servir para llevar la contabilidad, o retocar imágenes digitales, o resolver sistemas de ecuaciones, o generar música, o graficar tablas de números, o ...

programa

A programa B

programa A programa

B

máquina máquina máquina máquina base base base base

Máquina A que tiene

cierto comportamiento

Máquina B que tiene cierto

comportamiento

1.2.4.2 Arquitectura de las máquinas algorítmica

Si tuviéramos que efectuar el cálculo del máximo común divisor de dos números utilizaríamos dos elementos. Uno, físico nuestro escritorio con papel y lápiz, y, otro intelectual que sería el algoritmo de Euklides. La combinación de ambos recursos elementales nos daría una solución parecida a esta:

m.c.d. 2 2

1 3 3 Donde, recordando el proceso que describe ele algoritmo de Euklides, tenemos los tres pasos marcados con sus respectivos números:

1. Llamremos M al mayor de los datos, N será el más pequeño de ellos. 2. Tras dividir M entre N se obtiene el resto R 3. Si R distinto de cero, asignar el valor de N a M, asignar el valor de R a N y volver al segundo; Paso, de lo contrario el m.c.d. coincide con el valor de N

Por tanto, siendo 36 y 16 los datos de entrada para calcular “a mano” el m.c.d. se realzan dos cometidos. Por una parte los valores deben ser guardados en algún lugar para que cuando sea oportuno se recuperen de ese almacén. En el ejemplo el dato 36 se almacena en la variable M (conceptualmente M es una variable pues cada vez puede ir tomando distintos valores), esta operación se conoce como almacenamiento de la información. El segundo cometido a realizar será el procesamiento de la información, que en nuestro ejemplo se sustancia en la ejecución de operaciones aritméticas y operaciones lógicas. Para obtener el valor de R se debe efectuar la división entre M y N, para detener el proceso repetitivo se debe comparar el valor de R con la constante cero (operación lógica).


Si en vez de hacerlo a mano, fuera una máquina la encargada de calcular el m.c.d. de 36 y 16, dicha máquina también necesitaría poseer esas dos características almacenamiento de la información (para guardar y recuperar valores) y procesamiento de la información (para ejecutar operaciones). En la arquitectura de las computadoras existen dos componentes perfectamente diferenciados que se ocupan de esas dos funciones: la memoria y la unidad procesadora.

Unidad

Procesadora

Memoria

En el anterior esquema se ve el núcleo de la computadora pero como ya sabemos las máquinas automáticas y las máquinas programables, para que se pongan en marcha, reciben del exterior las excitaciones del usuario. También a la computadora, se le deberá aportar el algoritmo programado y los datos que el programa necesita. Además, una vez de que la computadora haya realizado su trabajo tendrá que mostrar los rsultados al usuario (sacar la información al exterior de la máquina). En consecuencia, las acciones de una computadora serán cuatro, donde las dos dos primeras están relacionadas con la noción de entrada/salida y en algunos textos aparecen como una única función. He aquí la lista de funciones:

1. Aceptación de entradas. El usuario le aportará la información a la computadora, cuando de cimos información nos refereimos tanto a los datos como al programa. El dispositivo encargado de esta función es la unidad de entrada.

2. Generación de salidas. La computadora devolverá al exterior el resultado de la información ya procesada. El dispositivo encargado de esta función es la unidad de salida.

3. Almacenamiento de la información. La información se alamacena en la memoria de la computadora, desde la memoria la información puede ser llevada tanto a otros componentes internos de la unidad procesadora como a la unidad de salida.

4. Procesamiento de la información. El procesamiento de la información consiste en dos facetas. La computadora debe realizar operaciones aritméticas y operaciones lógicas, la computadura debe “entender” las intrucciones del programa y ejecutarlas.

y, el esquema más simple: La combinación de estos componentes constituye el hardware de la máquina programable, es decir la parte difícilmente alterable, la que hemos llamado de la máquina base. A la parte fija se le añade el programa que asbemos se puede cambian de forma sencilla.

programa programa

máquina máquina base base

Entradas / Salidas

Unidad

Procesadora

Memoria


1.4 LENGUAJES DE PROGRAMACIÓN Ya hemos visto lo que es un algoritmo, también hemos aprendido que para representar un algoritmo existen diversas posibilidades (el lenguaje natural, diagramas, dibujos, símbolos, etc). Al hacer la presentación del concepto de computadora hemos recalcado que por ser una máquina algorítmica tiene la posibilidad de ejecutar un conjunto de instrucciones. Pues bien, a la computadora se le introducen el conjunto de instrucciones mediante lo que se denomina programa. Los programas se pueden escribir utilizando diferentes lenguajes, por ejemplo: Cobol, Pascal, C, Ada, Java, Basic, Lisp, Logo, Prolog, y muchos más. El lenguaje es el nexo de unión entre el algoritmo y la computadora. Definimos el concepto de lenguaje de programación de la siguiente manera:

Un lenguaje de programación tiene como propósito conseguir la comunicación con la computadora, para ello cuenta con una colección de símbolos y un conjunto de reglas para la utilización de esos símbolos

Son tres las características de todo lenguaje de programación:

1. Los símbolos que se pueden utilizar

2. La sintaxis del lenguaje. Esto es, cómo se deben combinar los símbolos para escribir las instrucciones

3. La semántica del lenguaje. Es decir, cuál es el significado de una instrucción sintácticamente correcta

Es conocido que los circuitos de la computadora son capaces de interpretar y ejecutar las instrucciones de un programa, pero precisando más al lenguaje que “entiende” una computadora se le dice “lenguaje máquina”. Excepto en casos muy especiales el programador no escribe sus programas en lenguaje máquina si no que utiliza un lenguaje de alto nivel. En la siguiente figura se muestra la diferencia de posición entre el lenguaje máquina (más cercano a la computadora) y el lenguaje de alto nivel (más cercano al programador):

Lo que la máquina entienede

Lo que nosotros entendemos Computadora

Makina- lengoaia

Programa traductor

Lenguaje de alto nivel

Nosotros

Esta figura se explicará en detalle más adelante.

1.4.1 Lenguaje máquina Las computadoras están constituidas por componentes electrónicos digitales. Es por ello que tienen la capacidad de procesar bits, o lo que es lo mismo únicamente pueden entender dos estados (ceros y unos). En consecuencia los datos se le suministrarán a la computadora utilizando exclusivamente esos dos dígitos, y, el algoritmo se deberá programar también mediante esos dos dígitos.


Las CPUs (Unidad Central de Proceso) que existen en el mercado son, en general, distintas entre sí, y a cada CPU le corresponde su propio lenguaje máquina. Él lenguaje máquina se define así: el lenguaje que la computadora entiende, está representado en código binario y es dependiente del diseño de la computadora. El desarrollo de programas para una determinada computadora mediante su lenguaje máquina supondría una supondría un gran esfuerzo para el programador, si bien el programa conseguido serái directamente ejecutable en la computadora:

Nos es muy difícil de entender

Computadora

Lenguaje máquinaa

Nosotros

Lo que la máquina entiende El esquema es más sencillo pero inviable desde el punto de vista práctico pues el coste de programar en lenguaje máquina es enorme (los errores de programación se producen con mucha frecuencia, dichos errores son más difíciles de localizar y subsanar, el mantenimiento del programa es mucho más difícil, etc). Si de todas formas se consiguiera el programa en lenguaje máquina, además se tendría un problema importante problema añadido a las anteriores desventajas, no se podría ejecutar ese programa en una computadora de otro modelo cuyo lenguaje máquina fuera diferente al de la máquina original. Podríamos aprovechar el algoritmo pero su codificación debería rehacerse utilizando el lenguaje máquina de la nueva computadora:

Lenguaje máquina 1

Algoritmo A Programa LM1

Lenguaje Máquina 2

Algoritmo A Programa LM2

Funcionalmente el programa LM1 es equivalente al programa LM2 tal y como se representa en la siguiente figura, pero si comparáramos sus respectivos códigos entre sí se podría comprobar que son distintos.

Programa

LM1 Programa LM2

Datos Máquina Resultado Datos Máquina Resultad

o base 1 base 2


1.4.2 Traductores De la figura anterior se extraen dos conclusiones. Una, son los componentes básicos (el hardware) de una máquina programable los que marcan cómo ha de ser su lenguaje de programación. Llamando Máquina base 1 a la CPU que le corresponde a una computadora, le corresponderá un lenguaje máquina que llamaremos Lenguaje máquina 1 y los programas que aquella computado aceptará estarán escritos codificados según dicho lenguaje máquina. En este dibujo se presentan dos computadoras distintas donde las marcas LM1 y LM2 indican el lenguaje máquina que cada una de ellas comprende:

programa

LM1 programa LM2

máquina máquina base 1 LM1 base 1

LM2

Dos, se una computadora tiene que ejecutar un programa escrito en un lenguaje máquina distinto al suyo, dicho programa deberá ser traducido. La traducción la llevará a cabo una persona, o, podría hacerlo un programa de computadora. Supongamos que se desea ejecutar un programa codificado según LM2 en una computadora del tipo LM1, y que se dispone de un programa traductor que llamamos TraductordeLM2aLM1, se tratará de obtener la versión LM1 del programa original escrito en LM2. La solución tiene dos pasos:

1. Mediante el programa TraductordeLM2aLM1 se obtiene el programa programa LM2 que es la traducción del original programa LM1

2. Una vez conseguido el programa programa LM1 se carga en la computadora tipo LM1 y se le suministran los datos

En el primer paso le programa que guiará el quehacer de la computadora será el programa TraductordeLM2aLM1, el traductor estará escrito según el código de LM1 y por tanto podrá ser ejecutado sin problemas en esa máquina. Al programa traductor se le introducirá como dato el programa programa LM2 y como resultado devolverá programa LM1:

Traductor deLM2aLM1 LM1

programa LM2 máquina programa

LM1 base 1

LM1

En el segundo paso se ejecutará el programa programa ML2 en la computadora ML1, realmente se ejecutará programa ML1 que es una traducción de programa ML2. Para ello se retirará de la computadora el programa traductor que está cargado y se colocará en memoria el programa programa ML1:

Programa ML1

Datos máquina Resultad

o base 1

LM1



El resultado obtenido sería exactamente igual al que se lograría de tener una computadora LM2 y se ejecuta en ella el programa programa ML2 con los mismos de entrada. Recuperando el primer esquema que presentamos al comenzar este capítulo, ahora estamos en condiciones de ser más explícitos y entender mejor su significado. Al suministrar un algoritmo a una computadora lo programaremos escribiéndolo en un lenguaje cercano al idioma natural, es decir en un lenguaje de alto nivel, nos encontraremos en la necesidad de traducir dicho programa: Lo que la máquina entienede

Lo que nosotros entendemos Computadora

Makina- lengoaia

Programa traductor

Lenguaje de alto nivel

Nosotros Cuando programamos un algoritmo mediante un lenguaje de alto nivel damos la denominación de programa fuente o también código fuente al texto que recoge el conjunto de sentencias. Mediante un compilador o un intérprete se traducen esas sentencias al lenguaje máquina de la computadora, se obtienen as instrucciones en código binario y son susceptibles de ser ejecutadas por la computadora. El resultado de la traducción se llama lenguaje máquina o código máquina.

1.4.2.1 Compiladores

Los lenguajes de alto nivel deben ser traducidos al lenguaje máquina de la computadora en la que se desean ejecutar, atendiendo al modo de realizar esa traducción hemos mencionado que se distinguen dos tipos de traductores: compiladores e intérpretes. El programa escrito en un lenguaje de alto nivel consiste en un texto legible que en Java contiene palabras como if, new, do, for, while, etc, a ese texto se le dice programa fuente y se consigue mediante un programa editor:

Editor LM

máquina base 1

LM

Programa fuente

if (x==0) sentencias de alto nivel

Lenguaje máquina Programa fuente

Compilador o

Intérprete

10110000 01101100 11101110 00001000

if (x==0)


Una vez obtenido el programa fuente se retira de la computadora el editor y se carga en memoria el programa compilador. Gracias a él el programa fuente es traducido obteniéndose el programa objeto que es una versión binaria del programa fuente pero al faltarle el código de las rutinas llamadas por el programador aún no es ejecutable:

Compilador LM

máquina base 1

LM

Tras el compilador entra en juego el programa linker que añade al programa objeto las rutinas no desarrolladas por el programador y que han sido utilizadas en el programa fuente, dichos trozos de código los enlaza el linker tomándolos de una desde una biblioteca de rutinas:

Linker LM

máquina base 1

LM

Programa fuente

if (x==0) 10110000 01101100 11101110 00001000

Programa objeto

10110000 01101100 11101110 00001000

Errutinak

11111100 01101100 11101000 00111000

Programa objeto

Programa ejecutable

01111011 10111100 01101100 11000010 01101110 11101111 00001000

Una vez obtenido el programa ejecutable se pueden introducir los datos y se obtendrían los resultados:

Programa ML

ejecutable

máquina base 1

LM

Datos

Resultados

Tal y como se ha visto, desde que tenemos el programa fuente hasta que se obtiene el programa ejecutable se dan dos pasos, en el primero el compilador traduce el código fuente y en el segundo el linker le añada las rutinas externas. Normalmente estos dos pasos se dan consecutivamente de forma que el desarrollador no los percibe como algo separado. Desde la perspectiva del programador producir un programa ejecutable supone recorrer el diagrama de flujo mostrado seguidamente:

SI

NO ¿errores?

cambios

programa ejecutable

compilar y

linkar

editar las instrucciones de alto nivel


Es inevitable que al programar se deslicen errores. Algunos de ellos se producen al editar las instrucciones de alto nivel, por tanto tras editar el programa fuente puede ser que el compilador detecte algunos errores. Los errores que es posible descubrir en la fase de compilación se clasifican en tres grupos:

1. Errores sintácticos, el error está originado por una instrucción que va en contra de las leyes del lenguaje. Por ejemplo porque en vez de la palabra reservada for se ha escrito la palabra F0R (donde además de las mayúsculas, en vez de la letra o se ha escrito un cero).

2. Errores de tipo, las variables y otras entidades de los programas se definirán según unos determinados tipos de datos y la mayoría de los lenguajes disponen de reglas muy estrictas para el control de las operaciones admitidas. Por ejemplo, si en una variable se guarda un nombre no será luego posible realizar operaciones aritméticas con ese dato.

3. Errores de declaración, en la mayoría de los lenguajes antes de utilizar una variable ha de ser declarada. Por ejemplo si se ha declarado una variable anchura y en una sentencia en vez de escribir anchura se escribe ancho el compilador hallará el error. En resumen, los errores de declaración surgen al utilizar un identificador no declarado previamente o al duplicar la declaración del mismo identificador.

Hasta enmendar todos los errores de compilación no se podrá conseguir el programa ejecutable pues el programa fuente no podrá ser traducido. Puede ser que se tenga un programa fuente correcto con respecto al cumplimiento de las reglas sintácticas del lenguaje, y sin embargo al ejecutar el programa los resultados obtenidos no se ajusten a los esperados. Por ejemplo, si un programa trata de hacer una división por cero o trata de abrir un fichero que no existe, surgen errores en tiempo de ejecución. Este diagrama considera las dos fases de depuración de programas compilados:

editar las instrucciones de

alto nivel

compilar y

linkar

programa ejecutable

cambios

¿errores?

NO

SI

ejecutar

cambios

¿funciona?

NO

datos resultados

fase compilación

fase ejecución

El proceso hasta lograr los resultados es aparentemente largo, pero téngase en cuenta que durante el desarrollo del programa se han de cubrir las dos etapas (etapa de compilación y etapa de ejecución), pero una vez testeado el programa su ejecutable lo podremos hacer funcionar tantas veces como queramos sin más que cargarlo en la computadora. Por tanto y dejando a un lado la perspectiva del desarrollador, el usuario del programa se ajustará al modo de operación que se resume en la siguiente figura:

resultados

datos

programa ejecutable

ejecutar


La ejecución del programa ejecutable no requiere mucho tiempo pues está en código máquina. Existe además otra buena razón para justificar el éxito de los lenguajes compilados, y es que el programador no tiene por qué proporcionar al usuario el programa fuente de la aplicación a ejecutar, de esta manera la propiedad intelectual queda preservada y para el usuario le resulta más fácil la ejecución de la aplicación pues no necesita ningún programa traductor.

1.4.2.1 Intérpretes

El intérprete es un programa traductor que se define de esta manera: programa que efectúa la traducción del código fuente al código máquina, pero de modo interactivo y sin crear ningún programa objeto, el intérprete toma el programa fuente sentencia a sentencia traduciendola y ejecutándola. Para que cada sentencia del programa fuente sea traducida y ejecutada el intérprete debe obtener las instrucciones elementales en lenguaje máquina. Por tanto, el intérprete guarda en su interior las correspondencias en bajo nivel de las sentencias de alto nivel. Cuando el lenguaje es interpretado, igual que el caso del lenguaje compilado, el primer paso consiste en editar el código fuente, pero posteriormente no se obtiene programa ejecutable:

Editor LM máquina base 1

LM

instrucciones de

alto nivel

if (x==0)

Programa fuente

Una vez obtenido el programa fuente se retira de la computadora el editor y se carga en memoria el programa intérprete, junto al intérprete se carga también en memoria el código fuente y sin más se puede ejecutar el programa. Para ello el intérprete toma la primera sentencia del programa fuente la traduce (genera las instrucciones de bajo nivel relativas a esa sentencia) y las ejecuta, si no se produce error el intérprete continúa con la segunda sentencia traduciéndola y ejecutándola. Si la sentencia en curso requiere algún dato se le suministrará desde el exterior como en el tiempo de ejecución de los programas compilados:

Intérprete LM

máquina base 1

LM

if (x==0)

Programa fuente

Datos

Resultados

Resumiendo, el intérprete trabaja sentencia a sentencia (traduciéndola y ejecutándola), y la pareja compilador/linker procesa todo el código fuente (traduce el programa fuente obteniendo el programa ejecutable que luego será ejecutado de forma independiente). Se puede decir que el modo de trabajo del intérprete comparado con el del compilador es más sencillo, pero remarcaríamos dos inconvenientes, por una parte la necesidad de la presencia del código fuente al ejecutar el programa, y, por otra este hecho tiene la consecuencia de que se ejecuta más lentamente pues la traducción se produce durante la propia ejecución.


En los lenguajes interpretados la búsqueda de los errores es más sencilla que en los lenguajes compilados, pues cuando se detecta un error se tiene la seguridad de que se ha producido en la sentencia en curso. Puesto que en los lenguajes interpretados la perspectiva del desarrollador y del usuario son la misma, el diagrama de ambos escenarios es único, éste:

SI

resultad ¿errores?

cambios

datos interpreta

r y

ejecutar

editar las instruccio

nes de alto nivel


Documents

Módulo 1 - docentes.uni.edu.nidocentes.uni.edu.ni/fec/Giovanni.Saenz/archivos/Algoritmos y... · • Ingeniería del software ... ¿cómo es nuestro personal?, ¿en qué ... cumple