Mapeamento de difusão no reconhecimento e reconstrução de sinais

Em muitas representações de objetos ou sistemas físicos se faz necessário a utilização de técnicas de redução de dimensionalidade que possibilitam a análise dos dados em baixas dimensões, capturando os parâmetros essenciais associados ao problema. No contexto de aprendizagem de máquina esta redução se destina primordialmente à clusterização, reconhecimento e reconstrução de sinais. Esta tese faz uma análise meticulosa destes tópicos e suas conexões que se encontram em verdadeira ebulição na literatura, sendo o mapeamento de difusão o foco principal deste trabalho. Tal método é construído a partir de um grafo onde os vértices são os sinais (dados do problema) e o peso das arestas é estabelecido a partir do núcleo gaussiano da equação do calor. Além disso, um processo de Markov é estabelecido o que permite a visualização do problema em diferentes escalas conforme variação de um determinado parâmetro t: Um outro parâmetro de escala, Є, para o núcleo gaussiano é avaliado com cuidado relacionando-o com a dinâmica de Markov de forma a poder aprender a variedade que eventualmente seja o suporte do dados. Nesta tese é proposto o reconhecimento de imagens digitais envolvendo transformações de rotação e variação de iluminação. Também o problema da reconstrução de sinais é atacado com a proposta de pré-imagem utilizando-se da otimização de uma função custo com um parâmetro regularizador, γ, que leva em conta também o conjunto de dados iniciais.

Formulação teórica dos fundamentos da otimização global topográfica com análise de desempenho e aplicações à estabilidade de fases de misturas termodinâmicas

Métodos de otimização que utilizam condições de otimalidade de primeira e/ou segunda ordem são conhecidos por serem eficientes. Comumente, esses métodos iterativos são desenvolvidos e analisados à luz da análise matemática do espaço euclidiano n-dimensional, cuja natureza é de caráter local. Consequentemente, esses métodos levam a algoritmos iterativos que executam apenas as buscas locais. Assim, a aplicação de tais algoritmos para o cálculo de minimizadores globais de uma função não linear,especialmente não-convexas e multimodais, depende fortemente da localização dos pontos de partida. O método de Otimização Global Topográfico é um algoritmo de agrupamento, que utiliza uma abordagem baseada em conceitos elementares da teoria dos grafos, a fim de gerar bons pontos de partida para os métodos de busca local, a partir de pontos distribuídos de modo uniforme no interior da região viável. Este trabalho tem dois objetivos. O primeiro é realizar uma nova abordagem sobre método de Otimização Global Topográfica, onde, pela primeira vez, seus fundamentos são formalmente descritos e suas propriedades básicas são matematicamente comprovadas. Neste contexto, propõe-se uma fórmula semi-empírica para calcular o parâmetro chave deste algoritmo de agrupamento, e, usando um método robusto e eficiente de direções viáveis por pontos-interiores, estendemos o uso do método de Otimização Global Topográfica a problemas com restrições de desigualdade. O segundo objetivo é a aplicação deste método para a análise de estabilidade de fase em misturas termodinâmicas,o qual consiste em determinar se uma dada mistura se apresenta em uma ou mais fases. A solução deste problema de otimização global é necessária para o cálculo do equilíbrio de fases, que é um problema de grande importância em processos da engenharia, como, por exemplo, na separação por destilação, em processos de extração e simulação da recuperação terciária de petróleo, entre outros. Além disso, afim de ter uma avaliação inicial do potencial dessa técnica, primeiro vamos resolver 70 problemas testes, e então comparar o desempenho do método proposto aqui com o solver MIDACO, um poderoso software recentemente introduzido no campo da otimização global.

Otimização global topográfica aplicada a problemas de otimização com restrições de igualdade e desigualdade

Os métodos de otimização que adotam condições de otimalidade de primeira e/ou segunda ordem são eficientes e normalmente esses métodos iterativos são desenvolvidos e analisados através da análise matemática do espaço euclidiano n-dimensional, o qual tem caráter local. Esses métodos levam a algoritmos iterativos que são usados para o cálculo de minimizadores globais de uma função não linear, principalmente não-convexas e multimodais, dependendo da posição dos pontos de partida. Método de Otimização Global Topográfico é um algoritmo de agrupamento, o qual é fundamentado nos conceitos elementares da teoria dos grafos, com a finalidade de gerar bons pontos de partida para os métodos de busca local, com base nos pontos distribuídos de modo uniforme no interior da região viável. Este trabalho tem como objetivo a aplicação do método de Otimização Global Topográfica junto com um método robusto e eficaz de direções viáveis por pontos-interiores a problemas de otimização que tem restrições de igualdade e/ou desigualdade lineares e/ou não lineares, que constituem conjuntos viáveis com interiores não vazios. Para cada um destes problemas, é representado também um hiper-retângulo compreendendo cada conjunto viável, onde os pontos amostrais são gerados.

Bicontactual hypermaps

Esta tese dedica-se ao estudo de hipermapas regulares bicontactuais, hipermapas com a propriedade que cada hiperface contacta só com outras duas hiperfaces. Nos anos 70, S. Wilson classificou os mapas bicontactuais e, em 2003, Wilson e Breda d’Azevedo classificaram os hipermapas bicontactuais no caso não-orientável. Quando esta propriedade é transferida para hipermapas origina três tipos de bicontactualidade, atendendo ao modo como as duas hiperfaces aparecem à volta de uma hiperface fixa: edge-twin, vertextwin and alternate (dois deles são o dual um do outro). Um hipermapa topológico é um mergulho celular de um grafo conexo trivalente numa superfície compacta e conexa tal que as células são 3-coloridas. Ou de maneira mais simples, um hipermapa pode ser visto como um mapa bipartido. Um hipermapa orientado regular é um triplo ordenado consistindo num conjunto finito e dois geradores, que são permutações (involuções) do conjunto tal que o grupo gerado por eles, chamado o grupo de monodromia, actua regularmente no conjunto. Nesta tese, damos uma classificação de todos os hipermapas orientados regulares bicontactuais e, para completar, reclassificamos, usando o nosso método algébrico, os hipermapas não-orientáveis bicontactuais.

Politopo de Birkhoff acíclico

Neste trabalho estabelece-se uma interpreta c~ao geom etrica, em termos da teoria dos grafos, para v ertices, arestas e faces de uma qualquer dimens~ao do politopo de Birkho ac clico, Tn = n(T), onde T e uma arvore com n v ertices. Generaliza-se o resultado obtido por G. Dahl, [18], para o c alculo do di^ametro do grafo G( t n), onde t n e o politopo das matrizes tridiagonais duplamente estoc asticas. Adicionalmente, para q = 0; 1; 2; 3 s~ao obtidas f ormulas expl citas para a contagem do n umero de q faces do politopo de Birkho tridiagonal, t n, e e feito o estudo da natureza geom etrica dessas mesmas faces. S~ao, tamb em, apresentados algoritmos para efectuar contagens do n umero de faces de dimens~ao inferior a de uma dada face do politopo de Birkho ac clico.

Interacting agents on complex networks and stochastic processes in them

Nas últimas décadas, um grande número de processos têm sido descritos em termos de redes complexas. A teoria de redes complexas vem sendo utilizada com sucesso para descrever, modelar e caracterizar sistemas naturais, artificias e sociais, tais como ecossistemas, interações entre proteínas, a Internet, WWW, até mesmo as relações interpessoais na sociedade. Nesta tese de doutoramento apresentamos alguns modelos de agentes interagentes em redes complexas. Inicialmente, apresentamos uma breve introdução histórica (Capítulo 1), seguida de algumas noções básicas sobre redes complexas (Capítulo 2) e de alguns trabalhos e modelos mais relevantes a esta tese de doutoramento (Capítulo 3). Apresentamos, no Capítulo 4, o estudo de um modelo de dinâmica de opiniões, onde busca-se o consenso entre os agentes em uma população, seguido do estudo da evolução de agentes interagentes em um processo de ramificação espacialmente definido (Capítulo 5). No Capítulo 6 apresentamos um modelo de otimização de fluxos em rede e um estudo do surgimento de redes livres de escala a partir de um processo de otimização . Finalmente, no Capítulo 7, apresentamos nossas conclusões e perspectivas futuras.

Majorantes para a ordem de subgrafos induzidos k-regulares

Muitos dos problemas de otimização em grafos reduzem-se à determinação de um subconjunto de vértices de cardinalidade máxima que induza um subgrafo k-regular. Uma vez que a determinação da ordem de um subgrafo induzido k-regular de maior ordem é, em geral, um problema NP-difícil, são deduzidos novos majorantes, a determinar em tempo polinomial, que em muitos casos constituam boas aproximações das respetivas soluções ótimas. Introduzem-se majorantes espetrais usando uma abordagem baseada em técnicas de programação convexa e estabelecem-se condições necessárias e suficientes para que sejam atingidos. Adicionalmente, introduzem-se majorantes baseados no espetro das matrizes de adjacência, laplaciana e laplaciana sem sinal. É ainda apresentado um algoritmo não polinomial para a determinação de umsubconjunto de vértices de umgrafo que induz umsubgrafo k-regular de ordem máxima para uma classe particular de grafos. Finalmente, faz-se um estudo computacional comparativo com vários majorantes e apresentam-se algumas conclusões.

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.

Análise de risco em organizações: caso de estudo

Dissertação Final de Mestrado para obtenção do grau de Mestre em Engenharia Mecânica no perfil de Manutenção e Produção

Representação na forma normal disjuntiva para a flexibilidade de seqüência na manufatura

A crescente demanda por produtos de melhor qualidade, diferenciados e com custos competitivos tem forçado as manufaturas a se tornarem flexíveis, capacitando-as a responder às mudanças impostas pelo mercado. A flexibilidade permite que as empresas alcancem a customização desejada através da capacitação do sistema de responder e atuar em tempo real, mesmo em um ambiente de incertezas. Para atuar em tempo real, os sistemas de manufatura precisam de representações eficientes dos planos de produção. Muitas vezes, a atuação em tempo real torna-se inviável devido ao crescimento exponencial no número de planos de produção para cada máquina ou operação adicionada ao sistema. Uma possível solução para este problema é uso de representações adequadas para o espaço de estados. A escolha de uma representação adequada para o espaço de estados influencia na capacidade de reposta em tempo real, pois determina o desempenho computacional do sistema através da utilidade e eficiência dos algoritmos desenvolvidos, tornando possível explorar problemas clássicos de flexibilidade, tais como, seqüenciamento, otimização, etc. Entretanto, a geração de uma representação que trabalhe com o espaço de estados completo de uma manufatura é considerada um problema não polinomial (NP). Esta particularidade dificulta o desenvolvimento de algoritmos que trabalhem com uma manufatura flexível. Assim, a geração de uma representação, que trabalhe com pouca memória computacional e permita o desenvolvimento de heurísticas eficientes, é um importante desafio para uma avaliação efetiva da flexibilidade. Este trabalho objetiva o desenvolvimento de uma representação para o espaço de estados de uma manufatura com flexibilidade de seqüência. Na construção desta representação são aplicadas técnicas de modelagem baseadas na teoria dos grafos e nos princípios de álgebra booleana. Inicialmente, os grafos são utilizados para representar todas as seqüências de operações de uma manufatura, posteriormente estas seqüências são convertidas em formas normais disjuntivas (FND). Por fim, é apresentada uma possível aplicação da representação na FND em modelos de programação linear.

Solução de sistemas de equações algébrico-diferenciais ordinárias de índice superior

A modelagem matemática de problemas importantes e significativos da engenharia, física e ciências sociais pode ser formulada por um conjunto misto de equações diferenciais e algébricas (EADs). Este conjunto misto de equações deve ser previamente caracterizado quanto a resolubilidade, índice diferencial e condições iniciais, para que seja possível utilizar um código computacional para resolvê-lo numericamente. Sabendo-se que o índice diferencial é o parâmetro mais importante para caracterizar um sistema de EADs, neste trabalho aplica-se a redução de índice através da teoria de grafos, proposta por Pantelides (1988). Este processo de redução de índice é realizado numericamente através do algoritmo DAGRAFO, que transforma um sistema de índice superior para um sistema reduzido de índice 0 ou 1. Após esta etapa é necessário fornecer um conjunto de condições inicias consistentes para iniciar o código numérico de integração, DASSLC. No presente trabalho discute-se três técnicas para a inicialização consistente e integração numérica de sistemas de EADs de índice superior. A primeira técnica trabalha exclusivamente com o sistema reduzido, a segunda com o sistema reduzido e as restrições adicionais que surgem após a redução do índice introduzindo variáveis de restrição, e a terceira técnica trabalha com o sistema reduzido e as derivadas das variáveis de restrição. Após vários testes, conclui-se que a primeira e terceira técnica podem gerar um conjunto solução mesmo quando recebem condições iniciais inconsistentes. Para a primeira técnica, esta característica decorre do fato que no sistema reduzido algumas restrições, muitas vezes com significado físico importante, podem ser perdidas quando as equações algébricas são diferenciadas. Trabalhando com o sistema reduzido e as derivadas das variáveis de restrição, o erro da inicialização é absorvido pelas variáveis de restrição, mascarando a precisão do código numérico. A segunda técnica adotada não tem como absorver os erros da inicialização pelas variáveis de restrição, desta forma, quando as restrições adicionais não são satisfeitas, não é gerada solução alguma. Entretanto, ao aplicar condições iniciais consistentes para todas as técnicas, conclui-se que o sistema reduzido com as derivadas das variáveis restrição é o método mais conveniente, pois apresenta melhor desempenho computacional, inclusive quando a matriz jacobiana do sistema apresenta problema de mau condicionamento, e garante que todas as restrições que compõem o sistema original estejam presentes no sistema reduzido.

Data mining por meio de análise de redes, no contexto de filtro colaborativo

Tendo como motivação o desenvolvimento de uma representação gráfica de redes com grande número de vértices, útil para aplicações de filtro colaborativo, este trabalho propõe a utilização de superfícies de coesão sobre uma base temática multidimensionalmente escalonada. Para isso, utiliza uma combinação de escalonamento multidimensional clássico e análise de procrustes, em algoritmo iterativo que encaminha soluções parciais, depois combinadas numa solução global. Aplicado a um exemplo de transações de empréstimo de livros pela Biblioteca Karl A. Boedecker, o algoritmo proposto produz saídas interpretáveis e coerentes tematicamente, e apresenta um stress menor que a solução por escalonamento clássico.

Desenvolvendo o conceito de redes bayesianas na construção de cenários prospectivos

A incerteza é o principal elemento do futuro. Desde os primórdios, o homem busca métodos para estruturar essas incertezas futuras e assim poder guiar suas ações. Apenas a partir da segunda metade do século XX, porém, quando os métodos projetivos e preditivos já não eram mais capazes de explicar o futuro em um ambiente mundial cada vez mais interligado e turbulento, é que nasceram os primeiros métodos estruturados de construção de cenários. Esses métodos prospectivos visam lançar a luz sobre o futuro não para projetar um futuro único e certo, mas para visualizar uma gama de futuros possíveis e coerentes. Esse trabalho tem como objetivo propor uma nova abordagem à construção de cenários, integrando o Método de Impactos Cruzados à Análise Morfológica, utilizando o conceito de Rede Bayesianas, de fonna a reduzir a complexidade da análise sem perda de robustez. Este trabalho fará uma breve introdução histórica dos estudos do futuro, abordará os conceitos e definições de cenários e apresentará os métodos mais utilizados. Como a abordagem proposta pretende-se racionalista, será dado foco no Método de Cenários de Michel Godet e suas ferramentas mais utilizadas. Em seguida, serão apresentados os conceitos de Teoria dos Grafos, Causalidade e Redes Bayesianas. A proposta é apresentada em três etapas: 1) construção da estrutura do modelo através da Análise Estrutural, propondo a redução de um modelo inicialmente cíclico para um modelo acíclico direto; 2) utilização da Matriz de Impactos Cruzados como ferramenta de alimentação, preparação e organização dos dados de probabilidades; 3) utilização da Rede Bayesiana resultante da primeira etapa como subespaço de análise de uma Matriz Morfológica. Por último, um teste empírico é realizado para comprovar a proposta de redução do modelo cíclico em um modelo acíclico.

Mapas cognitivos SODA ampliados: prescrição de um método para articular atitudes, comportamentos e seqüências cognitivas a mapas SODA

Este trabalho de tese tem por objetivo ampliar o alcance e aplicação de mapas SODA, preservando a metodologia originalmente desenvolvida. Inicialmente é realizada uma revisão do método, abordando de forma conjunta os artigos seminais, a teoria psicológica de Kelly e a teoria dos grafos; e ao final propomos uma identidade entre construtos de mapas SODA com os conhecimentos tácitos e explícitos, da gestão do conhecimento (KM). Essa sequencia introdutória é completada com uma visão de como os mapas SODA tem sido aplicado. No estágio seguinte o trabalho passa a analisar de forma crítica alguns pontos do método que dão margens a interpretações equivocadas. Sobre elas passamos a propor a aplicação de teorias, de diversos campos, tais como a teoria de means-end (Marketing), a teoria da atribuição e os conceitos de atitude (Psicologia), permitindo inferências que conduzem à proposição da primeira tese: mapas SODA são descritores de atitudes. O próximo estágio prossegue analisando criticamente o método, e foca no paradigma estabelecido por Eden, que não permite conferir ao método o status de descritor de comportamento. Propomos aqui uma mudança de paradigma, adotando a teoria da ação comunicativa, de Habermas, e sobre ela prescrevemos a teoria da ação e da escada da inferência (Action Science) e uma teoria da emoção (neuro ciência), o que permite novas inferências, que conduzem à proposição da segunda tese: mapas SODA podem descrever comportamentos. Essas teses servem de base para o alargamento de escopos do método SODA. É proposta aqui a utilização da teoria de máquinas de estado finito determinístico, designadas por autômato. Demonstramos um mapeamento entre autômato com mapas SODA, obtendo assim o autômato SODA, e sobre ele realizamos a última contribuição, uma proposta de mapas SODA hierárquicos, o que vem a possibilitar a descrição de sequencias de raciocínio, ordenando de forma determinística atitudes e comportamentos, de forma estruturada. A visão de como ela pode ser aplicada é realizada por meio de estudo de caso.

Bank networks and firm credit: an agent based model approach

Starting from the idea that economic systems fall into complexity theory, where its many agents interact with each other without a central control and that these interactions are able to change the future behavior of the agents and the entire system, similar to a chaotic system we increase the model of Russo et al. (2014) to carry out three experiments focusing on the interaction between Banks and Firms in an artificial economy. The first experiment is relative to Relationship Banking where, according to the literature, the interaction over time between Banks and Firms are able to produce mutual benefits, mainly due to reduction of the information asymmetry between them. The following experiment is related to information heterogeneity in the credit market, where the larger the bank, the higher their visibility in the credit market, increasing the number of consult for new loans. Finally, the third experiment is about the effects on the credit market of the heterogeneity of prices that Firms faces in the goods market.