SCIENCE OF COMPUTERS (2)

Author: PEREZ GIMENEZ XAVIER.
Year: 2006.
University: POLITÉCNICA DE CATALUÑA [www.upc.edu].
Place of defense: SALA D'ACTES DE L'FME.
Place of preparation: U FACULTAT DE MATEMATIQUES I ESTADISTICA SUD.

Summary: This dissertation presents the author's work in some problems involving different models of random graphs. First it contains a technical contribution towards solving the open problem of deciding whether with high probability a random $5$-regular graph can be coloured with three colours. Next, the author proposes a model for the establishment and maintenance of communication between agents in a \emph{mobile ad-hoc network} ({\sc manet}), which is called the {\em walkers model}. We assume that the agents move through a fixed environment modelled by a motion graph, and are able to communicate only if they are at a distance of at most $d$. As the agents move randomly, we analyse how the connectivity between a set of $w$ agents evolves over time, asymptotically for a large number $N$ of vertices, when $w$ also grows large. The particular topologies of the environment which are studied here are the cycle and the toroidal grid. For the latter, the results apply under any $\ell_p$-normed distance, for $1\leq p\leq\infty$. Then, the dissertation follows with a continuous counterpart of the walkers model. Namely, it presents a model for {\sc manet}s based on random geometric graphs over the $2$-dimensional unit torus, where each node moves under the {\em random walk} mobility model. More precisely, our model starts from a random geometric graph over the torus \UT, with $n$ nodes and radius exactly at the connectivity threshold $r_c$. Then each node chooses independently a random angle in $[0,2\pi)$ and moves for a number $m$ of steps a fixed distance $s>0$ in that direction. After these steps, each node again chooses a new angle and starts moving in that new direction, repeating the change of direction every $m$ steps. We compute the expected number of steps for which the resulting graph stays connected or disconnected. In addition, for static random geometric graphs with radius at the connectivity threshold $r_c$, we provide asymptotic expressions on the probability of existence of components according to their sizes. Finally, in the last part of this work, we show in a constructive way that, for any arbitrary $\ell_p$-normed distance, $1\le p\le\infty$, the property that a random geometric graph under that distance contains a Hamiltonian cycle exhibits a sharp threshold at radius $r=\sqrt{\log n/(\alpha_p n)}$, where $\alpha_p$ is the area of the unit disk in the $\ell_p$ norm.

Author: CAMBRONERO PIQUERAS MARIA EMILIA.
Year: 2006.
University: CASTILLA-LA MANCHA [www.uclm.es].
Place of defense: ESCUELA POLITECNICA SUPERIOR DE ALBACETE.
Place of preparation: ESCUELA POLITECNICA SUPERIOR DE ALBACETE.

Summary: This thesis focuses on the analysis of various real-time systems using formal methods, in particular, we use automatons temporizados for that purpose. First, we study the parallelization of video compression algorithm MPEG-2, making a comparison between the results obtained with sequential and parallel versions, and analyzing the case, the potential improvement obtained with the parallel version. Moreover, in recent years the Internet has seen a big change, new languages and new emerging technologies, such as XML, component-based development, Web services, and so on. This has resulted in the emergence of a new area in software engineering, called Engineering Web. In this thesis we focus on the study of web services, which are one of the most important elements in the area of Information Systems Web (WIS), we present a methodology for modeling and verification of web services, as well as the tool implements. The web services cover a wide range of systems, and can be regarded as an evolutionary step in the design of distributed applications. Verification of properties in these systems can be of great importance, since some businesses depend on them, as well as looking for possible solutions to problems encountered. In this thesis we use formal methods, which provides a description of the systems to be developed at any level of detail; this description can be used to verify that the requirements of developing systems have been specified in a comprehensive manner and appropriate. In this case, we use "model checking" to carry out the analysis of these systems. On the other hand, most of the languages used to implement these web services are based on XML, which can be very complicated to use for developers who are not expert in that language. Therefore, in this thesis we have presented a series of translations that allow us to get to the XML web service, linking different representations of the same.

Author: DORRONSORO DÍAZ BERNABÉ.
Year: 2006.
University: MÁLAGA [www.uma.es].
Place of defense: E.T.S.I. INFORMÁTICA.
Place of preparation: E.T.S.I. INFORMÁTICA.

Summary: This thesis presents a study on cellular genetic algorithms and their application to solve complex problems. The thesis is organized into three main sections. The first part is an introduction to the field of evolutionary algorithms in general and the cellular genetic algorithms (cGAs) in particular, along with a complex study and discussion of the state of art in cGAs. It is also proposed in this Part two new mathematical models to characterize the operation of any cGA depending on the selection pressure, improving existing models to date. To finish this first part. In a second part, proposed, implemented and evaluated several new contributions to the field of cGAs obtained in all cases substantial improvements of these new models with respect to cGAs canonical equivalent. They are presented in this thesis new methods for managing the balance between exploration and exploitation of cGAs (as cGAs population auto-adaptativa and cGAs hierarchical). Also, the model cell is exported to other areas (for example, we propose an algorithm to estimate cellular distributions, an algorithm memético cell, or a multi CGA), a very good resutlados. Finally, we propose two new models parallel cGAs very efficient. In several of the studies in this thesis are obtained results that improve the state of the art today. In the third part of the thesis, apply some new algorithms developed for well-known problems belonging to the domains of the discrete and continuous optimization, as well as a new problem (defined in this thesis for the first time) of high real interest . It shows how the algorithms developed algorithms highly competitive with the state of art in the areas studied, including improvement in several cases.