MatDiscreta Semana8

Vista previa del material en texto

TEMA: Teoría de arboles (Parte 2) 
Semana 8
FACULTAD DE INGENIERÍA INDUSTRIAL Y 
SISTEMAS
CODIGOS PREFIJOS
Definición.- Un conjunto P de sucesiones binarias (que representa un conjunto de 
símbolos) es un código prefijo si ninguna de las sucesiones de p es el prefijo de otra 
sucesión de P.
▪ Ejemplos
1.-Sea el conjunto 𝐸 = 000, 001, 011, 10, 11 es un código prefijo
2.- Sea el conjunto 𝐹 = 1, 00, 01, 000, 0001 no es un código prefijo
3.-Consideremos un subconjunto del alfabeto 𝑆 = 𝑎, 𝑒, 𝑛, 𝑟, 𝑡 y representemos los 
elementos de S mediante las siguientes sucesiones binarias.
𝑎: 01 𝑒: 0 𝑛: 101 𝑟: 10 𝑡: 1
Si transmitimos el mensaje “ata” se enviara la sucesión binaria 01101 pero también 
se puede transmitir los mensajes con esta sucesión 𝒆𝒕𝒏, 𝒂𝒕𝒆𝒕, 𝒂𝒏 en consecuencia no 
es código prefijo 
FIIS - UNI
CODIDGOS PREJIFOS
Si consideramos un segundo esquema de 
codificación 
𝑎: 111 𝑒: 0 𝑛: 1100 𝑟: 1101 𝑡: 10 , ahora si 
transmitimos el mensaje “ata” se enviara la 
sucesión binaria 11110111 donde no hay 
posibilidades de confusión, en consecuencia es un
código prefijo
Además podemos usar el árbol binario completo 
etiquetado para decodificar la sucesión 11110111 
de la siguiente forma.
FIIS - UNI
CODIFICACIÓN DE HUFFMAN
▪ Es una técnica para comprensión de datos. Este algoritmo le asigna secuencias binarias (códigos) a 
los símbolos del alfabeto de manera de utilizar la menor cantidad de bits posibles 
▪ La idea del algoritmo del algoritmo de Huffman es que los datos a ser comprimidos, contienen 
símbolos que aparecen con mayor frecuencia y otros muy poco, asignándoles el código mas corto a 
los que más aparecen.
▪ A continuación los pasos a seguir 
▪ Paso 1.
▪ Se coloca los caracteres en orden creciente de acuerdo a la frecuencia de repetición 
▪ Paso 2.
▪ Fusionar los nodos de menor frecuencia hasta obtener un solo árbol manteniendo el ordenamiento 
creciente 
▪ Paso 3.
▪ En el árbol obtenido en el paso 2 las hojas representan los símbolos o caracteres, los caminos o 
trayectorias de la raíz a las hojas se codifica con 0 a la izquierda y con 1 a la derecha
▪ Paso 4.
▪ Finalmente de árbol se obtiene el código prefijo 
FIIS - UNI
CODIFICACIÓN DE HUFFMAN
▪ Ejemplo 
▪ Supongamos que en un cierto archivo con 100 000 caracteres, donde aparecen 6 
caracteres diferentes y la frecuencia de aparición de cada uno de ellos es la 
siguiente 
FIIS - UNI
caracter a b c d e f
Frecuencia 
( en miles )
45 13 12 16 9 5
CODIFICACIÓN HUFFMAN
Solución 
Fase 1. : Caracteres colocados en orden creciente de frecuencia.
Fase 2. y posteriores : Fusionar hasta obtener un sólo árbol 
Manteniendo la ordenación creciente.
FIIS - UNI
f:5 e:9 c:12 b:13 d:16 a:45
CODIFICACIÓN HUFFMAN FIIS - UNI
CODIGO DE HUFFMAN FIIS - UNI
FIIS - UNI
CODIGO HUFFMAN
▪ Dado finalmente el árbol binario 
ponderado podemos codificar y 
decodificar 
▪ Codificación: Basta con concatenar el 
código de cada uno de los caracteres.
▪ Ejemplo : aabacd  001010100111
001010100111
▪ Descodificación: ningún código es 
prefijo de otro código 
▪ Ejemplo :101011101111011100  badadcf
FIIS - UNI
ARBOL GENERADOR
Un árbol generador de un grafo G (también llamado árbol recubridor o árbol 
expandido), es un subgrafo de G que es árbol y contiene a todos los vértices de G
Un grafo G, un árbol T generador de G
FIIS - UNI
 
T F G 
ARBOL DE EXPANSIÓN MÍNIMA 
(RECUBRIDOR)
Dado un grafo 𝐺 = 𝑉, 𝐸 , no dirigido ponderado. Un árbol de expansión mínima es un 
árbol compuesto por todos los vértices y cuya suma de los pesos las aristas sea 
mínimo. El árbol generador mínimo de un grafo, no necesariamente es único. 
Ejemplo 1
▪ Para el grafo G de la siguiente figura existen dos árboles generadores mínimos T1 y 
T2
Un grafo ponderado G y dos árboles generadores mínimos de G (T1 y T2)
FIIS - UNI
 
T2 T1 G 
2 
 3 5 
1 
2 
 3 5 
1 
4 
2 
6 
 3 3 5 
1 
Ejemplo 2
Una compañía de teléfono móviles da servicio a ciertas áreas geográficas, considerando la 
distancia en kilómetros. Dichas áreas se representan por el siguiente grafo.
Determinar cuál sería la ruta del mensaje óptimo
FIIS - UNI
El árbol de expansión mínima que me indica la ruta del mensaje óptimo se muestra en 
la siguiente figura.
Los algoritmos que permiten hallar un árbol de expansión mínima son el algoritmo de 
PRIM y el algoritmo de KRUSKAL.
FIIS - UNI
ALGORITMO DE PRIM
▪ El algoritmo de Prim es un algoritmo perteneciente a la teoría de los grafos para 
encontrar un árbol recubridor mínimo en un grafo conexo, no dirigido y cuyas 
aristas están etiquetadas. 
▪ En otras palabras, el algoritmo encuentra un subconjunto de aristas que forman un 
árbol con todos los vértices, donde el peso total de todas las aristas en el árbol es el 
mínimo posible. Si el grafo no es conexo, entonces el algoritmo encontrará el árbol 
recubridor mínimo para uno de los componentes conexos que forman dicho grafo 
no conexo.
▪ El algoritmo fue diseñado en 1930 por el matemático Vojtech Jarnik y luego de 
manera independiente por el científico computacional Robert C. Prim en 1957 y 
redescubierto por Dijkstra en 1959. Por esta razón, el algoritmo es también conocido 
como algoritmo DJP o algoritmo de Jarnik.
▪ El algoritmo incrementa continuamente el tamaño de un árbol, comenzando por un 
vértice inicial al que se le van agregando sucesivamente vértices cuya distancia a 
los anteriores es mínima. Esto significa que en cada paso, las aristas a considerar son 
aquellas que inciden en vértices que ya pertenecen al árbol. El árbol recubridor
mínimo está completamente construido cuando no quedan más vértices por 
agregar.
FIIS - UNI
ALGORITMO DE PRIM
▪ Sea un grafo 𝐺 = 𝑉, 𝐴 ponderado donde se va ir construyendo sucesivamente 
conjunto de vértices 𝑉0, 𝑉1, 𝑉2………… ⊆ 𝑉 y de aristas 𝐴0, 𝐴1, 𝐴2………… ⊆ 𝐴, 
siguiendo los siguientes pasos.
▪ Paso 1.- Se elige un vértice 𝑣 de G y formamos 𝑉0= {𝑣}, donde en este paso el 
conjunto de aristas 𝐴0 = 𝜙 .
▪ Paso 2.-Se examina todas las aristas que tienen a 𝑣 como uno de sus extremos y de 
entre ellas seleccionamos la que tenga un peso menor. Consideremos la arista 𝑎 y 
sea el vértice 𝑤 su otro extremo de la arista donde se forman los conjuntos 𝑉1 =
𝑣,𝑤 y 𝐴1 = 𝑎
▪ Paso 3.- Repetimos el paso 2 hasta construir los conjuntos 𝑉𝑖−1 con 𝑖-vertives y 𝐴𝑖−1
con 𝑖 − 1 aristas 
▪ Paso 4.-Finalmente si en el paso 𝑡 no se puede encontrar una arista para continuar 
el procedimiento el algoritmo acaba y la salida es el grafo 𝐺𝑡 = 𝑉𝑡−1, 𝐴𝑡−1 .
FIIS - UNI
EJEMPLO 1
▪ La siguiente figura muestra cómo se construye, paso a paso, un árbol generador 
mínimo aplicando el algoritmo.
Construcción de un árbol generador mínimo (algoritmo de Prim)
FIIS - UNI
EJEMPLO 2
▪ Consideremos que el grafo que se muestra en la 
figura representa un pequeño distrito, que no 
cuenta con agua potable donde los vértices 
𝐴, 𝐵, 𝐶, 𝐷, 𝐸, 𝐹 representas las viviendas y las aristas 
representan la separación entre las viviendas 
medida en kilómetros .
▪ Determine la ruta que tenga el mínimo costo de 
habilitación de agua potable para el distrito
FIIS - UNI