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.

Statistical mechanics of multi-edge networks

Statistical properties of binary complex networks are well understood and recently many attempts have been made to extend this knowledge to weighted ones. There are, however, subtle yet important considerations to be made regarding the nature of the weights used in this generalization. Weights can be either continuous or discrete magnitudes, and in the latter case, they can additionally have undistinguishable or distinguishable nature. This fact has not been addressed in the literature insofar and has deep implications on the network statistics. In this work we face this problem introducing multiedge networks as graphs where multiple (distinguishable) connections between nodes are considered. We develop a statistical mechanics framework where it is possible to get information about the most relevant observables given a large spectrum of linear and nonlinear constraints including those depending both on the number of multiedges per link and their binary projection. The latter case is particularly interesting as we show that binary projections can be understood from multiedge processes. The implications of these results are important as many real-agent-based problems mapped onto graphs require this treatment for a proper characterization of their collective behavior.

Characterization of Mechanically Alloyed Nanocrystalline Fe(Al): Crystallite Size and Dislocation Density

A nanostructured disordered Fe(Al) solid solution was obtained from elemental powders of Fe and Al using a high-energy ball mill. The transformations occurring in the material during milling were studied with the use of X-ray diffraction. In addition lattice microstrain, average crystallite size, dislocation density, and the lattice parameter were determined. Scanning electron microscopy (SEM) was employed to examine the morphology of the samples as a function of milling times. Thermal behaviour of the milled powders was examined by differential scanning calorimetry (DSC). The results, as well as dissimilarity between calorimetric curves of the powders after 2 and 20 h of milling, indicated the formation of a nanostructured Fe(Al) solid solution

Free and fragmenting filling length

The filling length of an edge-circuit η in the Cayley 2-complex of a finite presentation of a group is the minimal integer length L such that there is a combinatorial null-homotopy of η down to a base point through loops of length at most L. We introduce similar notions in which the full-homotopy is not required to fix a base point, and in which the contracting loop is allowed to bifurcate. We exhibit a group in which the resulting filling invariants exhibit dramatically different behaviour to the standard notion of filling length. We also define the corresponding filling invariants for Riemannian manifolds and translate our results to this setting.

Fabricació de Lents Zonals de Fresnel per aplicació als raigs X tous

Estudi elaborat a partir d’una estada al Paul Scherrer Institut del Maig a l’Octubre del 2006 amb l’ajuda i supervisió dels Dr. Konstantins Jefimovs i Dr. Christian David. Focalitzar raigs X tous és una necessitat essencial per al microanàlisis, la microscopia, i fer imatges en moltes Instal·lacions de Radiació Sincrotró. Les Lents Zonals de Fresnel (FZP, de la denominació anglesa “Fresnel Zone Plates”) han demostrat donar uns punts focals amb una resolució espacial destacada i una baixa il·luminació de fons. Tanmateix, la fabricació de FZP és complexa i no totalment reproduïble. A més a més, el temps de vida de les FZP és força curt, ja que estant situades sobre membranes de nitrur de silici molt fines i altament absorbents. Per tant, hem fet esforços per implementar FZP de silici, que s’espera que siguin més resistents. L’element està fet d’una oblia de cristall de silici poc absorbent, i no presenta cap interfase entre materials. Així doncs, aquestes lents són especialment adequades per a aguantar les extremes càrregues de radiació de les fonts de raigs X més brillants. Particularment, això és molt important per a les aplicacions a les pròximes generacions de fonts de raigs X, com els Làsers d’Electrons Lliures (FEL, de la denominació anglesa “Free Electron Laser”). El silici també garanteix que no hi hagi cap banda d’absorció en el rang d’energies de la finestra de l’aigua (200-520 eV), fent aquestes lents ideals per a fer imatges de mostres biològiques. En aquest informe, hi ha una descripció detallada de tots els passos involucrats en la fabricació de les Lents Zonals de Fresnel de silici. En resum, les estructures de FZP es modelen sobre una resina utilitzant litografia per feix d’electrons i llavors el patró es transmet al silici mitjançant un gravat d’ions reactius (RIE, de la denominació anglesa ‘Reactive Ion Etching’) utilitzant una fina (20 nm) màscara de Crintermitja. Les membranes de silici es poden aprimar després de la fabricació de les estructures per a garantir una transmissió suficient fins i tot a baixes energies. Aquest informe també inclou l’anàlisi i la discussió d’alguns experiments preliminars per avaluar el rendiment de les Si FZPs fets a la línia de llum PolLux del Swiss Ligth Source amb l’ajuda dels Dr. Jörg Raabe i Dr. George Tzvetkov.

Clúster creatius en entorns urbans: 22@Bcn i Shoreditch East London

La localització de les empreses de nova economia en zones urbanes, a pesar que el factor distància no sigui important, no deixa de ser considerable pels seus avantatges que els suposa estar situades conjuntament en relació amb les infraestructures, consum, beneficis socioculturals, i facilitat en les transaccions cara a cara. És inevitable que el primer quart del segle vint-i-un estigui lligat a l’economia creativa de forma similar amb que el començament del segle vint estava íntimament lligat a l’economia industrial i la invenció del sistema de producció en massa. La ciutat també va jugar un dels papers més importants per al desenvolupament de “la nova economia industrial” a les albors del segle vint, com ho és la ciutat del coneixement que acull “la nova economia creativa” al segle vint-i-un. És evident que els resultats morfològics, socials, econòmics i urbans són ben diferents en ambdós fenòmens, però l’impacte a les ciutats és molt gran. L’objectiu d’aquest estudi és analitzar els mecanismes d’aglomeració (clustering) d’activitats competitives basades en creació de coneixement i de serveis avançats que estan al darrera de desenvolupaments punters a ciutats com Barcelona, el projecte 22@bcn, i East London, el projecte Shoreditch. L’esforç que han posat les autoritats locals en crear l’entorn apropiat per atreure i crear empreses innovadores, com a motor de desenvolupament d’algunes ciutats modernes europees ha resultat en el sorgiment de nuclis o centres urbans molt dinàmics que suposadament estan preparats i acullen punts de creació de coneixement (“Urban Knowledge Hubs”), amb una demanda i llocs de treball altament qualificats. Aquest és el cas dels projectes de Barcelona (22@bcn) i East London (Shoreditch).

Deconstructing Purism: Unconscious Drives and Meta-argumentation in Straight Photography

The thesis investigates the nature of the Purist discourse in photography, with the aim of unveiling its lack of a solid theoretical foundation and its unconscious content. Purism outlines the fact that photography is a unique craft, that may not borrow ideas from painting or any other art forms. What makes the Purist discourse suspect and attracts attention to its possible circular style? The fact that the views expressed by its supporters include a frenzied edge, an unnecessary ardor, a combative tone that discloses that there’s something hidden, something that doesn’t serve the purpose of presenting an unbiased philosophical claim

Desenvolupament d'un videojoc en 3D

La industria de los videojuegos crece exponencialmente y está ya superando a otras industrias punteras del ocio. En este proyecto, nos hemos planteado la realización de un videojuego con visualización en el espacio real 3D. Para la realización del videojuego se ha usado el siguiente software: Blender para diseñar los modelos 3D, C++ como lenguaje de programación para desarrollar el código y un conjunto de librerías básicas para desarrollar un videojuego llamadas Ogre3d (Motor Gráfico). La lógica del movimiento 3D y los choques entre las partículas del juego ha sido diseñada enteramente en este proyecto acorde con las necesidades del videojuego, y de forma compatible a los ficheros de Blender y a las librerías OGRE3D.

Análisis de prestaciones de procesadores multi-core y multi-thread

Los procesadores multi-core y el multi-threading por hardware permiten aumentar el rendimiento de las aplicaciones. Por un lado, los procesadores multi-core combinan 2 o más procesadores en un mismo chip. Por otro lado, el multi-threading por hardware es una técnica que incrementa la utilización de los recursos del procesador. Este trabajo presenta un análisis de rendimiento de los resultados obtenidos en dos aplicaciones, multiplicación de matrices densas y transformada rápida de Fourier. Ambas aplicaciones se han ejecutado en arquitecturas multi-core que explotan el paralelismo a nivel de thread pero con un modelo de multi-threading diferente. Los resultados obtenidos muestran la importancia de entender y saber analizar el efecto del multi-core y multi-threading en el rendimiento.

Statmedia 3 : activitats on-line individualitzades d'estadística i matemàtiques als ensenyaments de Ciències Experimentals i Socials

El projecte Statmedia 3 ha consolidat definitivament la proposta de les assignatures Bioestadística de Biologia, Anàlisi de dades de Ciències Ambientals i d’Estadística Matemàtica de la Diplomatura renovant una part del material creat amb Statmedia 2. S’han inclòs a més Matemàtiques d’Ambientals i Introducció a la Probabilitat del Grau d’Estadística. L’anterior MQD abastava només pràctiques mentre que aquest projecte permet una oferta diversa d’activitats individualitzades. La individualització consisteix en que cada estudiant rep una proposta de cas personalitzada amb dades diferents. Les activitats poden ser programades presencialment o no, però la clau de l’èxit de l’activitat és que l’alumne obtingui reconeixement del seu treball en l’avaluació continuada. La valoració que fan als alumnes de Statmedia és molt bo, i observem que es produeix una millora en els resultats acadèmics. Statmedia 3 ha implicat un important esforç en la vessant informàtica del projecte, la barreja de tecnologies que utilitzem son punteres: Ajax, servlets i applets Java... Hem posat a punt un assistent on-line per dissenyar documents i planificar activitats que facilita la tasca dels professors. La nostre participació en primera línea del procés de convergència a l’EEES ens ha permès anticipar alguns canvis, i s’ha traduït en que el claustre del Departament d’Estadística assumís que Statmedia és una metodologia essencial dels seus plans docents. El projecte continua en un quart projecte MQD consecutiu, on desplegarem la nova tecnologia implementada. L’objectiu principal serà dotar a les assignatures dels 7 graus on participa el departament d’activitats individualitzades en forma de casos pràctics, problemes i proves diverses. La col·lecció de material emmagatzemada en la nostra biblioteca, forjada després de quasi deu anys de treball continuat, juntament amb l’experiència acumulada de com utilitzar Statmedia de la forma més eficient han començat a ser explotades en els nous graus aquest mateix curs 2009-2010.

A linear optimization technique for graph pebbling

Graph pebbling is a network model for studying whether or not a given supply of discrete pebbles can satisfy a given demand via pebbling moves. A pebbling move across an edge of a graph takes two pebbles from one endpoint and places one pebble at the other endpoint; the other pebble is lost in transit as a toll. It has been shown that deciding whether a supply can meet a demand on a graph is NP-complete. The pebbling number of a graph is the smallest t such that every supply of t pebbles can satisfy every demand of one pebble. Deciding if the pebbling number is at most k is NP 2 -complete. In this paper we develop a tool, called theWeight Function Lemma, for computing upper bounds and sometimes exact values for pebbling numbers with the assistance of linear optimization. With this tool we are able to calculate the pebbling numbers of much larger graphs than in previous algorithms, and much more quickly as well. We also obtain results for many families of graphs, in many cases by hand, with much simpler and remarkably shorter proofs than given in previously existing arguments (certificates typically of size at most the number of vertices times the maximum degree), especially for highly symmetric graphs. Here we apply theWeight Function Lemma to several specific graphs, including the Petersen, Lemke, 4th weak Bruhat, Lemke squared, and two random graphs, as well as to a number of infinite families of graphs, such as trees, cycles, graph powers of cycles, cubes, and some generalized Petersen and Coxeter graphs. This partly answers a question of Pachter, et al., by computing the pebbling exponent of cycles to within an asymptotically small range. It is conceivable that this method yields an approximation algorithm for graph pebbling.

Nanotermoparells: heterounions de nanowires

Projecte de recerca elaborat a partir d’una estada a la University of California a Irvine, EEUU, entre juliol del 2007 i gener del 2008. Els termoparells són actualment els sensors de temperatura més populars i més utilitzats per a un ampli rang d’aplicacions: industrials, domèstiques, etc. Aconseguir miniaturar els dispositius fins a dimensions extremadament petites obra un ampli rang de noves aplicacions per aquests dispositius, per exemple, en el camp de la tecnologia lab-on-a-chip. En aquesta investigació, el concepte de termoparell, és a dir, dos cables de diferent metall connectats per un extrem s’ha extrapolat a l’escala nanomètrica, utilitzant nanowires com a element de construcció. Aquests nanowires s’han sintetitzat a través d’un nou procediment desenvolupat en el grup d’investigació de la Universitat de California, Irvine, que ha permès treballar amb nanowires de diferents dimensions (control independent de l’alçada i amplada) i un major grau d’èxit en la fabricació d’aquests termometres. El mètode també permet dipositar aquestes nanoestructures sobre substractes no conductors de manera controlable, simplificant notablement tot el procés de fabricació. L’obtenció d’aquests dispositius ha permès demostrar que, a part de ser bons sensors de temperatura a nivell macroscòpic (fonts de calor ambientals), també permet la determinació de temperatura a nivell microscòpic (fonts de calor focalitzada, com és el cas de feixos làser). Per a la seva caracterització ha estat necessari l’ús de tecnologia puntera (làsers, amplificadors, microscopis de forces atòmiques) i inclòs el disseny de nous dispositius. Aquests nanotermoparells presenten propietats extraordinàries, com una gran sensitivitat, gran velocitat de resposta a estímuls tèrmics, i un comportament estable vers l’ús i el temps.

Diseño integral de plataforma de virtualización

L'objectiu d'aquest projecte és el disseny, raonat i recolzat en dades objectives, d'una plataforma de virtualització basada en VMWARE ESXi (versió gratuïta de VMWARE), orientada al segment d'empreses i organitzacions que per la seva grandària podrien beneficiar-se d'un entorn de servidors virtualizados però que pel seu pressupost no poden accedir a tecnologies capdavanteres d'implantació.

Label Space Reduction in MPLS Networks: How Much Can A Single Stacked Label Do?

Most network operators have considered reducing LSR label spaces (number of labels used) as a way of simplifying management of underlaying virtual private networks (VPNs) and therefore reducing operational expenditure (OPEX). The IETF outlined the label merging feature in MPLS-allowing the configuration of multipoint-to-point connections (MP2P)-as a means of reducing label space in LSRs. We found two main drawbacks in this label space reduction a)it should be separately applied to a set of LSPs with the same egress LSR-which decreases the options for better reductions, and b)LSRs close to the edge of the network experience a greater label space reduction than those close to the core. The later implies that MP2P connections reduce the number of labels asymmetrically

Contrapuntos de la invención

Un instrumento musical implica la presencia de un registro sonoro que afecta tanto a la organización de los sonidos, silencios y ruidos, como a la disposición corporal que con él se va forjando. Desde esta consideración, la organización de la música llevada a cabo con las tecnologías eléctricas y electrónicas supone una profunda modificación de ambos aspectos. La llegada de la electricidad implica una tripledislocación: respecto a la transmisión de lo sonoro, a su posibilidad de reproducción y a la escucha. Estas dislocaciones son puestas en relación con invenciones que, desde el órgano de Ctesibios hasta el clavecín ocular de Castel, nos dibujan un marco en el que música, técnica, sensibilidad y sistemaeconómico-social, tejen sus nexos. A lo largo de este recorrido se trazan lo que se ha denominado contrapuntos de la invención, que pueden tomar en las figuras de J.S. Bach y de J. Cage sus ejemplos más prominentes