CEOC Seminars 2003 December 12, 2003 Contribuições da Álgebra Moderna para a Teoria de Controlo Não Linear Resumo: Álgebras não associativas, álgebras de Hopfe cálculo dobre séries formais são ferramentas eficazes no tratamento de problemas de controlo não linear. Nesta apresentação mostraremos como os objectos de Geometria Diferencial (campos de vectores, fluxos em variedades, etc.) podem ser vistos como operadores lineares em espaços de Fréchet. As propriedades destes operadores serão caracterizadas de uma forma puramente algébrica. Deste modo equações diferenciais não lineares e não autónomas para a estrutura de álgebra de Lie. Para terminar mostrar-se-á como estes objectos formais podem ser usados para resolver um problema de grande interesse na robótica, o problema da estabilizabilidade de um sistema arbitrário de dois corpos que rolem um sobre o outro sem deslizar ou torcer. December 5, 2003 Geração de Polígonos Ortogonais Resumo: Para testar e avaliar experimentalmente algoritmos de Geometria Computacional é, por vezes, necessário construir amostras aleatórias de objectos geométricos, como por exemplo, polígonos. Tal foi também a principal motivação deste trabalho, o qual se encontra no âmbito dum projecto sobre Problemas de Galeria de Arte, que tem vindo a ser desenvolvido em colaboração com o Prof. Leslie Bajuelos e Fábio Marques da Universidade de Aveiro. Descreveremos dois métodos para a geração de POs: um requer tempo quadrático e espaço linear no número de vértices; outro é computacionalmente mais dispendioso, mas tratando a geração como um problema de satisfação de restrições em domínios finitos permite (teoricamente) impor mais condições sobre os polígonos gerados. Continua em aberto o problema da caracterização da aleatoriedade das amostras geradas. November 28, 2003 Uma demonstração não Standard do Teorema de Existência de Caratheodory Resumo: ... October 31, 2003 Ensino Assistido vs E-Learning Resumo: O Projecto Matemática Ensino (PmatE) desenvolveu e mantém em desenvolvimento um conjunto de ferramentas que apresentam uma perpectiva inovadora sobre as tradicionais aplicações de eLearning - uma componente lúdica capaz de atrair os estudantes ao estudo. O trabalho desenvolvido neste domínio teve início em 1990/91, mas a plataforma tecnológica necessitou de uma profunda reestruturação no sentido de acompanhar os recentes desenvolvimentos nas novas tecnologias de informação e da comunicação. Esta tarefa foi iniciada em 2002. Esta apresentaçãopretende dar a conecer o trabalho desenvolvido no estudo e reformulação da nova plataforma base das aplicações do PmatE. October 24, 2003 Web Application Maker - a declarative web database tool Abstract: WAM allows rapid development of large web databases applications for SQL Server, by generating interface fragments from database-resident declarative specifications. The interface is available at runtime, contituting a high level API for tradicional JavaScript preogrammers. WAM is being used in applications in Portugal and the USA. The tool will be presented, illustrated with applications. It will also be argued that its meta-model and runtime machinery provide a fertile platform for cool Master thesis and graduation projects. October 17, 2003 Uma Introdução à Computação Quântica Resumo: Uma Introdução à Computação Quântica onde, com uns quantas de História e uns qubits de Matemática, se tentará descrever o algoritmo quântico de Shor para o Problema da Facorização em Primos. September 18, 2003 Self-Clique Graphs Abstract: The clique graph of a grah is te intersection graph of its (maximal) cliques. A graph is self-clique when it is isomorphic with its clique graph, and is clique-Helly when its clique satisfy the Helly property. We discuss the problem of finding families of graphs which are self-clique. We prove that a graph is clique-Helly and self-clique if and only if it admits a quasi-symmetric clique matrix, that is, a clique matrix whose families of row and column vectors are identical. We also give a characterization of such graphs in terms of vertex-clique duality. We describe new classes of self-clique and 2-self-clique graphs. Further, we consider some problems on permuted matrices (matrices obtained by permuting the rows and/or columns of a given matrix). In particular, we prove that deciding whether a (0,1)-matrix admits a symmetric (quasi-symmetric) permuted matrix is a graph (hypergraph) isomorphism complete. June 20, 2003 Planeamento Integrado da Produção e Sequenciamento de Lotes na Indústria de Tintas: Programação Inteira Mista, Decomposição e Programação por Restrições Resumo: Considera-se o problema de planeamento conjunto da produção de lotes e do seu sequenciamento numa linha de produção da indústria de tintas. Enquanto que o planeamento da produção considera um horizonte de 1 ou 2 semanas, o sequenciamento dos lotes (tarefas) nas máquinas tem que ser estabelecido diariamente. De forma a ser possível uma utilização correcta da capacidade de produção, é necessário considerar um modelo onde o planeamento é feito de forma integrada. No entanto, a complexidade deste modelo não permite resolver instâncias de dimensão de interesse prático. A abordagem apresentada considera um modelo em programação inteira mista para o problema de dimensionamento de lotes de produção. A existência de um sequenciamento compatível é então verificada resolvendo um problema simples de sequenciamento, recorrendo-se à programação por restrições. No caso de não existir tal sequenciamento, esta informação é incorporada no modelo inicial sob a forma de plano de corte, sendo este procedimento repetido. Apresentam-se resultados computacionais para um problema real de uma fábrica de tintas. June 13, 2003 Formulation of Linear Optimization Problems in C++ FLOPC++ (www.mat.ua.pt/thh/flopc) is a new C++ class library for algebraic modelling of linear optimization problems (LP/MIP). Using FLOPC++, linear optimization models can be specified in a declarative style, similar to algebraic modelling languages such as GAMS and AMPL, whithin a C++ program. As a result, the traditional strengths of algebraic modelling languages are combined with easy embedding of linear optimization in software applications. In this talk FLOPC++ will be introduced, and the motivation for its development as well as a comparision with other modelling tools will be presented. June 6, 2003 Polinómios Cúbicos em Espaços de Curvatura Constante Resumo: A determinação de uma conveniente generalização do conceito de polinómio cúbico para espaços não Euclidianos tem sido um problema longamente estudado, de especial interesse no planeamento de trajectórias em aeronáutica e robótica. Embora a formulação variacional seja teoricamente a abordagem mais natural, a dificuldade encontrada na resolução das respectivas equações de Euler-Lagrange inviabilizam a sua aplicação. Estas equações conduzem, em geral, à resolução de sistemas não lineares de equações diferenciais de quarta ordem em R^n. Este problema é analisado no contexto dos espaços de curvatura constante, em particular, no caso da esfera S^n. São deduzidos invariantes ao longo de polinómios cúbicos que desempenham um papel fundamental na redução da dimensão do sistema de equações diferenciais e na separação das suas variáveis. Uma condição suficiente de optimização é apresentada. May 30, 2003 Splines generalizados em espaços Euclidianos Resumo: Nesta comunicação é apresentada e discutida uma definição de splines generalizados em espaços Euclidianos de dimensão arbitrária. Esta definição baseia-se na relação existente entre estas curvas e problemas de controlo optimal para sistemas lineares de controlo invariantes no tempo. Alguns tópicos abordados no decorrer da comunicação são: splines generalizados escalares (por exemplo o spline cúbico); problemas de controlo optimal; abordagem variacional de problemas de controlo optimal; equações diferenciais lineares com coeficientes matriciais. April 4, 2003 Valores próprios múltiplos de matrizes cujo grafo é uma árvore Resumo: Entre os problemas mais importantes da Teoria das Matrizes contam-se os chamados problemas inversos. Um dos problemas é o problema inverso dos valores próprios: dados n números complexos em que condições existirá uma matriz de um certo conjunto (matriz de elementos positivos, matriz com um certo grafo...) tendo esses números como valores próprios. A questão abordada neste seminário será a seguinte: dada uma árvore T, com n vértices, e n números reais (distintos ou não), em que condições existe uma matriz simétrica real com grafo T e tendo aqueles números como valores próprios. No caso de os números dados serem todos distintos, existe sempre uma tal matriz; será, por isso, dado especial ênfase aqui ao caso em aqueles números são todos distintos; a solução deste problema não é conhecida salvo em casos particulares, dependendo fortemente da árvore considerada; serão mencionados vários problemas relacionados (cuja solução em geral também não é conhecida) como o das possíveis listas de multiplicidades para uma matriz simétrica cujo grafo é uma árvore. March 28, 2003 Contribuições da Optimização Combinatória na Protecção de Dados Estatísticos Resumo: Os dados publicados pelos institutos de estatística são previamente sujeitos a modificações para evitar a divulgação de informação confidencial sobre entidades como pessoas ou empresas. Os dados podem ser substituídos por novos dados ou omitidos. Na técnica da supressão essas dados são omitidos, sendo necessário para garantir a sua protecção, resolver um problema de optimização combinatória designado por Problema da Supressão (CSP). O CSP tem variantes que são função do tipo de dados, do grau de protecção pretendido para os dados confidenciais, e da medida utilizada para avaliar a perda de informação associada à supressão de um dado estatístico. É conhecido um algoritmo polinomial para resolver uma particular variante do problema. Na sua versão geral o CSP é NP-difícil. Neste seminário serão apresentados modelos e algorítmos de obtenção de minorantes e de soluções aproximadas para o CSP. March 21, 2003 O Cálculo de Variações Estocástico Não Standard (II) Resumo: Falaremos sobre Movimentos Brownianos e Passeios Aleatórios de Anderson e teceremos comentários sobre Integração e Diferenciação Estocástica por meio de discretizações internas nos números hiper-reais. March 14, 2003 Quantum computation and spin systems Abstract: We present a brief introduction to some aspects of quantum computation from a control theorist point of view. We focus our attention on spin systems, which exhibit a very simple behavior from the point of view of Quantum Mechanics, and provide many interesting examples. Our goal in this seminar is to formulate and discuss optimal control problems which appear naturally in applications. March 7, 2003 Relating the Lovász vartheta number with some convex quadratic bounds on the stability number of a graph Abstract: In previous works on upper bound on the stability number of a graph based on quadratic programming was introduced. In this talk a set of generalizations of this bound are introduced which will be related with the well known Lovász vartheta number. Several new results will be presented and discussed. February 21, 2003 Generic singularities of parametric average optimization of control systems Abstract: A control system on a smooth manifold is defined by a smooth family of vector fields parametrized by a smooth manifold of values of a control parameter. We optimize the time averaged profit along admissible motions og the control system. In such situation the optimal strategy can be of various nature [1], [2]. The situation is more complicated when the system itself or the density of the profit depend from additional parameters. In that case the time averaged profit as to do that too. Working in such a generic case we describe some optimal strategies and classify the respective singularities of time averaged profit like a function of parameters up to smooth diffeomorphism of its grafic space fibered over the parameter. These singularities are stable with respect to small perturbation of the system (profit density) and they are connected with generic relative maximum singularities studied in [3], [4]. [1] V.I. Arnol'd - Averaged optimization and phase transition in control dynamical systems// Funct. Anal. and its Appl. 36 (2002), 1-11. [2] V.I. Arnol'd - On a Variational Problem Connected with Phase Transisitons of Means in Controllable Dynamical Systems//in M. Birman (ed) et al., Nonlinear Problems in Mathematical Physics and Related Topics I, Kluwer/Plenum Publishers, ISBN 0-306-47333-X, July 2002. [3] Davydov, A.A.; Zakalyukin, V.M. - Coincidence of generic relative minimum singularities in problems with explicit and implicit constraints// J. Math. Sci., New York 103, No.6, 709-724 (2001). [4] Davydov, A.A.; Zakalyukin, V.M. - Classification of relative minima singularities//Janeczko, Stanislaw (ed.) et al., Geometry and topology of caustics - CAUSTICS '98. Proceedings of the Banach Center symposium, Warsaw, Poland, June 15-27, 1998. Warsaw: Polish Academy of Sciences, Institute of Mathematics, Banach Cent. Publ. 50, 75-90 (1999).