domingo, 21 de marzo de 2010

PROYECTO 3 "MAXIMO COMUN DIVISOR"

Hola, mi nombre es Gustavo Adolfo Salas Coronado pertenezco al grupo de los jueves y este es mi proyecto numero 3 que hize con mis compañeros de equipo

Carlos Triana Sarmiento http://www.eddypre.blogspot.com
Hiram Martinez Torres http://hiramalgoritmos.blogspot.com/
Fernando Aguilar http://algoritmosfernando.blogspot.com/




1.-Un algoritmo recursivo se usa cuando un programa que es corto necesita repetir ciertos ciclos para ello tambien se simplifica la escritura del pseudocodigo, haciendolo mas largo pero mas facil de analizar y entender. Cuando se usa un algoritmo recursivo se consumen mas recursos del sistema como memoria o uso del procesador, si se tiene una buena memoria y un buen procesador es recomendable usar algoritmos recursivos, pero si no se cuenta con tales recursos pues lo mas conveniente seria usar un algoritmo iterativo.

el siguiente es un ejemplo de un algoritmo recursivo que es el que viene en nuestra presentacion:

00.INICIO
01 .int a, b, p, q, r, mcd //Declaración de variables todas enteras
02 .IMPRESION (Introduzca dos números enteros y positivos)
//Introducción de los numero enteros
03. DATOS(a, b) //Datos en este ejemplo yo puse un 32 y un 56
04 .WHILE( a <= 0 || b <= 0 ) //Esta condición no se cumple porque no introduje
//números negativos, esta condición es solo para evitar los números negativos
05 .IMPRESION(Los números deben ser positivos, Introduzca nuevamente)
//Impresión de arriba en caso de introducir números negativos
06 .DATOS(a, b) //Datos en este ejemplo yo puse un 32 y un 56
07 .IF(a < b) //La condición se cumple porque 32<56
//Por lo tanto se ejecuta el código siguiente:
08 .p = b //Estas igualdades de variables solo son para
09 .q = a //representar el orden de los números en las operaciones
//En este caso p=56 y q=32
10 .ELSE
11 .p = a //Si no se cumpliera la condición pasada(a
12 .q = b //Este seria el orden que llevaría la operación
13 .r = p%q //Por lo tanto r=56%32, r=24
14 .WHILE ( r != 0 ) //Vemos que r=24 y cumple la condición(r!=0)
//Por lo y tanto se ejecuta todo el siguiente código donde se igualan las variables iniciales a otras
nuevas, para que se cumpla la secuencia de Máximo común divisor
15 .p = q //En este caso p=32
16 .q = r //Recordemos el valor de r=24, por lo tanto q=24
17.r = p%q //Ahora calculamos un nuevo valor de r
//r=32%24 r=8, y la condición de while es (r!=0) entonces se sigue ejecutando el código.
//Ahora p=q, q=r, p=24,q=8
//Seguimos con la operación r=p%q, r=24%8, r=0
//Con esto se rompe el ciclo while(r!=0) porque r=0
//Se sale del ciclo y continua con las siguientes lineas de código
18.mcd= q
//Recordando que nuestra ultima q=8, mcd =8
19.IMPRESION( a, b, mcd) //Impresión los 2 valores ingresados y su mcd.
20.FIN


2.-Bueno la verdad siempre la ventaja de trabajar como grupo es que siempre hay un margen mas amplio de ideas que aportar, con ello se logra realizar un trabajo muy bien hecho. Las ideas que aporta cada integrante son de vital importancia se toman en cuenta todas las ideas y se unen para formar una sola que seria la que termine plasmada en el trabajo.

3.-Mi contribucion al trabajo fue lo del ultimo punto que fue lo de:

Conclusiones y recomendaciones sobre cuándo usar
recursión y cuándo iteración.

4.-La verdad yo pienso que cada kien hizo muy bien su parte, ya que si alguien faltar tendriamos un trabajo incompleto y pues lo que me toco a mi es de la misma importancia que lo que le toco hacer a los demas del ekipo.

5.-En un futuro se podria mejorar estudiando mas sobre el tema y metiendose mas a fondo, con esto me imagino q los trabajos serian de mayor calidad y mas faciles de hacer.

LAS LIGAS A LOS BLOGS YA LAS PUSE ARRIBA.


ENTONCES PUES ESTA ES LA LIGA A LAS DIAPOSITIVAS ESTA ALOJADA EN MEGAUPLOAD.

http://www.megaupload.com/?d=D2SS5NNS


bueno eso es todo gracias por la atencion.

viernes, 5 de marzo de 2010

PROYECTO #2

Hola mi nombre es Gustavo Adolfo Salas Coronado estoy en la clase de los jueves de v1-v3 y esta es mi investigacion.



Codigos de Huffman

Los códigos de Huffman son una técnica muy útil para comprimir ficheros.
El algoritmo voraz de Huffman utiliza una tabla de frecuencias de aparición de cada carácter para construir una forma óptima de representar los caracteres con códigos binarios.

Ejemplos:

Se tiene un fichero con 100.000 caracteres que se desea compactar. Las frecuencias de aparición de caracteres en el fichero son las siguientes:


Puede usarse un código de longitud fija (de 3 bits). El fichero requeriría 300.000 bits.


Puede hacerse mejor con un código de longitud variable, dando codificaciones cortas a los caracteres más frecuentes y más largas a los menos frecuentes.Este código ahorra algo más del 25% (requiere 224.000 bits en lugar de 300.000).


Se precisa un código libre de prefijos:
–Ninguna codificación puede ser prefijo de otra.
–De esta forma, la decodificación es inmediata pues no hay ambigüedades.
–Por ejemplo: „001011101‟ sólo puede ser „aabe‟.

El código se representa mediante un trie(árbol lexicográfico):
–árbol binario cuyas hojas son los caracteres codificados;
–el código de cada carácter es el camino desde la raíz hasta la hoja, donde ir al hijo izquierdo significa 0 e ir hacia el derecho significa 1.

Ejemplo: árboles de los dos códigos anteriores.



–Cada hoja está etiquetada con un carácter y su frecuencia.
–Cada nodo interno está etiquetado con la suma de los pesos de las hojas de su subárbol.
–Un código óptimo siempre está representado por un árbol lleno:cada nodo interno tiene dos hijos.
Si el alfabeto que se quiere codificar es C, entonces el árbol del código óptimo tiene |C| hojas y |C|-1 nodos internos.

  • El algoritmo voraz de Huffman construye el árbol Ade un código óptimo de abajo hacia arriba.
  • Utiliza una cola Q de árboles con prioridades (las frecuencias hacen de prioridades).
  • Empieza con un conjunto de |C| hojas en Q y realiza una secuencia de |C|-1 “mezclas” hasta crear el árbol final.
  • En cada paso, se “mezclan” los dos objetos (árboles) de Q que tienen menos frecuencia y el resultado es un nuevo objeto (árbol) cuya frecuencia es la suma de las frecuencias de los dos objetos mezclados.

Y aqui el algoritmo:

Inicio
{Pre: C es el conjunto de caracteres y f es el
vector de frecuencias}
funciónHuffman(C:conjunto;f:vectFrec)
devuelveárbol
variablesQ:colaPri; i,fx,fy,fz:entero;
z,x,y:árbol
principio
creaVacía(Q);
para todox en C hacer
inserta(Q,)
fpara;
parai:=1 hasta|C|-1 hacer
:=primero(Q); borra(Q);
:=primero(Q); borra(Q);

fz:=fx+fy;
z:=creaÁrbol(raíz=>fz,
hijoIzq=>x;
hijoDer=>y);
inserta(Q,)

fpara;
:=primero(Q); borra(Q)
devuelvez
fin
{nota: z es el árbol de un código libre de
prefijos óptimo para (C,f)}

Para el ejemplo anterior esta lo siguiente:





Esto es un problema np ya que muestra diferentes soluciones.


Bueno pues eso es todo mi investigacion la sake de un archivo pdf que lo podran encontrar en el siguiente link http://www.slideshare.net/mejiaff/varios-algoritmos-voraces-de-decisin-y-optimizacin.

Me despido gracias por visitar mi blog