CEOC Seminars 2006 December 15, 2006 Escalonamento integrado de viaturas e tripulações Resumo: O escalonamento de viaturas e tripulações são etapas fundamentais no planeamento operacional nas companhias de transporte de passageiros. Devido à complexidade de cada um destes problemas, a sua resolução costuma ser feita em sequência, negligenciando a forte a forte ligação que existe entre ambos. No sentido de se obterem melhores escalas propõe-se o estudo do problema de escalonamento integrado de viaturas e tripulações. O problema é formulado usando um modelo de programação linear inteira que é resolvido combinando técnicas de geração implícita de colunas com um método de pesquisa em árvore. São apresentados resultados computacionais referentes a problemas reais e a problemas gerados aleatoriamente e disponíveis na literatura. November 24, 2006 O problema "Minimum Vertex Guard (MVG) em grid n-ogons" Resumo: Neste seminário estuda-se o problema MVG numa subclasse de polígonos ortogonais – os grid n-ogons. Um grid n-ogon é um polígono ortogonal com n vértices sem arestas colineares, definido numa grelha quadrada . Como um passo para a resolução do problema MVG em grid n-ogons, apresentam-se os resultados em duas subclasses de grid n-ogons: os MIN-AREA grid n-ogon e os Spiral grid n-ogon. November 17, 2006 Localização de Serviços Semiobnóxios. Alguns Modelos Resumo: Serviços semiobnóxios são serviços que prestam serviços às comunidades mas, simultaneamente devido ao tipo de funções que desempenham são poluentes sendo a sua proximidade desagradável. Assim, os modelos considerados para o problema de localização de serviços semiobnóxios são modelos de localização com dois objectivos. Os objectivos contraditórios são a minimização do efeito obnóxio quer em termos totais ou de pior caso e a maximização da acessibilidade das comunidades aos serviços quer em termos médios ou de pior caso. Modelos sem restrições de capacidade nos serviços, com restrições de capacidade máxima e restrições de capacidade por níveis são apresentados e comparados relativamente aos tempos médios de execução e à equidade das soluções obtidas. Estudam-se ainda, para todos os modelos, as alterações provocadas pela inclusão de uma restrição adicional ao investimento. Os resultados computacionais apresentados e analisados dizem respeito a problemas gerados aleatoriamente. November 10, 2006 Diagrama de Voronoi Envolvente Resumo: Pretende-se dar continuação ao estudo da 1-boa iluminação de alcance limitado como uma variante dos problemas clássicos de iluminação em Geometria Computacional. Com este propósito, será apresentado o Diagrama de Voronoi Envolvente que divide o espaço das luzes em várias regiões 1-bem iluminadas, assim como um algoritmo para a sua construção e algumas das suas propriedades. Será também apresentado outro algoritmo para a construção do referido diagrama restringido a um segmento de recta. November 3, 2006 Propriedades de diferenciabilidade de Invólucros não Standard – I Resumo: A uma função interna entre (extensões de) espaços localmente convexos que transforma vectores finitos em vectores finitos e respeita a proximidade infinitesimal, associa-se naturalmente uma função entre os invólucros dos domínio e do conjunto de chegada, espaços localmente convexos usuais (standard), quocientes por uma relação de equivalência; esta função é também designada por invólucro da inicial e as suas propriedades de diferenciabilidade de ambas estão fortemente relacionadas. October 27, 2006 Controlabilidade para algumas equações não lineares de física matemática Resumo: Discutimos a possibilidade de estender alguns métodos e ideias da teoria geométrica do controlo para estudo de sistemas de dimensão infinita, em particular para equações com derivadas parciais de física matemática (Navier-Stokes, Euler, Burgers etc.). July 21, 2006 Tornados and Turbulent Kinetic Energy Abstract: We will discuss connection between governing equations and constitutive theory in atmospheric boundary layer. Such a connection is of prime importance in building algorithms for numerical simulations. We consider averaging in time and its relation to the Boussinesq approximation of the governing equations. We will also talk about instantaneous turbulent kinetic energy and a balance equation for its material derivative. June 8, 2006 Nonessential Objective Functions in Vector Optimization Problems Abstract: In vector optimization problems among the given objective functions there exist some which do not influence the set of efficient solutions. These objective functions are said to be nonessential. In this paper we present a new method: how to test if the objective function is nonessential in a linear problem. May 19, 2006 Uma Conexão de Galois Resumo: Para cada álgebra dinâmica separável com elemento zero, D, iremos estabelecer uma conecção de Galois entre os reticulados CongD e IdeD , respectivamente, das congruências dinâmicas e dos ideais dinâmicos definidos em D. April 28, 2006 On a recursive equation, indexed by a tree, over p-adic numbers Abstract: It is completely described the set of all solutions of a recursive equation, arising from the Bethe lattice models over $p$-adic numbers. April 21, 2006 Técnicas de optimização baseadas na Biologia Resumo: Esta palestra apresenta os principais conceitos de um conjunto de técnicas de computação baseadas na biologia e que têm sido utilizadas com sucesso em problemas práticos. A maior parte da apresentação cobrirá uma área específica da computação bioinspirada, a saber, a computação evolutiva. No final serão apresentados exemplos de utilização da computação evolutiva em problemas reais. April 7, 2006 Computações de larga escala em teoria dos números Resumo: Descrição e apresentação de alguns resultados sobre: - a diferença Li(x)-pi(x) - a conjectura de Goldbach - a conjectura de Artin (raízes primitivas) - a conjectura de Collatz (3x+1) Com a excepção do primeiro tópico, os cálculos foram efectuados usando uma "grid" computacional formada pelos computadores das salas de aulas do DET (e alguns outros). Todos eles são recordes a nível mundial. No total, até ao momento foram gastos mais de 300 anos de tempo de cálculo. March 31, 2006 Eigenvalue Problems For Some Hybrid Aerial Cable-Way Systems Abstract: Dynamics of some hybrid systems of aerial cable-ways is investigated. The eigenvalue problems are considered for such systems at different assumptions. The overview of different methods for similar eigenvalue problems is given. For investigations the method of the normal fundamental systems is applied, which is effective for the considered problem. Dependence of dynamical characteristics of the systems on the controlled parameter is studied. March 24, 2006 A Chernoff scheme to approximate a nonlocal parabolic problem Abstract: In this talk we study a nonlocal parabolic equation obtained from the reduction of the well-known thermistor problem. Error estimate bounds are established for a family of time discretization scheme which the idea leads to Magenes. March 17, 2006 Teorema de Noether no Cálculo das Variações Fraccionário Resumo: O estudo de problemas do cálculo das variações com derivadas fraccionárias é um assunto recente, tendo sido obtida uma versão da condição necessária de Euler-Lagrange para este contexto. Neste trabalho usamos a noção de extremal fraccionária para a demonstração de um teorema do tipo de Noether. Para tal generalizamos o conceito de lei de conservação, introduzindo um operador de diferenciação adequado. March 10, 2006 Programação semi-infinita convexa: pontos imóveis e condições de optimalidade Resumo: Considera-se o problema de Programação Semi-Infinita (PSI) Convexa. Introduzem-se os novos conceitos de pontos imóveis e de ordens de imobilidade e descreve-se um algoritmo construtivo para a sua determinação (algoritmo DIO). Na base da informação sobre todos os pontos imóveis do problema convexo PSI formula-se um problema especial de Programação Não Linear (PNL) e mostra-se que as condições de optimalidade para o problema de PSI (infinito) podem ser substituídas por condições de optimalidade para o problema de PNL (finito). March 3, 2006 Topological entropy of "Game of Life" and similar cellular automata Abstract: We shall remind basic notations of the entropy theory for dynamical systems as well as the rules of "Game of Life". We shall discuss methods for estimation of the complexity of cellular automaton i.e. topological entropy and its renormalization. Those who are not familiar with "Game of Life" can visit www.math.com/students/wonders/life/life.html for interesting information. February 24, 2006 On the Formula for Impedance Change Used in Problems of Non-Destructive Testing by Eddy Current Method Abstract: The paper is devoted to the problems of non-destructive testing by the eddy current method. The authors analytically prove and investigate the fairness of the known formula for the induced changes in impedance, describing the influence of a conducting medium with a flaw of arbitrary shape on a source of current. The formula seems to be used before without a mathematical proof. February 17, 2006 Unsteady flows of a viscous incompressible fluid Abstract: 1) "Transient viscous flow in an annulus". It is considered a long horizontal annulus filled with a viscous fluid. At time t=0 the flow is instantaneously decelerated so that the total fluid flux through the cross-section of the annulus becomes equal to zero. The method of Laplace transform is used to derive an analytical solution for unsteady viscous flow in an annulus after a sudden reduction of the flow rate. The method of matched asymptotic expansions is used to derive an approximate solution. 2) "A mathematical model for detection of a partial blockage in pipelines using fluid transients". A one-dimensional linearized equation for pressure perturbation in the presence of a blockage is solved analytically by the method of the Laplace transform. February 10, 2006 Um problema complicado envolvendo árvores de custo mínimo Resumo: Apresenta-se um novo problema que envolve a determinação de uma árvore de custo mínimo sujeita a restrições de grau nos seus vértices. Mostrar-se-á, também, porque é este problema "complicado", ou seja, NP--difícil. February 3, 2006 Sobre a Complexidade de Circuitos no Modelo Quântico de Computação Resumo: Em 1985, Deutsch propôs dois modelos de Computação Quântica: Máquinas de Turing Quânticas e Circuitos Quânticos. A formalização do modelo de Circuitos Quânticos, em 1993, deve-se a Bernstein e Vazirani bem como a Yao. O trabalho de investigação que se seguiu, no âmbito da demonstração da equivalência entre estes dois modelos, revelou novos resultados, de certa forma inesperados, no que respeita à hierarquia das classes de complexidade. Nesta apresentação formulam-se generalizações de certos conceitos básicos (qubit, circuito quântico, família de circuitos quânticos) no contexto de sistemas quânticos híbridos e discutem-se alguns resultados relativos às seguintes classes de complexidade situadas na base da hierarquia quântica: QNC -- informalmente, o análogo quântico da classe de problemas resolúveis por circuitos Booleanos de tamanho polinomial e profundidade poli-logarítmica; QNC^0 -- informalmente, a classe de problemas resolúveis por circuitos quânticos de profundidade constante.