Algoritmos basados en animales: como los pelos de mosca ayudaron a resolver de una mejor manera los conjuntos independientes maximales

Hablemos un poco sobre teoría de grafos y sus implicaciones en la relación directa entre los nodos de redes inalámbricas, podría parecernos algo muy trivial y sin importancia, pero es un problema que ha costado mucho tiempo y esfuerzo, de hecho, en la actualidad no se tiene solución, sin embargo se están realizando estudios para entender mejor este problema y encontrarle solución.

Gracias a la forma en que están organizados los pelos de la mosca de la fruta, tiene el potencial de proporcionar la solución a los problemas que plantean las redes inalámbricas, ya que ésta es más simple y eficiente que cualquier red elaborada por el ser humano.

Mantener comunicados de forma eficiente dos computadoras es una tarea muy sencilla. Pero a medida que el número de computadoras de la red comienza a aumentar, la situación se complica. Las redes actuales suelen ser muy poco eficientes, sobre todo cuando el sistema de conexión elegido es el inalámbrico.

Teoría de grafos

Teoría de Grafos

Teoría de Grafos

La Teoría de Grafos juega un papel importante en la fundamentación matemática de las Ciencias de la Computación. Los grafos constituyen un instrumento básico para modelar fenómenos
discretos y son fundamentales para el entendimiento de las estructuras de datos y el análisis de algoritmos. En matemáticas y ciencias de la computación, la teoría de grafos estudia las propiedades de los grafos, que son colecciones de objetos llamados vértices (o nodos) conectados por líneas llamadas aristas (o arcos) que pueden tener orientación (dirección asignada). Típicamente, un grafo está diseñado por una serie de puntos (los vértices) conectados por líneas (las aristas).

Grafo

Grafo

Grafo

Un grafo es una dupla G = (V, A), donde V es un conjunto de puntos, llamados vértices, y A es un conjunto de pares de vértices, llamadas aristas, ¿Fácil no?.

En teoría de grafos, sólo queda lo esencial del dibujo: las formas de las aristas no son relevantes, sólo importa a qué vértices están unidas. La posición de los vértices tampoco importa, y se puede variar para obtener un grafo más claro.

Generalmente, se considera que colocar los vértices en forma de polígono regular da grafos muy legibles. Prácticamente cualquier red puede ser modelada con un grafo: una red de carreteras que conecta ciudades, una red eléctrica o un alcantarillado y por supuesto una red inalámbrica.

Conjunto independiente o estable

Ahora que ya sabemos lo que es un grafo entremos más en materia. Un conjunto independiente o estable es un conjunto de vértices en un grafo tal que ninguno de sus vértices es adyacente (Que está muy próximo o unido a) a otro. Es decir, es un conjunto V de vértices tal que para ningún par de ellos existe alguna arista que los conecten. En otras palabras, cada arista en el grafo contiene a lo más un vértice en V. El tamaño de un conjunto independiente es el número de vértices que contiene. Creo que la cosa se complica un poco.

Conjunto independiente maximal

Enfoquémonos en lo que las moscas nos pueden ayudar. Un conjunto independiente maximal es un conjunto independiente tal que, añadiendo cualquier otro vértice al conjunto, éste deja de ser independiente, ¿Claro no?

Bueno dejémonos de tanto rollo y hagámoslo más legible.

Al igual que en una red de ordenadores basada en la arquitectura cliente-servidor, las células del sistema nervioso de la mosca de la fruta se organizan de tal manera que un pequeño porcentaje de ellas funcionen como “centros” (vértices) que proporcionan las conexiones (aristas) necesarias con las demás células nerviosas. En base a esta relación, se creó un algoritmo informático que imita esta forma de trabajo, y descubrieron que esta manera de constituirse puede utilizarse para optimizar aquellas redes de ordenadores en las que el número y posición de los nodos que la componen no están rígidamente establecidos.

mosca5c

Los principales servicios que se beneficiarían serían las redes WIFI, los sistemas de recolección de datos basados en sensores inalámbricos o grupos de robots autónomos. Noga Alon, experto en matemática e informática de la Tel Aviv University y del Institute for Advanced Study de Princeton, Estados Unidos, coautor del artículo, explica que “se trata de una solución tan simple e intuitiva que cuesta creer que no hayamos descubierto su valor 25 años antes”.

“La mosca de la fruta posee en la superficie de su cuerpo un conjunto de pelos que actúan a modo de sensores mecánicos detectores de movimiento. Algunos de estos pelos más pequeños, denominados microsetas, se desarrollan a partir de un grupo de neuronas que son precursores de órganos sensoriales (POS).”

Los expertos se basaron en una estrategia muy conocida por muchos de nosotros, el famoso juego de buscaminas, si alguna vez llegaste a jugarlo, entenderás mejor este problema.
sop-640x234

Inicialmente podemos seleccionar cualquier casilla del juego (en gris). Cuando elegimos como POS una de las células aleatoriamente (en azul) las de su alrededor quedan marcadas (en rojo), porque lo que ya no pueden elegirse en el siguiente paso, exactamente igual al buscaminas.

Así es como los investigadores desarrollaron el algoritmo para el cálculo del Conjunto independiente maximal. Esto lo hace aplicable a problemas en los que la topología del grafo es variable, como los citados.

Fuente:[Naukas][emol][cmu][ScienceMag]  Matemáticas Discretas, Teoría de grafos, Tec de Monterey, Campus Cuernavaca.

CONOCE NUESTRO BUSCADOR DE CURSOS

IR >>

Te recomendamos seguirnos en nuestras redes para estar al tanto de noticias, cursos gratuitos y memes: Clic aquí para seguirnos en Facebook | Clic aquí para seguirnos en Instagram | Clic aquí para seguirnos en YouTube.

Descargar este artículo en PDF

Lo sentimos, esta opción solo está disponible para los socios. Más información de nuestro grupo de socios.


Ernesto Mota on EmailErnesto Mota on FacebookErnesto Mota on LinkedinErnesto Mota on Twitter
Ernesto Mota
Nací en el d.f., sigo siendo defeño, hoy radico en la hermosa ciudad de Cuernavaca, Morelos, soy Ing. en Sistemas computacionales, con un posgrado en Tecnologías de información, Doctorando en ambientes virtuales de aprendizaje y realidad aumentada, Tecnólogo es mi categoría laboral, y mi linea de investigación es la realidad aumentada aplicada a nuevos entornos de aprendizaje.

Déjanos un comentario:

Deja un comentario

LO MAS HOT DE AZUL WEB

¿QUÉ QUIERES APRENDER EL DÍA DE HOY?

Ingresa nombre del curso; Python, JavaScript, etc.