Algoritmos y Estructuras de Datos I

Facultad de Ciencias Exactas y Naturales

Universidad de Buenos Aires

Primer Cuatrimestre de 2000

Práctica 3

Primera Parte: Tipos Abstractos de Datos

Fecha sugerida de finalización:  18/05/2000.

Tipos Abstractos de Datos

Un conjunto de objetos más unas operaciones para manipularlos es, básicamente, lo que llamamos un tipo abstracto de datos (TAD). Por ejemplo, el tipo Color con las funciones de aridad cero (también llamadas constantes) Rojo, Verde, Azul, etc., y una operación binaria de igualdad (de color por color en bool) es todo lo que necesitamos para trabajar con el tipo abstracto de datos Color.

El TAD Conjunto de Naturales con la función de aridad cero Vacío (que devuelve el conjunto vacío), una función para agregar un elemento a un conjunto (de conjunto por nat en conjunto), una función para ver si un elemento pertenece a un conjunto (de nat por conjunto en bool) y una función para ver si un conjunto es vacío (de conjunto de nat en bool) es todo lo que necesitamos para tratar con conjuntos de naturales. Cualquier otra función para manipular conjuntos puede escribirse a partir de éstas.

Si miramos detenidamente las funciones de un TAD, veremos que hay algunas que nos sirven para armar elementos nuevos (ejemplo: vacío y agregar en conjuntos) y otras que nos permiten inspeccionar un elemento del tipo (ejemplo: pertenencia en conjuntos). A las primeras se las denomina constructores y a las segundas proyectores. Si extendemos el TAD Conjunto con operaciones de unión, intersección y diferencia, estas tres se escriben en función de Agregar y Vacío, o sea, en función de los constructores.

Consideramos que la forma de resolver un problema es identificar entidades (clientes, alquileres, inmuebles, ventas, etc.) y modelarlos con TAD (identificando las operaciones para manipularlos y la relación entre éstas). En esta materia vamos a tratar con problemas del estilo:

ü        Se cuenta con un Tipo matriz cuadrada de enteros. Tenemos una función dimensión de matriz en naturales para obtener la dimensión de una matriz y una función valor que recibe una matriz, un número de fila y un número de columna y devuelve un entero. Escribir la función Unitaria (de matriz en bool) que devuelve verdadero si la matriz recibida tiene ceros en todos lados menos en la diagonal, donde tiene unos.

La palabra abstracto en la denominación TAD, se refiere a que se trata de esconder la representación interna. Se podría asumir que una matriz es un vector de dos dimensiones, y dada una variable del tipo matriz, tratar de obtener el elemento M[f,c] (M es la matriz, [ ] es la función de vectores para acceder a un elemento). Supongamos que alguien desarrolló el tipo matriz y esto funciona porque por suerte el tipo matriz está definido así. Un día traen una nueva versión del tipo matriz y el programa deja de funcionar. Resulta que ahora las matrices son un conjunto de ternas del tipo fila, columna, valor (esto puede tener sentido para tratar matrices muy grandes cuyos elementos valen, en gran parte, cero). Si se hubiera usado en primera instancia la función Valor (que es la que habían dicho que debía usar para acceder al valor de la matriz en una fila dada y una columna) el programa hubiera seguido funcionando (ya que, obviamente, cuando el que desarrolló el tipo matriz, cambió la representación interna, modificó la implementación de la función valor).

Ejercicio 1

Se cuenta con el tipo enumerado Color, formado por las siguientes constantes: azul, amarillo, rojo (primarios), verde, naranja, violeta (secundarios), blanco y negro. Enriquecerlo, definiendo las siguientes operaciones:

i.                     primario :: Color ® Bool

ii.                    secundario :: Color ® Bool

iii.                  formado_por :: Color ® Color ® Bool          (Que retorna True si el primer parámetro esta formado por                                                                         el segundo. Por ejemplo, verde está formado por azul)

Ejercicio 2

Se tiene el tipo enumerado Día, formado por las constantes lunes, martes, miércoles, . . ., domingo. Enriquecerlo, definiendo las siguientes operaciones:

i.                     siguiente :: Día ® Día

ii.                    es_laborable :: Día ® Bool                             (lunes a viernes)

iii.                  es_fin_de_semana :: Día ® Bool                    (sábado o domingo)

Ejercicio 3

Se tiene definido el tipo Vector, con las siguientes operaciones:

·       abscisa :: Vector ® Real, que devuelve la componente x del vector.

·       ordenada :: Vector ® Real, que devuelve la componente y del vector.

Sobre ese tipo, definir las siguientes operaciones:

i.                     colineales :: Vector ® Vector ® Bool

ii.                    igual_x :: Vector ® Vector ® Bool                               (tienen la misma componente x)

iii.                  igual_y :: Vector ® Vector ® Bool                               (tienen la misma componente y)

iv.                  módulo :: Vector ®Real                    (se dispone de la operación raíz cuadrada, sqrt :: real ® real)

v.                   producto_escalar :: Vector ® Vector ® Real

Ejercicio 4

Se tiene definido el tipo MatrizCuadrada (de naturales), que consta de las siguientes operaciones:

·       dimensión :: MatrizCuadrada ® Nat, que devuelve el tamaño de la matriz.

·       valor :: MatrizCuadrada ® Fila ® Columna ® Nat, que devuelve el valor de la casilla indicada.

Los tipos Fila y Columna son sinónimos de Nat.

Ejemplo:

                Sea m la siguiente matriz cuadrada:

                Entonces dimensión m es 3, valor m 1 2 es 1 y valor m 3 2 es 4.

Definir las siguientes operaciones:

i.                     todas_iguales :: MatrizCuadrada ® Bool, que indica si todas las casillas de la matriz cuadrada tienen el mismo valor.

ii.                    identidad :: MatrizCuadrada ® Bool, que indica si la matriz es una matriz identidad. La matriz identidad es aquélla con 0 en todas las posiciones, excepto en las casillas de la diagonal, que tienen 1.

iii.                  máximo :: MatrizCuadrada ® Nat, que devuelve el valor máximo de la matriz.

iv.                  mínimo :: MatrizCuadrada ® Nat, que devuelve el valor mínimo de la matriz.

v.                   Redefinir la función de i, ahora usando solamente iii y iv.

Ejercicio 5

Se cuenta con el tipo Polinomio (de coeficientes naturales), que consta de las siguientes funciones:

·       grado :: Polinomio ® Nat, que permite saber el grado del polinomio.

·       coeficiente :: Polinomio ® Nat ® Nat, que permite saber el coeficiente del término de grado n del polinomio.

Ejemplos:              grado (2x³ + 8) = 3

                               coeficiente (2x³ + 8)  0 = 8

                               coeficiente (2x³ + 1)  1 = 0

                               coeficiente (2x³ + 1)  3 = 2

Definir la función evaluar :: Polinomio ® Nat ® Nat, que devuelve el valor del polinomio en el punto dado.

Ejercicio 6

Se tiene definido el tipo Tablero con las siguientes funciones:

·       cant_filas :: Tablero ® Nat, que devuelve la cantidad de filas de un tablero.

·       cant_columnas :: Tablero ® Nat, que devuelve la cantidad de columnas de un tablero.

·       color_casilla :: Tablero ® Fila ® Columna ® Color, que devuelve el color de una determinada casilla de un tablero, que puede ser solamente blanco o negro; si no es una casilla válida da error.

·       pintar_negro :: Tablero ® Fila ® Columna ® Tablero, que devuelve un tablero igual al original salvo por la casilla parámetro, que ahora es negra. Si no es una casilla válida devuelve un tablero igual al original.

Los tipos Fila y Columna son sinónimos de Nat. Una casilla es una Fila y una Columna. Las casillas pueden ser blancas o negras. El rango de las filas es 1 . . cant_filas, y el rango de las columnas es 1 . . cant_columnas.

Definir las siguientes funciones:

i.  cantidad_bloques_negros :: Tablero ® Nat

Esta función devuelve la cantidad de “bloques” negros que hay en el tablero, donde un “bloque” es un cuadrado de dos por dos casillas, todas negras. No importa que los bloques estén superpuestos.

Ejemplos: