O problema da árvore de suporte de custo mínimo com restrições de peso

Nesta tese abordam-se várias formulações e diferentes métodos para resolver o Problema da Árvore de Suporte de Custo Mínimo com Restrições de Peso (WMST – Weight-constrained Minimum Spanning Tree Problem). Este problema, com aplicações no desenho de redes de comunicações e telecomunicações, é um problema de Otimização Combinatória NP-difícil. O Problema WMST consiste em determinar, numa rede com custos e pesos associados às arestas, uma árvore de suporte de custo mínimo de tal forma que o seu peso total não exceda um dado limite especificado. Apresentam-se e comparam-se várias formulações para o problema. Uma delas é usada para desenvolver um procedimento com introdução de cortes baseado em separação e que se tornou bastante útil na obtenção de soluções para o problema. Tendo como propósito fortalecer as formulações apresentadas, introduzem-se novas classes de desigualdades válidas que foram adaptadas das conhecidas desigualdades de cobertura, desigualdades de cobertura estendida e desigualdades de cobertura levantada. As novas desigualdades incorporam a informação de dois conjuntos de soluções: o conjunto das árvores de suporte e o conjunto saco-mochila. Apresentam-se diversos algoritmos heurísticos de separação que nos permitem usar as desigualdades válidas propostas de forma eficiente. Com base na decomposição Lagrangeana, apresentam-se e comparam-se algoritmos simples, mas eficientes, que podem ser usados para calcular limites inferiores e superiores para o valor ótimo do WMST. Entre eles encontram-se dois novos algoritmos: um baseado na convexidade da função Lagrangeana e outro que faz uso da inclusão de desigualdades válidas. Com o objetivo de obter soluções aproximadas para o Problema WMST usam-se métodos heurísticos para encontrar uma solução inteira admissível. Os métodos heurísticos apresentados são baseados nas estratégias Feasibility Pump e Local Branching. Apresentam-se resultados computacionais usando todos os métodos apresentados. Os resultados mostram que os diferentes métodos apresentados são bastante eficientes para encontrar soluções para o Problema WMST.

Desenvolvimento de ferramentas de apoio multicritério à decisão em problemas de localização

Tese de doutoramento, Estatística e Investigação Operacional (Análise de Sistemas), Universidade de Lisboa, Faculdade de Ciências, 2014

Os valores semânticos das preposições a, até e para em Português Europeu Trajetórias, fronteiras, telicidade e topologia

Tese apresentada para cumprimento dos requisitos necessários à obtenção do grau de Doutor em Linguística

Combined Analysis of the Short-Term Effects of Photochemical Air Pollutants on Mortality within the EMECAM Project

In recent years, some epidemiologic studies have attributed adverse effects of air pollutants on health not only to particles and sulfur dioxide but also to photochemical air pollutants (nitrogen dioxide and ozone). The effects are usually small, leading to some inconsistencies in the results of the studies. Furthermore, the different methodologic approaches of the studies used has made it difficult to derive generic conclusions. We provide here a quantitative summary of the short-term effects of photochemical air pollutants on mortality in seven Spanish cities involved in the EMECAM project, using generalized additive models from analyses of single and multiple pollutants. Nitrogen dioxide and ozone data were provided by seven EMECAM cities (Barcelona, Gijón, Huelva, Madrid, Oviedo, Seville, and Valencia). Mortality indicators included daily total mortality from all causes excluding external causes, daily cardiovascular mortality, and daily respiratory mortality. Individual estimates, obtained from city-specific generalized additive Poisson autoregressive models, were combined by means of fixed effects models and, if significant heterogeneity among local estimates was found, also by random effects models. Significant positive associations were found between daily mortality (all causes and cardiovascular) and NO2, once the rest of air pollutants were taken into account. A 10 μg/m3 increase in the 24-hr average 1-day NO2 level was associated with an increase in the daily number of deaths of 0.43% [95% confidence interval(CI), –0.003–0.86%] for all causes excluding external. In the case of significant relationships, relative risks for cause-specific mortality were nearly twice as much as that for total mortality for all the photochemical pollutants. Ozone was independently related only to cardiovascular daily mortality. No independent statistically significant relationship between photochemical air pollutants and respiratory mortality was found. The results in this study suggest that, given the present levels of photochemical pollutants, people living in Spanish cities are exposed to health risks derived from air pollution

Good-visibility computation using graphics hardware

Aquesta tesi tracta del disseny, implementació i discussió d'algoritmes per resoldre problemes de visibilitat i bona-visibilitat utilitzant el hardware gràfic de l'ordinador. Concretament, s'obté una discretització dels mapes de multi-visibilitat i bona-visibilitat a partir d'un conjunt d'objectes de visió i un conjunt d'obstacles. Aquests algoritmes són útils tant per fer càlculs en dues dimensions com en tres dimensions. Fins i tot ens permeten calcular-los sobre terrenys.

Design and synthesis of short antimicrobial peptides for plant protection. Study of their mode of action

Aquesta tesi doctoral està basada en el desenvolupament de nous agents antimicrobians derivats del pèptid híbrid cecropina A-melitina WKLFKKILKVL-NH2 (Pep3) que siguin sostenibles i útils per al control de malalties de plantes. Es van dissenyar i sintetitzar més de 133 anàlegs de Pep3 mitjançant química combinatòria. Es van obtenir anàlegs de Pep3 amb una elevada activitat contra fitopatògens i que presentaven baixa toxicitat. Els millors anàlegs van presentar eficàcies comparables amb pesticides de referència en la prevenció d'infeccions causades per fitopatògens. Es va estudiar el mecanisme d'acció de KKLFKKILKYL-NH2 (BP100) investigant la seva interacció amb models de membrana mitjançant tècniques espectroscòpiques. Es va observar la capacitat de BP100 a induir la permeabilització, la neutralització, i l'agregació de vesícules lipídiques aniòniques a una determinada concentració llindar. Es va deduir una equació que relaciona la CMI d'un pèptid antimicrobià amb la constant de partició i la concentració llindar en la membrana.

Synthesis and evaluation of cyclic cationic peptides as antimicrobial agents for use in plant protection

Aquesta tesi doctoral se centra en l'estudi de l'aplicació de pèptids antimicrobians en la lluita contra agents patògens de cultius de plantes d'interès econòmic.L'estratègia sintètica s'ha portat a terme utilitzant metodologies convencionals de síntesi de pèptids en fase sòlida com l'estratègia tridimensional ortogonal Fmoc/tBut/Allyl. Ha calgut fer la recerca de les condicions òptimes per a l'eliminació del grup Allyl i la ciclació. D'entre els pèptids cíclics de 4-10 aminoacids sintetitzats, el decapèptid c(Lys-Leu-Lys-Leu-Lys-Phe-Lys-Lys-Leu-Gln) ha resultat ésser el més efectiu i s'ha pres com a base per al disseny d'una quimioteca de 56 pèptids. Dels resultats obtinguts s'ha sintetitzat una segona quimioteca basada en l'estructura general c(X1-X2-X3-X4-Lys-Phe-Lys-Lys-Leu-Gln) determinada com la que posseix el millor perfil d'activitat. Els pèptids més efectius obtinguts constituixen els primers exemples de pèptids cíclics actius contra E. amylovora i poden ser considerats com a bons candidats pel desenvolupament d'agents antimicrobians efectius en protecció vegetal.

Uma Proposta de especificação formal e fundamentação teórica para simulated annealing

Os algoritmos baseados no paradigma Simulated Annealing e suas variações são atualmente usados de forma ampla na resolução de problemas de otimização de larga escala. Esta popularidade é resultado da estrutura extremamente simples e aparentemente universal dos algoritmos, da aplicabilidade geral e da habilidade de fornecer soluções bastante próximas da ótima. No início da década de 80, Kirkpatrick e outros apresentaram uma proposta de utilização dos conceitos de annealing (resfriamento lento e controlado de sólidos) em otimização combinatória. Esta proposta considera a forte analogia entre o processo físico de annealing e a resolução de problemas grandes de otimização combinatória. Simulated Annealing (SA) é um denominação genérica para os algoritmos desenvolvidos com base nesta proposta. Estes algoritmos combinam técnicas de busca local e de randomização. O objetivo do presente trabalho é proporcionar um entendimento das características do Simulated Annealing e facilitar o desenvolvimento de algoritmos com estas características. Assim, é apresentado como Simulated Annealing e suas variações estão sendo utilizados na resolução de problemas de otimização combinatória, proposta uma formalização através de um método de desenvolvimento de algoritmos e analisados aspectos de complexidade. O método de desenvolvimento especifica um programa abstrato para um algoritmo Simulated Annealing seqüencial, identifica funções e predicados que constituem os procedimentos deste programa abstrato e estabelece axiomas que permitem a visualização das propriedades que estes procedimentos devem satisfazer. A complexidade do Simulated Annealing é analisada a partir do programa abstrato desenvolvido e de seus principais procedimentos, permitindo o estabelecimento de uma equação genérica para a complexidade. Esta equação genérica é aplicável aos algoritmos desenvolvidos com base no método proposto. Uma prova de correção é apresentada para o programa abstrato e um código exemplo é analisado com relação aos axiomas estabelecidos. O estabelecimento de axiomas tem como propósito definir uma semântica para o algoritmo, o que permite a um desenvolvedor analisar a correção do código especificado para um algoritmo levando em consideração estes axiomas. O trabalho foi realizado a partir de um estudo introdutório de otimização combinatória, de técnicas de resolução de problemas, de um levantamento histórico do uso do Simulated Annealing, das variações em torno do modelo e de embasamentos matemáticos documentados. Isto permitiu identificar as características essenciais dos algoritmos baseados no paradigma, analisar os aspectos relacionados com estas características, como as diferentes formas de realizar uma prescrição de resfriamento e percorrer um espaço de soluções, e construir a fundamentação teórica genérica proposta.

Da descrição lexicográfica : o caso dos adjetivos estéticos no português brasileiro

Tendo como objetivo a investigação acerca da descrição lexicográfica dos adjetivos estéticos, este trabalho observou como se estruturam a microestrutura, no enfoque da descrição sintático-semântica, e a macroestrutura, no que toca à organização lexical, de adjetivos do campo semântico da estética, em dicionários vernaculares do português brasileiro. Fundamentaram a análise dos dados os conceitos, definições e metodologia de elaboração de artigos de dicionário da Teoria Lexicológica Explicativo-Combinatória, bem como das pesquisas léxicosemânticas presentes no Dicionário Explicativo-Combinatório do Francês Contemporâneo. Observou-se que os adjetivos descritos nos dicionários vernaculares carecem da informação lexical que é passível de ser delineada apenas mediante uma descrição sintático-semântica acurada e rigorosa, em termos de lexicografia com base lexicológica. Os resultados apontam para a necessidade de serem estruturadas as entradas lexicais de adjetivos estéticos em obras lexicográficas, com base na sua caracterização sintático-semântica, que envolve, entre outras, questões de tipologia denotacional e inter-relação sintaxesemântica.

Murmúrios [im]possíveis: o desafio dialogante entre poesia e artes plásticas em Vasco Graça Moura

Nesta dissertação tento comprovar que a escrita poética de Vasco Graça Moura está repleta de “murmúrios [im]possíveis” com as artes plásticas; ou seja, que a sua poesia estabelece um diálogo fluido e permanente com a pintura, a fotografia e o desenho, do qual resulta a transfiguração do real e, por conseguinte, a reinterpretação do mundo. Com este intuito, analiso os suportes da escrita (Babo, 2006) assim como os conceitos de ecfrase (Ceia, 2005), rizoma (Deleuze e Guatarri, 2006) e desconstrução (Ceia, 2005), que fundamentam esta “arte combinatória” (Moura, 1983) e solidificam “os múltiplos casamentos do Vasco Graça Moura com as artes de encantamento e sedução” (Veiga, 2000). Esta investigação empreende, portanto, num diálogo com a escrita poética de Vasco Graça Moura, a pintura referida, as fotografias de Gérard Castello-Lopes (Em demanda de Moura – Giraldomachias, 1999) e de Ana Gaiaz (Variações metálicas, 2004), e os desenhos de Jorge Pinheiro (sombras com aquiles e pentesileia, 1999), tentando corroborar a presença da relação cúmplice entre poesia e artes plásticas e acompanhar as suas sucessivas “operações de desmontagem” (Moura, 2007).