CEOC Seminars 2007 November 30, 2007 O Contorno alfa-Envolvente Resumo: Cada noção de profundidade induz uma estratificação do plano em regiões de pontos que partilham a mesma profundidade. As fronteiras destas regiões são conhecidas como contornos de profundidade e são utilizados na visualização de dados. Há alguns contornos de profundidade conhecidos e já estudados como os da profundidade de Tukey ou de Delaunay. Os contornos de profundidade também têm aplicações em iluminação de qualidade, como é o caso da boa alfa-iluminação. Este tipo de iluminação de qualidade é uma generalização do conceito de 1-boa iluminação de alcance limitado que recorre a sectores não orientados de ângulo alfa. Neste seminário pretende-se abordar o primeiro contorno da alfa-profundidade: o contorno alfa-Envolvente e a sua relação com a iluminação de qualidade. November 16, 2007 A análise Não Standard de grafos (infinitos) Resumo: Far-se-á uma apresentação de aspectos fundamentais inspirada nos trabalhos de Armen Zemanian. Ordinais, métricas e correspondentes galáxias. November 2, 2007 Equação de Navier-Stokes: controlabilidade por meio de forças de dimensão finita Resumo: Consideramos a equação de Navier-Stokes num domínio bidimensional e estudamos a sua controlabilidade. Consideramos controlos internos e estamos interessados no caso em que os controlos tomam valores num espaço de dimensão finita g=span{g_1, ..., g_r}. Chegamos à conclusão de que a controlabilidade aproximada é possível se o conjunto de campos vectoriais {g_1, ..., g_r} é saturante. Definimos conjunto saturante e apresentamos exemplos de conjuntos saturantes para alguns tipos de domínios e condições de fronteira. October 26, 2007 Partição e geração de colunas e tópicos relacionados: aplicação ao problema de corte Resumo: O método de geração de colunas foi proposto por Gilmore e Gomory, nos anos 60, para abordar o problema de corte de stock com uma dimensão. Por outro lado, o método de partição e avaliação (branch-and-bound) foi também proposto nos anos 60 para resolver problemas de programação inteira. O método da partição e geração de colunas (branch-and-price) envolve a resolução de modelos com um número exponencial de variáveis, em que é necessário fazer geração de colunas em todos os nós da árvore de partição e avaliação. Nesta apresentação, revemos a decomposição de Dantzig-Wolfe, a importância de utilizar modelos fortes em programação inteira e conceitos relacionados com o método de partição e geração de colunas, ilustrando-os com aplicações ao problema de corte. São apresentados um modelo de fluxos em arco para o problema de corte, que é usado para derivar uma regra de partição robusta que não induz alterações na estrutura do subproblema, métodos para acelerar a resolução dos modelos de geração de colunas e alguns tópicos de investigação em curso. October 19, 2007 Colorações, Fluxos e Polinómios Resumo: Introduzem-se alguns resultados sobre colorações de vértices, arestas e faces de grafos, nomeadamente grafos planares. Estabelecem-se relações entre colorações de faces e fluxos e entre polinómios cromáticos e polinómios de fluxos. Apresentam-se algumas das principais conjecturas e problemas em aberto, bem como avanços conseguidos. May 25, 2007 Limites de difusão hidrodinâmicos para equações cinéticas de transporte Resumo: As equações cinéticas do tipo da equação de Boltzmann descrevem o comportamento estatístico de um sistema de partículas a uma escala "mesoescópica". É possível obter para uma grande classe de equações deste tipo limites de relaxação que conduzem a aproximações quer hiperbólicas, quer parabólicas. Veremos uma aplicação interessante a uma equação de transporte de radiação. May 18, 2007 Inclusões diferenciais vectoriais, noções de convexidade em sentido generalizado e aplicações a problemas de minimização não quasiconvexos Resumo: Consideram-se problemas de tipo vectorial escritos sob a forma de uma inclusão vectorial. O estudo de condições suficientes de existência de solução para este tipo de problemas foi desenvolvido por Dacorogna-Marcellini e Müller-Sverák, e levou à introdução de conceitos de invólucro convexo em sentido generalizado nem sempre coerentes com a teoria clássica de convexidade. Numa primeira parte da exposição propõe-se uma noção de conjunto quasiconvexo que é justificada pelas relações com as definições de conjunto policonvexo e conjunto rank-1 convexo. Ilustra-se então o método da Categoria de Baire de Dacorogna-Marcellini para a existência de solução de certas inclusões diferenciais através da aplicação a um problema envolvendo os valores singulares e o determinante da matriz gradiente. Por último, observa-se como a resolução da inclusão diferencial considerada permite garantir a existência de solução para um problema de minimização vectorial não quasiconvexo. May 11, 2007 Área interior em gestão florestal: um modelo de programação inteira Resumo: A gestão florestal tradicional tem como objectivo maximizar o benefício económico proveniente do corte da madeira. No entanto as operações florestais têm, em geral, um impacto negativo noutros valores como a biodiversidade, estética, qualidade da água e solos. Em particular, a calendarização e localização dos cortes florestais têm um efeito na paisagem que pode ser mais ou menos favorável à preservação daqueles valores. Nesta apresentação considera-se uma floresta onde há produção de madeira para corte. Uma característica favorável à conservação da vida animal é a existência de áreas interiores (core area), isto é zonas na floresta que estão longe do efeito de perturbações como estradas, a orla ou zonas recém cortadas. Pretende-se desta forma contribuir para a redução da fragmentação, bem como criar zonas de refugio para alguns animais. Considera-se um modelo em programação inteira, onde se pretende maximizar o benefício económico proveniente da produção de madeira, sujeito a restrições de área interior mínima. Apresentam-se resultados computacionais. May 2, 2007 How to determine the conjugacy of two hyperbolic operators using multidimensional continued fractions Abstract: Given two hyperbolic operators A and B, how to determine if there exists an integer unimodular operator C, such that AC=CB_ At this moment there seems to be no nice purely algebraic solution of this problem in the general case. However, considering the so called Klein polyhedra coresponding to these operators, which are in the essence the multidimensional generalization of the geometric interpretation of continued fractions, it is possible to find the answer to this question in a quite short period of time. April 27, 2007 Alguns problemas relacionados com Grid n-ogons Resumo: Apresentam-se alguns problemas relacionados com grid n-ogons. Um grid n-ogon é um polígono ortogonal com n vértices e sem arestas colineares, definido numa grelha quadrada (n/2)x(n/2) . Consideram-se, em particular, os THIN grid n-ogons e introduz-se uma possível classificação destes polígonos utilizando cadeias. Estudam-se os problemas Minimum Vertex Guard e Maximum Hidden Vertex Set nos grid n-ogons. O problema Minimum Vertex Guard consiste em determinar o número mínimo de guardas, colocados em vértices, necessário para vigiar um polígono. O problema Maximum Hidden Vertex Set consiste em determinar o número máximo de vértices num polígono de modo que esses vértices sejam ocultos dois a dois. April 20, 2007 Integração dos Problema de Rotas para Veículos com Janelas Temporais e Empacotamento de Contentores Resumo: Na generalidade dos estudos de problemas reais de distribuição, existem algumas considerações de ordem prática que não são consideradas. Uma dessas considerações está relacionada com a capacidade dos veículos, não só em termos de peso e volume, mas também em termos de colocação física da carga. De facto, tanto a ordem pela qual os clientes são visitados como a forma de colocação da carga no veículo são características importantes para a qualidade e admissibilidade da solução da distribuição. Nesta perspectiva, estamos perante dois problemas de optimização combinatória: Problema de Planeamento de Rotas para Veículos com Janelas Temporais (VRPTW) e Empacotamento em Contentores (CLP), entre os quais existe uma dependência recíproca, isto é, ao planearmos as rotas deve-se ter em consideração os pesos máximos da carga a distribuir, o seu volume e também a colocação desta em termos de ordem e estabilidade. Para um bom serviço de distribuição é necessário atender a todas estas considerações. Surge assim a necessidade da integração dos problemas VRPTW e CLP. Esta integração origina um novo problema denominado por Planeamento de Rotas e Empacotamento em Veículos (PREV). April 13, 2007 Problemas de Afectação com Preferências Resumo: Em complemento da apresentação "Casamentos estáveis e colocação de professores" (realizada no âmbito dos seminários do CEOC a 11 Março de 2005), descreve-se agora o trabalho desenvolvido posteriormente. Nesse trabalho, demonstrou-se que o problema da colocação pode ser resolvido polinomialmente. Apresenta-se o algoritmo que se desenvolveu para resolver o problema, baseado numa redução a problemas de determinação de emparelhamentos de cardinalidade máxima em grafos bipartidos, combinada com uma propagação adequada das restrições de estabilidade impostas pelas prioridades relativas dos docentes, suas preferências, e pela existência de docentes com direito a certos lugares. March 23, 2007 Ferramentas de modelação em optimização não linear Resumo: A modelação matemática de problemas reais ou académicos de optimização é apoiada por um conjunto de ferramentas de modelação. Essas ferramentas permitem uma fácil e rápida codificação dos problemas permitindo a sua posterior resolução de uma forma eficiente. Por outro lado o desenvolvimento de software científico na área da optimização é também apoiada pelas mesmas ferramentas na sua validação. Essa validação é suportada por um conjunto de colecções de problemas, quer reais, quer académicos. Nesta palestra serão apresentadas algumas ferramentas para modelação de problemas de optimização (AMPL, GAMS e CUTEr) bem como algumas colecções de problemas. É também descrita uma técnica de análise de desempenho entre diferentes softwares de resolução de problemas (perfis de desempenho). March 16, 2007 Teorema de Noether no Cálculo das Variações e Controlo Óptimo - resultados recentes Resumo: o seu célebre artigo publicado em 1918, Emmy Noether demonstrou um princípio geral sobre leis de conservação com importantes implicações em várias áreas da Física moderna, tais como a mecânica clássica e quântica, óptica geométrica e teoria da relatividade... O princípio de Noether afirma que "a invariância do problema sob transformações infinitesimais dependentes de um parâmetro, implica a existência de uma lei de conservação ao longo das extremais". Neste trabalho apresentamos algumas generalizações recentes do teorema de Noether no Cálculo das Variações e Controlo Óptimo: para problemas não-conservativos, fraccionários, com derivadas de escala e composições de funções. March 9, 2007 Boa Iluminação Angular Resumo: Pretende-se abordar duas generalizações do conceito de 1-boa iluminação de alcance limitado. A primeira recorre a quadrantes orientados e é por isso denominada de boa iluminação ortogonal. Será também apresentado de forma breve o respectivo diagrama E-Voronoi desta variante. A segunda generalização utiliza sectores não orientados (ângulo e posição variáveis) e é conhecida pela boa theta-iluminação. March 2, 2007 Ontologias e Topic-Maps: extracção, validação e navegação; aplicações, o NAVMAP Resumo: A necessidade de trabalhar com Ontologias para classificar e arquivar, ou para trabalhar uniformemente com fontes de informação distintas (inter-operabilidade), levou-nos a criar no grupo uma linha de investigação em torno da norma Topic-Maps e da sua representação em XML usando o dialecto XTM. Nesta palestra, que vou organizar em 2 partes, pretendo começar por caracterizar esta linha de trabalho, introduzindo a noção de ontologia e sua importância actual em informática e apresentando muito sumariamente a plataforma Metamorphosis que concebemos para manipular Topic-Maps, desde a sua extracção a partir de fontes heterogéneas até a sua publicação na Web com mecanismos de navegação conceptual. A sua aplicação na construção de um museu virtual, como é o caso do Museu da Emigração, será referida para ilustrar a ideia. Na segunda parte, relaciono o tema com os conhecidos Mapas de Conceitos usados em Educação para planificar as unidades de ensino de um curso e apresento um sistema, o NAVMAP - Mapa de Conceitos e Catálogo de Recursos: uma ajuda para planificar o ensino, desenvolvido para tornar o site de uma disciplina num espaço de aprendizagem. February 16, 2007 Caça aos patos Resumo: Singularidades de certas equações diferenciais ordinárias: um estudo com infinitésimos. February 9, 2007 Geometria infinitesimal em curvas Resumo: Serão apresentadas várias versões não standard de cúspides, estabelecendo uma relação entre elas assim como com algumas das definições clássicas de cúspides existentes. De seguida apresentamos um método para determinar a envolvente a uma família de curvas no espaço euclidiano de dimensão n. Por último apresentamos uma curva solução ideal de um problema de máxima resistência. February 2, 2007 Singularidades do proveito médio óptimo para estratégias estacionárias Resumo: Considere-se o problema que consiste em maximizar o proveito médio (temporal) de uma densidade de proveito (diferenciável) numa variedade compacta unidimensional (diferenciável) ao longo de uma trajectória originada por uma estratégia estacionária de um sistema polidinâmico. Quando o problema depende de um parâmetro k-dimensional, estuda-se o proveito médio óptimo como função do parâmetro e apresenta-se a classificação genérica das suas singulariades para k<=3.