The analysis of approximate quickselect and related problems

Approximate Quickselect, a simple modification of the well known Quickselect algorithm for selection, can be used to efficiently find an element with rank k in a given range [i..j], out of n given elements. We study basic cost measures of Approximate Quickselect by computing exact and asymptotic results for the expected number of passes, comparisons and data moves during the execution of this algorithm. The key element appearing in the analysis of Approximate Quickselect is a trivariate recurrence that we solve in full generality. The general solution of the recurrence proves to be very useful, as it allows us to tackle several related problems, besides the analysis that originally motivated us. In particular, we have been able to carry out a precise analysis of the expected number of moves of the ith element when selecting the jth smallest element with standard Quickselect, where we are able to give both exact and asymptotic results. Moreover, we can apply our general results to obtain exact and asymptotic results for several parameters in binary search trees, namely the expected number of common ancestors of the nodes with rank i and j, the expected size of the subtree rooted at the least common ancestor of the nodes with rank i and j, and the expected distance between the nodes of ranks i and j.

Modelling dependence in a ratemaking procedure with multivariate Poisson regression models

When actuaries face with the problem of pricing an insurance contract that contains different types of coverage, such as a motor insurance or homeowner's insurance policy, they usually assume that types of claim are independent. However, this assumption may not be realistic: several studies have shown that there is a positive correlation between types of claim. Here we introduce different regression models in order to relax the independence assumption, including zero-inflated models to account for excess of zeros and overdispersion. These models have been largely ignored to multivariate Poisson date, mainly because of their computational di±culties. Bayesian inference based on MCMC helps to solve this problem (and also lets us derive, for several quantities of interest, posterior summaries to account for uncertainty). Finally, these models are applied to an automobile insurance claims database with three different types of claims. We analyse the consequences for pure and loaded premiums when the independence assumption is relaxed by using different multivariate Poisson regression models and their zero-inflated versions.

Automatic DVB signal analyser

El problema de controlar les emissions de televisió digital a tota Europa pel desenvolupament de receptors robustos i fiables és cada vegada més significant, per això, sorgeix la necessitat d’automatitzar el procés d’anàlisi i control d’aquests senyals. Aquest projecte presenta el desenvolupament software d’una aplicació que vol solucionar una part d’aquest problema. L’aplicació s’encarrega d’analitzar, gestionar i capturar senyals de televisió digital. Aquest document fa una introducció a la matèria central que és la televisió digital i la informació que porten els senyals de televisió, concretament, la que es refereix a l’estàndard "Digital Video Broadcasting". A continuació d’aquesta part, l’escrit es concentra en l’explicació i descripció de les funcionalitats que necessita cobrir l'aplicació, així com introduir i explicar cada etapa d’un procés de desenvolupament software. Finalment, es resumeixen els avantatges de la creació d’aquest programa per l’automatització de l’anàlisi de senyal digital partint d’una optimització de recursos.

Interactive Epistemology and Reasoning: On the Foundations of Game Theory

Game theory describes and analyzes strategic interaction. It is usually distinguished between static games, which are strategic situations in which the players choose only once as well as simultaneously, and dynamic games, which are strategic situations involving sequential choices. In addition, dynamic games can be further classified according to perfect and imperfect information. Indeed, a dynamic game is said to exhibit perfect information, whenever at any point of the game every player has full informational access to all choices that have been conducted so far. However, in the case of imperfect information some players are not fully informed about some choices. Game-theoretic analysis proceeds in two steps. Firstly, games are modelled by so-called form structures which extract and formalize the significant parts of the underlying strategic interaction. The basic and most commonly used models of games are the normal form, which rather sparsely describes a game merely in terms of the players' strategy sets and utilities, and the extensive form, which models a game in a more detailed way as a tree. In fact, it is standard to formalize static games with the normal form and dynamic games with the extensive form. Secondly, solution concepts are developed to solve models of games in the sense of identifying the choices that should be taken by rational players. Indeed, the ultimate objective of the classical approach to game theory, which is of normative character, is the development of a solution concept that is capable of identifying a unique choice for every player in an arbitrary game. However, given the large variety of games, it is not at all certain whether it is possible to device a solution concept with such universal capability. Alternatively, interactive epistemology provides an epistemic approach to game theory of descriptive character. This rather recent discipline analyzes the relation between knowledge, belief and choice of game-playing agents in an epistemic framework. The description of the players' choices in a given game relative to various epistemic assumptions constitutes the fundamental problem addressed by an epistemic approach to game theory. In a general sense, the objective of interactive epistemology consists in characterizing existing game-theoretic solution concepts in terms of epistemic assumptions as well as in proposing novel solution concepts by studying the game-theoretic implications of refined or new epistemic hypotheses. Intuitively, an epistemic model of a game can be interpreted as representing the reasoning of the players. Indeed, before making a decision in a game, the players reason about the game and their respective opponents, given their knowledge and beliefs. Precisely these epistemic mental states on which players base their decisions are explicitly expressible in an epistemic framework. In this PhD thesis, we consider an epistemic approach to game theory from a foundational point of view. In Chapter 1, basic game-theoretic notions as well as Aumann's epistemic framework for games are expounded and illustrated. Also, Aumann's sufficient conditions for backward induction are presented and his conceptual views discussed. In Chapter 2, Aumann's interactive epistemology is conceptually analyzed. In Chapter 3, which is based on joint work with Conrad Heilmann, a three-stage account for dynamic games is introduced and a type-based epistemic model is extended with a notion of agent connectedness. Then, sufficient conditions for backward induction are derived. In Chapter 4, which is based on joint work with Jérémie Cabessa, a topological approach to interactive epistemology is initiated. In particular, the epistemic-topological operator limit knowledge is defined and some implications for games considered. In Chapter 5, which is based on joint work with Jérémie Cabessa and Andrés Perea, Aumann's impossibility theorem on agreeing to disagree is revisited and weakened in the sense that possible contexts are provided in which agents can indeed agree to disagree.

Anàlisi ambiental de La Pleta: oficina tècnica del Parc del Garraf

En aquest projecte s’ha analitzat la viabilitat de l’autosuficiència de la Pleta, l’oficina tècnica del Parc del Garraf, a partir de diferents recursos renovables. S’ha realitzat un estudi del consum hídric i energètic i de la generació de residus per tal d’avaluar les deficiències de cada sistema, per poder-hi aplicar les mesures pertinents. Els resultats obtinguts mostren que un 40% de l’aigua que es consumeix a l’edifici prové dels camions cisterna que la subministren. Per tant, la principal proposta de millora va encaminada a reduir aquest volum d’aigua i per aconseguir-ho, es proposa augmentar la superfície de recollida d’aigua de pluja aprofitant la zona pavimentada del pati de magatzems. Les altres propostes intentaran reduir el volum total d’aigua consumida, com per exemple canviar el filtre actual de les aixetes per airejadors que permeten estalviar fins a un 50% d’aigua, instal·lar cisternes de volum inferior o posar en funcionament el reg per degoteig instal·lat actualment a la Pleta però que no es troba en funcionament. Pel que fa a l’energia hi ha dues fonts, el gasoil i les plaques FV. En quant al gasoil cal diferenciar entre el consum del generador per produir electricitat i el consum de la caldera per la calefacció. Un cop estudiat el sistema s’ha obtingut que les plaques solars FV aconsegueixen produir el 73% de l’electricitat demandada a la Pleta, la resta de l’electricitat la proporciona el generador. El principal problema, però és el gran consum de gasoil per la calefacció. Les millores proposades per a solucionar aquesta problemàtica pretenen millorar l’eficiència de la instal·lació de plaques solars FV col·locant més panells solars i disminuir el consum de gasoil per part de la calefacció, ja sigui millorant l’eficiència energètica i/o canviant la font d’energia per biomassa. En el cas de residus s’ha observat que es produeixen 3.283 kg/any, sent el rebuig la fracció més important. Per tal de reduir el volum de residus generats, es pretén fomentar la utilització d’estris reutlilitzables i el correcte reciclatge, substituint les papereres actuals dels despatxos per les de paper i posant cartells informatius o indicatiu en els llocs adients.

The Impact of democratization: a preliminary investigation on social policies and political violence in Latin America

The recent strides of democracy in Latin America have been associated to conflicting outcomes. The expectation that democracy would bring about peace and prosperity have been only partly satisfied. While political violence has been by and large eradicated from the sub-continent, poverty and social injustice still prevail and hold sway. Our study argues that democracy matters for inequality through the growing strength of center left and left parties and by making political leaders in general more responsive to the underprivileged. Furthermore, although the pension reforms recently enacted in the region generated overall regressive outcomes on income distribution, democratic countries still benefit from their political past: where democratic tradition was stronger, such outcomes have been milder. Democratic tradition and the specific ideological connotations of the parties in power, on the other hand, did not play an equally crucial role in securing lower levels of political violence: during the last wave of democratizations in Latin America, domestic peace was rather an outcome of political and social concessions to those in distress. In sum, together with other factors and especially economic ones, the reason why recent democratizations have provided domestic peace in most cases, but have been unable so far to solve the problem of poverty and inequality, is that democratic traditions in the subcontinent have been relatively weak and, more specifically, that this weakness has undermined the growth of left and progressive parties, acting as an obstacle to redistribution. Such weakness, on the other hand, has not prevented the drastic reduction of domestic political violence, since what mattered in this case was a combination of symbolic or material concessions and political agreements among powerful élites and counter-élites.

Bacillus thuringiensis: fermentation process and risk assessment: a short review

Several factors make the local production of Bacillus thuringiensis (Bt) highly appropriate for pest control in developing nations. Bt can be cheaply produced on a wide variety of low cost, organic substrates. Local production results in considerable savings in hard currency which otherwise would be spent on importation of chemical and biological insecticides. The use of Bt in Brazil has been limited in comparison with chemical insecticides. Although Bt is imported, some Brazilian researchers have been working on its development and production. Fermentation processes (submerged and semi-solid) were applied, using by-products from agro-industries. As the semi-solid fermentation process demonstrated to be interesting for Bt endotoxins production, it could be adopted for small scale local production. Although promising results had been achieved, national products have not been registered due to the absence of a specific legislation for biological products. Effective actions are being developed in order to solve this gap. Regardless of the biocontrol agents being considered atoxic and harmless to the environment, information related to direct and indirect effects of microbials are still insufficient in many cases. The risk analysis of the use of microbial control agents is of upmost importance nowadays, and is also discussed.

CHO expression of a novel human recombinant IgG1 anti-RhD antibody isolated by phage display.

Replacement of the hyperimmune anti-Rhesus (Rh) D immunoglobulin, currently used to prevent haemolytic disease of the newborn, by fully recombinant human anti-RhD antibodies would solve the current logistic problems associated with supply and demand. The combination of phage display repertoire cloning with precise selection procedures enables isolation of specific genes that can then be inserted into mammalian expression systems allowing production of large quantities of recombinant human proteins. With the aim of selecting high-affinity anti-RhD antibodies, two human Fab libraries were constructed from a hyperimmune donor. Use of a new phage panning procedure involving bromelin-treated red blood cells enabled the isolation of two high-affinity Fab-expressing phage clones. LD-6-3 and LD-6-33, specific for RhD. These showed a novel reaction pattern by recognizing the D variants D(III), D(IVa), D(IVb), D(Va), D(VI) types I and II. D(VII), Rh33 and DFR. Full-length immunoglobulin molecules were constructed by cloning the variable regions into expression vectors containing genomic DNA encoding the immunoglobulin constant regions. We describe the first, stable, suspension growth-adapted Chinese hamster ovary (CHO) cell line producing a high affinity recombinant human IgG1 anti-RhD antibody adapted to pilot-scale production. Evaluation of the Fc region of this recombinant antibody by either chemiluminescence or antibody-dependent cell cytotoxicity (ADCC) assays demonstrated macrophage activation and lysis of red blood cells by human lymphocytes. A consistent source of recombinant human anti-RhD immunoglobulin produced by CHO cells is expected to meet the stringent safety and regulatory requirements for prophylactic application.

Discursos y representaciones médico-sanitarias en el cine documental colonial español de la posguerra (1939-1950)

El objetivo de este estudio es contribuir al entendimiento, desde un punto de vista histórico, del papel que juega el cine en los procesos de popularización de la ciencia, la medicina y la tecnología. El punto de partida es la consideración de la medicina y del cine como conjuntos complejos y multidimensionales de “prácticas y discursos” de carácter científico-tecnológico y, por tanto, como formas particulares de acción e interacción cotidiana entre personas, colectivos e instituciones que juegan un papel básico en los procesos de construcción y funcionamiento de las sociedades contemporáneas. Así, mediante el análisis de la representación y articulación de las prácticas y los discursos médico-sanitarios en el cine documental colonial español del primer franquismo, es decir, en el caso particular de la construcción, legitimación y consolidación de un régimen totalitario, se aportan algunas claves explicativas sobre las múltiples relaciones entre diferentes colectivos (expertos y no-expertos) en cuanto a la naturaleza y el nivel de intervención en los procesos de generación y gestión de conocimiento científico-tecnológico. Como resultado, el cine se revela como un espacio no sólo de evasión y entretenimiento, sino también de ciencia y educación, donde la capacidad de definir y solucionar problemas cotidianos de la población, y por tanto, su impacto en la construcción de la arquitectura social, ideológica, económica, política y cultural de las sociedades contemporáneas, se fundamenta en la combinación de sus aspectos como espectáculo narrativo y científico-tecnológico.

Sintonización dinámica de aplicaciones MPI

En la actualidad, la computación de altas prestaciones está siendo utilizada en multitud de campos científicos donde los distintos problemas estudiados se resuelven mediante aplicaciones paralelas/distribuidas. Estas aplicaciones requieren gran capacidad de cómputo, bien sea por la complejidad de los problemas o por la necesidad de solventar situaciones en tiempo real. Por lo tanto se debe aprovechar los recursos y altas capacidades computacionales de los sistemas paralelos en los que se ejecutan estas aplicaciones con el fin de obtener un buen rendimiento. Sin embargo, lograr este rendimiento en una aplicación ejecutándose en un sistema es una dura tarea que requiere un alto grado de experiencia, especialmente cuando se trata de aplicaciones que presentan un comportamiento dinámico o cuando se usan sistemas heterogéneos. En estos casos actualmente se plantea realizar una mejora de rendimiento automática y dinámica de las aplicaciones como mejor enfoque para el análisis del rendimiento. El presente trabajo de investigación se sitúa dentro de este ámbito de estudio y su objetivo principal es sintonizar dinámicamente mediante MATE (Monitoring, Analysis and Tuning Environment) una aplicación MPI empleada en computación de altas prestaciones que siga un paradigma Master/Worker. Las técnicas de sintonización integradas en MATE han sido desarrolladas a partir del estudio de un modelo de rendimiento que refleja los cuellos de botella propios de aplicaciones situadas bajo un paradigma Master/Worker: balanceo de carga y número de workers. La ejecución de la aplicación elegida bajo el control dinámico de MATE y de la estrategia de sintonización implementada ha permitido observar la adaptación del comportamiento de dicha aplicación a las condiciones actuales del sistema donde se ejecuta, obteniendo así una mejora de su rendimiento.

Ecologia de les Invasions Ecològiques

La paradoxa de les invasions planteja com és possible que algunes espècies siguin capaces d'envair regions a les que no han evolucionat i, fins i tot, arribar a ser més abundants que espècies autòctones que han tingut més oportunitat d’adaptars’hi. Comprendre l’ecologia de les invasions és especialment interessant perquè algunes d’aquestes espècies causen greus impactes ecològics i econòmics arreu del món. Per intentar resoldre la paradoxa en aquest treball s’ha seguit dues aproximacions. Per una banda, mitjançant anàlisis comparatius s’ha volgut identificar aquelles característiques que afecten el resultat de les introduccions d’ocells, i utilitzar-les com a predictors en protocols d’avaluació de riscos per prevenir futures invasions. Seguint en aquest nivell d’aproximació també s’ha volgut validar si, tal com prediu la teoria ecològica, les estratègies vitals de les espècies afecten l'èxit en l'establiment de poblacions d'ocells exòtics. D'altra banda, a través d'aproximacions descriptives i experimentals, s’ha volgut investigar els mecanismes d’invasió en un cas d’estudi concret, el del Rossinyol del Japó (Leiothrix lutea) als boscos de Collserola (Barcelona). Els anàlisis comparatius han mostrat que és possible de predir la probabilitat d’establiment de les espècies introduïdes a partir d’unes poques característiques amb notable precisió. Altrament, l’anàlisi sobre l’efecte de les estratègies vitals sobre el resultat de les invasions sembla indicar que hi ha un biaix en el registre històric d’introduccions que impedeix descobrir la naturalesa d’aquesta relació i suggereixen buscar una aproximació alternativa per al problema. Respecte el cas del Rossinyol del Japó, els resultats preliminars suggereixen que les raons del seu èxit als boscos de Collserola podrien ser que ha trobat un nínxol ecològic que està poc aprofitat per les espècies natives. Aquest treball vol mostrar com a través de la integració de diferents aproximacions podem ser capaços d’aportar una visió més completa per comprendre la paradoxa de les invasions.

Scepticism Revisited

Liberalism claims that for a subject S to be justified in believing p, a proposition about the external world, on the basis of his senses it is not necessary to be antecedently justified in believing propositions as there is an external world. On the other hand, conservatism claims that to be justified in believing that p on the basis of one’s perception, one must have antecedent justification to believe that p. Intuitively, we are inclined to think that liberalism about the structure of perceptual justification fits better with our epistemic practices. We acknowledge that, although we cannot produce warrant for the background belief in the external world, our empirical beliefs can be perceptually justified. However, I am interested in arguing that conservatism is theoretically better supported than liberalism. The first reason to defend this is based on the fact that in embracing liberalism dogmatism is affected by pervasive problems. The second one comes from recognizing the strength of the argument based on the thesis that experience is theory-laden. But not all are advantages for conservatism. Conservatism is presupposed in contemporary formulations of scepticism through the requirement of prior justification for background assumptions, and this fact compels anti-sceptical conservatives to conceive a non-evidential form of warrant, entitlement, to contest the sceptical threat My main worry is that, although the path of entitlement has some prospects to succeed, this new notion of justification seems to be posed ad hoc for conservatives to solve the sceptical problem. These contents are organized along the three chapters. The result of chapter 1 is a pattern of sceptical argument formed by two premises: P1*, a conservative principle, and P2*. In chapter 2 and chapter 3 two anti-sceptical proposals against the argument sketched in chapter 1 are described. Chapter 2 is devoted to explain and assess a first anti-sceptical proposal that denies P1*: dogmatism. Moreover, in chapter 3, another anti-sceptical strategy is described (the route of entitlement) that contests scepticism denying the plausibility of P2*.

Proposta metodològica per afavorir el treball en equip en assignatures que contenen la realització de projectes de disseny d'enginyeria

Aquest projecte ha tingut com a finalitat principal impulsar un aprenentatge més efectiu dels alumnes en assignatures que, impartides en una modalitat semipresencial a les escoles de Terrassa i Manresa, comporten la realització d’un treball de curs amb un alt contingut de disseny. A més a més, paral·lelament es contribueix a millorar el rendiment acadèmic de l'estudiant, en el marc de la millora global de la docència i de l'aprenentatge a la UPC amb un horitzó d'aproximació als elements que conformen l’Espai Europeu d’Educació Superior. En el context de semipresencialitat, es pretén fomentar l'aprenentatge cooperatiu i donar solució als problemes comunicatius existents a nivell d’intercanvi d’opinions, valoracions i formulació de dubtes vinculats amb el disseny, etc. En aquest projecte, doncs, s’ha creat una metodologia de treball que permet intercanviar informació gràfica (per exemple en format Autocad) a partir de les aplicacions ja incloses en la plataforma virtual Atenea (campus virtual de la UPC). Aquest projecte es basa principalment en tres objectius principals: 1. Millorar l'intercanvi d'informació entre alumnes d’un grup i entre els alumnes i el professor mitjançant el desenvolupament de protocols. 2. Fomentar l’aprenentatge cooperatiu mitjançant la integrar d’eines d’interacció instantània per Internet. 3. Adaptar l’assignatura de "Complexos Industrials" al procés de convergència a l’EEES. L'activitat ha estat desenvolupada al quadrimestre de tardor 2008-2009 i la metodologia ha estat implantadas a l'assignatura Complexos Industrials d'Enginyeria en Organització Industrial de la ETSEIAT i de la EUPM.

Les TIC a l'ensenyament de la modelització matemàtica en Ciències Econòmiques i en Ciències Experimentals

Aquest projecte proposa materials didàctics per a un nou plantejament de les assignatures de Matemàtiques dels primers cursos de Ciències Empresarials i d'Enginyeria Tècnica, més acord amb el procés de convergència europea, basat en la realització de projectes que anomenem “Tallers de Modelització Matemàtica” (TMM) en els quals: (1) Els alumnes parteixen de situacions i problemes reals per als quals han de construir per sí mateixos els models matemàtics més adients i, a partir de la manipulació adequada d’aquests models, poden obtenir la informació necessària per donar-los resposta. (2) El treball de construcció, experimentació i avaluació dels models es realitza amb el suport de la calculadora simbòlica Wiris i del full de càlcul Excel com a instruments “normalitzats” del treball matemàtic d’estudiants i professors. (3) S’adapten els programes de les assignatures de matemàtiques de primer curs per tal de poder-les associar a un petit nombre de Tallers que parteixen de situacions adaptades a cada titulació. L’assignatura de Matemàtiques per a les Ciències Empresarials s’articula entorn de dos tallers independents: “Matrius de transició” pel que fa a l’àlgebra lineal i “Previsió de vendes” per a la modelització funcional en una variable. L’assignatura de Matemàtiques per a l’Enginyeria s’articula entorn d’un únic taller, “Models de poblacions”, que abasta la majoria de continguts del curs: successions i models funcionals en una variable, àlgebra lineal i equacions diferencials. Un conjunt d’exercicis interactius basats en la calculadora simbòlica WIRIS (Wiris-player) serveix de suport per al treball tècnic imprescindible per al desenvolupament de les dues assignatures. L’experimentació d’aquests tallers durant 2 cursos consecutius (2006/07 i 2007/08) en dues universitats catalanes (URL i UAB) ha posat en evidència tant els innegables avantatges del nou dispositiu docent per a l’aprenentatge dels estudiants, així com les restriccions institucionals que actualment dificulten la seva gestió i difusió.

L'aprenentatge basat en problemes en models híbrids de docència-aprenentatge

La Facultat de Ciències de la Salut i de la Vida ha utilitzat des de 2004 la metodologia d'aprenentatge basat en problemes (en endavant ABP) com a mètode docent en els seus estudis de Biologia. En aquest període hem après algunes de les claus de l'aplicació del mètode en els nostres estudis. En primer lloc, cal disposar d'elements formatius que afavoreixin la formació dels tutors que participin en el projecte. Per assolir aquest objectiu hem dissenyat un portal on els nostres professors poden disposar de materials útils per a la seva activitat, així com de documents que permetin entendre millor el que suposa l'ABP. En segon lloc, el projecte tenia l'objectiu de dissenyar i avaluar activitats que permetessin integrar les pràctiques de laboratori en la lògica de la resolució de problemes pròpia de l'ABP. En aquest sentit vam dissenyar dues activitats en el tercer curs de la llicenciatura que anomenaren aprenentatge basat en el laboratori (ABL). Per aquest motiu es van dissenyar problemes que tinguessin una primera part de resolució a l'aula en grup de tutoria i una segona que obligués els estudiants a realitzar experiments de laboratori dirigits a entendre i resoldre les qüestions plantejades al grup de tutoria. L'ABL-1 fou un projecte de biologia cel·lular i destinat a aprofundir en els mecanismes implicats en els fenòmens de diferenciació dels miòcits. L'ABL-2 era un projecte conjunt dels professors de Fisiologia vegetal, Bioestadística i Microbiologia. En aquest cas es desitjava que els estudiants plantegessin la resolució a un problema que suposava la manipulació genètica de cèl·lules vegetals per fer possible que produïssin una substància específica, l'escopolamina. Finalment els estudiants havien d'escriure un article original com a projecte final de cada ABL. Els resultats dels dos anys d'experimentació han esta altament satisfactoris, d'acord amb les enquestes completades per alumnes i professors.