ıllı Internet y Tecnologías de la Información (2018)

internet, Hosting, dominios, seo, antivirus, banco de imágenes, páginas web, tiendas online

[Enciclopedia Online Gratuita] Diccionario de Internet y Tecnologías de la Información y la Comunicación (TIC):

ıllı Estructura de datos para conjuntos disjuntos wiki: info, historia y vídeos

videos internet

salud  Estructura de datos para conjuntos disjuntos 


En computación, una estructura de datos para conjuntos disjuntos, es una estructura de datos que sostiene un conjunto de elementos particionados en un número de conjuntos disjuntos(no se solapan los conjuntos).Un algoritmo Unión-Buscar es un algoritmo que efectúa 2 esenciales operaciones en esta estructura de datos:



  • Buscar: Determina a como subconjunto pertenece un factor. Esta operación puede emplearse para contrastar si 2 elementos están en exactamente el mismo conjunto.
  • Union: Une 2 subconjuntos en uno solo.

La otra operación esencial CrearConjunto es por norma general trivial, esta crea un conjunto con un factor dado. Con estas 3 operaciones, muchos inconvenientes prácticos de particionamiento pueden ser resueltos(ver la sección de Aplicaciones).


Con el fin de acotar estas operaciones más exactamente , es preciso representar los conjuntos de alguna forma. Una aproximación común es escoger un factor fijo de cada conjunto , llamado el representativo, para representar el conjunto como un todo. Entonces Buscar(x) regresa el factor representativo del conjunto al que x pertenece , y Unión toma como razonamiento 2 elementos representivos de 2 conjuntos respectivamente.


Un simple acercamiento para crear una estructura de datos para conjuntos disjuntos es crear una lista enlazada para cada conjunto. El factor en la cabeza de cada lista enlazada se elige como elemento representativo.


CrearConjunto crea una lista con un solo elemento. Unión concadena 2 listas , una operación en tiempo incesante. El inconveniente de esta implementación es que Buscar(x) requiere O(n) o bien orden lineal para recorrer de atrás cara adelante, desde el factor dado hasta la cabeza de la lista.


Esto puede ser eludido agregando a cada nodo de la lista enlazada un puntero a la cabeza de la lista; por consiguiente Buscar toma tiempo incesante. Mas ahora Unión ahora debe actualizar a cada elemento de la lista que es concatenada una referencia a la cabeza de la nueva lista combinada, requiriendo O(n) tiempo.


Cuando sabemos la longitud de cada lista, el tiempo requerido puede ser mejorado concadenando siempre y en todo momento la lista de menor longitud a la de mayor longitud. Utilizando esta heurística llamada weighted-union, una secuencia de m operaciones de CrearConjunto, Unión y Buscar sobre n elementos requiere O(m + nlog n) tiempo. Para operaciones asintóticamente más veloces otra estructura de datos es precisa.


Análisis de este acercamiento simple


Ahora vamos a explicar el tiempo O(nlog?(n)) de arriba. Pongamos que tenemos una compilación de listas, cada nodo de la lista contiene un objeto, el nombre de la lista a la que pertenece, y el número de elementos de esa lista. Asimismo aceptemos que la suma de la cantidad de los elementos de todas y cada una de las listas es n (por consiguiente existen n elementos). Quisiéramos poder entremezclar cualquiera 2 de estas listas, y actualizar sus nodos a fin de que prosigan teniendo el nombre de la lista a la que pertenecen. La regla para entremezclar las listas A y B es que, si A es mayor que B entonces se agregan los de B en A y se actualizan los elementos que pertenecen a B, y a la inversa.


Escoger un factor arbitrario de la lista L, afirmemos x. Quisiéramos contar en el peor de los casos cuántas veces el factor x va a precisar actualizar el nombre de la lista a la que pertenece. El factor x solo va a actualizar su nombre cuando la lista a la que pertenece es mezclada con una lista del mismo o bien mayor tamaño. Cada instante que pase esto , el tamaño de la lista de x cuando menos se dobla. Entonces por último, el interrogante es ¿Cuántas veces puede un número plegar su tamaño antes que llegue a n? (entonces la lista de x tiene tamaño n). La contestación precisa es log2?(n). Entonces para cualquier elemento en cualquier lista en la estructura descrita, va a ser preciso actualizar log2?(n) veces en el peor caso. Por consiguiente actualizar una lista de n elementos guardados así tomaría O(nlog?(n)) tiempo en el peor de los casos. Una operación de busca se puede efectuar en O(1) en esta estructura puesto que todos y cada uno de los nodos poseen el nombre de la lista a la que pertenecen.


Un razonamiento afín se sostienen para entremezclar los árboles de las estructuras de datos discutidas más abajo, de forma adicional ayuda a explicar el análisis de tiempo de ciertas operaciones sobre las estructuras de datos Heap Binomial y Montículo de Fibonacci.


Los Bosques de Conjuntos-Disjuntos son estructuras de datos donde cada conjunto está representado por un árbol , en el que cada nodo sostiene una referencia a su nodo padre (ver pila spaghetti). Estos fueron descritos primeros por Bernard A. Galler y Michael J. Fisher en mil novecientos sesenta y cuatro, tomando años para su preciso análisis.


En los Bosques de Conjuntos-Disjuntos, el representativo de cada conjunto es la raíz del árbol el que representa el conjunto. Buscar prosigue por los progenitores nodos hasta hallar la raíz del árbol. Unión combina 2 árboles en uno agregando la raíz de uno en la raíz del otro. Una forma de incorporar esto puede ser:

function CrearConjunto(x) x.padre := x
function Buscar(x) if x.padre == x return x elsereturn Buscar(x.padre)
function Unión(x,y) xRaíz := Buscar(x) yRaíz := Buscar(y) xRaíz.padre := yRaíz

En esta simple forma, este implementación no es mejor que la implementación basada en listas enlazadas, pues el árbol que se crea puede ser realmente desbalanceado; de todas y cada una formas , esto puede ser mejorado de 2 formas.


La primera forma, lleva por nombre unión por rank, consiste en siempre y en todo momento agregar el árbol más pequeño a la raíz del árbol más grande. Como la profundidad del árbol afecta el tiempo de ejecución del algoritmo, el árbol con menor profundidad es añadido a la raíz del árbol con mayor profundidad, el que aumenta su profundidad solo si sus profundidades son iguales. En el contexto de este algoritmo, el término rank se utiliza en lugar de profundidad por el hecho de que este deja de ser igual a la profundidad si se emplea la compresión de camino (descrita más abajo). Los árboles con un solo elemento tienen rank igual a cero, y cualquiera 2 árboles del mismo rank r son combinados, el rank resultante es r+1. Solo aplicando esta técnica conseguimos en el peor de los casos un tiempo de ejecución de O(log?n) para las operaciones CrearConjunto, Unión y Buscar. Pseudocódigo del CrearConjunto y Unión mejorado:

function CrearConjunto(x) x.padre := x x.rank := 0
function Unión(x, y) xRaíz := Buscar(x) yRaíz := Buscar(y) if xRaíz == yRaíz return //Ya que no están en exactamente el mismo conjunto, se unen. if xRaíz.rank < yRaíz.rank xRaíz.padre := yRaíz else if xRaíz.rank > yRaíz.rank yRaíz.padre := xRaíz else yRaíz.padre := xRaíz xRaíz.rank := xRaíz.rank + 1

La segunda mejora, llamada compresión de camino, es una forma de aplanar la estructura del árbol cuando se aplique Buscar. La idea es que cada nodo visitado en el camino cara la raíz puede ser añadido de forma directa a la raíz; todos comparten exactamente el mismo representativo. Para conseguir este efecto, mientras que Buscar recursivamente se mueve cara la raíz, este cambia la referencia del padre del nodo a la raíz que halle. El árbol resultante es más aplanado, acelerando operaciones futuras no solo en estos elementos sino más bien asimismo en aquellos que referencian a estos. Acá va el Buscar mejorado:

function Buscar(x) if x.padre != x x.padre:= Buscar(x.padre) return x.padre

Estas 2 técnicas se complementan una a otra; aplicadas juntas, el tiempo amortizado es solo O(a(n)), donde a(n) es la inversa de la funciónn=f(x)=A(x,x), y A es la función de Ackermann. Como a(n) es la inversa de esta función, a(n) es menor que cinco para todos y cada uno de los prácticamente recónditos valores de n. Por lo tanto el tiempo de ejecución amortizado es ciertamente una pequeña incesante.


  ELIGE TU TEMA DE INTERÉS: 


autoayuda.es   Internet y Tecnologias 

Está aquí: Inicio > [ INTERNET ] > ıllı Estructura de datos para conjuntos disjuntos wiki: info, historia y vídeos

Las cookies nos permiten ofrecer nuestros servicios. Al utilizar nuestros servicios, aceptas el uso que hacemos de las cookies. Ver políticas