1
Download UNIDAD I: Lenguajes y estructuras de programación
Document related concepts
Transcript
UNIVERSIDAD DE BUENOS AIRES - Facultad de Ciencias Económicas
Cátedra Teoría de Los Lenguajes y Sistemas Operativos
Teoría de los Lenguajes y Sistemas Operativos
Curso:
Juan José Arévalo Plá
Cátedra:
Víctor Veriansky
Página 1 de 61
UNIVERSIDAD DE BUENOS AIRES - Facultad de Ciencias Económicas
Cátedra Teoría de Los Lenguajes y Sistemas Operativos
Índice
UNIDAD I: Lenguajes y estructuras de programación
1. Tipos de lenguajes.
Estructuras.
Ámbito de aplicación.
Lenguajes orientados al problema.
Lenguajes de control.
2. Traductores de lenguaje.
Compaginadores, compiladores e intérpretes.
Características.
Vinculación.
3. Programas.
Constantes, variables y expresiones.
Tipos de instrucciones.
Bucles, contadores, acumuladores y selección.
4. Estructuras de datos.
Arreglos.
Ordenación, búsqueda e intercalación.
Estructuras dinámicas lineales.
Error! Bookmark not defined.
Error! Bookmark not defined.
Error! Bookmark not defined.
Error! Bookmark not defined.
Error! Bookmark not defined.
Error! Bookmark not defined.
Error! Bookmark not defined.
Error! Bookmark not defined.
Error! Bookmark not defined.
Error! Bookmark not defined.
Error! Bookmark not defined.
Error! Bookmark not defined.
Error! Bookmark not defined.
Error! Bookmark not defined.
Error! Bookmark not defined.
Error! Bookmark not defined.
Error! Bookmark not defined.
Error! Bookmark not defined.
UNIDAD II: Técnicas de Programación.
1. Programación convencional.
Programación modular.
Programación estructurada.
Estructuras de control y anidamiento.
Métodos de programación estructurada.
2. Declaración e invocación de funciones.
Definición de subrutinas.
Parámetros: métodos. Recursión.
3. Programación orientada a Objetos.
4. Tablas de decisión: reglas de decisión, tipos de tablas.
Construcción y encadenamiento.
5. Documentación de programas.
Pseudocódigos.
Autodocumentación.
Escritura de programas: cabecera, declaración de variables y constantes, comentarios.
Estilo de escritura y estándares.
Error! Bookmark not defined.
Error! Bookmark not defined.
Error! Bookmark not defined.
Error! Bookmark not defined.
Error! Bookmark not defined.
Error! Bookmark not defined.
Error! Bookmark not defined.
Error! Bookmark not defined.
Error! Bookmark not defined.
Error! Bookmark not defined.
Error! Bookmark not defined.
Error! Bookmark not defined.
Error! Bookmark not defined.
Error! Bookmark not defined.
Error! Bookmark not defined.
Error! Bookmark not defined.
Error! Bookmark not defined.
UNIDAD III: Lenguajes 4GL y generadores
1. Lenguajes orientados a usuarios finales.
Lenguajes de 4ta generación.
Lenguajes de cuarta generación
Lenguajes estructurados de recupero de información.
Elección del lenguaje.
2. Ayudas automatizadas de desarrollo y programas generadores para personal especializado.
Prototipos y modelización: herramientas y métodos para el desarrollo de prototipos.
Tendencias.
Estado del arte.
Error! Bookmark not defined.
Error! Bookmark not defined.
Error! Bookmark not defined.
Error! Bookmark not defined.
Error! Bookmark not defined.
Error! Bookmark not defined.
Error! Bookmark not defined.
Error! Bookmark not defined.
Error! Bookmark not defined.
Error! Bookmark not defined.
UNIDAD IV: SISTEMAS OPERATIVOS
1. Concepto y evolución.
Componentes y funciones.
2. Administración de los diversos componentes del sistema.
Administración del procesador.
Administración de la memoria.
Administración de los dispositivos
Administración de los archivos.
3. Análisis de los sistemas operativos más difundidos.
Tendencia.
Error! Bookmark not defined.
Error! Bookmark not defined.
Error! Bookmark not defined.
Error! Bookmark not defined.
Error! Bookmark not defined.
Error! Bookmark not defined.
Error! Bookmark not defined.
Error! Bookmark not defined.
Error! Bookmark not defined.
Error! Bookmark not defined.
Página 2 de 61
UNIVERSIDAD DE BUENOS AIRES - Facultad de Ciencias Económicas
Cátedra Teoría de Los Lenguajes y Sistemas Operativos
UNIDAD I: Lenguajes y estructuras de programación
1. Tipos de lenguajes.
Durante los últimos años los avances experimentados en materia de Hardware han sido enormes,
por ejemplo hace más de una década contábamos con las 386 DX con una velocidad de
procesador de 60MHZ y actualmente, ya hay disponibles procesadores de 4 núcleos a un precio
accesible (alrededor de 300 €). Estos procesadores son los Intel Core 2 Quad y sus velocidades
de proceso oscilan entre 2.400 y 2.666Mhz, aunque su principal ventaja es la elevada cantidad de
memoria caché de segundo nivel: 8 Mb. La memoria caché de un ordenador es la que almacena
las operaciones que más se repiten, por lo que se almacenan en esa memoria en concreto para
acelerar el proceso.
Ahora, bien para poder aprovechar las capacidades del hardware debemos contar con el software
adecuado. Con este objetivo se diseñaron los lenguajes de programación, algunos de propósito
general (ejemplo: Basic); y otros con un ámbito especifico de aplicación por ejemplo Fox Pro fue
diseñado para el trabajo con grandes bases de datos.
Un lenguaje de programación es una notación para escribir programas, mediante la cual
podemos comunicarnos con el hardware y dar las instrucciones adecuadas para realizar
determinado proceso. Un lenguaje esta definido por una gramática o conjunto de reglas que se
aplican a un alfabeto, constituido por el conjunto de símbolos utilizados.
Clasificaciones de los lenguajes de PROGRAMACIÓN
1ra clasificación: según se aproxime al lenguaje máquina o al lenguaje de las personas.
Lenguajes de bajo nivel: Comprende al lenguaje binario (Lenguaje máquina), y al lenguaje
Assembler o ensamblador.
Características:
Cada instrucción del lenguaje equivale a una instrucción del CPU.
Los programas solo servían para un modelo específico de procesador (Seria como decir
que en la actualidad requiero un Windows distinto para Celeron, Pentium 3, Pentium 4,
etc.).
Desventajas:
La programación era muy difícil ya que había que conocer el procesador sobre el que se
iba a programar, y además había que utilizar reglas nemotécnicas engorrosas.
Lenguajes de alto nivel: Son similares al lenguaje humano ya que utilizan palabras en inglés
como instrucciones; y por lo tanto son más sencillo de aprender respecto de los anteriores. Ej.:
Basic, Pascal, FORTRAN.
Surgieron con posterioridad a los anteriores con los objetivos que se mencionan a continuación.
Usar el mismo programa en distintos equipos teniendo un traductor o compilador, provisto por el
fabricante, para obtener el programa ejecutable en lenguaje binario del equipo en cuestión; en
consecuencia no se necesita conocer el hardware de dicho equipo.
Acercarse al lenguaje natural, logrando de esta manera que el programa sea fácil de escribir y
leer; y en consecuencia reduciendo la posibilidad de errores que se producían con el lenguaje
Página 3 de 61
UNIVERSIDAD DE BUENOS AIRES - Facultad de Ciencias Económicas
Cátedra Teoría de Los Lenguajes y Sistemas Operativos
máquina porque utilizamos palabras en inglés en vez de cadenas de ceros y unos sin un
significado aparente.
Proveer las rutinas más usadas como entrada / salida, funciones matemáticas, funciones de
manejo de bases de datos, de esta manera se fomenta la reutilización.
Hay que aclarar que las categorías anteriores pueden variar según el autor, ya que por ejemplo el
lenguaje C, se clasifica como de nivel intermedio por poseer características de las dos categorías;
pero otros autores lo clasifican como de bajo nivel.
El único problema que tienen los lenguajes de alto nivel es la gran cantidad que hay actualmente
en uso, y las versiones que se han desarrollado ya que suelen cambiar algunas instrucciones.
2da clasificación:
según la forma en que trabajar de los programas a la filosofía con que fueron
concebidos:
Lenguajes imperativos: usan sentencias o instrucciones como unidad de trabajo de los
programas (Cobol , Pascal , C, Ada).
Lenguajes declarativos: Los programas se codifican mediante descripciones de
funciones o expresiones lógicas (Prolog, Lisp).
Lenguajes orientados a objetos: El diseño de los programas se basa más en los datos y
su estructura. Se utilizan objetos para trabajar, y en este se incluyen los datos (variables)
y las operaciones que actúan sobres estos. Es importante remarcar que se deben tener
sólidos conocimientos de programación estructurada, para poder comprender
correctamente como trabajan los lenguajes orientados a objetos. (C++, Java, Smalltalk).
Lenguajes orientados al problema: están diseñados para solucionar problemas
específicos, en la mayoría de los casos de gestión. Estos suelen ser generadores de
aplicaciones (Ej: Clarion, Genexus, etc).
Lenguajes naturales: el objetivo de su creación es acercar el diseño y la construcción de
programas al lenguaje de las personas.
3ra clasificación: De acuerdo al desarrollo de los lenguajes desde la aparición de las
computadores, y habiendo una cierta correspondencia con las generaciones establecidas en la
evolución de las computadoras.
Primera generación: Lenguajes máquina y ensambladores.
Segunda generación: Comprende los primeros lenguajes de alto nivel imperativos
(Fortran, Cobol).
Tercera generación: Lenguajes de alto nivel imperativos. Son los más usados en la
actualidad (Basic, Pascal, C).
Cuarta generación: Están orientados a aplicaciones de gestión y a las bases de datos
(SQL).
Quinta generación: Orientados a la inteligencia artificial. (Prolog, Lisp).
Lenguajes de programación más importantes
Página 4 de 61
UNIVERSIDAD DE BUENOS AIRES - Facultad de Ciencias Económicas
Cátedra Teoría de Los Lenguajes y Sistemas Operativos
Desde la década del 50 hasta la actualidad, se han desarrollado más de 2.000 lenguajes
diferentes; sin embargo menos de 40 cuarenta fueron importantes en la historia informática. En
el apartado siguiente se explicaran los aspectos más relevantes de los lenguajes de programación
más importantes en la historia de la informática, desarrollando un ejemplo de escritura del
mismo. Los lenguajes que se trataran son los siguientes:
Lenguaje máquina
El lenguaje que entienden las computadoras directamente es el lenguaje binario (ceros y unos),
denominados bits. Este fue el primer lenguaje que se usó. Su principal desventaja fue era muy
difícil su programación; y esto hizo que se dejara de usar. En la mayoría de los casos se usaba el
sistema hexadecimal para facilitar la escritura.
Lenguaje ensamblador
Constituyo el primer intento de reemplazar al lenguaje máquina por uno más similar al de las
personas. En este cada instrucción es equivalente a una instrucción del lenguaje máquina, y para
su escritura se usan palabras nemotécnicas que reemplazan a las cadenas de bits.
Desventajas:
Cada computadora tiene un lenguaje ensamblador propio, en consecuencia un programa
solo puede usarse solo en la máquina en la que se programó.
El programador debe conocer el hardware del equipo, porque se programa directamente
sobre las direcciones de memoria, registros del procesador y otros elementos físicos.
Como todas las instrucciones del lenguaje son elementales, se debe describir
detalladamente todas las operaciones que efectuará el equipo cuando se realice cualquier
proceso.
FORTRAN
El nombre es la abreviatura de FORmula TRANslator (traductor de formulas. Fue creado en
1954 en los Estados Unidos por IBM. Fue el primer lenguaje de alto nivel. Antes se escribían
todos los programas en lenguaje máquina o en ensamblador. Es un lenguaje ideal para
aplicaciones técnicas y científicas por su gran potencia para realizar cálculos matemáticos. Su
principal desventaja es su limitación para aplicaciones de gestión, manejo de archivos,
tratamiento de cadenas de caracteres, e informes.
COBOL
Su nombre es la abreviatura de COmmon Business Oriented Language. Fue creado en 1960 por
un comité denominado CODASYL (COnference on DAta SYstems, Languages), patrocinado
por el departamento de defensa de los Estados Unidos con el objetivo de crear un lenguaje
universal para aplicaciones comerciales.
Entre sus características más importantes se pueden mencionar: es autodocumentado, su
facilidad para el manejo de archivos y edición de informes. Sus desventajas son: la rigidez de su
sintaxis, la extensión de sus sentencias, tener que escribir todos los elementos al máximo detalle,
y la ausencia de funciones matemáticas.
PL/1
Sus siglas son la abreviatura de Programming Language/1.Creado a comienzos de los setenta por
IBM para usarse en los equipo del sistema 360. Para su diseño se tomo como base los lenguajes
Algol, Cobol y Fortran con el objetivo de obtener un lenguaje para uso general. (Aplicaciones
Técnicas, Gestión, desarrollo de sistemas, etc).
Página 5 de 61
UNIVERSIDAD DE BUENOS AIRES - Facultad de Ciencias Económicas
Cátedra Teoría de Los Lenguajes y Sistemas Operativos
Como ventajas se pueden mencionar la sintaxis flexible que posee el lenguaje, es decir su
libertad de escritura; y que soporta la programación estructurada y el diseño modular. La única
desventaja es que al ser un lenguaje de propósito general, no supero a sus predecesores en
aplicaciones específicas.
BASIC
Fue diseñado por los profesores John. Kemeny y Thomas E. Kurst del Dartmouth College
(Estados Unidos) en 1965, con el fin de poseer un lenguaje fácil de aprender, como se indica en
su nombre Beginners All purpose Symbolic Instruction Code (Código de instrucción simbólico
de propósito general para principiantes.
Cabe destacar que su facilidad de aprendizaje hizo que se convirtiera en uno de los lenguajes
más populares de la actualidad, utilizándose para diversas aplicaciones. Hoy en día el Visual
Basic de Microsoft es uno de los lenguajes más utilizados en las PC´s.
PASCAL
Fue creado en 1970 por el matemático suizo Nicklaus Wirth, inspirándose en el lenguaje Algol.
Su nombre proviene del filósofo y matemático francés Blasise Pascal, que inventó la primera
máquina de tipo mecánico para sumar. Se creó con el fin de poder enseñar los conceptos y
técnicos de programación, sin embargo se popularizó utilizándose para desarrollar todo tipo de
aplicaciones.
Aportó los conceptos de tipo de datos, programación estructurada y diseño descendente, y
además fue predecesor del lenguaje ADA. La ventaja que posee que los programas desarrollados
en este se ejecutan con un mínimo de memoria, y sus desventajas son sus limitaciones en la
manejo de archivos, en la entrada y salida y por último que no es fácil de aprender. Actualmente
el Borland Delphi es el descendiente del Pascal.
Hace algunos años este lenguaje se enseñaba en la materia.
C/C++
Creado en 1972 por Dennis Ritchie en los laboratorios de AT&T Bell, con la intención de
conseguir un lenguaje que fuese independiente de la máquina con cual escribir su sistema Unix.
Inicialmente fue diseñado para la programación de sistemas, pero se ha utilizado para escribir
desde juegos hasta sistemas operativos como el Unix, DOS, y Windows.
Sus características son: programación estructurada para resolver tareas de bajo nivel, y las
diversas librerías de rutinas que posee.
El C++ fue una ampliación del lenguaje C incorporándole la programación orientada a objetos.
ADA
Fue el último gran intento de obtener un lenguaje de propósito general. El Departamento de
Defensa de los Estados Unidos encargó el diseño a la empresa Honeywell Bull; tomándose para
su desarrollo las mejoras características del Pascal, Algol, y PL/1. El nombre Ada es honor a
Augusta Ada Byron, condesa de Lovelace, la primera programadora de la historia.
Sus principales características son: tipos de datos abstractos, programación estructurada. El
principal inconveniente es su gran extensión.
LISP Y PROLOG
Lisp es la abreviatura de (LISt Procesor) y el Prolog son usados en la inteligencia artificial. El
Lisp fue creado a finales de los 50 por el matemático del M.I.T John McCarthy,
El Prolog fue creado en los setenta, proveniene del francés PROgrammation en LOGique, es un
lenguaje para programar artefactos electrónicos mediante el paradigma lógico con técnicas de
Página 6 de 61
UNIVERSIDAD DE BUENOS AIRES - Facultad de Ciencias Económicas
Cátedra Teoría de Los Lenguajes y Sistemas Operativos
producción final interpretada. Es bastante conocido en el área de la Ingeniería informática para
investigación en Inteligencia Artificial.
JAVA
Fue diseñado por la compañía Sun Microsystems Inc, con el propósito de crear un lenguaje que
pudiera funcionar en redes computacionales heterogéneas (redes de computadoras formadas por
más de un tipo de computadora, ya sean PC, MAC's, estaciones de trabajo, etc.), y que fuera
independiente de la plataforma en la que se vaya a ejecutar. Esto significa que un programa de
Java puede ejecutarse en cualquier máquina o plataforma. El lenguaje fue diseñado con las
siguientes características en mente:
Simple. Elimina la complejidad de los lenguajes como "C" y da paso al contexto de los
lenguajes modernos orientados a objetos.
Orientado a Objetos. La filosofía de programación orientada a objetos es diferente a la
programación convencional.
Familiar. Como la mayoría de los programadores están acostumbrados a programar en C
o en C++, el sintaxis de Java es muy similar al de estos.
Robusto. El sistema de Java maneja la memoria de la computadora por ti. No te tienes
que preocupar por apuntadores, memoria que no se esté utilizando, etc. Java realiza todo
esto sin necesidad de que uno se lo indique.
Seguro. El sistema de Java tiene ciertas políticas que evitan se puedan codificar virus con
este lenguaje. Existen muchas restricciones, especialmente para los applets, que limitan
lo que se puede y no puede hacer con los recursos críticos de una computadora.
Portable. Como el código compilado de Java (conocido como byte code) es interpretado,
un programa compilado de Java puede ser utilizado por cualquier computadora que tenga
implementado el interprete de Java.
Independiente a la arquitectura. Al compilar un programa en Java, el código resultante
un tipo de código binario conocido como byte code. Este código es interpretado por
diferentes computadoras de igual manera, solamente hay que implementar un intérprete
para cada plataforma. De esa manera Java logra ser un lenguaje que no depende de una
arquitectura computacional definida. Puede ejecutar diferentes líneas de código al mismo
tiempo.
Interpretado. Java corre en máquina virtual, por lo tanto es interpretado.
Dinámico. Java no requiere que compiles todas las clases de un programa para que este
funcione. Si realizas una modificación a una clase Java se encarga de realizar un
Dynamic Bynding o un Dynamic Loading para encontrar las clases.
Java puede funcionar como una aplicación sola o como un "applet", que es un pequeño programa
hecho en Java. Los applets de Java se pueden "pegar" a una página de Web (HTML), y con esto
puedes tener un programa que cualquier persona que tenga un browser compatible podrá usar.
Página 7 de 61
UNIVERSIDAD DE BUENOS AIRES - Facultad de Ciencias Económicas
Cátedra Teoría de Los Lenguajes y Sistemas Operativos
Página 8 de 61
UNIVERSIDAD DE BUENOS AIRES - Facultad de Ciencias Económicas
Cátedra Teoría de Los Lenguajes y Sistemas Operativos
Estructuras.
Ámbito de aplicación.
PROGRAMA
1.- CONCEPTO: Un programa de computadora es un conjunto de instrucciones, escritas en un
lenguaje formal siguiendo un orden lógico, que producirá la ejecución de una determinada tarea.
PROCESO DE PROGRAMACION:
DEFINICION Y ANALISIS DEL PROBLEMA
DISEÑO DEL ALGORITMO
CODIFICACION DEL PROGRAMA
DEPURACION Y VERIFICACION
D
O
C
U
M
E
N
T
A
CI
O
N
M
A
N
T
E
N
I
M
IE
N
T
O
2.- PARTES CONSTITUTIVAS
ENTRADA
DATOS
Provisión de dispositivos de entrada:
Teclado, disco, scaners…
Acción leer
PROGRAMA
ALGORITMO DE RESOLUCIÓN
(Caja negra)
SALIDA
DATOS
Pantalla, impresora,
discos, etc.
Acción escribir
3.- INSTRUCCIONES
Son las acciones que resolverán el problema, se escriben y almacenan en memoria en el mismo
orden que se van a ejecutar (en secuencia)
Un programa puede ser lineal o no lineal.
Es lineal si las instrucciones se ejecutan secuencialmente (sin bifurcaciones, decisiones,
comparaciones)
inst 1
inst 2
inst 3
Inst N
Es NO LINEAL cuando se interrumpe la secuencia mediante instrucciones de bifurcación.
Página 9 de 61
UNIVERSIDAD DE BUENOS AIRES - Facultad de Ciencias Económicas
Cátedra Teoría de Los Lenguajes y Sistemas Operativos
acción 1
acción 2
-
Acción H
Acción N
TIPOS DE INSTRUCCIONES
De INICIO/FIN
De ASIGNACION
De LECTURA
De ESCRITURA
De BIFURACION
COMIENZO/FIN
LEER
MOSTRAR
CONDICIONALES E INCONDICIONALES
ELEMENTOS BASICOS DE UN PROGRAMA O ALGORITMO
Palabras reservadas
Identificadores
Caracteres especiales
Constantes
Variables
Expresiones
Instrucciones
OTROS COMPONENTES QUE FORMAN PARTE SON:
Bucles
Contadores
Acumuladores
Interruptores
Estructuras
Secuenciales
Selectivas
Repetitivas
Lenguajes orientados al problema.
NOCION DE ALGORITMO
Resolución de problemas:
ETAPAS:
FORMULACION O ENUNCIACION DEL PROBLEMA. Debe ser formulado en forma
correcta, completa y sin ambigüedades
Página 10 de 61
UNIVERSIDAD DE BUENOS AIRES - Facultad de Ciencias Económicas
Cátedra Teoría de Los Lenguajes y Sistemas Operativos
ELECCION DE UN METODO O PROCEDIMEINTO. Para hallar la solución del
mismo
CODIFICACION. Consiste en expresar el método o procedimiento elegido de forma tal
que pueda ser interpretado por el procesador que va a utilizarse.
EJECUCION. Consiste en ejecutar el procedimiento elegido para obtener la solución del
problema.
PROCESADOR: llamamos procesador a toda entidad capaz de comprender un enunciado y
ejecutar el trabajo indicado en el mismo.
AMBIENTE: el conjunto de todos los recursos necesarios para la ejecución de un trabajo
constituye el ambiente de ese trabajo.
ACCION: una acción es un evento que modifica el ambiente
Tipos de Acciones: PRIMITIVAS y NO PRIMITIVAS.
Acción PRIMITIVA: para un procesador dado, una acción es primitiva si su enunciado es
suficiente para que pueda ejecutarla sin información adicional.
Acción NO PRIMITIVA: necesita ser descompuesta en acciones primitivas, para lograr
esto usamos por ejemplo la Técnica de Refinamientos Sucesivos (también llamado TOPDOW).
El PROCESADOR interpreta acciones y enunciados.
Un “enunciado” no es una acción que modifica el ambiente.
Una “condición” es una afirmación lógica sobre el estado del problema que puede ser cierta o
falsa, en el momento de la observación.
Definición de algoritmo
"Un algoritmo es una secuencia finita y ordenada de acciones primitivas que pueden ser
ejecutadas por un procesador y que lleve a la solución de un problema dado".
Las características fundamentales que debe cumplir todo algoritmo son:
Debe ser preciso. E indicar el orden de realización de cada paso.
Debe ser definido. Si se sigue un algoritmo dos veces, se debe obtener el mismo resultado cada
vez.
Debe ser finito. Si se sigue un algoritmo, se debe terminar en algún momento; o sea debe tener
un número finito de pasos.
La definición de un algoritmo debe describir tres partes: Entrada, Proceso y Salida.
Algoritmos Cotidianos
Se refiere a todos aquellos algoritmos que nos ayudan a resolver problemas diarios, y que los
hacemos casi sin darnos cuenta de que estamos siguiendo una metodología para resolverlos.
Página 11 de 61
UNIVERSIDAD DE BUENOS AIRES - Facultad de Ciencias Económicas
Cátedra Teoría de Los Lenguajes y Sistemas Operativos
Algunos ejemplos son:
Diseñar un algoritmo para cambiar una llanta a un coche.
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
Inicio.
Traer gato.
Levantar el coche con el gato.
Aflojar tornillos de las llantas.
Sacar los tornillos de las llantas.
Quitar la llanta.
Poner la llanta de repuesto.
Poner los tornillos.
Apretar los tornillos.
Bajar el gato.
Fin
Un cliente ejecuta un pedido a una fábrica. La fábrica examina en su banco de datos la ficha
del cliente, si el cliente es solvente entonces la empresa acepta el pedido, en caso contrario
rechazar el pedido.
Pasos del algoritmo:
Inicio
Leer el pedido
Examinar ficha del cliente
Si el cliente es solvente aceptar pedido, en caso contrario rechazar pedido
Fin
Determinar el mayor de tres números enteros.
Pasos del algoritmo:
1.- Comparar el primero y el segundo entero, deduciendo cuál es el mayor.
2.- Comparar el mayor anterior con el tercero y deducir cuál es el mayor. Este será el resultado.
Los pasos anteriores se pueden descomponer en otros pasos más simples en los que se denomina
refinamiento del algoritmo.
1.2.3.4.5.6.7.-
Obtener el primer número (entrada), denominado NUM1
Obtener el segundo número (entrada), denominado NUM2
Compara NUM1 con NUM2 y seleccionar el mayor; si los dos enteros son iguales,
seleccionar NUM1. Llamar a este número MAYOR.
Obtener el tercer número (entrada), y se denomina NUM3.
Compara MAYOR con NUM3 y seleccionar el mayor ; si los dos enteros son iguales,
seleccionar el MAYOR. Denominar a este número MAYOR.
Presentar el valor MAYOR (salida).
Fin
Definición de Lenguajes Algorítmicos
Página 12 de 61
UNIVERSIDAD DE BUENOS AIRES - Facultad de Ciencias Económicas
Cátedra Teoría de Los Lenguajes y Sistemas Operativos
Los algoritmos pueden describirse utilizando diversos lenguajes. Cada uno de estos lenguajes
permiten describir los pasos con mayor o menor detalle.
La clasificación de los lenguajes para algoritmos puede enunciarse de la siguiente manera:
Lenguaje Natural
Es aquél que describe en español, para nuestro caso, los pasos a seguir utilizando un vocabulario
cotidiano. Se le conoce como lenguaje jerga cuando se utilizan términos especializados de una
determinada ciencia, profesión o grupo.
Lenguaje de Diagrama de Flujo
Es aquél que se vale de diversos símbolos para representar las ideas o acciones a desarrollar. Es
útil para organizar las acciones o pasos de un algoritmo pero requiere de etapas posteriores para
implementarse en un sistema de cómputo.
Lenguaje Natural de Programación
Son aquellos que están orientados a la solución de problemas que se definen de una manera
precisa. Generalmente son aplicados para la elaboración de fórmulas o métodos científicos.
Tiene las siguientes características:
Evita la ambigüedad (algo confuso que se puede interpretar de varias maneras).
Son precisos y bien definidos.
Utilizan términos familiares al sentido común.
Elimina instrucciones innecesarias.
Lenguaje de Programación de Algoritmos
Es aquél que se utiliza para introducir en la computadora un algoritmo específico. Se les conoce
también como Lenguaje de Programación.
Lenguaje de Programación:
Es un conjunto de palabras, símbolos y reglas sintácticas mediante los cuales puede indicarse a la
computadora los pasos a seguir para resolver un problema.
Los lenguajes de programación pueden clasificarse por diversos criterios, siendo el más común
su nivel de semejanza con el lenguaje natural, y su capacidad de manejo de niveles internos de la
máquina.
Página 13 de 61
UNIVERSIDAD DE BUENOS AIRES - Facultad de Ciencias Económicas
Cátedra Teoría de Los Lenguajes y Sistemas Operativos
2. Traductores de lenguaje.
INTRODUCCIÓN
En la última clase vimos un sencillo algoritmo que lo único que hacia era mostrar un mensaje por
pantalla.
PSEUDOCODIGO
mostrar “Hola a todo el mundo...”
BASIC
‘ Programa demostración versión 1.0: print “Hola a todo el mundo...”
Ahora bien, este conjunto de instrucciones o sentencias de basic tenemos que guardarlas en un
archivo de texto con la extensión bas, ya que esta es la que se utiliza generalmente para los
programas de basic, caso contrario cuando apaguemos el equipo perdemos el programa. Este
conjunto de instrucciones basic se denominan código fuente o programa fuente; por si solo el
código fuente no hace nada porque como dijimos anteriormente es solo un archivo de texto; por
este motivo para poder ejecutar el programa que hicimos nos falta un traductor.
Es importante destacar que los traductores son solo necesarios para los lenguajes de alto nivel; en
consecuencia no haría falta un traductor para un programa escrito en lenguaje máquina.
TRADUCTORES DE LENGUAJES
Los traductores de lenguajes son programas que convierten o traducen los programas fuente que
codificamos en lenguajes de alto nivel a lenguaje máquina.
Los traductores se dividen en:
Compiladores
Interpretes
Compilador - Interprete
Compaginadores, compiladores e intérpretes.
INTÉRPRETES
Un intérprete es un traductor que toma un programa fuente, lo traduce y a continuación lo
ejecuta. (Línea a línea).
Un lenguaje de programación que utilice un intérprete se denomina lenguaje interpretado. La
versión 5.0 del sistema MS-DOS incorporó como accesorio al Quickbasic, este era un intérprete
del lenguaje Basic.; generalmente los intérpretes venían con un editor de texto que nos permitía
escribir el programa fuente. (Mostrar interprete QuickBasic y Ada). Se podría llegar a decir que
en su momento del Dbase III Plus era un intérprete.
Página 14 de 61
UNIVERSIDAD DE BUENOS AIRES - Facultad de Ciencias Económicas
Cátedra Teoría de Los Lenguajes y Sistemas Operativos
Figura 1 Intérprete
COMPILADORES
Un compilador es un programa que traduce los programas fuente escritos en lenguajes de alto
nivel a lenguaje maquina. El programa traducido a lenguaje máquina se llama programa objeto o
código objeto. Ejemplos de compiladores son: Visual C++, en su momento lo fue el Clipper y el
Turbo Pascal.
Figura 2 – Compilación
COMPILADORES – interpretes
Como su nombre lo indica es una combinación de los dos, permitiendo realizar ambos procesos.
Generalmente lo que se hace es usar el interprete y cuando se probó varias veces el programa y
se esta seguro que no tiene errores se realiza la compilación. Ejemplos: Visual Basic, Visual Fox
Pro.
Página 15 de 61
UNIVERSIDAD DE BUENOS AIRES - Facultad de Ciencias Económicas
Cátedra Teoría de Los Lenguajes y Sistemas Operativos
Características.
Vinculación.
El proceso de compilación
La compilación es el proceso mediante el cual se traducen los programas fuente a programas
objeto.
El programa objeto que se obtiene al final de la compilación no es código máquina ejecutable
sino ensamblador.
Para obtener el código máquina ejecutable, tenemos que usar un programa llamado enlazador o
linker. El proceso de link edición traduce un programa objeto a lenguaje máquina ejecutable.
Las etapas del proceso de compilación son las siguientes:
Figura 3: Fases de la compilación
Antes de seguir con la explicación vamos a ver un pantallazo de la evolución de las técnicas de
programación.
En sus comienzos la programación se reducía a escribir el programa en un único archivo; en
consecuencia luego del proceso de compilación y link edición se obtenía un único archivo
ejecutable. Estos programas tenían como principal característica que a cada una de sus líneas de
código fuente se las numeraba por ejemplo 10, 20, 30, 40, etc.; un programa extenso podía llegar
a tener por ejemplo 4000 líneas de código; por lo tanto, la principal desventaja que se desprende
de lo mencionado anteriormente es la dificultad de encontrar un error entre tantas líneas de
código. Esta técnica de programación se denominó programación lineal. Gráficamente el
proceso de escritura con esta técnica de programación sería de la siguiente manera.
Fuente
Objeto
Programa1.bas
Programa1.obj
Ejecutable
Programa1.exe
A la programación lineal le siguió la programación modular que líneas generales se refiere a
dividir un problema complejo, en muchos problemas con un menor grado de complejidad
subordinados al problema principal; en otras palabras es el principio divide y vencerás. Ahora en
vez de tener un único programa de muchas líneas de código, voy a tener muchos programas de
Página 16 de 61
UNIVERSIDAD DE BUENOS AIRES - Facultad de Ciencias Económicas
Cátedra Teoría de Los Lenguajes y Sistemas Operativos
pocas líneas de código, por ejemplo de 40 líneas cada uno; obteniéndose como principal ventaja
la facilidad de búsqueda de errores. Gráficamente el proceso será como se muestra a
continuación:
Fuente
Objeto
Ejecutable
Compilador
Programa1.bas
Programa1.obj
Programa2.bas
Programa2.obj
Programa3.bas
Programa3.obj
ProgramaN.bas
ProgramaN.obj
Editor de enlace
Programa.exe
Lo que muestra la figura anterior es que lo que hace el compilador es convertir o traducir cada
programa a código objeto, y posteriormente el editor de enlace o linker me genera un único
archivo ejecutable a partir de uno o más programas objeto.
El enlazador o editor de enlace también me permite juntar otros programas objeto para obtener
un único archivo ejecutable. Un ejemplo de esto sería el siguiente suponiendo que tenemos dos
programas fuente escritos en basic, principal.bas e imprimir.bas compilamos ambos obteniendo
dos programas objeto principal. obj e imprimir.obj; finalmente a través del uso del editor de
enlace obtendremos un único archivo ejecutable por ejemplo programa.exe.
Figura 4 Fases de la compilación utilizando otros programas objetos
Teniendo en cuenta lo mencionado anteriormente continuación vamos a ver las fases de
ejecución de un programa Pascal son las siguientes:
En síntesis las etapas de un proceso de compilación son las siguientes:
Escribir el programa fuente y guardarlo en un archivo.
Compilarlo
Página 17 de 61
UNIVERSIDAD DE BUENOS AIRES - Facultad de Ciencias Económicas
Cátedra Teoría de Los Lenguajes y Sistemas Operativos
Verificar y corregir los errores de compilación.
Obtención del programa objeto.
Obtención del programa ejecutable.
Se ejecuta el programa y si no hay errores se obtiene la salida.
Figura 4 Fases de la ejecución de un programa
3. Programas.
Constantes, variables y expresiones.
Tipos de instrucciones.
Bucles, contadores, acumuladores y selección.
Tipos de Datos
Un dato se define como la expresión general que describe los objetos con los cuales opera una
computadora. Los datos de entrada se transforman por el programa, después de las etapas
intermedias, en datos de salida.
Los datos se clasifican en diversas categorías, según el tipo de máquina o del lenguaje en uso.
Generalmente podemos encontrar las siguientes categorías:
Numéricos
Lógicos
Cadenas
Datos Numéricos
Son aquellos que representan una cantidad o valor determinado. Su representación se lleva a
cabo en los formatos ya conocidos (enteros, punto y fracciones decimales si estas existen).
Estos pueden representarse en dos formas distintas:
Tipo Numérico Entero (integer).
Tipo Numérico Real (real).
Página 18 de 61
UNIVERSIDAD DE BUENOS AIRES - Facultad de Ciencias Económicas
Cátedra Teoría de Los Lenguajes y Sistemas Operativos
Enteros
Es un conjunto finito de los números enteros. Los enteros son números completos, no tienen
componentes fraccionarios o decimales y pueden ser negativos y positivos.
Algunos ejemplos son:
3 7 -10 15.25 50
Reales
Consiste en un subconjunto de los números reales. Estos números siempre tienen un punto
decimal y pueden ser positivos o negativos. Un número real consiste de un número entero y una
parte decimal. Algunos ejemplos son :
0.52 664.32 -47.23
Datos Cadenas
Son los datos que representan información textual (palabras, frases, símbolos, etc). No
representan valor alguno para efectos numéricos. Pueden distinguirse porque son delimitados por
apóstrofes o comillas.
Se clasifica en dos categorías:
Datos tipo carácter (char)
Datos tipo Cadena (string)
Datos Tipo Carácter
Es un conjunto finito y ordenado de caracteres que la computadora reconoce. Un dato de este
tipo contiene solo un carácter.
Reconoce los siguientes caracteres:
Caracteres Alfabéticos (A,B,C,…Z,a,b,c…z)
Caracteres Numéricos (0,1,2,…9)
Caracteres Especiales (+, -, *, /, ^, . , ;, <, >, $, …….)
Datos Tipo Cadena (string)
Es un sucesión de caracteres que se encuentran delimitados por una comilla (apóstrofe) o dobles
comillas, según el tipo de lenguaje de programación. La longitud de una cadena de caracteres es
el número de ellos comprendidos entre los separadores o delimitadores.
Ejemplos:
“Hola a todos’
’12 de octubre de 1496’
“Enunciado cualquiera’
Nota: Los símbolos disponibles para la formulación de caracteres y de cadenas son aquellos
que se encuentran en el código ASCII.
ASCII (American Standard Code for Information Interchange).
Datos Lógicos
Página 19 de 61
UNIVERSIDAD DE BUENOS AIRES - Facultad de Ciencias Económicas
Cátedra Teoría de Los Lenguajes y Sistemas Operativos
También se le denomina Booleano, es aquél dato que solo puede tomar uno de dos valores: Falso
y verdadero.
Se utiliza para representar las alternativas (si/no) a determinadas condiciones. Por ejemplo,
cuando se pide si un valor entero sea primo, la respuesta será verdadera o falsa, según sea.
Las categorías y tipos que se mencionaron anteriormente se conocen como Tipos Simples, puesto
que no poseen una estructura compleja.
Constantes y variables
Una Constante es aquélla que no cambia de valor durante la ejecución de un programa (o
comprobación de un algoritmo en este caso). Se representa en la forma descrita para cada
categoría.
Las Variables son aquéllas que pueden modificar su valor durante la ejecución de un programa
(ídem).
Contienen un nombre, una dirección de memoria, un tipo de dato y un contenido. Su
representación se da a través de letras y símbolos generalmente numéricos a los que se les asigna
un valor.
Ejemplos:
Constantes
Numéricos
36
450.35
0.58
Cadena
'A'
'Juan'
'La Paz'
Lógicos
Falso
Verdadero
Variables
A
Nom
Edad
Ciudad
Estatura
Operadores y Operandos
Un operador es el símbolo que determina el tipo de operación o relación que habrá de
establecerse entre los operandos para alcanzar un resultado.
Los operadores se clasifican en tres grupos:
1.- Operadores Aritméticos
Son aquellos que permiten la realización de cálculos aritméticos. Utilizan operandos numéricos y
proporcionan resultados numéricos.
Operador
Operación
+
Suma
-
Resta
*
Multiplicación
/
División real
Div
División entera
Mod
Residuo
^
Exponenciación
Página 20 de 61
UNIVERSIDAD DE BUENOS AIRES - Facultad de Ciencias Económicas
Cátedra Teoría de Los Lenguajes y Sistemas Operativos
Ejemplos:
7+3 = 10
7-3 = 4
7*3 = 21
10/4= 2.5
10 Div 4 = 2
20 Mod 3 = 2
5 Mod 7 = 5
4 ^ 2 = 16
En la expresión 7+3, los valores 7 y 3 se denominan operandos. El valor de la expresión 7+3 se
conoce como resultado de la expresión.
Todos los operadores aritméticos no existen en todos los lenguajes de programación, por
ejemplo, en Fortran no existen Div y mod.
Operadores Div y Mod
El símbolo / se utiliza para la división real, y el operador Div representa la división entera.
Expresión
Resultado
Expresión
Resultado
10.5/3.0
3.5
10 Div 3
3
¼
0.25
18 Div 2
9
2.0/4.0
0.5
30 Div 30
1
30/30
1.0
10 Mod 3
1
6/8
0.75
10 Mod 2
0
2.- Operadores Relacionales
Permiten realizar comparaciones de valores de tipo numérico o carácter. Estos operadores sirven
para expresar las condiciones en los algoritmos. Proporcionan resultados lógicos.
Operador
Significado
<
Menor que
>
Mayor que
=
Igual que
<=
Menor o igual que
>=
Mayor o igual que
<>
Diferente de
El formato general para las comparaciones es:
expresión1 operador de relación expresión2
El resultado de la operación será Verdadero o Falso. Así por ejemplo, si A=4 y B=3, entonces:
A>B Es Verdadero
(A-2) < (B-4) Es Falso
Los operadores de relación se pueden aplicar a cualquiera de los cuatro tipos de datos estándar:
enteros, real, lógico y carácter.
‘A’ < ‘K’ = Verdadero
‘A’ > ‘a’ = Falso
Página 21 de 61
UNIVERSIDAD DE BUENOS AIRES - Facultad de Ciencias Económicas
Cátedra Teoría de Los Lenguajes y Sistemas Operativos
‘MARIA’ < ‘JUAN’ = Falso (se considera la primera letra)
‘JAIME’ > ‘JORGE’ = Falso
Nota: La comparación de cadenas se rige por el código ASCII.
Prioridad De Operadores Aritméticos y Relacionales
Determina el orden en que habrán de realizarse las operaciones en una expresión determinada.
Para obtener la prioridad se deben conocer las siguientes reglas:
Las operaciones que están encerradas entre paréntesis se evalúan primero. Si existen
diferentes paréntesis anidados (interiores unos a otros), las expresiones más internas se
evalúan primero.
Las operaciones aritméticas dentro de una expresión suelen seguir el siguiente orden de
prioridad.
Operador
^
Prioridad
Alta
*, /, Div
+, -, Mod
Relacionales
Baja
En caso de coincidir varios operadores de igual prioridad en una expresión o subexpresión
encerrada entre paréntesis, el orden de prioridad en este caso es de izquierda a derecha.
Cuando se desea realizar una operación con baja prioridad por adelantado, debe agruparse a los
operandos involucrados.
4 + 12 /2 = 10 (sin agrupar)
(4 + 12) /2 = 8 (con agrupador)
Los paréntesis tienen prioridad sobre el resto de las operaciones.
A * (B+3)
La constante 3 se suma primero al valor de B, después este resultado se
multiplica por el valor de A.
(A*B) +3 A y B Se multiplican primero y a continuación se suma 3.
A + (B/C) + D
Esta expresión equivale a A+ B/C + D
3.- Operadores Lógicos
Son aquellos que permiten la combinación de condiciones para formar una sola expresión lógica.
Utilizan operandos lógicos y proporcionan resultados lógicos también.
Operador
not
and
or
xor
Relación
Negación (No)
Conjunción (Y)
Disyunción (O)
Disyunción Exclusiva (O/SOLO)
Se obtiene Verdadero si:
NOT El operando es falso
AND Ambos operandos son verdaderos
OR
Al menos un operando es verdadero
Página 22 de 61
UNIVERSIDAD DE BUENOS AIRES - Facultad de Ciencias Económicas
Cátedra Teoría de Los Lenguajes y Sistemas Operativos
XOR Solo uno de los operandos son verdadero
Ejemplos:
X
Y
NOT(X)
NOT(Y)
X AND Y
X OR Y
X XOR Y
F
F
V
V
F
F
F
V
F
F
V
F
V
V
F
V
V
F
F
V
V
V
V
F
F
V
V
F
Not (4 > 14)
Produce un valor verdadero.
ASCII
Símbolo
ASCII
Símbolo
ASCII
Símbolo
ASCII
Símbolo
ASCII
Símbolo
ASCII
Símbolo
32
(espacio)
48
0
64
@
33
!
49
1
65
A
80
P
81
Q
96
`
112
p
97
a
113
34
"
50
2
66
B
82
R
q
98
b
114
r
35
#
51
3
36
$
52
4
67
C
83
S
68
D
84
T
99
c
115
s
100
d
116
37
%
53
5
69
E
85
U
101
t
e
117
u
38
&
39
'
54
6
70
F
86
V
55
7
71
G
87
W
102
f
118
v
103
g
119
w
40
(
56
8
72
H
88
X
104
h
120
x
41
)
57
9
73
I
42
*
58
:
74
J
89
Y
105
i
121
y
90
Z
106
j
122
z
43
+
59
;
75
44
,
60
<
76
K
91
[
107
k
123
{
L
92
\
108
l
124
|
45
-
61
=
77
M
93
]
109
m
125
}
46
.
62
47
/
63
>
78
N
94
^
110
n
126
~
?
79
O
95
_
111
o
127
•
Asignación
La operación de asignación es el modo de darle valores a una variable. La operación de
asignación se representa por el símbolo u operador =. La operación de asignación se conoce
como instrucción o sentencia de asignación cuando se refiere a un lenguaje de programación.
A fin de manejar datos por medio de variables, estos pueden recibir valores determinados. El
tipo de los valores que pueden recibir dependen de la declaración previa de tales variables.
En una asignación se resuelve, primeramente la expresión (al lado derecho del símbolo de
asignación) y se asigna el resultado en la variable.
El formato general de asignación es:
Nom_variable Expresión
Donde Expresión puede ser una variable o constante, operación, función.
Ejemplo:
A 9
Significa que la variable A se le ha asignado el valor 9. La acción de asignar es destructiva, ya
que el valor que tuviera la variable antes de la asignación se pierde y se reemplaza por el nuevo
valor.
Página 23 de 61
UNIVERSIDAD DE BUENOS AIRES - Facultad de Ciencias Económicas
Cátedra Teoría de Los Lenguajes y Sistemas Operativos
Lenguaje:
Conjunto de reglas y palabras apoyadas en algún lenguaje natural.
Programa:
Conjunto de instrucciones escritas en un lenguaje formal de computación siguiendo un orden
lógico.
Elementos de un Programa:
Variables
Constantes
Instrucciones
Estructuras
Variable:
Una posición con nombre en memoria donde se almacena un valor que puede modificarse
durante la ejecución del programa.
Tiene un nombre, un contenido, un tipo y una posición de memoria.
Constante:
Un elemento con nombre que, a diferencia de las variables, mantiene un valor constante a través
de la ejecución de un programa. Recibe un valor en el momento de la compilación y este
permanece inalterado durante todo el programa.
Instrucciones:
Utilizaremos las siguientes instrucciones:
Escribir:
Permite presentar en pantalla texto o el contenido de una variable.
Ejemplos:
mostrar “Ingrese el número de registro del alumno”
mostrar nota
mostrar “La nota del alumno seleccionado es: ”,nota
Asignar:
Permite asignar a una variable un determinado valor.
Ejemplos:
nota: = 7
nota: = promedio
contador: = contador + 1
Leer:
La instrucción pedir realiza 3 operaciones:
- Muestra el valor de una variable.
- Permite el ingreso por teclado de un nuevo valor.
- Asigna el valor ingresado a dicha variable.
Ejemplo:
Pedir nota
Página 24 de 61
UNIVERSIDAD DE BUENOS AIRES - Facultad de Ciencias Económicas
Cátedra Teoría de Los Lenguajes y Sistemas Operativos
Estructuras:
Las estructuras pueden clasificarse en dos grupos:
-
Estructuras de decisión
Estructuras de repetición
Estructuras de decisión:
Son estructuras de control condicional que permiten llevar a cabo una acción, si una condición
(expresión lógica) dada tiene un valor específico (verdadero o falso).
Son las que permiten la selección de acciones alternativas.
ESTRUCTURA DE DECISIÓN SIMPLE: se usan para representar estructuras en las que si la
evaluación de la expresión lógica resulta ser verdadera se ejecuta la sentencia o la serie de
sentencias, según sea el caso. Mientras que si el resultado de su evaluación es falso se continúa
como si la instrucción SI – ENTONCES no hubiese existido
Estructura Si:
Si <Condición>
<Sentencia 1>
<Sentencia 2>
...
<Sentencia n>
Fin Si
Condici
ón
V
F
Sentencia
s1an
Cuando se alcanza la sentencia Si dentro del programa, se evalúa la condición. Solo si la
condición es verdadera se ejecutan las sentencias que se encuentran entre Si y Fin Si.
Condición
SI
NO
Sentencia/s
Ejemplo:
Si total > 100
total : = total - descuentos
Mostrar total
Fin si
ESTRUCTURA DE DECISIÓN DOBLE
Estructura Si – Si no:
Página 25 de 61
UNIVERSIDAD DE BUENOS AIRES - Facultad de Ciencias Económicas
Cátedra Teoría de Los Lenguajes y Sistemas Operativos
Si <Condición>
<Sentencia 1>
<Sentencia 2>
...
<Sentencia n>
Si No
<Sentencia A>
<Sentencia B>
...
<Sentencia N>
Fin Si
V
Condici
ón
Sentencia
s1an
F
Sentencia
sAaN
Condición
SI
NO
Sentencia 1
Sentencia A
Cuando se alcanza la sentencia Si dentro del programa, se evalúa la condición. Si la condición es
verdadera se ejecuta el primer conjunto de sentencias. Si es falsa se ejecuta el segundo conjunto
de sentencias.
Ejemplo:
Si salario > 400
Salario _ neto: = salario – impuestos
Si no
Salario _ neto: = salario
Fin si
ESTRUCTURAS DE DECISIÓN MÚLTIPLE:
La estructura En caso de permite incluir múltiples condiciones, ejecutándose solo las sentencias
asociadas a condiciones verdaderas. De no ser verdadera ninguna condición, se ejecutarán las
sentencias que se encuentran entre Si no hacer y el fin de la estructura.
Estructura En caso de:
En caso de <Condición> hacer
<Sentencia 1>
<Sentencia 2>
Página 26 de 61
UNIVERSIDAD DE BUENOS AIRES - Facultad de Ciencias Económicas
Cátedra Teoría de Los Lenguajes y Sistemas Operativos
...
<Sentencia n>
<Condición> hacer
<Sentencia A>
<Sentencia B>
...
<Sentencia N>
Si no hacer
<Sentencia a>
<Sentencia b>
...
<Sentencia n>
Fin En caso de
La estructura En caso de permite incluir múltiples condiciones, ejecutandose solo las sentencias
asociadas a condiciones verdaderas. De no ser verdadera ninguna condición, se ejecutarán las
sentencias que se encuentran entre Si no hacer y el fin de la estructura.
Ejemplo:
En caso de (opción)
opcion = 1 hacer
Mostrar “Usted seleccionó la opción Proveedores.”
opcion = 2 hacer
Mostrar “Usted seleccionó la opción Clientes.”
Si no
Mostrar “Usted seleccionó una opción no válida.”
Fin en caso de
Ejercicio:
•
•
•
•
Se debe obtener la nomina semanal (salario neto) de los empleados de una empresa. La
misma liquida los sueldos de la siguiente manera:
– Se paga por hora trabajada
– Si la cantidad de horas es menor igual a 35 horas, la tarifa de las mismas es la
básica
– Si la cantidad de horas trabajadas es mayor a 40, las horas extras se pagan el 50%
mas de la tarifa de la hora básica (es decir 1,5)
Se debe ingresar por teclado:
– Nombre
– Horas
– Tarifa básica de la hora
Los impuestos varían en función del total de salario.
– Menor e igual a $20.000: sin impuesto
– De $20.000 a $35000: 20% del monto que supera al mínimo.
– Mas de $35000: 30% del monto que supera al punto anterior.
Se debe mostrar el nombre, sueldo bruto, impuestos y sueldo neto
Página 27 de 61
UNIVERSIDAD DE BUENOS AIRES - Facultad de Ciencias Económicas
Cátedra Teoría de Los Lenguajes y Sistemas Operativos
Página 28 de 61
UNIVERSIDAD DE BUENOS AIRES - Facultad de Ciencias Económicas
Cátedra Teoría de Los Lenguajes y Sistemas Operativos
Estructuras de Repetición
Estructura Repetir:
Repetir
<Sentencia 1>
<Sentencia 2>
...
<Sentencia n>
Hasta que <Condición>
Sentencia
s1an
F
Condición
V
La sentencia repetir se utiliza para especificar un bucle condicional que se ejecuta al menos una
vez. Las sentencias que se encuentran dentro de la estructura se ejecutarán hasta que la condición
tome un valor verdadero.
Ejemplo:
Repetir
Mostrar “Ingrese un número del 0 al 9”
Pedir número
Hasta que número >= 0 y número <= 9
Estructura Mientras:
Mientras <Condición>
<Sentencia 1>
<Sentencia 2>
...
<Sentencia n>
Fin mientras
Condición
F
V
Sentencia
s1an
A diferencia de la estructura Repetir, en la estructura Hacer mientras la condición esta
posicionada al inicio, de modo que esta se evalúa antes de ejecutarse las sentencias que se
encuentran dentro de la estructura. Esto significa que si la condición es inicialmente falsa
ninguna de las sentencias que conforman el cuerpo de la estructura se ejecutarán.
Ejemplo:
Mientras contador <= 100
contador : = contador + 1
Mostrar contador
Fin mientras
Estructura Para (I) desde hasta hacer:
Página 29 de 61
UNIVERSIDAD DE BUENOS AIRES - Facultad de Ciencias Económicas
Cátedra Teoría de Los Lenguajes y Sistemas Operativos
Para (I) desde vi hasta vf hacer
<Sentencia 1>
<Sentencia 2>
...
<Sentencia n>
Fin para
A diferencia de la estructura Repetir y Mientras , en la estructura Para…. hacer la cantidad de
veces que se va a ejecutar esta condicionada al inicio, de modo que se sabe de antemano cuantas
veces se van a ejecutar las sentencias que se encuentran dentro de la estructura. Se va a evaluar el
valor de la variable I desde el valor inicial hasta el valor final y la diferencia entre el valor final y
el valor inicial es la cantidad de veces que se van a ejecutar las sentencias que están dentro de la
estructura.
PRUEBA DE ESCRITORIO
Cuando tenemos un algoritmo y queremos saber si lo codificado cumple con lo solicitado para su
correcta resolucion, precisamos hacer lo que se llama una prueba de escritorio.
La misma consiste en enumerar todas las variables utilizadas en el algoritmos ya sean de entrada,
de salida o de entrada/salida e ir colocando valores para poder realizar la prueba, funciona como
un interprete que se ejecuta paso a paso.
Ejemplos de Ejercicios:
Hacer un seudocódigo que imprima los números del 1 al 100.
ALGORITMO: imprimir los 100 primeros números
Comienzo
c 0;
MIENTRAS (c < 101) HACER
c c + 1;
ESCRIBIR c;
FINMIENTRAS
FIN
Ejemplo de prueba de escritorio
c ESCRIBIR c
0
1
1
2
2
3
3
…
…
99
99
100 100
101
Página 30 de 61
UNIVERSIDAD DE BUENOS AIRES - Facultad de Ciencias Económicas
Cátedra Teoría de Los Lenguajes y Sistemas Operativos
Hacer un pseudocódigo que imprima los números del 100 al 0, en orden decreciente.
ALGORITMO del 1 al 100 decreciente
Comienzo
c 100;
MIENTRAS (c <= 0) HACER
ESCRIBIR c;
c c – 1;
FINMIENTRAS
FIN
Hacer un pseudocódigo que imprima los números del 100 al 0, en orden decreciente.
ALGORITMO del 1 al 100 decreciente
Comienzo
c 100;
MIENTRAS (c <= 0) HACER
ESCRIBIR c;
c c – 1;
FINMIENTRAS
FIN
Hacer un programa que imprima la suma de los 100 primeros números.
ALGORITMO: suma
Comienzo
c 1;
suma 0;
MIENTRAS (c <= 100) HACER
suma suma + c;
c c + 1;
FINMIENTRAS
ESCRIBIR "La suma de los 100 primeros números es: “;
ESCRIBIR suma;
FIN
Hacer un pseudocódigo que imprima los números impares hasta el 100 y que imprima cuantos
impares hay.
ALGORITMO
Comienzo
c 1;
son 0;
MIENTRAS (c < 100) Hacer
ESCRIBIR c;
c c + 2;
son son + 1;
FINMIENTRAS
ESCRIBIR "El número de impares: “;
Página 31 de 61
UNIVERSIDAD DE BUENOS AIRES - Facultad de Ciencias Económicas
Cátedra Teoría de Los Lenguajes y Sistemas Operativos
ESCRIBIR son;
FIN
Hacer un seudocódigo que imprima todos los números naturales que hay desde la unidad
hasta un número que introducimos por teclado.
ALGORITMO natural
Comienzo
i0
n0
ESCRIBIR "Introduce un número: "
LEER n;
MIENTRAS (i < n) HACER
i i + 1;
ESCRIBIR i:
FINMIENTRAS
FIN
•
•
•
Realizar un programa que permita ingresar 18 números enteros y que:
– Sume los positivos
– Cuente cuántos fueron negativos
– Calcule el mayor de los impares
–
Realizar un programa que admita solamente el ingreso de números impares y que calcule
el promedio de los mismos.
– El programa termina ante el ingreso de 8 números válidos o ante un valor cero.
– Si no se ingresaron valores válidos deberá informarlo.
Realizar un programa para un negocio de venta de camperas cuyo precio unitario es de
$10 + iva (21%). Según la cantidad comprada se tiene un descuento según tabla adjunta:
Cantidad comprada
2a4
5a7
8 a 12
13 a 20
21 o mas
-
Porcentaje de descuento
10
12
15
20
30
El programa debe solicitar al cliente nombre y cantidad que quiere comprar.
El programa debe mostrar el total a abonar por cada cliente. El programa
termina ante el ingreso de un dato “SALIR” ingresado en la variable nombre.
Página 32 de 61
UNIVERSIDAD DE BUENOS AIRES - Facultad de Ciencias Económicas
Cátedra Teoría de Los Lenguajes y Sistemas Operativos
4. Estructuras de datos.
Ya vimos el concepto de datos con sus distintos tipos, ahora extenderemos este concepto a un
conjunto o grupo de datos.
Definicion: “Es un conjunto de datos reunidos bajo un único nombre colectivo”
Es una colección de datos que pueden ser caracterizados por su organización y las operaciones
que se definen en ella.
Existen dos clases de Estructuras de datos:
Estructura de Datos ESTATICA: Es en la que el tamaño ocupado en memoria se define antes
de que el programa se ejecute y no puede cambiarse dicho tamaño durante se ejecute el
programa.
Estas son:
Arreglos (Vector/Matriz)
Registro
Archivo (Fichero)
Conjunto (específicos del lenguaje Pascal)
Cadena (string)
Estructura de Datos DINAMICA: Es en la que el tamaño ocupado en memoria no tiene
limitaciones ni restricciones. Mediante el uso de un tipo de datos específico denominado
puntero, es posible construir estructuras de datos dinámicas que son soportadas por la mayoría de
los lenguajes de programación, y en aquellos que sí tienen estas características ofrecen
soluciones eficaces y efectivas en la solución de problemas complejos (Pascal ofrece la
posibilidad de estructuras de datos dinámicas).
Estas a su vez se dividen en dos:
Estructuras dinámicas lineales:
Lista (pila/cola)
Lista enlazada
Estructuras dinámicas no lineales
Árbol (binario, arbol-b, de búsqueda binaria)
Grafo
Arreglos.
ARREGLO LINEAL
Una variable con estructura de arreglo es un conjunto de variables de un mismo tipo:
Ej: VENTAS (n)
Donde VENTAS es el nombre de la variable y n es el índice.
La dimensión del arreglo es igual a la cantidad de componentes y es invariable una vez que se
define.
Página 33 de 61
UNIVERSIDAD DE BUENOS AIRES - Facultad de Ciencias Económicas
Cátedra Teoría de Los Lenguajes y Sistemas Operativos
EJERCICIO: Una empresa recibe mensualmente información sobre las ventas de cada una de sus
tres sucursales y desea obtener un listado de aquellas cuyas ventas superan el promedio de las
mismas.
Variables: ventas(I), promedio, I “nro de sucursal”
Algoritmo:
Calcular el promedio de ventas
Comprobar cual sucursal tiene ventas superiores al promedio
Informar
Refinaminetos sucesivos:
Inicializar variables
Para cada sucursal hacer
Ingresar ventas y acumular valores
Fin Para
Calcular promedio
Para cada sucursal hacer
Ingresar ventas comprobar si es mayor o igual al promedio
Fin Para
Mostrar resultados
ALGORITMO “ventas”
COMENZAR
Var tipo entero: I;
tipo real: ventas, Promedio ;
Promedio0;
Para I desde 1 hasta 3 hacer
leer ventas;
promedio promedio + ventas;
Fin para
Promedio Promedio / 3;
Para I desde 1 hasta 3 hacer
Leer ventas;
Si (ventas > Promedio) entonces
Escribir “ Sucursal : “ I, “ Venta : “ ventas;
FinSi;
FinPara;
Fin
Esto es válido para 3 sucursales.
Si tenemos 100
1 2
3 ..................
120 300 280
100
426
Tabla ventas de 1 a 100 valores
Ventas(2) es 300
Definimos arreglo lineal, tabla o vector de nombre venta.
Página 34 de 61
UNIVERSIDAD DE BUENOS AIRES - Facultad de Ciencias Económicas
Cátedra Teoría de Los Lenguajes y Sistemas Operativos
En venta(I) en donde I es una variable numerica cuyo valor es un número entero tal que I =
{1,2,....,100}
Venta (I) designa el I-enésimo elemento del arreglo
OPERACIONES DE ARREGLOS:
ASIGNACION
Ventas(8) 30
a la posición 8 del arreglo ventas le asigno el valor 30.
Asigno 0 a todos los elementos de un arreglo ventas de 30 elementos
Para I desde 1 hasta 30 hacer
Ventas (I) 0;
Fin para
ESCRIBIR
LEER
ARREGLOS BIDIMENSIONALES
Tiene un único nombre y dos índices (fila, columna)
El elemento del arreglo se indica Peso (5,2) = 68 kg.
El total de elementos del arreglo es la dimensión y se calcula como el producto del total de filas
por el total de columnas.
Ej.: Peso (10,4) entonces la dimensión es 10x4 = 40
Ejercicio: “Obesos Anónimos” tiene un programa de reducción de peso. Toma 10 miembros al
azar para verificar la efectividad del programa.
Éstos tendrán un control semanal de peso durante un mes.
Se desea determinar la siguiente información:
La variación promedio de peso de los 10 miembros para ese mes.
el número de individuos que han excedido esta variación
La variación promedio semanal, por individuo.
El informe de los datos recibidos semanalmente tiene la forma de una tabal de doble entrada,
donde:
Las FILAS (renglones) indican los pesos correspondientes a cada individuo
Las COLUMNAS indican los pesos semanales
Miembros
1
1
2
3
4
5
6
7
8
9
10
2
3
4
68 kg
Semanas
El participante 5 en la semana numero 2 pesó 68 kg.
METODO DE RESOLUCIÓN:
Para cada miembro se leen los pesos de las últimas 4 semanas.
Página 35 de 61
UNIVERSIDAD DE BUENOS AIRES - Facultad de Ciencias Económicas
Cátedra Teoría de Los Lenguajes y Sistemas Operativos
Se calcula la variación total del peso, por cada miembro acumulándose éstas variaciones en una
variable.
Luego se calcula la variación promedio mensual
ADEMÁS:
Para cada miembro se debe comprobar, si su variación de peso excede el promedio
recientemente calculado y en caso afirmativo, se debe incrementar el contador. Simultáneamente
se calcula la variación promedio semanal de cada individuo. (Este promedio se calcula
acumulando las diferencias entre los pesos de dos semanas sucesivas y dividiendo el promedio
por 3)
VARIABLES
PESO
Arreglo bidimensional, de tipo real de 10 filas y 4 columnas
PART
Variable de tipo entero que representa el primer índice del arreglo, (participantes)
SEMANA
Variable de tipo entero que representa el segundo índice del arreglo, (semanas)
VPM
Variable de tipo real que indica la variación promedio mensual del peso
VPS
Variable de tipo real que indica la variación promedio semanal del peso
CI
Variable de tipo entero que cuenta los individuos que han excedido la variación
promedio mensual
RESOLUCIÓN EN PSEUDOCODIGO:
ALGORITMO “OBESOS ANÓNIMOS”
COMENZAR
// DECLARACIÓN DE VARIABLES//
TIPO ENTERO: PART, SEMANA, CI;
TIPO REAL:
VPM, VPS, PESO (10,4)
// INICIALIZACION DE VARIABLES: CONTADOR Y ACUMULADORES//
CI 0;
VPM 0;
VPS 0 ;
// ENTRADA DE PESO Y CALCULO DE LA VARIACION MENSUAL //
PARA PART desde 1 hasta 10 hacer
PARA SEMANA desde 1 hasta 4 hacer
LEER PESO (PART, SEMANA);
FIN PARA
VPM VPM + PESO (PART,1) – PESO(PART,4);
FIN PARA
VPM VPM / 10;
ESCRIBIR “ LA VARIACION PROMEDIO MENSUAL ES: “, VPM;
// CONTAR LOS INDIVIDUOS CUYA VARIACIÓN DE PESO EXCEDE AL PROMEDIO
MENSUAL //
PARA PART desde 1 hasta 10 hacer
SI ( [PESO (PART, 1) – PESO (PART, 4)] > VPM ) ENTONCES
CI CI + 1;
FIN SI
// VARIACIÓN PROMEDIO SEMANAL POR INDIVIDUO //
PARA SEMANA desde 2 hasta 4 hacer
VPS VPS + PESO (PART, SEMANA) – PESO (PART, SEMANA-1);
FIN PARA
VPS VPS / 3;
Página 36 de 61
UNIVERSIDAD DE BUENOS AIRES - Facultad de Ciencias Económicas
Cátedra Teoría de Los Lenguajes y Sistemas Operativos
ESCRIBIR “ LA VARIACION PROMEDIO SEMANAL DEL MIEMBRO : “ PART, “
ES: “ VPS;
VPS 0;
FIN PARA
ESCRIBIR “EL NUMERO DE MIEMBROS EXCEDIDO DE LA VPM ES: “, CI;
FIN
Página 37 de 61
UNIVERSIDAD DE BUENOS AIRES - Facultad de Ciencias Económicas
Cátedra Teoría de Los Lenguajes y Sistemas Operativos
Ordenación, búsqueda e intercalación.
(sorting) (searching) - (merging)
ORDENACION:
En forma ascendente o descendente de los elementos o ítems de un conjunto.
Ej:
{ 7, 15, 23, 26, 78}
{a, arevalo, asturias, bilbao, de, dedo, zorro}
ORDENACION POR SELECCION:
Usamos dos arreglos. Dado un vector A, de n elementos, el método de Selección para ordenar al
mismo en forma ascendente, es el siguiente:
Encontrar el elemento más pequeño del arreglo (en una pasada: buscar por todo el arreglo y
seleccionar el elemento pequeño)
Transferirlo a la primera posición del arreglo B
Remplazar el elemento en el que vector A por un valor tope
Buscar el elemento mas pequeño en el vector A (segundo mas pequeño)
Transferirlo a la segunda posición del vector B
Remplazar el elemento en el Vector A por valor tope
Se continúa repitiendo el mismo procedimiento hasta agotar los n elementos del arreglo A
AMBIENTE DEL ALGORITMO
VARIABLE DESCRIPCION
A
Arreglo lineal de tipo numérico o cadena que contiene los n elementos a ser
ordenados
B
Arreglo lineal del mismo tipo que el vector A, contiene los elementos ordenados
N
Variable de tipo entero que representa la dimensión de A y B
I
Variable de tipo entero que se usa como índice en el arreglo A
J
Variable entera que se usa como índice en el arreglo B
TOPE
Variable del mismo tipo entero que cada elemento del Vector A (debe tener un
valor mayor que cualquier elemento del arreglo)
MINIMO
Variable entera que representa el valor del índice donde se encuentra el elemento
mínimo de A, en cada pasada.
ALGORITMO “SELECCIÓN”
COMENZAR
LEER A, TOPE;
Para J desde 1 hasta N hacer
MINIMO 1;
Para I desde 1 hasta N hacer
Si A(I) < A (MINIMO) entonces
MINIMO I;
FinSi
Fin Para
B(J) A (MINIMO);
A(MINIMO) TOPE;
Fin Para
Escribir B;
FIN.
Página 38 de 61
UNIVERSIDAD DE BUENOS AIRES - Facultad de Ciencias Económicas
Cátedra Teoría de Los Lenguajes y Sistemas Operativos
Analizamos la cantidad de comparaciones:
Para seleccionar cada elemento se efectúan N-1 comparaciones
Para seleccionar los n elementos se efectúan N (N-1) comparaciones
Si N es grande entonces la multiplicación se aproxima a N2
ORDENACION POR SELECCIÓN (IN SITU)
Ordenar un arreglo en forma no descendente.
Encontrar el menor elemento entre los N elementos del arreglo
Intercambiarlo con el primero del arreglo
A partir del segundo elemento encontrar entre los N-1 el menor e intercambiarlo con el 2do.
Repetir con los N-2, N-3 hasta que quede el mayor valor.
Ejemplo:
INICIAR
PASADA 1
PASADA 2
PASADA 3
PASADA 4
PASADA 5
21
2
2
2
2
2
35
35
8
8
8
8
17
17
17
14
14
14
8
8
35
35
17
17
14
14
14
17
35
21
2
21
21
21
21
35
Variables:
A
N
AUX
i,j
MINIMO
Arreglo
entera
mismo tipo que cada elemento de A
tipo entero usadas como índice de A
entero que representa el valor índice donde se encuentra el elemento mínimo
de A en cada pasada
Para i desde 1 hasta N-1 hacer
Asignar a mínimo el valor del índice correspondiente al menor elemento entre a(i),….,a(n).
Intercambiar a(i) con a(mínimo)
Fin Para
ALGORITMO “SELECCIÓN IN SITU”
Comenzar
Leer A;
Para i desde 1 hasta N-1 hacer
MINIMO 1;
Para j desde I+1 hasta N hacer
Si A(j) < A (MINIMO) entonces
MINIMO J;
Fin Si
Fin Para
AUX A(i);
A(i) A (MINIMO);
A(MINIMO) AUX;
Fin Para
Escribir A;
Fin.
Página 39 de 61
UNIVERSIDAD DE BUENOS AIRES - Facultad de Ciencias Económicas
Cátedra Teoría de Los Lenguajes y Sistemas Operativos
Cantidad de comparaciones:
(n-1)+(n-2)+……+(n-(n-1) = ½ n (n-1)
si n es grande entonces: ½ n2
(Mitad que el anterior)
ORDENACION POR INSERCION:
Ordenar A(1) con A(2),
Comparar A(3) con A(2); Si A(3) es >= a(2), seguir con el próximo elemento del arreglo, Sino
comparar A(3) con A(1), si A(3) es mayor o igual que A(1) insertar A(3) entre A(1) y A(2). Si
A(3) es menor que A(1) entonces transferir A(3) a la posición A(1), A(1) a la de A(2) y A(2) a la
de A(3).
En el siguiente ejemplo mostraremos el arreglo después de cada pasada:
INICIAL
I=2
I=3
I=4
I=5
I=6
I=7
I=8
14
14
14
14
35
35
21
21
42
42
42
42
42
42
35
26
Cantidad de comparaciones:
2/2 + 3/2 + 4/2 + …… + n/2 = ¼ (n2 + n-2)
Si n es grande, este valor es aproximadamente:
¼ n2
Variables:
A
N
AUX
i, k
SW
21
21
17
8
8
8
2
2
35
35
21
17
14
14
8
8
17
17
35
21
17
17
14
14
8
8
8
35
21
21
17
17
2
2
2
2
2
2
42
35
26
26
26
26
26
26
26
42
Arreglo
entera, cantidad de elementos del arreglo
mismo tipo que cada elemento de A
tipo entero usadas como índice de A
tipo booleano, toma solo los valores verdadero o falso.
ALGORITMO “POR INSERCION”
Comenzar
/* Blanquear Arreglos, contadores y acumuladores. Leer valores del Arreglo */
Para i desde 2 hasta N hacer
AUX A(i);
k i – 1;
sw Falso;
Mientras NO (sw) y k >= 1 Hacer
Si AUX < A (k) entonces
A(k+1) A(k);
k k – 1;
si no
sw verdadero;
Página 40 de 61
UNIVERSIDAD DE BUENOS AIRES - Facultad de Ciencias Económicas
Cátedra Teoría de Los Lenguajes y Sistemas Operativos
Fin Si
Fin mientras
A(k+1) AUX
Fin Para
Fin.
ORDENACION POR INTERCAMBIO: Compara pares adyacentes.
Comparo A(1) con A(2) intercambio si están desordenados
Comparo A(2) con A(3) intercambio si están desordenados
Y así sucesivamente comparo todos los elementos del arreglo.
En el siguiente ejemplo mostraremos el arreglo después de cada pasada:
INICIAL
I=2
I=3
I=4
I=5
I=6
I=7
21
21
17
8
8
8
2
35
17
8
14
14
2
8
17
8
14
17
2
14
14
8
14
21
2
17
17
17
14
35
2
21
21
21
21
42
2
26
26
26
26
35
Variables:
A
N
AUX
i, j
Arreglo
entera, cantidad de elementos del arreglo
mismo tipo que cada elemento de A
tipo entero usadas como índice de A
2
26
35
35
35
35
35
26
42
42
42
42
42
42
ALGORITMO “POR INTERCAMBIO”
Comenzar
/* Blanquear Arreglos, contadores y acumuladores. Leer valores del Arreglo */
Para i desde 1 hasta (N-1) hacer
Para j desde 1 hasta (N-1) hacer
Si A(j) > A (j+1) entonces
AUX A(j);
A(j) A(j+1);
A(j+1) AUX;
Fin Si
Fin para
Fin Para
Fin.
Cantidad de comparaciones:
Si n es grande, este valor es aproximadamente:
(n-1)2
Página 41 de 61
UNIVERSIDAD DE BUENOS AIRES - Facultad de Ciencias Económicas
Cátedra Teoría de Los Lenguajes y Sistemas Operativos
BUSQUEDA
Localizar un dato dentro de un conjunto (el dato puede estar o no)
BUSQUEDA SECUENCIAL
Consiste en encontrar un elemento k dentro de un conjunto de n elementos.
Variables
A
Arreglo de tipo numérico o carácter
K
variable de igual tipo que el arreglo
N
dimensión del arreglo de tipo entera
I
índice del arreglo de tipo entera
ALGORITMO “BUSQUEDA SECUENCIAL”
Comenzar
Leer A, K;
I 1;
Mientras I <= N hacer
Si K = A (I) entonces
Escribir “ en encontró en la posición : “ I;
I N+2;
Sino
I I + 1;
Fin Si
Fin Mientras
Si I = N+ 1 entonces
Escribir “ no se encontró el elemento”
Fin Si
Fin
Cantidad de comparaciones: (n+1)/2
BUSQUEDA BINARIA:
Para un arreglo previamente ordenado, voy analizando por mitades
Ej.
2
8
14
17
21
26
35
42
Suponemos que tenemos que buscar el número 35.
Entonces como el arreglo tiene 8 posiciones, sumo la primera y la última y la divido entre 2 y me
quedo con la parte entera.
(1+ 8) / 2 = 4
A (4) = 17, descarto los anteriores.
Busco en la segunda mitad del arreglo desde la posición 5 a la 8
(5+8)/2=6
A (6) = 26 descarto los anteriores y sigo buscando.
(7+8)/2=7
Página 42 de 61
UNIVERSIDAD DE BUENOS AIRES - Facultad de Ciencias Económicas
Cátedra Teoría de Los Lenguajes y Sistemas Operativos
A ( 7 ) = 35 , finalizó la búsqueda.
Variables
A
k
n
bajo, alto, central
Arreglo de tipo numérico o carácter
variable de igual tipo que el arreglo, valor a buscar.
dimensión del arreglo de tipo entera
variables enteras
ALGORITMO “BUSQUEDA BINARIA”
Comenzar
Leer A, k;
bajo 1;
alto n
central (bajo + alto) DIV 2
Mientras bajo <= alto y A(central) <> k hacer
Si k < A (central) entonces
alto central - 1;
Sino
bajo central + 1;
Fin Si
central (bajo + alto) DIV 2
Fin Mientras
Si k = A(central) entonces
Mostrar “El elemento se encuentra en la posición”, central;
Si no
Mostrar “No se encontró el elemento”;
Fin Si
Fin
Cantidad de comparaciones:
Log(n+1)/2
Cantidad de comparaciones: [Log (n+1)]/2
INTERCALACION:
Es el proceso de ordenar dos arreglos en uno único
Ej.
A1
A2
9
7
35
20
41
25
9
35
41
20
25
43
35
41
20
25
43
7
7
9
43
Página 43 de 61
UNIVERSIDAD DE BUENOS AIRES - Facultad de Ciencias Económicas
Cátedra Teoría de Los Lenguajes y Sistemas Operativos
7
9
35
41
25
43
20
35
7
9
20
41
25
43
41
7
9
20
25
35
43
7
9
20
25
35
41
43
7
9
Variables
A, B, C
n, m
i, j, k
20
25
35
41
43.
Arreglo de tipo numérico o carácter
dimensión del arreglo de tipo entera
variables enteras. Indices de los vectores
ALGORITMO “INTERCALACION”
Comenzar
Leer A, B
i 1;
j 1;
k 0;
Mientras i <= m y j <= n
Kk+1
Si A(i) < B(j) entonces
C(k) A(i);
ii+1
Sino
C(k) B(j)
j j + 1;
Fin Si
Fin Mientras
Si i <= m entonces
Para r desde i hasta m hacer
k k + 1;
C(k) A(r)
Fin para
Sino
Para r desde i hasta m hacer
k k + 1;
C(k) B(r)
Fin para
Fin si
Página 44 de 61
UNIVERSIDAD DE BUENOS AIRES - Facultad de Ciencias Económicas
Cátedra Teoría de Los Lenguajes y Sistemas Operativos
Fin
Estructuras dinámicas lineales.
Una estructura dinámica de datos puede modificar su estructura mediante la ejecucción de un
programa. Puede ampliar o limitar su tamaño mientras se ejecuta el programa.
LISTAS
LISTA LINEAL
Una lista lineal es un conjunto de elementos de un tipo dado que se encuentran ordenados y
pueden variar en número.
Los elementos de una lista lineal se almacenan normalmente en forma contigua, en posiciones
consecutivas de memoria.
Las líneas así definidas se denominan contiguas. Las operaciones que se pueden realizar con
listas lineales contiguas son:
1.
2.
3.
4.
5.
6.
7.
8.
Insertar, eliminar o localizar un elemento.
Denerminar el tamaño – número de elementos – de la lista.
Recorrer la lista para localizar un determinado elemento
Clasificar los elementos de la lista en orden ascendente o descendente
Unir dos o más listas en una sola
Dividir una lista en varias sublistas
Copiar a Lista
Borrar la lista
Una lista lineal se almacena en la memoria de la computadora en posiciones sucesivas o
adyacentes y se procesa como un array unidimensional. En este caso, el acceso a cualquier
elemento de la lista y la adición de nuevos elementos es fácil, sin embargo la inserción o borrado
requiere un desplazamiento de lugar de los elementos que le siguen y, en consecuencia, el diseño
de un algoritmo específico, siempre y cuando no sea en la cabecera o final de la lista.
Las operaciones directas de añadir y eleminar se efectúan únicamente en los extremos de la lista.
Esta limitación es una de las razones por las que esta estructura es poco utilizada.
Para permitir operaciones con listas se deben dimensionar éstos con tamaño suficiente para que
contengan todos los posibles elementos de la lista.
Ejemplo:
Se desea leer el elemento j-ésimo de una lista P.
El algoritmo requiere conocer el número de elementos de la lista (su longitud, L).
Los pasos a seguir para su resolución son:
- Conocer longitud de la lista L.
- si L = 0 visualizar “lista vacía”
si_no comprobar si el elemento j-ésimo está dentro del rango permitido de elementos
1<=j<=L; en este caso, asignar el valor del elemento P(j) a una variable B; si el elemento jésimo no está dentro del rango visualizar un mensaje de error “elemento solicitado no existe
en la lista”
Página 45 de 61
UNIVERSIDAD DE BUENOS AIRES - Facultad de Ciencias Económicas
Cátedra Teoría de Los Lenguajes y Sistemas Operativos
-
fin
LISTA ENLAZADA
Es un conjunto de elementos en los que cada elemento contiene la posición –o dirección – del
siguiente elemento de la lista.
Cada elemento (NODO)de la lista debe tener al menos dos campos:
Uno llamado info guarda el valor del elemento
Otro llamado enlace guarda la posición del siguiente elemento.
NODO
INFO
ENLACE
El último elemento de la lista tiene un enlace nulo. Puntero nil
Ejemplo: El gerente de un hotel quiere ingresar a medida de su ingreso los nombres de los
arqueros que asisten al congreso mundial y su habitación. Por otro lado desea disponer de una
lista de los mismos en forma alfabética.
Registro
1
2
3
4
5
6
7
8
9
10
11
12
-
Nombre
Van der Sar
Carrizo
Meola
Barthez
Goicochea
Higuita
Zenga
Gatti
Mondragon
Arevalo
Dida
Cordoba
-
Habitacion
136
425
201
305
135
403
302
204
109
309
214
110
-
Puntero
7
12
9
2
6
3
0 (final)
5
1
4
8
11
-
Arevalo
Barthez
Carrizo
Cordoba
Dida
Gatti
Goicochea
Higuita
Meola
Mondragon
Van der Sar
Zenga
Procesamiento de Listas enlazadas
Para procesar un alista enlazada son imprescindibles las siguientes informaciones:
Primer nodo (cabecera de la lista)
El tipo de sus elementos
Las operaciones que normalmente se ejecutan con listas incluyen:
Recuperar información de un nodo específico (acceso a un elemento)
Encontrar el nodo que contiene una información específica (localizar la posición de un elemento
dado)
Insertar un nuevo nodo en un lugar específico de la lista
Insertar un nuevo nodo en relación a una información particular.
Borrar (eliminar) un nodo existente que contiene información específica.
LISTA DOBLEMENTE ENLAZADA
En las listas lineales el recorrido de ellas sólo se podía hacer en una única forma, en sentido de
izquierda a derecha (principio a final). En numerosas ocasiones se necesita recorre las listas en
ambas direcciones.
Página 46 de 61
UNIVERSIDAD DE BUENOS AIRES - Facultad de Ciencias Económicas
Cátedra Teoría de Los Lenguajes y Sistemas Operativos
Las listas doblemente enlazadas se pueden recorrer en ambas direcciones, ya que cada nodo
consta de un campo INFO y dos campos enlace o punteros (anterior y siguiente), que apuntan
hacia delante y hacia atrás.
PILA
Una pila (stack) es un tipo especial de lista lineal en la que la inserción y borrado de nuevos
elementos se realiza sólo por un extremo que se denomina cima o tope (top)
La pila es una estructura con numerosas analogías en la vida real: una pila de platos, una pila de
monedas, una pila de camisas, etc.
Dado que las operaciones de insertar o eliminar se realizan por un solo extremo (el superior), los
elementos sólo pueden eliminarse en orden inverso al que se insertan en la pila. El último
elemento que se pone en la pila es el primero que se puede sacar; por ello, a estas estructuras se
les conoce por el nombre de LIFO (last-in, first-out), último en entrar, primero en salir)
Las operaciones más usuales son:
Push meter o poner,
operación de insertar un elemento en la pila
Pop sacar o quitar,
operación de eliminar un elemento en la pila
COLA
Las colas (queues) son otro tipo de estructura lineal de datos, en las que las eliminaciones se
realizan al principio de la lista, frente (front) y las inserciones se realizan en el otro extremo final
(rear).
Se las conoce como FIFO first in first out, primero en entrar , primero en salir.
Son utilizadas para almacenar datos que necesitan ser procesadas según el orden de llegada.
Ejemplos de la vida real, cola de un cine, caravana de autos, cola de un cajero.
Existe una variante llamada la doble cola, que es una cola bidimensional en las que las
inserciones y eleminaciones se pueden realizar en cualquiera de los dos extremos de la lista.
Funciones y Procedimientos
El diseño descendente permite obtener un programa que resuelva un problema dividiendo este en
subproblemas cada vez más sencillos.
Cada subproblema tiene asociado un pseudocódigo de alto nivel compuesto por acciones no
primitivas.
Cuando una de estas acciones no primitivas se repite en varios puntos del algoritmo es
interesante darle un nombre y reutilizarla.
Estas acciones con nombre se denominan subprogramas, pudiendo ser, a su vez, funciones y
Subrutinas o procedimientos
Los subprogramas facilitan la utilización de técnicas de diseño descendente para la construcción
de programas.
Los subprogramas:
· Facilitan la modularidad y estructuración de los algoritmos.
· Facilitan la lectura e inteligibilidad de los algoritmos.
· Permiten una economización del esfuerzo del programador al poder escribir código
reutilizable en muchas partes de un mismo algoritmo.
· Facilitan la depuración y mantenimiento de los programas.
Página 47 de 61
UNIVERSIDAD DE BUENOS AIRES - Facultad de Ciencias Económicas
Cátedra Teoría de Los Lenguajes y Sistemas Operativos
Los subprogramas pueden ser funciones y subrutinas.
as funciones son subrutinas con 0 ó más argumentos y que devuelven un único valor de retorno.
Las funciones pueden formar parte de expresiones o aparecer en la parte derecha de una
sentencia de asignación pero nunca pueden constituir una sentencia aislada o aparecer en la parte
izquierda de una asignación.
Las funciones son invocadas mediante su nombre seguido de los argumentos entre paréntesis.
Declaración e invocación de funciones
Una función es una operación que toma uno o más valores llamados argumentos y produce
un valor denominado resultado (es el valor de la función para los argumentos dados)
Las funciones incorporadas al sistema se denominan funciones internas o intrínsecas y las
funciones definidas por el usuario se denominan funciones externas.
Declaración: una función consta de una cabecera que comienza con el tipo del valor devuelto
por la función, seguido de la palabra función y del nombre y argumentos de dicha función.
Luego se escribe el cuerpo de la función que consiste en una serie de acciones o
instrucciones cuya ejecución hará que se asigne un valor al nombre de la función.
El algoritmo o programa llama o invoca a la función con el nombre de esta última en una
expresión seguida de una lista de argumentos que deben coincidir en cantidad, tipo y orden
con los de la función que fue definida. La función devuelve un único valor.
En la declaración es
<tipo de resultado> función <nombre de la función> (lista de parámetros formales)
[declaraciones locales]
Comienzo
Acciones
Devolver (<expresión>)
Fin función
Invocación de la función:
X <nombre función> ( lista de parámetros actuales)
Ejemplo: El algoritmo “Elementos de un rectángulo”, permite luego de ingresar la base y la
altura, hallar el perímetro y el área. Para el cálculo del perímetro, se invoca a una función que
lo calcule. El algoritmo muestra los datos de la base, la altura, el perímetro y el área.
ALGORITMO “Elementos de un rectángulo”
Comienzo
Variables
Entero: base, altura, perímetro, área;
Mostrar “Ingrese base del rectángulo: “, base;
Mostrar “Ingrese altura del rectángulo: “, altura;
Perím perimetro(base, altura);
area base * altura;
Mostrar “Los elementos del rectángulo son”;
Mostrar “base: “, base, “ altura: “, altura, “ area: “, area, “ perímetro: “,perím;
Fin
Página 48 de 61
UNIVERSIDAD DE BUENOS AIRES - Facultad de Ciencias Económicas
Cátedra Teoría de Los Lenguajes y Sistemas Operativos
Entero función perim(entero base, entero altura)
Variables
Entero y
Comienzo
y (base + altura) * 2;
devolver (y);
fin_funcion
función suma_enteros (x:entero, y:entero) dev z:entero
z x + y;
devolver z
finfunción
Definición de subrutinas o Procedimientos
Un procedimiento o subrutina es un subprograma que ejecuta un proceso específico. Ningún
valor está asociado al nombre, por lo tanto no puede ocurrir en una expresión. Un procedimiento
se llama escribiendo su nombre, cuando se invoca el procedimiento, los pasos que lo definen se
ejecutan y a continuación se devuelve el control al programa que lo llamó.
La declaración de una subrutina es similar a la de las funciones.
Procedimiento nombre (lista de parámetros formales)
….
Acciones
Fin procedimiento
El procedimiento se llama mediante la instrucción
Llamar_a nombre (lista de parámetros actuales)
La palabra llamar_a (call) es opcional y depende del lenguaje de programación.
procedimiento suma_uno (x:entero)
xx+1
Finprocedimiento
Diferencias entre funciones y subrutinas:
•
Un procedimiento es llamado desde el algoritmo o programa principal, mediante su
nombre y una lista de parámetros actuales, o bien con la instrucción llamar a (call). Al
llamar al procedimiento se detiene momentáneamente el programa que se estuviera
realizando y el control pasa la procedimiento llamado. Después de que las acciones del
procedimiento se ejecutan, se regresa a la acción inmediatamente siguiente a la que se
llamó.
Página 49 de 61
UNIVERSIDAD DE BUENOS AIRES - Facultad de Ciencias Económicas
Cátedra Teoría de Los Lenguajes y Sistemas Operativos
•
•
Las funciones devuelven un valor, los procedimientos pueden devolver 0,1 o n valores, y
en forma de lista de parámetros.
El procedimiento se declara igual que la función, pero su nombre no esta asociado a
ninguno de los resultados que obtiene.
VARIABLES LOCALES Y GLOBALES
Las variables utilizadas en los principales y subprogramas se clasifican en dos tipos:
· Variables locales.
· Variables globales.
• Una variable local es aquella que está declarada y definida dentro de un subprograma, en
el sentido de que está dentro de ese subprograma y es distinta de las variables con el
mismo nombre declaradas en cualquier parte del programa principal. El significado de
una variable se confina al procedimiento en el que está declarada. Cuando otro
subprograma utiliza el mismo nombre se refiere a una posición diferente en memoria. Se
dice que tales variable son locales al subprogramaen el que están declaradas.
Esta característica hace posible dividir grandes proyectos en piezas más pequeñas
independientes. Cuando diferentes programadores están implicados, ellos pueden trabajar
independientemente.
Página 50 de 61
UNIVERSIDAD DE BUENOS AIRES - Facultad de Ciencias Económicas
Cátedra Teoría de Los Lenguajes y Sistemas Operativos
A pesar del hecho importante de los subprogramas independientes y las variables locales, la
mayoría de los lenguajes proporcionan algún método para tratar ambos tipos de variables.
Una variable local a un subprograma no tiene ningún significado en otros subprogramas. Si un
subprograma asigna un valor a sus variables locales, este valor no es accesible a otros programas
es decir, no puede utilizar esta valor. A veces, también es necesario que una variable tenga el
mismo nombre en diferentes subprogramas.
Por el contrario las variables globales tienen la ventaja de compartir información de diferentes
subprogramas sin una correspondiente entrada en la lista de parámetros.
En un programa sencillo con un subprograma, cada variable u otro identificador es o bien local al
procedimiento o global al programa completo. Sin embargo, si el programa incluye
procedimientos que engloban a otros procedimientos –procedimientos anidados -, entonces la
noción de global/local es algo más complicada de entender.
El ámbito de un identificador (variables, constantes, procedimientos) es la parte del programa
donde se conoce el identificador. Si un procedimiento está definido localmente a otro
procedimiento, tendrá significado solo dentro del ámbito de ese procedimiento. A las variables
les sucede lo mismo; si están definidas local mente dentro de un procedimiento, su significa o
uso se confina a cualquier función o procedimiento que pertenezca a esa definición.
La siguiente figura muestra un esquema de un programa con diferentes procedimientos, algunas
variables son locales y otras globales. En esta citada figura se muestra el ámbito de cada
definición.
Los lenguajes que admiten variables locales y globales suelen tener la posibilidad explícita de
definir dichas variables como tales en el cuerpo del programa o, lo que es lo mismo, definir su
ámbito de actuación, para ello se utilizan las cabeceras de programas y subprogramas, con lo que
se definen los ámbitos.
Las variables definidas en un ámbito son accesibles en el mismo, es decir, en todos los
procedimientos interiores.
Página 51 de 61
UNIVERSIDAD DE BUENOS AIRES - Facultad de Ciencias Económicas
Cátedra Teoría de Los Lenguajes y Sistemas Operativos
COMUNICACIÓN CON SUBPROGRAMAS
PASO DE PARÁMETROS
Cuando un programa llama a un subprograma, la información se comunica a través de la lista de
Parámetros y se establece una correspondencia automática entre los parámetros formales y
actuales. Los parámetros actuales son sustituidos o utilizados en lugar de los parámetros
formales.
Existen diferentes métodos para la transmisión o el paso de parámetros o subprogramas. Es
preciso conocer el método adoptado por cada lenguaje , ya que la elección puede afectar a la
semántica del lenguaje. Dicho de otro modo, un mismo programa puede producir diferentes
resultados bajo diferentes sistemas de paso de parámetros.
Los parámetros pueden ser clasificados como:
entradas: (E)
las entradas proporcionan valores desde el programa que llama y que se utilizan dentro de un
procedimiento. En los programas función, las entradas son los argumentos en el sentido
tradicional:
salidas: (S)
Las salidas producen los resultados del subprograma: de nuevo si se utiliza el caso una función,
éste devuelve un valor calculado por dicha función, mientras que con procedimientos puede
calcularse cero, una o varias salidas:
entrada/salida (E/S)
Un solo parámetro se utiliza para mandar argumentos a un programa y para devolver resultados
Página 52 de 61
UNIVERSIDAD DE BUENOS AIRES - Facultad de Ciencias Económicas
Cátedra Teoría de Los Lenguajes y Sistemas Operativos
Desgraciadamente, el conocimiento del tipo de parámetros no es suficiente para caracterizar su
funcionamiento; por ello, examinaremos los diferentes métodos que se utilizan para pasar o
transmitir parámetros.
Los métodos mas empleados para realizar el paso de parámetros son:
• paso por valor (también conocido por parámetro valor)
• paso por referencia o diferencia (también conocido por parámetro variable)
• paso por nombre
• paso por resultado
Paso por Valor
El paso por valor se utiliza en muchos lenguajes de programación: por ejemplo, C, Modulo-2,
Pascal, Algol y Snobol. La razón de su popularidad es la analogía con los argumentos de una
función, donde los valores se proporcionan en el orden de cálculo de resultados. Los parámetros
se tratan como variables locales y los valores iniciales se proporcionan copiando los valores de
los correspondientes argumentos.
• Los parametros formales –locales a la función- reciben como valores iniciales los valores
de parámetros actuales y con ellos se ejecutan las acciones descritos en el subprograma.
• No se hace diferencia entre un argumento que es variable, Constante o expresión, ya que
solo importa el valor del argumento.
PASO POR REFERENCIA
En numerosas ocasiones se requieren que ciertos parámetros sirvan como parámetros de salida,
es decir, se devuelvan los resultados a la mitad o programas que llama. Este método se denomina
paso por referencia o también de llamada por dirección o variable. La unidad que llama pasa a
la unidad llamada la dirección del parámetro actual (que está en el ambiente de la unidad
llamante).
Una referencia al correspondiente parámetro formal se trata como una referencia a la posición de
memoria, cuya dirección se ha pasado. Entonces una variable pasada como parámetro real es
compartida, es decir, se puede modificar directamente por el subprograma.
Este método existe en FORTRAN, COBOL, Modulo-2, Pascal, PL/1 y Algol 68. La
característica de este método se debe a la simplicidad y su analogía directa con la idea de que las
variables tienen una posición de memoria asignada desde la cual se pueden obtener o actualizar
sus valores.
El área de almacenamiento (direcciones de memoria) se utiliza para pasar información de entrada
y/o salida: en ambas direcciones.
En este método los parámetros son de entrada/salida y los parámetros se denominan parámetros
variables.
La llamada por referencia es muy útil para programas donde se necesita la comunicación del
valor en ambas direcciones.
Página 53 de 61
UNIVERSIDAD DE BUENOS AIRES - Facultad de Ciencias Económicas
Cátedra Teoría de Los Lenguajes y Sistemas Operativos
Programación Orientada a Objetos
•
Tecnología orientada a objetos
– Una Perspectiva Histórica
– ¿Cuáles son las ventajas de un lenguaje orientado a objetos?
• El modelo orientado a objetos
– Objetos
– Clases
– Herencia
– Envío de mensajes
• Características asociadas a la POO
– Abstracción
– Encapsulamiento
– Ocultamiento
• Lenguajes de programación orientado a objetos
• Análisis y diseño orientado a objetos
• Resumen
Una Perspectiva Histórica
Tradicionalmente, la programación fue hecha en una manera secuencial o lineal, es decir una
serie de pasos consecutivos con estructuras consecutivas y bifurcaciones.
Los lenguajes basados en esta forma de programación ofrecían ventajas al principio, pero el
problema ocurre cuando los sistemas se vuelven complejos. Estos programas escritos al estilo
“espagueti” no ofrecen flexibilidad y el mantener una gran cantidad de líneas de código en sólo
bloque se vuelve una tarea complicada.
Página 54 de 61
UNIVERSIDAD DE BUENOS AIRES - Facultad de Ciencias Económicas
Cátedra Teoría de Los Lenguajes y Sistemas Operativos
Frente a esta dificultad aparecieron los lenguajes basados en la programación estructurada. La
idea principal de esta forma de programación es separar las partes complejas del programa en
módulos o segmentos que sean ejecutados conforme se requieran. De esta manera tenemos un
diseño modular, compuesto por módulos independientes que puedan comunicarse entre sí. Poco
a poco este estilo de programación fue reemplazando al estilo “espagueti” impuesto por la
programación lineal.
Entonces, vemos que la evolución que se fue dando en la programación se orientaba siempre a ir
descomponiendo más el programa. Este tipo de descomposición conduce directamente a la
programación orientada a objetos.
Pues la creciente tendencia de crear programas cada vez más grandes y complejos llevó a los
desarrolladores a crear una nueva forma de programar que les permita crear sistemas de niveles
empresariales y con reglas de negocios muy complejas. Para estas necesidades ya no bastaba la
programación estructurada ni mucho menos la programación lineal. Es así como aparece la
programación orientada a objetos (POO). La POO viene de la evolución de la programación
estructurada; básicamente la POO simplifica la programación con la nueva filosofía y nuevos
conceptos que tiene. La POO se basa en la dividir el programa en pequeñas unidades lógicas de
código. A estas pequeñas unidades lógicas de código se les llama objetos. Los objetos son
unidades independientes que se comunican entre ellos mediante mensajes. Veamos con mayor
detenimiento este tema.
¿Cuáles son las ventajas de un lenguaje orientado a objetos?
• Fomenta la reutilización y extensión del código.
• Permite crear sistemas más complejos.
• Relacionar el sistema al mundo real.
• Facilita la creación de programas visuales.
• Construcción de prototipos
• Agiliza el desarrollo de software
• Facilita el trabajo en equipo
• Facilita el mantenimiento del software
Lo interesante de la POO es que proporciona conceptos y herramientas con las cuales se modela
y representa el mundo real tan fielmente como sea posible.
El modelo Orientado a Objetos
Para entender este modelo vamos a revisar 4 conceptos básicos:
– Objetos
– Clases
– Herencia
– Envío de mensajes
Objetos
Entender que es un objeto es la clave para entender cualquier lenguaje orientado a objetos.
Existen muchas definiciones que se le ha dado al Objeto. Primero empecemos entendiendo que
es un objeto del mundo real. Un objeto del mundo real es cualquier cosa que vemos a nuestro
alrededor. Digamos que para leer este artículo lo hacemos a través del monitor y una
computadora, ambos son objetos, al igual que nuestro teléfono celular, un árbol o un automóvil.
Analicemos un poco más a un objeto del mundo real, como la computadora. No necesitamos ser
expertos en hardware para saber que una computadora está compuesta internamente por varios
Página 55 de 61
UNIVERSIDAD DE BUENOS AIRES - Facultad de Ciencias Económicas
Cátedra Teoría de Los Lenguajes y Sistemas Operativos
componentes: la tarjeta madre, el chip del procesador, un disco duro, una tarjeta de video, y otras
partes más. El trabajo en conjunto de todos estos componentes hace operar a una computadora.
Internamente, cada uno de estos componentes puede ser sumamente complicado y puede ser
fabricado por diversas compañías con diversos métodos de diseño. Pero nosotros no necesitamos
saber cómo trabajan cada uno de estos componentes, como saber que hace cada uno de los chips
de la tarjeta madre, o cómo funciona internamente el procesador. Cada componente es una
unidad autónoma, y todo lo que necesitamos saber de adentro es cómo interactúan entre sí los
componentes, saber por ejemplo si el procesador y las memorias son compatibles con la tarjeta
madre, o conocer donde se coloca la tarjeta de video. Cuando conocemos como interaccionan los
componentes entre sí, podremos armar fácilmente una computadora.
¿Qué tiene que ver esto con la programación? La programación orientada a objetos trabaja de
esta manera. Todo el programa está construido en base a diferentes componentes (Objetos), cada
uno tiene un rol específico en el programa y todos los componentes pueden comunicarse entre
ellos de formas predefinidas.
Todo objeto del mundo real tiene 2 componentes: características y comportamiento.
Por ejemplo, los automóviles tienen características (marca, modelo, color, velocidad máxima,
etc.) y comportamiento (frenar, acelerar, retroceder, llenar combustible, cambiar llantas, etc.).
Los Objetos de Software, al igual que los objetos del mundo real, también tienen características y
comportamientos. Un objeto de software mantiene sus características en una o más "variables", e
implementa su comportamiento con "métodos". Un método es una función o subrutina asociada a
un objeto.
Página 56 de 61
UNIVERSIDAD DE BUENOS AIRES - Facultad de Ciencias Económicas
Cátedra Teoría de Los Lenguajes y Sistemas Operativos
Para redondear estas ideas, imaginemos que tenemos estacionado en nuestra cochera un Ford
Focus color azul que corre hasta 260 km/h. Si pasamos ese objeto del mundo real al mundo del
software, tendremos un objeto Automóvil con sus características predeterminadas:
Marca = Ford
Modelo = Focus
Color = Azul
Velocidad Máxima = 260 km/h
Cuando a las características del objeto le ponemos valores decimos que el objeto tiene estados.
Las variables almacenan los estados de un objeto en un determinado momento.
Definición teórica: Un objeto es una unidad de código compuesto de variables y métodos
relacionados.
Las Clases
En el mundo real, normalmente tenemos muchos objetos del mismo tipo. Por ejemplo, nuestro
teléfono celular es sólo uno de los miles que hay en el mundo. Si hablamos en términos de la
programación orientada a objetos, podemos decir que nuestro objeto celular es una instancia de
una clase conocida como "celular". Los celulares tienen características (marca, modelo, sistema
operativo, pantalla, teclado, etc.) y comportamientos (hacer y recibir llamadas, enviar mensajes
multimedia, transmisión de datos, etc.).
Cuando se fabrican los celulares, los fabricantes aprovechan el hecho de que los celulares
comparten esas características comunes y construyen modelos o plantillas comunes, para que a
partir de esas se puedan crear muchos equipos celulares del mismo modelo. A ese modelo o
plantilla le llamamos CLASE, y a los equipos que sacamos a partir de ella la llamamos
OBJETOS.
Esto mismo se aplica a los objetos de software, se puede tener muchos objetos del mismo tipo y
mismas características.
Página 57 de 61
UNIVERSIDAD DE BUENOS AIRES - Facultad de Ciencias Económicas
Cátedra Teoría de Los Lenguajes y Sistemas Operativos
Definición teórica: La clase es un modelo o prototipo que define las variables y métodos
comunes a todos los objetos de cierta clase. También se puede decir que una clase es una
plantilla genérica para un conjunto de objetos de similares características.
Por otro lado, una instancia de una clase es otra forma de llamar a un objeto. En realidad no
existe diferencia entre un objeto y una instancia. Sólo que el objeto es un término más general,
pero los objetos y las instancias son ambas representación de una clase.
Definición Teórica: Una instancia es un objeto de una clase en particular.
Herencia
La herencia es uno de los conceptos más cruciales en la POO. La herencia básicamente consiste
en que una clase puede heredar sus variables y métodos a varias subclases (la clase que hereda
es llamada superclase o clase padre). Esto significa que una subclase, aparte de los atributos y
métodos propios, tiene incorporados los atributos y métodos heredados de la superclase. De esta
manera se crea una jerarquía de herencia.
Por ejemplo, imaginemos que estamos haciendo el análisis de un Sistema para una tienda que
vende y repara equipos celulares.
Página 58 de 61
UNIVERSIDAD DE BUENOS AIRES - Facultad de Ciencias Económicas
Cátedra Teoría de Los Lenguajes y Sistemas Operativos
En el gráfico vemos 2 Clases más que posiblemente necesitemos para crear nuestro Sistema.
Esas 2 Clases nuevas se construirán a partir de la Clase Celular existente. De esa forma
utilizamos el comportamiento de la SuperClase.
En general, podemos tener una gran jerarquía de Clases tal y como vemos en el siguiente gráfico:
Envío de Mensajes
•
Un objeto es inútil si está aislado. El medio empleado para que un objeto interactúe con
otro son los mensajes. Hablando en términos técnicos, los mensajes son invocaciones a
los métodos de los objetos.
Características asociadas al POO
Abstracción
La abstracción consiste en captar las características esenciales de un objeto, así como su
comportamiento. Por ejemplo, volvamos al ejemplo de los automóviles, ¿Qué características
podemos abstraer de los automóviles? O lo que es lo mismo ¿Qué características semejantes
tienen todos los automóviles? Todos tendrán una marca, un modelo, número de chasis, peso,
llantas, puertas, ventanas, etc. Y en cuanto a su comportamiento todos los automóviles podrán
acelerar, frenar, retroceder, etc.
En los lenguajes de programación orientada a objetos, el concepto de Clase es la representación
y el mecanismo por el cual se gestionan las abstracciones.
Por ejemplo, en Java tenemos:
public class Automovil {
// variables
// métodos
}
Encapsulamiento
El encapsulamiento consiste en unir en la Clase las características y comportamientos, esto es,
las variables y métodos. Es tener todo esto es una sola entidad. En los lenguajes estructurados
Página 59 de 61
UNIVERSIDAD DE BUENOS AIRES - Facultad de Ciencias Económicas
Cátedra Teoría de Los Lenguajes y Sistemas Operativos
esto era imposible. Es evidente que el encapsulamiento se logra gracias a la abstracción y el
ocultamiento que veremos a continuación.
La utilidad del encapsulamiento va por la facilidad para manejar la complejidad, ya que
tendremos a las Clases como cajas negras donde sólo se conoce el comportamiento pero no los
detalles internos, y esto es conveniente porque nos interesará será conocer qué hace la Clase pero
no será necesario saber cómo lo hace.
Ocultamiento
Es la capacidad de ocultar los detalles internos del comportamiento de una Clase y exponer sólo
los detalles que sean necesarios para el resto del sistema.
El ocultamiento permite 2 cosas: restringir y controlar el uso de la Clase. Restringir porque habrá
cierto comportamiento privado de la Clase que no podrá ser accedido por otras Clases. Y
controlar porque daremos ciertos mecanismos para modificar el estado de nuestra Clase y es en
estos mecanismos dónde se validarán que algunas condiciones se cumplan. En Java el
ocultamiento se logra usando las palabras reservadas: public, private y protected delante de las
variables y métodos.
Lenguajes de Programación Orientado a Objetos
En 1985, E. Stroustrup extendió el lenguaje de programación C a C++, es decir C con conceptos
de clases y objetos, también por esas fechas se creó desde sus bases el lenguaje EIFFEL.
En 1995 apareció el más reciente lenguaje OO, Java desarrollado por SUN, que hereda
conceptos de C++.
El lenguaje de desarrollo más extendido para aplicaciones Web, el PHP 5, trae todas las
características necesarias para desarrollar software orientado a objetos.
Además de otros lenguajes que fueron evolucionando, como el Pascal a Delphi.
Finalmente también otros lenguajes script como el ActionScript que si bien no es totalmente
orientado a objetos pero sí posee las características.
Análisis y diseño Orientado a Objetos
Para el desarrollo de software orientado a objetos no basta usar un lenguaje orientado a objetos.
También se necesitará realizar un análisis y diseño orientado a objetos.
El modelamiento visual es la clave para realizar el análisis OO. Desde los inicios del desarrollo
de software OO han existido diferentes metodologías para hacer esto del modelamiento, pero sin
lugar a duda, el Lenguaje de Modelamiento Unificado (UML) puso fin a la guerra de
metodologías.
Según los mismos diseñadores del lenguaje UML, éste tiene como fin modelar cualquier tipo de
sistemas (no solamente de software) usando los conceptos de la orientación a objetos. Y además,
este lenguaje debe ser entendible para los humanos y máquinas.
Actualmente en la industria del desarrollo de software tenemos al UML como un estándar para el
modelamiento de sistemas OO. Fue la empresa Racional que creó estas definiciones y
especificaciones del estándar UML, y lo abrió al mercado. La misma empresa creó uno de los
programas más conocidos hoy en día para este fin; el Racional Rose, pero también existen otros
programas como el Poseidon que trae licencias del tipo community edition que permiten su uso
libremente.
Página 60 de 61
UNIVERSIDAD DE BUENOS AIRES - Facultad de Ciencias Económicas
Cátedra Teoría de Los Lenguajes y Sistemas Operativos
El UML consta de todos los elementos y diagramas que permiten modelar los sistemas en base al
paradigma orientado a objetos. Los modelos orientados a objetos cuando se construyen en forma
correcta, son fáciles de comunicar, cambiar, expandir, validar y verificar. Este modelamiento en
UML es flexible al cambio y permite crear componentes plenamente reutilizables.
Resumen
•
•
•
•
•
•
•
•
•
¿Por qué seguimos buscando nuevas técnicas de desarrollo? Por el aumento de la
complejidad de los sistemas.
En un programa orientado a objetos tendremos a un conjunto de objetos colaborando
entre ellos.
La orientación a objetos es paradigma de que está de moda para el desarrollo de software.
Un objeto es una abstracción conceptual del mundo real que se puede traducir a un
lenguaje de programación orientado a objetos.
Un objeto del mundo real tiene características y comportamientos, y de la misma manera,
un objeto del mundo del software tiene variables y métodos.
¿Una Clase es una plantilla que define las variables y métodos a ser incluidas en un tipo
de objeto específico.
Los objetos también son llamados instancias de la Clase. Los objetos sólo almacenan su
estado. Se dice que un objeto tiene estado cuando tiene valores en sus variables.
Los objetos se comunican entre ellos usando los mensajes. Un mensaje es la invocación
de un método del objeto.
La orientación a objetos requiere de una metodología que integre el proceso de desarrollo
y un lenguaje de modelamiento con herramientas y técnicas adecuadas.
Página 61 de 61
