Generating hard SAT/CSP instances using expander graphs

In this paper we provide a new method to generate hard k-SAT instances. We incrementally construct a high girth bipartite incidence graph of the k-SAT instance. Having high girth assures high expansion for the graph, and high expansion implies high resolution width. We have extended this approach to generate hard n-ary CSP instances and we have also adapted this idea to increase the expansion of the system of linear equations used to generate XORSAT instances, being able to produce harder satisfiable instances than former generators.

Edge matching puzzles as hard SAT/CSP benchmarks

Recently, edge matching puzzles, an NP-complete problem, have rececived, thanks to money-prized contests, considerable attention from wide audiences. We consider these competitions not only a challenge for SAT/CSP solving techniques but also as an opportunity to showcase the advances in the SAT/CSP community to a general audience. This paper studies the NP-complete problem of edge matching puzzles focusing on providing generation models of problem instances of variable hardness and on its resolution through the application of SAT and CSP techniques. From the generation side, we also identify the phase transition phenomena for each model. As solving methods, we employ both; SAT solvers through the translation to a SAT formula, and two ad-hoc CSP solvers we have developed, with different levels of consistency, employing several generic and specialized heuristics. Finally, we conducted an extensive experimental investigation to identify the hardest generation models and the best performing solving techniques.

Artificial diets for the production of natural enemies (predators and parasitoids) of greenhouse pest insects

The aim of this contract was to finalise in vitro rearing on artificial diets of entomophagous insects useful to control insect pests mainly in greenhouses through an analytical and rational approach. The work focuses on the development and optimisation of artificial diets for one coccinellid (Harmonia axyridis), two heteropteran predators (Orius laevigatus, Dicyphus tamaninii), and a braconid parasitoid of aphids (Aphidius ervi). The definition of the artificial diets was based on biochemical analyses of their natural food (aphids) or substitution food for the predators (Ephestia kuehniella eggs). Reliable quality control parameters of the entomophages produced were used in order to adjust dietary composition and formulation of the different diets tested.

Codificación a nivel de paquete para comunicaciones móviles por satélite

Una de les opcions que es contemplen per transmetre continguts multimèdia i proporcionar accés a Internet a grups de usuaris mòbils és fer servir satèl·lits. Les condiciones de propagació del canal mòbil impliquen que d'una manera o altra haurem de garantir la qualitat de servei. Això té fins i tot més importància si tenim en compte que, en el cas d'accés a Internet, no es té la capacitat d'assumir cert percentatge de pèrdua de dades que tenim, per exemple, en la transmissió de so o vídeo (rebaixant la qualitat). Entre les principals alternatives per a aquesta classe d’entorns es troba la inclusió de codificacions a nivell de paquet. El funcionament d'aquesta tècnica es basa en incloure a la transmissió paquets redundants, obtinguts mitjançant un determinat algoritme. El receptor podrà recuperar la informació original que es volia enviar, sempre que hagi rebut una certa quantitat de paquets, similar a la quantitat de paquets originals. A aquest mecanisme se'l coneix com Forward Error Correction (FEC) a nivell de paquet. En aquesta memòria es valoren breument les alternatives existents i s'expliquen algunes de les codificacions per a FEC més importants. A continuació es realitza un estudi compartiu d’algunes d'elles: les variants de LDPC (Low Density Parity Check) conegudes com LDGM (Low Density Generator Matrix), i la codificació Raptor

L'albedo lunar i els satèl·lits: Recerca sobre els efectes de l'albedo lunar en les plaques solars d'un satèl·lit artificial que orbita al voltant de la Lluna

Treball de recerca realitzat per una alumna d'ensenyament secundari i guardonat amb un Premi CIRIT per fomentar l'esperit científic del Jovent l'any 2009. L’albedo lunar i els satèl•lits és un treball que relaciona l’enginyeria aeroespacial amb l’astronomia. El seu objectiu principal investigar si l’albedo lunar, els rajos de sol reflectits a la superfície lunar, pot modificar significativament la temperatura de les plaques solars d’un satèl•lit artificial que orbiti la Lluna i, en conseqüència, afectar-ne el rendiment. El segon objectiu del treball és calcular si seria possible fer un mapa d’albedo lunar, a partir de la temperatura d’un satèl•lit en òrbita al voltant de la Lluna, que permetria conèixer amb més precisió la composició de la superfície lunar. Després d’adquirir els fonaments teòrics necessaris per a realitzar el treball, del procés per a trobar la manera de dur a terme els càlculs i d’efectuar els càlculs en si, les conclusions del treball són que l’albedo lunar causa un augment de temperatura en els satèl•lits prou significatiu per afectar-ne el rendiment; i que amb les temperatures enregistrades per un satèl•lit en òrbita al voltant de la Lluna es podria crear un mapa d’albedo. Aquesta recerca ha estat feta per suggeriment i sota la supervisió del CTAE (Centre de Tecnologia Aeroespacial) per analitzar si els resultats són aplicables al satèl•lit que s’enviarà a la Lluna, Lunar Mission BW1.

Soporte geoespacial para modelos de distribución de especies (I): generalización del mapa de vegetación del Montseny apoyada en información de imágenes de satélite

Los mapas de vegetación son a menudo utilizados como proxis de una estratificación de hábitats para generar distribuciones geográficas contínuas de organismos a partir de datos discretos mediante modelos multi-variantes. Sin embargo, los mapas de vegetación suelen ser poco apropiados para ser directamente aplicados a este fin, pues sus categorías no se concibieron con la intención de corresponder a tipos de hábitat. En este artículo presentamos y aplicamos el método de Agrupamiento por Doble Criterio para generalizar un mapa de vegetación extraordinariamente detallado (350 clases) del Parque Natural del Montseny (Cataluña) en categorías que mantienen la coherencia tanto desde el punto de vista estructural (a través de una matriz de disimilaridad espectral calculada mediante una imágen del satélite SPOT-5) como en términos de vegetación (gracias a una matriz de disimilaridad calculada mediante propiedades de vegetación deducidas de la leyenda jerárquica del mapa). El método simplifica de 114 a 18 clases el 67% del área de estudio. Añadiendo otras agregaciones más triviales basadas exclusivamente en criterios de cubierta de suelo, el 73% del área de estudio pasa de 167 a 25 categorías. Como valor añadido, el método identifica el 10% de los polígonos originales como anómalos (a partir de comparar las propiedades espectrales de cada polígono con el resto de los de su clases), lo que implica cambios en la cubierta entre las fechas del soporte utilizado para generar el mapa original y la imagen de satélite, o errores en la producción de éste.

La intel·ligència artificial i la seva aplicació a l'ensenyament

L'objectiu fonamental d'aquest article és mostrar com les técniques desenvolupades en intel'ligéncia artificial (lA) són d'una gran utilitat per tal de millorar el software destinat a I'ambit educatiu. Per a aixó, en primer Iloc, s'hi fa un breu resum de les finalitats i els objectius generals de les investigacions en lA realitzades fins al moment. Posteriorment, es descriuen les diferents aplicacions de la lA en I'educació dirigides als alumnes en tasques formatives i instructives, i als professors en tasques de disseny i planificació de les activitats docents. L'article acaba amb una reflexió sobre les tendéncies futures de la lA aplicada a I'educació.

Bases boquímicas de resistencia a Penicillium expansum en manzana "golden delicious"

La producción frutícola española es muy importante y los problemas relacionados con su conservación, sobre todo desde la entrada de España en la UE, tienen un interés peculiar con el objetivo de mejorar la calidad y disminuir el uso de los productos susceptibles de perjudicar la salud humana. Para conseguir avances importantes en el aspecto tecnológico se precisa una profundización en los fenómenos bioquímicos que determinan las capacidades de conservación del fruto. Dentro de la complejidad de esta temática, este proyecto pretende determinar los factores bioquímicos involucrados en el control de podredumbres en la fruta y más específicamente los factores endógenos que determinan la resistencia del fruto a este tipo de daños. El objetivo general de este proyecto era de definir los mecanismos bioquímicos involucrados en la resistencia de la manzana ‘Golden Delicious’ contra la acción de un patógeno: Penicillium expansum. Para lograr este objetivo se plantearon las diferentes tareas: Tarea 1 (T1): determinación de madurez y del estado fisiológico a la cosecha Tarea 2 (T2): determinación de las capacidades de resistencia endógenas iniciales e influencia del estado de madurez a la cosecha Tarea 3 (T3): respuesta inicial a una inoculación artificial: cambios bioquímicos y sensibilidad al patógeno Tarea 4 (T4): comportamiento después de conservación: respuesta a una inoculación (cambios bioquímicos y sensibilidad al patógeno) y sensibilidad natural durante la conservación Tarea 5 (T5): determinación de un esquema explicativo y caracterización de los factores bioquímicos determinantes Tarea 6 (T6): elaboración de un test de predicción.

Modelo de pérdida de paquetes para redes híbridas

El objetivo de este proyecto es la predicción de la pérdida de paquete. Para ello necesitaremos el modelado del canal. De esta manera, podremos determinar cuando una transmisión llega con éxito o no. En primer lugar, se han estudiado los algoritmos de adaptación de la tasa. Estos algoritmos mejoran el rendimiento de la comunicación. Por este motivo, el programa de simulación se basa en algunos de estos algoritmos. En paralelo, se han capturado medidas del canal terrestre para realizar el modelado. Finalmente, con un programa mucho más completo se ha simulado el comportamiento de una transmisión con el modelado del canal físico, y se han asumido algunas consideraciones, como las colisiones. Por lo tanto, se ha obtenido un resultado más realista, con el cual se ha analizado teóricamente las posibilidades de un enlace entre el canal terrestre y el canal satélite, para crear una red híbrida.

Indexació de continguts televisius: anàlisis de vídeo

Aquest és un projecte que tracta sobre la indexació automàtica de continguts televisius. És una tasca que guanyarà importància amb els imminents canvis que hi haurà en la televisió que coneixem. L'entrada de la nova televisió digital farà que hi hagi una interacció molt més fluida entre l'espectador i la cadena, a més de grans quantitats de canals, cada un amb programes de tipus totalment diferents. Tot això farà que tenir mètodes de cerca basats en els continguts d'aquests programes sigui del tot imprescindible. Així doncs, el nostre projecte està basat plenament en poder extreure alguns d'aquests descriptors que faran possible la categorització dels diferents programes televisius.

Indexació de continguts televisius: anàlisi de so

Aquest és un projecte sobre la indexació de continguts televisius; és a dir, el procés d’etiquetatge de programes televisius per facilitar cerques segons diferents paràmetres. El món de la televisió està immers en un procés d'evolució i canvis gràcies a l'entrada de la televisió digital. Aquesta nova forma d'entendre la televisió obrirà un gran ventall de possibilitats i permetrà la interacció entre usuaris i emissora. El primer pas de la gestió de continguts consisteix en la indexació dels programes segons el contingut. Aquest és el nostre objectiu. Indexar els continguts televisius de manera automàtica mitjançant la intelligència artificial.

Aplicació de la tecnologia RFID a les cadenes de subministrament: estudi de viabilitat

El present treball és un projecte d'aplicació de la tecnologia RFID a les cadenes de subministrament per tal de millorar-ne la gestió interna i d'augmentar l'eficiència i la productivitat de les empreses d'aquest sector.

Programación de un robot autónomo: diseño, construcción, programación e integración de un robot autónomo en el entorno Pyro

En aquest projecte, s'ha dissenyat, construït i programat un robot autònom, dotat de sistema de locomoció i sensors que li permeten navegar sense impactar en un entorn controlat. Per assolir aquests objectius s'ha dissenyat i programat una unitat de control que gestiona el hardware de baix volum de dades amb diferents modes d'operació, abstraient-lo en una única interfície. Posteriorment s'ha integrat aquest sistema en l'entorn de robòtica Pyro. Aquest entorn permet usar i adaptar, segons es necessiti, eines d'intel·ligència artificial ja desenvolupades.

Diseño cooperativo de un sistema de comunicaciones por satélite basado en diversidad espacial

En este proyecto se han presentado los modelos de distribución de canal más comunes que se puede encontrar una señal en una transmisión. Seguidamente se ha presentado el concepto de diversidad en comunicaciones inalámbricas terrestres y se ha trasladado el escenario a comunicaciones por satélite. Para analizar la calidad de los enlaces con diversidad se ha realizado un simulador, con Matlab, que modele la estructura básica de un sistema de comunicaciones (emisor, canal y receptor). Simulando las comunicaciones entre los diferentes sistemas de diversidad se ha podido comparar la calidad de cada enlace. El modelo Alamouti ha presentado una robustez y una baja probabilidad de error que hacen que sea la mejor elección a la hora de diseñar un sistema de diversidad para comunicaciones por satélite. Utiliza la diversidad de canal para aprovechar cada pizca de señal que recibe y así poder descifrar el mensaje enviado.