University, Diss., 1999--Osnabrück.

University, Diss., 2003--Kiel.

University, Diss., 2001--Saarbrücken.

Techn. University, Diss., 2004--Berlin.

University, Diss., 2005--Düsseldorf.

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.

Constraint programming is an invaluable tool for solving many of the complex NP-complete problems that we need solutions to. These problems can be easily described as Constraint Satisfaction Problems (CSPs) and then passed to constraint solvers: complex pieces of software written to solve general CSPs efficiently. Many of the problems we need solutions to are real world problems: planning (e.g. vehicle routing), scheduling (e.g. job shop schedules) and timetabling problems (e.g. staff rotas) to name but a few. In the real world, we place structure on objects to make them easier to deal with. This manifests itself as symmetry. The symmetry in these real world problems make them easier to deal with for humans. However, they lead to a great deal of redundancy when using computational methods of problem solving. Thus, this thesis examines some of the many aspects of utilising the symmetry of CSPs to reduce the amount of computation needed by constraint solvers. In this thesis we look at the ease of use of previous symmetry breaking methods. We introduce a new and novel method of describing the symmetries of CSPs. We look at previous methods of symmetry breaking and show how we can drastically reduce their computation while still breaking all symmetry. We give the first detailed investigation into the behaviour of breaking only subsets of all symmetry. We look at how this affects the performance of constraint solvers before discovering the properties of a good symmetry. We then present an original method for choosing the best symmetries to use. Finally, we look at areas of redundant computation in constraint solvers that no other research has examined. New ways of dealing with this redundancy are proposed with results of an example implementation which improves efficiency by several orders of magnitude.

The Bohemian Forest, a mountain range located in Central Europe on the border between the Czech Republic, Germany and Austria, has many well-known qualities. The areas of Modravské slatě moors and Trojmezná, are considered to be the most valuable biocenters in the Czech part of the Bohemian Forest. This Master thesis confirms the quality of these areas in a transboundary context Natura 2000 habitats and their representativeness. A new transboundary (European) biocentre is proposed and its importance for several species is discussed.

Submitted by Daniella Sodre (daniella.sodre@ufpe.br) on 2015-04-13T13:41:14Z No. of bitstreams: 2 DISSERTAÇÃO Wanessa Botelho Cabral.pdf: 1347764 bytes, checksum: e922b207be73f5f6dd67b374c36e0e16 (MD5) license_rdf: 1232 bytes, checksum: 66e71c371cc565284e70f40736c94386 (MD5) / Made available in DSpace on 2015-04-13T13:41:14Z (GMT). No. of bitstreams: 2 DISSERTAÇÃO Wanessa Botelho Cabral.pdf: 1347764 bytes, checksum: e922b207be73f5f6dd67b374c36e0e16 (MD5) license_rdf: 1232 bytes, checksum: 66e71c371cc565284e70f40736c94386 (MD5) Previous issue date: 2014-01-22 / CAPES; CNPq / Os agrotóxicos são largamente utilizados no mundo para proteger as plantações contra pragas e doenças, e na saúde pública no controle de vetores que causam doenças ao homem. Contudo, a exposição a esses produtos pode representar graves riscos à saúde humana e ao meio ambiente. Relatos da literatura sobre ação genotóxica das formulações comerciais isoladas de agrotóxicos é bastante escaça, uma vez que a maioria das pesquisas se preocupa em estudar o efeito das misturas desses compostos. Desta forma, o presente trabalho realizou um biomonitoramento in vivo, utilizando camundongos Mus musculus, para avaliar a ação genotóxica aguda, através da ingestão isolada dos agrotóxicos Ciromazina (Trigard 700 WP) e Maconzeb (Dithame NT) em baixas doses. Foram realizados os testes do micronúcleo e do ensaio cometa, para avaliar respectivamente a mutagenicidade e a genotoxicidade desses pesticidas. Sendo utilizados 80 camundongos, divididos em oito grupos contendo 10 animais (cinco machos e cinco fêmeas). As administrações foram feitas por gavagem e cada animal recebeu 1 mL da solução, de acordo com o grupo a que pertencia: o grupo controle negativo recebeu apenas o veículo de diluição (água destilada); para a Ciromazina foram usados três grupos experimentais: C1 com a concentração de 2,5.10−4 mg/Kg, o C2 com a concentração de 5.10−4 mg/Kg, e C3 com a concentração de 5.10-3 mg/Kg; para o Mancozeb foram usados também três grupos experimentais: C1 com a concentração de 3,76.10−4 mg/Kg, C2 com a concentração de 7,52.10−4 mg/Kg, e C3 com a concentração de 7,52.10-3 mg/Kg; para o grupo controle positivo foi administrado via injeção intraperitonial 20 mg/kg p.c. de ciclofosfamida. Na análise estatística, foram realizados dois testes: uma ANOVA multifatorial (Análise de variância), para comparar a ação genotóxica entre os grupos experimentais; e o teste de Mann-Whitney para verificar a influência do sexo no aparecimento do dano genético dentro de um mesmo grupo tratado. O agrotóxico Ciromazina demonstrou ser mutagênico e altamente genotóxico na concentração do grupo C2, além de apresentar uma diferença significativa entre os sexos no grupo C1. Já o pesticida Mancozeb mostrou ser genotóxico na concentração do grupo C2, e foi constatado também que houve diferença significativa entre os sexos dos individuos do grupo C3. Através desta pesquisar evidenciamos que mesmo em baixas concentrações estes pesticidas oferecem grandes riscos à saúde humana e ao meio ambiente.

Esta tesis trata sobre un problema de reconstrucción en Tomografía Discreta en el cual se está interesado en colorear una grilla usando k colores, de tal forma que para cada fila y columna, el número de celdas de cada color sea un cierto valor previamente dado. Para k = 2, un resultado clásico de la Combinatoria entrega una condición necesaria y suficiente para la existencia de tal coloración junto con un algoritmo polinomial para construirla cuando existe. Por otro lado, Chrobak y Dürr mostraron que para k mayor o igual a 4 el problema es NP-difícil. La equivalencia natural entre una grilla y un grafo bipartito completo muestra que el caso k=3 corresponde a la restricción a esta clase de grafos del siguiente problema: Dados un grafo G y funciones enteras b¹ y b² en V(G), ¿existen b¹ y b²-factores de G que sean disjuntos? En esta tesis introducimos una nueva condición para este problema, la que resulta ser suficiente cuando G es un grafo bipartito completo y la diferencia entre el máximo y mínimo valor de b¹ + b² es a los más dos. La demostración de este resultado se basa en un algoritmo polinomial que encuentra dos factores disjuntos o bien un certificado de inexistencia. Junto con esto, la contribución principal de esta tesis es la prueba de NP-dificultad del problema para grafos bipartitos completos cuando no se impone ninguna condición a b¹ y b². Esto resuelve el caso k = 3 del mencionado problema en Tomografía Discreta, lo que cierra el problema para todos los valores de k. Como corolario obtenemos además que el problema para grafos completos es también NP-difícil. Para el problema de unicidad, caracterizamos las transformaciones que preservan las funciones b¹ y b² cuando G es un grafo bipartito. Este resultado es luego utilizado para probar la existencia de invariantes para algunas 3-coloraciones de la grilla. Además, estudiamos la generalización del problema de k-coloración a la reconstrucción de embaldosados de la grilla usando como baldosas k rectángulos de diferentes tamaños. Para este problema, presentamos demostraciones que abarcan y extienden todos los resultados previos conocidos. Para finalizar, se prueba la existencia de un núcleo cuadrático para una generalización del problema de Vertex Cover parametrizado por el tamaño requerido del conjunto solución.