Árboles y grafos

rboles y grafos

rboles y grafosVladimir Tmara Patio. 2004. Dominio pblico. Sin garantas. Agradecemos que como fuente se cite: http://structio.sourceforge.net/guias/arbgraf/Este escrito se dedican a nuestro Padre Creador, a su santo Espritu y a Jess su Hijo y maestro nuestro.

Captulo 1 Introduccin y definicioneslogro: Define grafo, bosque y rbol logro: Emplea rboles binarios

1.1 DefinicionesIndicadores de logro: indicador: Define diversos tipos de grafo indicador: Define rbol indicador: Implementa y emplea un TAD para rboles binarios En este contexto rboles y grafos se refiere a estructuras de datos que permiten organizar y mantener informacin en un computador. Esta forma se inspira una forma de organizar informacin con lpiz y papel usando nodos y flechas entre los nodos (a esas flechas tambin se les llama arcos, a los nodos tambin se les llama vrtices). Los grafos y rboles en papel son apropiados por ejemplo para capturar slo una parte de la informacin de objetos, situaciones y otros tipos de informacin (i.e son apropiados para abstraer). En un computador adems de permitir organizar informacin, resultan estructuras tiles para resolver ciertos tipos de problema (por ejemplo pueden emplearse rboles AVL para mantener informacin ordenada de forma eficiente). Para jugar, entender y emplear mejor grafos (y rboles) varias personas (e.g Euler) han propuesto definiciones; a partir de estas definiciones y con ayuda de razonamientos lgicos han demostrado propiedades. Un mnimo de definiciones y de propiedades de grafos y rboles (con estilo inspirado en [6]) se presenta a continuacin. Note que para ver mejor esta pgina puede requerir configurar su navegador para que presente smbolos especiales, que se esperan con el tipo de letra de symbol. En el caso del navegador Mozilla, y suponiendo que en su sistema ya est instalado y configurado para Mozilla el tipo de letra para smbolos marque el botn de chequeo que permite que el documento use otras fuentes, en el men apariencia del dilogo de preferencias (elemento del men editar).

1.1.1 Teora

Grafos Un grafo G es una pareja G=(V,A), donde V es un conjunto finito (i.e vrtices) y A es un subconjunto del conjunto de parejas no ordenadas de V (i.e arcos). Por ejemplo G=({a,b,c},{{a,c},{c,b}}), que se representa grficamentehttp://structio.sourceforge.net/guias/arbgraf/arbgraf.html[03/08/2011 12:41:31 a.m.]

rboles y grafos

en la figura 1.1.

Figure 1.1: Ejemplo de grafo

Dado un grafo G con V(G) denotamos el conjunto de vrtices y con A(G) denotamos el conjunto de arcos. Decimos que un arco {x,y} A(G) une los vrtices x e y; as que x,y denota el mismo arco que {y,x}. Si {x,y} es un arco, decimos que x e y son extremos del arco, tambin decimos que x es adyacente o vecino de y. Un grafo G'=(V',A') es subgrafo de G=(V,A) si V' V y A A'. En tal caso escribimos G' G. Si G' contiene todos los arcos de G que unen dos vrtices de V' decimos que G' es un subgrafo inducido por V' y se denota por G[V']. El orden de un grafo G es el nmero de vrtices, tambin se denota por G 1 . El tamao de G es el nmero de arcos, y se denota por a(G). Decimos que dos grafos son isomorfos si hay una correspondencia entre sus conjuntos de vrtices que preserva la adyacencia. As que G=(V,E) es isomorfo a G'=(V',E') si hay una biyeccin j: V V' tal que x,y E si y solo si j(x)j(y) E'. Entonces dos grafos isomorfos tienen el mismo orden y el mismo tamao. El tamao de un grafo de orden n es al menos 0 y a lo sumo ( 2 n ). Un grafo de orden n y tamao ( 2 n ) se llama un n-grafo completo2 y se denota por Kn ; un n-grafo vaci En tiene orden n y ningn vrtice. En todo Kn todo par de vrtices son adyacentes, mientras que en En ningn par de vrtices son adyacentes. El conjunto de vrtices adyacentes a un vrtice x G, se denota por G(x). El grado de x es g(x)= G(x). El grado mnimo de los vrtices de un grafo se denota por d(G), mientras que el grado mximo se denota por D(G). Un vrtice de grado 0 se dice que es un vrtice aislado. Si d(G)=D(G)=k, es decir todo vrtice es de grado k entonces se dice que G es k-regular o regular de grado k. Un grafo es regular si es k-regular para algn k. Dado que V(G)={x 1 ,x 2 x n }, como todo arco tiene dos vrtices extremos, la suma de los grados es exactamente dos veces el nmero de vrtices:n

i=1

g(x i)=2e(G)

Esta observacin se llama tambin el lema de los apretones de manos, pues expresa que en una fiesta el nmero total de manos apretadas es par. Esto tambin establece que el nmero de vrtices de grado impar es par. Un camino W en un grafo G es una secuencia de los vrtices de G, (x 0 ,x 1 ,,x l) tal que {x i,x i+1} A(G) para 0 i2 tambin se denomina un ciclo, y puede denotarse por x 1 x 2 x l.

http://structio.sourceforge.net/guias/arbgraf/arbgraf.html[03/08/2011 12:41:31 a.m.]

rboles y grafos

Con Cl denotamos un ciclo de longitud l. Llamamos a C3 un tringulo, a C4 un cuadriltero, a C5 un pentgono, etc. Dados vrtices x, y su distancia d(x,y) es la longitud mnima de un camino de x a y. Un grafo es conexo si para todo par x, y de vrtices diferentes hay un camino de x a y. Note que un grafo conexo de orden al menos 2 no puede tener vrtices aislados. Con la definicin que empleamos un grafo no contiene lazos, es decir un arco que una vrtice consigo mismo; ni contiene arcos mltiples es decir que varios arcos unan los mismos dos vrtices. En un multigrafo se permiten lazos, arcos mltiples y lazos mltiples. Si los arcos son parejas ordenadas de vrtices entonces tenemos la nocin de grafo dirigido o multigrafo dirigido. Un pareja ordenada (a,b) se llama un arco dirigido de a hacia b, o decimos que el arco comienza en a y termina en b. En un grafo dirigido dado un vrtice x, llamamos grado de entrada de x ge(x) a la cantidad de arcos dirigidos que comienzan en x, mientras que el grado de salida de x gs(x) es la cantidad de arcos dirigidos que terminan en x. En un grafo dirigido una secuencia de vrtices (x 0 ,x 1 ,,x l) es un camino si existen arcos dirigidos (x i,x i+1) para 0 i string) -> 'a arbin que permite generar un rbol binario en formato .dot .

2.1.3 Lecturas recomendadasDesde el punto de vista de programacin funcional, puede verse el uso de rboles de bsqueda en [5], desde el punto de vista de programacin imperativa en [11]. Puede consultase ms sobre Graphviz en [2].

2.1.4 Ejercicios para afianzar teora


rboles y grafos

1. Usando el tipo presentado al comienzo de esta gua puede escribirse el rbol:(ABcons(ABcons(ABvacio,3,ABvacio),2, ABcons(ABcons(ABvacio,3,ABvacio),5,ABvacio)))

Dibuje una representacin grfica de este rbol, escriba las listas que resultan de recorrerlo en preorden, en inorden y en postorden. 2. Algunos lenguajes de programacin facilitan la creacin de estructuras polimrficas (en algunos contexto llamadas paramtricas o genricas). Por ejemplo un TAD rbol Binario Ordenado en Ocaml podra basarse en el tipo presentado al comienzo de esta gua. Que podra despus emplearse con enteros, cadenas o cualquier otro tipo. Dado que Ocaml es un lenguaje con un recolector de basura, el programador en casos sencillos no debe preocuparse por liberar memoria, detalle que puede ser difcil en lenguajes sin recolector de basura (y por tanto ms eficientes en tiempo de ejecucin) como C o C++. Como podra implementar un rbol polimrfico en C? Cmo puede implementar una funcin para liberar memoria de una estructura como la que plantee? 3. Hay diversas formas de implementar eliminacin en un rbol binario ordenado, explique (o implemente) por lo menos dos algoritmos para esto. 4. Indique los rboles resultantes tras balancear los casos presentados en la figura (2.3). 5. Escriba en formato .dot el rbol 2.2 y visualicelo con dotty .

2.1.5 Ejercicios de programacin

1. Implemente un TAD que representa un conjunto de enteros, empleando una lista. Las operaciones mnimas que debe tener este TAD son:ce_vacio: -> conjent constructora que retorna un conjunto vacio ce_ad: conjent -> int -> conjent constructora que agrega un entero a un conjunto. ce_miembro: conjent -> int -> bool selectora que decide si un entero pertenece o no

a un conjunto. de enteros

conjunto.ce_esVacio: conjent -> bool selectora que decide si un conjunto es vaci. ce_cardinalidad: conjent -> int selectora que retorna la cantidad de elementos en el ce_inv: conjent -> bool que decide si la estructura de datos que recibe es un conjunto

(por ejemplo verificando que no haya elementos repetidos). ce_elim: conjent -> int -> conjent que elimina un elemento de un conjunto. Fije algunos casos de pruebas de diversa longitud (e.g 0, 10, 100, 10000) y mida el tiempo que tarda la funcin ce_miembro al buscar un elemento que no est en el conjunto (Ayuda: Para medir el tiempo que toma la ejecucin de un programa --digamos prog -- puede emplear desde la lnea de comandos: time prog . Con este mtodo diferenciar hasta milsimas de segundo). Cual es la complejidad de la funcin de bsqueda? 2. Implemente el TAD del ejercicio anterior pero empleando una rbol binario ordenado (Ayuda: puede emplear la implementacin disponible con estas guas en http://structio.sourceforge.net/guias/arbgraf/). Empleando los mismos casos de prueba del punto anterior determine tiempo que tarda la funcin ce_miembro al buscar un elemento que no est en el conjunto. Cual es la complejidad de esa funcin con esta implementacin? 3. Implemente el TAD del ejercicio anterior, excepto la funcin de eliminar, pero empleando una rbol AVL . Realice pruebas anlogas a las de los puntos anteriores e indique la complejidad de la funcin ce_miembro .


rboles y grafos

2.2 Complejidad y MontculosIndicadores de logro: indicador: Calcula informalmente complejidad de funciones sencillas indicador: Emplea montculos y diferencia sus ventajas con respecto a otras estructuras estudiadas indicador: Implementa y usa un TAD conjunto de enteros acotados eficiente

2.2.1 Teora

Clculo de complejidad Note que nuestra mtrica de complejidad es independiente de multiplicacin por constantes, i.e para todo k 0, O(f(n))=O(k f(n)). As que O(1) es la mismo que O(5), mientras que O(n) es lo mismo que O(3n). La complejidad temporal de una funcin puede determinarse contando cuantas veces se realiza cierta operacin bsica escogida (por ejemplo comparaciones o sumas o productos), en el peor de los casos cuando el tamao de la entrada es n. Considere la funcin esta del TAD rbol binario ordenado:let rec esta e a= match a with | ABvacio -> false | ABcons(i,v,d) -> if v=e then true else if (e monticulo -> monticulo que mezcle dos montculos en un tercero y calcule la complejidad temporal y espacial de su solucin. 2. Escriba una funcin que reciba un montculo y retorne una lista con los elementos del montculo ordenados de menor a mayor. 3. Escriba una funcin que reciba una lista de elementos (ordenables) y que retorne un montculo con los mismos elementos. Calcule la complejidad de la funcin que escribi. Note que esta operacin junto con la funcin del punto anterior, permiten ordenar una lista. Si esta operacin se realiza de manera eficiente se tendr una implementacin de un algoritmo conocido como HeapSort. 4. Usando las ideas presentadas en esta gua, implemente el TAD conjunto de enteros en el rango 0 a 31 con un entero de 32 bits (mdulo Int32 en el caso de Ocaml). Implemente por lo menos las funciones sugeridas en los ejercicios de la gua sobre rboles de bsquedas.

2.3 rboles n-arios: rboles de sintaxis y rboles BIndicadores de logro: indicador: Emplea rboles de sintaxis indicador: Emplea rboles B

2.3.1 TeoraEn un rbol n-ario cada nodo puede tener un nmero variable de subrboles, puede modelarse en Ocaml con un tipo como:type 'a arbnario= ANvacio | ANcons of 'a * ('a arbnario) list;;

junto con un invariante para evitar representar con diversa sintaxis el mismo rbol: El constructor ANvacio no aparece en la lista de un constructor ANcons.

rboles de sintaxis abstracta Un rbol de sintaxis abstracta permite representar ciertos elementos de un lenguaje para despus analizarlo o transformarlo. Por ejemplo para un lenguaje simple que permita realizar operaciones aritmticas basta el siguiente rbol (note que algunos nodos son binarios, mientras que otros unarios y otros slo permiten representar hojas7 ):type exprar = Const of int | InvAd of exprar | Suma of exprar * exprar | Resta of exprar * exprar | Prod of exprar * exprar | Div of exprar * exprar;;

usndolo, la expresin 3*(-5+4) se representa como:Prod(Const(3), Suma(InvAd(Const(5)),Const(4)))

Es posible hacer una funcin que reciba una cadena con la sintaxis apropiada y genere un rbol de estos. A tal funcin se le llama un reconocedor 8 para el lenguaje. De esta manera ser fcil implementar funciones que empleen tales expresiones. El rbol de sintaxis para expresiones regulares del analizador lxico ocamllex es 9 :type regular_expression = Epsilon | Characters of char


rboles y grafos

| | | | |

Eof Sequence of regular_expression * regular_expression Alternative of regular_expression * regular_expression Repetition of regular_expression Bind of regular_expression * string

En este rbol se representan expresiones regulares como:"pa" que slo corresponder con la cadena "pa" y que se representa con Sequence(Characters('p'),Characters('a')). 'p' 'a'* 'l' que corresponder entre otras con las cadenas "pl", "pal", "paal" y que se representa con Sequence(Characters('p'),Sequence(Repetition(Characters('a')),Character('l'))) . ('p' 'a')* que corresponder entre otras con la cadena vaca, con "pa", "papa", "papapa". Se representa con Repetition(Sequence(Characters('p'), Characters('a'))). ('p' | 'a')* que corresponder entre otras con la cadena vaca, con "p", "pp", "aaaa", "ppaaap". Se representa con Repetition(Alternative(Characters('p'), Characters('a'))).

Un rbol de sintaxis para una porcin del formato de graphviz puede ser10:(** Identificacin de un nodo *) type idNodo=string;; (** Un arco puede conectar un nodo o un campo de un nodo registro *) type arco_ext=Id_nodo of idNodo | Id_field of idNodo * string;; (** Un atributo tiene una identificacin y un valor. *) type atributo=string*string ;; (** Un arco tiene un nodo fuente, un destino y una lista de atributos *) type arco=arco_ext*arco_ext*(atributo list);; (** Un nodo tiene una identificacin y una lista de atributos *) type nodo=string*(atributo list);; (** Un grafo tiene una identificacin, una lista de nodos y una lista de arcos *) type dot_graph=string*(nodo list*arco list);;

Incluso es posible proponer rboles de sintaxis para lenguajes naturales como el espaol o para porciones de este. En general estos rboles no cumplen invariante alguno, aunque de una aplicacin a otra pueden imponerse invariantes por ejemplo para mejorar eficiencia.

rboles B En diversas aplicaciones se requiere mantener en cada nodo del rbol una llave junto con los datos que se desean representar. De esta forma el ordenamiento de los nodos puede hacerse con las llaves. Esta es una situacin tpica en bases de datos, pues cada tabla debe tener una llave, que facilita ubicar registros completos. Por ejemplo el tipo rbol binario antes estudiado podra definirse y usarse as:type ('a,'b) arbindat = ABDvacio | ABDcons of (('a,'b) arbindat * ('a*'b) * ('a,'b) arbindat);; let ej=ABDcons(ABDvacio,(10,"Magdalena"),ABDvacio);;

Note que el rbol polimrfico tiene dos parmetros: 'a que ser el tipo de la llave y 'b que ser el tipo de los datos. En el ejemplo presentado las llaves son enteras, mientras que los datos mantenidos son cadenas. Adems de esto en una base de datos debe buscarse minimizar las transferencias de bloques de datos de disco a memoria y viceversa. En un rbol AVL el balanceo que debe hacerse despus de insertar o eliminar elementos puede requerir hacer varios intercambios en el rbol (i.e varias transferencias en disco en el caso de una B.D). Para disminuir la posibilidad de balancear puede mantenerse ms de un dato en cada nodo hasta un cierto mximo, as al insertar slo debe balancearse si se crea un nuevo nodo cuando no haya espacio para ms datos en otros nodos y al eliminarse slo debe balancearse cuando desaparezca un nodo despus de que todos los datos que tuviera hubieran


rboles y grafos

sido eliminados. Un rbol B es un rbol n-ario balanceado sin llaves repetidas, que en cada nodo mantiene el siguiente invariante: Tiene de 0 a m llaves (k i) en orden, siendo m un nmero no superior a una constante positiva M, i.e. k i0, Ai=A.Ai-1 . Unin A B={x | x A x B}. Clausura A* =i=0inf Ai Un reconocedor para un lenguaje es un programa que dada una cadena s decide si pertenece o no al lenguaje.

Expresiones regulares Una expresin regular denota un lenguaje 1 La expresin regular e denota el lenguaje {e}. La expresin regular a, donde a es un smbolo de un alfabeto, denota el lenguaje {a}. Si R y S son expresiones regulares que denotan los lenguajes LR y LS respectivamente: R|S denota LR LS .http://structio.sourceforge.net/guias/arbgraf/arbgraf.html[03/08/2011 12:41:31 a.m.]

rboles y grafos

RS denota LR.LS R* denota LR* En cuanto a sintaxis concreta, de estos operadores, * tiene precedencia mxima, mientras que | tendr precedencia mnima, pueden emplearse parntesis para cambiar la precedencia y como convencin los caracteres de escape \\, \*, \|, \( y \) denotarn los caracteres \, *, |, ( y ) respectivamente. En la seccin sobre rboles de sintaxis se introdujo un tipo que puede adaptarse (eliminando el constructor Eof ) para representar las expresiones regulares aqu presentadas.

Autmatas Finitos Un autmata finito es un grafo directo decorado2 . Se usa como reconocedor de lenguajes, los nodos representan posibles estados durante el reconocimiento, y los arcos representan posibles transiciones de un estado a otro. Hay un nodo inicial y un conjunto de nodos finales (cuando se comienza el reconocimiento de un nuevo texto, el autmata comienza en el estado inicial y la cadena pertenece al lenguaje si alcanza un estado final cuando la cadena se procesa por completo). Cada etiqueta tiene una letra que indica cuando puede ocurrir una transicin.

Figure 3.1: Ejemplo de autmata finito

En la figura 3.1, hay un arco del vrtice 1 al vrtice 2 con etiqueta a. El nodo inicial es 1 que se indica por el smbolo !, mientras que el nodo final es 2 que se indica por el smbolo #. Si durante un reconocimiento el estado es 1, ir al estado 2 slo si el siguiente carcter del texto reconocido es a. Hay dos clases de autmatas finitos: determinsticos (AFD) y no-determinsticos (AFN), las diferencias son: Un AFN permite etiquetas vacas mientras que en un AFD todos los arcos deben estar decorados con un carcter. Un AFN permite que varios arcos que partan de un nodo tengan la misma etiqueta. En un AFD todas las etiquetas de los arcos que parten de un nodo deben ser diferentes. Para efectos de implementacin es ms sencillo hacer un reconocedor con un AFD, pues los cambios de estado se determinan con una sola comparacin.

De expresiones regulares a autmatas finitos eficientes Es relativamente fcil generar un AFN que reconozca el lenguaje representado por una expresin regular, basta aplicar las transformaciones de la figura ??.


rboles y grafos

Figure 3.2: Transformaciones de expresiones regulares en autmatas finitos no determinsticos

Una caracterstica de esta transformacin es que da un AFN que tienen un slo estado final. En el primer caso, el de un smbolo, el estado inicial lo representamos con i mientras que el estado final con f. Note que a representa un smbolo cualquiera del alfabeto, mientras que R y S son expresiones regulares. Las elipses NR y NS representan el autmata finito que resulta de transformar R y S respectivamente, el primero tiene como estado inicial i 1 y como estado final f 1 , los anlogos para NS son i 2 y f 2 . Por ejemplo para transformar la expresin regular "(ab)|c*": pueden crearse subgrafos siguiendo las reglas descritas hasta obtener el grafo que corresponde a la expresin completa, como se presenta en la figura ??.


rboles y grafos

Figure 3.3: Ejemplo de transformacin de la expresin (ab)|c*

Por facilidad y eficiencia al implementar un reconocedor de lenguajes regulares puede resultar buena opcin transformar el AFN que se obtiene tras traducir la expresin regular en un AFD mnimo, labor que puede hacer en dos pasos: (1) transformando el AFN en un AFD y (2) minimizando el nmero de estados del AFD. Transformacin de un AFN en un AFD La idea es identificar muchos nodos de un AFN en un slo nodo de un AFD. Todos los vrtices de un AFN a los que pueda llegarse desde un nodo dado pasando slo por arcos con etiqueta e deben identificarse como un nico nodo en el AFD (la clausura vaca de un conjunto de nodos N consta justamente de todos los nodos a los que puede llegarse desde nodos de N pasando slo por arcos con etiqueta e). En el siguiente algoritmo D ser el AFD que se construye, cada vrtice de D ser un conjunto de nodos del AFN.I=clausura\_epsilon(nodo inicial del AFN) D=({I},{})


rboles y grafos

Si I contiene un nodo final marcarlo como vrtice final de D I no ha sido visitado mientras (haya vrtices no visitados en D) N=Tomar un vrtice (conjunto) no visitado de D marcar N como visitado para cada etiqueta posible l S=conjunto de nodos a los que se puede llegar desde nodos en N pasando por arcos con etiqueta l T=clausura_epsilon(S) si (T ya es vrtice de D) entonces agregar en D un arco de N a T con etiqueta l sino agregar T como vrtice no marcado a D si T contiene el vrtice final del NFA marcar T como final agregar un arco de N a T con etiqueta l fin-si fin-para fin-mientras

Minimizacin de la cantidad de estados de un DFA Dados todos los estados de un DFA, la idea es hacer una particin P de estos estados identificando en el mismo subconjunto todos los vrtices que tengan las mismas salidas (i.e todos ellos tienen arcos que parten a los mismo subconjuntos con las mismas etiquetas). Inicialmente divida los estados en dos grupos F y NF donde F contiene todos los estados finales y NF los estados no finales, P={F,NF}.mientras (se haya modificado P) para cada posible etiqueta c del DFA inicial para cada conjunto S de P escoja un elemento x de S del que salga un arco con etiqueta c S1={y en S | y va al mismo conjunto de P que x por una etiqueta c} S2=S-S1 eliminar S de P agregar S1 a P si S2 no es vaco agregar S2 a P fin-para fin-para fin-mientras

3.1.2 Lecturas recomendadasLa fuente de consulta fundamental ha sido [4], libro clsico y muy recomendado.

3.1.3 Ejercicios para afianzar teora

1. Sobre un alfabeto S={x,y,7,2}, se definen los lenguajes A={xx, xy, x72} y B={x i | i Nat} donde x 0 =e, x 1 =x, x 2 =xx, x 3 =xxx y as sucesivamente. A qu lenguaje corresponden: A.A, A3 , A A3 , A*, A B, B2 , (A B)*. 2. Qu lenguajes representan las siguientes expresiones regulares a m* x|y (%)\\\*

ab|c a|b*http://structio.sourceforge.net/guias/arbgraf/arbgraf.html[03/08/2011 12:41:31 a.m.]

rboles y grafos

a*|b ab* (ab)*c(d|e)

3. Escriba AFNs o AFDs que reconozcan cada uno de los lenguajes descritos por las expresiones regulares del punto anterior.

4.

Figure 3.4: AFD

Dado el AFD de la figura 3.4 indique cuales de las siguientes cadenas reconoce: casa cas faa fabdadasbl casb dasa 5. Transforme cada una de las siguientes expresiones regulares a un AFN siguiendo el algoritmo descrito en la gua, despus transforme el AFN resultante en un AFD siguiendo el algoritmo descrito en la gua. xy*z*u db*(c(d|e))* (ab)|(de)* x*x*x*

6. Minimice los estados de cada uno de los AFDs del ejercicio anterior, siguiendo el algoritmo descrito en la gua.

3.1.4 Ejercicios de programacin

1. Empleando el tipo


rboles y grafos

type expreg= Epsilon | Car of char | Secuencia of expreg * expreg | Alternativa of expreg * expreg | Repeticion of expreg ;;

(adaptado de uno introducido en la gua anterior) escriba la funcin reconoce_expreg: int -> int -> string -> expreg que recibe como tercer parmetro una cadena con una expresin regular (con la sintaxis concreta descrita en esta gua), como primer parmetro una posicin inicial dentro de la cadena y como segundo parmetro una posicin final dentro de la cadena. Retorna la expresin regular que puede reconocer entre las posiciones inicial y final (incluidas). 2. Implemente un tipo paramtrico ('a,'b) afd para representar AFDs con nodos tipo 'a y etiquetas tipo 'b, e implemente la funcin afd_reconocedor: string -> afd -> bool que retorne verdadero slo si el autmata reconoce la cadena que recibe. 3. Para representar autmatas finitos no determinsticos con un slo estado inicial y un slo estado final podra emplearse el tipo: type ('a,'b) afn='a list * ('a*'a*'b option) list * 'a option * 'aoption;;

La primera lista es de vrtices, la segunda de arcos etiquetados, el tercer elemento de la tupla es el vrtice inicial y el ltimo el vrtice final. La etiqueta e se representa con None. El NFA vacio sera ([],[],None,None), los dems NFAs deben tener nodo inicial y final diferentes a None (i.e Some x). Usando este tipo (o uno anlogo en un lenguaje diferente a Ocaml) y el tipo expreg del primer ejercicio de esta gua, implemente la funcin afn_de_expreg : int -> expreg -> ((int,char) afn, int) que traduce una expresin regular a un AFN con el algoritmo descrito en la gua. Los vrtices los numera con enteros comenzando con el entero que recibe como segundo parmetro. Retorna el AFN y el siguiente entero que no se uso para numerar vrtices. Opcional: Los AFN que resultan del algoritmo de traduccin descrito tienen una caracterstica que puede aprovecharse para hacer una estructura de datos ms eficiente. De todo vrtice salen a lo sumo dos arcos y cuando salen dos ambos tienen etiquetas e. Proponga una estructura de datos que aproveche esta caracterstica e indique que cambios deben hacerse a afn_de_expreg para que la use. 4. Empleando el tipo del ejercicio anterior, un tipo para AFDs ('a, 'b) afd, y un TAD conjunto de enteros conjent , implemente la funcin afd_de_afn: (int, char) afn -> (conjent, char) afd que transforme un AFN en un AFD con el algoritmo descrito en la gua. Opcional: La eficiencia de esta transformacin depende en buena medida del TAD conjunto de enteros que se emplee. Mejore la implementacin de conjunto de enteros como bits en enteros de 32 bits, para que emplee un vector de enteros en lugar de un slo entero, y verifique que funciona con la funcin de este ejercicio. 5. Escriba una funcin que renombre los estados de un AFD para que sean enteros: numest_afd: ('a, 'b) afd -> (int, 'b) afd . Cul es la complejidad de esta funcin? 6. Escriba una funcin que implemente el algoritmo de minimizacin de estados de un AFD descrito en la gua: minest_afd: (int, char) afd -> (conjent, char) afd .

1Los lenguajes que una expresin regular puede denotar se llaman lenguajes regulares.

2Un grafo es decorado si a cada arco se le asocia un valor. Es decir un grafo dirigido decorado con valores en un conjunto D, es una tupla G=(V,A,ea) donde V es conjunto de vrtices, A es conjunto de arcos (parejas ordenadas de vrtices) y ea:A D. Grficamente puede representarse agregando sobre cada arco el valorhttp://structio.sourceforge.net/guias/arbgraf/arbgraf.html[03/08/2011 12:41:31 a.m.]

rboles y grafos

asociado.

Bibliografa[1] B-tree algorithms. http://www.semaphorecorp.com/btp/algo.html, 2004. [2] Graphviz - open source graph drawing software. http://www.research.att.com/sw/tools/graphviz/, 2004. [3] Sqlite: An enbeddable sql database engine. http://www.sqlite.org/, 2004. [4] Alfred V. Aho and Jeffrey D. Ullman. Principles of Compiler Design. Addison Wesley, 1978. [5] Richard Bird. Introduccin a la Programacin Funcional con Haskell. Prentice Hall, 2000. [6] Bla Boolobs. Graph Theory: An Introductory Course. Springer Verlag, 1979. [7] Tom Moog. Pccts resources. http://www.polhode.com/pccts.html, 2004. [8] John Morris. Data structures and algorithms. http://ciips.ee.uwa.edu.au/ morris/Year2/PLDS210/ds_ToC.html, 2004. [9] Vladimir Tmara Patio. Restricted design spaces: Visualization and consistency tools. Technical Report 03/01, Sonderforschungsbereich 501, Teilprojekt B5, Universitt Kaiserslautern, "http://wwwmadlener.informatik.uni-kl.de/ag-madlener/publications/2001/sfb501-03-01.ps.gz", 2001. [10] Vladimir Tmara and Carlos Fidel Rodriguez. Programacin en ocaml. http://structio.sourceforge.net/guias/arbgraf, 2004. [11] Jorge Villalobos, Alejandro Quintero, and Mario Otero. Estructuras de Datos: Un Enfoque desde Tipos Abstractos. Mc-Graw Hill. Ediciones Uniandes, 1988.

IndexThis document was translated from LATEX by HEVEA.


Árboles y grafos

Documents