Title: Combinatorial Games Theory Author: Tomáš Valla Department / Institute: IUUK MFF UK Supervisor: Prof. RNDr. Jaroslav Nešetřil, DrSc., IUUK MFF UK Abstract: In this thesis we study the complexity that appears when we consider the competitive version of a certain environment or process, using mainly the tools of al- gorithmic game theory, complexity theory, and others. For example, in the Internet environment, one cannot apply any classical graph algorithm on the graph of connected computers, because it usually requires existence of a central authority, that manipu- lates with the graph. We describe a local and distributed game, that in a competitive environment without a central authority simulates the computation of the weighted vertex cover, together with generalisation to hitting set and submodular weight func- tion. We prove that this game always has a Nash equilibrium and each equilibrium yields the same approximation of optimal cover, that is achieved by the best known ap- proximation algorithms. More precisely, the Price of Anarchy of our game is the same as the best known approximation ratio for this problem. All previous results in this field do not have the Price of Anarchy bounded by a constant. Moreover, we include the results in two more fields, related to the complexity of competitive...

In a developing oil-based economy like Libya the availability of finance is largely affected by the availability of oil revenues which are subjected to disturbances and shocks. Therefore, the decision to save and invest a certain ratio of the country's aggregate output is, to large extent, determined (and affected) by the shocks in the oil markets rather than the requirements of economic development. In this study an attempt is made to determine the optimal rate of saving and investment, both defined as a ratio of the aggregate output, according to the requirements of economic development. For this purpose, a neo-classical Ramsey-type model for Libya is constructed and applied to obtain theoretically and empirically the optimal saving and investment rate during the period (1965-1991). The results reveal that Libya was investing over the optimal level during the oil boom of 1970s and less than the optimal level during the oil crisis of 1980s. In addition, an econometric investigation of the determinants of actual investment by sector (agriculture, non-oil industry, and services) is carried out in order to shed lights on how possible it is for Libya to adjust actual investment towards its optimal level. It is found that, as expected, the most important factor which can be used in this respect is the oil revenues or, generally, the availability of finance. In addition, the study reveals that investment in agriculture is associated, during the period of study, with a very low marginal productivity of capital whereas marginal productivity was higher in both non-oil industry and services. Finally, the study investigates also the future potential saving and investment rates and concludes that the economy, which has already reached its steady state, can be pushed out towards further growth if the economy can be able to increase the level of per worker human capital, proxied by the secondary school enrolment as a percentage of population. / Secretariat of Higher Education in Libya and Libyan Interests Section in London

No description available.

Les postulats de la mesure, définissant une mesure Quantique Non Destructive (QND), précisent que la perturbation minimale sur un objet mesuré est une projection de son état. Les appareils de mesure habituellement utilisés se situent largement au-delà de cette limite minimale. Les photodétecteurs usuels en particulier absorbent, donc détruisent, les photons qu'ils détectent. Dans notre expérience d'électrodynamique quantique en cavité, des atomes de Rydberg circulaires et des photons micro-onde confinés dans une cavité supraconductrice interagissent dans le régime de couplage fort. A l'issue de l'interaction les deux systèmes sont intriqués: chacun d'eux emporte une information sur l'autre. Dans le cas désaccordé, l'effet de l'interaction est un simple déplacement d'énergie des niveaux atomiques, résultant en un déphasage du dipôle proportionnel au nombre de photons, mesurable par interférométrie de Ramsey. Les atomes délivrent donc une information sur le nombre de photons présents dans le champ sans l'avoir modifié. Selon ce principe, nous avons pu grâce au long temps de vie de notre cavité réaliser une mesure QND répétée du nombre de photons. L'évolution du nombre de photons en présence de relaxation révèle alors des sauts brusques, appelés sauts quantiques. Notre expérience a permis la première observation de ce comportement pour la lumière. En décrivant à l'aide de la loi de Bayes l'information délivrée par chaque détection atomique, nous avons pu suivre la projection progressive d'un état cohérent vers des états de Fock contenant jusqu'à sept photons. L'analyse statistique de nos résultats fournit une très claire illustration des postulats de la mesure quantique.

In a developing oil-based economy like Libya the availability of finance is largely affected by the availability of oil revenues which are subjected to disturbances and shocks. Therefore, the decision to save and invest a certain ratio of the country's aggregate output is, to large extent, determined (and affected) by the shocks in the oil markets rather than the requirements of economic development. In this study an attempt is made to determine the optimal rate of saving and investment, both defined as a ratio of the aggregate output, according to the requirements of economic development. For this purpose, a neo-classical Ramsey-type model for Libya is constructed and applied to obtain theoretically and empirically the optimal saving and investment rate during the period (1965-1991). The results reveal that Libya was investing over the optimal level during the oil boom of 1970s and less than the optimal level during the oil crisis of 1980s. In addition, an econometric investigation of the determinants of actual investment by sector (agriculture, non-oil industry, and services) is carried out in order to shed lights on how possible it is for Libya to adjust actual investment towards its optimal level. It is found that, as expected, the most important factor which can be used in this respect is the oil revenues or, generally, the availability of finance. In addition, the study reveals that investment in agriculture is associated, during the period of study, with a very low marginal productivity of capital whereas marginal productivity was higher in both non-oil industry and services. Finally, the study investigates also the future potential saving and investment rates and concludes that the economy, which has already reached its steady state, can be pushed out towards further growth if the economy can be able to increase the level of per worker human capital, proxied by the secondary school enrolment as a percentage of population.

Climate change must deal with two market failures: global warming and learning by doing in renewable energy production. The first-best policy consists of an aggressive renewables subsidy in the near term and a gradually rising and falling carbon tax. Given that global carbon taxes remain elusive, policy makers might have to rely on a second-best subsidy only. With credible commitment the second-best subsidy is higher than the social benefit of learning to cut the transition time and peak warming close to first-best levels at the cost of higher fossil fuel use in the short run (weak Green Paradox). Without commitment the second-best subsidy is set to the social benefit of learning. It generates smaller weak Green Paradox effects, but the transition to the carbon-free takes longer and cumulative carbon emissions are higher. Under first best and second best with pre-commitment peak warming is 2.1-2.3 °C, under second best without commitment 3.5 °C, and without any policy 5.1 °C above pre-industrial levels. Not being able to commit yields a welfare loss of 95% of initial GDP compared to first best. Being able to commit brings this figure down to 7%.

Une transition entre deux niveaux voisins d'un atome de Rydberg et une cavité micro-onde de très haut facteur de qualité constituent un excellent outil pour la recherche sur les interactions matière- rayonnement au niveau le plus fondamental. La simplicité du système (deux niveaux atomiques couplés à un seul mode du champ) permet un traitement analytique complet de la plupart des phénomènes. Dans ce mémoire nous étudions les effets dispersifs de l'interaction non-résonnante entre atomes et cavité. Nous avons mesuré la variation linéaire des déplacements des niveaux d'énergie atomiques avec le nombre moyen de photons dans la cavité. Des déplacements dus à une intensité moyenne inférieure au photon unique ont été observés. En l'absence de champ injecté, il a été possible de mesurer le déplacement résiduel d'un des deux niveaux de la transition atomique: un déplacement de Lamb dû à un seul mode du champ. Ces déplacements d'énergie sont mesurés de façon sensible par une méthode interférométrique: la technique des champs oscillants séparés de Ramsey. Des expériences futures, dans une situation de très faible relaxation du champ, sont proposées. Le caractère quantique du champ sera alors dominant et il sera possible de réaliser une mesure nondestructive du nombre de photons: le caractère non-résonnant de l'interaction assure que les atomes ne peuvent ni absorber ni émettre des photons dans la cavité. Les expériences réalisées démontrent la sensibilité de l'appareil et ouvrent la voie à ces mesures non-destructives ainsi qu'à l'étude de systèmes "mésoscopiques" (états "chat de Schrödinger" du champ), à la "frontière" entre les mondes classique et quantique.

Dans le domaine micro-onde, deux niveaux de Rydberg voisins d'un atome alcalin, d'une part, et le champ électromagnétique confiné dans une cavité supraconductrice de très haute surtension, d'autre part, échangent de manière cohérente un quantum d'énergie lorsqu'ils sont à résonance. Une telle situation est conceptuellement la plus simple dans laquelle le couplage matière-rayonnement se manifeste à l'échelle élémentaire. Ce mémoire présente une mise en évidence expérimentale de cette interaction, dans une situation où l'évolution cohérente atome-champ domine les processus dissipatifs. Le couplage atome-champ est d'abord décrit théoriquement (dans un point de vue classique puis quantique), ainsi que des expériences permettant de le mettre en évidence. Ensuite, une expérience de spectroscopie des premiers états excités du système {atome + cavité} est exposée. Elle a permis d'accéder à la fréquence avec laquelle un échantillon de trois atomes et un mode résonnant du champ échangent leur énergie. Enfin, un nouveau montage expérimental est présenté. Il possède une résolution spectrale très élevée grâce à l'utilisation de la technique du champ oscillant séparé de Ramsey, et doit permettre l'observation, dans le domaine micro-onde, du couplage élémentaire entre un seul atome à deux niveaux et un seul mode du champ électromagnétique, cette observation pouvant se faire aussi bien spectralement que temporellement. La réalisation d'un montage expérimental aussi sensible, et dans lequel les amortissements de l'atome-et de la cavité sont rendus négligeables, ouvre également la voie à des tests subtils de la Mécanique Quantique (mesures sans démolition, chats de Schrödinger, etc.) mettant en jeu une interaction atome-champ non résonnante.

L'objet de ce travail est d'examiner et de comparer les différentes méthodes de mesures du déphasage résiduel de la cavité de Ramsey dans une horloge à jet de césium à pompage optique. <br> Dans ce but nous avons étudié et réalisé une horloge compacte à deux jets de césium. Dans la première partie du mémoire sont présentés le résonateur atomique de faible encombrement, et la cavité de Ramsey courte qui en est le c?ur. La cavité de Ramsey est une cavité micro-onde à deux zones d'interaction, rigoureusement réglée à 9,192 GHz. L'importance de ses propriétés est précisée, notamment l'influence du déphasage résiduel entre les deux zones d'interaction. <br> Puis l'étude théorique de ce déphasage et de ses conséquences sur les signaux délivrés par l'horloge - la frange de Ramsey et la fréquence d'horloge - est effectuée. Plusieurs méthodes de mesure de ce déphasage sont alors déduites de cette analyse. <br> La présentation des mesures du déphasage effectuées une fois le résonateur assemblé fait l'objet de la seconde moitié du manuscrit. La méthode traditionnelle appliquée à tous les étalons primaires de fréquence est la méthode par renversement de jet ; elle demeure dans notre résonateur compact la plus précise et la plus fiable. La seconde méthode utilisant des mesures de la fréquence d'horloge dans différentes conditions de fonctionnement s'avère délicate à appliquer sur une horloge compacte et ses limites sont analysées. <br> Finalement, les différents déplacements de fréquence significatifs sur ce type d'horloge font l'objet d'une étude expérimentale systématique. Un bilan de fréquence complet pour ce type d'horloge en est déduit. Le déplacement de fréquence dû au déphasage de la cavité reste l'effet limitatif pour l'exactitude en fréquence. On montre cependant que la seconde méthode de mesure permet d'obtenir une exactitude en fréquence inférieure à 10-12.

Le travail, présenté dans ce manuscrit, a consisté en l'élaboration et l'optimisation d'un dispositif expérimental dédié à la mesure de la violation de la parité (VP) dans les molécules chirales en jet supersonique. Les molécules envisagées qui sont en cours de synthèse, ont la propriété d'être à l'état solide à 300 K. Afin de pouvoir les mettre en jet, nous avons construit un dispositif permettant de réaliser la mise en phase vapeur par chauffage et leur ensemencement dans un gaz porteur. De plus, nous avons utilisé une technique de détection par temps de vol, afin d'estimer la quantité de molécules ensemencées. Nous avons testé notre dispositif avec le méthyltrioxorhénium (MTO) dont des dérivés chiraux sont en cours de synthèse. Nous avons mis au point une procédure expérimentale afin de déterminer les caractéristiques spectrales et les paramètres moléculaires du MTO. Pour cela, nous avons mesuré le spectre d'absorption saturée en cellule à 300 K. Puis, nous avons réalisé la mise en jet du MTO dans de l'hélium par chauffage et obtenu de très bons résultats, puisqu'une fraction molaire de MTO de ~10% a été mesurée. Enfin, nous avons enregistré le spectre d'absorption linéaire du MTO en jet sur le dispositif expérimental dédié à la mesure de la VP, notamment grâce à l'utilisation d'une cellule multi-passages. L'analyse des données nous a permis d'obtenir une simulation du spectre théorique. Ces résultats sont très prometteurs en vue des expériences sur les molécules chirales.