Árboles

Tarea 5

Arreglos, tablas y listas

Tarea 4

Realicé una lista enlazada simple en Python, con la cual puedo agregar al inicio, al final, eliminar, y imprimir la lista. En el vídeo primero explico rapidamente lo que son arreglos, tablas y listas y después mi código.
El vídeo originalmente dura 7 minutos pero al convertirlo de ogv a avi algo paso y solo dura 4 minutos.. lo que noto es que todo sucede más rápido así que si no alcanzan a leer pues es poreso que explico pero pueden ir poniendo pause y así.

Vídeo:




Código:

#!/usr/bin/python
#listas simples enlazadas con python
class Nodo: # en clase nodo definio el dato..y el apuntador al siguiente nodo "" sig""
    def __init__(self, dato):
        self.dato = dato
        self.sig = None
        
    def  __str__(self):#esta funcion me sirve para poder meter cualquier dato a la lista
        return str(self.dato)
        
class ListaEnlazada:#esta clase me ayuda a manejar la lista enlazada identificando la cabeza y el ultimo elemenyo
    def __init__(self): 
        self.cabeza =  None
        self.cola = None
        
    def agregarFinal(self, dato):  # funcion agregar al final
        nodo_nuevo = Nodo(dato)
        if self.cabeza == None: # aqui si no hay cabezera el elemento se vuelve la cabezera
            self.cabeza = nodo_nuevo
            
        if self.cola != None: # si si hay entonces se va a la cola.sig y esta apuntara a nodo nuevo
            self.cola.sig = nodo_nuevo
                    
        self.cola = nodo_nuevo

    def agregarInicio(self, dato):#aqui agregamos al inicio
        nodo_nuevo = Nodo(dato)
        if self.cabeza == None: # si no habia cabeza este se vuelve la cabeza
            self.cabeza = nodo_nuevo
        
        if self.cola != None: #cuando si habia mas datos entonces el nuevo elemento apuntara ala cabeza
            nodo_nuevo.sig = self.cabeza 
            self.cabeza =  nodo_nuevo # y la cabeza es el nuevo elemento(nodo nuevo)

    def eliminar(self, d):#para eliminar
        nodo = self.cabeza
        anterior = nodo#usamos anterior como auxiliar
        if self.cabeza.dato == d:  #si el dato a eliminar esta en la cabezera se elimina la cabeza y el cabeza.sig se vuelve la cabeza
            self.cabeza = self.cabeza.sig
        else:#si no se busca en el resto
            while nodo != None: 
                if nodo.dato == d:
                    anterior.sig = nodo.sig
                anterior = nodo
                nodo = nodo.sig

                       
    def imprimir(self):#aqui la funcion imprimir me ayuda a imprimir mientras haya elementos en la lista
        nodo = self.cabeza
        while nodo != None: 
            print nodo.dato
            nodo=nodo.sig#aqui se recorre






lista = ListaEnlazada()#creo un objeto nuevo que llamo lista
lista.agregarFinal(1)
lista.agregarFinal(2)
lista.agregarFinal(3)
lista.agregarInicio(7)
lista.agregarFinal(4)
lista.agregarFinal(5)
lista.agregarFinal(6)
lista.agregarInicio(10)
lista.eliminar(10)
lista.eliminar(7)
lista.imprimir()

Ejecución:



Referencias:

Listas en Python
Listas enlazadas
Tablas de dispersión

lñlñl

Algoritmos recursivos

Tarea 3

Flood fill on Prezi

Aclaro que en la parte de Complejidad, llegué a esa conclusión por el pdf que leí más no me copie de la conclusión de nadie :D.
.

Fundamentos de la complejidad computacional

Tarea 2

Algoritmos de Huffman

La finalidad de este algoritmo es encontrar una manera de comprimir datos, la manera en que lo hace es dandole a cada símbolo un código, el código que se le da a cada símbolo depende de la frecuencia con que el símbolo aparece en los datos, es fácil de comprender, al símbolo que aparezca más veces en los datos tendrá un código de representación más corto que un símbolo que aparesca menos veces.

Para hacerlo se debe primero hacer una tabla que relacione al símbolo con su frecuencia(esto no corresponde al algoritmo de Huffman), para así empezar a hacer el árbol binario usando el algoritmo de Huffman.

Voy a hacer un ejemplo con la frase: "clase de algoritmos computacionales"

Letra Frecuencia

a ------>4
c ------>3
d ------>1
e ------>3
g ------>1
i ------>2
l ------>3
m------>2
n ------>1
o ------>4
p ------>1
r ------>1
s ------>3
t ------>2
u ------->1
" "------>3

Algoritmo

Ahora teniendo mi frencuencia de palabras en la frase puedo empezar a dibujar mi árbol binario, el método para hacerlo es:

Hacer un arbol para cada símbolo escribiendo el símbolo con su frecuencia

Juntar los arboles con menor frecuencia para formar un nuevo árbol(binario), las etiquetas de los nodos serán la suma de las frecuencias de los hijos

Se repite el proceso hasta tener un solo árbol binario

Y este es el árbol que diseñé para la frase "clase de algoritmos computacionales":

Y ahora si estamos listos para codificar los símbolos, este paso del algoritmo es muy sencillo se escriben números en cada rama de el árbol, 0 para el lado izquierdo y 1 para el lado derecho.

Y ahora se ve de esta manera:

Entonces ahora poder encontrar el código de cada símbolo debemos empezar desde la raiz hasta el símbolo, por ejemplo:

para la letra "a" el código 010,

para la letra m el código 0011,

y para la letra "u" el código 01100,

podemos ver que entre menos es la frecuencia de la letra el tamaño de la cadena de código que representa a la letra se vuelve mas larga. Esto es el funcionamiento de el algoritmo.

Definición formal

Entradas

Tenemos el conjunto A que representa a los símbolos que se codificarán A={a1, a2,...an}

También el conjunto F que representa la frecuencia de cada símbolo F={f1, f2....fn},

Salidas

C representara el conjunto de códigos que representan a cada símbolo entonces tenemos C(A, F)={c1, c2, ... cn}. Esto quiere decir que por ejemplo c1 es la cadena de código que me representa a a1, a1 es el símbolo de entrada.

Complejidad

Por ser un algoritmo iterativo tiene su complejidad O(nlogn).

Ya que se tiene un bucle interno con complejidad logn y luego se repite n veces, dónde n es el conjunto de símbolos.

Características del algoritmo

La manera en que se ecuentra la tabla de frecuencia de palabras no es asunto de este algoritmo.

El caso óptimo es cuando se tiene que la probabilidad de que salga un número es una potencia negativa de dos.

El peor caso es cuando se tiene 2^-1.

Esto tiene sentido porque cuando se tiene una letra que sale el 50%, se supone que entre todos las demas símbolos habran probabilidades demasiado bajas, entonces se tendrán para ellos cadenas muy largas, que es lo contrario a lo que se busca.

Otros algoritmos

Existe otro algoritmo "codificación aritmética" que tiene ventaja sobre la codificación de Huffman pero su ventaja no es tan grande como para cambiar la simplicidad de Huffman y el no pago de patentes por la complejidad de codificación aritmética además de que este método no es tan libre de usarse ya que esta patentado por IBM.

Aplicaciones

Este algoritmo sigue siendo muy utilizado debido a su simplicidad, velocidad y no problemas de patentes.

Ejemplos de su uso en compresión multimedia de jpeg y mp3.

Referencias

Codificación de Huffman

Algoritmo de Huffman

Algoritmos voraces

Fundamentos de la complejidad computacional

Tarea 2

Algoritmo de Huffman

La finalidad de este algoritmo es encontrar una manera de comprimir datos, la manera en que lo hace es dandole a cada símbolo un código, el código que se le da a cada símbolo depende de la frecuencia con que el símbolo aparece en los datos, es fácil de comprender, al símbolo que aparezca más veces en los datos tendrá un código de representación más corto que un símbolo que aparesca menos veces.

Para hacerlo se debe primero hacer una tabla que relacione al símbolo con su frecuencia(esto no corresponde al algoritmo de Huffman), para así empezar a hacer el árbol binario usando el algoritmo de Huffman.

Voy a hacer un ejemplo con la frase: "clase de algoritmos computacionales"

Letra	Frecuencia
a	4
c	3
d	1
e	3
g	1
i	2
l	3
m	2
n	1
o	4
p	1
r	1
s	3
t	2
u	1
" "	3

Algoritmo

Ahora teniendo mi frencuencia de palabras en la frase puedo empezar a dibujar mi árbol binario, el método para hacerlo es:

1. Hacer un arbol para cada símbolo escribiendo el símbolo con su frecuencia
2. Juntar los arboles con menor frecuencia para formar un nuevo árbol(binario), las etiquetas de los nodos serán la suma de las frecuencias de los hijos
3. Se repite el proceso hasta tener un solo árbol binario

Y este es el árbol que diseñé para la frase "clase de algoritmos computacionales"

Y ahora si estamos listos para codificar los símbolos, este paso del algoritmo es muy sencillo se escriben números en cada rama de el árbol, 0 para el lado izquierdo y 1 para el lado derecho.

Y ahora se ve de esta manera:

Entonces ahora poder encontrar el código de cada símbolo debemos empezar desde la raiz hasta el símbolo, por ejemplo:

para la letra "a" el código 010,

para la letra m el código 0011,

y para la letra "u" el código 01100,

podemos ver que entre menos es la frecuencia de la letra el tamaño de la cadena de código que representa a la letra se vuelve mas larga. Esto es el funcionamiento de el algoritmo.

Definición formal

Entradas

Tenemos el conjunto A que representa a los símbolos que se codificarán A={a1, a2,...an}

También el conjunto F que representa la frecuencia de cada símbolo F={f1, f2....fn},

Salidas

C representara el conjunto de códigos que representan a cada símbolo entonces tenemos C(A, F)={c1, c2, ... cn}. Esto quiere decir que por ejemplo c1 es la cadena de código que me representa a a1, a1 es el símbolo de entrada.

Complejidad

Por ser un algoritmo iterativo tiene su complejidad O(nlogn).

Ya que se tiene un bucle interno con complejidad logn y luego se repite n veces, dónde n es el conjunto de símbolos.

Características del algoritmo

La manera en que se ecuentra la tabla de frecuencia de palabras no es asunto de este algoritmo.

El caso óptimo es cuando se tiene que la probabilidad de que salga un número es una potencia negativa de dos.

El peor caso es cuando se tiene 2^-1.

Esto tiene sentido porque cuando se tiene una letra que sale el 50%, se supone que entre todos las demas símbolos habran probabilidades demasiado bajas, entonces se tendrán para ellos cadenas muy largas, que es lo contrario a lo que se busca.

Otros algoritmos

Existe otro algoritmo "codificación aritmética" que tiene ventaja sobre la codificación de Huffman pero su ventaja no es tan grande como para cambiar la simplicidad de Huffman y el no pago de patentes por la complejidad de codificación aritmética además de que este método no es tan libre de usarse ya que esta patentado por IBM.

Aplicaciones

Este algoritmo sigue siendo muy utilizado debido a su simplicidad, velocidad y no problemas de patentes.

Ejemplos de su uso en compresión multimedia de jpeg y mp3.

Referencias

Codificación de Huffman

Algoritmo de Huffman

Algoritmos voraces