On the Faria's inequality for the Laplacian and signless Laplacian spectra: a unified approach

Let p(G)p(G) and q(G)q(G) be the number of pendant vertices and quasi-pendant vertices of a simple undirected graph G, respectively. Let m_L±(G)(1) be the multiplicity of 1 as eigenvalue of a matrix which can be either the Laplacian or the signless Laplacian of a graph G. A result due to I. Faria states that mL±(G)(1) is bounded below by p(G)−q(G). Let r(G) be the number of internal vertices of G. If r(G)=q(G), following a unified approach we prove that mL±(G)(1)=p(G)−q(G). If r(G)>q(G) then we determine the equality mL±(G)(1)=p(G)−q(G)+mN±(1), where mN±(1) denotes the multiplicity of 1 as eigenvalue of a matrix N±. This matrix is obtained from either the Laplacian or signless Laplacian matrix of the subgraph induced by the internal vertices which are non-quasi-pendant vertices. Furthermore, conditions for 1 to be an eigenvalue of a principal submatrix are deduced and applied to some families of graphs.

O desenvolvimento do raciocínio dedutivo ao nível do ensino secundário : recurso a geometrias planas

Este trabalho, no âmbito da Didáctica da Matemática, foca-se no estudo de abordagens alternativas de ensino e aprendizagem da Geometria Euclidiana, no Ensino Secundário, no sentido de promover níveis estruturados do pensamento matemático. Em particular, as potencialidades do recurso a outros modelos de Geometria Plana (e.g. Geometria Hiperbólica, Geometria do Motorista de Táxi) em relação a este problema serão investigadas. A opção pelo Ensino Secundário deve-se ao facto de se tratar de um nível de ensino onde se regista uma elevada taxa de insucesso escolar (especialmente no 10º ano) e onde é notório o abismo existente, entre o ensino Secundário e Universitário, no âmbito do raciocínio lógico - dedutivo. O trabalho a desenvolver pretende aprofundar o estudo de questões ligadas à natureza do conhecimento envolvido que estarão na base de decisões, tais como: Quais os processos que vão ser ensinados? Que processos queremos que os alunos dominem? E, por outro lado, ter em conta que se pretende desenvolver capacidades de ordem superior, significando que o ensino da Matemática deve dirigir-se para níveis elevados de pensamento, tais como: resolução de problemas; comunicar matematicamente; raciocínio e demonstração. No currículo de matemática para o Ensino Básico e Secundário tem-se negligenciado a demonstração matemática, contribuindo para que exista uma desconformidade entre os graus de ensino, secundário e universitário. Muitas vezes as abordagens de ensino centram-se na verificação de resultados e desvalorizam a exploração e explicação (Villiers, 1998). Actualmente, assiste-se a uma tendência para retomar o raciocínio lógico - dedutivo. O principal objectivo desta investigação é analisar ambientes de aprendizagem em que os alunos sejam solicitados a resolver problemas de prova em contextos diversificados e, de uma forma mais geral promover o desenvolvimento do raciocínio dedutivo e uma visão mais alargada do conhecimento matemático. Em particular, a abordagem de problemas de prova num contexto de geometria não Euclidiana, com recurso a artefactos e a software de geometria dinâmica, será investigada.

Quantum criptography in optical fibers

As comunicações quânticas aplicam as leis fundamentais da física quântica para codificar, transmitir, guardar e processar informação. A mais importante e bem-sucedida aplicação é a distribuição de chaves quânticas (QKD). Os sistemas de QKD são suportados por tecnologias capazes de processar fotões únicos. Nesta tese analisamos a geração, transmissão e deteção de fotões únicos e entrelaçados em fibras óticas. É proposta uma fonte de fotões única baseada no processo clássico de mistura de quatro ondas (FWM) em fibras óticas num regime de baixas potências. Implementamos essa fonte no laboratório, e desenvolvemos um modelo teórico capaz de descrever corretamente o processo de geração de fotões únicos. O modelo teórico considera o papel das nãolinearidades da fibra e os efeitos da polarização na geração de fotões através do processo de FWM. Analisamos a estatística da fonte de fotões baseada no processo clássico de FWM em fibras óticas. Derivamos um modelo teórico capaz de descrever a estatística dessa fonte de fotões. Mostramos que a estatística da fonte de fotões evolui de térmica num regime de baixas potências óticas, para Poissoniana num regime de potências óticas moderadas. Validamos experimentalmente o modelo teórico, através do uso de fotodetetores de avalanche, do método estimativo da máxima verossimilhança e do algoritmo de maximização de expectativa. Estudamos o processo espontâneo de FWM como uma fonte condicional de fotões únicos. Analisamos a estatística dessa fonte em termos da função condicional de coerência de segunda ordem, considerando o espalhamento de Raman na geração de pares de fotões, e a perda durante a propagação de fotões numa fibra ótica padrão. Identificamos regimes apropriados onde a fonte é quase ideal. Fontes de pares de fotões implementadas em fibras óticas fornecem uma solução prática ao problema de acoplamento que surge quando os pares de fotões são gerados fora da fibra. Exploramos a geração de pares de fotões através do processo espontâneo de FWM no interior de guias de onda com suceptibilidade elétrica de terceira ordem. Descrevemos a geração de pares de fotões em meios com elevado coeficiente de absorção, e identificamos regimes ótimos para o rácio contagens coincidentes/acidentais (CAR) e para a desigualdade de Clauser, Horne, Shimony, and Holt (CHSH), para o qual o compromisso entre perda do guia de onda e não-linearidades maximiza esses parâmetros.

Polyhedral study of mixed integer sets arising from inventory problems

“Branch-and-cut” algorithm is one of the most efficient exact approaches to solve mixed integer programs. This algorithm combines the advantages of a pure branch-and-bound approach and cutting planes scheme. Branch-and-cut algorithm computes the linear programming relaxation of the problem at each node of the search tree which is improved by the use of cuts, i.e. by the inclusion of valid inequalities. It should be taken into account that selection of strongest cuts is crucial for their effective use in branch-and-cut algorithm. In this thesis, we focus on the derivation and use of cutting planes to solve general mixed integer problems, and in particular inventory problems combined with other problems such as distribution, supplier selection, vehicle routing, etc. In order to achieve this goal, we first consider substructures (relaxations) of such problems which are obtained by the coherent loss of information. The polyhedral structure of those simpler mixed integer sets is studied to derive strong valid inequalities. Finally those strong inequalities are included in the cutting plane algorithms to solve the general mixed integer problems. We study three mixed integer sets in this dissertation. The first two mixed integer sets arise as a subproblem of the lot-sizing with supplier selection, the network design and the vendor-managed inventory routing problems. These sets are variants of the well-known single node fixed-charge network set where a binary or integer variable is associated with the node. The third set occurs as a subproblem of mixed integer sets where incompatibility between binary variables is considered. We generate families of valid inequalities for those sets, identify classes of facet-defining inequalities, and discuss the separation problems associated with the inequalities. Then cutting plane frameworks are implemented to solve some mixed integer programs. Preliminary computational experiments are presented in this direction.

Ensaios sobre o crescimento económico regional e a dinâmica do processo de convergência

The research is centred on economic growth and it adopts a regional view focused on European regions (NUTS 2). Under analysis is the undergoing convergence process in Europe to evaluate if there is an increase in regional economic growth and a simultaneous decrease in regional disparities. The empirical evidence shows signs of transience on the regional convergence process, along with the formation of several clusters of regions. Considering this evidence it is of interest to assess the profiles of such clusters, and evaluate the homogeneousness of its regions and their spread across European space. As suggested in the literature, space is a relevant factor in the spread of clusters, according to the different variables (regions profiles, diversity measures and growth indicators). Regional disparities across Europe are, on average, large and persistent, with a high degree of stability among the relative rankings of European regions. Such results cast shadows about the impact of European structural funding in diminishing regional disparities. Such an approach is of interest due to the growing need to evaluate the effectiveness and efficiency of public policies implemented. The fact that there is an undergoing process of economic integration in Europe increases the usefulness of such an analysis, especially in a context in which European public funds are negotiated and granted.