Ad astra per aspera
A volarrrr se ha dicho.............:-D
miércoles, 2 de junio de 2010
Algoritmos ávidos
Realmente pienso que su implementación es complicada aunque siempre se mencione que es fácil. Realmente vale la pena conocer de este tipo de algoritmos que se pueden aplicar en la vida real y que nos facilitan la toma de decisiones.
Probablemente no todos conozcan su aplicación pero una vez que se comprende su funcionamiento es cuando notamos de verdad que son de utiles y que las soluciones que se han obtenido son un gran aporte en la resolución de problemas.
sábado, 15 de mayo de 2010
¿Qué tiempo O(n) nos lleva representar un grafo dirigido con matrices de adyacencia? ¿ es ventajoso o no? ¿Qué otro método podemos usar?
Una representación común para un grafo dirigido G=(v,a) es la matriz de adyacencia. Supóngase que V {1,2…,n}. la matriz de adyacencia para g es una matriz A de dimensión nxn, de elementos booleanos, donde a [i,j] es verdadero sí, y solo sí existe un arco que vaya del vértice i al j . Con frecuencia se exhibirán matrices de adyacencia con 1 par verdadero y 0 para falso; las matrices de adyacencia pueden incluso obtenerse de esa forma. En la representación con una matriz de adyacencia, el tiempo de acceso requerido a un elemento es independiente del tamaño de V y A.
Así la representación con matrices de adyacencia es útil en los logaritmos para grafos en los cuales suele ser necesario saber si un arco dado está presente.
Algo muy relacionado es la representación con matriz de adyacencia etiquetada de un grafo dirigido, donde A[i,j] es la etiqueta del árbol que va del vértice i al vértice j. si no existe un arco de i a j, debe emplearse como entrada para A[i,j] un valoer que no pueda ser una etiqueta valida.
La principal desventaja de usar una matriz de adyacencia para representar un grafo dirigido es que requiere un Ω(n2) aún si el grafo dirigido tiene menos de n2 arcos. Solo leer o examinar la matriz puede llevar un tiempo O(n2), lo cual invalidara los algoritmos O(n) para la manipulación de grafos dirigidos con O(n ) arcos.
Para evitar esta desventaja se puede utilizar otra representación común para un grafo dirigido G=(v,a) llamada representación con lista de adyacencia. La lista de adyacencia para un vértice i es una lista en algún orden, de todos los vértices adyacentes a i. se pude representar G por medio de un arreglo CABEZA, donde CABEZA [i] es un apuntador a la lista de adyacencia del vértice i. la representación con lista de adyacencia de un grafo dirigido requiere un espacio proporcional a la suma de números de vértices mas el numero de arcos; se usa bastante cuando el numero de arcos es mucho menor que n2. Sin embargo una desventaja potencial es de la representación con listas de adyacencia es que puede llevar O(n) determinar si existe un arco del vértice i al vértice j, ya que puede haber O(n) vértices en la lista de adyacencia para el vértice i.
La estructura consiste (en el caso de que tengamos un grafo dirigido en una lista de vértices donde cada uno de estos posee dos listas, una de aristas incidentes a él y otra de adyacentes. Cada vez que se añade una arista al grafo se inserta en la lista de aristas adyacentes del vértice origen y en la de incidentes del vértice destino. De esta forma la estructura desplegada se asemejaría a una matriz de adyacencia en la cual hay una arista por cada 1 y el índice de la matriz es la posición dentro de la lista de vértices.
Estructuras de datos y algoritmos: Alfred V. Aho, John E. Hopcroft, Jeffrey D. Ullman
jueves, 13 de mayo de 2010
Búsqueda binaria
Un árbo binario es aquel tipo de árbol en el que sus nodos solamente pueden tener cero, uno o dos nodos hijos.
El interés de los árboles binarios de búsqueda (ABB) radica en que su recorrido en inorden proporciona los elementos ordenados de forma ascendente y en que la búsqueda de algún elemento suele ser muy eficiente.
La búsqueda en árboles binarios es un método de búsqueda simple, dinámico y eficiente considerado como uno de los fundamentales en Ciencia de la Computación. De toda la terminología sobre árboles, tan sólo recordar que la propiedad que define un árbol binario es que cada nodo tiene a lo más un hijo a la izquierda y uno a la derecha. Para construir los algoritmos consideraremos que cada nodo contiene un registro con un valor clave a través del cual se efectuaran las búsquedas.
Aplicaciones de árboles binarios
Un árbol binario es una estructura de datos útil cuando se trata de hacer modelos de procesos en donde se requiere tomar decisiones en uno de dos sentidos en cada parte del proceso. Por ejemplo, supongamos que tenemos un arreglo en donde queremos encontrar todos los duplicados. Esta situación es bastante útil en el manejo de las bases de datos, para evitar un problema que se llama redundancia.
Una manera de encontrar los elementos duplicados en un arreglo es recorrer todo el arreglo y comparar con cada uno de los elementos del arreglo. Esto implica que si el arreglo tiene elementos, se deben hacer comparaciones, claro, no es mucho problema si es un número pequeño, pero el problema se va complicando más a medida que aumenta.
Si usamos un árbol binario, el número de comparaciones se reduce bastante, veamos cómo.
El primer número del arreglo se coloca en la raíz del con sus subárboles izquierdo y derecho vacíos. Luego, cada elemento del arreglo se compara son la información del nodo raíz y se crean los nuevos hijos con el siguiente criterio:
Si el elemento del arreglo es igual que la información del nodo raíz, entonces notificar duplicidad.
Si el elemento del arreglo es menor que la información del nodo raíz, entonces se crea un hijo izquierdo.
Si el elemento del arreglo es mayor que la información del nodo raíz, entonces se crea un hijo derecho.
La búsqueda lineal probablemente es sencilla de implementar e intuitiva. Básicamente consiste en buscar de manera secuencial un elemento, es decir, preguntar si el elemento buscado es igual al primero, segundo, tercero y así sucesivamente hasta encontrar el deseado. Entonces este algoritmo tiene una complejidad de O(n).
La búsqueda binaria al igual que otros algoritmos como el quicksort utiliza la técnica divide y vencerás. Uno de los requisitos antes de ejecutar la búsqueda binaria, es que el conjunto de elementos debe de estar ordenado. La idea consiste en ir dividiendo el arreglo en mitades. Por ejemplo supongamos que tenemos este vector:
int vector[10] = {2,4,6,8,10,12,14,16,18,20};
La clave que queremos buscar es 6.
El algoritmo funciona de la siguiente manera:
Su tiempo es (log2 n)
- Se busca el elemento del centro de la lista.
-Si es el buscado, se devuelve Si es mayor que el buscado (6), se repite la búsqueda sobre la primera mitad de la lista.
-Si es menor que el buscado (6), se repite la búsqueda sobre la segunda mitad de la lista.
-Se repite el algoritmo hasta que se encuentra el elemento o se llega a una lista de longitud cero (el elemento no existe).
Este proceso se resume de la siguiente forma: comienza comparando el elemento central del arreglo con el valor buscado. Si ambos coinciden finaliza la búsqueda. Si no ocurre así, el elemento buscado será mayor o menor en sentido estricto que el central del arreglo. Si el elemento buscado es mayor se procede a hacer búsqueda binaria en el subarray superior, si el elemento buscado es menor que el contenido de la casilla central, se debe cambiar el segmento a considerar al segmento que está a la izquierda de tal sitio central.
http://decsai.ugr.es/~jfv/ed1/tedi/cdrom/docs/arb_BB.htm
http://computacion.cs.cinvestav.mx/~acaceres/courses/estDatosCPP/node53.html
http://www.mailxmail.com/curso-aprende-programar/metodos-ordenamiento-busqueda
martes, 11 de mayo de 2010
Aplicacion de grafos en la vida real
buscando encontre unos cuantos ejemplos que fueron los que me resultaron bastante interesantes con sus respectivos links.
Ejemplos:
1
Uso de Grafos de Conceptos para la Generación Automática de Resúmenes en Biomedicina
La cantidad de documentación electrónica accesible desde cualquier lugar y cualquier dispositivo crece de manera exponencial. Gracias a los avances tecnológicos de las ´ultimas décadas, su almacenamiento y acceso ya no suponen un problema, pero el tiempo sigue siendo un bien valioso y limitado. Esta realidad afecta especialmente al campo de la medicina, en el que los recursos digitales son muchos y muy variados.
Es obvio que en este contexto, la generación automática de resúmenes (en adelante,
GAR), ya sean informativos o meramente indicativos, puede ser de gran utilidad.
Durante el ejercicio de la medicina, disponer de resúmenes de los historiales de los asientes puede ayudar a los profesionales a actuar con mayor celeridad en el tratamiento de urgencias sanitarias; mientras que, durante la Formación y la investigación, los resúmenes pueden ser útiles para determinar si un documento resulta de interés, y si merece o no una lectura exhaustiva.
Durante los últimos años, y como respuesta a esta explosión de información, han aparecido nuevos recursos lingüísticos para su tratamiento. Diccionarios, tesauros, bases de datos léxicas y grandes bases de conocimiento biomédico, muchos de ellos de disponibilidad publica, facilitan la construcción de sistemas de procesamiento de lenguaje natural y les confieren mayores garantías de éxito.
Por otra parte, construir resúmenes genéricos y totalmente independientes del Contexto es un ideal aún lejos de alcanzar.
Restringir el problema a un dominio concreto, la biomedicina, y un tipo de documentos
Específico.
En este trabajo se propone un método De extracción de oraciones de artículos biomédicos, mediante el mapeo del documento a los conceptos de la ontología biomédica, y la representación del documento y de sus oraciones como grafos. La selección de las oraciones relevantes se realiza a partir de la conectividad de los conceptos que contienen en el grafo del documento.
http://www.sepln.org/revistaSEPLN/revista/41/sec7-art2.pdf
2
La aplicación Grafos han optimizado la planeación de rutas a través de una secuencia de
visitas planteada en una ruta inicial, demostrando que puede mejorarse dicha ruta
mediante el algoritmo del problema del viajante tomando en cuenta factores como kilómetros, tiempo y coste .
http://www.upo.es/RevMetCuant/art21.pdf
3
La necesidad de realizar un análisis de impacto previo a la implementación de un cambio de configuraciones en la infraestructura tecnológica de un servicio de telecomunicaciones se puede realizar mediante un análisis que puede ser realizado visualizando a los componentes de la infraestructura como un grafo sobre el cual, realizando recorridas, se puede efectuar un análisis de alcance y con ello identificar a los involucrados. http://telcom2006.fing.edu.uy/trabajos/mvdtelcom-001.pdf
Anteriormente cito cada ejemplo con su link debido a que son estudios un tanto extensos y para una mejor comprensión es necesario leer los articulos completos, pero definitivamente me gusto mucho el tercero debido a la implementacion en telecomunicaciones.
sábado, 8 de mayo de 2010
Arboles Binarios
En teoría de grafos, se usa la siguiente definición: «Un árbol binario es un grafo conexo, acíclico y no dirigido tal que el grado de cada vértice no es mayor a 3». De esta forma sólo existe un camino entre un par de nodos.
Un árbol binario con enraizado es como un grafo que tiene uno de sus vértices, llamado raíz, de grado no mayor a 2. Con la raíz escogida, cada vértice tendrá un único padre, y nunca más de dos hijos. Si rehusamos el requerimiento de la conectividad, permitiendo múltiples componentes conectados en el grafo, llamaremos a esta última estructura un bosque.
Tienen una corta pero importante historia. A finales de los años 60, fabricantes de computadores y grupos de investigación independientes, compitieron en el desarrollo de sistemas de archivo de propósito general y los llamados "métodos de acceso" para sus máquinas. La Sperry Univac Corporation (junto con la Case Western Reserve University), H. Chiat, M. Schwartz y otros, desarrollaron e implementaron un sistema el cual llevaba a cabo las operaciones de
Independientemente, B. cole, S. Radcliffe, M. Kauffman y otros, desarrollaron un sistema similar al de Control Data Corporation (junto con la Stanford University). R. Bayer y E. McCreight, hasta entonces, en los Boeing Scientific Research Labs, propusieron un mecanismo externo para el ndice con un costo relativamente bajo para la mayoría de las operaciones de búsqueda, inserción, actualización y borrado de datos. Lo llamaron Árbol B1. De aquí nace el Árbol B que todos conocemos.
Tipos de árboles binarios
Un árbol binario es un árbol con raíz en el que cada nodo tiene como máximo dos hijos.
Un árbol binario lleno es un árbol en el que cada nodo tiene cero o dos hijos.
Un árbol binario perfecto es un árbol binario lleno en el que todas las hojas (vértices con cero hijos) están a la misma profundidad (distancia desde la raíz, también llamada altura).
A veces un árbol binario perfecto es denominado árbol binario completo. Otros definen un árbol binario completo como un árbol binario lleno en el que todas las hojas están a profundidad n o n-1, para alguna n.
Un árbol binario es un árbol en el que ningún nodo puede tener más de dos subárboles. En un árbol binario cada nodo puede tener cero, uno o dos hijos (subárboles). Se conoce el nodo de la izquierda como hijo izquierdo y el nodo de la derecha como hijo derecho.
se usan en una inmensa gama de sistemas informáticos. Y constituyen una herramienta muy eficiente para administrar grandes volúmenes de datos. Es por ésto, que los Arboles B constituyen el núcleo de los motores de Búsqueda de las Bases de Datos.
Veamos un ejemplo real. Si como Ingenieros en Computación se nos encarga administrar la Base de Datos de todos los sufragantes de Honduras (los cuales son cientos de miles), entonces eberíamos usar una Estructura de Datos adecuada a nuestra problemática. Sabiendo que se nos pide Buscar personas, Verificar domicilios, Inscribir un sufragante, Eliminar a un sufragante, etc. La manera más idónea de hacerlo es usar una estructura dinámica y capaz de almacenar grandes cantidades de datos. Es por eso que elegimos los Arboles B, porque nos entregan una eficaz administración de los datos de muchas personas.
Además se usan en aplicaciones de Administración de Memoria, los Sistemas Operativos deben realizar un manejo óptimo de los datos en memoria primaria. Los Arboles B+ son muy usados en este ámbito.
En mi opinion las aplicaciones de los arboles binarios son muy variadas ya que se les puede utilizar para representar una estructura en la cual es posible tomar decisiones con dos opciones en distintos puntos, pero siento qiue poder implementarlos es complicado y repsentan ciertas desventajas como: Pero este tipo de árboles tienen varias desventajas:
Es difícil construir un árbol binario de búsqueda perfectamente equilibrado.
El número de consultas en el árbol no equilibrado es impredecible.
Y además el número de consultas aumenta rápidamente con el número de registros a ordenar..
http://msdn.microsoft.com/en-us/library/bb397951.aspx
http://msdn.microsoft.com/es-es/library/bb882536(v=VS.90).aspxhttp://articulos.conclase.net/?tema=algoritmos&art=arbolesb&pag=000
http://usuarios.multimania.es/arbolesbpro/historia.htm
http://es.wikipedia.org/wiki/%C3%81rbol_binario
Manejo de árboles en C#
En c# se pueden implementar una expresión lambda que es una función anónima que puede contener expresiones e instrucciones y se puede utilizar para crear delegados o tipos de árboles de expresión.
Todas las expresiones lambda utilizan el operador lambda = >, que se lee como "va a". El lado izquierdo del operador lambda especifica los parámetros de entrada (si existe alguno), mientras que el lado derecho contiene el bloque de expresiones o instrucciones. La expresión lambda x => x * x se lee "x va a x veces x". Esta expresión se puede asignar a un tipo de delegado del siguiente modo:
Las expresiones lambda de C# 3.0 ofrecen una posibilidad adicional, no disponible para los métodos anónimos, y que juega un papel importante en la implementación de la tecnología LINQ (Language Integrated Query – Consultas Integradas en el Lenguaje), que también será incorporada a la próxima versión de C# y VB y que constituye, según la modesta opinión de este autor, uno de los avances más significativos de los últimos tiempos en el área de los lenguajes y sistemas de programación.
C# da la posibilidad de que las expresiones lambda puedan compilarse como árboles de expresiones, objetos de datos que representan en memoria al algoritmo de evaluación de una expresión. Estos árboles en memoria pueden ser luego fácilmente manipulados mediante software, almacenados, transmitidos, etc.
Como Generar árboles de expresiones
El espacio de nombres System.Linq.Expressions en c# proporciona una API para la compilación manual de árboles de expresiones. La clase Expression contiene métodos de generador estáticos que crean nodos del árbol de expresión de tipos específicos, por ejemplo, un objeto ParameterExpression, que representa una expresión de parámetro con nombre, o un objeto, MethodCallExpression, que representa una llamada a un método. ParameterExpression, MethodCallExpression y los demás tipos de árboles de expresiones específicos de la expresión se definen también en el espacio de nombres System.Linq.Expressions. Estos tipos se derivan del tipo abstracto Expression.
El compilador también puede generar un árbol de expresión. Un árbol de expresión generado por el compilador siempre tiene como raíz un nodo de tipo Expression(Of TDelegate); es decir, su nodo raíz representa una expresión lambda.
Los árboles de expresión deben ser inmutables. Esto significa que si desea modificar un árbol de expresión, debe construir un árbol de expresión nueva copiando la ya existente y la sustitución de los nodos en el mismo. Puede utilizar un visitante de árbol de expresión para recorrer el árbol de expresión existente.
http://msdn.microsoft.com/en-us/library/bb397951.aspx
http://msdn.microsoft.com/es-es/library/bb882536(v=VS.90).aspx
viernes, 30 de abril de 2010
Recolector de basura
El Concepto de Recolección de Basura FUE inventado Por John McCarthy en 1959 párr Evitar la Gestión manual de memoria en El lenguaje Lisp.
John McCarthy (n. 4 de septiembre de 1927, Boston, Massachusetts), tambien conocido Como Tío John McCarthy, es sin Prominente informático Que recibio El Premio Turing en 1971 SUS CONTRIBUCIONES Por Importantes en el Campo de Inteligencia Artificial la. De hecho ", fué el Responsable de introducir El Término" inteligencia "artificial, Concepto Que acuñó en la Conferencia de Dartmouth en 1955.McCarthy inventarios El lenguaje de Programación Lisp y publico Su DISEÑO EN Comunicaciones del ACM en 1960.
Cualquier Programa informático hace USO DE UNA Cierta Lea la versión de memoria de Trabajo Puesta A Su Disposición Por El Sistema Operativo.
This memoria Tiene Que servicios gestionada Por El Propio Programa párrafo:
- Reservar Espacios de memoria párr USO su.
- Liberar Espacios de memoria previamente reservados.
- Compactar consecutivos Espacios de memoria libres y Entre Sí.
- Llevar Cuenta de qué estan Espacios libres y Cuales no.
Generalmente, El programador dispone de Una Biblioteca de Código Que Se encarga de ESTAS tareas. No obstante, El programador es responsable Propio de utilizar adecuadamente this Biblioteca.
Ésto TIENE LA Ventaja De Que Se hace sin obligación de servicio universal Eficiente de la memoria, es Decir, Los Espacios libres de Quedán memoria de Cuando ya no necesarios hijo. No obstante, Este mecanismo Explícito de Gestión de memoria es propenso un Errores.
Por Ejemplo, sin olvidar programador PUEDE Liberar la Memoria De Que Manera, Tarde o Temprano, no disponible quede memoria, abortando la ejecución ni del Programa.