Estructura de Datos

El siguiente comentario es sobre el informe de Backtracking que realizamos, de cómo su técnica nos ayuda a resolver problemas sin tener una base, el inconveniente es que tenemos que probar todas las posibles soluciones hasta llegar a nuestro objetivo, a medida vamos conociendo de los distintos algoritmos y de las estructuras de datos nos damos cuenta de la importancia de los mismos y que no los podemos ignorar, aunque es bien difícil de encontrar información escrita para seres humanos comunes ya que en su mayoría la información está hecha en notación científica y difícil de encontrar, creo que es una de las principales razones el alumno le desagrade estos temas por su complejidad.
El llegar a conocer más de estas herramientas por así decirles nos ayudan a entender mejor como están hechas las cosas y comprender su finalidad, una vez manejándolas les podemos sacar un enorme provecho en nuestra vida profesional.
.

1 Comment

Comenzaremos definiendo.¿Qué es XML?
XML (eXtensible Markup Language) es un lenguaje orientado a identificar estructuras de datos en un documento. La especificación XML define la manera estándar de cómo hay que realizar el marcado de expresiones en un documento no estructurado , para que con dicho marcado se defina una determinada estructura de datos.

La especificación XML no define el contenido de las estructuras de datos, son los expertos de cada dominio y las entidades reguladoras, los agentes que pueden utilizar el estándar XML para consensuar un lenguaje común que permita transformar los documentos no estructurados en estructuras procesables por un sistema "machine readable system" (SGBD, HL7, EDI, etc.).

Cuando hablamos de un documento nos referimos no solo al concepto tradicional de documento en papel o soporte electrónico sino a todos los tipos de documentos actuales: páginas Web, correo electrónico, gráficos vectoriales, transacciones de comercio electrónico, etc. Un documento XML es un documento que puede ser leído y entendido por una persona "human readable system" y a la vez puede ser procesado por un sistema para extraer información "machine readable system".

XML Schemas.


¿Porqué usar XML para crear estructuras de datos?

¿Hay otras maneras para estructurar datos que no sean XML? Por supuesto, de hecho cada fabricante de hardware y software desde el origen de los tiempos ha creado sus propios mecanismos propietarios para añadir contexto a datos fuente y definir estructuras de datos. La ventaja de XML es que es un estándar con independencia del tipo de implementación seleccionado. Esto significa que podemos usar herramientas de distintos proveedores para estructurar datos con la especificación XML, almacenarlos en una base de datos, realizar búsquedas o ejecutar cualquier proceso. En conclusión, nuestros datos serán accesibles y procesables por todas las herramientas que siguen el estándar XML con independencia de su plataforma y su fabricante.

Ejemplo.


La mayoría de compañías han optado por seleccionar los estándares más aceptados en todas sus herramientas de información (un buen ejemplo son los procesadores de textos y los gestores de correo electrónico), con la finalidad de intercambiar información sin tener problemas con el formato del soporte. Cualquier procesador de textos, por muy extendido que esté en el mercado, dispone de un formato específico propiedad de su fabricante que puede ocasionar problemas en el caso de intercambio de datos a través de distintas plataformas. XML establece un formato de datos que representa un estándar abierto independiente de fabricantes y de plataformas (sistemas operativos), también permite producir documentos en entornos multimedia (web, CD-ROM) de manera muy eficiente.

Para apreciar todas las posibilidades de interoperabilidad de XML es importante saber que fue creado originalmente para poder utilizar documentos con estructuras complejas dentro de la web. De hecho incorpora una serie de nuevos elementos con respecto al HTML, pero sigue siendo una variante evolutiva del SGML. HTML y SGML no están diseñados para definir estructuras de datos. Las últimas versiones del Explorer y Netscape ya soportan la especificación XML y aunque importantes gurús del sector anuncian la extinción del HTML, lo más probable es que ambos cohabiten en las miríadas de páginas web publicadas.

Comentario.
El manejo que se le da a las estructuras de datos es estándar y se puede aplicar en cualquier plataforma, esto nos ayuda en gran manera a dar el formato y manejo que necesitemos a nuestros datos.

Bibliografia.
Taller básico XML.23 mayo 2010
http://www.vico.org/pages/Talleres/Taller_XML.html#Anchor-14210

Estructuras de datos XML.23 mayo 2010
http://translate.google.hn/translate?hl=es&langpair=en%7Ces&u=http://www.treelight.com/software/collaboration/
dataStructures0_1.html

1 Comment

La principal desventaja de usar una matriz de adyacencia para representar un grafo dirigido es que requiere un espacio 12(n2) aun si el grafo dirigido tiene menos de n 2 cos. Sólo leer o examinar la matriz puede llevar un tiempo O ( n 2) , lo cual invalidaríalos 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 puede representar G por medio de un arreglo CABEZA, donde CABEZA[:] 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 del número de vértices más el número de arcos; se usa bastante cuando el número de arcos es mucho menor que n'. Sin embargo, una desventaja potencial de la representacion con lista de adyaccia es que puede llevar un tiempo 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.

Bibliografia.
Matrices de Adyacencia.15 mayo 2010
http://docencia.udea.edu.co/regionalizacion/teoriaderedes/representacionu1.html

1 Comment

La aplicación de búsqueda (x) es sencillo. Comenzamos en la raíz del árbol.

Caso 1 El árbol está vacío: entonces x no está presente.
Caso 2 x = y (el tema en la raíz): y entonces el tema, en la raíz se devuelve
Caso 3 x Caso 4 x> y: búsqueda recursivamente el subárbol derecho.

Buscando un árbol binario de un valor específico puede ser un recursivo o iterativo proceso. Esta explicación abarca un método iterativo.
Comenzamos examinando el nodo raíz . Si el árbol es nulo, el valor que está buscando no existe en el árbol. De lo contrario, si el valor es igual a la raíz, la búsqueda tiene éxito. Si el valor es inferior a la raíz, busque en el subárbol izquierdo. Del mismo modo, si ésta es superior a la raíz, busque en el subárbol derecho. Este proceso se repite hasta que el valor se encuentra o el subárbol indicado es nulo. Si el valor buscado no se encuentra ante un subárbol nula es alcanzado, entonces el tema no debe estar presente en el árbol.
El tiempo de duración de la operación de búsqueda es O (h), donde h es la altura del árbol. Por lo tanto, si el árbol está equilibrado y en su altura mínima (es decir, si el árbol está casi completo), entonces el caso en tiempo de ejecución peor, siendo directamente proporcional a la altura del árbol, es log n. Por ejemplo, para un árbol de búsqueda binario con n elementos, con n = 1000, que necesita alrededor de 10 comparaciones para la operación de búsqueda, con n = 1.000.000, se necesita alrededor de 20 comparaciones. Sin embargo, si el árbol de búsqueda binaria es desequilibrado y es alargada , el tiempo de ejecución de una operación de búsqueda es más largo.



Bibliografia.
Evelyne Robidoux.17 de febrero 1997.Arbol de busqueda binaria.14 mayo 2010
http://translate.google.hn/translate?hl=es&langpair=en|es&u=http://www.cs.mcgill.ca/~cs251/OldCourses/1997/topic9/
Henning Biermann.22 de marzo 1998.Los árboles binarios de búsqueda.14 mayo 2010
http://translate.google.hn/translate?hl=es&langpair=en|es&u=http://cs.nyu.edu/algvis/java/bst.html

1 Comment

Modelizacion de la World-Wide Web
Estudio de la topología de la Web (conectividad, diámetro).
Formulación de algoritmos de valoración de las paginas web (p.e. algoritmo
PageRank de Google).



Aplicación a la Ecología.
Estudio de la conectividad del paisaje (Urban et al.)



Análisis del camino critico.
Formulación del problema: Planificar las actividades de un proyecto de forma
que el tiempo total para realizarlo sea el menor posible.
Modelizacion: Dado el correspondiente grafo de actividades, hallar el camino
mas largo entre los v ertices que representan los estados `inicio' y ` fin'.



El problema de los `horarios'
Formulaci on del problema: Confeccionar un calendario de examenes, que
comprenda el mínimo numero de días, teniendo en cuenta que un estudiante
no puede realizar mas de un examen en un mismo día.
El problema de la asignación de frecuencias en una red celular de
teléfono a móvil.
Formulación del problema: Asignar a cada celda un rango de frecuencias de
manera que celdas contiguas tengan rangos disjuntos (`bien separados').
Como debe hacerse dicha asignación con el fin de minimizar el total de
frecuencias usadas.
Modelizaci on: Dado el grafo de incompatibilidades, hallar una vértice
coloración del mismo utilizando el menor numero de colores posible.

El problema del camino m nimo (Dijkstra, 1959)
Formulaci on del problema: Dada una red de transporte hallar la ruta optima
entre cada par de elementos de la misma.
Modelización: Calcular la distancia y encontrar un camino minimo entre cada
par de vértices de un grafo conexo y ponderado.



El problema de los de cuatro colores (Appel y Haken 1976)
Conjetura (Francis Guthrie, 1852): Todo mapa trazado sobre una hoja de
papel puede colorearse usando solamente cuatro tintas de manera que
los paises" con \frontera com un" tengan colores diferentes.



An alisis de redes el ectricas (Kirchho , 1847).


Enumeración de is-omeros quimicos (Cayley, 1857).


Comentario.
Nos sirven para dar una mejor interpretación sobre un problema que tengamos y por medio de un algoritmo matemático poder resolverlo de la mejor manera.

Bibliografía.
Aplicaciones de los grafos.12 mayo 2010
http://web.udl.es/usuaris/p4088280/teaching/grafos_modelos.pdf

1 Comment

Los árboles de expresiones representan el código de nivel del lenguaje en forma de datos en otras palabras "se permite manejar el código como si fueran datos y los datos como si fueran código". Los datos se almacenan en una estructura con forma de árbol. Cada nodo del árbol de expresión representa una expresión, por ejemplo, una llamada al método o una operación binaria, como x < y.

En la ilustración siguiente se muestra un ejemplo de una expresión y su representación en forma de un árbol de expresión. Las diferentes partes de la expresión tienen un color distinto para hacerlas coincidir con el nodo correspondiente del árbol de expresión. También se muestran los diferentes tipos de los nodos del árbol de expresión.



Inmutabilidad de los árboles de expresiones.

Los árboles de expresiones son inmutables. Esto significa que si desea modificar un árbol de expresión, debe construir un nuevo árbol de expresión; para ello, deberá copiar el árbol existente y modificarlo. Puede utilizar un visitante de árbol de expresión para que recorra el árbol de expresión existente.
Cuando se ejecuta un árbol de expresión, puede devolverse un valor o simplemente puede realizarse una acción, como llamar a un método.

¿Que es una expresión lambda?
"Una expresión lambda 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".

Una forma más simple de definirla sería:

Para definir una expresión lambda se usa el llamado operador lambda (=>).
A la izquierda de este operador se indicarán las variables o parámetros de la función anónima.
A la derecha del operador indicaremos el código de la función (la expresión o bloque de instrucciones).

Las lambda como árboles de expresión
Los compiladores de C# y VB.NET pueden, bajo determinadas circunstancias, utilizar las lambdas para crear un árbol de expresión, una estructura en memoria que representa en forma de árbol las operaciones a realizar, y en el orden que hay que hacerlo, para lograr un objetivo.

Uso de los árboles de expresión C#.
Se utilizan para crear intérpretes de expresiones matemáticas recibe del usuario una cadena de caracteres que representa una expresión matemática (como 2 * sin(x) * cos(x), por ejemplo) y la traduce a una representación interna que permite la posterior evaluación de la expresión para diferentes valores de las variables.

Conclusión.
Es ideal cuando tengamos interés en interpretar una expresión numérica para realizar alguna acción con ella.

Bibliografía.
msdn.Árboles de expresiones.07 abril 2010
http://msdn.microsoft.com/es-es/library/bb397951(VS.90).aspx
El Guille. 16 enero 2007.Árboles de expresiones.07 abril 2010
http://www.elguille.info/NET/futuro/firmas_octavio_ArbolesExpresiones.htm
José M. Aguilar.01 abril 2009.Árboles de expresiones.07 abril 2010
http://www.variablenotfound.com/2009/03/c-desmitificando-las-expresiones-lambda_2829.html

1 Comment