Tese de mestrado. Métodos Computacionais em Ciências e Engenharia. Faculdade de Engenharia. Universidade do Porto. 2008

Um emparelhamento em um grafo é um conjunto de arestas duas a duas não adjacentes. Dado um grafo G com pesos em suas arestas, o problema do emparelhamento de peso é máximo é encontrar um emparelhamento cuja soma dos pesos de suas arestas é máxima. Neste trabalho estudamos diferentes soluções para esse problema. Estudamos algoritmos combinatórios que resolvem o problema no caso em que G é bipartido e no caso geral. O algoritmo de Edmonds é um algoritmo polinomial cuja complexidade de tempo é O(n^4), onde n é o número de vértices do grafo G. Discutimos nesse trabalho nossa implementação desse algoritmo. Num trabalho de 1985, Grötschel e Holland propuseram o uso de ferramentas de programação linear para resolver o mesmo problema. O método chamado de planos-de-corte baseia-se em um resultado de Padberg e Rao de que o problema da separação associado ao poliedro dos emparelhamentos pode ser resolvido em tempo polinomial. Neste trabalho fizemos implementações dos dois métodos e os utilizamos para resolver diversos tipos de instâncias do problema. Nossa conclusão é que o método poliédrico, apesar de utilizar ferramentas genéricas, é bastante eficiente na prática. / A matching in a graph G is a set of pairwise disjoint edges of G. Given a graph G with edge weights, we define the maximum weight matching problem as that of finding a matching which maximizes the sum of its weights. In this thesis we study different solutions to this problem. We studied combinatorial algorithms that solve this problem in the case where G is bipartite and also in the general case. Edmonds algorithm [Edm65a] is a polynomial time algorithm with complexity O(n4 ), where n is the number of vertices in the graph G. We discuss in this document our implementation of this algorithm. In a paper from 1985, Gr tschel & Holland [GH85] discussed the use of linear programming o tools for solving the maximum weight matching problem. This so called cut-plane method relies on a result by Padberg & Rao [PR82] that proves that the separation problem associated with matching polyhedron is solvable in polinomial time. In this work we implemented both methods and used then to solve different instances of the problem. Our conclusion is that the polyhedral method, although using generical tools is very efficient in practice.

PESSOA, A. M. Emparelhamento de subportadoras e alocação de potência de transmissão para redes cooperativas. 2016. 104 f. Dissertação (Mestrado em Engenharia Elétrica e da Computação), Campus de Sobral, Universidade Federal do Ceará, Sobral, 2016. / Submitted by Programa de Pós-Graduação Engenharia Elétrica e de Computação (secretaria_ppgeec@sobral.ufc.br) on 2017-02-03T13:18:56Z No. of bitstreams: 1 2017_dis_ampessoa.pdf: 1254061 bytes, checksum: 2374c25823a476483959e77f155b1e24 (MD5) / Rejected by Ana Márcia Sousa (marciasousa@ufc.br), reason: Prezada, Conforme conversa por telefone corrigir campos e preencher o que faltou. Quanto a dissertação do aluno ele deverá refazer toda a normalização do trabalho de acordo a Normalização de Trabalhos Acadêmicos e templates que se encontram na pagina da biblioteca: biblioteca.ufc.br em Normalização de Trabalhos Acadêmicos. on 2017-02-03T13:35:38Z (GMT) / Submitted by Programa de Pós-Graduação Engenharia Elétrica e de Computação (secretaria_ppgeec@sobral.ufc.br) on 2017-02-03T14:20:26Z No. of bitstreams: 1 2017_dis_ampessoa.pdf: 1254061 bytes, checksum: 2374c25823a476483959e77f155b1e24 (MD5) / Rejected by Ana Márcia Sousa (marciasousa@ufc.br), reason: Prezada, Favor verificar os campus: Autor, orientador, citação, descrição e título em inglês e fazer como está no guia de preenchimento que está na documentação enviada a você por ocasião do treinamento. Quanto a dissertação do aluno ainda falta corrigir toda a Normalização do trabalho de acordo com as normas da UFC e templates na página da Biblioteca: biblioteca.ufc.br. Você precisa avisar isto ao aluno e esperar que ele lhe envie corrigido e fazer a troca no ri e submeter novamente. on 2017-02-03T15:08:06Z (GMT) / Submitted by Programa de Pós-Graduação Engenharia Elétrica e de Computação (secretaria_ppgeec@sobral.ufc.br) on 2017-02-13T14:46:26Z No. of bitstreams: 1 2017_dis_ampessoa.pdf: 1145087 bytes, checksum: 5f78bf6574910be8bb12b18e9fe5f1b1 (MD5) / Approved for entry into archive by Ana Márcia Sousa (marciasousa@ufc.br) on 2017-02-15T10:47:00Z (GMT) No. of bitstreams: 1 2017_dis_ampessoa.pdf: 1145087 bytes, checksum: 5f78bf6574910be8bb12b18e9fe5f1b1 (MD5) / Made available in DSpace on 2017-02-15T10:47:00Z (GMT). No. of bitstreams: 1 2017_dis_ampessoa.pdf: 1145087 bytes, checksum: 5f78bf6574910be8bb12b18e9fe5f1b1 (MD5) Previous issue date: 2017-01 / present in the fourth generation of mobile communications due to its potential to combat fading and extend the cell coverage area. In addition, efficient radio resource management when applied to relay networks is capable of improving the performance of mobile communication systems in terms of space diversity, coverage, spectral and energy efficiencies. One of the main assumption in our work is a discrete mapping between channel quality and transmit data rate. This discrete mapping models the use of finite MCSs and has been neglected by most of the articles in the literature. In this master thesis we formulate two problems. The first problem consists in the maximization of the total data rate in a cooperative system through subcarrier pairing and transmit power allocation. The second problem aims at maximizing the number of satisfied users with the demanded QoS. For both problems we provide the optimal solution, some basic properties and suboptimal solutions with low computational complexity. By means of computational simulations, we show that the proposed solution to the total data rate maximization problem has a maximum error to the optimal solution lower than 0.1%. Furthermore, the heuristic solution proposed to the problem of maximizing the number of satisfied users is capable of attaining a performance loss in the number of satisfied users not higher than 10% to the optimal solution with much lower transmit power leading to energy efficiency gains. / Rede de repetidores e comunicação cooperativa se consolidaram como duas importantes tecnologias presentes na quarta geração das comunicações móveis devido ao seu potencial em combater o desvanecimento em pequena e larga escalas e ampliar a zona de cobertura das células. Além disso, o gerenciamento dos recursos de rádio de forma eficiente aplicado em redes de repetidores tem se mostrado como uma importante ferramenta para melhorar o desempenho dos sistemas de comunicações móveis em termos de diversidade espacial, cobertura, eficiência espectral e energética. Um dos pilares de nosso estudo foi a consideração de um mapeamento discreto entre a qualidade de canal de comunicação geralmente representada pela SNR (do inglês, Signal-to-Noise Ratio) e a taxa de dados. Essa consideração está em consonância com o uso de MCSs (do inglês, Modulation and Coding Schemes) e tem sido ignorada em grande parte dos trabalhos da área. Nesta dissertação, formulamos dois problemas. O primeiro problema consiste na maximização da taxa total em um cenário cooperativo através do emparelhamento de subportadoras e alocação adaptativa de potência de transmissão. O segundo problema consiste na maximização do número de usuário satisfeitos com o QoS (do inglês, Quality of Service) solicitado. Para ambos os problemas, provemos a solução ótima, propriedades básicas e soluções subótimas de baixo custo computacional. Através de simulações computacionais mostramos que a solução subótima para o problema de maximização de taxa apresentou erro máximo de 0.1% em relação a solução ótima. Além disso, a solução subótima para o problema de maximização do número de usuário satisfeitos foi capaz de atender a perdas de desempenho menores que 10% com relação ao ótimo, utilizando muito menos potência em ambos os saltos.

Um emparelhamento em um grafo é um conjunto de arestas duas a duas não adjacentes. Dado um grafo G com pesos em suas arestas, o problema do emparelhamento de peso é máximo é encontrar um emparelhamento cuja soma dos pesos de suas arestas é máxima. Neste trabalho estudamos diferentes soluções para esse problema. Estudamos algoritmos combinatórios que resolvem o problema no caso em que G é bipartido e no caso geral. O algoritmo de Edmonds é um algoritmo polinomial cuja complexidade de tempo é O(n^4), onde n é o número de vértices do grafo G. Discutimos nesse trabalho nossa implementação desse algoritmo. Num trabalho de 1985, Grötschel e Holland propuseram o uso de ferramentas de programação linear para resolver o mesmo problema. O método chamado de planos-de-corte baseia-se em um resultado de Padberg e Rao de que o problema da separação associado ao poliedro dos emparelhamentos pode ser resolvido em tempo polinomial. Neste trabalho fizemos implementações dos dois métodos e os utilizamos para resolver diversos tipos de instâncias do problema. Nossa conclusão é que o método poliédrico, apesar de utilizar ferramentas genéricas, é bastante eficiente na prática. / A matching in a graph G is a set of pairwise disjoint edges of G. Given a graph G with edge weights, we define the maximum weight matching problem as that of finding a matching which maximizes the sum of its weights. In this thesis we study different solutions to this problem. We studied combinatorial algorithms that solve this problem in the case where G is bipartite and also in the general case. Edmonds algorithm [Edm65a] is a polynomial time algorithm with complexity O(n4 ), where n is the number of vertices in the graph G. We discuss in this document our implementation of this algorithm. In a paper from 1985, Gr tschel & Holland [GH85] discussed the use of linear programming o tools for solving the maximum weight matching problem. This so called cut-plane method relies on a result by Padberg & Rao [PR82] that proves that the separation problem associated with matching polyhedron is solvable in polinomial time. In this work we implemented both methods and used then to solve different instances of the problem. Our conclusion is that the polyhedral method, although using generical tools is very efficient in practice.

Made available in DSpace on 2016-06-02T20:30:49Z (GMT). No. of bitstreams: 1 2813.pdf: 4703512 bytes, checksum: 0d0d1d4f45e0c362db43d35a057df866 (MD5) Previous issue date: 2009-12-21 / Universidade Federal de Minas Gerais / Behavioral analysts have used the equivalence class paradigm to investigate and explain the processes involved in the formation and modification of social attitudes. From this perspective, attitudes are defined as equivalence classes established between social groups and certain attributes, with the classes specifying the psychological function of the social group for members of the verbal community. Following this line of research, the present study investigated attitude change by means of the reversal of the equivalence class relating black men to negative symbols. In two versions of the procedure, two pre-tests were conducted involving C-A and A-C relations in order to assess the association made by the participants between pictures of black men and the aforementioned negative symbols. Next, the participants were exposed to a conditional discrimination task with delay, a task in which they were taught the relations A-B (between a positive stimulus and an abstract picture) and B-C (between the abstract picture and pictures of black men). Post-tests assessed whether training had induced the emergence of a new relation between the figures of black men and positive symbols, which emergence would suggest a change of attitude and a reversal of the initial equivalence class exposed during the pre-test. Results showed that, for three of the five participants, the equivalence class relating pictures of black men to positive symbols did not emerge, which suggests resistance to revert the class relating black men to negative symbols. It seems that responses typical of natural settings generalized to the experimental situation, making responding in the latter case insensitive to the arranged reinforcement contingencies. The results are discussed in terms of the extension of the stimulus equivalence paradigm to cases in which the equivalence class comprises stimuli loaded with pre-experimental meaning. / Estudiosos da Análise do Comportamento têm se concentrado no uso do paradigma de equivalência de estímulos para investigar e explicar os processos envolvidos na formação e mudança de atitudes sociais. Desta perspectiva, atitudes são definidas como classes de equivalência estabelecidas entre grupos sociais e determinados atributos, classes essas que especificariam a função psicológica do grupo social em questão para os membros da comunidade verbal. O presente trabalho dá continuidade a esta linha de pesquisa, objetivando investigar a mudança de atitude a partir da reversão de classe de equivalência entre homens negros e símbolos negativos. Em duas versões do mesmo procedimento, foram conduzidos dois testes iniciais (das relações C-A e A-C) nos quais se buscou avaliar a associação que os participantes faziam entre imagens de negros e os referidos símbolos. Em seguida, foi feito treino em tentativas de discriminação condicional com atraso no qual foram ensinadas diretamente as relações A-B (entre símbolo positivo e figura abstrata) e B-C (entre figura abstrata e homens negros). Em pós-testes, foi verificado o efeito do treino para a emergência de relação entre negros e símbolos positivos relação esta sugestiva de mudança de atitude e de reversão da classe inicial verificada no pré-teste. Os resultados indicaram que não houve formação da classe esperada entre negros e símbolos positivos para três de cinco participantes, sugerindo resistência à reversão da classe entre negros e símbolos negativos. Ao que parece, estes dados permitem afirmar que o responder em situação natural foi generalizado para a situação experimental, não estando sob controle das contingências de reforçamento ali arranjadas. Os dados produzidos subsidiaram discussão acerca da aplicação do paradigma de equivalência de estímulos quando são tratadas classes de equivalência constituídas por estímulos já dotados de significado pré-experimental.

Made available in DSpace on 2016-06-02T20:30:50Z (GMT). No. of bitstreams: 1 3189.pdf: 1746240 bytes, checksum: dc2fe90f99f924dedd0fb25b667670dc (MD5) Previous issue date: 2010-05-28 / Universidade Federal de Minas Gerais / Studies on learning by exclusion and stimuli equivalence are usually conducted by means of conditional discriminations teaching procedures. Some recent studies have investigated important variables in procedures for teaching conditional discriminations to babies, both for the maintenance of the subjects in the task and for the establishment of conditional responding in babies. Considering the recent advances in the literature and seeking to develop procedures for investigating relational repertoires in infants, two studies were performed. The first study was divided into two parts whose objectives was: 1A) replicating and adapting to the child care center context a study about conditional discrimination teaching by exclusion for a baby of 17 months, in which photographs were used as stimuli and; 1B ) to evaluate the generality of the procedure employed in the previous study. The second study aimed to investigate the effect of using abstract stimuli and toys stimuli on an identity matching teaching procedure. In Study 1A, the three participants were trained a baseline auditory-visual conditional discriminations with familiar photographs. After that subjects were presented to exclusion and learning evaluation trials. The three participants (between 17 and 19 months) learned the baseline conditional discriminations and chose correctly in all exclusion trials, although they have not demonstrated learning by exclusion. In Study 1B the same procedure was used and only two of three children, aged between 15 and 18 months, learned the baseline relations, although all of them chose the correct stimulus in the exclusion trials. There was evidence of learning by exclusion for some children, however, the performance of infants in the novelty control trials suggested that children could be choosing based on such bias. The results suggest that the presented procedure is a useful tool for the study of exclusion responding in babies and thus enables further investigations on the process. In Study 2, two babies of 17 and 20 months were submitted to an identity matching training with abstract shapes or toys used as discriminative stimuli. The stimuli presentation was made by a mechanical apparatus that allowed the exposure of stimuli in closed and open windows. The programmed consequences varied according to the stimuli training condition. Babies have not learned the identity conditional discriminations in any stimuli conditions, although there was a greater number of corrects choices when the stimuli used were abstract shapes. Nevertheless, it was not possible to obtain conclusive evidence about the effectiveness of the use of those different stimuli conditions on the infant s conditional discrimination learning. / Estudos sobre aprendizagem por exclusão e equivalência de estímulos são geralmente realizados por meio de procedimentos de ensino de discriminações condicionais. Alguns trabalhos recentes têm investigado variáveis de procedimentos de ensino de discriminações condicionais para bebês, importantes tanto para a manutenção dos pequenos na tarefa quanto para o estabelecimento do responder condicional nos bebês. Considerando os avanços recentes na literatura e visando o desenvolvimento de procedimentos para a investigação de repertórios relacionais em bebês, foram realizados dois estudos. O primeiro foi dividido em duas partes que tiveram como objetivo: 1A) replicar e adaptar para o contexto da creche um estudo sobre ensino de discriminações condicionais por exclusão para um bebê de 17 meses, no qual foram utilizadas fotografias como estímulos e; 1B) avaliar a generalidade do procedimento empregado no estudo anterior. O segundo estudo objetivou investigar o efeito da utilização de estímulos abstratos e estímulos brinquedos sobre o ensino de emparelhamento de identidade para bebês. No estudo 1A, os três bebês foram submetidos a um treino de discriminações condicionais auditivo-visuais de linha de base com estímulos fotografias familiares. Após o treino, foram realizadas tentativas de exclusão e de verificação aprendizagem. Os três participantes, entre 17 e 19 meses, aprenderam as discriminações condicionais de linha de base e escolheram corretamente nas tentativas de exclusão, embora não tenham demonstrado aprendizagem por exclusão. No Estudo 1B, com o mesmo procedimento, apenas duas de três crianças, com idades entre 15 e 18 meses, aprenderam as relações de linha de base, embora todos tenham escolhido corretamente o estímulo novo nas tentativas de exclusão. Houve evidência de aprendizagem para algumas crianças, no entanto, o desempenho dos bebês nas sondas de controle da novidade sugeriu que a escolha correta poderia estar baseada neste viés. Os resultados apresentados sugerem que o procedimento utilizado é uma ferramenta útil para o estudo do responder por exclusão e, dessa forma, possibilita investigações futuras sobre processo. No Estudo 2, dois bebês, de 17 e 20 meses, foram submetidos a um treino de emparelhamento de identidade no qual formas abstratas ou brinquedos era utilizados como estímulos discriminativos. Os estímulos eram apresentados em um aparato mecânico que permitia a exposição dos estímulos em janelas fechadas e abertas. As consequências programadas variaram de acordo com a condição de estímulo utilizada. Os bebês não aprenderam as relações condicionais em qualquer das condições de estímulos, embora tenha ocorrido um maior número de acertos quando os estímulos eram arbitrários. No entanto, não foram observadas evidências conclusivas sobre a efetividade das diferentes condições de estímulos utilizadas sobre a aprendizagem de discriminações condicionais.

Na área de emparelhamento de ontologias, são utilizadas algumas métricas para avaliar os alinhamentos produzidos. As métricas baseadas em alinhamento têm como princípio básico confrontar um alinhamento proposto com um alinhamento de referência. Algumas destas métricas, entretanto, não têm alcançado êxito suficiente porque (i) não conseguem discriminar sempre entre um alinhamento totalmente errado e um quase correto; e (ii) não conseguem estimar o esforço do usuário para refinar o alinhamento resultante. Este trabalho tem como objetivo apresentar uma nova abordagem para avaliar os alinhamentos de ontologias. A nossa abordagem apresenta uma métrica na qual utilizamos as próprias consultas normalmente já realizadas nas ontologias originais para julgar a qualidade do alinhamento proposto. Apresentamos também alguns resultados satisfatórios de nossa abordagem em relação às outras métricas já existentes e largamente utilizadas. / In the ontology matching field, different metrics are used to evaluate the resulting alignments. Metrics based on alignment adopt the basic principle of verifying a proposed alignment against a reference alignment. Some of these metrics do not achieve good results because (i) they cannot always distinguish between a totally wrong alignment and one which is almost correct; and (ii) they cannot estimate the effort for the user to refine the resulting alignment. This work aims to present a new approach to evaluate ontology alignments. Our approach presents a measure that uses the usual queries in the original ontologies to assess the quality of the proposed alignment. We also present some satisfactory results of our approach with regard to widely used metrics.

Muitos problemas de otimização em grafos, em especial problemas métricos, são mais fáceis de resolver em árvores. Portanto, uma estratégia para obter um bom algoritmo para certos problemas é obter uma árvore que aproxime o grafo, e utilizar uma solução do problema nessa árvore como uma solução aproximada para o problema no grafo original. Neste trabalho é estudada a técnica de Fakcharoenphol, Rao e Talwar, que mostraram como aproximar uma métrica finita arbitrária com n pontos por uma métrica numa árvore com distorção esperada O(lg n) -- o ótimo assintótico. Essa estratégia resulta em algoritmos de aproximação com boas razões de aproximação, e em algoritmos com bom fator de competitividade para diversos problemas de otimização online e distribuídos. É apresentada especificamente a aplicação da técnica ao problema do emparelhamento mínimo bipartido online, que ilustra como a aproximação de métricas auxilia na resolução de um problema e os cuidados que devem ser tomados nessa aplicação. / Many optimization problems on graphs, especially metric problems, are easier to solve on trees. Therefore, a strategy for obtaining a good algorithm for certain problems is to obtain a tree that approximates the graph, and use a solution of the problem on the tree as an approximate solution for the problem on the original graph. We study the work of Fakcharoenphol, Rao e Talwar, who showed how to approximate an arbitrary finite metric on n points by a tree metric with expected distortion O(lg n), which is asymptotically optimum. This strategy leads to algorithms with good approximation factors, and to competitive algorithms for various optimization problems, some of them online and distributed. Here, we present the application of that technique to the problem of finding a minimum online matching on a bipartite metric graph. This problem illustrates how metric approximation aids in solving a problem, and the care that must be taken when doing such an application.

Neste trabalho apresentamos dois conjuntos de transformações do campo médio de emparelhamento e o cálculo deste no canal n--p isovetorial. Correlações de curto alcance são descritas numa teoria de campo médio nuclear relativístico na aproximação de Dirac-Hartree-Fock-Bogoliubov (DHFB). Esta aproximação foi desenvolvida inicialmente para descrever o dito emparelhamento padrão em matéria nuclear simétrica. A generalização da aproximação DHFB inclui o emparelhamento no canal quasideuteron em matéria assimétrica. Construímos transformações do campo de emparelhamento usando como geradores destas as matrizes $gamma$ e $ au$ e suas possíveis combinações. Existem dois conjuntos distintos que transformam de forma diferente o campo de emparelhamento. Como resultado destas transformações, obteve-se que ambos os campos de emparelhamento n--n e p--p podem ser tomados como funções reais de momento $vec{k}$. Já o cálculo do emparelhamento isovetorial n--p, baseia-se na decomposição deste campo em função dos propagadores de Gorkov. Como resultado principal, obteve-se que a inclusão de um novo vínculo $mu_{1}$ ao modelo permite soluções n--n, p--p e n--p para matéria nuclear simétrica. Fora da simetria, encontramos somente soluções n--n e p--p. Porém, nenhuma solução n--p isovetorial foi encontrada.

Estudamos um programador generalizado de campo de spin-0 que considera não só a propagação do campo mas também de sua coordenada conjugada e a misturados dois. A motivação para este estudo é a possibilidade de encontrarmos um "gap" de massa, como um novo termo no propagador, que seria o análogo bosônico de emparelhamento.