jueves, 14 de julio de 2011

Árboles

Tarea 5


martes, 12 de julio de 2011

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

sábado, 9 de julio de 2011



lñlñl

jueves, 7 de julio de 2011

Algoritmos recursivos

Tarea 3





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.
.

miércoles, 6 de julio de 2011

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

lunes, 4 de julio de 2011

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