Ingeniería Técnica En Informática De Gestión Licenciado En

Transcript

Universidad Rey Juan Carlos Curso 2009/2010 Ingeniería Técnica en Informática de Gestión Licenciado en Dirección y Administración de Empresa + Ingeniería Técnica en Informática de Gestión Estructura de Datos y de la Información SEGUNDO PARCIAL 24-06-2010 Normas: La duración de esta parte del examen es de 2 horas y 30 minutos Todos los ejercicios se entregarán en hojas separadas, incluidos los que se dejen en blanco. En cada ejercicio se indica su puntuación total y, en su caso, el valor de los apartados que lo componen. No está permitido el uso de apuntes, libros ni teléfonos móviles. 1. (5 puntos) Un árbol binario de decisión es un árbol binario cuyos nodos internos representan preguntas sobre un determinado objeto o situación, y cuyas hojas representan las posibles categorías en las que es posible clasicar dicho objeto o situación. Las preguntas del árbol sólo pueden contestarse armativa o negativamente, de tal manera que el hijo izquierdo se encuentra asociado a las respuestas negativas y el derecho a las armativas. Por ejemplo, la gura 1 muestra un árbol binario de decisión que permite clasicar frutas en base a preguntas que hacen referencia a aspectos tales como el color, la forma, etc. no ¾color rojo? no si ¾diámetro >5cm? ¾forma redonda? no Plátano si ¾diámetro >10cm? no Limón ¾color verde? no ¾es duro? no si Pomelo Uva si no ¾diámetro >5cm? no si Manzana ¾diámetro >15cm? si Sandía si Uva Manzana si Cereza Figura 1: Ejemplo de árbol de decisión El siguiente diálogo representa un posible escenario de uso de una aplicación de toma de decisiones basada en este árbol. Como puede observarse, la aplicación formula preguntas al usuario que éste responde armativa o negativamente. La primera pregunta es la asociada a la raíz del árbol de decisión; las siguientes preguntas se determinan en función de las respuestas del usuario. La sesión termina cuando la aplicación alcanza una categoría del árbol. Aplicación> Usuario> Aplicación> Usuario> Aplicación> Usuario> Aplicación> Usuario> Aplicación> ¾Color verde? No ¾Color rojo? Sí ¾Diámetro >5cm? No ¾Es duro? No Es una cereza Los árboles binarios de decisión pueden especicarse mediante un tipo abstracto de datos ArbDecision compuesto por las siguientes operaciones: CrearCategoria: String → TipoArbDecision CrearPregunta: TipoArbDecision × String × TipoArbDecision → TipoArbDecision EsCategoria: TipoArbDecision → Booleano PARCIAL Pregunta: TipoArbDecision → String PARCIAL Categoria: TipoArbDecision → String PARCIAL SiguienteArbolDecision: TipoArbDecision × Booleano → TipoArbDecision Las dos primeras operaciones consisten en las generadoras del TAD. Concretamente, la primera permite crear un árbol de decisión compuesto únicamente por una categoría, mientras que la segunda permite asociar dos árboles de decisión a las respuestas armativa y negativa de una nueva pregunta. La operación EsCategoria devuelve cierto si el árbol representa una categoría (es decir, una hoja) y falso en caso contrario. Las operaciones Pregunta y Categoria devuelven la cadena de caracteres asociada al nodo raíz del árbol. Naturalmente, sólo están denidas en caso de que la raíz del árbol represente una pregunta o una categoría, respectivamente. La última operación devuelve el árbol de decisión asociado a una respuesta armativa o negativa a la pregunta del nodo raíz. El listado 1 muestra una implementación parcial de este TAD mediante el paquete ArbDecision. PACKAGE A r b D e c i s i o n IS TYPE T i p o A r b o l D e c i s i o n IS . . . Es_Categoria : EXCEPTION ; Es_Pregunta : EXCEPTION ; PROCEDURE C r e a r C a t e g o r i a ( c a t e g o r i a : S t r i n g ; a r b o l : IN OUT T i p o A r b o l D e c i s i o n ) ; PROCEDURE CrearPregunta ( arbol_no : pregunta : arbol_si : a r b o l : IN IN T i p o A r b o l D e c i s i o n ; IN S t r i n g ; IN T i p o A r b o l D e c i s i o n ; OUT T i p o A r b o l D e c i s i o n ) ; FUNCTION E s C a t e g o r i a ( a r b o l : T i p o A r b o l D e c i s i o n ) RETURN Boolean ; FUNCTION C a t e g o r i a ( a r b o l : T i p o A r b o l D e c i s i o n ) RETURN S t r i n g ; FUNCTION Pregunta ( a r b o l : T i p o A r b o l D e c i s i o n ) RETURN S t r i n g ; ... FUNCTION S i g u i e n t e A r b o l D e c i s i o n ( a r b o l : T i p o A r b o l D e c i s i o n ; r e s p u e s t a : Boolean ) RETURN T i p o A r b o l D e c i s i o n ; PRIVATE .... END A r b D e c i s i o n ; Listado 1: ArbDecision.ads Se pide: (a) (1.5 puntos) Basándose en la interfaz del paquete ArbDecision, implementar los siguientes subprogramas: (0.5 puntos) PROCEDURE CrearArbol ( a r b o l : IN OUT A r b D e c i s i o n . TipoArbDecision ) ; −− −− POST : El decisión propósito de la de figura este subprograma es simplemente construir el árbol de 2 ¾diámetro >15cm? no si ¾diámetro >5cm? no Sandía si Uva Manzana Figura 2: Árbol de ejemplo Solución: PROCEDURE CrearArbol ( a r b o l : IN OUT T i p o A r b o l D e c i s i o n ) IS arb_uva , arb_manzana , arb_sandia , arb_dia_5 : A r b D e c i s i o n . T i p o A r b o l D e c i s i o n ; BEGIN C r e a r C a t e g o r i a ( "Uva" , arb_uva ) ; C r e a r C a t e g o r i a ( "Manzana" , arb_manzana ) ; C r e a r C a t e g o r i a ( " Sandía " , arb_sandia ) ; CrearPregunta ( arb_uva , " ¾ d i á m e t r o > 5cm? " , arb_manzana , arb_dia_5 ) ; CrearPregunta ( arb_dia_5 , " ¾ d i á m e t r o > 15cm? " , arb_sandia , a r b o l ) ; END CrearArbol ; (1 punto) FUNCTION D e c i s i o n ( a r b o l : T i p o A r b o l D e c i s i o n ; fd_in : Ada . Text_IO . File_Type ; fd_out : Ada . Text_IO . File_Type ) RETURN S t r i n g IS −− −− −− −− −− −− −− −− −− PRE : ' arbol ' fichero el las que es el teclado ); y preguntas POST : La la árbol árbol al es de decisión ; utiliza ' fd_out ' función anteriormente , del un usuario es usuario el ( por implementa decir , para descriptor de decisión y correcta del es un sus donde la descriptor respuestas aplicación ejemplo , la pantalla ). proceso de toma el muestra categoría ' fd_in ' introducir recibe al sus árbol . La usuario respuestas función de las decisiones preguntas hasta devuelve que se de ( por ejemplo , escribe descrito correspondientes determina precisamente dicha categoría . PACKAGE Bool_Io IS NEW Ada . Text_Io . Enumeration_Io ( Boolean ) ; −− −− −− La lectura el procedimiento paquete BEGIN ... END D e c i s i o n ; de la respuestas Get ( f : del usuario se deberá Ada . t e x t _ I O . F i l e _ T y p e ; Bool_Io . Solución: FUNCTION D e c i s i o n ( a r b o l : T i p o A r b o l D e c i s i o n ; fd_in : Ada . Text_IO . File_Type ; v: realizar mediante Boolean ) del fd_out : Ada . Text_IO . File_Type ) RETURN S t r i n g IS PACKAGE Bool_Io IS NEW Ada . Text_Io . Enumeration_Io ( Boolean ) ; USE Bool_Io ; r e s p u e s t a : Boolean ; BEGIN IF E s C a t e g o r i a ( a r b o l ) THEN RETURN C a t e g o r i a ( a r b o l ) ; ELSE Put_Line ( fd_out , Pregunta ( a r b o l ) ) ; Get ( fd_in , r e s p u e s t a ) ; RETURN D e c i s i o n ( S i g u i e n t e A r b o l D e c i s i o n ( a r b o l , r e s p u e s t a ) , fd_in , fd_out ) ; END IF ; END D e c i s i o n ; (b) (1 puntos) Se desea implementar el TAD ArbDecision mediante el TAD Arbin explicado en clase y cuya interfaz está incluida en el anexo del enunciado. Nótese que dicha interfaz diere de la vista en clase en que posee la operación Alias, con la misma semántica de la operación del mismo nombre del TAD Arbol. Completar la declaración del TAD ArbDecision (chero .ADS) mostrada en el listado 1, con la especicación del tipo, la denición de su parte privada, así como de todos lo métodos auxiliares que se estimen necesarios. La denición del tipo TipoArbDecision deberá hacer uso del tipo Unbounded_String, el cual permite representar cadenas de caracteres de longitud variable (en este ejercicio, las preguntas y categorías del árbol de decisión). El paquete Ada.Strings.Unbounded.Unbounded_String, entre otras, contiene las siguientes operaciones: FUNCTION To_Unbounded_String (Source : in String) RETURN Unbounded_String;, para la transformación de un String estándar de Ada a una cadena Unbounded_String. FUNCTION To_String (Source : in Unbounded_String) RETURN String;, para la transformación de una cadena Unbounded_String a un String estándar. Solución: −−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−− −− Modulo : A r b o l _ D e c i s i o n −− F i c h e r o : Programa ( ) I n t e r f a z TAD ( x ) I m p l e m e n t . TAD ( ) O t r o s ( ) −− A u t o r ( e s ) : E . D . I . −− F e c h a : Mayo 2 0 1 0 −− −− D e s c r i p c i o n : TAD p a r a l a r e p r e s e n t a c i ó n d e Á r b o l e s d e a y u d a a l a −− d e c i s i ó n , b a s a d o s en e l TAD a r b i n −−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−− WITH Arbin , Ada . S t r i n g s . Unbounded ; USE Ada . S t r i n g s . Unbounded ; PACKAGE A r b D e c i s i o n IS −− definición −− Excepciones −− Operaciones privada y limitada del tipo TYPE T i p o A r b o l D e c i s i o n IS LIMITED PRIVATE ; Es_Categoria : EXCEPTION ; Es_Pregunta : EXCEPTION ; Constructoras Generadoras de datos PROCEDURE C r e a r C a t e g o r i a ( c a t e g o r i a : IN S t r i n g ; a r b o l : IN OUT T i p o A r b o l D e c i s i o n ) ; PROCEDURE CrearPregunta ( arbol_no : pregunta : arbol_si : a r b o l : IN IN T i p o A r b o l D e c i s i o n ; IN S t r i n g ; IN T i p o A r b o l D e c i s i o n ; OUT T i p o A r b o l D e c i s i o n ) ; FUNCTION E s C a t e g o r i a ( a r b o l : T i p o A r b o l D e c i s i o n ) RETURN Boolean ; FUNCTION C a t e g o r i a ( a r b o l : T i p o A r b o l D e c i s i o n ) RETURN S t r i n g ; −− −− PRE : El nodo EXCEPCION : actual es Es_Pregunta una si respuesta el nodo actual es una pregunta FUNCTION Pregunta ( a r b o l : T i p o A r b o l D e c i s i o n ) RETURN S t r i n g ; −− −− PRE : El nodo EXCEPCION : actual es Es_Categoria una si pregunta el nodo actual es una respuesta FUNCTION S i g u i e n t e A r b o l D e c i s i o n ( a r b o l : T i p o A r b o l D e c i s i o n ; r e s p u e s t a : Boolean ) RETURN T i p o A r b o l D e c i s i o n ; −− −− PRE : El nodo EXCEPCION : actual es Es_Categoria una si PROCEDURE Copiar ( d e s t i n o : IN o r i g e n : IN FUNCTION "=" ( a r b o l 1 , a r b o l 2 : PROCEDURE D e s t r u i r ( a r b o l : IN pregunta el nodo actual es una respuesta OUT T i p o A r b o l D e c i s i o n ; TipoArbolDecision ) ; T i p o A r b o l D e c i s i o n ) RETURN Boolean ; OUT T i p o A r b o l D e c i s i o n ) ; PRIVATE −− Instancia Arbin PACKAGE ArbinDec IS NEW Arbin ( TipoElemento => Unbounded_String ) ; USE ArbinDec ; TYPE T i p o A r b o l D e c i s i o n IS RECORD a r b o l : ArbinDec . TipoArbin ; END RECORD ; END A r b D e c i s i o n ; (c) (2.5 puntos) Realizar la implementación de todas las operaciones del TAD ArbDecision (chero .ADB) descritas en el listado 1. Solución: −−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−− −− Modulo : A r b o l _ D e c i s i o n −− F i c h e r o : Programa ( ) I n t e r f a z TAD ( ) I m p l e m e n t . TAD ( x ) O t r o s ( ) −− A u t o r ( e s ) : E . D . I . −− F e c h a : Mayo 2 0 1 0 −− −− D e s c r i p c i o n : TAD p a r a l a r e p r e s e n t a c i ó n d e Á r b o l e s d e a y u d a a l a −− d e c i s i ó n , b a s a d o s en e l TAD a r b i n −−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−− WITH Arbin , Ada . S t r i n g s . Unbounded ; USE Ada . S t r i n g s . Unbounded ; PACKAGE BODY A r b D e c i s i o n IS −− Operaciones Constructoras Generadoras PROCEDURE C r e a r C a t e g o r i a ( c a t e g o r i a : IN S t r i n g ; a r b o l : IN OUT T i p o A r b o l D e c i s i o n ) IS arb_vacio : ArbinDec . TipoArbin ; BEGIN ArbinDec . C re a r A r b o l V a ci o ( a r b o l . a r b o l ) ; ArbinDec . C re a r A r b o l V a ci o ( arb_vacio ) ; ArbinDec . C o n s t r u i r ( arb_vacio , To_Unbounded_String ( C a t e g o r i a ) , arb_vacio , arbol . arbol ) ; END C r e a r C a t e g o r i a ; PROCEDURE CrearPregunta ( arbol_no : IN T i p o A r b o l D e c i s i o n ; p r e g u n t a : IN S t r i n g ; a r b o l _ s i : IN T i p o A r b o l D e c i s i o n ; a r b o l : IN OUT T i p o A r b o l D e c i s i o n ) IS BEGIN ArbinDec . C o n s t r u i r ( arbol_no . a r b o l , To_Unbounded_String ( Pregunta ) , arbol_si . arbol , arbol . arbol ) ; END CrearPregunta ; FUNCTION E s C a t e g o r i a ( a r b o l : T i p o A r b o l D e c i s i o n ) RETURN Boolean IS BEGIN RETURN ArbinDec . EsArbolVacio ( ArbinDec . H i j o I z q d o ( a r b o l . a r b o l ) ) AND ArbinDec . EsArbolVacio ( ArbinDec . HijoDcho ( a r b o l . a r b o l ) ) ; END E s C a t e g o r i a ; FUNCTION S i g u i e n t e A r b o l D e c i s i o n ( a r b o l : T i p o A r b o l D e c i s i o n ; r e s p u e s t a : Boolean ) RETURN T i p o A r b o l D e c i s i o n IS arbol_decision : TipoArbolDecision ; BEGIN IF E s C a t e g o r i a ( a r b o l ) THEN RAISE Es_Categoria ; ELSIF r e s p u e s t a THEN −− SI −> derecha −− NO −> izquierda ArbinDec . A l i a s ( a r b o l _ d e c i s i o n . a r b o l , HijoDcho ( a r b o l . a r b o l ) ) ; RETURN a r b o l _ d e c i s i o n ; ELSE ArbinDec . A l i a s ( a r b o l _ d e c i s i o n . a r b o l , H i j o I z q d o ( a r b o l . a r b o l ) ) ; RETURN a r b o l _ d e c i s i o n ; END IF ; END S i g u i e n t e A r b o l D e c i s i o n ; FUNCTION C a t e g o r i a ( a r b o l : T i p o A r b o l D e c i s i o n ) RETURN S t r i n g IS BEGIN IF E s C a t e g o r i a ( a r b o l ) THEN RETURN To_String ( ArbinDec . Raiz ( a r b o l . a r b o l ) ) ; ELSE RAISE Es_Pregunta ; END IF ; END C a t e g o r i a ; FUNCTION Pregunta ( a r b o l : T i p o A r b o l D e c i s i o n ) RETURN S t r i n g IS BEGIN IF E s C a t e g o r i a ( a r b o l ) THEN RAISE Es_Categoria ; ELSE RETURN To_String ( ArbinDec . Raiz ( a r b o l . a r b o l ) ) ; END IF ; END Pregunta ; END A r b D e c i s i o n ; 2. (2 puntos) Se desea almacenar y recuperar información referente a regiones y poblaciones españolas en una tabla hash con direccionamiento abierto. Para poder identicar cada región o población se utilizará su código postal. Los códigos postales están compuestos por cinco dígitos, de los cuales los dos primeros representan la provincia a la que pertenece la región o población. A continuación se muestran las características de la tabla hash a implementar: Elemento: Región o población Clave: código postal N1 N2 N3 N4 N5 Máxima capacidad de la tabla: M AX = 11 Tipo del rango de dispersión: 0..M AX − 1 Función hash: hash(N1 N2 N3 N4 N5 ) = N3 N4 mod M AX Función de recolocación: rehash1 (p, i) = (p + i) mod M AX Se dispone de la siguiente relación de localidades y códigos postales como información: Código Postal Población Código Postal Población 28119 JOSE ANTONIO 28300 ARANJUEZ 28752 LOZOYUELA 28690 BRUNETE 28979 MAJUELO, EL 28650 CENICIENTOS 28600 NAVALCARNERO 28814 DAGANZO DE ARRIBA 28570 ORUSCO 28648 ENTREPINOS 28723 PEDREZUELA 28620 FRESNO, EL 28730 RIOSEQUILLO, DE 28260 GALAPAGAR 28756 SOMOSIERRA 28191 HORCAJO DE LA SIERRA La gura 3 muestra el estado de la tabla en un momento determinado. En dicha gura, cada población se representa mediante su inicial y los símbolos O (ocupada), B (borrada) y V (vacía) describen el estado de cada una de las posiciones del rango de dispersión. 0 1 2 3 4 5 6 7 8 9 10 O V O V V B O O V B O J O P F C Figura 3: Situación inicial de la tabla Se pide: (a) (1.5 puntos) Dada la situación inicial de la gura 3, aplicar las inserciones y eliminaciones que se estimen necesarias para alcanzar el estado de la tabla representado en la gura 4. Deberán representarse los estados intermedios alcanzados tras cada operación y la secuencia de posiciones exploradas. Se valorará utilizar el menor número de operaciones posible. 0 1 2 3 4 5 6 7 8 9 10 O V O V V B O O B O O J O P R A C Figura 4: Situación nal de la tabla Solución: Una posible secuencia de operaciones sería la siguiente: Eliminar(t,28620) Insertar(t,HORCAJO DE LA SIERRA) Insertar(t,RIOSEQUILLO) Insertar(t,ARANJUEZ) Eliminar(t,28191) Eliminar(t,28620) Insertar(t,HORCAJO DE LA SIERRA) 0 1 2 3 4 5 6 7 O V O V V B O B J O P 1 0 1 2 3 4 5 6 7 O V O V V B O B J O P 0 O J 5 0 O J 4 0 O J Insertar(t,RIOSEQUILLO) Insertar(t,ARANJUEZ) Eliminar(t,28191 1 2 V O O 6 1 2 V O O 5 1 2 V O O 3 4 5 6 7 V V B O O P R 1 3 4 5 6 7 V V B O O P R 3 4 5 6 7 V V B O O P R 8 9 10 V B O C 8 O H 1 8 O H 2 8 O H 1 8 B 1 9 10 B O C 9 10 B O C 3 4 9 10 O O A C 2 3 9 10 O O A C (b) (0.5 puntos) Partiendo de la situación inicial de la gura 3 y la siguiente función de recolocación (que sustituye a rehash1 ): rehash2 (p, i) = p + (−1)i−1   2 ! i−1 +1 mod M AX 2 representar los estados de la tabla alcanzados y la secuencia de posiciones exploradas tras realizar las siguientes operaciones (en el orden que se indica): Insertar(t,Riosequillo), Insertar(t,Aranjuez) Solución: Insertar(t,RIOSEQUILLO) 0 1 2 3 4 5 6 7 8 9 10 O V O V V B O O O B O J O P F R C 1 2 Insertar(t,ARANJUEZ) 0 1 2 3 4 5 6 7 8 9 10 O V O V V B O O O O O J O P F R A C 4 3 1 2 3. (3 puntos) Se desea implementar en Ada 95 una operación que permita obtener todos los nodos de un grafo que se encuentran a una determinada distancia mínima de un nodo dado. La operación se denomina NodosADistancia y su declaración es la siguiente: NodosADistancia: TipoGrafo × TipoNodo × Natural → TipoConjunto[TipoNodo] La operación es completa. En particular, si el nodo de entrada no pertenece al grafo la operación devuelve el conjunto vacío. Dado el grafo de caracteres g mostrado a continuación, los siguientes ejemplos ilustran la funcionalidad de la operación: NodosADistancia(g,'i',4)={} NodosADistancia(g,'b',0)={'b'} NodosADistancia(g,'b',1)={'a','q','c','r'} NodosADistancia(g,'b',2)={'p','s'} NodosADistancia(g,'b',3)={'d'} NodosADistancia(g,'b',4)={} NodosADistancia(g,'b',5)={} a b c d p q r s La operación deberá implementarse en el paquete hijo grafos.junio10. Se pide: (a) (0.5 puntos) Implementar la interfaz (chero .ads) del paquete grafos.junio10. Solución: GENERIC PACKAGE G r a f o s . Junio10 IS USE ConjuntoNodos ; PROCEDURE NodosADistancia ( g : IN TipoGrafo ; i n i c i o : IN TipoNodo ; d i s t a n c i a : IN N a t u r a l ; nodos : IN OUT TipoConjunto ) ; END G r a f o s . Junio10 ; (b) (2.5 puntos) Implementar el cuerpo (chero .adb) del paquete grafos.junio10. Solución: WITH C o n j u n t o s D e D i s c r e t o s . I t e r a d o r e s ; PACKAGE BODY G r a f o s . Junio10 IS PROCEDURE NodosADistancia ( g : IN TipoGrafo ; i n i c i o : IN TipoNodo ; d i s t a n c i a : IN N a t u r a l ; nodos : IN OUT TipoConjunto ) IS PACKAGE ConjuntoNodosIte IS NEW ConjuntoNodos . I t e r a d o r e s ; USE ConjuntoNodosIte ; PROCEDURE NodosADistancia_Aux ( g : IN TipoGrafo ; a c t u a l : IN TipoNodo ; d i s t a n c i a : IN N a t u r a l ; v i s i t a d o s : IN OUT ConjuntoNodos . TipoConjunto ; nodos : IN OUT TipoConjunto ) IS adys : TipoConjunto ; c u r s o r : TipoCursor ; nodo : TipoNodo ; BEGIN IF d i s t a n c i a =0 THEN Poner ( a c t u a l , nodos ) ; ELSE Poner ( a c t u a l , v i s i t a d o s ) ; Adyacentes ( g , a c t u a l , adys ) ; c u r s o r := PrimerCursor ( adys ) ; WHILE E s C u r s o r V a l i d o ( adys , c u r s o r ) LOOP nodo := Elemento ( adys , c u r s o r ) ; IF NOT P e r t e n e c e ( nodo , v i s i t a d o s ) THEN NodosADistancia_Aux ( g , nodo , d i s t a n c i a − 1, v i s i t a d o s , nodos ) ; END IF ; c u r s o r := S i g u i e n t e ( adys , c u r s o r ) ; END LOOP ; END IF ; END NodosADistancia_Aux ; v i s i t a d o s : ConjuntoNodos . TipoConjunto ; BEGIN CrearVacio ( nodos ) ; IF PerteneceNodo ( g , i n i c i o ) THEN CrearVacio ( v i s i t a d o s ) ; NodosADistancia_Aux ( g , i n i c i o , d i s t a n c i a , v i s i t a d o s , nodos ) ; END IF ; END NodosADistancia ; END G r a f o s . Junio10 ; ANEXO WITH Conjuntos , C o n j u n t o s D e D i s c r e t o s ; GENERIC TYPE TipoNodo IS (<>); WITH PACKAGE ConjuntoNodos IS NEW C o n j u n t o s D e D i s c r e t o s ( TipoNodo ) ; PACKAGE G r a f o s IS PACKAGE ArcosV IS TYPE TipoArco IS PRIVATE ; −− Generadores −− Observadoras FUNCTION CrearArco ( n1 , n2 : TipoNodo ; c : F l o a t ) RETURN TipoArco ; FUNCTION FUNCTION FUNCTION FUNCTION Extremo1 ( a : TipoArco ) RETURN TipoNodo ; Extremo2 ( a : TipoArco ) RETURN TipoNodo ; Coste ( a : TipoArco ) RETURN F l o a t ; "<" (A1 , A2 : TipoArco ) RETURN Boolean ; PRIVATE ... END ArcosV ; USE ArcosV ; PACKAGE ConjuntoArcos IS NEW Conjuntos ( TipoArco ) ; TYPE TipoGrafo IS PRIVATE ; −− Operaciones Constructoras −− Operaciones Observadoras −− Otras PROCEDURE Cr ea rGr af oVa ci o PROCEDURE I n s e r t a r N o d o ( g : n: PROCEDURE I n s e r t a r A r c o ( g : a: Generadoras ( g : OUT TipoGrafo ) ; IN OUT TipoGrafo ; IN TipoNodo ) ; IN OUT TipoGrafo ; IN TipoArco ) ; PROCEDURE Nodos ( g : IN TipoGrafo ; c : IN OUT ConjuntoNodos . TipoConjunto ) ; PROCEDURE Arcos ( g : TipoGrafo ; c : IN OUT ConjuntoArcos . TipoConjunto ) ; FUNCTION EsGrafoVacio ( g : TipoGrafo ) RETURN Boolean ; FUNCTION PerteneceNodo ( g : TipoGrafo ; n : IN TipoNodo ) RETURN Boolean ; PROCEDURE Adyacentes ( g : IN TipoGrafo ; n : IN TipoNodo ; c : IN OUT ConjuntoNodos . TipoConjunto ) ; PROCEDURE A r c o s I n c i d e n t e s ( g : IN TipoGrafo ; n : IN TipoNodo ; i n c i d e n t e s : IN OUT ConjuntoArcos . TipoConjunto ) ; operaciones constructoras PROCEDURE BorrarNodo ( g : IN OUT TipoGrafo ; n : IN TipoNodo ) ; PROCEDURE BorrarArco ( g : IN OUT TipoGrafo ; a : IN TipoArco ) ; PRIVATE ... END G r a f o s ; Listado 2: grafos.ads GENERIC −− elementos del árbol TYPE TipoElemento IS PRIVATE ; PACKAGE a r b i n IS −− definición −− excepciones privada y limitada del TYPE TipoArbin IS LIMITED PRIVATE ; ArbolVacio MemoriaAgotada −− : EXCEPTION ; : EXCEPTION ; Operaciones Constructoras −− −− tipo de el árbol la memoria datos está vacío dinámica está agotada Generadoras PROCEDURE C r e a r A rb o l V a c i o ( a r b i n : IN OUT TipoArbin ) ; PROCEDURE C o n s t r u i r ( i z q d o : IN TipoArbin ; e : IN TipoElemento ; dcho : IN TipoArbin ; a r b i n : IN OUT TipoArbin ) ; −− Operaciones Observadoras Selectoras FUNCTION Raiz ( a r b i n : TipoArbin ) RETURN TipoElemento ; FUNCTION H i j o I z q d o ( a r b i n : TipoArbin ) RETURN TipoArbin ; FUNCTION HijoDcho ( a r b i n : TipoArbin ) RETURN TipoArbin ; −− Otras Operaciones Observadoras −− −− Otras operaciones ( necesarias −− Otras FUNCTION EsArbolVacio ( a r b i n : TipoArbin ) RETURN Boolean ; se implementa debido a que el tipo de datos como LIMITED PRIVATE ) . PROCEDURE Copiar ( d e s t i n o : IN o r i g e n : IN FUNCTION "=" ( a r b i n 1 , a r b i n 2 : PROCEDURE D e s t r u i r ( a r b i n : IN OUT TipoArbin ; TipoArbin ) ; TipoArbin ) RETURN Boolean ; OUT TipoArbin ) ; operaciones PROCEDURE A l i a s ( d e s t i n o : IN OUT TipoArbin ; o r i g e n : IN TipoArbin ) ; PRIVATE ... END a r b i n ; Listado 3: arbin.ads GENERIC PACKAGE C o n j u n t o s D e D i s c r e t o s . I t e r a d o r e s IS TYPE TipoCursor IS PRIVATE ; −− Excepciones CursorNoValido : EXCEPTION ; FUNCTION PrimerCursor ( c o n j u n t o : TipoConjunto ) RETURN TipoCursor ; FUNCTION S i g u i e n t e ( c o n j u n t o : TipoConjunto ; c : TipoCursor ) RETURN TipoCursor ; FUNCTION E s C u r s o r V a l i d o ( c o n j u n t o : TipoConjunto ; c : TipoCursor ) RETURN Boolean ; FUNCTION Elemento ( c o n j u n t o : TipoConjunto ; c : TipoCursor ) RETURN TipoElemento ; PROCEDURE E l i m i n a r ( c o n j u n t o : IN OUT TipoConjunto ; c : IN OUT TipoCursor ) ; PRIVATE ... END C o n j u n t o s D e D i s c r e t o s . I t e r a d o r e s ; Listado 4: conjuntos-iteradores.ads GENERIC −− Parámetro del TAD TYPE TipoElemento IS (<>); −− PACKAGE C o n j u n t o s D e D i s c r e t o s IS TYPE TipoConjunto IS PRIVATE ; ConjuntoVacio : EXCEPTION ; −−O p e r a c i o n e s Constructoras tipo de −− datos el discreto conjunto está vacío Generadoras PROCEDURE CrearVacio ( c o n j : IN OUT TipoConjunto ) ; PROCEDURE Poner ( e : IN TipoElemento ; c o n j : IN OUT TipoConjunto ) ; −− Operaciones Observadoras Selectoras −− Operaciones Observadoras no −− Operaciones Constructoras FUNCTION E l e g i r ( c o n j : TipoConjunto ) RETURN TipoElemento ; selectoras FUNCTION EsConjuntoVacio ( c o n j : TipoConjunto ) RETURN Boolean ; FUNCTION P e r t e n e c e ( e : TipoElemento ; c o n j : TipoConjunto ) RETURN Boolean ; FUNCTION EsSubconjunto ( conj1 , c o n j 2 : TipoConjunto ) RETURN Boolean ; FUNCTION C a r d i n a l ( c o n j : TipoConjunto ) RETURN N a t u r a l ; no Generadoras PROCEDURE Q u i t a r ( e : IN TipoElemento ; c o n j : IN OUT TipoConjunto ) ; PROCEDURE Union ( conj1 , c o n j 2 : IN TipoConjunto ; s a l i d a : IN OUT TipoConjunto ) ; PROCEDURE I n t e r s e c c i o n ( conj1 , c o n j 2 : IN TipoConjunto ; s a l i d a : IN OUT TipoConjunto ) ; PRIVATE ... END C o n j u n t o s D e D i s c r e t o s ; Listado 5: conjuntos.ads PROCEDURE RecorridoProfundidad_Rec ( g : IN TipoGrafo ; i n i c i o : IN TipoNodo ; r e c o r r i d o : IN OUT T i p o L i s t a ) IS −− COMPLEJIDAD : O(N^ 2 ) , d o n d e N=C a r d i n a l ( TipoNodo ) PROCEDURE Profundidad_Aux ( g : IN TipoGrafo ; a c t u a l : IN TipoNodo ; r e c o r r i d o : IN OUT T i p o L i s t a ; v i s i t a d o s : IN OUT ConjuntoNodos . TipoConjunto ) IS adys : ConjuntoNodos . TipoConjunto ; c u r s o r : ConjuntoNodosIte . TipoCursor ; e l e m e n t o : TipoNodo ; BEGIN InsertarFinal ( recorrido , actual ) ; Poner ( a c t u a l , v i s i t a d o s ) ; Adyacentes ( g , a c t u a l , adys ) ; −− iterador sobre conjuntos : c u r s o r := ConjuntoNodosIte . PrimerCursor ( adys ) ; WHILE ConjuntoNodosIte . E s C u r s o r V a l i d o ( adys , c u r s o r ) LOOP e l e m e n t o := ConjuntoNodosIte . Elemento ( adys , c u r s o r ) ; IF NOT P e r t e n e c e ( elemento , v i s i t a d o s ) THEN −− O( 1 ) Profundidad_Aux ( g , elemento , r e c o r r i d o , v i s i t a d o s ) ; END IF ; c u r s o r := ConjuntoNodosIte . S i g u i e n t e ( adys , c u r s o r ) ; END LOOP ; END Profundidad_Aux ; v i s i t a d o s : ConjuntoNodos . TipoConjunto ; BEGIN IF NOT PerteneceNodo ( g , i n i c i o ) THEN Ada . E x c e p t i o n s . Raise_Exception ( NodoNoPertenece ' i d e n t i t y , MSG_NOPERTENECE) ; ELSE CrearVacia ( r e c o r r i d o ) ; CrearVacio ( v i s i t a d o s ) ; Profundidad_Aux ( g , i n i c i o , r e c o r r i d o , v i s i t a d o s ) ; END IF ; END RecorridoProfundidad_Rec ; Listado 6: Implementación recursiva del recorrido en profundidad sobre grafos