El tipo abstracto de datos de las colas de prioridad

1. El tipo abstracto de datos de las colas de prioridad

Una cola de prioridad es una cola en la que cada elemento tiene asociada una prioridad. La operación de extracción siempre elige el elemento de menor prioridad.

Las operaciones que definen a tipo abstracto de datos (TAD) de las colas de prioridad (cuyos elementos son del tipo a) son las siguientes:

tales que

  • vacia es la cola de prioridad vacía.
  • (inserta x c) añade el elemento x a la cola de prioridad c.
  • (primero c) es el primer elemento de la cola de prioridad c.
  • (resto c) es el resto de la cola de prioridad c.
  • (esVacia c) se verifica si la cola de prioridad c es vacía.

Las operaciones tienen que verificar las siguientes propiedades:

  • inserta x (inserta y c) == inserta y (inserta x c)
  • primero (inserta x vacia) == x
  • Si x <= y, entonces primero (inserta y (inserta x c)) == primero (inserta x c)
  • resto (inserta x vacia) == vacia
  • Si x <= y, entonces resto (inserta y (inserta x c)) == inserta y (resto (inserta x c))
  • esVacia vacia
  • not (esVacia (inserta x c))

2. Las colas de prioridad en Haskell

2.1. El tipo abstracto de datos de las colas de prioridad en Haskell

El TAD de las colas de prioridadd se encuentra en el módulo ColaDePrioridad.hs cuyo contenido es el siguiente:

Para usar el TAD hay que usar una implementación concreta. En principio,
solo considearemos una que usa las listas.

2.2. Implementación de las colas de prioridad mediante listas

La implementación se encuentra en el módulo ColaDePrioridadConListas.hs cuyo contenido es el siguiente:

3. Las colas de prioridad en Python

3.1. El tipo abstracto de las colas de prioridad en Python

La implementación se encuentra en el módulo ColaDePrioridad.py cuyo contenido es el siguiente:

Para usar el TAD hay que usar una implementación concreta. En principio, consideraremos solo una que usa las listas.

3.2. Implementación de las colas de prioridad mediante listas

La implementación se encuentra en el módulo ColaDePrioridadConListas.py en el que se define la clase CPrioridad con los siguientes métodos:

  • inserta(x) añade x a la cola.
  • primero() es el primero de la cola.
  • resto() elimina el primero de la cola.
  • esVacia() se verifica si la cola es vacía.

Por ejemplo,

Además se definen las correspondientes funciones. Por ejemplo,

Finalmente, se define un generador aleatorio de colas de prioridad y se comprueba que las colas de prioridad cumplen las propiedades de su especificación.

El problema de la mochila (mediante espacio de estados)

Se tiene una mochila de capacidad de peso p y una lista de n para colocar en la mochila. Cada objeto i tiene un peso w(i) y un valor v(i). Considerando la posibilidad de colocar el mismo objeto varias veces en la mochila, el problema consiste en determinar la forma de colocar los objetos en la mochila sin sobrepasar la capacidad de la mochila colocando el máximo valor posible.

Para solucionar el problema se definen los siguientes tipos:

  • Una solución del problema de la mochila es una lista de objetos.

  • Los objetos son pares formado por un peso y un valor

  • Los pesos son número enteros

  • Los valores son números reales.

  • Los estados del problema de la mochila son 5-tupla de la (v,p,l,o,s) donde v es el valor de los objetos colocados, p es el peso de los objetos colocados, l es el límite de la capacidad de la mochila, o es la lista de los objetos colocados (ordenados de forma creciente según sus pesos) y s es la solución parcial.

Usando el procedimiento de búsqueda en profundidad, definir la función

tal que mochila os l es la solución del problema de la mochila para la lista de objetos os y el límite de capacidad l. Por ejemplo,

Soluciones

A continuación se muestran las soluciones en Haskell y las soluciones en Python.


Soluciones en Haskell


Soluciones en Python

El problema de las n reinas (mediante búsqueda por anchura en espacios de estados)

El problema de las n reinas consiste en colocar n reinas en un tablero cuadrado de dimensiones n por n de forma que no se encuentren más de una en la misma línea: horizontal, vertical o diagonal.

Las posiciones de las reinas en el tablero se representan por su columna y su fila.

Una solución del problema de las n reinas es una lista de posiciones.

Usando el procedimiento de búsqueda en anchura, definir las funciones

tales que

  • solucionesNR n es la lista de las soluciones del problema de las n reinas, por búsqueda de espacio de estados en anchura. Por ejemplo,

  • primeraSolucionNR n es la primera solución del problema de las n reinas, por búsqueda en espacio de estados por anchura. Por ejemplo,

  • nSolucionesNR n es el número de soluciones del problema de las n reinas, por búsqueda en espacio de estados. Por ejemplo,

Soluciones

A continuación se muestran las soluciones en Haskell y las soluciones en Python.


Soluciones en Haskell


Soluciones en Python

Búsqueda por anchura en espacios de estados

Las características de los problemas de espacios de estados son:

  • un conjunto de las posibles situaciones o nodos que constituye el espacio de estados (estos son las potenciales soluciones que se necesitan explorar),
  • un conjunto de movimientos de un nodo a otros nodos, llamados los sucesores del nodo,
  • un nodo inicial y
  • un nodo objetivo que es la solución.

Definir la función

tal que buscaAnchura s o e es la lista de soluciones del problema de espacio de estado definido por la función sucesores s, el objetivo o y estado inicial e obtenidas mediante búsqueda en anchura.

Soluciones

A continuación se muestran las soluciones en Haskell y las soluciones en Python.


Soluciones en Haskell


Soluciones en Python

El problema de las n reinas (mediante búsqueda por profundidad en espacios de estados)

El problema de las n reinas consiste en colocar n reinas en un tablero cuadrado de dimensiones n por n de forma que no se encuentren más de una en la misma línea: horizontal, vertical o diagonal.

Las posiciones de las reinas en el tablero se representan por su columna y su fila.

Una solución del problema de las n reinas es una lista de posiciones.

Usando el procedimiento de búsqueda en profundidad, definir las funciones

tales que

  • solucionesNR n es la lista de las soluciones del problema de las n reinas, por búsqueda de espacio de estados en profundidad. Por ejemplo,

  • primeraSolucionNR n es la primera solución del problema de las n reinas, por búsqueda en espacio de estados por profundidad. Por ejemplo,

  • nSolucionesNR n es el número de soluciones del problema de las n reinas, por búsqueda en espacio de estados. Por ejemplo,

Soluciones

A continuación se muestran las soluciones en Haskell y las soluciones en Python.


Soluciones en Haskell


Soluciones en Python

Búsqueda en espacios de estados por profundidad

Las características de los problemas de espacios de estados son:

  • un conjunto de las posibles situaciones o nodos que constituye el espacio de estados (estos son las potenciales soluciones que se necesitan explorar),
  • un conjunto de movimientos de un nodo a otros nodos, llamados los sucesores del nodo,
  • un nodo inicial y
  • un nodo objetivo que es la solución.

Definir la función

tal que buscaProfundidad s o e es la lista de soluciones del problema de espacio de estado definido por la función sucesores s, el objetivo o y estado inicial e obtenidas mediante búsqueda en profundidad.

Soluciones

A continuación se muestran las soluciones en Haskell y las soluciones en Python.


Soluciones en Haskell


Soluciones en Python

Rompecabeza del triominó mediante divide y vencerás

Un poliominó es una figura geométrica plana formada conectando dos o más cuadrados por alguno de sus lados. Los cuadrados se conectan lado con lado, pero no se pueden conectar ni por sus vértices, ni juntando solo parte de un lado de un cuadrado con parte de un lado de otro. Si unimos dos cuadrados se obtiene un dominó, si se juntan tres cuadrados se construye un triominó.

Sólo existen dos triominós, el I-triomino (por tener forma de I) y el L-triominó (por su forma de L) como se observa en las siguientes figuras

El rompecabeza del triominó consiste en cubrir un tablero cuadrado con 2^n filas y 2^n columnas, en el que se ha eliminado una casilla, con L-triominós de formas que cubran todas las casillas excepto la eliminada y los triominós no se solapen.

La casilla eliminada se representará con -1 y los L-triominós sucesiones de tres números consecutivos en forma de L. Con esta representación una solución del rompecabeza del triominó con 4 filas y la fila eliminada en la posición (4,4) es

Definir la función

tal que (triomino n p) es la solución, mediante divide y vencerás, del rompecabeza del triominó en un cuadrado nxn en el que se ha eliminado la casilla de la posición p. Por ejemplo,

Soluciones

A continuación se muestran las soluciones en Haskell y las soluciones en Python.


Soluciones en Haskell


Soluciones en Python

Algoritmo divide y vencerás

La técnica divide y vencerás consta de los siguientes pasos:

  • Dividir el problema en subproblemas menores.
  • Resolver por separado cada uno de los subproblemas:
    • si los subproblemas son complejos, usar la misma técnica recursivamente;
    • si son simples, resolverlos directamente.
  • Combinar todas las soluciones de los subproblemas en una solución simple.

Definir la función

tal que divideVenceras ind resuelve divide combina pbInicial resuelve el problema pbInicial mediante la técnica de divide y vencerás, donde

  • ind pb se verifica si el problema pb es indivisible
  • resuelve pb es la solución del problema indivisible pb
  • divide pb es la lista de subproblemas de pb
  • combina pb ss es la combinación de las soluciones ss de los subproblemas del problema pb.
  • pbInicial es el problema inicial

Usando la función DivideVenceras, definir las funciones

tales que

  • ordenaPorMezcla xs es la lista obtenida ordenando xs por el procedimiento de ordenación por mezcla. Por ejemplo,

  • ordenaRapida xs es la lista obtenida ordenando xs por el procedimiento de ordenación rápida. Por ejemplo,

Soluciones

A continuación se muestran las soluciones en Haskell y las soluciones en Python.


Soluciones en Haskell


Soluciones en Python

TAD de los grafos: Algoritmo de Prim

El algoritmo de Prim calcula un árbol recubridor mínimo en un grafo conexo y ponderado. Es decir, busca un subconjunto de aristas que, formando un árbol, incluyen todos los vértices y donde el valor de la suma de todas las aristas del árbol es el mínimo.

El algoritmo de Prim funciona de la siguiente manera:

  • Inicializar un árbol con un único vértice, elegido arbitrariamente, del grafo.
  • Aumentar el árbol por un lado. Llamamos lado a la unión entre dos vértices: de las posibles uniones que pueden conectar el árbol a los vértices que no están aún en el árbol, encontrar el lado de menor distancia y unirlo al árbol.
  • Repetir el paso 2 (hasta que todos los vértices pertenezcan al árbol)

Usando el tipo abstracto de datos de los grafos, definir la función,

tal que prim g es el árbol de expansión mínimo del grafo g calculado mediante el algoritmo de Prim. Por ejemplo, si g1, g2, g3 y g4 son los grafos definidos por

entonces

Soluciones

A continuación se muestran las soluciones en Haskell y las soluciones en Python.


Soluciones en Haskell


Soluciones en Python

TAD de los grafos: Algoritmo de Kruskal

El algoritmo de Kruskal calcula un árbol recubridor mínimo en un grafo conexo y ponderado. Es decir, busca un subconjunto de aristas que, formando un árbol, incluyen todos los vértices y donde el valor de la suma de todas las aristas del árbol es el mínimo.

El algoritmo de Kruskal funciona de la siguiente manera:

  • se crea un bosque B (un conjunto de árboles), donde cada vértice del grafo es un árbol separado
  • se crea un conjunto C que contenga a todas las aristas del grafo
  • mientras C es no vacío,
    • eliminar una arista de peso mínimo de C
    • si esa arista conecta dos árboles diferentes se añade al bosque, combinando los dos árboles en un solo árbol
    • en caso contrario, se desecha la arista

Al acabar el algoritmo, el bosque tiene un solo componente, el cual forma un árbol de expansión mínimo del grafo.

Usando el tipo abstracto de datos de los grafos, definir la función,

tal que kruskal g es el árbol de expansión mínimo del grafo g calculado mediante el algoritmo de Kruskal. Por ejemplo, si g1, g2, g3 y g4 son los grafos definidos por

entonces

Soluciones

A continuación se muestran las soluciones en Haskell y las soluciones en Python.


Soluciones en Haskell


Soluciones en Python

TAD de los grafos: Nodos conectados en un grafo

Usando el tipo abstracto de datos de los grafos, definir la función,

tal que conectados g v1 v2 se verifica si los vértices v1 y v2 están conectados en el grafo g. Por ejemplo, si grafo1 es el grafo definido por

entonces,

Soluciones

A continuación se muestran las soluciones en Haskell y las soluciones en Python.


Soluciones en Haskell


Soluciones en Python

TAD de los grafos: Nodos aislados de un grafo

Dado un grafo dirigido G, diremos que un nodo está aislado si o bien de dicho nodo no sale ninguna arista o bien no llega al nodo ninguna arista. Por ejemplo, en el siguiente grafo

podemos ver que del nodo 1 salen 3 aristas pero no llega ninguna, por lo que lo consideramos aislado. Así mismo, a los nodos 2 y 4 llegan aristas pero no sale ninguna, por tanto también estarán aislados.

Usando el tipo abstracto de datos de los grafos, definir la función,

tal que aislados g es la lista de nodos aislados del grafo g. Por ejemplo,

Soluciones

A continuación se muestran las soluciones en Haskell y las soluciones en Python.


Soluciones en Haskell


Soluciones en Python

TAD de los grafos: Coloreado correcto de un mapa

Un mapa se puede representar mediante un grafo donde los vértices son las regiones del mapa y hay una arista entre dos vértices si las correspondientes regiones son vecinas. Por ejemplo, el mapa siguiente

se pueden representar por

Para colorear el mapa se dispone de 4 colores definidos por

Usando el tipo abstracto de datos de los grafos, definir la función,

tal que correcta ncs m se verifica si ncs es una coloración del mapa m tal que todos las regiones vecinas tienen colores distintos. Por ejemplo,

Soluciones

A continuación se muestran las soluciones en Haskell y las soluciones en Python.


Soluciones en Haskell


Soluciones en Python

TAD de los grafos: Grafos conexos

Un grafo no dirigido G se dice conexo, si para cualquier par de vértices u y v en G, existe al menos una trayectoria (una sucesión de vértices adyacentes) de u a v.

Usando el tipo abstracto de datos de los grafos, definir la función,

tal que conexo g se verifica si el grafo g es conexo. Por ejemplo,

Soluciones

A continuación se muestran las soluciones en Haskell y las soluciones en Python.


Soluciones en Haskell


Soluciones en Python

TAD de los grafos: Recorrido en anchura

Usando el tipo abstracto de datos de los grafos, definir la función,

tal que recorridoEnAnchura i g es el recorrido en anchura del grafo g desde el vértice i. Por ejemplo, en el grafo

definido por

entonces

Soluciones

A continuación se muestran las soluciones en Haskell y las soluciones en Python.


Soluciones en Haskell


Soluciones en Python

TAD de los grafos: Recorrido en profundidad

Usando el tipo abstracto de datos de los grafos, definir la función,

tal que recorridoEnProfundidad i g es el recorrido en profundidad del grafo g desde el vértice i. Por ejemplo, en el grafo

definido por

entonces

Soluciones

A continuación se muestran las soluciones en Haskell y las soluciones en Python.


Soluciones en Haskell


Soluciones en Python

TAD de los grafos: Anchura de un grafo

En un grafo, la anchura de un nodo es el máximo de los absolutos de la diferencia entre el valor del nodo y los de sus adyacentes; y la anchura del grafo es la máxima anchura de sus nodos. Por ejemplo, en el grafo

su anchura es 4 y el nodo de máxima anchura es el 5.

Usando el tipo abstracto de datos de los grafos, definir la función,

tal que (anchuraG g) es la anchura del grafo g. Por ejemplo,

Comprobar experimentalmente que la anchura del grafo ciclo de orden n es n-1.

Soluciones

A continuación se muestran las soluciones en Haskell y las soluciones en Python.


Soluciones en Haskell


Soluciones en Python

TAD de los grafos: Recorridos en un grafo completo

Definir la función

tal que recorridos xs es la lista de todos los posibles por el grafo cuyo conjunto de vértices es xs y cada vértice se encuentra conectado con todos los otros y los recorridos pasan por todos los vértices una vez y terminan en el vértice inicial. Por ejemplo,

Soluciones

A continuación se muestran las soluciones en Haskell y las soluciones en Python.


Soluciones en Haskell


Soluciones en Python

TAD de los grafos: Grafos k-regulares

Un grafo k-regular es un grafo con todos sus vértices son de grado k.

Usando el tipo abstracto de datos de los grafos, definir la función,

tal que (regularidad g) es la regularidad de g. Por ejemplo,

Comprobar que el grafo completo de orden n es (n-1)-regular (para n de 1 a 20) y el grafo ciclo de orden n es 2-regular (para n de 3 a 20).

Soluciones

A continuación se muestran las soluciones en Haskell y las soluciones en Python.


Soluciones en Haskell


Soluciones en Python

TAD de los grafos: Grafos regulares

Un grafo regular es un grafo en el que todos sus vértices tienen el mismo grado.

Usando el tipo abstracto de datos de los grafos, definir la función,

tal que (regular g) se verifica si el grafo g es regular. Por ejemplo,

Comprobar que los grafos completos son regulares.

Soluciones

A continuación se muestran las soluciones en Haskell y las soluciones en Python.


Soluciones en Haskell


Soluciones en Python

TAD de los grafos: Lema del apretón de manos

En la teoría de grafos, se conoce como «Lema del apretón de manos» la siguiente propiedad: la suma de los grados de los vértices de g es el doble del número de aristas de g.

Comprobar con QuickCheck que para cualquier grafo g, se verifica dicha propiedad.

Soluciones

A continuación se muestran las soluciones en Haskell y las soluciones en Python.


Soluciones en Haskell


Soluciones en Python

TAD de los grafos: Grado de un vértice

El grado de un vértice v de un grafo dirigido g, es el número aristas de g que contiene a v. Si g es no dirigido, el grado de un vértice v es el número de aristas incidentes en v, teniendo en cuenta que los lazos se cuentan dos veces.

Usando el tipo abstracto de datos de los grafos, definir las funciones,

tal que grado g v es el grado del vértice v en el grafo g. Por ejemplo,

Comprobar con QuickCheck que en todo grafo, el número de nodos de grado impar es par.

Soluciones

A continuación se muestran las soluciones en Haskell y las soluciones en Python.


Soluciones en Haskell


Soluciones en Python

TAD de los grafos: Generadores de grafos

Definir un generador de grafos para comprobar propiedades de grafos con QuickCheck y hacer el tipo de los Grafos un subtipo de Arbitrary.

Usando el generador, con QuickCheck que para cualquier grafo g, las sumas de los grados positivos y la de los grados negativos de los vértices de g son iguales.

Soluciones

A continuación se muestran las soluciones en Haskell y las soluciones en Python.


Soluciones en Haskell

La definición del generador es

La comprobación de la propiedad es


Soluciones en Python

La definición del generador es

La comprobación de la propiedad es

TAD de los grafos: Grado positivo y negativo de un vértice

El grado positivo de un vértice v de un grafo g es el número de vértices de g adyacentes con v y su grado negativo es el número de vértices de g incidentes con v.

Usando el tipo abstracto de datos de los grafos, definir las funciones,

tales que
+ gradoPos g v es el grado positivo del vértice v en el grafo g. Por ejemplo,

  • gradoNeg g v es el grado negativo del vértice v en el grafo g. Por ejemplo,

Soluciones

A continuación se muestran las soluciones en Haskell y las soluciones en Python.


Soluciones en Haskell


Soluciones en Python

TAD de los grafos: Número de aristas de un grafo

Usando el tipo abstracto de datos de los grafos, definir la función,

tal que nAristas g es el número de aristas del grafo g. Si g es no dirigido, las aristas de v1 a v2 y de v2 a v1 sólo se cuentan una vez. Por ejemplo,

Definir la función

tal que prop_nAristasCompleto n se verifica si el número de aristas del grafo completo de orden n es n*(n-1)/2 y, usando la función, comprobar que la propiedad se cumple para n de 1 a 20.

Soluciones

A continuación se muestran las soluciones en Haskell y las soluciones en Python.


Soluciones en Haskell


Soluciones en Python

TAD de los grafos: Lazos de un grafo

Usando el tipo abstracto de datos de los grafos, definir las funciones,

tales que

  • lazos g es el conjunto de los lazos (es decir, aristas cuyos extremos son iguales) del grafo g. Por ejemplo,

  • nLazos g es el número de lazos del grafo g. Por ejemplo,

Soluciones

A continuación se muestran las soluciones en Haskell y las soluciones en Python.


Soluciones en Haskell


Soluciones en Python

TAD de los grafos: Contiguos de un vértice

En un un grafo g, los contiguos de un vértice v es el conjuntos de vértices x de g tales que x es adyacente o incidente con v.

Usando el tipo abstracto de datos de los grafos, definir la función,

tal que contiguos g v es el conjunto de los vértices de g contiguos con el vértice v. Por ejemplo,

Soluciones

A continuación se muestran las soluciones en Haskell y las soluciones en Python.


Soluciones en Haskell


Soluciones en Python

TAD de los grafos: Incidentes de un vértice

En un un grafo g, los incidentes de un vértice v es el conjuntos de vértices x de g para los que hay un arco (o una arista) de x a v; es decir, que v es adyacente a x.

Usando el tipo abstracto de datos de los grafos, definir la función,

tal que incidentes g v es la lista de los vértices incidentes en el vértice v. Por ejemplo,

Soluciones

A continuación se muestran las soluciones en Haskell y las soluciones en Python.


Soluciones en Haskell


Soluciones en Python

TAD de los grafos: Número de vértices

Usando el tipo abstracto de datos de los grafos, definir la función,

tal que nVertices g es el número de vértices del grafo g. Por ejemplo,

Soluciones

A continuación se muestran las soluciones en Haskell y las soluciones en Python.


Soluciones en Haskell


Soluciones en Python

TAD de los grafos: Grafos ciclos

El ciclo de orden n, C(n), es un grafo no dirigido cuyo conjunto de vértices es {1,…,n} y las aristas son

Usando el tipo abstracto de datos de los grafos, definir la función,

tal que (grafoCiclo n) es el grafo ciclo de orden n. Por ejemplo,

Soluciones

A continuación se muestran las soluciones en Haskell y las soluciones en Python.


Soluciones en Haskell


Soluciones en Python