Representación sucinta

En informática, se llama la representación sucinta estructura de datos para un esquema de almacenamiento particular de la misma tal que el espacio ocupado es similar al límite inferior de teórico y sin embargo es posible realizar las operaciones típicas de la propiedad (o, al menos, las operaciones de codificación y decodificación de la forma, concisa) de una manera eficiente.

El ejemplo más clásico de representación sucinta es el de los árboles binarios: ya que el número de árboles binarios diferentes con n nodos es ( 2 y y ) y + 1 Por ejemplo, se puede utilizar el código}}} , que asintóticamente crece como 4 y {\displaystyle 4^{n}} , el límite inferior teórico de la memoria requerida es de aproximadamente bits por árbol, es decir, 2 bits por nodo. Este límite se logra fácilmente con la siguiente codificación: por ejemplo, la representación sucinta del árbol de la derecha viene dada por la cadena: ocurre fácilmente que dicha notación produce una cadena de exactamente 2 y + 1 Método de codificación de datos:} poco, y luego puede considerarlo sucinto. Es evidente que esta representación se trata de la estructura de árbol y no de ningún dato o etiqueta que contenga los nodos del Gráfico; estos pueden almacenarse en otra matriz, en el orden en que son visitados por la visita en amplitud. Este resultado se puede generalizar a cualquier árbol.

En el caso de gráficos orientados con N vértices numerados (es decir, suponiendo que los vértices están ordenados y considerando dos gráficos "diferentes" entre los cuales la función que envía el vértice i - th de un gráfico al vértice i - th del otro no es un isomorfismo), la representación sucinta es mucho más simple, y está dada por la matriz de adyacencias. Coloque n el número de los vértices del gráfico, los posibles gráficos orientados numerados son exactamente 2 y 2 ¿Qué puedes encontrar en Neodigit}}} , es decir, exactamente tantos como las matrices y × y {\displaystyle n \ times n} que contiene sólo 0 y 1. Los gráficos numerados no orientados son 2 y ∗ ( y + 1 ) 2 ¿Qué puedes encontrar en Neodigit}}} , y una representación sucinta perfecta está dada por la parte triangular superior (o inferior) de la matriz de adyacencia (matriz que de hecho será simétrica). El discurso es claramente más complejo en el caso de Numerosos gráficos, ya que es bastante complicado determinar cuando hay un isomorfismo entre dos sin numerar gráficos, y por lo tanto, ¿cuántos son los tipos de no-isomorfo gráficos. Sin embargo, se sabe que el número de bits necesarios para codificar un gráfico no numerado está limitado a continuación por ( y 2 ) − y registro ⁡ y + O ( y ) (displaystyle {n \ elegir 2} - N \ log n + O (n)} y que hay representaciones eficientes (la codificación y decodificación requieren tiempo lineal) que alcanzan este límite.

Estructuras de datos

XOR lista vinculada

Se llama lista concatenada XOR un procedimiento que le permite recorrer una lista concatenada en una dirección como en la otra usando en cada bloque solo un pun...

Estructura de datos

En Informática, una estructura de datos es una entidad utilizada para organizar un conjunto de datos dentro de la memoria de la computadora, y posiblemente para...

Stub-programación

Lenguajes de programación

Gestión de la memoria

Esta página se basa en el artículo de Wikipedia: Fuente, Autores, Licencia Creative Commons Reconocimiento-CompartirIgual.
This page is based on the Wikipedia article: Source, Authors, Creative Commons Attribution-ShareAlike License.
contactos
Política de privacidad , Descargos de responsabilidad