Orientador: Eduardo Candido Xavier / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação / Made available in DSpace on 2018-08-18T10:12:53Z (GMT). No. of bitstreams: 1 Peixoto_RobsonRobertoSouza_M.pdf: 1268588 bytes, checksum: ff8a093aa133696dcd5bbe31bc4d6e78 (MD5) Previous issue date: 2011 / Resumo: Nesta dissertação estudamos algoritmos para resolver problemas de escalonamento de tarefas em grades computacionais. Dado um conjunto de tarefas submetidas a uma grade computacional, deve-se definir em quais recursos essas tarefas serão executadas. Algoritmos de escalonamento são empregados com o objetivo de minimizar o tempo necessário para executar todas as tarefas (makespan) que foram submetidas. Nosso foco é estudar os atuais algoritmos de escalonamento usados em grades computacionais e comparar estes algoritmos. Nesta dissertação apresentamos algoritmos onlines, aproximados e heurísticas para o problema. Como resultados novos, provamos fatores de aproximação para o algoritmo RR quando utilizado para resolver os problemas R; sit|Tj|Cmax, R; sit|Tj|TPCC, R; sit|Tj = L| Cmax e R; sit|Tj = L|TPCC é justo. Por fim, definimos uma interface que adiciona replicação de tarefas a qualquer algoritmo de escalonamento, onde nós mostramos a aproximação desta interface, e apresentamos uma comparação via simulação dos algoritmos sem e com replicação. Nossas simulações mostram que, com a utilização de replicação, houve a redução no makespan de até 80% para o algoritmo Min-min. Nas nossas análises também fazemos uso da métrica RTPCC que calcula exatamente a quantidade de instruções que foram usadas para executar todas as tarefas / Abstract: In this dissertation, we studied algorithms to solve task scheduling problems in computational grids. Given a task set that was submitted to a computational grid, the problem is to define in which resources these tasks will be executed and the order they will be executed. Scheduling algorithms are used in order to minimize the time required to execute all tasks (makespan). We studied the most recent scheduling algorithms proposed to be used in computational grids, and then compare them using simulations. In this dissertation we also present approximate algorithms and new heuristics for the problem. As new results, we proved approximation factors to the RR algorithm when applied to solve the problems R; sit|Tj|Cmax, R; sit|Tj|TPCC, R; sit|Tj = L| Cmax and R; sit|Tj = L|TPCC. Finally, we defined an interface that adds task replication capability to any scheduling algorithm. We then show approximation results for algorithms using this interface, and present a comparison of well know algorithms with and without replication. This comparison is done via simulation. Our simulations show that, with replication, there was up to 80% of reduction in the makespan to some algorithms like the Min-min / Mestrado / Teoria da Computação / Mestre em Ciência da Computação

Orientador: Edson Moschim / Tese (doutorado) - Universidade Estadual de Campinas, Faculdade de Engenharia Eletrica e de Computação / Made available in DSpace on 2018-08-04T21:57:49Z (GMT). No. of bitstreams: 1 DomingosNeto_Adriano_D.pdf: 1544823 bytes, checksum: f09f4717b59d1cce526b7c8746e53efb (MD5) Previous issue date: 2005 / Resumo: Nesta tese, propõe se três novas construções de códigos ortogonais ópticos (OOC), do tipo congruentes, tendo como base a estrutura algébrica do grupo multiplicativo do corpo de Galois GF(p), para aplicação em sistemas de comunicação utilizando a técnica de acesso múltiplo por divisão de códigos ópticos (OCDMA). Os códigos ópticos primos e códigos quadráticos são, pela primeira vez na literatura, gerados a partir de códigos de Slepian (códigos esféricos) e, códigos de resíduos quadráticos, respectivamente. Através do algoritmo da d-cadeia fechada, são obtidos os códigos de primos, como caso particular dos códigos de Slepian. Os códigos quadráticos ópticos são representados por números inteiros quadráticos binários na forma de equações de Diofanto com duas variáveis, de modo que, o reticulado Z2 ou reticulado Â2 fornecem as palavra do código quadrático. O desempenho dos códigos é avaliado usando o critério da probabilidade de erro para situações em que o receptor óptico incorpora um limitador óptico e um fotodiodo APD. O desempenho do sistema é obtido considerando os efeitos da interferência de acesso múltiplo, o ruído balístico do fotodiodo e o ruído térmico do receptor. O desempenho dos códigos propostos é comparado ao desempenho de códigos amplamente divulgados em literatura técnica. Mostra-se ainda que os códigos propostos apresentam desempenho semelhante aos códigos divulgados, tendo como vantagem uma estrutura algébrica de simples implementação e melhor sincronismo / Abstract: This thesis presents a study of optical orthogonal codes (OOe) for application in communication systems using the technique of fiber-optics code division multiple access (OCDMA). The Prime Sequence codes and Quadratic codes are, for the first time in literature, characterized as Slepian group codes (spherical codes) and Quadratic Residues codes, respectively. Through the algorithm of the closed d-chain the Prime Sequence codes are obtained, as a particular case of the Slepian codes. The Quadratic codes are represented by binary quadratic integers in the form of Diophantine equations with two variables, so that, Z2 lattice or Â3 lattice supplies the codeword of the quadratic code. Furthermore, this thesis presents three new constructions of optical orthogonal codes (OOC), construed via congruences having as base the algebraic structure of the multiplicative group of the GaloisField GF(p). The performance of the codes is evaluated using the criterion of the error probability, for situations where the optic receiver incorporates a fiber-optic limiter and a APD photodiode. The performance of the system is evaluated considering the effect of the interference of multiple access, the ballistic noise of the photodiode and the thermal noise of the receiver. The performance of the considered codes is compared with the performance of other codes found in the technical literature. It is observed that the codes considered in this thesis, in this thesis, present similar performance to the reported codes, having as advantage an algebraic structure of simple implementation and better synchronism / Doutorado / Telecomunicações e Telemática / Doutor em Engenharia Elétrica

The spatial evolution of a pair of resonant Bragg modes through a medium characterized by a complex one-dimensional PT -symmetric periodic relative electric permittivity is thoroughly investigated. By using the two wave model, analytic solutions of Maxwell’s equations are derived in the nonparaxial regime in order to investigate the periodic energy exchange between the Bragg modes for the Hermitian optical lattices as well as for complex lattices and also to investigate the spatial evolution of the real part of the electric field that propagates through this medium. Three regimes defined by the symmetry breaking point are discussed: below it, above it and at it. These regimes are determined by the existence of four complex eigenvalues below the symmetry breaking point, which collide and coalesce into a pair of complex doubly degenerate eigenvalues at the breaking point. Above the critical value each member of the pair bifurcates into a pair of complex values and now they have a nonzero real part. In the Hermitian case, it is demonstrated that a complete reciprocal energy transfer between the pair of Bragg modes, in a manner similiar to the Pendellösung effect known from X-ray diffraction by a crystal, takes place. When the optical lattice is complex, the dynamics of the energy transfer is completely different from the Hermitian case: below the symmetry breaking point there exist a very nonreciprocal beating-like oscillatory behavior of the energy transfer between the Bragg modes; above the symmetry breaking point the spatial evolution of the energy transfer grows unlimited but an oscillatory evolution still takes place; and at the symmetry breaking point the phenomenon of mode trapping does not occur in this nonparaxial regime (previously seen in PT -symmetric optical lattices in the paraxial regime). For the complex lattice, all these regimes share the common features: existence of a preferable mode for which the energy is transferred and a spatial evolution of this transfer in a nonreciprocal fashion, some of the characteristics very well known of PT -symmetric optical systems. / CAPES - Coordenação de Aperfeiçoamento de Pessoal de Nível Superior / A evolução espacial de um par de modos de Bragg ressonantes através de um meio descrito por uma permissividade elétrica relativa PT -simétrica é completamente investigada. Usando o modelo de duas ondas, soluções analíticas para as equações de Maxwell são derivadas no regime não-paraxial a fim de investigar a transferência de energia entre esses modos de Bragg para uma rede ótica Hermitiana bem como para uma rede ótica complexa e também estudar a evolução espacial da parte real do campo elétrico que se propaga através desse meio. Três regimes definidos pela quebra de simetria são discutidos: abaixo, acima e no ponto de quebra de simetria. Estes regimes são determinados pela existência de quatro autovalores complexos distintos abaixo da quebra de simetria, que colidem e coalescem num par de autovalores valores complexos duplamente degenerados no ponto de quebra de simetria. Acima do ponto de quebra, quatro autovalores complexos distintos voltam a existir e agora cada um possui uma parte real não-nula. No caso Hermitiano, é demonstrado que uma transferência de energia completamente recíproca entre o par de modos de Bragg, numa maneira similiar ao efeito Pendellösung conhecido da difração de raios X por cristais, ocorre. Quando a rede ótica é complexa, a dinâmica da transferência de energia é completamente diferente do caso Hermitiano: abaixo do ponto de quebra de simetria existe um comportamento oscilatório do tipo batimento muito não-recíproco para a transferência de energia entre os modos de Bragg; acima do ponto de quebra de simetria a evolução espacial da transferência de energia cresce ilimitadamente mas um evolução oscilatória ainda ocorre; no ponto de quebra o fenômeno do aprisionamento de modo não ocorre nesse regime não-paraxial (anteriormente visto em redes óticas PT -simétricas no regime paraxial). Para a rede ótica complexa, todos estes regimes compartilham características em comum: existência de um modo preferencial para o qual a energia é transferida e uma evolução espacial dessa transferência de maneira não-recíproca, algumas das características muito bem conhecidas de sistemas óticos PT simétricos.

Submitted by Divisão de Documentação/BC Biblioteca Central (ddbc@ufam.edu.br) on 2018-05-16T14:49:10Z No. of bitstreams: 2 Dissertação.pdf: 26629967 bytes, checksum: d8fcb48ed60770cf6ba7a8936168718d (MD5) license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) / Approved for entry into archive by Divisão de Documentação/BC Biblioteca Central (ddbc@ufam.edu.br) on 2018-05-16T14:49:24Z (GMT) No. of bitstreams: 2 Dissertação.pdf: 26629967 bytes, checksum: d8fcb48ed60770cf6ba7a8936168718d (MD5) license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) / Made available in DSpace on 2018-05-16T14:49:24Z (GMT). No. of bitstreams: 2 Dissertação.pdf: 26629967 bytes, checksum: d8fcb48ed60770cf6ba7a8936168718d (MD5) license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) Previous issue date: 2018-03-23 / CNPq - Conselho Nacional de Desenvolvimento Científico e Tecnológico / The main goal in this dissertation is to study the versions for compact operators of Lindenstrauss property A and B. In the course of our work, we present results concerning weak-star topology, Schauder basis, approximation properties, Banach spaces that locally depend upon finitely many coordinates, strictly convex spaces, uniformly convex spaces, among others. In 2014 Miguel Martín answered positively the following question: Are there compact operators between Banach spaces that can not be approximated by compact operators that attain their norms? In order to do that, he introduced two properties called properties Ak and Bk or versions for compact operators of Lindenstrauss properties. In this dissertation we present some results regarding Lindenstrauss properties A and B, and we also provide several results regarding properties Ak and Bk. / O objetivo desta dissertação é estudar as versões das propriedades A e B de Lindenstrauss para operadores compactos. No decorrer do nosso trabalho, apresentamos resultados sobre a topologia fraca-estrela, bases de Schauder, propriedades da aproximação, espaços de Banach cuja norma depende localmente de finitas coordenados, espaço estritamente convexo, espaço uniformemente convexo, dentre outros. Em 2014 Miguel Martín publicou um artigo respondendo de maneira positiva a seguinte pergunta: Existem operadores compactos entre espaços de Banach que não podem ser aproximados por operadores compactos que atingem a norma? Ao fazer isso, introduziu, no mesmo trabalho, duas propriedades chamadas de propriedades Ak e Bk ou versões para operadores compactos das propriedades de Lindenstrauss. Nesta dissertação, são apresentados de maneira detalhada resultados relacionados às propriedades A e B de Lindenstrauss e propriedades Ak e Bk.

Submitted by Erika Demachki (erikademachki@gmail.com) on 2015-03-24T21:17:09Z No. of bitstreams: 3 Dissertação - Luiz Mario Lustosa Pascoal - 2014.pdf: 7280181 bytes, checksum: 68a6ac0602e3e51f6e6952bbd6916150 (MD5) FunctionApproximator.zip: 2288624 bytes, checksum: 178c2e6a0b080b3d0548836974016236 (MD5) license_rdf: 23148 bytes, checksum: 9da0b6dfac957114c6a7714714b86306 (MD5) / Approved for entry into archive by Erika Demachki (erikademachki@gmail.com) on 2015-03-24T21:19:16Z (GMT) No. of bitstreams: 3 Dissertação - Luiz Mario Lustosa Pascoal - 2014.pdf: 7280181 bytes, checksum: 68a6ac0602e3e51f6e6952bbd6916150 (MD5) FunctionApproximator.zip: 2288624 bytes, checksum: 178c2e6a0b080b3d0548836974016236 (MD5) license_rdf: 23148 bytes, checksum: 9da0b6dfac957114c6a7714714b86306 (MD5) / Made available in DSpace on 2015-03-24T21:19:16Z (GMT). No. of bitstreams: 3 Dissertação - Luiz Mario Lustosa Pascoal - 2014.pdf: 7280181 bytes, checksum: 68a6ac0602e3e51f6e6952bbd6916150 (MD5) FunctionApproximator.zip: 2288624 bytes, checksum: 178c2e6a0b080b3d0548836974016236 (MD5) license_rdf: 23148 bytes, checksum: 9da0b6dfac957114c6a7714714b86306 (MD5) Previous issue date: 2014-08-22 / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior - CAPES / With the development of web 2.0, social networks have achieved great space on the internet, with that many users provide information and interests about themselves. There are expert systems that make use of the user’s interests to recommend different products, these systems are known as Recommender Systems. One of the main techniques of a Recommender Systems is the Collaborative Filtering (User-based) which recommends products to users based on what other similar people liked in the past. Therefore, this work presents model approximation of functions that generates rankings, that through a Genetic Algorithm, is able to learn an approximation function composed by different social variables, customized for each Facebook user. The learned function must be able to reproduce a ranking of people (friends) originally created with user’s information, that apply some influence in the user’s decision. As a case study, this work discusses the context of events through information regarding the frequency of participation of some users at several distinct events. Two different approaches on learning and applying the approximation function have been developed. The first approach provides a general model that learns a function in advance and then applies it in a set of test data and the second approach presents an specialist model that learns a specific function for each test scenario. Two proposals for evaluating the ordering created by the learned function, called objective functions A and B, where the results for both objective functions show that it is possible to obtain good solutions with the generalist and the specialist approaches of the proposed method. / Com o desenvolvimento da Web 2.0, as redes sociais têm conquistado grande espaço na internet, com isso muitos usuários acabam fornecendo diversas informações e interesses sobre si mesmos. Existem sistemas especialistas que fazem uso dos interesses do usuário para recomendar diferentes produtos, esses sistemas são conhecidos como Sistemas de Recomendação. Uma das principais técnicas de um Sistema de Recomendação é a Filtragem Colaborativa (User-based) que recomenda produtos para seus usuários baseados no que outras pessoas similares à ele tenham gostado no passado. Portanto, este trabalho apresenta um modelo de aproximação de funções geradora de rankings que, através de um Algoritmo Genético, é capaz de aprender uma função de aproximação composta por diferentes atributos sociais, personalizada para cada usuário do Facebook. A função aprendida deve ser capaz de reproduzir um ranking de pessoas (amigos) criado originalmente com informações do usuário, que exercem certa influência na decisão do usuário. Como estudo de caso, esse trabalho aborda o contexto de eventos através de informações com relação a frequência de participação de alguns usuários em vários eventos distintos. Foram desenvolvidas duas abordagens distintas para aprendizagem e aplicação da função de aproximação. A primeira abordagem apresenta um modelo generalista, que previamente aprende uma função e em seguida a aplica em um conjunto de dados de testes e a segunda abordagem apresenta um modelo especialista, que aprende uma função específica para cada cenário de teste. Também foram apresentadas duas propostas para avaliação da ordenação criada pela função aprendida, denominadas funções objetivo A e B, onde os resultados para ambas as funções objetivo A e B mostram que é possível obter boas soluções com as abordagens generalista e especialista do método proposto.

Desenvolve-se um novo método de cálculo da probabilidade de adsorção química de átomos incidentes em superfícies metálicas. Introduz-se um modelo teórico de adsorção cujo Hamiltoniano descreve um átomo incidindo normalmente e interagindo com os elétrons da banda de condução de uma superfície metálica. Como interações, são levadas em consideração (1) a possibilidade de transferência de energia cinética e de carga do átomo para o metal e (2) o potencial de carga imagem do átomo ionizado. A solução do modelo consiste em se tratar a parte eletrônica e a nuclear do Hamiltoniano separadamente. A parte eletrônica é tratada com a técnica de grupo de renormalização introduzida por Wilson e a parte nuclear, através da solução numérica da equação de Schrödinger para o movimento nuclear. O acoplamento entre as duas componentes do hamiltoniano é tratado como perturbação à aproximação adiabática. A probabilidade de adsorção é calculada em função da energia cinética do átomo incidente através da regra de ouro de Fermi. Os resultados, mostrando que a probabilidade de adsorção decai rapidamente acima de uma energia cinética característica, são interpretados fisicamente. / A new procedure that calculates sticking coefficients for atomic beams incident upon metallic surfaces is discussed. A model Hamiltonian describing the normal incidence of an ad-atom and its interaction with the conduction electrons of the adsorbate is introduced. The Hamiltonian accounts for two couplings: (1) the overlap between the atomic orbital and the metallic conduction states, allowing charge transfer between incident particle and adsorbate, and (2) the image potential associated with the ionized ad-atom. The electronic and nuclear parts of the model Hamiltonian are diagonalized separately, the former by renormalization group techniques and the second by numerical integration of the Schrödinger equation for the nuclear motion. Through the perturbative treatment, the first order corrections to the adiabatic approximation are presented. The results, showing that the sticking coefficient diminishes rapidly above a characteristic kinetic energy o£ the incident atom, are interpreted.

Um modelo matemático e simulações numéricas são apresentados para investigação da dinâmica do escoamento de gás, óleo e água em sistemas pipeline-riser. O pipeline é modelado como um sistema de parâmetros concentrados e considera dois estados comutáveis: um em que o gás é capaz de penetrar no riser e outro no qual há uma frente de acúmulo de líquido, prevenindo a penetração do gás. O modelo do riser considera um sistema de parâmetros distribuídos, no qual nós móveis são usados para avaliar as condições locais ao longo do subsistema. Efeitos de transferência de massa são modelados utilizando a aproximação de black-oil. O modelo prediz a localização da frente de acúmulo de líquido no pipeline e do nível de líquido no riser, de maneira que é possível determinar qual tipo de intermitência severa ocorre no sistema. O método das características é usado para simplificar a diferenciação no sistema de equações mistas hiperbólicas-parabólicas resultante. As equações são discretizadas e integradas usando um método implícito com um esquema preditor-corretor para o tratamento das não-linearidades. Simulações correspondentes às condições de intermitência severa são apresentadas e comparadas aos resultados obtidos com o código computacional OLGA, resultando em uma boa concordância. Apresenta-se uma descrição dos tipos de intermitência severa para o escoamento trifásico de gás, óleo e água em um sistema pipeline-riser com efeitos de transferência de massa, assim como um estudo da influência de parâmetros geométricos e de caracterização dos fluidos sobre os mapas de estabilidade. / A mathematical model and numerical simulations are presented to investigate the dynamics of gas, oil and water flow in a pipeline-riser system. The pipeline is modeled as a lumped parameter system and considers two switchable states: one in which the gas is able to penetrate into the riser and another in which there is a liquid accumulation front, preventing the gas from penetrating the riser. The riser model considers a distributed parameter system, in which movable nodes are used to evaluate local conditions along the subsystem. Mass transfer effects are modeled by using a black oil approximation. The model predicts the location of the liquid accumulation front in the pipeline and the liquid level in the riser, so it is possible to determine which type of severe slugging occurs in the system. The method of characteristics is used to simplify the differentiation of the resulting mixed hyperbolic-parabolic system of equations. The equations are discretized and integrated using an implicit method with a predictor-corrector scheme for the treatment of the nonlinearities. Simulations corresponding to severe slugging conditions are presented and compared to results obtained with OLGA computer code, showing a very good agreement. A description of the types of severe slugging for the three-phase flow of gas, oil and water in a pipeline-riser system with mass transfer effects is presented, as well as a study of the influence of geometric and fluid characterization parameters on the stability maps.

Coordenação de Aperfeiçoamento de Pessoal de Nível Superior / No presente trabalho investigamos os efeitos da mudança das constantes de acoplamento entre os híperons (D; L; S e X) e os mésons (s; w e r) tendo em vista sua aplicacação na estrutura de estrelas de nêutron. Para tanto, adotamos o modelo de Walecka não-linear numa aproximacão de campo médio. / In the present work we investigated the effects of changing of the coupling constants between the hyperons (D; L; S and X) and mesons (s; w and r) regarding its application in the structure of neutron stars. To this end, we adopted the non-linear Walecka model in the mean field approximation.

Made available in DSpace on 2016-08-17T14:52:56Z (GMT). No. of bitstreams: 1 Juan Moises Mauricio Villanueva.pdf: 944458 bytes, checksum: 0b17f88c59a4149e61f4f3fa0969445e (MD5) Previous issue date: 2005-03-03 / In several applications in electronics, the generation of nonlinear function values using low-cost embedded systems is a problem. The nonlinear functions cannot be directly implemented due to restrictions of fixed-point calculations and limited resolution that are characteristics of the architecture of the processor employed. In this work, a procedure for determining piecewise linear approximation of nonlinear functions for a low-cost embedded system is presented. In order to solve this problem, a hierarchical evolutionary algorithm has been developed for determining the position and the minimal number of breakpoints and the minimal size of the look-up table for storing these breakpoints, for generating the approximated function values. The nonlinear function can be approximated using piecewise linear functions from the obtained breakpoints. The developed algorithm is tested using the case of approximating the first quadrant of a sine function, and the obtained results are presented for different resolutions for the input and output values generation. / Em diversas aplicações em eletrônica existe o problema de gerar valores de funções não lineares utilizando-se sistemas embarcados de baixo custo. Essas funções não lineares não podem ser implementadas diretamente devido às restrições de cálculo em ponto fixo e resolução limitada, características de arquitetura do processador empregado. Nesta dissertação, apresenta-se um procedimento para a determinação de aproximação linear por partes de funções não lineares para sistemas embarcados de baixo custo. Para resolver este problema, desenvolveu-se um algoritmo hierárquico evolutivo que determinará a posição e número mínimo de pontos de quebra e tamanho mínimo da tabela de equivalência para armazenar esses pontos de quebra, para gerar os valores da função aproximada. A função não linear pode então ser aproximada por funções lineares a partir dos valores dos pontos de quebra encontrados. O algoritmo desenvolvido é testado para o caso de aproximação da função seno no primeiro quadrante, e os resultados obtidos são apresentados para diversas resoluções de entrada e de geração dos valores de saída.

Nessa tese consideramos problemas de alocação e precificação de itens, onde temos um conjunto de itens e um conjunto de compradores interessados em tais itens. Nosso objetivo é escolher uma alocação de itens a compradores juntamente com uma precificação para tais itens para maximizar o lucro obtido, considerando o valor máximo que um comprador está disposto a pagar por um determinado item. Em particular, focamos em três problemas: o Problema da Compra Máxima, o Problema da Precificação Livre de Inveja e o Leilão de Anúncios de Segundo Preço. O Problema da Compra Máxima e o Problema da Precificação Livre de Inveja modelam o problema que empresas que vendem produtos ou serviços enfrentam na realidade, onde é necessário escolher corretamente os preços dos produtos ou serviços disponíveis para os clientes para obter um lucro interessante. Já o Leilão de Anúncios de Segundo Preço modela o problema enfrentado por empresas donas de ferramentas de busca que desejam vender espaço para anunciantes nos resultados das buscas dos usuários. Ambas as questões, tanto a precificação de produtos e serviços quanto a alocação de anunciantes em resultados de buscas, são de grande relevância econômica e, portanto, são interessantes de serem atacadas dos pontos de vista teórico e prático. Nosso foco nesse trabalho é considerar algoritmos de aproximação e algoritmos de programação inteira mista para os problemas mencionados, apresentando novos resultados superiores àqueles conhecidos previamente na literatura, bem como determinar a complexidade computacional destes problemas ou de alguns de seus casos particulares de interesse. / In this thesis we consider allocation and pricing problems, where we have a set of items and a set of consumers interested in such items. Our objective is to choose an allocation of items to consumers, considering the maximum value a consumer is willing to pay in a specific item. In particular, we focus in three problems: the Max-Buying Problem, the Envy-Free Pricing Problem and the Second-Price Ad Auction. The Max-Buying Problem and the Envy-Free Pricing Problem model a problem faced in reality by companies that sell products or services, where it is necessary to correctly choose the price of the products or services available to clients in order to obtain an interesting profit. The Second-Price Ad Auction models the problem faced by companies that own search engines and desire to sell space for advertisers in the search results of the users. Both questions, the pricing of items and services and the allocation of advertisers in search results are of great economical relevance and, for this, are interesting to be attacked from a theoretical and a practical perspective. Our focus in this work is to consider approximation algorithms and mixed integer programming algorithms for the aforementioned problems, presenting new results superior than the previously known in the literature, as well as to determine the computational complexity of such problems or some of their interesting particular cases.