02 Tda
02 Tda
02 Tda
Estructura de datos
TDA
Juan Jess Gutirrez Garca
Abstraccin
Del griego y del latn abstractio Operacin mediante la cual cualquier cosa es elegida como objeto de su percepcin, atencin, observacin, consideracin, investigacin, estudio, etc y aislada de otras cosas con las cuales se encuentra en una relacin cualquiera. Aislar la cosa elegida de las otras con las cuales se halla en relacin Adoptar como objeto especfico de consideracin aquel con que ste queda aislado [1]
[1] Nicola Abbagnano. Diccionario de filosofa. Fondo de Cultura econmica. Mxico. 2001.
06/02/2013
TDA
Abstract Data Type (WP) In computer science, an abstract data type (ADT) is a mathematical model for a certain class of data structures that have similar behavior; or for certain data types of one or more programming languages that have similar semantics. An abstract data type is defined indirectly, only by the operations that may be performed on it and by mathematical constraints on the effects (and possibly cost) of those operations [2].
[2] Barbara Liskov, Programming with Abstract Data Types, in Proceedings of the ACM SIGPLAN Symposium on Very High Level Languages, pp. 50--59, 1974, Santa Monica, California
Definition: A set of data values and associated operations that are precisely specified independent of any particular implementation. Also known as ADT.
Note: Since the data values and operations are defined with mathematical precision, rather than as an implementation in a computer language, we may reason about effects of the operations, relations to other abstract data types, whether a program implements the data type, etc.
06/02/2013
One of the simplest abstract data types is the stack. The operations new(), push(v, S), top(S), and popOff(S) may be defined with axiomatic semantics as following.
new() returns a stack popOff(push(v, S)) = S top(push(v, S)) = v
where S is a stack and v is a value. (The usual pop operation is a combination of top, to return the top value, and popOff, to remove the top value.)
From these axioms, one may define equality between stacks, define a pop function which returns the top value in a non-empty stack, etc. For instance, the predicate isEmpty(S) may be added and defined with the following additional axioms.
isEmpty(new()) = true isEmpty(push(v, S)) = false
06/02/2013
Haskel example
06/02/2013
Especificaciones
Formal
Una notacin que permite construir los TDA y sus propiedades
Informal
Una descripcin texto que permite entender el funcionamiento
Notacin
especificacin NOMBRE-ESPEC usa BOOLEANOS, OTRA-ESPEC, OTRA-MAS tipos nombre-tipo operaciones c: f: nombre-tipo1, ...nombre-tipon g: nombre-tipo1, ...nombre-tipom operaciones privadas p: nombre-tipo1, ...nombre-tipol g: nombre-tipo1, ...nombre-tipok variables x, y : nombre-tipo z : otro-tip Ecuaciones t1 = t2 t1 = t2 <= c1 = c1 Fin de especificacin
06/02/2013
Ejemplo
especificacin BOOLEAN tipos bool operaciones cierto : falso: _ : bool _^_ : bool bool _ _ : bool bool variables b : bool Ecuaciones b =b cierto ^ b = b falso ^ b = falso cierto b = cierto falso b = b Fin de especificacin bool {constructora} bool {constructora} bool bool bool
Ejemplo
especificacin BOOLEAN tipos bool operaciones cierto : falso: _ : bool _^_ : bool _ _ : bool variables b : bool Ecuaciones b =b cierto ^ b = b falso ^ b = falso cierto b = cierto falso b = b Fin de especificacin bool {constructora} bool {constructora} bool bool bool
06/02/2013
Informal
LIFO, FIFO (Last input first output, First input first output)
Formal
especificacin PILA[elem] Usa BOOLEANOS tipos pila operaciones pila-vaca : apilar : elemento pila desapilar : pila cima: pila es-pila-vaca? variables e : elemento p: pila Ecuaciones desapilar(pila-vaca) = error desapilar(apilar(e, p)) = p es-pila-vaca(pila-vaca) = cierto es-pila-vaca(apilar(e, p)) = falso Fin de especificacin
06/02/2013
Formal
Extender la especificacin de las pilas con las siguientes operaciones Consultar el nmero de elementos en una pila Consultar el elemento de fondo de una pila Obtener la inversa de una pila Duplicar una pila p, de forma que cada elemento de p aparezca apilado dos veces seguidas, conservando el mismo orden relativo que en p Concatenar dos pilas colocando los elementos de la segunda sobre los de la primera Entremezclar dos pilas, donde la pila resultante se obtiene apilando alternativamente los elementos de las pilas argumento, empezando por el fondo de la primera pila
Formal
especificacin PILA+[elem] Usa PILA[elem], NATURALES operaciones profundidad : fondo : pila inversa : pila duplicar: pila concatenar : pila pila entremezclar: pila pila variables e : elemento p: pila Ecuaciones profundidad (pila-vaca) = 0 profundidad (apilar(e,p)) = 1+profundidad(p) fondo(pila-vaca) error fondo(apilar(e,p)) e <= es-vaca-pila(p) fondo(apilar(e,p)) fondo(p) <= es-vaca-pila(p) Fin de especificacin nat p elemento pila pila pila pila
06/02/2013
Ejercicio
Una pila puede considerarse como un cambio de va, los vagones numerados 1,2,3,,n estn sobre la va izquierda y se desea reacomodarlos (permutarlos) al salir sobre la pista de la mano derecha.
Ejercicio
06/02/2013
Ejercicio
Practica
Para n=3 vagones encuentre todas las posibles permutaciones que pueden obtenerse Lo mismo para n = 4 Lo mismo para n = 5
10
06/02/2013
Preguntas
Alguna pregunta?
11