miércoles, 22 de junio de 2011

UNIDAD IX: DATOS COMPLEJOS (PILAS, COLAS, LISTAS, GRAFOS Y ÁRBOLE)

PILAS
Una pila es una lista de elementos en la que se pueden insertar y eliminar elementos sólo por uno de los extremos. Como consecuencia, los elementos de una pila serán eliminados en orden inverso al que se insertaron. Es decir, el último elemento que se metió a la pila será el primero en salir de ella. 
En la vida cotidiana existen muchos ejemplos de pilas, una pila de platos en una alacena, una pila de latas en un supermercado, una pila de papeles sobre un escritorio, etc.


Representación en Memoria 

Las pilas no son estructuras de datos fundamentales, es decir, no están definidas como tales  en los lenguajes de programación. Las pilas pueden representarse mediante el uso de: 

• Arreglos.
• Listas enlazadas.

La representación gráfica de una pila es la siguiente:





COLAS

Son listas lineales de información a las cuales de accede de un modo determinado siendo el de tipo FIFO (First In, First Out) (Primero en Entrar, Primero en Salir), lo que quiere decir que el primer dato en entrar es también el primer dato  en salir, en las colas no se permite el acceso aleatorio a ningún elemento concreto. Las recuperaciones de operaciones son destructivas (elimina el elemento) de la cola, si no es almacenado en otro lugar se destruye.

Su utilización principal en las simulaciones, planificación de sucesos, y los procesos de entrada y salida con buffer. 
Existen muchísimos ejemplos de colas en la vida real, como por ejemplo: personas esperando en un teléfono público, niños esperando para subir a un juego mecánico, estudiantes esperando para subir a un camión escolar, etc.

Representación en Memoria 

Podemos representar a las colas de dos formas: 

• Como arreglos 
• Como listas ordenadas 

En lo sucesivo, al apuntador del primer elemento lo llamaremos F, al último elemento A y MAXIMO para definir el número máximo de elementos en la cola. 

Las colas lineales se representan gráficamente de la siguiente manera:




LISTAS

Son colecciones de elementos, donde cada uno de ellos, además de almacenar información, almacena la dirección del siguiente elemento. Una lista es una estructura lineal de datos. Es decir, cada uno de sus componentes y un predecesor únicos, con excepción del último y del primero. 

Las listas pueden implementarse mediante arreglos,  resultando así una estructura estática. También puede ser una memoria dinámica (La cantidad de memoria ocupada puede modificarse durante la ejecución del programa). Una lista enlazada o encadenada es una colección de elementos ó nodos, en donde cada uno contiene datos y un enlace o liga. 

A continuación se muestra el esquema de una lista:


GRAFOS

Un grafo es un conjunto de puntos (vértices) en el  espacio, que están conectados por un conjunto de líneas (aristas). 

Los grafos son estructuras de datos dinámicas no lineales, utilizadas comúnmente en el análisis de redes, en diseño de circuitos eléctricos, en estrategias de mercados, cartografía, mapas conceptuales, matemáticas, planificación de procesos y muchas área del conocimiento. 

Aristas

Son las líneas con las que se unen las aristas de un grafo y con la que se construyen también caminos.  
Si la arista carece de dirección se denota indistintamente  {a, b} o  {b, a}, siendo a y b los vértices que une.  
Si {a ,b} es una arista, a los vértices a y b se les llama sus extremos.  

Aristas Adyacentes: Se dice que dos aristas son adyacentes si convergen en el mismo vértice.  
Aristas Paralelas: Se dice que dos aristas son paralelas si vértice inicial y el final son el mismo.  
Aristas Cíclicas: Arista que parte de un vértice para entrar en el mismo.  
Cruce: Son dos aristas que cruzan en un punto.  

Vértices

Son los puntos o nodos con los que esta conformado  un grafo. Llamaremos grado de un vértice al número de aristas de las que es extremo. Se dice que un vértice es `par' o `impar' según lo sea su grado.  

Vértices Adyacentes: si tenemos un par de vértices de un grafo (U, V) y si tenemos un arista que los une, entonces U y V son vértices adyacentes y se dice que U es el vértice inicial y V el vértice adyacente. 
Vértice Aislado: Es un vértice de grado cero.  
 Vértice Terminal: Es un vértice de grado 1. 


ÁRBOLES
Es una estructura de datos formada por nodos los cuales están conectados por aristas. Un árbol se define como un tipo de grafo que no contiene ciclos.

Árbol Vacío: Un árbol puede estar vacío; es decir no contener ningún nodo. 
Raíz: es el nodo que está al tope del árbol. Un árbol solo tiene una raíz.

Camino: es la secuencia de nodos que hay que visitar para llegar de un nodo a otro de un árbol.

Padre: En un árbol toda rama va de un nodo n1 a un nodo n2, se dice que n1 es padre de n2.

Hijo: todo nodo puede tener más de una arista que lo lleva a otro nodo por debajo de él. Estos nodos que se encuentran por debajo de un nodo dado se llaman hijos.

Hojas: son aquellos  nodos que no tienen hijos.  En un árbol solo puede haber una raíz pero puede haber muchas hojas.
Subárbol: Cualquier nodo se puede considerar como la raíz de un subárbol.






UNIDAD VIII: FUNCIONES Y PROCEDIMIENTOS EN TURBO PASCAL

PROCEDIMIENTOS

Un procedimiento es un programa que realiza una tarea específica. Puede recibir cero o más  valores del programa que llama y devolver cero o más valores al programa que realizó la  llamada. Un procedimiento está compuesto de un grupo de sentencias a las que se asigna  un nombre (identificador) y constituye una unidad de programa. La tarea asignada al procedimiento se ejecuta siempre que Pascal encuentra el nombre del procedimiento.  Los procedimientos es obligatorio declararlos y deben ser declarados antes de que puedan ser referenciados en el cuerpo del programa. En Pascal reciben el nombre de PROCEDURE. 

Declaración de un procedimiento  

Al igual que los identificadores, los procedimientos deben declararse dentro del cuerpo del programa. La declaración de un procedimiento NO indica a la computadora que ejecute las instrucciones dadas, sino que indica a la computadora cuáles son estas instrucciones y dónde están localizadas cuando sea necesario.


Cabecera del procedimiento 

Proporciona el nombre del mismo y, en caso de existir, una lista de parámetros formales.  

Ventajas de utilizar procedimientos  

  • La organización de un programa en procedimientos lo hace más fácil de escribir y depurar. Los procedimientos no deben exceder de 25 líneas. 
  • Facilita el diseño descendente.  
  • Los procedimientos se pueden ejecutar más de una vez en un programa y/o en diferentes programas, ahorrando tiempo de programación.  
  • El uso de procedimientos facilita la división de las tareas entre un equipo de programadores y se pueden comprobar individualmente.  


PARÁMETROS

Un parámetro es un método para pasar información (valores a variables) del programa principal a un procedimiento y viceversa.
Un parámetro es, prácticamente, una variable cuyo valor debe ser ya sea proporcionado por el programa principal al procedimiento o ser devuelto desde el procedimiento hasta el programa principal.


 Tipos de parámetros

  • Parámetros de entrada: Sus valores deben ser proporcionados por el programa principal. 
  • Parámetros de salida: Son parámetros cuyos valores se calcularán en el procedimiento y se deben devolver al programa principal para su proceso posterior.

Transferencia de información desde y/o hasta los procedimientos  

Existen dos tipos de procedimientos: 

  • Procedimientos sin parámetros: No existe comunicación entre el programa principal y los procedimientos ni viceversa. 
  • Procedimientos con parámetros: Existe comunicación entre el programa principal y  los procedimientos o entre dos procedimientos. 

FUNCIONES 
Una función es un subprograma que recibe como argumentos o parámetros datos de un tipo numérico o no numérico (char, string, bolean u otros) y devuelve un resultado. Esta característica le diferencia de un procedimiento. Una función es un subprograma que devuelve un único resultado al programa o subprograma 
que le llamó

CLASES USUALES DE FUNCIONES
• Las primeras son de tipo computacional que son diseñadas para realizar operaciones con los argumentos y regresan un valor basado en el resultado de esa operación.  
• Las segundas funciones son aquellas que manipulan información y regresan un valor que indican la terminación o la falla de esa manipulación.  
• Las terceras son aquellas que no regresan ningún valor, es decir son estrictamente procedurales.  

Comparación entre funciones y procedimientos  

• En vez de la palabra procedure se debe utilizar la palabra function  
• Al igual que en los procedimientos, el nombre de una función es un identificador. Sin embargo, el nombre de la función se refiere a la posición de memoria que contiene el valor devuelto por la función.  
• La lista de los parámetros formales son los identificadores utilizados para recibir valores del programa.  
• El tipo de datos del resultado coincide con el tipo expresado en la cabecera de la función.  
• En el cuerpo de la función tiene que existir una sentencia de asignación como la siguiente: Nombre_función := valor_función 
• La función sólo devuelve un valor, el procedimiento puede devolver cero, uno o varios valores.  
• El tipo de dato del resultado de la función debe estar indicado en la cabecera  y puede ser tipo char, integer, real o bolean. 

RECURSIVIDAD

En Pascal, a un procedimiento o función le es permitido no sólo invocar a otro procedimiento o función, sino también invocarse a sí mismo. Una invocación de éste tipo se dice que es recursiva.  
La función recursiva más utilizada como ejemplo es la que calcula el factorial de un número entero no negativo, partiendo de las siguientes definiciones:  
factorial (0) = 1 
factorial (n) = n*factorial(n-1), para n>0  

Permite que un procedimiento se llame a si mismo como un subprocedimiento. A través de esta poderosa herramienta se pueden expresar muchos algoritmos, sin embargo es poco utilizada, motivado quizás por el desconocimiento de los principales fundamentales que la sustentan.

miércoles, 1 de junio de 2011

Taller de 10 %

Evaluación de Laboratorio 3 y 4.                                      10%,    2ptos c/u

☺Escribir un programa en Pascal que sume, reste, multiplique y divida dos números:
x = 10       y = 2

☺Escribir un programa en Pascal que calcule el área de un rectángulo:
lado1 = 3 lado2 = 4
Área del rectángulo=lado1 * lado2

☺Escribir un programa en Pascal que calcule el área de un triángulo:
Base = 7          altura = 4        área del triángulo = (base * altura)/2

Escribir un programa que calcule la longitud y el área de una circunferencia:
Radio = 4  longitud de la circunferencia = 2 * PI * radio
                        Área de la circunferencia = PI * radio2

Escribir un programa en Pascal que evalúe la siguiente expresión:
(a+7*c)/(b+2-a)+2*b              a = 3,b = 6,c = 4

OJO con esta evaluación sera entregada el día 7/06/11 antes de presentar el parcial, recuerden que se esta evaluando el 5 % restante de laboratorio y el 5% del taller de teoría.

Buena Suerte y estudien todo lo referente al 2do corte para el martes