lunes, 25 de abril de 2011

Capítulo III

3. Teoría de Grafos.


Las computadoras son buenas
siguiendo instrucciones,
no leyendo tu mente.
Donald Knuth.

Desarrollo de capacidades del alumno:

§  Que el alumno a partir de los grafos, sea capaz de formalizar y especificar proyectos de ingeniería en sistemas computacionales.
§  Que el alumno sea capaz de distinguir las diferentes teorías sobre grafos y la forma en que se aplican en diferentes ámbitos de la ingeniería en sistemas computacionales.
§  El alumno será capaz de conocer la importancia de los grafos dentro del campo profesional de la Ingeniería en Sistemas Computacionales.
§  Partiendo de los conceptos de árboles el alumno será capaz de aplicarlo en el planteamiento formal de problemas computacionales.
§  Partiendo del conocimiento de las estrategias de los algoritmos de búsqueda, el alumno será capaz aplicarlos en la solución de problemas computacionales.
§  Partiendo del conocimiento de la teoría redes, el alumno será capaz de identificar y modelar  la solución a problemas de redes de transporte.
§  Partiendo del conocimiento de las redes de Petri, el alumno será capaz de formalizar y especificar aplicaciones en la ingeniería en sistemas computacionales.
§  En general el alumno será capaz de entender la importancia de estudiar  los problemas de ingeniería en sistemas computacionales, mediante un análisis formal apoyándose en la teoría de grafos.

Preguntas básicas.

Quién se inicia en el estudio de las matemáticas discretas y se topa con el tema de teoría de grafos debe hacerse cuatro preguntas básicas. ¿De qué trata?, ¿Para qué sirve? ¿Cómo se relaciona con la carrera de Ingeniería en Sistemas Computacionales?  ¿Y por qué es tan apasionante?

¿De qué trata?

La teoría de grafos (o teoría de gráficas), trata del estudio matemático de problemas asociados a rutas o trayectorias en una, dos o más dimensiones mediante representaciones gráficas con el propósito de ofrecer soluciones algorítmicas a dichos problemas. En general, la teoría de grafos se puede describir a través de un problema clásico de computación conocido como el problema del agente viajero y que en resumen trata del encontrar la trayectoria mínima al visitar varias ciudades sin pasar dos veces por la misma ciudad.  Un problema asociado al agente viajero es el siguiente: en una tarjeta de circuito impreso (como la tarjeta madre de una computadora), se presenta el problema de interconectar los componentes como diodos, resistencias, capacitores, transistores y pines de conexión de circuitos integrados,  las pistas de interconexión de componentes no deben cruzarse porque daría paso a un corto circuito, pero al mismo tiempo, los componentes se deben conectar siguiendo la ruta más corta y todo circunscrito al área limitada de la tarjeta del circuito impreso.

¿Para qué sirve?

La teoría de grafos son modelos matemáticos que nos sirven para representar y diseñar soluciones computacionales de manera grafica. En general, podemos pensar que las aplicaciones computacionales tratan de objetos abstractos que interactúan bajos ciertas reglas definidas y que estos objetos abstractos representan objetos del mundo real que realizan ciertas actividades también sujetos a reglas establecidas. Imagine, por ejemplo el tráfico aéreo de la ciudad de La Paz. El controlador del sistema de control de tráfico aéreo visualiza en su monitor de computadora las llegadas y salidas de los aviones. Los pilotos deben formar los aviones en una cola en la que se deben respetar las prioridades de llegada y de salida establecidas por el controlador. Los aviones en el sistema de navegación aérea se visualizan como puntos que se mueven en una trayectoria y que muestran al controlador  la ruta del avión real. Cada punto en el sistema que el controlador visualiza en su monitor es una representación abstracta de un avión y uno se pregunta ¿Qué información trae asociada cada punto? La información típicamente es: número de vuelo (que relaciona tamaño del avión, el origen y destino del vuelo), aerolínea y trayectoria, es decir información pertinente y útil al controlador aéreo para que llegado el caso pueda éste tomar decisiones. La información pertinente de cada avión almacenado en el sistema se conoce como un registro de información mientras que la forma es que se organizan estos registros es decir en forma de “cola” se conoce como estructura de datos. Toda la actividad del tráfico aéreo se controla mediante programas computacionales elaborados con algoritmos muy precisos de la teoría de grafos. La estructura de datos en forma de cola, es conveniente para el control de tráfico aéreo, pero en algunas otras aplicaciones computacionales son más convenientes otro tipo de estructuras de datos como pilas o árboles y sus algoritmos asociados. En resumen podría decirse que la teoría de grafos nos sirve para crear modelos matemáticos que nos dan pautas de solución a diversas aplicaciones computacionales ayudándonos en la construcción de las estructuras de datos y la elaboración de algoritmos para manejarlas. Más adelante abundaremos más detalladamente sobre las estructuras de datos y los algoritmos.

¿Cómo se relaciona con la carrera de Ingeniería en Sistemas Computacionales? 

Un sistema de software o de la electrónica digital no trivial debe sr especificado, por ejemplo, la especificación de un sistema de control automático para una refinería de petróleo  debe ser precisa, no únicamente la especificación del sistema final, sino también de los subsistemas y componentes que se usaran para construir el sistema. Dependiendo del contexto el ingeniero en sistemas computacionales debe formular la especificación del sistema, tanto si se trata de la fase de análisis como si se trata de la fase de diseño. Una especificación de diseño por ejemplo se expresa en términos de la forma en que se va a usar el sistema; el diseño se entrega como un documento o como un prototipo que describe la arquitectura del sistema y la implantación. En general los grafos les son útiles a los ingenieros en sistemas computacionales para modelar y describir sistemas reales que se desean automatizar mediante aplicaciones computacionales. Los grafos en general los usa el ingeniero en sistemas computacionales para modelar las estructuras de datos de los objetos que interactúan en una situación real y al mismo tiempo para desarrollar los algoritmos para manipular dichas estructuras de datos. Un modelo producto de la teoría de grafos pasa por varias fases de desarrollo que tienen que ver con el análisis, el diseño y la implantación, prueba y documentación aunque no necesariamente en este orden.

¿Y por qué es tan apasionante?

Si estudiamos la teoría de grafos como un  sistema matemático abstracto quizá no sea muy apasionante, pero en cuanto nos adentramos en las aplicaciones computacionales un nuevo paisaje se muestra ante nosotros. Imagine la situación en la que un grupo de robots, por alguna razón tiene que visitar varios sitios de ensamble dentro de una fabrica y deseamos que no choquen, que sigan la ruta más corta para cada visita y visiten todos y cada uno de los sitios estipulados sólo una vez. El problema se resuelve fácilmente mediante un grafo, el cual nos dirá si existe solución para un problema específico de esta naturaleza, pero además, nos dirá en caso de existir solución como resolverlo mediante un algoritmo, sin embargo, ¿Qué hay como soporte a la solución mediante grafos? Lo que existe es justamente un sistema matemático abstracto en forma de teoremas y sus demostraciones lógico matemáticas. Es muy apasionante resolver problemas mediante la tecnología computacional, porque esa es la vocación del ingeniero en sistemas computacionales, pero el ingeniero, no resuelve un problema y listo, se lava las manos, además tiene que esforzarse y sacar conclusiones y por ejemplo plantearse la siguiente pregunta ¿Se puede utilizar el resultado o el método matemático para resolver algún otro problema? Si se animan un poco, los ingenieros encontrarán fácilmente aplicaciones, las cuales consisten esencialmente en dar una interpretación concreta a los elementos matemáticos abstractos al problema. Es ese tipo de interpretación concreta es en la que el ingeniero dará muestra de mayor imaginación, ingenio y dedicación.

No hay comentarios:

Publicar un comentario