Introduction to technical communications of the 26th Int'l. Conference on logic programming (ICLP'10)

Abstract is not available.

Programming with Global Analysis

Abstract is not available

The ciao logic programming environment: A tutorial

Abstract is not available.

An abstract machine based execution model for computer architecture design and efficient implementation of logic programs in parallel.

The term "Logic Programming" refers to a variety of computer languages and execution models which are based on the traditional concept of Symbolic Logic. The expressive power of these languages offers promise to be of great assistance in facing the programming challenges of present and future symbolic processing applications in Artificial Intelligence, Knowledge-based systems, and many other areas of computing. The sequential execution speed of logic programs has been greatly improved since the advent of the first interpreters. However, higher inference speeds are still required in order to meet the demands of applications such as those contemplated for next generation computer systems. The execution of logic programs in parallel is currently considered a promising strategy for attaining such inference speeds. Logic Programming in turn appears as a suitable programming paradigm for parallel architectures because of the many opportunities for parallel execution present in the implementation of logic programs. This dissertation presents an efficient parallel execution model for logic programs. The model is described from the source language level down to an "Abstract Machine" level suitable for direct implementation on existing parallel systems or for the design of special purpose parallel architectures. Few assumptions are made at the source language level and therefore the techniques developed and the general Abstract Machine design are applicable to a variety of logic (and also functional) languages. These techniques offer efficient solutions to several areas of parallel Logic Programming implementation previously considered problematic or a source of considerable overhead, such as the detection and handling of variable binding conflicts in AND-Parallelism, the specification of control and management of the execution tree, the treatment of distributed backtracking, and goal scheduling and memory management issues, etc. A parallel Abstract Machine design is offered, specifying data areas, operation, and a suitable instruction set. This design is based on extending to a parallel environment the techniques introduced by the Warren Abstract Machine, which have already made very fast and space efficient sequential systems a reality. Therefore, the model herein presented is capable of retaining sequential execution speed similar to that of high performance sequential systems, while extracting additional gains in speed by efficiently implementing parallel execution. These claims are supported by simulations of the Abstract Machine on sample programs.

Improving probabilistic flood forecasting through a data assimilation scheme based on genetic programming

Opportunities offered by high performance computing provide a significant degree of promise in the enhancement of the performance of real-time flood forecasting systems. In this paper, a real-time framework for probabilistic flood forecasting through data assimilation is presented. The distributed rainfall-runoff real-time interactive basin simulator (RIBS) model is selected to simulate the hydrological process in the basin. Although the RIBS model is deterministic, it is run in a probabilistic way through the results of calibration developed in a previous work performed by the authors that identifies the probability distribution functions that best characterise the most relevant model parameters. Adaptive techniques improve the result of flood forecasts because the model can be adapted to observations in real time as new information is available. The new adaptive forecast model based on genetic programming as a data assimilation technique is compared with the previously developed flood forecast model based on the calibration results. Both models are probabilistic as they generate an ensemble of hydrographs, taking the different uncertainties inherent in any forecast process into account. The Manzanares River basin was selected as a case study, with the process being computationally intensive as it requires simulation of many replicas of the ensemble in real time.

El problema del rozamiento en el análisis de estructuras de fábrica mediante modelos de sólidos rígidos

La evaluación de la seguridad de estructuras antiguas de fábrica es un problema abierto.El material es heterogéneo y anisótropo, el estado previo de tensiones difícil de conocer y las condiciones de contorno inciertas. A comienzos de los años 50 se demostró que el análisis límite era aplicable a este tipo de estructuras, considerándose desde entonces como una herramienta adecuada. En los casos en los que no se produce deslizamiento la aplicación de los teoremas del análisis límite estándar constituye una herramienta formidable por su simplicidad y robustez. No es necesario conocer el estado real de tensiones. Basta con encontrar cualquier solución de equilibrio, y que satisfaga las condiciones de límite del material, en la seguridad de que su carga será igual o inferior a la carga real de inicio de colapso. Además esta carga de inicio de colapso es única (teorema de la unicidad) y se puede obtener como el óptimo de uno cualquiera entre un par de programas matemáticos convexos duales. Sin embargo, cuando puedan existir mecanismos de inicio de colapso que impliquen deslizamientos, cualquier solución debe satisfacer tanto las restricciones estáticas como las cinemáticas, así como un tipo especial de restricciones disyuntivas que ligan las anteriores y que pueden plantearse como de complementariedad. En este último caso no está asegurada la existencia de una solución única, por lo que es necesaria la búsqueda de otros métodos para tratar la incertidumbre asociada a su multiplicidad. En los últimos años, la investigación se ha centrado en la búsqueda de un mínimo absoluto por debajo del cual el colapso sea imposible. Este método es fácil de plantear desde el punto de vista matemático, pero intratable computacionalmente, debido a las restricciones de complementariedad 0 y z 0 que no son ni convexas ni suaves. El problema de decisión resultante es de complejidad computacional No determinista Polinomial (NP)- completo y el problema de optimización global NP-difícil. A pesar de ello, obtener una solución (sin garantía de exito) es un problema asequible. La presente tesis propone resolver el problema mediante Programación Lineal Secuencial, aprovechando las especiales características de las restricciones de complementariedad, que escritas en forma bilineal son del tipo y z = 0; y 0; z 0 , y aprovechando que el error de complementariedad (en forma bilineal) es una función de penalización exacta. Pero cuando se trata de encontrar la peor solución, el problema de optimización global equivalente es intratable (NP-difícil). Además, en tanto no se demuestre la existencia de un principio de máximo o mínimo, existe la duda de que el esfuerzo empleado en aproximar este mínimo esté justificado. En el capítulo 5, se propone hallar la distribución de frecuencias del factor de carga, para todas las soluciones de inicio de colapso posibles, sobre un sencillo ejemplo. Para ello, se realiza un muestreo de soluciones mediante el método de Monte Carlo, utilizando como contraste un método exacto de computación de politopos. El objetivo final es plantear hasta que punto está justificada la busqueda del mínimo absoluto y proponer un método alternativo de evaluación de la seguridad basado en probabilidades. Las distribuciones de frecuencias, de los factores de carga correspondientes a las soluciones de inicio de colapso obtenidas para el caso estudiado, muestran que tanto el valor máximo como el mínimo de los factores de carga son muy infrecuentes, y tanto más, cuanto más perfecto y contínuo es el contacto. Los resultados obtenidos confirman el interés de desarrollar nuevos métodos probabilistas. En el capítulo 6, se propone un método de este tipo basado en la obtención de múltiples soluciones, desde puntos de partida aleatorios y calificando los resultados mediante la Estadística de Orden. El propósito es determinar la probabilidad de inicio de colapso para cada solución.El método se aplica (de acuerdo a la reducción de expectativas propuesta por la Optimización Ordinal) para obtener una solución que se encuentre en un porcentaje determinado de las peores. Finalmente, en el capítulo 7, se proponen métodos híbridos, incorporando metaheurísticas, para los casos en que la búsqueda del mínimo global esté justificada. Abstract Safety assessment of the historic masonry structures is an open problem. The material is heterogeneous and anisotropic, the previous state of stress is hard to know and the boundary conditions are uncertain. In the early 50's it was proven that limit analysis was applicable to this kind of structures, being considered a suitable tool since then. In cases where no slip occurs, the application of the standard limit analysis theorems constitutes an excellent tool due to its simplicity and robustness. It is enough find any equilibrium solution which satisfy the limit constraints of the material. As we are certain that this load will be equal to or less than the actual load of the onset of collapse, it is not necessary to know the actual stresses state. Furthermore this load for the onset of collapse is unique (uniqueness theorem), and it can be obtained as the optimal from any of two mathematical convex duals programs However, if the mechanisms of the onset of collapse involve sliding, any solution must satisfy both static and kinematic constraints, and also a special kind of disjunctive constraints linking the previous ones, which can be formulated as complementarity constraints. In the latter case, it is not guaranted the existence of a single solution, so it is necessary to look for other ways to treat the uncertainty associated with its multiplicity. In recent years, research has been focused on finding an absolute minimum below which collapse is impossible. This method is easy to set from a mathematical point of view, but computationally intractable. This is due to the complementarity constraints 0 y z 0 , which are neither convex nor smooth. The computational complexity of the resulting decision problem is "Not-deterministic Polynomialcomplete" (NP-complete), and the corresponding global optimization problem is NP-hard. However, obtaining a solution (success is not guaranteed) is an affordable problem. This thesis proposes solve that problem through Successive Linear Programming: taking advantage of the special characteristics of complementarity constraints, which written in bilinear form are y z = 0; y 0; z 0 ; and taking advantage of the fact that the complementarity error (bilinear form) is an exact penalty function. But when it comes to finding the worst solution, the (equivalent) global optimization problem is intractable (NP-hard). Furthermore, until a minimum or maximum principle is not demonstrated, it is questionable that the effort expended in approximating this minimum is justified. XIV In chapter 5, it is proposed find the frequency distribution of the load factor, for all possible solutions of the onset of collapse, on a simple example. For this purpose, a Monte Carlo sampling of solutions is performed using a contrast method "exact computation of polytopes". The ultimate goal is to determine to which extent the search of the global minimum is justified, and to propose an alternative approach to safety assessment based on probabilities. The frequency distributions for the case study show that both the maximum and the minimum load factors are very infrequent, especially when the contact gets more perfect and more continuous. The results indicates the interest of developing new probabilistic methods. In Chapter 6, is proposed a method based on multiple solutions obtained from random starting points, and qualifying the results through Order Statistics. The purpose is to determine the probability for each solution of the onset of collapse. The method is applied (according to expectations reduction given by the Ordinal Optimization) to obtain a solution that is in a certain percentage of the worst. Finally, in Chapter 7, hybrid methods incorporating metaheuristics are proposed for cases in which the search for the global minimum is justified.

Sustainability of irrigated farming systems in a Tunisian region: A recursive stochastic programming analysis

The aim of this study was to evaluate the sustainability of farm irrigation systems in the Cébalat district in northern Tunisia. It addressed the challenging topic of sustainable agriculture through a bio-economic approach linking a biophysical model to an economic optimisation model. A crop growth simulation model (CropSyst) was used to build a database to determine the relationships between agricultural practices, crop yields and environmental effects (salt accumulation in soil and leaching of nitrates) in a context of high climatic variability. The database was then fed into a recursive stochastic model set for a 10-year plan that allowed analysing the effects of cropping patterns on farm income, salt accumulation and nitrate leaching. We assumed that the long-term sustainability of soil productivity might be in conflict with farm profitability in the short-term. Assuming a discount rate of 10% (for the base scenario), the model closely reproduced the current system and allowed to predict the degradation of soil quality due to long-term salt accumulation. The results showed that there was more accumulation of salt in the soil for the base scenario than for the alternative scenario (discount rate of 0%). This result was induced by applying a higher quantity of water per hectare for the alternative as compared to a base scenario. The results also showed that nitrogen leaching is very low for the two discount rates and all climate scenarios. In conclusion, the results show that the difference in farm income between the alternative and base scenarios increases over time to attain 45% after 10 years.

Goal-oriented self-adaptive hp-strategies for finite element analysis of electromagnetic scattering and radiation problems

In this paper, a fully automatic goal-oriented hp-adaptive finite element strategy for open region electromagnetic problems (radiation and scattering) is presented. The methodology leads to exponential rates of convergence in terms of an upper bound of an user-prescribed quantity of interest. Thus, the adaptivity may be guided to provide an optimal error, not globally for the field in the whole finite element domain, but for specific parameters of engineering interest. For instance, the error on the numerical computation of the S-parameters of an antenna array, the field radiated by an antenna, or the Radar Cross Section on given directions, can be minimized. The efficiency of the approach is illustrated with several numerical simulations with two dimensional problem domains. Results include the comparison with the previously developed energy-norm based hp-adaptivity.

Implementación de algoritmos para la manipulación de curvas concoides en diseño geométrico

Este proyecto se enmarca dentro de la Computación Simbólica y de los fundamentos matemáticos del Diseño Geométrico Asistido por ordenador (CAGD). Se abordara uno de los problemas principales en el ámbito del CAGD y que es la manipulación de las Curvas Concoide. La importancia del avance en la manipulación de las curvas concoide radica en el papel fundamental que desempeñan en múltiples aplicaciones en la actualidad dentro de campos de diversa índole tales como la medicina, la óptica, el electromagnetismo, la construcción, etc. El objetivo principal de este proyecto es el diseño e implementación de algoritmos para el estudio, cálculo y manipulación de curvas concoides, utilizando técnicas propias del Calculo Simbólico. Esta implementación se ha programado utilizando el sistema de computación simbólica Maple. El proyecto consiste en dos partes bien diferenciadas, una parte teórica y otra más practica. La primera incluye la descripción geométrica y definición formal de curvas concoide, así como las ideas y propiedades básicas. De forma más precisa, se presenta un estudio matemático sobre el análisis de racionalidad de estas curvas, explicando los algoritmos que serán implementados en las segunda parte, y que constituye el objetivo principal de este proyecto. Para cerrar esta parte, se presenta una pequeña introducción al sistema y a la programación en Maple. Por otro lado, la segunda parte de este proyecto es totalmente original, y en ella el autor desarrolla las implementaciones en Maple de los algoritmos presentados en la parte anterior, así como la creación de un paquete Maple que las recoge. Por último, se crean las paginas de ayudas en el sistema Maple para la correcta utilización del paquete matemático anteriormente mencionado. Una vez terminada la parte de implementación, se aplican los algoritmos implementados a una colección de curvas clásicas conocidas, recogiendo los datos y resultados obtenidos en un atlas de curvas. Finalmente, se presenta una recopilación de las aplicaciones más destacadas en las que las concoides desempeñan un papel importante así como una breve reseña sobre las concoides de superficies, objeto de varios estudios en la actualidad y a los que se considera que el presente proyecto les puede resultar de gran utilidad. Abstract This project is set up in the framework of Symbolic Computation as well as in the implementation of algebraic-geometric problems that arise from Computer Aided Geometric Design (C.A.G.D.) applications. We address problems related to conchoid curves. The importance of these curves is the fundamental role that they play in current applications as medicine, optics, electromagnetism, construction, etc. The main goal of this project is to design and implement some algorithms to solve problems in studying, calculating and generating conchoid curves with symbolic computation techniques. For this purpose, we program our implementations in the symbolic system “Maple". The project consists of two differentiated parts, one more theoretical part and another part more practical. The first one includes the description of conchoid curves as well as the basic ideas about the concept and its basic properties. More precisely, we introduce in this part the mathematical analysis of the rationality of the conchoids, and we present the algorithms that will be implemented. Furthermore, the reader will be brie y introduced in Maple programming. On the other hand, the second part of this project is totally original. In this more practical part, the author presents the implemented algorithms and a Maple package that includes them, as well as their help pages. These implemented procedures will be check and illustrated with some classical and well known curves, collecting the main properties of the conchoid curves obtained in a brief atlas. Finally, a compilation of the most important applications where conchoids play a fundamental role, and a brief introduction to the conchoids of surfaces, subject of several studies today and where this project could be very useful, are presented.

Independence, Global analysis, and parallelism, in dinamically scheduled constraint logic programming.

El punto de vista de muchas otras aplicaciones que modifican las reglas de computación. En segundo lugar, y una vez generalizado el concepto de independencia, es necesario realizar un estudio exhaustivo de la efectividad de las herramientas de análisis en la tarea de la paralelizacion automática. Los resultados obtenidos de dicha evaluación permiten asegurar de forma empírica que la utilización de analizadores globales en la tarea de la paralelizacion automática es vital para la consecución de una paralelizarían efectiva. Por último, a la luz de los buenos resultados obtenidos sobre la efectividad de los analizadores de flujo globales basados en la interpretación abstracta, se presenta la generalización de las herramientas de análisis al contexto de los lenguajes lógicos restricciones y planificación dinámica.

Sistema para cambiar la geometría de un motor

En este proyecto se desarrolla un sistema electrónico para variar la geometría de un motor de un monoplaza que participa en la competición Fórmula SAE. Fórmula SAE es una competición de diseño de monoplazas para estudiantes, organizado por “Society of Automotive Enginners” (SAE). Este concurso busca la innovación tecnológica de la automoción, así como que estudiantes participen en un trabajo real, en el cual el objetivo es obtener resultados competitivos cumpliendo con una serie de requisitos. La variación de la geometría de un motor en un vehículo permite mejorar el rendimiento del monoplaza consiguiendo elevar el par de potencia del motor. Cualquier mejora en del vehículo en un ámbito de competición puede resultar determinante en el desenlace de la misma. El objetivo del proyecto es realizar esta variación mediante el control de la longitud de los tubos de admisión de aire o “runners” del motor de combustión, empleando un motor lineal paso a paso. A partir de la información obtenida por sensores de revoluciones del motor de combustión y la posición del acelerador se debe controlar la distancia de dichos tubos. Integrando este sistema en el bus CAN del vehículo para que comparta la información medida al resto de módulos. Por todo esto se realiza un estudio aclarando los aspectos generales del objetivo del trabajo, para la comprensión del proyecto a realizar, las posibilidades de realización y adquisición de conocimientos para un mejor desarrollo. Se presenta una solución basada en el control del motor lineal paso a paso mediante el microcontrolador PIC32MX795F512-L. Dispositivo del fabricante Microchip con una arquitectura de 32 bits. Este dispone de un módulo CAN integrado y distintos periféricos que se emplean en la medición de los sensores y actuación sobre el motor paso a paso empleando el driver de Texas Instruments DRV8805. Entonces el trabajo se realiza en dos líneas, una parte software de programación del control del sistema, empleando el software de Microchip MPLABX IDE y otra parte hardware de diseño de una PCB y circuitos acondicionadores para la conexión del microcontrolador, con los sensores, driver, motor paso a paso y bus CAN. El software empleado para la realización de la PCB es Orcad9.2/Layout. Para la evaluación de las medidas obtenidas por los sensores y la comprobación del bus CAN se emplea el kit de desarrollo de Microchip, MCP2515 CAN Bus Monitor Demo Board, que permite ver la información en el bus CAN e introducir tramas al mismo. ABSTRACT. This project develops an electronic system to vary the geometry of a car engine which runs the Formula SAE competition. Formula SAE is a design car competition for students, organized by "Society of Automotive Engineers" (SAE). This competition seeks technological innovation in the automotive industry and brings in students to participate in a real job, in which the objective is to obtain competitive results in compliance with certain requirements. Varying engine’s geometry in a vehicle improves car’s performance raising engine output torque. Any improvement in the vehicle in a competition field can be decisive in the outcome of it. The goal of the project is the variation by controlling the length of the air intake pipe or "runners" in a combustion engine, using a linear motor step. For these, uses the information gathered by speed sensors from the combustion engine and by the throttle position to control the distance of these tubes. This system is integrated in the vehicle CAN bus to share the information with the other modules. For all this is made a study to clarify the general aspects of the project in order to understand the activities developed inside the project, the different options available and also, to acquire knowledge for a better development of the project. The solution is based on linear stepper motor control by the microcontroller PIC32MX795F512-L. Device from manufacturer Microchip with a 32-bit architecture. This module has an integrated CAN various peripherals that are used in measuring the performance of the sensors and drives the stepper motor using Texas Instruments DRV8805 driver. Then the work is done in two lines, first, control programming software system using software MPLABX Microchip IDE and, second, hardware design of a PCB and conditioning circuits for connecting the microcontroller, with sensors, driver stepper motor and CAN bus. The software used to carry out the PCB is Orcad9.2/Layout. For the evaluation of the measurements obtained by the sensors and CAN bus checking is used Microchip development kit, MCP2515 CAN Bus Monitor Demo Board, that allows you to see the information on the CAN bus and enter new frames in the bus.

Sonophone: Desarrollo y evaluación de un sonómetro profesional para iOS

La medida de la presión sonora es un proceso de extrema importancia para la ingeniería acústica, de aplicación en numerosas áreas de esta disciplina, como la acústica arquitectónica o el control de ruido. Sobre todo en esta última, es necesario poder efectuar medidas precisas en condiciones muy diversas. Por otra parte, la ubicuidad de los dispositivos móviles inteligentes (smartphones, tabletas, etc.), dispositivos que integran potencia de procesado, conectividad, interactividad y una interfaz intuitiva en un tamaño reducido, abre la posibilidad de su uso como sistemas de medida de calidad y de coste bajo. En este Proyecto se pretende utilizar las capacidades de entrada y salida, procesado, conectividad inalámbrica y geolocalización de los dispositivos móviles basados en iOS, en concreto el iPhone, para implementar un sistema de medidas acústicas que iguale o supere las prestaciones de los sonómetros existentes en el mercado. SonoPhone permitirá, mediante la conexión de un micrófono de medida adecuado, la realización de medidas de acuerdo a las normas técnicas en vigor, así como la posibilidad de programar, configurar y almacenar o trasmitir las medidas realizadas, que además estarán geolocalizadas con el GPS integrado en el dispositivo móvil. También se permitirá enviar los datos de la medida a un almacenamiento remoto en la nube. La aplicación tiene una estructura modular en la que un módulo de adquisición de datos lee la señal del micrófono, un back-end efectúa el procesado necesario, y otros módulos permiten la calibración del dispositivo y programar y configurar las medidas, así como su almacenamiento y transmisión en red. Una interfaz de usuario (GUI) permite visualizar las medidas y efectuar las configuraciones deseadas por el usuario, todo ello en tiempo real. Además de implementar la aplicación, se ha realizado una prueba de funcionamiento para determinar si el hardware del iPhone es adecuado para la medida de la presión acústica de acuerdo a las normas internacionales. Sound pressure measurement is an extremely important process in the field of acoustic engineering, with applications in numerous subfields, like for instance building acoustics and noise control, where it is necessary to be able to accurately measure sound pressure in very diverse (and sometimes adverse) conditions. On the other hand, the growing ubiquity of mobile devices such as smartphones or tablets, which combine processing power, connectivity, interactivity and an intuitive interface in a small size, makes it possible to use these devices as quality low-cost measurement systems. This Project aims to use the input-output capabilities of iOS-based mobile devices, in particular the iPhone, together with their processing power, wireless connectivity and geolocation features, to implement an acoustic measurement system that rivals the performance of existing devices. SonoPhone allows, with the addition of an adequate measurement microphone, to carry out measurements that comply with current technical regulations, as well as programming, configuring, storing and transmitting the results of the measurement. These measurements will be geolocated using the integrated GPS, and can be transmitted effortlessly to a remote cloud storage. The application is structured in modular fashion. A data acquisition module reads the signal from the microphone, while a back-end module carries out the necessary processing. Other modules permit the device to be calibrated, or control the configuration of the measurement and its storage or transmission. A Graphical User Interface (GUI) allows visual feedback on the measurement in progress, and provides the user with real-time control over the measurement parameters. Not only an application has been developed; a laboratory test was carried out with the goal of determining if the hardware of the iPhone permits the whole system to comply with international regulations regarding sound level meters.

Mobile devices: dominant design as a goal

Since the beginning of the smartphones in the 80s, the mobile device market has grown and evolved towards devices connected everywhere, with hardware more and more close to computers and laptops than a classic mobile telephone. Nowadays, this market seems to be crowded and some companies seem not to know exactly which step is next. In this manner, a concept appears in the market as a solution or a difficulty to overcome: the dominant design. The thesis aims to establish an analysis and definition of what a dominant design is and how we should understand this concept: which are the costumers’ demands and needs? How can we relate this information with the dominant design? What is the strategy of the firm before designing a device? Do they use a concept similar to a dominant design?. The research base its analysis in a theoretical framework based in innovation and marketing literature, to then compare the model studied with data collected from surveys made to customers, interviews made to workers of the mobile device market, and different new projects on the market. The research finishes with a discussion about the theoretical and the empirical frameworks, and concludes replying the research questions, and defining a dominant design and its current situation in the market. RESUMEN. Desde la aparición de los Smartphones en los años 80, el mercado de los dispositivos móviles ha crecido y evolucionado hacia dispositivos cada vez más conectados, con hardware cada vez más cercano a los ordenadores de sobremesa y portátiles que al clásico teléfono móvil. A día de hoy, el mercado está saturado y algunas compañías parecen dubitativas ante el próximo paso a seguir. De esta manera, el concepto del diseño dominante aparece en el mercado como una solución a esta dificultad. El primer capítulo de este estudio se centra en establecer, a modo de introducción, los antecedentes al caso a estudiar, el objetivo de la tesis con sus limitaciones y delimitaciones, así como la metodología utilizada. También se plantean las preguntas principales (Research Questions) sobre el objetivo de la tesis, las cuales darán respuesta en la conclusión final al caso de estudio. Este proyecto tiene como objetivo establecer un análisis y definición sobre que es un diseño dominante y qué deberíamos entender como tal: ¿cuáles son las necesidades y las exigencias de los clientes? ¿Cómo se puede relacionar esta información con el diseño dominante en el sector tecnológico? ¿Cuáles son las estrategias de las empresas antes de diseñar un nuevo dispositivo? ¿Usan un concepto o modelos similares a un diseño dominante? Posteriormente, el segundo capítulo expone la bibliografía utilizada, y el enfoque analítico que se llevará a cabo con las 3 principales fuentes de datos. La investigación enfoca su análisis en un marco teórico, basado en publicaciones y bibliografía relacionadas con la innovación y el marketing, para luego comparar el modelo estudiado con un marco empírico: datos obtenidos de encuestas a consumidores, entrevistas a profesionales del sector de los dispositivos móviles, y diferentes prototipos y nuevos proyectos en este mercado. Entre esta literatura se encuentran manuales de marketing como “22 Immutable laws of Marketing” (de Al Ries & Jack Trout), publicaciones sobre el sector industrial de la tecnología y negocios: “Crossing the Chasm” de Geoffrey A. Moore y modelos de innovación entre otros como “Mastering the Dynamics of Innovation” de James M. Utterback. El tercer capítulo corresponde al estudio del marco teórico de la tesis, donde se analizará principalmente el modelo de innovación utilizado (el modelo cíclico de Utterback) y varios principios de marketing aplicados a este sector. Se plantean las bases de este modelo, la definición que el propio Utterback ofrece sobre el diseño dominante, y las 3 fases del proceso del mismo (Fluid Phase, Transitional Phase y Specific Phase), donde las empresas cambian de estrategia según las circunstancias evolutivas del dispositivo, su posición respecto el líder del mercado, o los procesos de estandarización y de costes. Por último se plantea la base para el desarrollo del diseño dominante en un ciclo evolutivo constante en el tiempo. Respecto a la parte más analítica de la tesis, el cuarto capítulo se desarrolla a partir de los datos obtenidos de las fuentes de información en el marco empírico de estudio. Se obtienen conclusiones sobre los datos realizados en ambas encuestas (en Español e Inglés) y sobre la relevancia de esta información; se estudian uno por uno hasta cuatro casos de nuevos dispositivos a corto-medio plazo en el mercado y se obtienen unas conclusiones globales sobre las entrevistas realizadas a los profesionales del sector y la relevancia de todas estas informaciones. En el quinto capítulo de la tesis se desarrolla la discusión en torno a los marcos teórico y empírico utilizados, para concluir respondiendo a las “Research Questions”, definiendo de esta manera el concepto de diseño dominante y comparando esta definición con la situación real del mercado. Se contrastan las bases del modelo de Utterback con los datos obtenidos en el capítulo cuarto, enfatizando la comparación entre las fases de este modelo con la realidad obtenida a través del estudio. Las encuestas realizadas a los consumidores se enmarcan en la segunda y tercera fase del ciclo, donde el desarrollo del diseño dominante ya está establecido y más desarrollado, mientras que las entrevistas unifican varios puntos clave a tener en cuenta en la primera y segunda fases, orientándose a las capas previas del proceso. Después se comparan uno a uno los 4 dispositivos analizados, a fin de establecer su jerarquía dentro del mercado, como posibles nuevos diseños dominantes o evoluciones especializadas de otros que ya aparecieron en el mercado con anterioridad. Así mismo, en esta parte final del estudio se comparan entre sí los resultados similares entre las tres fuentes de datos, y se analiza la veracidad de todas las fuentes consultadas. Finalmente, se han registrado en un sexto capítulo todas las referencias utilizadas en este proyecto, tanto publicaciones bibliográficas, entrevistas, citas de personajes relevantes del sector y enlaces en la red sobre noticias relevantes. En el apartado de apéndices se adjuntan tres anexos, donde se adjunta información utilizada en el caso de estudio, y la cual se ha obviado del texto principal con el objetivo de agilizar la lectura y la comprensión del mismo. Estos tres apéndices corresponden a las dos encuestas realizadas en ambos idiomas y la entrevista realizada a los profesionales del sector de los dispositivos móviles.

Generación de Casos de Prueba en Programación Orientada a Objetos = Test Case Generation in Object-Oriented Programming

Las pruebas de software (Testing) son en la actualidad la técnica más utilizada para la validación y la evaluación de la calidad de un programa. El testing está integrado en todas las metodologías prácticas de desarrollo de software y juega un papel crucial en el éxito de cualquier proyecto de software. Desde las unidades de código más pequeñas a los componentes más complejos, su integración en un sistema de software y su despliegue a producción, todas las piezas de un producto de software deben ser probadas a fondo antes de que el producto de software pueda ser liberado a un entorno de producción. La mayor limitación del testing de software es que continúa siendo un conjunto de tareas manuales, representando una buena parte del coste total de desarrollo. En este escenario, la automatización resulta fundamental para aliviar estos altos costes. La generación automática de casos de pruebas (TCG, del inglés test case generation) es el proceso de generar automáticamente casos de prueba que logren un alto recubrimiento del programa. Entre la gran variedad de enfoques hacia la TCG, esta tesis se centra en un enfoque estructural de caja blanca, y más concretamente en una de las técnicas más utilizadas actualmente, la ejecución simbólica. En ejecución simbólica, el programa bajo pruebas es ejecutado con expresiones simbólicas como argumentos de entrada en lugar de valores concretos. Esta tesis se basa en un marco general para la generación automática de casos de prueba dirigido a programas imperativos orientados a objetos (Java, por ejemplo) y basado en programación lógica con restricciones (CLP, del inglés constraint logic programming). En este marco general, el programa imperativo bajo pruebas es primeramente traducido a un programa CLP equivalente, y luego dicho programa CLP es ejecutado simbólicamente utilizando los mecanismos de evaluación estándar de CLP, extendidos con operaciones especiales para el tratamiento de estructuras de datos dinámicas. Mejorar la escalabilidad y la eficiencia de la ejecución simbólica constituye un reto muy importante. Es bien sabido que la ejecución simbólica resulta impracticable debido al gran número de caminos de ejecución que deben ser explorados y a tamaño de las restricciones que se deben manipular. Además, la generación de casos de prueba mediante ejecución simbólica tiende a producir un número innecesariamente grande de casos de prueba cuando es aplicada a programas de tamaño medio o grande. Las contribuciones de esta tesis pueden ser resumidas como sigue. (1) Se desarrolla un enfoque composicional basado en CLP para la generación de casos de prueba, el cual busca aliviar el problema de la explosión de caminos interprocedimiento analizando de forma separada cada componente (p.ej. método) del programa bajo pruebas, almacenando los resultados y reutilizándolos incrementalmente hasta obtener resultados para el programa completo. También se ha desarrollado un enfoque composicional basado en especialización de programas (evaluación parcial) para la herramienta de ejecución simbólica Symbolic PathFinder (SPF). (2) Se propone una metodología para usar información del consumo de recursos del programa bajo pruebas para guiar la ejecución simbólica hacia aquellas partes del programa que satisfacen una determinada política de recursos, evitando la exploración de aquellas partes del programa que violan dicha política. (3) Se propone una metodología genérica para guiar la ejecución simbólica hacia las partes más interesantes del programa, la cual utiliza abstracciones como generadores de trazas para guiar la ejecución de acuerdo a criterios de selección estructurales. (4) Se propone un nuevo resolutor de restricciones, el cual maneja eficientemente restricciones sobre el uso de la memoria dinámica global (heap) durante ejecución simbólica, el cual mejora considerablemente el rendimiento de la técnica estándar utilizada para este propósito, la \lazy initialization". (5) Todas las técnicas propuestas han sido implementadas en el sistema PET (el enfoque composicional ha sido también implementado en la herramienta SPF). Mediante evaluación experimental se ha confirmado que todas ellas mejoran considerablemente la escalabilidad y eficiencia de la ejecución simbólica y la generación de casos de prueba. ABSTRACT Testing is nowadays the most used technique to validate software and assess its quality. It is integrated into all practical software development methodologies and plays a crucial role towards the success of any software project. From the smallest units of code to the most complex components and their integration into a software system and later deployment; all pieces of a software product must be tested thoroughly before a software product can be released. The main limitation of software testing is that it remains a mostly manual task, representing a large fraction of the total development cost. In this scenario, test automation is paramount to alleviate such high costs. Test case generation (TCG) is the process of automatically generating test inputs that achieve high coverage of the system under test. Among a wide variety of approaches to TCG, this thesis focuses on structural (white-box) TCG, where one of the most successful enabling techniques is symbolic execution. In symbolic execution, the program under test is executed with its input arguments being symbolic expressions rather than concrete values. This thesis relies on a previously developed constraint-based TCG framework for imperative object-oriented programs (e.g., Java), in which the imperative program under test is first translated into an equivalent constraint logic program, and then such translated program is symbolically executed by relying on standard evaluation mechanisms of Constraint Logic Programming (CLP), extended with special treatment for dynamically allocated data structures. Improving the scalability and efficiency of symbolic execution constitutes a major challenge. It is well known that symbolic execution quickly becomes impractical due to the large number of paths that must be explored and the size of the constraints that must be handled. Moreover, symbolic execution-based TCG tends to produce an unnecessarily large number of test cases when applied to medium or large programs. The contributions of this dissertation can be summarized as follows. (1) A compositional approach to CLP-based TCG is developed which overcomes the inter-procedural path explosion by separately analyzing each component (method) in a program under test, stowing the results as method summaries and incrementally reusing them to obtain whole-program results. A similar compositional strategy that relies on program specialization is also developed for the state-of-the-art symbolic execution tool Symbolic PathFinder (SPF). (2) Resource-driven TCG is proposed as a methodology to use resource consumption information to drive symbolic execution towards those parts of the program under test that comply with a user-provided resource policy, avoiding the exploration of those parts of the program that violate such policy. (3) A generic methodology to guide symbolic execution towards the most interesting parts of a program is proposed, which uses abstractions as oracles to steer symbolic execution through those parts of the program under test that interest the programmer/tester most. (4) A new heap-constraint solver is proposed, which efficiently handles heap-related constraints and aliasing of references during symbolic execution and greatly outperforms the state-of-the-art standard technique known as lazy initialization. (5) All techniques above have been implemented in the PET system (and some of them in the SPF tool). Experimental evaluation has confirmed that they considerably help towards a more scalable and efficient symbolic execution and TCG.