Hoy en día podemos ver muchas cosas que nos pueden parecer de lo mas cotidianas, redes de comunicaciones, redes de transporte, circuitos, planificación de tareas, carreteras, líneas telefónicas, líneas de televisión por cable, el transporte colectivo metro, circuitos eléctricos de nuestras casas, automóviles, y tantas cosas mas; lo que no pensamos frecuentemente es que estos forman parte de algo que en matemáticas se denomina como grafos.
Desafortunadamente no existe una terminología estandarizada en la teoría de los grafos, por lo tanto es oportuno aclarar que las presentes definiciones pueden variar ligeramente entre diferentes publicaciones de estructura de datos y de teoría de grafos, pero en general se puede decir que un grafo como indica su nombre lo indica es la representación (para nuestro caso) gráfica de los datos de una situación particular,
Ejemplos
>El diagrama de cableado de una red en un edificio
>Supongamos que unas líneas aéreas realizan vuelos entre las ciudades, conectadas por líneas.
>Al visitar una pagina web y hacer click a un enlace, visto como un grafo los vértices son los sitios, y cuyas aristas son lógicamente los enlaces
Los Grafos Puedes Clasificarse según su aplicaciones;
Grafos múltiples (vuelos entre aeropuertos)
Grafos simples (líneas de ferrocarril)
A la orientación de los arcos:
Grafos orientados (vuelos entre aeropuertos)
Grafos no orientados (red de carreteras, líneas de teléfono)
A la existencia de funciones definidas sobre los arcos o los nodos:
Grafos no valorados
Grafos valorados (red de carreteras con kms, vuelos con duración)
Otras Aplicaciones De Grafos
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.
Los grafos se utilizan los mismos 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
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.
El concepto de recolección de basura fue inventado por John McCarthy en 1959 para evitar la gestión manual de memoria en el lenguaje Lisp.
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.
Cómo funciona
Cuando un lenguaje dispone de recolección de basura, el programador no tiene que invocar a una subrutina para liberar memoria. La reserva de memoria también es más o menos automática sin la intervención del programador. Por ejemplo:
En los lenguajes orientados a objetos: se reserva memoria cada vez que el programador crea un objeto, pero éste no tiene que saber cuanta memoria se reserva ni cómo se hace esto.
En los lenguajes declarativos: cada vez que se construye una expresión se reserva memoria (de una manera inteligente), pero el programador no es consciente de ello.
Cuando se compila el programa, automáticamente se incluye en éste una subrutina correspondiente al recolector de basura. Esta subrutina también es invocada periódicamente sin la intervención del programador.
El recolector de basura es informado de todas las reservas de memoria que se producen en el programa. Además, el compilador colabora para que sea posible llevar una cuenta de todas las referencias que existen a un determinado espacio de memoria reservado.
Cuando se invoca el recolector de basura, recorre la lista de espacios reservados observando el contador de referencias de cada espacio. Si un contador ha llegado a cero significa que ese espacio de memoria ya no se usa y, por tanto, puede ser liberado.
Naturalmente, este proceso consume un cierto tiempo en el que no se hace nada verdaderamente útil para el propósito del programa. Por tanto, no puede ser invocado con demasiada frecuencia.
En consecuencia, el único inconveniente a este mecanismo es determinar cuándo se tiene que ejecutar el recolector de basura. Existen varios algoritmos para hacerlo, pero el más eficiente es el primero de ellos:
Esperar a que no quede memoria libre, y entonces, ejecutar el recolector de basura.
Fijar un umbral de ocupación de la memoria libre y ejecutar el recolector de basura cuando se supere dicho umbral.
Ejecutar el recolector de basura a intervalos regulares (no siempre es posible).
Ejecutar el recolector de basura justo antes de cada reserva de memoria.
Permitir al programador que invoque explícitamente al recolector de basura cuando quiera.
Ventajas y desventajas
Las ventajas y desventajas de este mecanismo de gestión de memoria son las opuestas al mecanismo explícito:
El programador no puede cometer errores y queda liberado de la tediosa tarea de gestionar la memoria.
La memoria permanece retenida durante más tiempo del estrictamente necesario.
El recolector de basura tarda cierto tiempo en hacer su tarea y produce pausas que pueden hacer la técnica incompatible con sistemas de tiempo real.
Cómo se implementa
Existe la posibilidad de implementar la recolección de basura como una biblioteca de código más, pero por norma general no es así. El propio diseño de ciertos lenguajes de programación hace necesaria la existencia del recolector de basura. Para poder implementar estos lenguajes se requieren dos actuaciones:
Que el compilador proporcione la información necesaria para el recolector de basura (el contador de referencias).
Que el entorno de ejecución o máquina virtual implemente la subrutina del recolector de basura.
