Algoritmo para la resolución física en tiempo lineal del problema de los n-cuerpos en colonias de bacterias

Muñoz Martín, Luis Enrique (2017). Algoritmo para la resolución física en tiempo lineal del problema de los n-cuerpos en colonias de bacterias. Thesis (Master thesis), E.T.S. de Ingenieros Informáticos (UPM).

Description

Title: Algoritmo para la resolución física en tiempo lineal del problema de los n-cuerpos en colonias de bacterias
Author/s:
  • Muñoz Martín, Luis Enrique
Contributor/s:
Item Type: Thesis (Master thesis)
Masters title: Inteligencia Artificial
Date: May 2017
Subjects:
Faculty: E.T.S. de Ingenieros Informáticos (UPM)
Department: Inteligencia Artificial
Creative Commons Licenses: Recognition - No derivative works - Non commercial

Full text

[thumbnail of TFM_LUIS_ENRIQUE_MUNOZ_MARTIN.pdf]
Preview
PDF - Requires a PDF viewer, such as GSview, Xpdf or Adobe Acrobat Reader
Download (1MB) | Preview

Abstract

Con el fin de conocer mejor las dinámicas bacterianas, se han desarrollado aplicaciones que permiten simular los comportamientos que se encuentran en las colonias de éstas. Una pieza de gran importancia en estas simulaciones es el motor físico. Éste es el encargado de emular y resolver todas las interacciones físicas que ocurren en las colonias, llevándose gran parte del cómputo total del simulador. En una simulación de estas características, todas las bacterias crecen en un espacio falto de libertad, dificultando en gran medida su resolución mediante los métodos habituales. Este es un problema que se enmarca dentro de los problemas de los n-cuerpos cuya solución tiene un coste computacional de O(N2 ). En este trabajo se presenta un nuevo algoritmo, llamado Pushing by Rings, que permite la resolución de este tipo de problemas en O(N). El objetivo de esta aproximación es liberar la carga computacional que requiere el motor físico con el fin de lograr simular poblaciones de bacterias muy elevadas en poco tiempo.---ABSTRACT---Many applications have been developed with a focus kept on extracting knowledge about bacterial dynamics. The aim of these applications is to simulate behaviors that are found in bacterial colonies. An important piece in these simulations is the physics engine. It is responsible for emulating and resolving all physical interactions that arise in the colony, carrying the largest part of the computation cost within a simulator. In this type of simulations, the entire population grows in a space lacking freedom, hindering its resolution by usual methods. This problem lies in the class of n-body problems, whose solution has a cost of O(N2 ). In this work, a novel algorithm called Pushing by Rings is proposed. It allows the resolution of n-body problems applied to bacterial colonies with a computational cost of O(N). The aim of this approach is to make the computational load of the physical engine lighter, with the purpose of simulating high populations in less time.

More information

Item ID: 57242
DC Identifier: https://oa.upm.es/57242/
OAI Identifier: oai:oa.upm.es:57242
Deposited by: Biblioteca Facultad de Informatica
Deposited on: 12 Nov 2019 14:09
Last Modified: 13 Nov 2019 10:45
  • Logo InvestigaM (UPM)
  • Logo GEOUP4
  • Logo Open Access
  • Open Access
  • Logo Sherpa/Romeo
    Check whether the anglo-saxon journal in which you have published an article allows you to also publish it under open access.
  • Logo Dulcinea
    Check whether the spanish journal in which you have published an article allows you to also publish it under open access.
  • Logo de Recolecta
  • Logo del Observatorio I+D+i UPM
  • Logo de OpenCourseWare UPM