Maximal triangle trades with foundation 5 (mod 6) - the final case

The maximum possible volume of a simple, non-Steiner (v, 3, 2) trade was determined for all v by Xhosrovshahi and Torabi (Ars Combinatoria 51 (1999), 211-223), except that in the-case v equivalent to 5 (mod 6), v >= 23, they were only able to provide an upper, bound on the volume. In this paper we construct trades with volume equal to that bound for all v equivalent to 5 (mod 6), thus completing the problem.

Escalas bien formadas, palabras no bien formadasa y la dualidad de Christoffel

La presente tesis analiza las escalas musicales generadas desde la perspectiva y las técnicas que ofrece la combinatoria algebraica de palabras. La noción de escala musical es una de las más primitivas: intuitivamente se puede reducir a un conjunto de notas ordenadas seg un la frecuencia de su fundamental (altura del sonido). Ya desde tiempos de la Escuela Pitagórica se vio que al pulsar una cuerda tensa, los sonidos que mejor suenan juntos, los más consonantes, están determinados por unas longitudes de cuerda cuyas proporciones son números fraccionarios sencillos. El más consonante de ellos, la octava, tiene una relación de longitudes 2:1. Este intervalo es tan consonante, que muchas veces los sonidos cuyas frecuencias están separadas en una octava suenan indistinguibles. Es por ello por lo que al estudiar las escalas se suelen identificar las notas cuya distancia es de una o varias octavas. Como resultado, suele entenderse por escala un conjunto de notas dentro de un rango de una octava, transportando dicha secuencia al resto de octavas en caso de necesidad. La definición formal de escala se llevar a a cabo en la sección 2.2, donde se mostrar a como cada octava puede representarse geométricamente mediante una circunferencia unitaria o, aritméticamente, como el conjunto cociente R=Z, es decir, como el intervalo (0,1]. De esta forma, una escala queda determinada por un conjunto de números ordenados entre el 0 y el 1 o bien, geométricamente, por un polígono inscrito en el círculo unidad...

Sistemas dinámicos secuenciales y autómatas celulares

El estudio de los sistemas dinámicos es un campo importante de la investigación matemática actual. Estos pueden ser clasificados como sistemas dinámicos clásicos y sistemas dinámicos 100% discretos. A su vez los sistemas dinámicos clásicos se pueden dividir en sistemas dinámicos discretos y sistemas dinámicos continuos. El estudio de los sistemas dinámicos clásicos involucra herramientas de cálculo y geometría diferencial. En cambio los sistemas dinámicos 100% discretos se requiere utilizar herramientas de teoría de números, álgebra, combinatoria y teoría de grafos. Históricamente, los sistemas dinámicos llamados finitos sistemas dinámicos discretos no han recibido en modo alguna atención como la han tenido los sistemas continuos. Hay por supuesto muchas razones para esto, una de las cuales es el uso exitoso de las Ecuaciones Diferenciales Ordinarias (EDO’s) y Ecuaciones Diferenciales Parciales (EDP’s) como herramientas analíticas y descriptivas en las ciencias y sus aplicaciones.

Problemas de corte : métodos exactos y aproximados para formulaciones mono y multi-objetivo

Los problemas de corte y empaquetado son una familia de problemas de optimización combinatoria que han sido ampliamente estudiados en numerosas áreas de la industria y la investigación, debido a su relevancia en una enorme variedad de aplicaciones reales. Son problemas que surgen en muchas industrias de producción donde se debe realizar la subdivisión de un material o espacio disponible en partes más pequeñas. Existe una gran variedad de métodos para resolver este tipo de problemas de optimización. A la hora de proponer un método de resolución para un problema de optimización, es recomendable tener en cuenta el enfoque y las necesidades que se tienen en relación al problema y su solución. Las aproximaciones exactas encuentran la solución óptima, pero sólo es viable aplicarlas a instancias del problema muy pequeñas. Las heurísticas manejan conocimiento específico del problema para obtener soluciones de alta calidad sin necesitar un excesivo esfuerzo computacional. Por otra parte, las metaheurísticas van un paso más allá, ya que son capaces de resolver una clase muy general de problemas computacionales. Finalmente, las hiperheurísticas tratan de automatizar, normalmente incorporando técnicas de aprendizaje, el proceso de selección, combinación, generación o adaptación de heurísticas más simples para resolver eficientemente problemas de optimización. Para obtener lo mejor de estos métodos se requiere conocer, además del tipo de optimización (mono o multi-objetivo) y el tamaño del problema, los medios computacionales de los que se dispone, puesto que el uso de máquinas e implementaciones paralelas puede reducir considerablemente los tiempos para obtener una solución. En las aplicaciones reales de los problemas de corte y empaquetado en la industria, la diferencia entre usar una solución obtenida rápidamente y usar propuestas más sofisticadas para encontrar la solución óptima puede determinar la supervivencia de la empresa. Sin embargo, el desarrollo de propuestas más sofisticadas y efectivas normalmente involucra un gran esfuerzo computacional, que en las aplicaciones reales puede provocar una reducción de la velocidad del proceso de producción. Por lo tanto, el diseño de propuestas efectivas y, al mismo tiempo, eficientes es fundamental. Por esta razón, el principal objetivo de este trabajo consiste en el diseño e implementación de métodos efectivos y eficientes para resolver distintos problemas de corte y empaquetado. Además, si estos métodos se definen como esquemas lo más generales posible, se podrán aplicar a diferentes problemas de corte y empaquetado sin realizar demasiados cambios para adaptarlos a cada uno. Así, teniendo en cuenta el amplio rango de metodologías de resolución de problemas de optimización y las técnicas disponibles para incrementar su eficiencia, se han diseñado e implementado diversos métodos para resolver varios problemas de corte y empaquetado, tratando de mejorar las propuestas existentes en la literatura. Los problemas que se han abordado han sido: el Two-Dimensional Cutting Stock Problem, el Two-Dimensional Strip Packing Problem, y el Container Loading Problem. Para cada uno de estos problemas se ha realizado una amplia y minuciosa revisión bibliográfica, y se ha obtenido la solución de las distintas variantes escogidas aplicando diferentes métodos de resolución: métodos exactos mono-objetivo y paralelizaciones de los mismos, y métodos aproximados multi-objetivo y paralelizaciones de los mismos. Los métodos exactos mono-objetivo aplicados se han basado en técnicas de búsqueda en árbol. Por otra parte, como métodos aproximados multi-objetivo se han seleccionado unas metaheurísticas multi-objetivo, los MOEAs. Además, para la representación de los individuos utilizados por estos métodos se han empleado codificaciones directas mediante una notación postfija, y codificaciones que usan heurísticas de colocación e hiperheurísticas. Algunas de estas metodologías se han mejorado utilizando esquemas paralelos haciendo uso de las herramientas de programación OpenMP y MPI.

Problemas matemáticos sin resolver que cualquier niño puede entender

Un lastre que incide en el rechazo a las matemáticas es su imagen de ser una ciencia inerte, sin nada por descubrir y limitada a unos pocos expertos. Esta charla pretende mostrar que la investigación en matemáticas está muy viva y que cualquiera puede acercarse a ella. Para ello se tratarán algunos problemas muy sencillos de entender (comprensibles para un niño) que los investigadores matemáticos siguen intentando resolver. Se propondrá a los asistentes que jueguen con estos problemas, se explicará cómo resolver algunos casos y se contará la trayectoria histórica de cada problema.

Aplicando programación lineal entera a la búsqueda de conjuntos de productos de prueba priorizados para líneas de productos software

Las líneas de productos software son familias de productos que están íntimamente relacionados entre sí, normalmente formados por combinaciones de un conjunto de características software. Generalmente no es factible testar todos los productos de la familia, ya que el número de productos es muy elevado debido a la explosión combinatoria de características. Por este motivo, se han propuesto criterios de cobertura que pretenden probar al menos todas las interacciones entre características sin necesidad de probar todos los productos, por ejemplo todos los pares de características (emph{pairwise coverage}). Además, es deseable testar primero los productos compuestos por un conjunto de características prioritarias. Este problema es conocido como emph{Prioritized Pairwise Test Data Generation}. En este trabajo proponemos una técnica basada en programación lineal entera para generar este conjunto de pruebas priorizado. Nuestro estudio revela que la propuesta basada en programación lineal entera consigue mejores resultados estadísticamente tanto en calidad como en tiempo de computación con respecto a las técnicas existentes para este problema.

Dos estrategias de búsqueda anytime basadas en programación lineal entera para resolver el problema de selección de requisitos

El problema de selección de requisitos (o Next Release Problem, NRP) consiste en seleccionar el subconjunto de requisitos que se va a desarrollar en la siguiente versión de una aplicación software. Esta selección se debe hacer de tal forma que maximice la satisfacción de las partes interesadas a la vez que se minimiza el esfuerzo empleado en el desarrollo y se cumplen un conjunto de restricciones. Trabajos recientes han abordado la formulación bi-objetivo de este problema usando técnicas exactas basadas en resolutores SAT y resolutores de programación lineal entera. Ambos se enfrentan a dificultades cuando las instancias tienen un gran tamaño, sin embargo la programación lineal entera (ILP) parece ser más efectiva que los resolutores SAT. En la práctica, no es necesario calcular todas las soluciones del frente de Pareto (que pueden llegar a ser muchas) y basta con obtener un buen número de soluciones eficientes bien distribuidas en el espacio objetivo. Las estrategias de búsqueda basadas en ILP que se han utilizado en el pasado para encontrar un frente bien distribuido en cualquier instante de tiempo solo buscan soluciones soportadas. En este trabajo proponemos dos estrategias basadas en ILP que son capaces de encontrar el frente completo con suficiente tiempo y que, además, tienen la propiedad de aportar un conjunto de soluciones bien distribuido en el frente objetivo en cualquier momento de la búsqueda.