Dissertations / Theses on the topic 'NP'

Mestrado em Ciência e Engenharia de Materiais
For the design of drug delivery systems, in which a large amount of drug should be stored and released over a sustained period of time, utilization of nanostructures is frequently advantageous as their high specific surface areas are beneficial for adsorptive drug loading. Additionally, the use of nanostructured drug carriers in concert with polymeric materials in composite drug delivery systems affords control over the drug release characteristics. While many combinations of materials can be imagined, the use of zinc-oxide and poly(urethane) is of particular interest in that nanostructures based on the former are easily producible and the latter is already an established material in biomedical applications. In this investigation, various aspects of the drug delivery properties were examined. In particular, the effects of altering the amount of drug loaded (by loading in solutions of 1, 2, 10, and 20 mg ibuprofen/mL ethanol) were studied and it was demonstrated that the amount of drug loaded can be controlled, which is important for customizing dosages in drug delivery systems. Additionally, the role of a washing procedure after loading the nanoparticles was examined in order to show that these procedures influence the drug loading by removal of loosely bound layers of drug. In completion of this study, the release of ibuprofen from both pure zinc oxide nanoparticles and the composites with poly(urethane) was investigated by tracking the concentration of drug present in a phosphate buffered saline solution containing the drug carrier with respect to time. In order better understand the mechanisms of drug release and analyze the degradation processes of the drug carrier, SEM images were produced for the samples at various times during the drug release process.
Para projectar um sistema de entrega de fármacos, em que se pretende armazenar uma grande quantidade de fármaco a ser libertada durante um período de tempo longo, é vantajoso recorrer a nanoestruturas com elevada área específica para o carregamento do fármaco por processos adsortivos. Além disso, a combinação de transportadores nanoestruturados com materiais poliméricos, formando sistemas compósitos para a entrega de fármacos pode proporcionar o controlo de certos parâmetros associados à libertação do fármaco. Entre as várias combinações possíveis, o óxido de zinco (ZnO) e o poliuretano (PU) oferecem um particular interesse dado ser possível preparar ZnO nanoestruturado e o PU ser um polímero com reconhecida aptidão para aplicações médicas. Neste trabalho, estudaram-se vários aspectos do processo de libertação de um fármaco modelo (o ibuprofeno) a partir de nanoestruturas de óxido de zinco e de compositos ZnO/PU. Em particular, estudaram-se os efeitos da variação da carga do fármaco usando soluções etanólicas com diferentes concentrações do fármaco,i.e. 1, 2, 10, e 20 mg de ibuprofeno / mL de etanol, tendo-se demonstrado que por esta via se pode controlar a carga do fármaco , o que é importante para personalização da dose em sistemas de entrega de fármacos. Além disso, a importância dos procedimentos de lavagem das nanoestruturas após carregamento do fármaco foi também avaliada, concluindo-se que tais procedimentos condicionam a carga de fármaco por remoção das camadas de fármaco fracamente adsorvidas. Estudou-se também a libertação de ibuprofeno a partir das nanoestruturas de óxido de zinco puro e dos compositos ZnO/PU, medindo a variação no tempo da quantidade de fármaco libertada em solução tampão de fosfato. Os perfis de libertação do fármaco aliados às imagens de microscopia electrónica (SEM) dos materiais obtidas no fim de diferentes períodos de tempo de libertação são usados neste trabalho para discutir os mecanismos de libertação do fármaco e avaliar a sua relação com a degradação do material em análise.

Thema der Dissertation sind Nominalphrasen im Deutschen und Spanischen. Die Dissertation ist in 5 Abschnitte unterteilt. Das erste Kapitel gibt die Motivation der Arbeit, und im letzten Kapitel werden die Ergebnisse zusammengefasst und mögliche Erweiterungen diskutiert. Im zweiten Kapitel wird eine Einführung in den theoretischen Rahmen, die Head-Driven Phrase Structure Grammar (HPSG), gegeben und mit generativen Ansätzen verglichen. Dabei werden die Grundlagen und die Beschreibungsmechanismen der Theorie erklärt. HPSG ist ein oberflächenorientiertes, deklaratives, beschränkungsbasiertes Framework. Im dritten Kapitel werden vier zentrale syntaktische Begriffe besprochen und diskutiert: Kopf, Argument, Adjunkt und Spezifikator. Trotz ihrer Relevanz in der linguistischen Literatur werden diese vier Relationen verschieden interpretiert. Bei der Diskussion dieser syntaktischen Hauptrelationen werden die entsprechenden HPSG Mechanismen erklärt, mit denen sie beschrieben werden, u.a. das Semantik-Prinzip und das Kopfmerkmalsprinzip. Das vierte Kapitel der Dissertation beinhaltet Analysen für drei verschiedene Phänomene der NPs im Deutschen und Spanischen: Kasusmarkierung, optionale Argumente und pränominale Argumente. Deutsch und Spanisch unterscheiden sich in der Art und Weise, wie sie Kasus an ihren NPs markieren. Deutsch markiert sie morphologisch und Spanisch syntaktisch. Beide Arten der Markierung werden modelliert und verglichen. In Bezug auf die Optionalität von Argumenten wird zunächst die verbale Domäne betrachtet. Anhand dieser Analyse wird dann die nominale Domäne modelliert. Im letzten Teil wird eine Analyse für die pränominalen Argumente gegeben. Dabei werden folgende Aspekte betrachtet: Kombinatorik verschiedener Argumente, Theta-Rollenvergabe für die Argumente, Fakultativität der Argumente und Behandlung der (In-)Definitheit bei pränominalen Genitiven.
The topic of this dissertation are noun phrases in German and Spanish. This thesis is divided into five chapters. The first chapter presents the motivation of the work, and in the last chapter a summary is presented and discussed. In the second chapter, I give an introduction into the theoretical framework, Head-Driven Phase Structure Grammar (HPSG) by explaining its fundamental mechanisms, and compare it to generative approaches. HPSG is a surface oriented, declarative, constraint-based framework. In the third chapter, four central syntactic concepts are critically discussed: head, argument, adjunct, and specifier. Although these four concepts are highly relevant in the linguistic literature, they are often interpreted differently. While discussing these fours syntactic relations, I explain the main mechanisms of HPSG to describe them, e.g. the Semantic Principle and the Head Feature Principle. The fourth chapter contains analyses for three different NP phenomena in German and Spanish: case marking, optionality of arguments, and prenominal arguments. German and Spanish differ in the way they mark case on their NPs. German case-marks NPs morphologically, while case marking in Spanish is syntactic. Both types of marking are modelled and compared. Regarding argument optionality, I first look at the verbal domain and use this analysis to model optionality in the nominal domain. The last part of this chapter gives an analysis of prenominal arguments. The following aspects are considered: combinatory of a head noun with different arguments, theta role assignment for the arguments of a nominal head, optionality of arguments and treatment of (in-)definiteness in prenominal genitives.

SOFIA (Studies On FIssion with Aladin - Études de fission avec ALADIN) est un projet expérimental qui se propose de mesurer systématiquement les rendements isotopiques de fission, ainsi que l'énergie cinétique totale des fragments, pour une large gamme de noyaux fissionnants. Le travail de thèse présenté ici prend part au projet SOFIA, et a pour objet l'étude de la fission de noyaux dans la région des actinides : ²³⁴U, ²³⁵U, ²³⁷Np et ²³⁸Np.L'expérience SOFIA est menée au GSI, un accélérateur d'ions lourds situé à Darmstadt en Allemagne. Cette installation fournit un faisceau relativiste et intense d'uranium-238. Par une réaction de fragmentation de ce faisceau primaire, il est créé un faisceau secondaire contenant une large variété d'ions, dont, pour certains, la fission va être étudiée. Les ions de ce faisceau secondaire sont triés et identifiés dans le séparateur de fragments FRS, un spectromètre de recul de haute résolution qui est réglé pour sélectionner les ions d'intérêt.Ensuite, les ions fissiles sélectionnés continuent leur vol jusqu'à la Cave-C, une aire expérimentale où l'expérience de fission elle-même a lieu. À l'entrée de la cave, l'ion du faisceau secondaire est excité par interaction Coulombienne alors qu'il traverse une cible; les voies de dé-excitation possibles incluent la fission de basse énergie. Lors d'une fission, les deux fragments sont émis dans un cône étroit dans le référentiel du laboratoire, dû à l'impulsion relativiste qui leur est transmise par le système fissionnant. Un spectromètre de recul complet a été développé par la collaboration SOFIA autour du dipôle existant ALADIN. L'identification des fragments est réalisée par des mesures de perte d'énergie, de temps de vol et de déviation dans l'aimant. Les deux fragments de fission sont identifiés simultanément et complètement (en masse et en charge). Ce document présente l'analyse menée pour (1) l'identification du système fissionnant, (2) l'identification des deux fragments de fission - évènements par évènements -, et (3) l'extraction des observables de fission : rendements, énergie cinétique totale, multiplicité total en neutrons prompts. Ces résultats concernant les actinides sont discutés, et l'ensemble des données extraites est fourni
SOFIA (Studies On FIssion with Aladin) is an experimental project which aims at systematically measuring the fission fragments' isotopic yields as well as their total kinetic energy, for a wide variety of fissioning nuclei. The PhD work presented in this dissertation takes part in the SOFIA project, and covers the fission of nuclei in the region of the actinides : ²³⁴U, ²³⁵U, ²³⁷Np and ²³⁸Np.The experiment is led at the heavy-ion accelerator GSI in Darmstadt, Germany. This facility provides intense relativistic primary beam of 238U. A fragmentation reaction of the primary beam permits to create a secondary beam of radioactive ions, some of which the fission is studied. The ions of the secondary beam are sorted and identified through the FR-S (FRagment Separator), a high resolution recoil spectrometer which is tuned to select the ions of interest.The selected - fissile - ions then fly further to Cave-C, an experimental area where the fission experiment itself takes place. At the entrance of the cave, the secondary beam is excited by Coulomb interaction when flying through an target; the de-excitation process involves low-energy fission. Both fission fragments fly forward in the laboratory frame, due to the relativistic boost inferred from the fissioning nucleus.A complete recoil spectrometer has been designed and built by the SOFIA collaboration in the path of the fission fragments, around the existing ALADIN magnet. The identification of the fragments is performed by means of energy loss, time of flight and deviation in the magnet measurements. Both fission fragments are fully (in mass and charge) and simultaneously identified.This document reports on the analysis performed for (1) the identification of the fissioning system, (2) the identification of both fission fragments, on an event-by-event basis, and (3) the extraction of fission observables: yields, TKE, total prompt neutron multiplicity. These results, concerning the actinides, are discussed, and the set of data extracted is provided

Finite state methods for natural language processing often require the construction and the intersection of several automata. In this paper, we investigate the question of determining the best order in which these intersections should be performed. We take as an example lexical disambiguation in polarity grammars. We show that there is no efficient way to minimize the state complexity of these intersections.

Для обрахунку фаз одноканального нуклон-нуклонного розсіяння розглянуто відомий метод фазових функцій. У роботі в рамках J- матриці зворотної теорії розсіяння отримано хвильові функції спектроскопічних станів для моделей ISTP. Для порівняння значення хвильових функцій приведено у відн. од. Енергії взаємодії нуклонної системи становили Еlab=10; 50; 150 і 350 МеВ.

Питання про рівність класів P і NP займає центральне місце в сучасній теоретичній і практичній інформатиці серед задач з теорії алгоритмів. Це також одна з семи невирішених задач тисячоліття, розв’язання якої триває вже більше трьох десятиліть.

Le problème de la détermination de la qualité d’une solution partielle se pose dans la majeure partie des approches algorithmiques cherchant à calculer progressivement une solution globale. L’élagage des arbres de recherche, la preuve de garanties d’approximation et l’efficacité des stratégies d’énumération sont des approches algorithmiques qui exigent souvent un moyen approprié de décider si une solution partielle donnée est un bon candidat pour l’étendre à une solution globale de bonne qualité. Dans cette thèse, nous étudions un type particulier de problèmes d’optimisation, appelés problèmes d’extension pour un grand nombre de problèmes basés sur des graphes. Contredisant peut-être l’intuition, ces problèmes ont tendance à être NP-difficile, même quand le problème d’optimisation sous-jacent peut être résolu en temps polynomial. Nous présentons de nombreux résultats positifs et négatifs de NP-difficulté et d’approximation pour différents scénarios d’entrée. De plus, nous étudions la complexité paramétrée des problèmes d’extension par rapport à la taille des pré-solutions, ainsi que l’optimalité de certains algorithmes exacts sous l’hypothèse du temps exponentielle
The problem of determining the quality of a partial solution occurs in almost every algorithmic approach that gradually computes a global solution. Pruning search trees, proving approximation guarantees, or the efficiency of enumeration strategies usually require a suitable way to decide if a given partial solution is a reasonable candidate to pursue for extension to a global one, of assured quality. In this thesis, we study a special type of optimization problems, called extension problems for a large number of optimization problems on graphs. Possibly contradicting intuition, these problems tend to be NP-hard, even for problems where the underlying optimization problem can be solved in polynomial time. We present many positive/negative hardness and approximation results for different input scenarios. Moreover, the parameterized complexity of extension problems with respect to size of partial solutions, as well as the optimality of some exact algorithms under the Exponential-Time Hypothesis (ETH) are studied

The purpose with this paper is to give an overview of the P ≟ NP problem and explore the impact of the three possible solutions on our computerized society. We will, inter alia, go through the P ≟ NP problems  importance, beliefs about the problem and essential concepts.
Syftet med uppsatsen är att ge en översiktlig bild av P ≟ NP problemet och redogöra kring problemets tre möjliga lösningar samt vad dessa skulle innebära för vårt datoriserade samhälle. Vi kommer bland annat att gå igenom P ≟ NP problemets betydelse, tro kring problemet och relevanta begrepp.

In this paper, we show how the theory of NP completeness can be introduced to students in secondary schools. The motivation of this research is that although there are difficult issues that require technical backgrounds, students are already familiar with demanding computational problems through games such as Sudoku or Tetris. Our intention is to bring together important concepts in the theory of NP completeness in such a way that students in secondary schools can easily understand them. This is part of our ongoing research about how to teach fundamental issues in Computer Science in secondary schools. We discuss what needs to be taught in which sequence in order to introduce ideas behind NP completeness to students without technical backgrounds.

Cette these est consacree a l'etude des liens entre le temps lineaire et les problemes np-complets. Nous etudions tout d'abord les reductions lineaires entre problemes np-complets et les classes d'equivalence qu'elles induisent. De nombreux problemes sont montres etre lineairement equivalents a la satisfaisabilite. Dans ce cadre une methode uniforme pour prouver la np-completude est developpee. Elle est centree sur un probleme cle: la 3-colorabilite. Deux autres classes d'equivalence sont mises en evidence, l'une contenant dominating set et l'autre max-2sat. Cette derniere met en jeu des problemes d'optimisation et permet de montrer que divers problemes tels max-sat, max-2sat, min-2sat et simple max-cut sont lineairement equivalents. Nous proposons finalement de nouveaux problemes nlinear-complets, c'est-a-dire complets pour le temps lineaire non deterministe. Nous obtenons ainsi une borne inferieure non triviale de complexite pour chacun d'entre eux. Ces problemes portent sur les graphes orientes et non orientes

A Theory of Algorithms course is essential to any Computer Science curriculum at both the undergraduate and graduate levels. It is also considered to be difficult material to teach or to learn. In particular the topics of Computational Complexity Theory, reductions, and the NP-Complete class of problems are considered difficult by students. Numerous algorithm visualizations (AVs) have been developed over the years to portray the dynamic nature of known algorithms commonly taught in undergraduate classes. However, to the best of our knowledge, the instructional material available for NP-Completeness is mostly static and textual, which does little to alleviate the complexity of the topic. Our aim is to improve the pedagogy of NP-Completeness by providing intuitive, interactive, and easy-to-understand visualizations for standard NP Complete problems, reductions, and proofs. In this thesis, we present a set of visualizations that we developed using the OpenDSA framework for certain NP-Complete problems. Our paradigm is a three step process. We first use an AV to illustrate a particular NP-Complete problem. Then we present an exercise to provide a first-hand experience with attempting to solve a problem instance. Finally, we present a visualization of a reduction as a part of the proof for NP-Completeness. Our work has been delivered as a collection of modules in OpenDSA, an interactive eTextbook system developed at Virginia Tech. The tutorial has been introduced as a teaching supplement in both a senior undergraduate and a graduate class. We present an analysis of the system use based on records of online interactions by students who used the tutorial. We also present results from a survey of the students.
Master of Science

This is a study of topicalization (OSV) and object preposing (SOV) in Mandarin Chinese. Whether topics in Mandarin are base-generated or derived by movement has been controversial. We provide a detailed discussion and show that they are derived by movement. Topicalization in Mandarin is generally assumed to be A'-movement. Based on Mahajan's (1990) criteria, we however find that it may be A or A'-movement for it exhibits reconstruction effects, lacks WCO effects and topics can bind anaphors. Yet we still argue that it is uniformly A'-movement based on the logophoric analysis of anaphor binding and the reconstruction effects. We explain the lack of WCO effects by adding the constraint "a trace v is a formal variable if the chain is triggered by a (+wh) / (+quant) feature" to Higginbotham' s (1983) Accessibility Condition. Topic traces are thus classified as A'-anaphors for topicalization is triggered by (+topic). With this feature-based definition, we admit a third type of position--A'-positions may be operator or non-operator positions, depending on the features they host. Topics in Mandarin are normally assumed to move to IP-adjunct position. We however suggest that they move to (Spec, CP) because: topicalization is triggered by the topic feature, the occurrence of an embedded topic depends on the verb that selects the embedded clause, and no topic is allowed after an adjunct complementizer. Object preposing in Mandarin is assumed to be movement to adjunct positions in some studies. We however find it movement to specifier positions because it is an A-movement triggered by the focus feature. We suggest that the preposed object lands on (Spec, ModalP) or (Spec, VP). We divide the preposed objects into (+C-focus) and (+focus) objects; (+C-focus) objects have emphatic markers or contrastive conjuncts but (+focus) objects do not. The focus features reside in Modal or V to trigger object preposing, with selectional restrictions; e.g., modals only select verbs with (+C-focus), which explains why objects in (Spec, VP) must have emphatic markers or contrastive conjuncts. Related phenomena such as clause-boundness of object preposing are also discussed.

The aim of this study was to examine the mechanisms of transcription and replication of the paramyxovirus, simian virus type 5 (SV5). This was initially attempted using reverse genetics techniques and subsequently examining specific viral protein: protein interactions within the replication complex. A cDNA clone encoding a synthetic negative-sense RNA genome analogue was constructed. Reverse genetics techniques were used to attempt to characterise conditions which supported the transcription and replication of this genome analogue, with or without the use of wild-type helper virus but were unsuccessful. During the course of these studies, a number of mammalian cell lines inducibly expressing SV5 proteins were isolated. These cell lines were subsequently used to examine viral protein: protein interactions within the replication complex. When expressed alone, both P and V proteins exhibited diffuse cytoplasmic fluorescence and V was also found in the nucleus. However, when NP was expressed alone, it was seen as punctate and granular cytoplasmic fluorescence. The distribution patterns of the proteins changed when expressed in combination. Large cytoplasmic aggregates similar to those at late times in an SV5 infection were seen in cells which co-expressed NP and P. When NP was co-expressed with V, however, NP was partially redistributed to give diffuse cytoplasmic and nuclear fluorescence. This showed that both P and V proteins could interact with NP and suggested that V may play a role in keeping NP soluble prior to an ordered encapsidation process. Extracts from these cell lines were then used in a novel protein: protein capture assay and demonstrated that NP could interact with both P and V proteins. NP expressed by the cell line was shown to contained both soluble and polymeric forms of NP. P was shown to bind both forms of NP, while V could only bind soluble NP. Since P and V proteins are amino co-terminal, the site of interaction between P and polymeric NP was predicted to be in the P unique C-terminus. This was strengthened when a P-specific C- terminal mAb was found to block the binding of P with polymeric NP. Deletion mutant analysis in the C-terminus of the P protein showed that the mAb binding site was at the extreme C-terminus of the protein suggesting this is the point of interaction between P and polymeric NP. Possible roles for these protein: protein interactions and implications for the paramyxovirus replication complex are discussed.

This thesis on propositional proof systems and disjoint NP-pairs gives a survey of these fields. We present history and motivation of both theories by giving examples for their use. The reader is then introduced into the formal notions of the fields. Dedicated chapters present important and outstanding results from the theories. Some results are proven, some results are given without a proof. It follows a chapter that presents the relation of both fields with a result due to Razborov. As for none of the assertions in this thesis the absolute truth value is known, we also survey some oracles relative to which we know the truth value of important statements. We finally look into open questions and suggest future work on both fields.

This thesis is a structural analysis of the DP in Irish. The thesis is based on analysis of a number of different types of noun phrases and a consideration of the observed patterns in relation to other languages and syntactic theory in general. The proposal accounts for the typical data that has been analysed previously in the literature as well as novel data not yet accounted for within existing analyses. As well as providing a full structural account of the Irish NP, the findings of this thesis provide evidence in Support of the universal existence of a number of functional projections, which have been shown to be projected for language in general.

Le developpement de la theorie des modeles finis a favorise une nouvelle approche de la notion de complexite algorithmique. L'identification des problemes combinatoires a des ensembles de structures finies a en effet permis l'interpretation des classes de complexite en terme de langages logiques. Nous prouvons dans ce cadre l'inclusion de la classe nlin des problemes reconnaissables en temps lineaire sur ram non deterministes dans la logique du second ordre monadique existentiel avec addition. Ceci permet d'affirmer la caracterisation par cette logique de la plupart des problemes np-complets usuels. Puis nous montrons qu'en presence du successeur, les classes de structures nlin coincident avec les ensembles de modeles des formules du second ordre existentiel fonctionnel unaire comportant une unique variable du premier ordre quantifiee universellement, et dont la matrice est une simple conjonction d'egalites. Cette caracterisation purement conjonctive, a bien des egards optimale, se generalise au temps polynomial. Enfin nous etablissons l'identite des langages rudimentaires et des langages caracterises par une formule du second ordre monadique. Nous obtenons en corollaire un resultat de representation des spectres en termes d'ensembles d'entiers rudimentaires

The thesis focuses on the attractiveness of the Šumava National Park. Basic terminology within tourism or rather attractiveness of the tourist destination is discussed. There are four different approaches for measuring the attractiveness of the tourist destination. There was chosen one model based on an economic approach in this thesis. The main goal was to calculate the attractiveness of this region and to compare it with the results of other tourists destinations in the Czech republic.

No estudo da complexidade de problemas computacionais destacam-se duas classes conhecidas como P e NP. A questao P=NP e um dos maiores problemas nao resolvidos em Ciencia da Compu- tacao teorica e Matematica contemporanea. O problema SAT foi o primeiro problema reconhecido como NP-completo e consiste em verificar se uma determinada formula da logica proposicional clas- sica e ou nao satisfazivel. As implementacoes de algoritmos para resolver problemas SAT sao conhe- cidas como resolvedores SAT (SAT Solvers). Existem diversas aplicacoes em Ciencia da Computacao que podem ser realizadas com SAT Solvers e com outros resolvedores de problemas NP-completos que podem ser reduzidos ao SAT como por exemplo problemas de coloracao de grafos, problemas de agendamento e problemas de planejamento. Dentre os mais eficientes algoritmos para resolvedores de SAT estao Sato, Grasp, Chaff, MiniSat e Berkmin. O Algoritmo Chaff e baseado no Algoritmo DPLL o qual existe a mais de 40 anos e e a estrategia mais utilizada para os Sat Solvers. Essa dissertacao apresenta um estudo aprofundado do comportamento do zChaff (uma implementacao muito eficiente do Chaff) para saber o que esperar de suas execucoes em geral .
In the study of computational complexity stand out two classes known as P and NP. The question P = NP is one of the greatest unsolved problems in theoretical computer science and contemporary mathematics. The SAT problem was first problem recognized as NP-complete and consists to check whether a certain formula of classical propositional logic is satisfiable or not. The implementations of algorithms to solve SAT problems are known as SAT solvers. There are several applications in computer science that can be performed with SAT solvers and other solvers NP- complete problems can be reduced to SAT problems such as graph coloring, scheduling problems and planning problems. Among the most efficient algorithms for SAT solvers are Sato, Grasp, Chaf, MiniSat and Berkmin. The Chaff algorithm is based on the DPLL algorithm which there is more than 40 years and is the most used strategy for Sat Solvers. This dissertation presents a detailed study of the behavior of zChaff (a very efficient implementation of the Chaff) to know what to expect from their performance in general.

Le neptunium 237 est un radionucleide a vie longue (2,14 10#6 ans) concerne par le programme spin, mis en place par le cea afin de repondre a la loi du 30 decembre 1991, en vue d'une meilleure gestion des dechets nucleaires. L'objectif etant de separer totalement le neptunium afin de le gerer, il a ete decide d'oxyder quantitativement np(5) (non extractible) en np(6) (fortement extractible), sans pour autant perturber les autres elements presents et en particulier le plutonium qui doit rester a son degre d'oxydation +4. La voie retenue est une adaptation des parametres operatoires du procede purex, qui est actuellement le procede de retraitement des combustibles nucleaires. Dans ce but, il a ete decide d'entreprendre une etude a caractere fondamental des reactions d'oxydation du np(5) en np(6) et surtout de reduction du np(6) en np(5), cette derniere n'ayant, a notre connaissance, fait l'objet d'aucune publication. Cette etude se divise en deux parties, une etude thermodynamique et une etude cinetique en utilisant le concept des activites des especes pour l'interpretation de l'ensemble des resultats, afin de mieux prendre en compte les effets de milieux preponderants dans ces solutions concentrees. Les resultats thermodynamiques ont demontre l'obtention d'un seul et unique equilibre caracterise par une constante d'equilibre egale a 6,7 10#-#4 met des grandeurs thermodynamiques d'oxydation et de reduction, telles que l'enthalpie et l'entropie, ont ete determinees. Les donnees cinetiques ont permis l'obtention des lois de vitesse d'oxydation de np(5) et de reduction de np(6), ainsi que les energies, enthalpies, enthalpies libres et entropies d'activation d'oxydation et de reduction. Enfin, un mecanisme reactionnel a ete propose. Cette etude a permis de confirmer l'interet de l'approche des phenomenes par le concept des activites des especes pour une meilleure maitrise du comportement du neptunium. Elle devrait de plus permettre d'envisager une amelioration sensible de la modelisation du neptunium lors du premier cycle d'extraction du procede purex

Thesis: S.M., Massachusetts Institute of Technology, Department of Electrical Engineering and Computer Science, 2016.
Cataloged from PDF version of thesis.
Includes bibliographical references (pages 17-19).
The possibility of basing the security of cryptographic objects on the (minimal) assumption that NP ... BPP is at the very heart of complexity-theoretic cryptography. Most known results along these lines are negative, showing that assuming widely believed complexity-theoretic conjectures, there are no reductions from an NP-hard problem to the task of breaking certain cryptographic schemes. We make progress along this line of inquiry by showing that the security of single-server single-round private information retrieval schemes cannot be based on NP-hardness, unless the polynomial hierarchy collapses. Our main technical contribution is in showing how to break the security of a PIR protocol given an SZK oracle. Our result is tight in terms of both the correctness and the privacy parameter of the PIR scheme.
by Tianren Liu.
S.M.

Orientador: Arnaldo Vieira Moura
Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Matemática, Estatística e Computação Científica
Made available in DSpace on 2018-08-16T09:31:55Z (GMT). No. of bitstreams: 1 Oliveira_IgorCarboni_M.pdf: 1109272 bytes, checksum: 3ab44664e4e0b862409cc8038c431a06 (MD5) Previous issue date: 2010
Resumo: A teoria de complexidade computacional procura estabelecer limites para a eficiência dos algoritmos, investigando a dificuldade inerente dos problemas computacionais. O problema P vs NP é uma questão central em complexidade computacional. Informalmente, ele procura determinar se, para uma classe importante de problemas computacionais, a busca exaustiva por soluções é essencialmente a melhor alternativa algorítmica possível. Esta dissertação oferece tanto uma introdução clássica ao tema, quanto uma exposição a diversos teoremas mais avançados, resultados recentes e problemas em aberto. Em particular, o método da diagonalização é discutido em profundidade. Os principais resultados obtidos por diagonalização são os teoremas de hierarquia de tempo e de espaço (Hartmanis e Stearns [54, 104]). Apresentamos uma generalização desses resultados, obtendo como corolários os teoremas clássicos provados por Hartmanis e Stearns. Essa é a primeira vez que uma prova unificada desses resultados aparece na literatura
Abstract: Computational complexity theory is the field of theoretical computer science that aims to establish limits on the efficiency of algorithms. The main open question in computational complexity is the P vs NP problem. Intuitively, it states that, for several important computational problems, there is no algorithm that performs better than a trivial exhaustive search. We present here an introduction to the subject, followed by more recent and advanced results. In particular, the diagonalization method is discussed in detail. Although it is a classical technique in computational complexity, it is the only method that was able to separate strong complexity classes so far. Some of the most important results in computational complexity theory have been proven by diagonalization. In particular, Hartmanis and Stearns [54, 104] proved that, given more resources, one can solve more computational problems. These results are known as hierarchy theorems. We present a generalization of the deterministic hierarchy theorems, recovering the classical results proved by Hartmanis and Stearns as corollaries. This is the first time that such unified treatment is presented in the literature
Mestrado
Teoria da Computação
Mestre em Ciência da Computação

In the 1970's computer scientists developed the theory of computational complexity. Some problems seemed hard-to-compute, while others were easy. It turned out that many of the hard problems were equally hard in a way that could be precisely specified. They became known as the NP-complete problems. The SATISFIABILITY problem (SAT) was the first problem to be proved NP-complete in 1971. Since then numerous other hard-to-solve problems have been proved to be in NP-complete. In this paper we will examine the problem of how to find a maximum independent set of vertices for a graph. This problem is known as Maximum Independent Set (MIS) for a graph. The corresponding decision problem for MIS is the question, given an integer K, is there a independent set with at least K vertices? This decision problem is INDEPENDENT SET (IS). The intention of this paper is to show through polynomial transformation that IS is in the set of NP-complete Problems. We intend to show that 3SAT is NP-complete and then using this fact, that IS is NP-complete.

This thesis furthers our understanding of the canonical quadrupolar system UPd. which is unusual and interesting for several reasons. It is the only known localised uranium intermetallic. it exhibits long range quadrupolar or der, and it has four phase transitions below 8 K attributed to a succession of different quadrupolar orderings of the of'2 uranium electrons. The two strate gies used in this work are: probing the quadrupolar order directly using X-ray resonant scattering, to determine the order parameters, and investigating how the quadrupolar order is perturbed by the substitution of neptunium for ura nium through bulk thermodynamic measurements. This is the first time that the symmetry of the quadrupolar order in lPd i has been examined directly, making use of the unique properties of X-ray resonant scattering, which couples directly to the quadrupoles as opposed to neutrons which only couple to the induced lattice distortions. We have4 been able to ascertain, through a detailed comparison between calculations and experimental data, that the T() = 7.8 K transition is to a quadrupolar or dered phase described by the anti-phase stacking of Q/x quadrupoles along the r axis. This, in combination with new high precision low temperature heat capacity measurements, has enabled us to place constraints on the quadrupolar operators within the crystal field model. We have also investigated the order- ing in two of the lower temperature phases, and shown that the scattering corresponds to a more complex model. We have also investigated XpPd i by measurements of the electrical resis tivity, magnetic susceptibility and heat capacity, and demonstrated that it undergoes two phase transitions, one antiferromagnetic and the other possibly quadrupolar. In the dilute neptunium region of (U.Xp)Pd3 we have followed the lowering of the transition temperatures with increasing neptunium con tent, and shown that several observed features of (Uo.9oXpo.oo)Pd3 are con sistent with proximity to a quantum critical point, which we have associated with the suppression of a quadrupolar transition to zero temperature. This preliminary work has indicated that there is considerably more scope for inves tigating the (Ui_.rXp.r)Pd3 system to identify a new type of quantum critical point associated with the "squeezing out" of quadrupolar order.

Le type de liaison et la structure cristalline sont etroitement lies au degre de localisation des electrons 5f. Un des facteurs determinant du degre de localisation des electrons 5f est la distance interactinide. L'action des hautes pressions sur un solide provoque un rearrangement electronique et structural. Observation par diffraction rx des transitions de phase cristallographiques induites par la pression. Ces transitions peuvent etre significatives de la defocalisation des electrons 5f, dans le cas des actinides. Construction a partir de ces resultats du diagramme de phase

Les premiers algorithmes exacts exponentiels pour résoudre des problèmes NP-difficiles datent des années soixante. Ces dernières années ont vu un intérêt croissant pour la conception de tels algorithmes tout comme pour l'amélioration de la précision de l'analyse de leur temps d'exécution. Ils sont motivés par les larges applications de problèmes réputés difficiles et qui, sous l'hypothèse P 6= NP, n'admettent pas d'algorithme polynomial en calculant une solution exacte. Dans cette thèse on s'intéresse au problème classique de la domination dans un graphe. On étudie également plusieurs variantes et généralisations de ce problème fondamental. Nous proposons des algorithmes exponentiels pour déterminer un ensemble dominant de taille minimum sur les graphes c-denses, cordaux, 4-cordaux, faiblement cordaux, cercles et bipartis. Puis, nous étudions le problème de la clique dominante qui demande de trouver un ensemble dominant qui soit aussi une clique du graphe. Nous proposons un algorithme Brancher & Réduire qui détermine une clique dominante de taille minimum. L'analyse du temps d'exécution est réalisée en utilisant la technique Mesurer pour Conquérir. Nous donnons ensuite un algorithme général pour énumérer tous les ensembles ( %)-dominants d'un graphe en temps O(cn), avec c < 2, sous certaines conditions sur les ensembles et %, et établissons une borne supérieure combinatoire sur leur nombre. Finalement, nous nous intéressons à un problème de domination partielle et obtenons un algorithme pour le problème de la domination romaine. Grâce à un algorithme basé sur le paradigme de la Programmation Dynamique, nous proposons un algorithme pour le problème de la domination avec des puissances variables
The first exact exponential-time algorithms solving NP-hard problems date back to the sixties. The last years have seen an increasing interest for designing such algorithms as well as analysing their running time. The existence of many applications of well known hard problems is one of the main motivations. Moreover, under the hypothesis P 6= NP, apolynomial time algorithm for these problems does not exist. In this thesis, we deal with the classical domination problem in graphs. We are also interested in some variants and generalizations of this fondamental problem. We give exponential-time algorithms for computing a minimum dominating set on c-dense graphs, chordal graphs, 4-chordal graphs, weakly chordal graphs, circle graphs and bipartite graphs. Then, we study the dominating clique problem requiring to find a minimum dominating set inducing a clique of the graph. We provide a Branch & Reduce algorithm computing a minimum dominating clique. The analysis of the running time is done by using the Measure and Conquer technique. Afterwards, we propose a general algorithm for enumerating all (%)-dominating sets of a graph in time O(cn), with c < 2, under some assumptions on the sets and %. Subsequently, we establish a combinatorial upper bound on the number of such sets in a graph. Finally, we consider a partial dominating set problem and we give an algorithm for solving the Roman domination problem. Using the dynamic programming paradigm, we obtain an algorithm for the domination problem with flexible powers

C'est d'abord à partir du poème Beowulf, mais aussi en recourant à de nombreuses autres sources latines et vernaculaires - poèmes, récits, sermons, lois, chartes, mais aussi images et surtout archéologie - que j'ai tenté d'écrire une "histoire politique du festin" dans la partie orientale de l'île de Grande-Bretagne entre le départ des légions romaines et la Conquête normande. La thèse se compose de quatre parties : une partie introductive considérant les sources, les modèles théoriques, l'environnement historique et géographique et les enjeux du sujet ; une étude des temps, des acteurs, les lieux et de la matière même des festins ; une exploration de deux questions plus spécifiques - la sacralité du festin et les identités alimentaires - ; une tentative de synthèse chronologique permettant de dégager, au VIIe siècle, une période de "classicisme" qui vit la mise en place d'une idéologie politique centrée sur le festin, et autour de laquelle s'organise notre histoire du festin

Computer and Information Science
Ph.D.
The set cover problem, weighted set cover problem, minimum dominating set problem and minimum weighted dominating set problem are all classical NP-hard optimization problems of great importance in both theory and real applications. Since the exact algorithms, which require exhaustive exploration of exponentially many options, are infeasible in practice, approximation algorithms and heuristic algorithms are widely used to find reasonably good solutions in polynomial time. I propose novel algorithms for these problems. My algorithms for the weighted set cover and minimum weighted dominating set problems are based on a three-step strategy. For the weighted set cover problem, in the first step, we reserve the sets indispensable for the optimal solution and reduce the problem size. In the second step, we build a robust solution with a novel greedy heuristic. Sets are iteratively selected according to a measure which integrates the weight, the coverage gain for the current iteration and the global coverage capacity of each set. It favors the sets that have smaller weights and better extend or consolidate the coverage, especially on the items that are contained in less sets. Since the obtained solution tends to have a robust coverage, in the third step, we further improve it by removing the redundant sets in an efficient way. For the minimum weighted dominating set problem, we first reserve the indispensable vertices for the optimal solution. Then we convert it into a weighted set cover problem to solve it. These two algorithms can be used to solve the set cover problem and minimum dominating set problem by simply considering all the sets or vertices as having the same weights. Extensive experimental evaluations on a large number of synthetic and real-world set cover instances and graphs from many domains demonstrate the superiority of my algorithms over state-of-the-art. Cluster analysis is a fundamental problem in data analysis, and has extensive applications in artificial intelligence, statistics and even in social sciences. The goal is to partition the data objects into a set of groups (clusters) such that objects in the same group are similar, while objects in different groups are dissimilar. Most of the existing algorithms for clustering are designed to handle data with only one type of attributes, e.g. continuous, categorical or ordinal. Mixed data clustering has received relatively less attention, despite the fact that data with mixed types of attributes are common in real applications. I propose a novel affinity learning based framework for mixed data clustering, which includes: how to process data with mixed-type attributes, how to learn affinities between data points, and how to exploit the learned affinities for clustering. In the proposed framework, each original data attribute is represented with several abstract objects defined according to the specific data type and values. Each attribute value is transformed into the initial affinities between the data point and the abstract objects of attribute. I refine these affinities and infer the unknown affinities between data points by taking into account the interconnections among the attribute values of all data points. The inferred affinities between data points can be exploited for clustering. Alternatively, the refined affinities between data points and the abstract objects of attributes can be transformed into new data features for clustering. Experimental results on many real world data sets demonstrate that the proposed framework is effective for mixed data clustering. This work was published in our IJCAI 2017 paper Li & Latecki (2017). Clustering aggregation, also known as consensus clustering or clustering ensemble, aims to find a single superior clustering from a number of input clusterings obtained by different algorithms with different parameters. I formulate clustering aggregation as a special instance of the maximum-weight independent set (MWIS) problem. For a given data set, an attributed graph is constructed from the union of the input clusterings. The vertices, which represent the distinct clusters, are weighted by an internal index measuring both cohesion and separation. The edges connect the vertices whose corresponding clusters overlap. Intuitively, an optimal aggregated clustering can be obtained by selecting an optimal subset of non-overlapping clusters partitioning the data set together. I formalize this intuition as the MWIS problem on the attributed graph, i.e., finding the heaviest subset of mutually non-adjacent vertices. This MWIS problem exhibits a special structure. Since the clusters of each input clustering form a partition of the dataset, the vertices corresponding to each clustering form a maximal independent set (MIS) in the attributed graph. I propose a variant of simulated annealing method that takes advantage of this special structure. My algorithm starts from each MIS, which is close to a distinct local optimum of the MWIS problem, and utilizes a local search heuristic to explore its neighborhood in order to find the MWIS. Extensive experiments on many challenging data sets show that both my algorithm for the maximum-weight independent set problem and my approach to the application of clustering aggregation achieve good performance. This work was published in our NIPS 2012 paper Li & Latecki (2012). Some new results were published in our IJCAI 2017 paper Fan et al. (2017).
Temple University--Theses

Nous détaillons dans cette thèse des algorithmes modérément exponentiels pour l'approximation du problème MAX SAT. Nous discutons d'une méthode générique pour la conception d'algorithmes exponentiels réalisant des schémas d'approximation dans un cadre plus général. Enfin, nous présentons des résultats paramétrés pour des problèmes de coupe à cardinalité contrainte.

L'étude expérimentale d'algorithmes est un sujet crucial dans la conception de nouveaux algorithmes, puisque le contexte d'évaluation influence inévitablement la mesure de la qualité des algorithmes. Le sujet particulier qui nous intéresse dans l'étude expérimentale est la pertinence des instances choisies pour servir de base de test à l'expérimentation. Nous formalisons ce critère par la notion de "difficulté d'instance" qui dépend des performances pratiques de méthodes de résolution. Le coeur de la thèse porte sur un outil pour évaluer empiriquement la difficulté d'instance. L'approche proposée présente une méthode de benchmarking d'instances sur des jeux de test d'algorithmes. Nous illustrons cette méthode expérimentale pour évaluer des classes d'instances à travers plusieurs exemples d'applications sur le problème du voyageur de commerce. Nous présentons ensuite une approche pour générer des instances difficiles. Elle repose sur des opérations qui modifient les instances, mais qui permettent de retrouver facilement une solution optimale, d'une instance à l'autre. Nous étudions théoriquement et expérimentalement son impact sur les performances de méthodes de résolution.

Ce travail se situe dans le cadre de la resolution de problemes d'optimisation par des methodes deterministes et/ou stochastiques. Les problemes poses sont np-difficiles. Les methodes deterministes et les divers algorithmes de type recuit simule sont presentes. Un algorithme nouveau (dit du kangourou) est propose et sa convergence est demontree. Deux resultats de convergence sont etablis pour les algorithmes genetiques. Des algorithmes de type recuit simule applicables a la minimisation d'une fonction aleatoire sont donnes, leur convergence est demontree. Les divers couplages possibles entre ces methodes sont etudies. Les problemes du flow-shop et a une machine sont resolus numeriquement par diverses methodes. Les algorithmes stochastiques sont appliques a plusieurs problemes reels: job-shop avec transport, placement de conteneurs, habillage des services (ou nous appliquons un algorithme du kangourou cooperant avec une methode de programmation lineaire)

L'hypothèse qu'un grand nombre de problèmes n'admettent pas d'algorithme (exact et déterministe) polynomial date de l'avènement de la théorie de la NP-complétude dans les années 70. Depuis, de nombreuses théories et techniques algorithmiques se sont développées pour résoudre ces problèmes difficiles le plus efficacement possible. Dans cette thèse, nous nous intéressons aux algorithmes exacts faiblement exponentiels. L'objectif est d'obtenir des algorithmes de complexité 0* (c^n) où n est la taille de la donnée et c une Constante la plus faible possible
The assumption that many problems do not admit algorithm (exact and deterministic) polynomial ate of the advent of the theory of NP-completeness in the 70s. Since many theories and algorithmic techniques have been developed to solve these problems difficult as efficiently as possible. In this thesis, we focus on exact algorithms weakly exponential. The objective is to obtain algorithms complexity 0 * (c ^ n) where n is the size of the data and one constant c as small as possible

Thesis (MMath)--University of Waterloo, 2004.
"A thesis presented to the University of Waterloo in fulfillment of the thesis requirements for the degree of Master of Mathematics in Computer Science." Includes bibliographical references.

Die Endlagerung von radioaktivem Abfall ist eine der vordringlichsten Aufgaben auf dem Gebiet der Kerntechnik. Als Teil der Sicherheitsanforderungen steht dabei der Schutz von Mensch und Umwelt vor den Gefahren der radioaktiven Stoffe selbst im Falle einer Freisetzung dieser Stoffe aus dem Endlager im Vordergrund. Als Basis für Langzeitsicherheitsanalysen dienen Modellierungen. Für diese sind umfassende Kenntnisse der chemisch-physikalischen Effekte und Einflüsse, die eine Mobilisierung und den Transport der Actiniden bewirken können, erforderlich. Diese Arbeit war ein eigenständiger Teil eines Projektes, welches sich mit der Aufklärung des Einflusses von Mikroorganismen auf die Ausbreitung von Actiniden bei einer Freisetzung dieser aus dem Endlager beschäftigt. Dabei wurde der Einfluss von mikrobiell produzierten Substanzen auf die Mobilisierung ausgewählter Actiniden untersucht. Die in diesem Projekt untersuchten mikrobiell produzierten Substanzen, sogenannte Bioliganden, wurden von Bakterien des Genus Pseudomonas unter speziellen Bedingungen produziert. Die von den Pseudomonaden freigesetzten Bioliganden, hier Siderophore vom Pyoverdin-Typ, haben ein hohes Potential, Metalle, insbesondere Eisen(III), zu komplexieren und so zu transportieren. Es wurde untersucht, in welcher Weise und unter welchen Bedingungen diese Bioliganden in der Lage sind, auch radioaktive Schadstoffe zu komplexieren und damit zu mobilisieren. Für die Untersuchungen wurden die α-strahlenden Actiniden Uran, Curium und Neptunium ausgewählt, weil diese auf Grund ihrer Langlebigkeit und Radiotoxizität von besonderem Interesse sind. Diese Arbeit beschäftigte sich mit der Wechselwirkung der Actiniden U(VI), Np(V) und Cm(III) mit Modellliganden, die die Funktionalitäten der Pyoverdine simulieren. Für die Metallbindung der Pyoverdine sind die Katecholgruppe des Chromophors und die funktionellen Gruppen der Peptidkette (Hydroxamsäuregruppen und α-Hydroxysäurereste) verantwortlich. Für die Simulation der Hydroxamsäuregruppen kamen dabei die Monohydroxamate Salicylhydroxamsäure (SHA) und Benzohydroxamsäure (BHA) und das natürliche Trihydroxamat Desferrioxamin B (DFO) zum Einsatz und für die Katecholgruppe das 6-Hydroxychinolin (6HQ) und 2,3-Dihydroxynaphthalin (NAP). Als Vergleichsligand wurde außerdem Benzoesäure (BA) untersucht. Für die Bestimmung der Stabilitätskonstanten zur Einschätzung der Stärke der gebildeten Komplexe, die Aufklärung der Struktur der Actinid-Ligand-Verbindungen und die Verfolgung der Änderung der Speziation der Actiniden vor und nach der Wechselwirkung mit den Modellliganden kamen verschiedene spektroskopische Verfahren wie Absorptionsspektroskopie, Laserfluoreszenzspektroskopie, Röntgenabsorptionsspektroskopie und Schwingungsspektroskopie zum Einsatz. Außerdem wurden erstmals theoretische Modellierungen zur Aufklärung der Struktur der Actinid-Modellligand-Komplexe durchgeführt. Die Ziele dieser Arbeit waren also die spektroskopische Charakterisierung und Bestimmung der Speziation und Komplexbildungskonstanten sowohl der ausgewählten Modellliganden als auch der gebildeten Actinid-Modellligand-Komplexe, die Aufklärung möglicher Strukturen der Komplexe sowie ein Vergleich der Ergebnisse mit denen der Pyoverdine. Der Vergleich der Stabilitätskonstanten der untersuchten Liganden mit den drei Actiniden U(VI), Cm(III) und Np(V) ergab im Wesentlichen folgende Reihenfolge der Komplexstärke: PYO ≥ DFO &gt; NAP &gt; 6HQ &gt; SHA ≥ BHA &gt; BA. Benzoesäure (hier wurde nur die Komplexbildung mit U(VI) untersucht) besitzt als einziger Ligand eine Carboxylfunktionalität und weist mit 103 die geringste Stabilitätskonstante auf. Die beiden Monohydroxamate SHA und BHA bilden mit allen drei Actiniden ähnlich starke 1:1-Komplexe. Bei den 1:2-Komplexen besitzt SHA mit Cm(III) und Np(V) etwas höhere Stabilitätskonstanten als BHA, wahrscheinlich verursacht durch einen stabilisierenden Einfluss der zusätzlichen phenolischen OH-Gruppe. Dieser Trend wurde auch in den theoretischen Modellierungen für die U(VI)-Komplexe beobachtet. Die natürlichen Siderophore DFO und PYO bilden die stärksten Komplexe mit den Actiniden (Stabilitätskonstanten von 1012 bis 1034). Dies liegt in der Struktur und der hohen Anzahl an funktionellen Gruppen begründet; DFO besitzt drei Hydroxamatgruppen, das Pyoverdinmolekül neben den Hydroxamatgruppen noch die Katecholgruppen der Chromophorfunktionalität. Die Modellliganden für die Chromophorfunktionalität, NAP und 6HQ, bilden stärkere Komplexe als die Monohydroxamate SHA und BHA, aber schwächere Komplexe als DFO und PYO. Daraus lässt sich schlussfolgern, dass die Chromophorfunktionalität eine wichtige Rolle bei der Anbindung der Actiniden an die Pyoverdine spielt. Der Vergleich der Stabilitätskonstanten der Komplexe der Liganden SHA, BHA und 6HQ mit den drei untersuchten Actiniden U(VI), Cm(III) und Np(V) untereinander zeigte, dass die Stärke der Komplexe von U(VI) über Cm(III) zu Np(V) abnimmt. Der Grund dafür liegt in den unterschiedlichen Ladungsdichten der Actinidionen. Während das UO2 2+-Ion mit einer Koordinationszahl von 5 und einem Ionenradius von ~ 0.6 eine effektive Ladung von + 3.3 besitzt, hat das Cm3+-Ion eine effektive Ladung von + 2.6 und das NpO2+-Ion von + 2.3. Damit besitzt das NpO2+-Ion die geringste Ladungsdichte der untersuchten Actinidionen und bildet damit auch die schwächsten Komplexe mit den niedrigsten Stabilitätskonstanten. Die Stärke der Komplexe der Liganden NAP, DFO und PYO nimmt von Cm(III) über U(VI) zu Np(V) ab. Obwohl Cm(III) eine geringere effektive Ladung als U(VI) hat, bildet es stärkere Komplexe als U(VI). Eventuell sind dafür strukturelle Behinderungen der Koordination durch die lineare O=U=O Einheit verantwortlich. Die Struktur der wässrigen U(VI)-Komplexe wurde mittels EXAFS-Spektroskopie und ATRFTIR-Spektroskopie untersucht. Aus den EXAFS-Spektren ließ sich schließen, dass die Koordination des Uranylions an die Hydroxamsäuregruppen der Liganden SHA, BHA und DFO eine Verkürzung des Abstandes der äquatorialen Sauerstoffatome zur Folge hat. Im Gegensatz dazu resultiert eine Koordination des Uranylions an die Carboxylgruppe des Liganden BA in einer Verlängerung des U-Oäq Abstandes. Die Ergebnisse des NAP als Modellligand für die Chromophorfunktionalität des Pyoverdins und die Ergebnisse des Pyoverdins selbst zeigten, dass das Uranylion mit großer Wahrscheinlichkeit an die katecholischen OH-Gruppen der Chromophorfunktionalität des Pyoverdinmoleküls gebunden ist. In den Spektren der ATR-FTIR-Spektroskopie ist besonders der Bereich um die Schwingungsbande des Uranylions (961 cm-1) für die Beobachtung der Komplexbildung interessant. Dabei zeigte sich im U(VI)-BHA- und U(VI)-SHA-System eine Mischung aus zwei Komplexen mit 1:1- und 1:2-Stöchiometrie, die auch durch Speziationsrechnungen nachgewiesen werden konnten. Außerdem ließ sich anhand der Schwingungsbanden des Liganden feststellen, dass die Hydroxamsäuregruppe von SHA und BHA während der Komplexierung deprotoniert und direkt an der Komplexbildung beteiligt ist. Im Falle von SHA konnte weiterhin nachgewiesen werden, dass die phenolische OH-Gruppe bei den untersuchten pH-Werten nicht deprotoniert ist. Die pH-abhängigen Spektren des U(VI)-DFOSystems zeigten bei pH 3 die Bildung eines 1:1-Komplexes ähnlich dem der Monohydroxamate, bei Erhöhung des pH-Wertes bis pH 4 dann die Bildung eines 1:1- Komplexes, bei dem das Uranylion an zwei Hydroxamsäuregruppen gebunden ist. Dies stützt die Annahme einer 112-Stöchiometrie des Komplexes, die bei den anderen verwendeten experimentellen Methoden getätigt wurde. Durch Ausfällung aus wässrigen U(VI)-SHA- und U(VI)-BHA-Lösungen wurden Feststoffe der U(VI)-Komplexe hergestellt. Die Struktur dieser ausgefällten, pulverförmigen Feststoffe wurde mittels EXAFS, XRD und FTIR untersucht. Die Untersuchung der ausgefällten Feststoffe ergab, dass die Feststoffkomplexe mit sehr hoher Wahrscheinlichkeit den in Lösung gefundenen Komplexen mit 1:2-Stöchiometrie entsprechen. Der Vergleich der Uran und Kohlenstoffgehalte der Feststoffe mit den in der Literatur beschriebenen Uranverbindungen (zur gravimetrischen Bestimmung von Urangehalten) zeigte übereinstimmende Werte. In den FTIR-Messungen wurden Banden bei 916 cm-1 beobachtet, die denen in der Lösung dem 1:2-Komplex zugeordneten Banden entsprechen. Die Ergebnisse der EXAFS-Messungen deuten auf eine unterschiedliche Nahordnung des U(VI) im Feststoff und in der Lösung hin. So ergab der Vergleich der Strukturparameter der Hydroxamat- Feststoffe mit den U(VI)-Hydroxamat-Komplexen in Lösung deutliche Unterschiede zwischen den Feststoffkomplexen und denen in Lösung. So ist in wässriger Lösung der Abstand der äquatorialen Sauerstoffatome mit 2.41 Å signifikant kürzer als der der Feststoffkomplexe mit 2.47 Å (SHA) und 2.44 Å (BHA). Die röntgendiffraktogrammischen Messungen der Festphasen ergaben reflexreiche Spektren mit signifikanten Peaks, die sich allerdings keinen bekannten U(VI)-Festphasen zuordnen ließen. In einer Kooperation mit dem Institut für Theoretische Chemie der Universität zu Köln wurden für die 1:1- und 1:2-Komplexe der wässrigen U(VI)-SHA-, U(VI)-BHA- und U(VI)-BA-Systeme erstmals theoretische Modellierungen durchgeführt. Dabei wurden die Strukturen der Komplexe sowohl in der Gasphase als auch unter Berücksichtigung der Solvatation optimiert und die relativen Stabilitäten und Anregungsspektren berechnet. Die mit DFT berechneten Bindungsenergien bestätigen die experimentell anhand der Stabilitätskonstanten log β ermittelte Reihenfolge der Komplexstabilitäten (SHA ≥ BHA &gt; BA). Außerdem zeigen die höheren Bindungsenergien der 1:2-Komplexe, dass diese stabiler sind als die 1:1-Komplexe. Dies lässt sich auch anhand der experimentell ermittelten Stabilitätskonstanten nachweisen. Die Maxima der mit TD-DFT berechneten Anregungsspektren weichen um 0.4 ± 0.2 eV von den experimentellen UV-Vis Spektren ab. Dies zeigt die gute Übereinstimmung der berechneten Anregungsspektren mit den gemessenen UV-Vis Spektren. Für den 1:1-Komplex des U(VI)-SHA-Systems konnte mit Hilfe der theoretischen Modellierung die strukturelle Anbindung des Uranylions an die Hydroxamsäuregruppe aufgeklärt werden. Der Vergleich der berechneten Strukturen, Bindungsenergien, Bindungslängen und Anregungsspektren der beiden möglichen Anbindungsmodi [O,O] und [N,O’] zeigte deutlich, dass das Uranylion bevorzugt über die beiden Sauerstoffatome der Hydroxamsäuregruppe, also den [O,O]-Modus, gebunden wird. Die Methode der DFT konnte also dazu beitragen, Defizite in der experimentellen Aufklärung der Komplexstruktur im Fall des U(VI)-SHA-Systems zu beheben. Die Modellliganden und deren Komplexe mit U(VI), Cm(III) und Np(V) wurden zum größten Teil erstmals spektroskopisch charakterisiert sowie deren bisher weitgehend unbekannten Stabilitätskonstanten bestimmt. Außerdem konnte die Struktur der U(VI)-Hydroxamat- Komplexe mit Hilfe der ATR-FTIR-Spektroskopie und der theoretischen Modellierung aufgeklärt werden. Im Vergleich der Ergebnisse der Modellliganden mit denen der Pyoverdine konnte festgestellt werden, dass die Katecholfunktionalität der Pyoverdine eine große Rolle bei der Komplexierung mit den Actiniden spielen wird. Weiterhin ließen sich aus den Ergebnissen Schlussfolgerungen zur Stärke der gebildeten Actinid-Modellligand- und Actinid-Pyoverdin-Komplexe ziehen. Die Pyoverdine bildeten mit U(VI) Komplexe mit Stabilitätskonstanten bis 1030, mit Cm(III) bis 1032 und mit Np(V) bis 1020. Die wichtigsten, in höheren Konzentrationen vorkommenden anorganischen Komplexbildner in natürlichen Wässern sind das Hydroxidion OH- sowie das Carbonation CO32-. Diese besitzen eine hohe Komplexierungsfähigkeit und bilden mit den drei Actiniden U(VI), Cm(III) und Np(V) Komplexe mit Stabilitätskonstanten von 102 bis 1020. Der Vergleich der Konstanten von OH und CO32- mit denen der organischen, mikrobiellen Pyoverdin-Liganden zeigt, dass die Pyoverdine ähnlich starke bzw. teilweise stärkere Komplexe mit den Actiniden bilden als die anorganischen Komplexbildner. Daraus lässt sich ableiten, dass die Pyoverdine selbst in niedrigeren Konzentrationen ein hohes Potential besitzen, Actiniden in natürlichen Wässern zu binden und damit zu transportieren. Die untersuchten Bioliganden sind also in der Lage, bei Anwesenheit in der Natur in bestimmten Konzentrationen im Grundwasser Actiniden, z.B. durch Herauslösen aus Festphasen, zu mobilisieren. Damit können solche Bioliganden das Verhalten der Actiniden in der Umwelt entscheidend beeinflussen. Die Ergebnisse dieser Arbeit tragen dazu bei, den Einfluss der mikrobiellen Liganden auf die Mobilisierung und Ausbreitung der Actiniden besser einschätzen zu können. Damit können die Ergebnisse zur Quantifizierung des Mobilisierungseffekts der Actiniden durch freigesetzte Bioliganden im Nahfeld genutzt werden
One of the urgent tasks in the field of nuclear technology is the final storage of radioactive substances. As a part of the safety requirements the protection of humans and the environment from the danger of radioactive substances in case of the release from the final storage is essential. For performing long-term safety calculations the detailed understanding of the physico-chemical effects and influences which cause the mobilisation and transport of actinides are necessary. The presented work was a discrete part of a project, which was focused on the clarification of the influence of microorganisms on the migration of actinides in case of the release of actinides from a final storage. The influence of microbial produced substances on the mobilisation of selected actinides was studied thereby. The microbial produced substances studied in this project were synthesized by bacteria from the Pseudomonas genus under special conditions. Fluorescent Pseudomonads secrete bacterial pyoverdin-type siderophores with a high potential to complex and transport metals, especially iron(III). The aim of the project was to determine how and under which conditions the bioligands are able to complex also radioactive substances and therefore to transport them. For this work the alpha-emitting actinides uranium, curium and neptunium were chosen because their long-life cycle and their radiotoxicity are a matter of particular interest. This work dealed with the interaction of the actinides U(VI), Np(V) and Cm(III) with model ligands simulating the functionality of the pyoverdins. The functional groups that participate in the metal binding of the pyoverdins are the catechol group of the chromophore and the ligand sites in the peptide chain, i.e. the hydroxamate groups and the α-hydroxy acid moieties. For the simulation of the hydroxamate functionality the monohydroxamates salicylhydroxamic acid (SHA) and benzohydroxamic acid (BHA) and the natural trihydroxamate desferrioxamine B (DFO) and for the simulation of the catechol groups 6-hydroxyquinoline (6HQ) and 2,3-dihydroxynaphthalene (NAP) were used. A further ligand with carboxyl functionality, benzoic acid (BA), was used as a comparison. Absorption spectroscopy, laser fluorescence spectroscopy, X-ray absorption spectroscopy and vibrational spectroscopy were applied for the determination of the stability constants to assess the strength of the formed actinide-model ligand-complexes, for the clarification of the structures of the formed complexes and to observe the variation of the speciation of the actinides during the interaction with the ligands. Furthermore, for the first time density functional theory (DFT) calculations were performed to determine the molecular structure of the actinide-modelligand-complexes. Thus, the objectives of this work were the determination of the spectroscopic properties, speciation and stability constants of the model ligands and the formed actinide-model ligand-complexes, the clarification of the complex structures and a comparison of the results with those of the pyoverdins. The comparison of the stability constants of the studied ligands with the three actinides U(VI), Cm(III) and Np(V) systems results mainly in the following order of complex strength: PYO ≥ DFO &gt; NAP &gt; 6HQ &gt; SHA ≥ BHA &gt; BA. Benzoic acid, the ligand with the carboxyl functionality, has the lowest stability constant of 103. Both monohydroxamates, SHA and BHA, form 1:1 complexes with similar stability. The stability constants of the 1:2 complexes of SHA with Cm(III) and Np(V) are slightly higher than those of BHA, which is probably caused by a stabilizing effect of the additional phenolic OH-group of SHA. This behaviour was also found in the theoretical calculations of the U(VI)-complexes. The natural siderophores DFO and PYO have the highest stability constants with U(VI) and form the strongest complexes (constants from 1012 to 1034). The reason therefore is the structure and high number of functional groups of these ligands; DFO has three hydroxamate groups, the pyoverdin molecule has the catechol groups of the chromophore functionality in addition to the hydroxamate groups. The model ligands for the chromophore functionality, NAP and 6HQ, form stronger complexes than SHA and BHA, but weaker complexes than DFO and PYO. From this it can be reasoned that the chromophore functionality probably plays an important role for the coordination of the actinides to the pyoverdins. The comparison of the stability constants of the complexes of the ligands SHA, BHA and 6HQ with the studied actinides U(VI), Cm(III) and Np(V) shows that the strength of the complex formation decreases from U(VI) via Cm(III) to Np(V). The reason therefore is the different charge density of the actinide ions. The UO22+-ion has an effective charge of + 3.3 (with a coordination number of 5 and an ionic radius of ~ 0.6), the Cm3+-ion of + 2.6 and the NpO2+-ion of + 2.3. Therefore, the neptunyl ion has the lowest charge density of the studied actinide ions and on account of this it forms the weakest complexes with the lowest stability constants. The strength of the complex formation of the ligands NAP, DFO and PYO decreases from Cm(III) via U(VI) to Np(V). Cm(III) forms stronger complexes than U(VI) although Cm(III) has a lower effective charge. The reason therefore could be a possible structural hampering of the coordination through the linear O=U=O unit. The structure of the aqueous U(VI)-complexes was studied using EXAFS spectroscopy and FTIR spectroscopy. From the results of the EXAFS spectra one can conclude that the coordination of the uranyl ion to the hydroxamic acid groups of the SHA, BHA and DFO ligands results in a shortening of the distance of the equatorial oxygen atoms. In contrast to this the coordination of the uranyl ion to the carboxyl group of BA yields in a longer U-Oeq bond length. From the findings of the EXAFS studies with NAP and pyoverdin one can conclude a strong affinity of U(VI) to the catechol functionality of the pyoverdin molecule. For the observation of the complexation in the ATR-FTIR spectra the region around the vibration band of the uranyl ion (916 cm-1) is interesting to observe. In the spectra of the U(VI)-BHA- and U(VI)-SHA-system a mixture of two complexes with 1:1 and 1:2 stoichiometry was observed, which was also existing in the speciation. Furthermore, on the basis of the vibration bands of the ligands it could be ascertained that the hydroxamate groups of SHA and BHA are deprotonated and directly involved in the complexation. Also, in case of SHA it could be verified that the phenolic OH-group is protonated at the investigated pH values. At pH 3 the pH dependent spectra of the U(VI)-DFO-system showed the formation of a 1:1 complex similar to those of the monohydroxamates. With increasing pH up to 4 the formation of a 1:1 complex was observed, in which the uranyl ion is bound to two hydroxamic acid groups. This underlines the assumption that the complex had a 112-stoichiometry, which was concluded on the basis of the other used experimental methods. Solid phases of U(VI) complexes were assembled by precipitation from the aqueous U(VI)-SHA and U(VI)-BHA solutions. The structure of these powder solids was analyzed using EXAFS, XRD and FTIR. The analysis of the solid phases showed that the solid complexes are most likely consistent with the complexes in aqueous solution with 1:2 stoichiometrie. The comparison of the uranium and carbon percentage of the solids with those of the uranium compounds described in the literature (for the gravimetric estimation of uranium contents) results in analogue values. In the FTIR spectra of the solids vibration bands at 916 cm-1 were observed according to the bands of the 1:2 complexes in aqueous solution. The results of the EXAFS measurements indicated a different short-range order of the U(VI) in solid phases and solutions. The comparison of the structural parameters of the solid phases with those of the aqueous U(VI)-hydroxamate complex species points to strong differences. Thus, in aqueous solution the distance of the equatorial oxygen atoms of 2.41 Å is significant shorter than those of the solid complexes with 2.47 Å (SHA) and 2.44 Å (BHA). The XRD measurements showed spectra high in reflexes and with significant peaks which could not be assigned to known U(VI) solid phases. In a cooperation with the Institute of Theoretical Chemistry at the University of Cologne density functional theory (DFT) calculations were performed to determine the molecular structure of 1:1 and 1:2 U(VI)-complexes with SHA, BHA and BA. The precise molecular structures of the complexes in gas phase have been calculated as well as the relative stabilities and the time-dependent DFT excitation spectra with consideration of the solvation effects. The relative stabilities calculated with DFT confirm the order of strength of the complexes determined using the stability constants log β (SHA ≥ BHA &gt; BA). Furthermore, the higher binding energies of the 1:2 complexes point to a higher complex stability of these complexes in comparison to the corresponding 1:1 complexes. This could be also demonstrated by means of the stability constants determined by the experimental studies. The peak maxima of the TD-DFT excitation spectra deviate at 0.4 ± 0.2 eV from the absorption maxima of the experimental UV-vis spectra. Thus, calculated and experimental spectra show a good qualitative agreement. For the 1:1 complex of the U(VI)-SHA-system the structurally coordination of the uranium ion to the hydroxamate group could be clarified with the help of the theoretical modelling. The comparison of the calculated structures, binding energies, bond lengths and excitation spectra of the two possible coordination modes [O,O] and [N,O’] showed clearly that the uranyl ion is bound preferable to the two oxygen atoms of the hydroxamate group ([O,O]-mode). Therefore, the method of DFT could contribute to eliminate shortcomings in the experimental determination of the complex structure in case of the U(VI)-SHA-system. The model ligands and their complexes with U(VI), Cm(III) and Np(V) were characterized spectroscopically and their widely unknown stability constants were determined for the first time. Furthermore, the structures of the U(VI)-hydroxamate-complexes were clarified using ATR-FTIR spectroscopy and theoretical calculations. The comparison of the results of the model ligands with those of the pyoverdins showed that the chromophore functionality of the pyoverdins probably plays an important role for the coordination of the actinides to the pyoverdins. Furthermore, conclusions to the strength of the formed actinide-model ligandand actinide-pyoverdin-complexes could be drawn from those results. The pyoverdins formed U(VI)-complexes with stability constants up to 1030, Cm(III)-complexes with constants up to 1032 and Np(V)-complexes with values up to 1020. The hydroxide ion OH- and the carbonato ion CO32- are the most important inorganic complexing agents in natural aquatic systems. They are highly concentrated and have great complexing ability. With the three studied actinides U(VI), Cm(III) and Np(V) complexes with stability constants from 102 to 1020 were formed. The comparison of the constants of OH- and CO3 2- with those of the organic microbial ligands showed that the pyoverdins complexes the actinides with similar and particularly higher strength than the inorganic complexing agents. Thus, it appears that the pyoverdins have a high potential to bind actinides and transport them in natural aquatic systems even though the pyoverdins exist in lower concentrations. Therefore, the studied bioligands are able to mobilize the actinides in natural aquatic systems, for example through dissolving them from solid phases, if they are present in the nature in specific concentrations. So, such bioligands can essentially influence the behaviour of actinides in the environment. The results of this work contribute to a better understanding and assessment of the influence of the microbial ligands to the mobilisation and migration of the radionuclides. The outcomes could be used to quantify the actinide-mobilising effect of the bioligands, which are released, for example, in the vicinity of a nuclear waste disposal site