El flujo desbordado en secciones de ríos con llanuras de inundación (secciones compuestas) presenta fuertes fenómenos tridimensionales que lo diferencian del flujo confinado en el cauce principal (asimilable a secciones simples). Estos fenómenos hacen que la modelación del flujo desbordado sea más compleja, y que los resultados obtenidos con los métodos clásicos de cálculo no representen adecuadamente la realidad. La diferencia de calado y de rugosidad entre el cauce principal y las llanuras provoca que las velocidades en las llanuras sean diferentes que las del cauce. Este gradiente de velocidad genera una capa de corte en la línea imaginaría que separa las zonas de cauce y llanuras, a través de la cual se produce una transferencia de cantidad de movimiento (momentum) entre ambas zonas. En el caso de cauces de planta recta (cauces prismáticos), la transferencia es debida únicamente a la tensión de interacción entre las masas fluidas de diferente velocidad, y en el caso de cauces de planta meandriforme, el intercambio de caudal entre cauce y llanuras y el ángulo que forman las direcciones del flujo entre ambos son otros factores que hay que tener en cuenta. Tradicionalmente, la capacidad de las secciones compuestas se ha calculado adaptando los métodos utilizados en secciones simples a las diferencias de calado y rugosidad. Entre los años 1980-2000 se demostró experimentalmente que estos métodos no dan buenos resultados, especialmente cuando la rugosidad de las llanuras es mucho mayor que la del cauce principal, y se desarrollaron nuevos métodos de cálculo. En cauces rectos, el Método de la Fuerza de Interacción, Apparent Shear Force Method (ASFM) en inglés, es el método más estudiado. En el ASFM es necesario calcular la tensión de interacción en la línea vertical de separación entre el cauce y las llanuras (Figura 1). Muchos autores han estimado esta tensión con fórmulas empíricas que son válidas únicamente para la geometría para la cual fueron deducidas En el presente trabajo se propone una formulación generalizada, basada en la hipótesis de la longitud de mezcla de Prandtl, para estimar la tensión de interacción entre cauce y llanura en cauces prismáticos. Esta formulación depende del gradiente de velocidades al cuadrado y de un coeficiente de fricción entre superficies de agua, llamado coeficiente aparente de fricción (apparent friction coefficient en inglés) o coeficiente de interacción. El coeficiente aparente de fricción ha sido calibrado y validado con datos de tensiones de diversos autores La nueva formulación propuesta para la tensión de interacción se ha aplicado al cálculo uni-dimensional usando el método de la fuerza de interacción, Apparent Shear Force Method en inglés (ASFM). La comparación de los resultados con datos de canales de gran escala, el FCF (Flood Channel Facility), y de pequeña escala demuestran la validez y precisión del método para una gran variedad de geometrías. Otros métodos de cálculo, como los métodos tradicionales de separación en zonas, Divided Channel Method en inglés (DCM) o de sección completa, Single Channel Method en inglés (SCM) y los nuevos métodos desarrollados en los últimos años, el método de la Coherencia, Coherence Method (COHM), el método de divisiones promediadas, Weighted Divided Channel Method (WDCM), el método del intercambio de caudales, Exchange Discharge Method (EDM), y el método de separación con interacción, Interacting Divided Channel Method (IDCM), se han aplicado al cálculo unidimensional y se han comparado entre sí en términos de caudal total y de distribución de caudales entre cauce y llanuras. Se mostrarán las ventajas e inconvenientes de cada método en cuanto a ajuste con los datos, sencillez de aplicación y fundamento físico del método. En el caso de cauces naturales donde la geometría en planta es meandriforme, el problema se complica. Se han analizado algunos aspectos de este tipo de flujo, especialmente cuando las llanuras son más rugosas que el cauce, y se ha mostrado la importancia de fuentes de pérdidas como las debidas a la transferencia de caudal y a la interacción turbulenta. El flujo desbordado en cauces meandriformes es marcadamente tridimensional y los métodos tradicionales de cálculo dan errores mayores que en los cauces rectos. En esta tesis se ha generalizado un nuevo método que tiene en cuenta la transferencia de caudal entre el cauce y las llanuras y las tensiones de interacción entre ambas zonas. Este método, que propone una separación vertical entre el cauce y las llanuras, presenta mejoras respecto a los métodos tradicionales, especialmente en el caso de cauces meandriformes con llanuras más rugosas. Se ha demostrado que en estos casos la separación vertical representa mejor la realidad que la separación horizontal. Finalmente, se han utilizado modelos numéricos en una, dos y tres dimensiones para simular el flujo desbordado en canales con datos disponibles y se ha comprobado la influencia de la condición de contorno en el resultado final. Las nuevas formulaciones presentadas para cauces rectos y meandriformes permiten mejorar la estimación de las condiciones de contorno que son habituales en los modelos numéricos, respecto a los métodos tradicionalmente usados que no tienen en cuenta la interacción entre el cauce y las llanuras. / This thesis deals with the interaction between main channel and floodplain flows during overbank in rivers with a compound section. In straight compound channel the interaction is mainly due to the turbulent shear stress between fluid masses with different velocity, but in meandering compound channels the mass exchange between main channel and floodplains has also to be considered. The present thesis summarizes the most important experimental data of apparent shear stress available in straight compound channels, covering a wide range of geometries, scales and roughness distributions. A dimensionally sound formula has been followed for estimating the apparent shear stress. The formula is depending on the square of the velocity gradient between the main channel and the floodplain and on the "apparent friction coefficient". The influence of cross-section geometry, asymmetry and roughness on the variation of the apparent friction coefficient has been studied, and a more general formula for estimating this coefficient has been developed, being calibrated from the laboratory data, which include small-scale flumes and the FCF, with smooth or rough floodplains and with rigid or mobile bed in the main channel. The formulae proposed are valid for small scale flumes and for large scale laboratory channels but it is necessary to point out the likely dependence on the scale. The new formulation has been applied to one-dimensional computation by using the ASFM. The results have been compared with experimental data from large channels, FCF, and small channels, showing the validity and accuracy of the ASFM for a wide variety of geometries. Traditional methods, like Single Channel Method (SCM) and Divided Channel Method (DCM), and new methods, like Coherence Methods (COHM), Weighted Divided Channel Method (WDCM), Exchange Discharge Method (EDM) and Interacting Divided Channel Method (IDCM), have been applied to the same data and the performance of these methods have been investigated in terms of total discharge and its distribution between the main channel and floodplains. In natural rivers the main channel usually meanders across the floodplains and the flow interaction is more complicated. In this thesis the overbank flow in a sinuous channel with floodplains has been also investigated, focusing on the effect of floodplain vegetation on different aspects of flow. The available data of the scale model of the Besós River has given the opportunity of working with roughness elements which simulate the natural vegetation of rivers. A complete analysis about the depth-averaged velocity distribution, the discharge distribution and the momentum balance between the main channel and floodplains have been presented. The effects of floodplain roughness (which is flexible vegetation) on discharge distribution and momentum balance have been also investigated. This advances in the compound sinuous channel flow have also been used to generalize a 1D model based on the momentum equation (Martín-Vide and López-Querol, 2004), which include new terms for the interaction between main channel and floodplains. For these terms a closure is presented so that this friction force is expressed in terms of depth and velocity gradients with the aid of one single coefficient (k), which is used throughout the tests. Finally, this thesis also attempts to compare the accuracy of one-dimensional (1D), two-dimensional (2D) depth-averaged and three-dimensional (3D) codes in the numerical simulation of free surface flows in compound open channels. Assessment was conducted using benchmark data collected from a straight compound channel at the UK EPSRC Flood Channel Facility (FCF) and the sinuous compound channel at the Besós river model. Assessment of the codes has been based on the prediction of water surface elevations and depth-averaged velocity traverses at the middle section of the straight channel and at around a meander bend for the sinuous channel.

The evolution of constraint based geometric models is tightly tied to parametric and feature-based Computer-Aided Design (CAD) systems. Since the introduction of parametric design by Pro/Engineer in the 1980's, most major CAD systems adopted constraint based geometric models as a core technology. Constraint based geometric models allowed CAD systems to provide a more powerful data model while offering an intuitive user interface. Later on, the same models also found application to fields like linkage design, chemical modeling, computer vision and dynamic geometry. Constraint based geometric models are unevaluated models. A key problem related to constraint based geometric models is the geometric constraint based solving problem which, roughly speaking, can be stated as the problem of evaluating a constraint based model. Among the different approaches to geometric constraint solving, we are interested in graph-based Decomposition-Recombination solvers. In the graph-based constructive approach, the geometric problem is first translated into a graph whose vertices represent the set of geometric elements and whose edges are the constraints. Then the constraint problem is solved by decomposing the graph into a set of sub-problems, each sub-problem is recursively divided until reaching basic problems which are solved by a dedicated equational solver. The solution to the initial problem is computed by merging the solutions to the sub-problems. The approach used by DR-solvers has been particularly successful when the decomposition into subproblems and subsequent recombination of solutions to these subproblems can be described by a plan generated a priori, that is, a plan generated as a preprocessing step without actually solving the subsystems. The plan output by the DR-planner remains unchanged as numerical values of parameters change. Such a plan is known as a DR-plan and the unit in the solver that generates it is the DR-planner. In this setting, the DR-plan is then used to drive the actual solving process, that is, computing specific coordinates that properly place geometric objects with respect to each other. In this thesis we develop a new DR-planner algorithm for graph-constructive two dimensional DR-solvers. This DR-planner is based on the tree-decomposition of a graph. The triangle- or tree-decomposition of a graph decomposes a graph into three subgraphs such that subgraphs pairwise share one vertex. Shared vertices are called hinges. The tree-decomposition of a geometric constraint graph is in some sense the construction plan that solves the corresponding problem. The DR-planner algorithm first transforms the input graph into a simpler, planar graph. After that, an specific planar embedding is computed for the transformed graph where hinges, if any, can be straightly found. In the work we proof the soundness of the new algorithm. We also show that the worst case time performance of the resthe number of vertices of the input graph. The resulting algorithm is easy to implement and is as efficient as other known solving algorithms. / L'evolució de models geomètrics basats en restriccions està fortament lligada al sistemes de Disseny Assistit per Computador (CAD) paramètrics i als basats en el paradigma de disseny per mitjà de característiques. Des de la introducció del disseny paramètric per part de Pro/Engineer en els anys 80, la major part de sistemes CAD utilitzaren com a tecnologia de base els models geomètrics basats en restriccions. Els models geomètrics basats en restriccions permeteren als sistemes CAD proporcionar un model d'informació més ampli i alhora oferir una interfície d'usuari intuitiva. Posteriorment, els mateixos models s'aplicaren en camps com el disseny de mecanismes, el modelatge químic, la visió per computador i la geometria dinàmica. Els models geomètrics basats en restriccions són models no avaluats. Un problema clau relacionat amb el models de restriccions geomètriques és el problema de la resolució de restriccions geomètriques, que es resumeix com el problema d'avaluar un model basat en restriccions. Entre els diferents enfocs de resolució de restriccions geomètriques, tractem els solvers de Descomposició-Recombinació (DR-solvers) basats en graphs. En l'enfoc constructiu basat en grafs, el problema geomètric es trasllada en un pas inicial a un graf, on els vèrtexs del graf representen el conjunt d'elements geomètrics i on les arestes corresponen a les restriccions geomètriques entre els elements. A continuació el problema de restriccions es resol descomposant el graf en un conjunt de subproblemes, cadascun dels quals es divideix recursivament fins a obtenir problemes bàsics, que sovint són operacions geomètriques realitzables, per exemple, amb regle i compàs, i que es resolen per mitjà d'un solver numèric específic. Finalment, la solució del problema inicial s'obté recombinant les solucions dels subproblemes. L'enfoc utilitzat pels DR-solvers ha esdevingut especialment interessant quan la descomposició en subproblemes i la posterior recombinació de solucions d'aquests subproblemes es pot descriure com un pla de construcció generat a priori, és a dir, un pla generat com a pas de pre-procés sense necessitat de resoldre realment els subsistemes. El pla generat pel DR-planner esdevé inalterable encara que els valors numèrics dels paràmetres canviin. Aquest pla es coneix com a DR-plan i la unitat en el solver que el genera és l'anomenat DR-planner. En aquest context, el DR-plan s'utilitza com a eina del procés de resolució en curs, és a dir, permet calcular les coordenades específiques que correctament posicionen els elements geomètrics uns respecte els altres. En aquesta tesi desenvolupem un nou algoritme que és la base del DR-planner per a DR-solvers constructius basats en grafs en l'espai bidimensional. Aquest DR-planner es basa en la descomposició en arbre d'un graf. La descomposició en triangles o arbre de descomposició d'un graf es basa en descomposar un graf en tres subgrafs tals que comparteixen un vèrtex 2 a 2. El conjunt de vèrtexs compartits s'anomenen \emph{hinges}. La descomposició en arbre d'un graf de restriccions geomètriques equival, en cert sentit, a resoldre el problema de restriccions geomètriques. L'algoritme del DR-planner en primer lloc transforma el graf proporcionat en un graf més simple i planar. A continuació, es calcula el dibuix en el pla del graf transformat, on les hinges, si n'hi ha, es calculen de manera directa. En aquest treball demostrem la correctesa del nou algoritme. Finalment, proporcionem l'estudi de la complexitat temporal de l'algoritme en cas pitjor i demostrem que és quadràtica en el nombre de vèrtexs del graf proporcionat. L'algoritme resultant és senzill d'implementar i tan eficient com altres algoritmes de resolució concrets

El fenómeno de urbanización a escala global es uno de los retos esenciales para la planificación urbana del siglo actual, más aún si se tienen en cuenta los impactos que este tipo de crecimiento genera cuando la expansión de la ciudad se realiza de manera acelerada y sin planificación. Las ciudades de América Latina han experimentado desde mediados del siglo XX un rápido crecimiento, el cual ha promovido como en el caso colombiano ciudades de hasta más de 2 millones de habitantes como Medellín y Cali o hasta de más de 6 millones de habitantes como Bogotá. Estas ciudades poseen grandes problemas urbanos de gran complejidad y requieren grandes inversiones no solo por parte del gobierno local sino también estatal. Es por eso que esta investigación propone unas estrategias aplicables a la planificación de las ciudades de tamaño medio, teniendo como base la creencia de que la planificación de una ciudad a escala mediana o pequeña, puede ser más manejable y puede permitir con más facilidad la aplicación de políticas de gestión sostenibles sobre el territorio. El estudio de caso se desarrolla en Manizales una ciudad intermedia andina de Colombia. El trabajo se desarrolla en dos partes: En la primera parte se hace un desarrollo teórico y conceptual en torno a las ciudades intermedias, el desarrollo urbano sostenible de la ciudad intermedia de América Latina, y sobre estrategias de sostenibilidad urbana. Más adelante se hace una presentación del problema y los objetivos del estudio. Se hace un análisis del contexto colombiano y especialmente regional del caso de estudio- Manizales- reconociendo a su vez las causas de desequilibrios en el territorio y se explican los métodos que se llevarán a cabo a lo largo de la presente investigación. En la parte II se desarrolla la metodología propuesta en la primera parte. Posteriormente se pretende articular los resultados de la metodología propuesta con las herramientas de espacialización proporcionadas por medio de Sistemas de Información Geográfica SIG, todo ello como aporte a la toma de decisiones adecuada y propia para cada territorio. Al final, se presentan las conclusiones en las que se podrán evidenciar resultados y/o recomendaciones generadas del trabajo. / The urbanization phenomenon of worldwide presents a major challenge for the planning of cities in the XXI century, especially when taking into account the impact that this kind of growth generated when the expansion of the city takes place rapidly, and without planning. Specifically in the case of intermediate cities in Latin America, they have experienced since midtwentieth century rapid unplanned growth, as in the case of Colombia, a country in which cities are up to over 2 million as Medellin and Cali or even more than 6 million people and Bogota. These cities have large imbalances that are reflected in highly complex urban problems and require large investments not only by the state but also local government. For the above, this research proposes a strategy for planning of medium-sized cities, recognizing that planning a city-wide medium or small, may be more manageable and can allow easier application of management policies sustainable over the territory. The case study is developed in an intermediate city Manizales Colombia Andean. To model the city of study, is used as a tool Geographic Information Systems and discusses the conditions of sustainability at regional distances from proximity to equipment as a contribution to the solution of problems such as social exclusion and spatial. The aim is to observe the distribution of equipment in the city, and in turn the deficit detect them in certain areas (neighborhoods), all proposed as a contribution to decision-making at local level. In the first part of the study is theoretical and conceptual development regarding intermediate cities, sustainable urban development of intermediate cities in Latin America, and urban sustainability strategies chords Colombian regional context while recognizing the causes of imbalances in this territory. In the second part of the proposed methodology is developed with the support of GIS, all as input to decision making adequate and appropriate for each territory, the results are articulated with urban sustainability strategies identified and recommendations are made to be applied in City study.

The growing significance, technical development and employment of electromagnetic (EM) methods in exploration geophysics have led to the increasing need for reliable and fast techniques of interpretation of 3-D EM data sets acquired in complex geological environments. The first and most important step to creating an inversion method is the development of a solver for the forward problem. In order to create an efficient, reliable and practical 3-D EM inversion, it is necessary to have a 3-D EM modelling code that is highly accurate, robust and very fast. This thesis focuses precisely on this crucial and very demanding step to building a 3-D EM interpretation method. The thesis presents as its main contribution a highly accurate, robust, very fast and extremely scalable numerical method for 3-D EM modelling in geophysics that is based on finite elements (FE) and designed to run on massively parallel computing platforms. Thanks to the fact that the FE approach supports completely unstructured tetrahedral meshes as well as local mesh refinements, the presented solver is able to represent complex geometries of subsurface structures very precisely and thus improve the solution accuracy and avoid misleading artefacts in images. Consequently, it can be successfully used in geological environments of arbitrary geometrical complexities. The parallel implementation of the method, which is based on the domain decomposition and a hybrid MPI-OpenMP scheme, has proved to be highly scalable - the achieved speed-up is close to the linear for more than a thousand processors. Thanks to this, the code is able to deal with extremely large problems, which may have hundreds of millions of degrees of freedom, in a very efficient way. The importance of having this forward-problem solver lies in the fact that it is now possible to create a 3-D EM inversion that can deal with data obtained in extremely complex geological environments in a way that is realistic for practical use in industry. So far, such imaging tool has not been proposed due to a lack of efficient, parallel FE solutions as well as the limitations of efficient solvers based on finite differences. In addition, the thesis discusses physical, mathematical and numerical aspects and challenges of 3-D EM modelling, which have been studied during my research in order to properly design the presented software for EM field simulations on 3-D areas of the Earth. Through this work, a physical problem formulation based on the secondary Coulomb-gauged EM potentials has been validated, proving that it can be successfully used with the standard nodal FE method to give highly accurate numerical solutions. Also, this work has shown that Krylov subspace iterative methods are the best solution for solving linear systems that arise after FE discretisation of the problem under consideration. More precisely, it has been discovered empirically that the best iterative method for this kind of problems is biconjugate gradient stabilised with an elaborate preconditioner. Since most commonly used preconditioners proved to be either unable to improve the convergence of the implemented solvers to the desired extent, or impractical in the parallel context, I have proposed a preconditioning technique for Krylov methods that is based on algebraic multigrid. Tests for various problems with different conductivity structures and characteristics have shown that the new preconditioner greatly improves the convergence of different Krylov subspace methods, which significantly reduces the total execution time of the program and improves the solution quality. Furthermore, the preconditioner is very practical for parallel implementation. Finally, it has been concluded that there are not any restrictions in employing classical parallel programming models, MPI and OpenMP, for parallelisation of the presented FE solver. Moreover, they have proved to be enough to provide an excellent scalability for it.

The rewrite relation with parameters m and n and with the possible lengthlimit = k or :::; k we denote by w~, =kW~· or ::;kw~ respectively. Theidempotency languages generated from a starting word w by the respectiveoperations are wD<l::', w=kD<l::' and W<;kD<l::'.Also other special cases of idempotency languages besides duplication havecome up in different contexts. The investigations of Ito et al. about insertionand deletion, Le., operations that are also observed in DNA molecules, haveestablished that w5 and w~ both preserve regularity.Our investigations about idempotency relations and languages start out fromthe case of a uniform length bound. For these relations =kW~ the conditionsfor confluence are characterized completely. Also the question of regularity is-k n answered for aH the languages w- D<lm . They are nearly always regular. Onlythe languages wD<lo for n > 1 are more complicated and belong to the class ofcontext-free languages.For a generallength bound, i.e."for the relations :"::kW~, confluence doesnot hold so frequently. This complicatedness of the relations results also inmore complicated languages, which are often non-regular, as for example thelanguages W<;kD<l::' for aH bounds k 2 4. For k :::; 2 they are regular. The case ofk :::; 3, though, remains open. We show, however, that none of these languagesever exceeds the complexity of being context-free.Without any length bound, idempotency relations have a very complicatedstructure. Over alphabets of one or two letters we still characterize the conditionsfor confluence. Over three or more letters, in contrast, only a few casesare solved. We determine the combinations of parameters that result in theregularity of wD<l::', when the alphabet of w contains only two letters. Only thecase of 2 :::; m < n remains open.In a second chapter sorne more involved questions are solved for the specialcase of duplication. First we shed sorne light on the reasons why it is so difficultto determine the context-freeness ofduplication languages. We show that theyfulfiH aH pumping properties and that they are very dense. Therefore aH thestandard tools to prove non-context-freness do not apply here.The concept of root in Formal Language ·Theory is frequently used to describethe reduction of a word to another one, which is in sorne sense elementary.For example, there are primitive roots, periodicity roots, etc. Elementaryin connection with duplication are square-free words, Le., words that do notcontain any repetition. Thus we define the duplication root of w to consist ofaH the square-free words, from which w can be reached via the relation w~.Besides sorne general observations we prove the decidability of the question,whether the duplication root of a language is finite.Then we devise acode, which is robust under duplication of its code words.This would keep the result of a computation from being destroyed by duplications in the code words. We determine the exact conditions, under whichinfinite such codes exist: over an alphabet of two letters they exist for a lengthbound of 2, over three letters already for a length bound of 1.Also we apply duplication to entire languages rather than to single words;then it is interesting to determine, whether regular and context-free languagesare closed under this operation. We show that the regular languages are closedunder uniformly bounded duplication, while they are not closed under duplicationwith a generallength bound. The context-free languages are closed underboth operations.The thesis concludes with a list of open problems related with the thesis'topics.

A graph where every vertex has three neighboring vertices is a cubic graph. An edge-coloring is an assignment of colors to the edges of a graph in such a way that the edges incident to a vertex have no repeated colors. An edge-coloring is optimal if it uses the minimum possible number of colors. Vizing's Theorem implies that an optimal edge-coloring of a cubic graph requires three or four colors. If three colors are enough, we call the edge-coloring a Tait-coloring. If four colors are needed, we call the graph a snark. Holyer proved that deciding wether a cubic graph is Tait-colorable is an NP-complete problem, therefore it is widely believed that it is a very difficult or intractable problem in the general case. Nevertheless, theory does not forbid efficient solutions in specific cases: this is called "breaking intractability". We describe an heuristic algorithm called CVD, for "Conflicting Vertex Displacement", which has a good empirical performance in random regular graphs. Also it allows us to check a conjecture by Biggs on "odd graphs" in instances with milions of vertices and edges, using moderately powerful computers. Snarks are relevant in graph theory: they appear often as minimal counterexamples of important conjectures, such as the Cycle Double Cover Conjecture (every bridgeless graph has a family of cycles such that every edge belongs to exactly two cycles of the family). In the analysis and synthesis of snarks, multipoles, "pieces" of cubic graphs with free ends that can be joined to each other, are often used. In a Tait-colored multipole, the number of equally colored free ends for each color and the total number of free ends have the same parity (the number of vertices of the multipole has this same parity, too). This result, known as the Parity Lemma, allows the interpretation of multipoles as logic gates and cubic graphs as logic circuits. This gives a very general way to construct snarks, based on logic circuits with no valid Boolean assignment, and allows us to relate the Tait-coloring of cubic graphs to integer factorization. In particular, we can construct snarks from prime numbers. A state of a multipole is the restriction of a Tait-coloring of the multipole to its free ends. If the set of states of a multipole is a non-empty subset of the set of states of another multipole with a larger number of vertices, we call the smaller multipole a reduction of the larger one. An irreducible multipole is a multipole with no reduction (an obvious example is a minimal multipole, that is, with no vertices or with a single vertex). The maximum number of vertices of an irreducible multipole as a function of its number (m) of free ends is denoted by v(m). Its behavior is well-known only for m<6, while there is a specific lower bound for v(6). We prove the irreducibility of multipoles having a tree, a forest or a cycle as their underlying graphs. This allows us to prove a linear lower bound for v(m), the first general result for this function. / Un graf on cada vèrtex té tres vèrtexs adjacents és un graf cúbic. Un aresta-acoloriment és una assignació de colors a les arestes d'un graf de tal manera que no es repeteixin colors en les arestes incidents a un mateix vèrtex. Un aresta-acoloriment és òptim si utilitza el mínim nombre possible de colors. El Teorema de Vizing implica que un aresta-acolorament òptim d'un graf cúbic requereix tres o quatre colors. Si tres colors són suficients, de l'aresta-acoloriment en diem Tait-acoloriment. Si fan falta quatre colors, diem que el graf és un snark. Holyer va demostrar que determinar si un graf cúbic és Tait-acolorible és un problema NP-complet, i per tant se suposa àmpliament que és un problema molt difícil o intractable en el cas general. Tanmateix, la teoria no prohibeix que es puguin resoldre eficientment casos concrets: és el que s'anomena "ruptura de la intractabilitat". Descrivim un algorisme heurístic anomenat DVC, per "Desplaçament de Vèrtexs Conflictius", que té un bon rendiment empíric en grafs regulars aleatoris. També ens permet comprovar una conjectura de Biggs sobre els "odd graphs" en instàncies de milions de vèrtexs i arestes, utilitzant ordinadors de potència moderada. Els snarks són rellevants en la teoria de grafs: sovint apareixen com a contraexemples minimals de conjectures importants, com per exemple la Conjectura del Recobriment Doble per Cicles (tot graf sense ponts té una família de cicles tal que cada aresta pertany exactament a dos dels cicles). En l'anàlisi i síntesi d'snarks se solen utilitzar multipols, que són "peces" de grafs cúbics amb extrems lliures que es poden unir entre ells. En un multipol Tait-acolorit, el nombre d'extrems lliures de cada color té la mateixa paritat que el nombre total d'extrems lliures (i que el nombre de vèrtexs del multipol). Aquest resultat, conegut com el Lema de Paritat, permet interpretar els multipols com a portes lògiques i els grafs cúbics com a circuits lògics. Això proporciona una manera molt general de construir snarks, en base a circuits lògics sense cap assignació booleana vàlida, i també permet relacionar l'aresta-acoloriment de grafs amb la factorització de nombres enters. En particular, permet construir snarks a partir de nombres primers. Un estat d'un multipol és la restricció d'un Tait-acoloriment del multipol als seus extrems lliures. Si el conjunt d'estats d'un multipol és un subconjunt no buit del conjunt d'estats d'un altre multipol amb un nombre de vèrtexs més gran, diem que n'és una reducció. Un multipol irreductible és un multipol sense cap reducció (un exemple obvi és un multipol minimal, és a dir sense vèrtexs o amb un sol vèrtex). El màxim nombre de vèrtexs d'un multipol irreductible en termes del seu nombre d'extrems lliures és una funció, representada per v(m), el comportament de la qual només es coneix exactament per m<6, mentre que hi ha una fita inferior específica per v(6). Demostrem la irreductibilitat dels multipols que tenen un arbre, un bosc o un cicle com a graf subjacent. Això ens permet establir una fita lineal inferior que és el primer resultat de naturalesa general sobre la funció v(m).

This thesis is based on the implementation of a computational system to numerically simulate the interaction between a fluid and an arbitrary number of rigid bodies. This implementation was performed in a distributed memory parallelization context, which makes the process and its description especially challenging. As a consequence, for the sake of descriptive precision and conceptual clarity, a new formal framework using set theory concepts is developed. The fluid is discretized using a non body-conforming mesh and the boundaries of the bodies are embedded in this mesh. The force that the fluid exerts on a body is determined from the residual of the momentum equations. Conversely, the velocity of the body is imposed as a boundary condition in the fluid. In this context, two new approaches are proposed. To account for the fact that fluid nodes can become solid nodes and vice versa due to the rigid body movement, we have adopted the FMALE approach, which is based on the idea of a virtual movement of the fluid mesh at each time step. A new method of interpolation is adopted inside the FMALE implementation in order to improve the results. The physics of the fluid is described by the incompressible Navier-Stokes equations. These equations are stabilized using a variational multiscale finite element method and solved using a fractional step like scheme at the algebraic level. The incompressible Navier-Stokes solver is a parallel solver based on master-worker strategy. The bodies can have arbitrary shapes and their motions are determined by the Newton-Euler equations. The contacts between bodies are solved using impulses to avoid interpenetrations. The time of impact is determined implementing a dynamic collision detection algorithm. As far as the parallel implementation is concerned, the data of all the bodies are shared by all the subdomains. To track the boundary of the bodies in the fluid mesh, computational geometry tools have been used. / Esta tesis se basa en la implementación de un sistema computacional para simular numéricamente la interacción entre un fluido y un número arbitrario de sólidos rígidos. La implementación se llevó a cabo considerando un ambiente de programación paralelo con memoria distribuida, lo que convierte al proceso y a su descripción en un reto importante. Como consecuencia, para una descripción conceptual clara y precisa, un nuevo marco formal se desarrolló utilizando los conceptos de la teoría de conjuntos. El fluido se discretiza utilizando una malla no conforme donde las mallas de contorno de los sólidos rígidos están embebidas. La fuerza que el fluido ejerce sobre un sólido se determina en base al residuo de las ecuaciones de conservación del momento. En cambio, la velocidad del sólido se impone como una condición de contorno en el fluido. En este contexto, en el marco de los métodos de malla de contorno embebidos, se proponen dos nuevas aproximaciones. Para resolver el problema que se plantea cuando un número dado de nodos que pertenecían al fluido se convierten en nodos que pertenecen al sólido y viceversa debido al propio movimiento de los sólidos, hemos adoptado la aproximación conocida como FMALE, la cual se basa en la idea de un movimiento virtual de la malla que discretiza al fluido a cada paso de tiempo. Un nuevo método de interpolación se implementó dentro del método FMALE para mejorar los resultados obtenidos. La física del fluido se describe mediante las ecuaciones de Navier-Stokes. Estas ecuaciones se estabilizaron utilizando el método variacional multiescala de los elementos finitos y se resolvieron utilizando un esquema similar al de los de paso de tiempo fraccionado. En general, los sólidos pueden tener formas arbitrarias y sus movimientos se describen mediante las ecuaciones de Newton-Euler. Los contactos entre sólidos se resuelven usando impulsos para evitar interpenetraciones. El tiempo de contacto se determina implementando un algoritmo de detección de colisiones dinámico. En paralelo, los datos de todos los sólidos se comparten entre todos los subdominios. Sin embargo, para tratar los contornos de los sólidos dentro de la malla no conforme que discretiza el problema, varias herramientas computaciones han sido usadas para reducir el tiempo de ejecución

Aquesta tesi proposa l'ús d'aproximacions de control inspirades biològicament per a generar i controlar el patró de locomoció omnidireccional de robots humanoides, adaptant el seu moviment a diversos tipus de terreny pla usant realimentació multisensorial. Els sistemes de control de locomoció proposats van ser implementats usant xarxes de Generadors Centrals de Patrons (CPG) basades en el model de neurona de Matsuoka. Els CPGs són xarxes neuronals biològiques situades en el sistema nerviós central dels vertebrats o en els ganglis principals d'invertebrats, les quals poden controlar moviments coordinats. El fet que, a la natura, la locomoció humana i animal sigui controlada mitjançant xarxes CPG ha inspirat la teoria en la qual es basa la present tesi. En particular, la tesi proposa dues arquitectures de control en llaç tancat basades en mètodes de control CPG-espai-articulacions, les quals han estat validades mitjançant un robot simulat i un robot humanoide NAO real. La primera arquitectura de control va identificar algunes característiques importants que un esquema de control CPG-espai-articulacions ha de tenir si es vol descriure un patró de locomoció útil. A partir d'aquesta anàlisi, la segona arquitectura de control va ser proposada per descriure patrons de locomoció ben caracteritzats. Per a millorar el comportament del sistema en llaç tancat, s’ha proposat un mecanisme de reinicialització de fase per a xarxes CPG basades en el model de neurona de Matsuoka. Aquest mecanisme fa possible dissenyar i estudiar controladors de realimentació que poden modificar ràpidament els patrons de locomoció generats. Els resultats obtinguts mostren que els esquemes de control proposats poden produir patrons de locomoció ben caracteritzats amb una resposta ràpida adequada per a robots humanoides amb una capacitat de processament reduïda. Els experiments també indiquen que el sistema de control proposat habilita el robot a respondre ràpida i robustament, i poder fer front a situacions complexes. / Esta tesis propone el uso de aproximaciones de control inspiradas biológicamente para generar y controlar el modo de caminar omnidireccional de robots humanoides, adaptando su movimiento a varios tipos de terreno plano usando realimentación multisensorial. Los sistemas de control de locomoción propuestos fueron implementados usando redes de Generadores Centrales de Patrones (CPG) basadas en el modelo de neurona de Matsuoka. Los CPGs son redes neuronales biológicas ubicadas en el sistema nervioso central de vertebrados o en los ganglios principales de invertebrados, las cuales pueden controlar movimientos coordinados. El hecho de que, en la naturaleza, la locomoción humana y animal sea controlada mediante redes CPG ha inspirado la teoría en la cual se basa la presente tesis. En particular, dos arquitecturas de control en lazo cerrado basadas en métodos de control CPG-espacio-articulaciones han sido propuestas y probadas mediante ambos un robot simulado y un robot humanoide NAO real. La primera arquitectura de control identificó algunas características importantes que un esquema de control CPG-espacio-articulaciones debe tener si se quiere describir un patrón de locomoción útil. A partir de este análisis, la segunda arquitectura de control fue propuesta para describir patrones de locomoción bien caracterizados. Para mejorar cómo se comporta el sistema en lazo cerrado, un mecanismo de reseteo de fase para redes CPG basadas en el modelo de neurona de Matsuoka ha sido propuesto. Este mecanismo hace posible diseñar y estudiar controladores de realimentación que pueden modificar rápidamente los patrones de locomoción generados. Los resultados obtenidos muestran que los esquemas de control propuestos pueden producir patrones de locomoción bien caracterizados con una respuesta rápida adecuada para robots humanoides con una capacidad de procesamiento reducida. Estos experimentos también indican que el sistema de control propuesto habilita al robot a responder rápida y robustamente, y poder hacer frente a situaciones complejas. / This thesis proposes the use of biologically inspired control approaches to generate and control the omnidirectional gait of humanoid robots, adapting their movement to various types of flat terrain using multi-sensory feedback. The proposed locomotion control systems were implemented using Central Pattern Generator (CPG) networks based on Matsuoka’s neuron model. CPGs are biological neural networks located in the central nervous system of vertebrates or in the main ganglia of invertebrates, which can control coordinated movements, such as those involved in locomotion, respiration, chewing or swallowing. The fact that, in nature, human and animal locomotion is controlled by CPG networks has inspired the theory on which the present thesis is based. In particular, two closed-loop control architectures based on CPG-joint-space control methods have been proposed and tested by using both a simulated and a real NAO humanoid robot. The first control architecture identified some important features that a CPG-joint-space control scheme must have if a useful locomotion pattern is to be described. On the basis of this analysis, the second control architecture was proposed to describe well-characterized locomotion patterns. The new system, characterized by optimized parameters obtained with a genetic algorithm (GA), effectively generated and controlled locomotion patterns for biped robots on flat and sloped terrain. To improve how the system behaves in closed loop, a phase resetting mechanism for CPG networks based on Matsuoka’s neuron model has been proposed. It makes it possible to design and study feedback controllers that can quickly modify the locomotion pattern generated. The results obtained show that the proposed control schemes can yield well-characterized locomotion patterns with a fast response suitable for humanoid robots with a reduced processing capability. These experiments also indicate that the proposed system enables the robot to respond quickly and robustly, and to cope with complex situations.

Aquesta tesi s'ha dut a terme dins del Grup en de Tecnologies Mèdia (GTM) de l'Escola d'Enginyeria i Arquitectura la Salle. El grup te una llarga trajectòria dins del cap de la síntesi de veu i fins i tot disposa d'un sistema propi de síntesi per concatenació d'unitats (US-TTS) que permet sintetitzar diferents estils expressius usant múltiples corpus. De forma que per a realitzar una síntesi agressiva, el sistema usa el corpus de l'estil agressiu, i per a realitzar una síntesi sensual, usa el corpus de l'estil corresponent. Aquesta tesi pretén proposar modificacions del esquema del US-TTS que permetin millorar la flexibilitat del sistema per sintetitzar múltiples expressivitats usant només un únic corpus d'estil neutre. L'enfoc seguit en aquesta tesi es basa en l'ús de tècniques de processament digital del senyal (DSP) per aplicar modificacions de senyal a la veu sintetitzada per tal que aquesta expressi l'estil de parla desitjat. Per tal de dur a terme aquestes modificacions de senyal s'han usat els models harmònic més soroll per la seva flexibilitat a l'hora de realitzar modificacions de senyal. La qualitat de la veu (VoQ) juga un paper important en els diferents estils expressius. És per això que es va estudiar la síntesi de diferents emocions mitjançant la modificació de paràmetres de VoQ de baix nivell. D'aquest estudi es van identificar un conjunt de limitacions que van donar lloc als objectius d'aquesta tesi, entre ells el trobar un paràmetre amb gran impacte sobre els estils expressius. Per aquest fet l'esforç vocal (VE) es va escollir per el seu paper important en la parla expressiva. Primer es va estudiar la possibilitat de transferir l'VE entre dues realitzacions amb diferent VE de la mateixa paraula basant-se en la tècnica de predicció lineal adaptativa del filtre de pre-èmfasi (APLP). La proposta va permetre transferir l'VE correctament però presentava limitacions per a poder generar nivells intermitjos d'VE. Amb la finalitat de millorar la flexibilitat i control de l'VE expressat a la veu sintetitzada, es va proposar un nou model d'VE basat en polinomis lineals. Aquesta proposta va permetre transferir l'VE entre dues paraules qualsevols i sintetitzar nous nivells d'VE diferents dels disponibles al corpus. Aquesta flexibilitat esta alineada amb l'objectiu general d'aquesta tesi, permetre als sistemes US-TTS sintetitzar diferents estils expressius a partir d'un únic corpus d'estil neutre. La proposta realitzada també inclou un paràmetre que permet controlar fàcilment el nivell d'VE sintetitzat. Això obre moltes possibilitats per controlar fàcilment el procés de síntesi tal i com es va fer al projecte CreaVeu usant interfícies gràfiques simples i intuïtives, també realitzat dins del grup GTM. Aquesta memòria conclou presentant el treball realitzat en aquesta tesi i amb una proposta de modificació de l'esquema d'un sistema US-TTS per incloure els blocs de DSP desenvolupats en aquesta tesi que permetin al sistema sintetitzar múltiple nivells d'VE a partir d'un corpus d'estil neutre. Això obre moltes possibilitats per generar interfícies d'usuari que permetin controlar fàcilment el procés de síntesi, tal i com es va fer al projecte CreaVeu, també realitzat dins del grup GTM. Aquesta memòria conclou presentant el treball realitzat en aquesta tesi i amb una proposta de modificació de l'esquema del sistema US-TTS per incloure els blocs de DSP desenvolupats en aquesta tesi que permetin al sistema sintetitzar múltiple nivells d'VE a partir d'un corpus d'estil neutre. / Esta tesis se llevó a cabo en el Grup en Tecnologies Mèdia de la Escuela de Ingeniería y Arquitectura la Salle. El grupo lleva una larga trayectoria dentro del campo de la síntesis de voz y cuenta con su propio sistema de síntesis por concatenación de unidades (US-TTS). El sistema permite sintetizar múltiples estilos expresivos mediante el uso de corpus específicos para cada estilo expresivo. De este modo, para realizar una síntesis agresiva, el sistema usa el corpus de este estilo, y para un estilo sensual, usa otro corpus específico para ese estilo. La presente tesis aborda el problema con un enfoque distinto proponiendo cambios en el esquema del sistema con el fin de mejorar la flexibilidad para sintetizar múltiples estilos expresivos a partir de un único corpus de estilo de habla neutro. El planteamiento seguido en esta tesis esta basado en el uso de técnicas de procesamiento de señales (DSP) para llevar a cabo modificaciones del señal de voz para que este exprese el estilo de habla deseado. Para llevar acabo las modificaciones de la señal de voz se han usado los modelos harmónico más ruido (HNM) por su flexibilidad para efectuar modificaciones de señales. La cualidad de la voz (VoQ) juega un papel importante en diferentes estilos expresivos. Por ello se exploró la síntesis expresiva basada en modificaciones de parámetros de bajo nivel de la VoQ. Durante este estudio se detectaron diferentes problemas que dieron pié a los objetivos planteados en esta tesis, entre ellos el encontrar un único parámetro con fuerte influencia en la expresividad. El parámetro seleccionado fue el esfuerzo vocal (VE) por su importante papel a la hora de expresar diferentes emociones. Las primeras pruebas se realizaron con el fin de transferir el VE entre dos realizaciones con diferente grado de VE de la misma palabra usando una metodología basada en un proceso filtrado de pre-émfasis adaptativo con coeficientes de predicción lineales (APLP). Esta primera aproximación logró transferir el nivel de VE entre dos realizaciones de la misma palabra, sin embargo el proceso presentaba limitaciones para generar niveles de esfuerzo vocal intermedios. A fin de mejorar la flexibilidad y el control del sistema para expresar diferentes niveles de VE, se planteó un nuevo modelo de VE basado en polinomios lineales. Este modelo permitió transferir el VE entre dos palabras diferentes e incluso generar nuevos niveles no presentes en el corpus usado para la síntesis. Esta flexibilidad está alineada con el objetivo general de esta tesis de permitir a un sistema US-TTS expresar múltiples estilos de habla expresivos a partir de un único corpus de estilo neutro. Además, la metodología propuesta incorpora un parámetro que permite de forma sencilla controlar el nivel de VE expresado en la voz sintetizada. Esto abre la posibilidad de controlar fácilmente el proceso de síntesis tal y como se hizo en el proyecto CreaVeu usando interfaces simples e intuitivas, también realizado dentro del grupo GTM. Esta memoria concluye con una revisión del trabajo realizado en esta tesis y con una propuesta de modificación de un esquema de US-TTS para expresar diferentes niveles de VE a partir de un único corpus neutro. / This thesis was conducted in the Grup en Tecnologies M`edia (GTM) from Escola d’Enginyeria i Arquitectura la Salle. The group has a long trajectory in the speech synthesis field and has developed their own Unit-Selection Text-To-Speech (US-TTS) which is able to convey multiple expressive styles using multiple expressive corpora, one for each expressive style. Thus, in order to convey aggressive speech, the US-TTS uses an aggressive corpus, whereas for a sensual speech style, the system uses a sensual corpus. Unlike that approach, this dissertation aims to present a new schema for enhancing the flexibility of the US-TTS system for performing multiple expressive styles using a single neutral corpus. The approach followed in this dissertation is based on applying Digital Signal Processing (DSP) techniques for carrying out speech modifications in order to synthesize the desired expressive style. For conducting the speech modifications the Harmonics plus Noise Model (HNM) was chosen for its flexibility in conducting signal modifications. Voice Quality (VoQ) has been proven to play an important role in different expressive styles. Thus, low-level VoQ acoustic parameters were explored for conveying multiple emotions. This raised several problems setting new objectives for the rest of the thesis, among them finding a single parameter with strong impact on the expressive style conveyed. Vocal Effort (VE) was selected for conducting expressive speech style modifications due to its salient role in expressive speech. The first approach working with VE was based on transferring VE between two parallel utterances based on the Adaptive Pre-emphasis Linear Prediction (APLP) technique. This approach allowed transferring VE but the model presented certain restrictions regarding its flexibility for generating new intermediate VE levels. Aiming to improve the flexibility and control of the conveyed VE, a new approach using polynomial model for modelling VE was presented. This model not only allowed transferring VE levels between two different utterances, but also allowed to generate other VE levels than those present in the speech corpus. This is aligned with the general goal of this thesis, allowing US-TTS systems to convey multiple expressive styles with a single neutral corpus. Moreover, the proposed methodology introduces a parameter for controlling the degree of VE in the synthesized speech signal. This opens new possibilities for controlling the synthesis process such as the one in the CreaVeu project using a simple and intuitive graphical interfaces, also conducted in the GTM group. The dissertation concludes with a review of the conducted work and a proposal for schema modifications within a US-TTS system for introducing the VE modification blocks designed in this dissertation.

The usability of computer models of the heart depends mostly on their capacity to accurately represent heart anatomy, microstructure and function. However, integrating such a variety of biological data is often not possible. This is the case of the cardiac conduction system (CCS), which is responsible for the fast and coordinated distribution of the electrical impulses. The CCS cannot be observed in-vivo but it is mandatory in several cardiac modeling applications involving arrhythmias. The aims of this thesis are to show the importance of explicitly modeling the CCS structure and function for an accurate description of the electrical activation of the ventricles and to present a novel technique to build automatically a CCS structure that meets physiological observations. Pursuing that goal has required a multidisciplinary effort to build models for cardiac electrophysiology, and imaging techniques to acquire and analyze data of the CCS at different scales. / La usabilidad de modelos computacionales cardíacos depende del poder representar con precisión la anatomía del corazón, su microestructura y su función. Sin embargo, la integración de tal variedad de datos biológicos no siempre es posible. Este es el caso del sistema de conducción cardiaco (CCS), que es responsable de la distribución rápida y coordinada de los impulsos eléctricos. El CCS no puede ser observado in vivo pero es imprescindible en los modelos del corazón que involucran las arritmias. Los objetivos de esta tesis son el modelar la estructura y función del CCS para obtener una descripción precisa de la activación eléctrica del corazón y el construir la estructura de un CCS que cumpla con las observaciones fisiológicas. La persecución de este objetivo ha requerido un esfuerzo multidisciplinar para construir modelos de la electrofisiología cardiaca y las técnicas de imagen necesarias para adquirir y analizar datos del CCS a diferentes escalas.