Algoritmo Recolector de Basura

Un recolector de basura (del inglés, garbage collector) es un mecanismo implícito de gestión de memoria implementado en algunos lenguajes de programación de tipo interpretado o semi-interpretado.

Su improtancia radica en que Cualquier programa informático hace uso de una cierta cantidad de memoria de trabajo puesta a su disposición por el sistema operativo. Esta memoria tiene que ser gestionada por el propio programa para:

* Reservar espacios de memoria para su uso.
* Liberar espacios de memoria previamente reservados.
* Compactar espacios de memoria libres y consecutivos entre sí.
* Llevar cuenta de qué espacios están libres y cuáles no.

Generalmente, el programador dispone de una biblioteca de código que se encarga de estas tareas. No obstante, el propio programador es responsable de utilizar adecuadamente esta biblioteca.

Esto tiene la ventaja de que se hace un uso eficiente de la memoria, es decir, los espacios de memoria quedan libres cuando ya no son necesarios. No obstante, este mecanismo explícito de gestión de memoria es propenso a errores. Por ejemplo, un programador puede olvidar liberar la memoria de manera que, tarde o temprano, no quede memoria disponible, abortando la ejecución del programa.

Como alternativa es necesaria una gestión implícita de memoria, donde el programador no es consciente de la reserva y liberación de memoria. Esto es obligado en algunos lenguajes de programación donde no se maneja el concepto de memoria. Por ejemplo en lenguajes declarativos como Lisp o Prolog.

Recolección de basura: El espacio de memoria se va llenando con diferentes "objetos" (representados con colores), también pueden destruirse algunos de ellos, dejando "huecos" en el espacio de memoria. Cuando ya no queda espacio disponible, o cuando lo decide la rutina de recolección de basura, la memoria es "compactada", colocando todos los "objetos" que se están usando al principio, y consolidando todos los "huecos" de memoria al final, quedando así un gran área de memoria disponible para la futura creación de objetos.

Algunos lenguajes que Usan garbage collector:

• BASIC
• C#
• Haskell
• Java
• JavaScript
• etc.
  

Como anotacion final. la mayoria de lenguajes nuevos tienen recolector de basura (garbage collector) propio, el cual va liberando automáticamente la memoria inutilizada para evitar hacer un gasto innecesario de memoria, pero los algoritmos de estos “recogedores de basura” son complicados y no son ni mucho menos perfectos, así que si le ayudamos un poco y además así maximizaremos la memoria disponible en el momento deseado.

Para liberar estos recursos podemos hacer uso de por ejemplo en PHP la variable unset($variable) para así liberar la memoria.

por ultimo dejo este video del instructor Jonathan Shewchuk de la universidad de Berkeley acerca de garbage collections en java, que espero el ingeniero guillen no lo mire para que no tome ideas de evaluacion de él jeje. este video lo encontre muy entretenido e informativo en este tema.

Bibliografia:
http://java.sun.com/docs/hotspot/gc1.4.2/
http://www.cristalab.com/tips/clase-para-manejar-el-garbage-collector-de-flash-player-c68118l/
http://www.youtube.com/watch?v=rp8PvFvSO_c
http://en.wikipedia.org/wiki/Garbage_collection_%28computer_science%29

Colorear Grafos con Algoritmos

¿Qué es un grafo?
Es aquel que se compone de un conjunto de puntos, llamados vértices, y de líneas que
unen los puntos, llamadas aristas. La Coloración de un grafo Consiste en la asignación de un color a cada vértice de
éste, de tal forma que no haya dos vértices del mismo color unidos por un arista
De manera simple, una coloración de los vértices de un grafo tal que ningún vértice adyacente comparta el mismo color es llamado vértice coloración. Similarmente, una arista coloración asigna colores a cada arista talque aristas adyacentes no compartan el mismo color, y una coloración de caras de un grafo plano a la asignación de un color a cada cara o región tal que caras que compartan una frontera común tengan colores diferentes.

La vértice coloración es el punto de inicio de la coloración, y los otros problemas de coloreo pueden ser transformados a una versión con vértices. Por ejemplo, una arista coloración de un grafo es justamente una vértice coloración del grafo de línea respectivo, y una coloración de caras de un grafo plano es una vértice coloración del grafo dual.

La convención de usar colores se origina de la coloración de países de un mapa, donde cada cara es literalmente coloreada. Esto fue generalizado a la coloración de caras de grafos inmersos en el plano. En representaciones matemáticas y computacionales es típicamente usado enteros no-negativos como colores. En general se puede usar un conjunto finito como conjunto de colores. La naturaleza del problema de coloración depende del número de colores pero no sobre cuales son.

¿Cómo colorear un grafo?


Se selecciona un vértice no coloreado y se le
asigna el nuevo color.
Se examina la lista de vértices no coloreados coloreados.
Para cada uno de ellos se determina si existe
alguna arista que una con un vértice que ya
tenga asignado el nuevo color color, si tal arista no
existe, se asigna el nuevo color al vértice.


Básicamente el algoritmo emplearía dos ciclos (en
algunos casos usa while, en otros casos ciclos for)
de esta forma por cada vértice no coloreado visita
sus adyacentes y comprueba si ya fueron
coloreados, si no han sido pintados, entonces los
colorea de tal forma que no hayan vértices
consecutivos con la misma tonalidad de color.
Este algoritmo en su forma básica nos lleva un
tiempo O(v²).

Uno de los mayores aplicaciones de la coloración de grafos, es la asignación de registros en compiladores introducida en 1981.
Gracias a la teoría de grafos se pueden resolver diversos problemas como por ejemplo la síntesis de circuitos secuenciales, contadores o sistemas de apertura. Se utiliza para diferentes áreas por ejemplo, Dibujo computacional, en toda las áreas de Ingeniería.

Los grafos se utilizan también para modelar trayectos como el de una línea de autobús a través de las calles de una ciudad, en el que podemos obtener caminos óptimos para el trayecto aplicando diversos algoritmos como puede ser el algoritmo de Floyd.

Para la administración de proyectos, utilizamos técnicas como PERT en las que se modelan los mismos utilizando grafos y optimizando los tiempos para concretar los mismos.

Creo que para problemas con algoritmos de este tipo es de suma importancia poder reconocer que nos intereza mas si rapidez o eficiencia. puesto que al ser un algoritmo tan complejo debemos tener cuidado con la misma complejidad con el que sea estructurado, para poder reducir lo mas posible la cantidad de colores a usar, tiempo de ejecucion o eficiencia de codigo.

Por ultimo dejo este excelente video con el que queda mejor plasmado la idea de coloracion de un grafo.







Bibliografía
http://www.youtube.com/watch?v=moZdSyN1KuI
http://www.sol.com/algoritmos/pagina02.asp
http://es.wikipedia.org/wiki/Teor%C3%ADa_de_grafos
http://www.infovis.net/printMag.php?num=137&lang=1
http://www.monografias.com/trabajos/grafos/grafos.shtml

Los Apuntadores en Programacion.

Los apuntadores son variables que almacenan direcciones de memoria. En general una variable contiene un valor específico dependiendo de cómo fue declarada. Un apuntador contiene la dirección de una variable que contiene un valor específico. Un puntero o apuntador es una variable que referencia una región de memoria;

En otras palabras es una variable cuyo valor es una dirección de memoria. Si se tiene una variable ' p’ De tipo puntero que contiene una dirección de memoria en la que se encuentra almacenado un valor ' v ' se dice que ' p ' apunta a ' v’.
Una variable se refiere directamente a un valor y un apuntador se refiere indirectamente a un valor. Cuentan con una declaración propia. Los apuntadores disponen de dos operadores unarios

Los apuntadores como cualquier otra variable deben de ser declarados antes de que puedan ser utilizados. El tipo de un apuntador lo proporciona implícitamente el tipo de la variable a la que apunta. Los apuntadores pueden ser declarados para apuntar a objetos de cualquier clase.

La sintaxis general de declaración es:
*
Ejemplos de declaraciones:
int *contPtr, cont;
float *res;
unsugned int *nosigno;
char *mensaje;
La variable contPtr es del tipo apuntador a entero, (int *) y se lee ``contPtr es un apuntador a int'' o ``contPtr apunta a una variable entera''.

El ejemplo que sigue es propio del lenguaje C/C++ y no es de aplicación en otros lenguajes de programación:

struct Elemento // Ejemplo de un nodo de lista doble enlazada
{
int dato;
struct Elemento *siguiente; // Para la declaración de un puntero se usa '*'
struct Elemento *anterior;
};

Los apuntadores en C, C++ son una herramienta muy potente de programación que suele causar mucha confusión en el programador sin experiencia o en quienes estamos aprendiendo a programar, y que lastimosamente en los cursos universitarios a veces se le da una cobertura muy superficial al tema de apuntadores. Además, cuando los programadores cometen un error en su utilización, puede ser muy difícil encontrar el error, por lo cual es importante saber utilizarlos muy bien. El uso de apuntadores en C y C++ es muy importante debido a que permite hacer los programas más eficientes y más flexibles. Y para el manejo de estructuras de TDAs como las pilas, listas, colas etc. son de gran importancia para crear un código de programación mas solido

dejo el video de un interesante uso de punteros:

Continuacion parte 2: http://www.youtube.com/watch?v=T7I5om7CDSk
continuacion parte 3: http://www.youtube.com/watch?v=mFs02rqsRIE

Bibliografia:
http://expo.itchihuahua.edu.mx/view.php?f=c_51#page6
http://html.rincondelvago.com/apuntadores-en-lenguajes-de-programacion.html
http://gilberto2112.brinkster.net/programaconkarel/administrador/Mis_Archivos_GRB/apuntadores.pdf

Ejemplo de Algoritmos Recursivos

Ejemplo Se muestra un programa recursivo para calcular n\, que es el producto de todos los enteros de 1 a n inclusive.
Una medida de tamaño apropiado para esta función es el valor de n. Sea T(n) el tiempo de ejecución para fact(n). El tiempo de ejecución para las líneas (1) y (2) es 0(1), y para la línea (3) es 0(1) + 7X*-1). Por tanto, para ciertas constantes c y d.Esto es, T(n-\) - c + T(n-2)> como se puede ver al sustituir n por n-\ en (1.1). Así pues, es posible reemplazar T(n-\) con c + T(n-2) en la ecuación T(n) - c + T(n-t) Después, se puede usar (1.1) para desarrollar 7\n-2), con lo que se obtiene
T(n) - 3c + T(n-3) si« > 3
y así sucesivamente. En general,
T(n) ~ ic + T(n-i) si n > i
Por último, cuando / - /i-l, se obtiene
T(n) - c(n-l) + 7(1) - c(«-l) + d (1.2)
Por eso concluye que T(n) es 0(n). Es importante observar que en este análisis se ha supuesto que la multiplicación de dos enteros es una operación de tiempo 0(1). En la práctica, no obstante, no se puede emplear el programa de la figura 1.14 para calcular n\ cuando los valores de n son grandes, pues el tamaño de los enteros que se calculen excederá del tamaño de palabra de la máquina en cuestión.
El método general para resolver una ecuación de recurrencia, tal como se tipifica en el ejemplo 1.10, consiste en reemplazar en forma repetida términos T(k) del lado derecho de la ecuación por el lado derecho completo, donde k se reemplaza por n, hasta obtener una fórmula en la que Tno aparezca en el lado derecho como en (1.2). A menudo es necesario calcular la suma de una sucesión o, si no es posible encon¬trar la suma exacta, obtener una cota superior cercana para la suma a fin de hallar una cota superior para 7^«).

Bibliografia:
Aho, Alfred V., John E. Hopcroft y Jeffrey D. Ullman. (1998). Diseño y análisis de algoritmos. En Estructuras de datos y algoritmos

Algoritmos Recursivos

Se dice que un método es recursivo si contiene llamadas o
Invocaciones a sí mismo.
Un método recursivo tendría este aspecto:
… metodoRecursivo (…){
……
metodoRecursivo (…);
……
}
Esto implica que una llamada al método recursivo puede generar una o
más invocaciones al mismo método, que a su vez genera otras
invocaciones, y así sucesivamente.

Siempre hay que asegurar que existe una condición de salida, es decir,
si se cumple esa condición, estaremos en el caso base, donde no se
producen llamadas recursivas.
Ya que la solución recursiva tiene un coste de tiempo y memoria mayor
que la iterativa. Es decir, los programas recursivos en general son
menos eficientes. Podríamos utilizar los siguientes consejos:
Los algoritmos que por naturaleza son recursivos, y donde la solución iterativa es complicada y debe manejarse explícitamente una pila para enumerar las llamadas recursivas, deben resolverse por métodos recursivos.
Cuando haya una solución obvia por iteración al problema, debe evitarse la recursividad.

El backtraking o “vuelta atrás” es una técnica algorítmica de resolución
general de problemas mediante una búsqueda sistemática de
soluciones.
Se descompone la tarea a realizar en tareas parciales de posibles
soluciones, y estas tareas parciales a su vez se descompondrán en
más tareas, en caso de que una tarea no conduzca a una solución se
tendrá que hacer vuelta atrás guardando los puntos de elección para
poder volver a ellos cuando no se alcance una solución.

Pienso que la experiencia es un factor importante al momento de programar decidir cuándo utilizar algoritmos recursivos o iterativos no es algo que deba tomarse a la ligera porque es algo que afectara positiva o negativamente al comportamiento de nuestros programas. La recursividad es quizás uno de los temas más ambiguos que y oscuros que eh recibido en cursos de programación. Sin embargo puede ser una herramienta potente si se sabe aprovechar.

Por ultimo dejo este video acerca de la resolucion de un problema simple con un algoritmo recursivo.



Bibliografía
http://www.slideshare.net/demogorgon/algoritmos-recursivos
http://es.wikipedia.org/wiki/Algoritmo_recursivo
http://www.uniandes.edu.co/la_universidad/Informatica.php
http://www.youtube.com/watch?v=FVkZzdZxEks

Volker Strasse y su investigacion de algoritmos.

Volker Strassen es un matemático alemán, profesor del departamento de matemáticas y estadística de la Universidad de Constanza.
Strassen nació el 29 de abril de 1936 en Düsseldorf-Gerresheim. estudio música, filosofía, física y matemáticas en muchas universidades alemanas, recibió su doctorado en matemáticas en 1962 en la Universidad de Göttingen bajo la supervisión de Konrad Jacobs.


Strassen comenzó su investigación como probabilista; su artículo de 1964 Un principio de invariancia para la ley del logaritmo iterado definió una forma funcional de la ley del logaritmo iterado, mostrando una forma de invariancia de escala en un paseo aleatorio. Este resultado, ahora conocido como Principio de invariancia de Strassen o Ley de Strassen del logaritmo iterado, ha sido muy citado y llevado a una presentación de 1966 en el Congreso Internacional de Matemáticos.


Ocupó un puesto en el departamento de estadística de la Universidad de California, Berkeley. En 1968, se trasladó al Instituto de Matemática Aplicada de la Universidad de Zúrich, donde permaneció 20 hasta trasladarse a la Universidad de Constanza en 1988.
En 1969, Strassen desplazó sus esfuerzos investigadores hacia el análisis de algoritmos con un artículo sobre eliminación gaussiana, presentando el algoritmo de Strassen, el primer algoritmo para realizar multiplicación de matrices más rápido que O(n3), la complejidad temporal que tendría el algoritmo más sencillo. En el mismo artículo también presentó un método asintóticamente rápido para realizar la inversión de una matriz, basada en la multiplicación rápida de matrices. Este resultado fue un importante avance teórico, logrando mucha investigación adicional sobre la multiplicación rápida de matrices, y a pesar de las mejoras teóricas posteriores sigue siendo un método práctico para la multiplicación de matrices densas de tamaños moderados a grandes. En 1971 Strassen publicó otro artículo junto a Arnold Schönhage sobre la multiplicación de enteros asintóticamente rápida basada en transformada rápida de Fourier; vea algoritmo de Schönhage–Strassen. Strassen también es conocido por su trabajo de 1977 con Robert M. Solovay por el test de primalidad Solovay–Strassen, el primer método muestra que probar cuándo un número es primo puede ser realizado tiempo polinomial aleatorio y es uno de los primeros resultados que muestra la potencia de los algoritmos aleatorios más generalmente. Se jubiló en 1998.



Bibliografia:
http://www.ics.uci.edu/~eppstein/pix/strassen/
http://www.sigact.org/prizes/knuth/2008.html
http://es.wikipedia.org/wiki/Volker_Strassen
http://www.math.uni-konstanz.de/~strassen/

Quien Soy....

Tener una identidad propia en este mundo se ha vuelto complicado, dejamos que otros decidan quienes somos. Dejamos que el molde establecido por otros se adueñe de nuestra forma de ser y pensar.

Creo en la soberanía de los pueblos y en la libertad de las personas. Soy estudiante de la carrera Ingeniería en Informática en el Centro Universitario Tecnológico (CEUTEC) y Trabajo en la Financiera Finca Honduras, en el departamento de sistemas, para poder costear mis estudios universitarios y poder obtener mayor experiencia laboral, por un mejor futuro aun cuando este en nuestra sociedad cada vez se pone más gris. Me fascina la informática, la computación, creo que estoy siguiendo la carrera correcta para mí.

Me gusta el la lectura, (cuando las tarántulas atacan y prisión verde son de esos libros que me han hecho formar una opinión muy solida acerca de las cosas que ocurren en la actualidad en mi país) me gusta el cine, los videojuegos, la música (jazz, blues, rock los favoritos), el manga, anime, comics, al fin soy una persona normal.

Pienso que la religión es lo peor en este mundo… pero también creo que Jesús murió en la cruz por mis pecado. Gran contradicción prefiero creer en El…..que en los pastores.

Por ultimo dejo el video de una de las mejores compositoras de la actualidad: Yoko Kano