Jeux de policiers et voleurs, Modèles et applications

Les jeux de policiers et voleurs sont étudiés depuis une trentaine d’années en informatique et en mathématiques. Comme dans les jeux de poursuite en général, des poursuivants (les policiers) cherchent à capturer des évadés (les voleurs), cependant ici les joueurs agissent tour à tour et sont contraints de se déplacer sur une structure discrète. On suppose toujours que les joueurs connaissent les positions exactes de leurs opposants, autrement dit le jeu se déroule à information parfaite. La première définition d’un jeu de policiers-voleurs remonte à celle de Nowakowski et Winkler [39] et, indépendamment, Quilliot [46]. Cette première définition présente un jeu opposant un seul policier et un seul voleur avec des contraintes sur leurs vitesses de déplacement. Des extensions furent graduellement proposées telles que l’ajout de policiers et l’augmentation des vitesses de mouvement. En 2014, Bonato et MacGillivray [6] proposèrent une généralisation des jeux de policiers-voleurs pour permettre l’étude de ceux-ci dans leur globalité. Cependant, leur modèle ne couvre aucunement les jeux possédant des composantes stochastiques tels que ceux dans lesquels les voleurs peuvent bouger de manière aléatoire. Dans ce mémoire est donc présenté un nouveau modèle incluant des aspects stochastiques. En second lieu, on présente dans ce mémoire une application concrète de l’utilisation de ces jeux sous la forme d’une méthode de résolution d’un problème provenant de la théorie de la recherche. Alors que les jeux de policiers et voleurs utilisent l’hypothèse de l’information parfaite, les problèmes de recherches ne peuvent faire cette supposition. Il appert cependant que le jeu de policiers et voleurs peut être analysé comme une relaxation de contraintes d’un problème de recherche. Ce nouvel angle de vue est exploité pour la conception d’une borne supérieure sur la fonction objectif d’un problème de recherche pouvant être mise à contribution dans une méthode dite de branch and bound.

On MDS convolutional codes over Z_p^r

Maximum distance separable (MDS) convolutional codes are characterized through the property that the free distance meets the generalized Singleton bound. The existence of free MDS convolutional codes over Zpr was recently discovered in Oued and Sole (IEEE Trans Inf Theory 59(11):7305–7313, 2013) via the Hensel lift of a cyclic code. In this paper we further investigate this important class of convolutional codes over Zpr from a new perspective. We introduce the notions of p-standard form and r-optimal parameters to derive a novel upper bound of Singleton type on the free distance. Moreover, we present a constructive method for building general (non necessarily free) MDS convolutional codes over Zpr for any given set of parameters.

Numerical estimation of Carbonate properties using a digital rock physics workflow

Digital rock physics combines modern imaging with advanced numerical simulations to analyze the physical properties of rocks -- In this paper we suggest a special segmentation procedure which is applied to a carbonate rock from Switzerland -- Starting point is a CTscan of a specimen of Hauptmuschelkalk -- The first step applied to the raw image data is a nonlocal mean filter -- We then apply different thresholds to identify pores and solid phases -- Because we are aware of a nonneglectable amount of unresolved microporosity we also define intermediate phases -- Based on this segmentation determine porositydependent values for the pwave velocity and for the permeability -- The porosity measured in the laboratory is then used to compare our numerical data with experimental data -- We observe a good agreement -- Future work includes an analytic validation to the numerical results of the pwave velocity upper bound, employing different filters for the image segmentation and using data with higher resolution

Numerical enclosures of the optimal cost of the Kantorovitch’s mass transportation problem

International audience

RESILIENCE OF NETWORKED INFRASTRUCTURE WITH EVOLVING COMPONENT CONDITIONS: A PAVEMENT NETWORK APPLICATION

This thesis deals with quantifying the resilience of a network of pavements. Calculations were carried out by modeling network performance under a set of possible damage-meteorological scenarios with known probability of occurrence. Resilience evaluation was performed a priori while accounting for optimal preparedness decisions and additional response actions that can be taken under each of the scenarios. Unlike the common assumption that the pre-event condition of all system components is uniform, fixed, and pristine, component condition evolution was incorporated herein. For this purpose, the health of the individual system components immediately prior to hazard event impact, under all considered scenarios, was associated with a serviceability rating. This rating was projected to reflect both natural deterioration and any intermittent improvements due to maintenance. The scheme was demonstrated for a hypothetical case study involving Laguardia Airport. Results show that resilience can be impacted by the condition of the infrastructure elements, their natural deterioration processes, and prevailing maintenance plans. The findings imply that, in general, upper bound values are reported in ordinary resilience work, and that including evolving component conditions is of value.

Euclidean Distance Between Haar Orthogonal and Gaussian Matrices

In this work, we study a version of the general question of how well a Haar-distributed orthogonal matrix can be approximated by a random Gaussian matrix. Here, we consider a Gaussian random matrix (Formula presented.) of order n and apply to it the Gram–Schmidt orthonormalization procedure by columns to obtain a Haar-distributed orthogonal matrix (Formula presented.). If (Formula presented.) denotes the vector formed by the first m-coordinates of the ith row of (Formula presented.) and (Formula presented.), our main result shows that the Euclidean norm of (Formula presented.) converges exponentially fast to (Formula presented.), up to negligible terms. To show the extent of this result, we use it to study the convergence of the supremum norm (Formula presented.) and we find a coupling that improves by a factor (Formula presented.) the recently proved best known upper bound on (Formula presented.). Our main result also has applications in Quantum Information Theory.

Efficient algorithms for beacon routing in polygons

In a paper by Biro et al. [7], a novel twist on guarding in art galleries is introduced. A beacon is a fixed point with an attraction pull that can move points within the polygon. Points move greedily to monotonically decrease their Euclidean distance to the beacon by moving straight towards the beacon or sliding on the edges of the polygon. The beacon attracts a point if the point eventually reaches the beacon. Unlike most variations of the art gallery problem, the beacon attraction has the intriguing property of being asymmetric, leading to separate definitions of attraction region and inverse attraction region. The attraction region of a beacon is the set of points that it attracts. For a given point in the polygon, the inverse attraction region is the set of beacon locations that can attract the point. We first study the characteristics of beacon attraction. We consider the quality of a "successful" beacon attraction and provide an upper bound of $\sqrt{2}$ on the ratio between the length of the beacon trajectory and the length of the geodesic distance in a simple polygon. In addition, we provide an example of a polygon with holes in which this ratio is unbounded. Next we consider the problem of computing the shortest beacon watchtower in a polygonal terrain and present an $O(n \log n)$ time algorithm to solve this problem. In doing this, we introduce $O(n \log n)$ time algorithms to compute the beacon kernel and the inverse beacon kernel in a monotone polygon. We also prove that $\Omega(n \log n)$ time is a lower bound for computing the beacon kernel of a monotone polygon. Finally, we study the inverse attraction region of a point in a simple polygon. We present algorithms to efficiently compute the inverse attraction region of a point for simple, monotone, and terrain polygons with respective time complexities $O(n^2)$, $O(n \log n)$ and $O(n)$. We show that the inverse attraction region of a point in a simple polygon has linear complexity and the problem of computing the inverse attraction region has a lower bound of $\Omega(n \log n)$ in monotone polygons and consequently in simple polygons.

The impact and control of malignant catarrhal fever in Tanzania

Malignant Catarrhal Fever (MCF), an often-lethal infectious disease, presents as a variable complex of lesions in susceptible ungulate species. The disease is caused by a -herpesvirus following transmission from an inapparent carrier host. Two major epidemiological forms exist: wildebeest-associated MCF (WA-MCF), in which the virus is transmitted to susceptible species by wildebeest calves less than approximately four months of age, and sheepassociated MCF (SA-MCF) in which the virus is spread by sheep (primarily adolescents). Due to the lack of an in-vitro propagation system for the causative agent of the more economically significant SA-MCF, and with the expectation that cross-protective immunity may be provided, vaccine development has focused on the more easily propagated alcelaphine herpesvirus-1 (AlHV-1) that causes WA-MCF. In 2008 a direct viral challenge trial showed that a novel vaccine, employing an attenuated AlHV-1 (atAlHV-1) `C5000 virus strain, protected British Friesian-Holstein (FH) cattle against an intranasal challenge with virulent AlHV-1 `C5000 virus. For cattle keeping people living near wildebeest calving areas in sub-Saharan Africa an effective vaccine would have value as it would release them from the costly annual disease avoidance strategy of having to move their herds away from the oncoming wildebeest. On the other hand, an effective vaccine will release herd owners from the need to avoid MCF, allowing them to graze their cattle alongside wildebeest on the highly nutritious pastures of the calving areas. As such conservationists have raised concerns that the development of a vaccine might lead to detrimental grazing competition. The principle objective of this study was to test the novel vaccine on Tanzanian shorthorn zebu cross cattle (SZC).We did this firstly using a natural challenge field trial (Chapter Two) which demonstrated that immunisation with the atAlHV-1 vaccine was well tolerated and induced an oro-nasopharyngeal AlHV-1-specific and -neutralising antibody response. This resulted in an immunity in SZC cattle that was partially protective and reduced naturally transmitted infection by 56%. We also demonstrated that non-fatal infections occurred with a much higher frequency than previously thought. Because the calculated efficacy of the vaccine was less than that seen in British FH cattle we wanted to determine whether host factors, particular to SZC cattle, had impacted the outcomes of the field trial. To do this we repeated the 2008 direct viral challenge trial using SZC cattle (Chapter Four). During this trial we also investigated whether the recombinant bacterial flagellin monomer (FliC), when used as an adjuvant, might improve the vaccine’s efficacy. The findings from this trial indicated that direct challenge with pathogenic AlHV-1 is effective at inducing MCF in SZC cattle and that FliC is not an appropriate adjuvant for this vaccine. Furthermore, with less control group cattle dying of MCF than expected we speculate that SZC cattle may have a degree of resistance to MCF that affords them protection from infection and developing fatal disease. In Chapter Three we investigated aspects of the epidemiology of MCF, specifically whether wildebeest placenta, long implicated by Maasai cattle owners as a source of MCF, might play a role in viral transmission. Additionally, through comparative sequence analysis, at two specific genes (A9.5 and ORF50) of wild-type and atAlHV-1, we investigated whether the `C5000 strain, the source of which was taken from Africa more than 40 years ago, was appropriate for vaccine development. The detection of AlHV-1 virus in approximately 50% of placentae indicated that infection can occur in-utero and that this tissue might play a role in disease transmission. And, despite describing three new alleles of the A9.5 gene (supporting previous evidence that this gene is polymorphic and encodes a secretory protein with interleukin-4 as the major homologue), the observation that the most frequently detected haplotypes, in both wild-type and attenuated AlHV-1, were identical suggests that AlHV-1 has a slow molecular clock and that the attenuated strain was appropriate for vaccine development. In Chapter Five we present the first quantitative assessment of the annual MCF avoidance costs that Maasai pastoralists incur. In particular we estimated that as a result of MCF avoidance 64% of the total daily milk yield during the MCF season was not available to be used by the 81% of the family unit remaining at the permanent boma. This represents an upper-bound loss of approximately 8% of a household0s annual income. Despite these considerable losses we concluded that, given an incidence of fatal MCF in cattle living in wildebeest calving areas of 5% to 10%, if herd owners were to stop trying to avoid MCF by allowing their cattle to graze alongside wildebeest, any gains made through increased availability of milk, improved body condition and reduced energy demands would be offset by an increase in MCF-incidence. With the development of an effective vaccine, however, this alternative strategy might become optimal. The overall conclusion we draw therefore is that, despite the substantial costs incurred each year avoiding MCF, the partial protection afforded by the novel vaccine strategy is not sufficient to warrant a wholesale change in disease avoidance strategy. Nonetheless, even the partial protection provided by this vaccine could be of value to protect animals that cannot be moved, for example where some of the herd remain at the boma to provide milk or where land-use changes make traditional disease avoidance difficult. Furthermore, the vaccine may offer a feasible solution to some of the current land-use challenges and conflicts, providing a degree of protection to valuable livestock where avoidance strategies are not possible, but with less risk of precipitating the potentially damaging environmental consequences, such as overgrazing of highly nutritious seasonal pastures, that might result if herd owners decide they no longer need to avoid wildebeest.

Synthesis, Modification and Characterization of Polymeric Membranes for CO2 Separation

This doctorate focused on the development of dense polymeric membranes for carbon capture, mostly in post combustion applications, and for natural gas sweetening. The work was supported by the European Project NANOMEMC2 funded under H2020 program. Different materials have been investigated, that rely on two main transport mechanisms: the solution-diffusion and the facilitated transport. In both cases, proper nano-fillers have been added to the matrix, in order to boost the mechanical and permselective properties of the membranes. Facilitated transport membranes were based on the use of was polyvinylamine (PVAm), as main matrix with fixed-site carriers, and L-Arginine as mobile carrier; the filler, used mostly as reinforcer, was carboxymethylated nanocellulose (cNFC). Humid test showed interesting results, and especially the blend made of PVAm/cNFC/Arg in weight ratio 27,5/27,5/45 crossed the Robeson CO2/N2 upper bound, representing current state of the art membranes, with a CO2 permeability of 271 Barrer and CO2/N2 selectivity of 70. Solution diffusion membranes were based on Pebax®2533 matrix which was added with three different graphene oxide (GO)-based materials, namely pristine GO, Porous Graphene Oxide (PGO) and a GO functionalized with polyetheramine (PEAGO). All of them provided a modest but clear increment of permeability of the Pebax matrix, from plus 2% (GO) to plus 8% (PGO), with no change in selectivity. The gas tested with this type of composites were CO2 and N2, for Post combustion capture applications. Pebax®2533 was also chemically modified, obtaining the product called “Benzoyl-P2533”, that was fully characterized, and tested in term of permeation using five gas: CO2, N2, CH4, O2, and He. Modified material showed an increment of the overall permeability of the material of a fair 10% for all gases tested, apart from helium, that increased of almost 50%.

Sviluppo di Metodi di Soft Labeling per la Multi-Document Summarization in Ambito Legale

In questo elaborato viene trattata l’analisi del problema di soft labeling applicato alla multi-document summarization, in particolare vengono testate varie tecniche per estrarre frasi rilevanti dai documenti presi in dettaglio, al fine di fornire al modello di summarization quelle di maggior rilievo e più informative per il riassunto da generare. Questo problema nasce per far fronte ai limiti che presentano i modelli di summarization attualmente a disposizione, che possono processare un numero limitato di frasi; sorge quindi la necessità di filtrare le informazioni più rilevanti quando il lavoro si applica a documenti lunghi. Al fine di scandire la metrica di importanza, vengono presi come riferimento metodi sintattici, semantici e basati su rappresentazione a grafi AMR. Il dataset preso come riferimento è Multi-LexSum, che include tre granularità di summarization di testi legali. L’analisi in questione si compone quindi della fase di estrazione delle frasi dai documenti, della misurazione delle metriche stabilite e del passaggio al modello stato dell’arte PRIMERA per l’elaborazione del riassunto. Il testo ottenuto viene poi confrontato con il riassunto target già fornito, considerato come ottimale; lavorando in queste condizioni l’obiettivo è di definire soglie ottimali di upper-bound per l’accuratezza delle metriche, che potrebbero ampliare il lavoro ad analisi più dettagliate qualora queste superino lo stato dell’arte attuale.

Hydrogeological investigations in the upper Ouémé catchment in Benin, West Africa

The scope of this PhD thesis was the hydrogeological conceptualisation of the Upper Ouémé river catchment in Benin. The study area exceeds 14,500 km**2 and is underlain by a crystalline basement. At this setting the typical sequence of aquifers - a regolith aquifer at the top and a fractured bedrock aquifer at the bottom - is encountered, which is found in basement areas all over Africa and elsewhere in the world. The chosen regional approach revealed important information about the hydrochemistry and hydrogeology of this catchment. Based on the regional conceptual model a numerical groundwater flow model was designed. The numerical model was used to estimate the impact of climate change on the regional groundwater resources. This study was realised within the framework of the German interdisciplinary research project IMPETUS (English translation: "Integrated approach to the efficient management of scarce water resources in West Africa"), which is jointly managed by the German universities of Bonn and Cologne. Since the year 2000 the Upper Ouémé catchment was the principal target for investigations into the relevant processes of the regional water cycle. A first study from 2000 to 2003 (Fass, 2004, http://nbn-resolving.de/urn:nbn:de:hbz:5n-03849) focused on the hydrogeology of a small local catchment (~30 km**2). In the course of this thesis five field campaigns were underdone from the year 2004 to 2006. In the beginning of 2004 a groundwater monitoring net was installed based on 12 automatic data loggers. Manual piezometric measurements and the sampling of groundwater and surface water were realised for each campaign throughout the whole study area. Water samples were analysed for major ions, for a choice of heavy metals and for their composition by deuterium, oxygen-18 and tritium. The numerical model was performed with FEFLOW. The hydraulic and hydrochemical characteristics were described for the regolith aquifer and the bedrock aquifer. The regolith aquifer plays the role of the groundwater stock with low conductivity while the fractures of the bedrock may conduct water relatively fast towards extraction points. Flow in fractures of the bedrock depends on the connectivity of the fracture network which might be of local to subregional importance. Stable isotopes in combination with hydrochemistry proved that recharge occurs on catchment scale and exclusively by precipitation. Influx of groundwater from distant areas along dominant structures like the Kandi fault or from the Atacora mountain chain is excluded. The analysis of tritium in groundwater from different depths revealed the interesting fact of the strongly rising groundwater ages. Bedrock groundwater may possibly be much older than 50 years. Equilibrium phases of the silicate weathering products kaolinite and montmorillonite showed that the deeper part of the regolith aquifer and the bedrock aquifer feature either stagnant or less mobile groundwater while the shallow aquifer level is influenced by seasonal groundwater table fluctuations. The hydrochemical data characterised this zone by the progressive change of the hydrochemical facies of recently infiltrated rainwater on its flow path into deeper parts of the aquifers. Surprisingly it was found out that seasonal influences on groundwater hydrochemistry are minor, mainly because they affect only the groundwater levels close to the surface. The transfer of the hydrogeological features of the Upper Ouémé catchment into a regional numerical model demanded a strong simplification. Groundwater tables are a reprint of the general surface morphology. Pumping or other types of groundwater extraction would have only very local impact on the available groundwater resources. It was possible to integrate IMPETUS scenario data into the groundwater model. As a result it was shown that the impact of climate change on the groundwater resources until the year 2025 under the given conditions will be negligible due to the little share of precipitation needed for recharge and the low water needs for domestic use. Reason for concern is the groundwater quality on water points in the vicinity of settlements because of contamination by human activities as shown for the village of Dogué. Nitrate concentrations achieved in many places already alerting levels. Health risks from fluoride or heavy metals were excluded for the Upper Ouémé area.

Geochemistry of lavas and dikes from the upper oceanic crust of Hess Deep Rift, eastern Pacific Ocean

Strontium isotopes are useful tracers of fluid-rock interaction in marine hydrothermal systems and provide a potential way to quantify the amount of seawater that passes through these systems. We have determined the whole-rock Sr-isotopic compositions of a section of upper oceanic crust that formed at the fast-spreading East Pacific Rise, now exposed at Hess Deep. This dataset provides the first detailed comparison for the much-studied Ocean Drilling Program (ODP) drill core from Site 504B. Whole-rock and mineral Sr concentrations indicate that Sr-exchange between hydrothermal fluids and the oceanic crust is complex, being dependent on the mineralogical reactions occurring; in particular, epidote formation takes up Sr from the fluid increasing the 87Sr/86Sr of the bulk-rock. Calculating the fluid-flux required to shift the Sr-isotopic composition of the Hess Deep sheeted-dike complex, using the approach of Bickle and Teagle (1992, doi:10.1016/0012-821X(92)90221-G) gives a fluid-flux similar to that determined for ODP Hole 504B. This suggests that the level of isotopic exchange observed in these two regions is probably typical for modern oceanic crust. Unfortunately, uncertainties in the modeling approach do not allow us to determine a fluid-flux that is directly comparable to fluxes calculated by other methods.

A new estimate for the composition of weathered young upper continental crust from alluvial sediments, Queensland, Australia

We present new major element, trace element and Nd-isotope data for 30 alluvial sediments collected from 25 rivers in Queensland, E Australia. Samples were chosen to represent drainage from the region's most important lithologies, including Tertiary intraplate volcanic rocks, a Cretaceous igneous province (and sedimentary rocks derived thereof) as well as Proterozoic blocks. In most chemical and isotopic aspects, the alluvial sediments represent binary or ternary mixing relationships, with absolute abundances implied to reflect the proportion of lithologies in the catchments. When averaged, the studied sediments differ from other proxies of upper continental crust (UCC) mainly in their relative middle rare earth element enrichment (including an elevated Sm/Nd ratio), higher relative Eu abundance and higher Nb/Ta ratio. These features are inherited from eroded Tertiary intraplate basalts, which commonly form topographic highs in the studied region. Despite the high degree of weathering strong to excellent coherence between similarly incompatible elements is found for all samples. From this coherence, we suggest revisions of the following upper crustal element ratios: Y/Ho = 26.2, Yb/Tm = 6.37, Th/W = 7.14, Th/Tl = 24 and Zr/Hf = 36.9. Lithium, Rb, Cs and Be contents do not seem depleted relative to UCC, which may reflect paucity of K-feldspar in the eroded catchments. Nickel, Cr, Pb, Cu and Zn concentrations are elevated in polluted rivers surrounding the state capital. River sediments in the Proterozoic Georgetown Inlier are elevated in Pb, Cu and Zn but this could be a natural phenomenon reflecting abundant sulphide mineralisation in the area. Except for relative Sr concentrations, which broadly anticorrelate with mean annual rainfall in catchments, there is no obvious relationship between the extent of weathering and climate types, which range from and to tropical. The most likely explanation for this observation is that the weathering profiles in many catchments are several Myr old, established during the much wetter Miocene period. The studied sediment compositions (excluding those from the Proterozoic catchments) are used to propose a new trace element normalisation termed MUQ (MUd from Queensland), which serves as an alternative to UCC proxies derived from sedimentary rocks. Copyright (C) 2005 Elsevier Ltd