Um importante fator que precisa ser considerado para alcançar alto desempenho em aplicações paralelas é a distribuição dos processos nos núcleos do sistema, denominada mapeamento de processos. Mesmo o mapeamento estático de processos é um problema NP-difícil. Por esse motivo, são utilizadas heurísticas que dependem da aplicação e do hardware no qual a aplicação será mapeada. Nas arquiteturas atuais, além da possibilidade de haver mais de um processador por nó do cluster, é possível haver mais de um núcleo de processamento por processador, assim, o mapeamento estático de processos pode considerar pelo menos três níveis de comunicação entre os processos que executam em um cluster multi-core: intra-chip, intra-nó e inter-nó. Este trabalho propõe a heurística MapEME (Mapeamento Estático MPI com Emparelhamento) que emprega o Emparelhamento Perfeito de Custo Máximo (EPCM) no cálculo do mapeamento estático de processos paralelos MPI em processadores multi-core. Os resultados alcançados pelo mapeamento gerado pela MapEME são comparados aos resultados obtidos pelo mapeamento gerado pela aplicação Scotch, que utiliza o Biparticionamento Recursivo Dual (BRD), já utilizado como heurística para mapeamento estático de processos. Ambas as heurísticas são comparadas à Busca Exaustiva (BE) para verificar o quanto estão próximas do ótimo. Os três métodos têm a complexidade e o ganho no tempo de execução em ralação à distribuição padrão da biblioteca MPICH2 comparados entre si. A principal contribuição deste trabalho é mostrar que a heurística EPCM apresenta ganho de até 40% equivalente a já difundida BRD, e possui uma complexidade menor ao ser aplicado em um cluster multi-core que compartilha cache nível 2 a cada dois núcleos. / An important factor that must be considered to achieve high performance on parallel applications is the mapping of processes on cores. However, since this is defined as an NP-Hard problem, it requires different mapping heuristics that depends on the application and the hardware on which it will be mapped. On the current architectures we can have more than one multi-core processors per node, and consequently the process mapping can consider three process communication types: intrachip, intranode and internode. This work propose the MapEME (Static Mapping MPI using Matching) that use the Maximum Weighted Perfect Matching (MWPM) to calculate the static process mapping and analyze its performance. The results provided by MapEME are compared with the results of application Scotch. It uses Dual Recursive Bipartitioning (DRB), an already used heuristics for static mapping. Both heuristics are compared with Exhaustive Search (ES) to verify how much the two heuristics are near the optimum. The three methods have theirs complexities analyzed. Also the mapping gain when compared with the standard MPICH2 distribution was measured. The main contribution of this work is to show that the heuristic, EPCM, provides gain up to 40%, close of DRB gain. Furthermore, EPCM has a lower complexity when applied to a multicore cluster that shares L2 cache every two cores.

RODRIGUES, Lorena da Silva. E tenho dito: a gramaticalização e a variação do pretérito perfeito composto em narrativas dos séculos XV a XVII. 2010. 132f. – Dissertação (Mestrado) – Universidade Federal do Ceará, Departamento de Letras Vernáculas, Programa de Pós-graduação em Linguística, Fortaleza (CE), 2010. / Submitted by Márcia Araújo (marcia_m_bezerra@yahoo.com.br) on 2014-08-22T16:41:41Z No. of bitstreams: 1 2010_dis_lsrodrigues.pdf: 828896 bytes, checksum: c534a2f1cea68b1d7ad1b956a887eb6b (MD5) / Approved for entry into archive by Márcia Araújo(marcia_m_bezerra@yahoo.com.br) on 2014-08-22T17:09:35Z (GMT) No. of bitstreams: 1 2010_dis_lsrodrigues.pdf: 828896 bytes, checksum: c534a2f1cea68b1d7ad1b956a887eb6b (MD5) / Made available in DSpace on 2014-08-22T17:09:35Z (GMT). No. of bitstreams: 1 2010_dis_lsrodrigues.pdf: 828896 bytes, checksum: c534a2f1cea68b1d7ad1b956a887eb6b (MD5) Previous issue date: 2010 / In this dissertation, we deal with the grammaticalization of past tense compound in Portuguese. We discuss linguistic change, based on the correlation form(s)-function(s) in two lines of analysis: (I) the grammaticalization continuum of to have/there to be (full) + adjectival participle > to have/there to be (auxiliary) + verb participle and (ii) the linguistic variation in coding the perfective past tense before the moment of speech. Two theoretical approaches base the research: the linguistic Functionalism, focused on grammaticalization, and the Theory of Linguistic Variation and Change, establishing thus a socio-functionalist research model. For this, we used narratives in prose from the XV, XVI and XVII centuries, Portuguese transition and fixation moment. Regarding grammaticalization, we investigated Lehmann’s (2002[1985]) grammaticalization parameters - Integrity, Paradigmaticity, Paradigmatic Variability, Scope, Bondedness, Syntagmatic Variability - modality, reference time and verb type. Regarding variation, we investigated modality, aspect, semantic nature of arguments, type of verb, time and textual reference and the historical moment. Out of these factors, the ones shown as relevant for conditioning were time and reference relation, semantic nature of the subject, aspect and historical moment. This proposal is relevant because, besides attesting the past tense compound use made throughout Portuguese history as previous research has done on the topic, it investigates the factors that condition to have/there to be + past participle change from the socio-functionalist viewpoint. / Nesta dissertação, tratamos da gramaticalização do pretérito perfeito composto em Língua Portuguesa. Abordamos a mudança linguística, partindo da correlação forma(s)-função(ões) em dois eixos de análise: (i) o continnum de gramaticalização de ter/haver (pleno) + particípio adjetival > ter/haver (auxiliar) + particípio verbal e (ii) a variação linguística na codificação do tempo passado perfectivo anterior ao momento da fala. Duas abordagens teóricas embasam a pesquisa: o Funcionalismo linguístico, voltado à gramaticalização e a Teoria da Variação e Mudança Linguística, estabelecendo, dessa forma, um modelo sociofuncionalista de investigação. Para isso, utilizamos narrativas em prosa dos séculos XV, XVI e XVII, período de transição e fixação da Língua Portuguesa. No que concerne à gramaticalização, foram investigados os parâmetros de gramaticalização de Lehmann (2002[1985]) – Integridade, Paradigmaticidade, Variabilidade paradigmática, Escopo, Conexidade, Variabilidade sintagmática – a modalidade, o tempo em relação à referência e o tipo de verbo. No que diz respeito à variação, foram analisados a modalidade, o aspecto, a natureza semântica dos argumentos, o tipo de verbo, a referência temporal – textual e o período histórico. Desses fatores mostram-se relevantes para o condicionamento a relação entre tempo e referência, a natureza semântica do sujeito, o aspecto e o período histórico. Essa proposta se mostra relevante, porque, além de atestar o uso o pretérito perfeito composto ao longo da história da linguística do Português como as pesquisas anteriores sobre o tema, investiga os fatores que condicionaram a mudança de ter/haver + particípio passado sob a ótica sociofuncionalista.

FONSECA, Maria Cristina Micelli. A semântica e a pragmática na compreensão das oposições present perfect X past simple do inglês e pretérito perfecto X pretérito indefinido do espanhol. 2006. 229f. Tese (Doutorado) - Universidade de São Paulo, Departamento de Linguística, São Paulo, 2006. / Submitted by anizia almeida (aniziaalmeida80@gmail.com) on 2016-09-09T11:22:10Z No. of bitstreams: 1 2006_tese_mcmfonseca.pdf: 2203074 bytes, checksum: 6e6d060283ef30feaa9761f29f478e51 (MD5) / Approved for entry into archive by Márcia Araújo (marcia_m_bezerra@yahoo.com.br) on 2016-09-13T14:39:48Z (GMT) No. of bitstreams: 1 2006_tese_mcmfonseca.pdf: 2203074 bytes, checksum: 6e6d060283ef30feaa9761f29f478e51 (MD5) / Made available in DSpace on 2016-09-13T14:39:48Z (GMT). No. of bitstreams: 1 2006_tese_mcmfonseca.pdf: 2203074 bytes, checksum: 6e6d060283ef30feaa9761f29f478e51 (MD5) Previous issue date: 2006 / In this thesis, the roles of Semantics and Pragmatics in text comprehension tasks have been investigated in Portuguese speakers interlanguage early grammar. The texts in both English and Spanish had past events told employing Present Perfect x Past Simple and Pretérito Perfecto x Pretérito Indefinido pairings. We have adopted (Michaellis, 1998) that the English periphrasis has as its most salient meaning the resultative reading and have applied it to the Spanish periphrasis as well. Portuguese, on the other hand, expresses resultative meaning in different ways most of the times leading students to see in the Present Perfect and Pretérito Perfecto structures the past event meaning alone. Consequently, when analyzing the foreign language structures, learners end up assigning them the aspectual values which belong to the Portuguese [TER+Participle] and [ESTAR+Gerund] periphrases, despite their not sharing the same aspectual values most of the time, because the English and Spanish forms express the perfective and resultative aspect, while the Portuguese periphrasis indicates the imperfective and durative aspect. This mismatch affects text comprehension, but is not perceived by the students. Learners first analyze the target language structure (topdown procedure, Liceras, 2003a), once they cannot have access to the features which trigger the parameter setting, precluding a bottom-up procedure. The same pattern of value assignment from the L1 periphrasis to both L2 is noticeable in both English and Spanish interlanguages. Analysis of Variance tests have proven that both interlanguages undergo the same process, which starts from L1 reestructuring. This fact suggests that adult L2 learner will make use of UG principles, but will not set parameters the way children do, L2 will grow by reestructuring portions of L1. The semantic values applied in both English and Spanish interlanguages at this stage, are L1?s as well, allowing a comparison to the phonology acquisition. Children are born sensitive to any semantic value, but due to a critical period for semantics, adult L2 learners will acquire L2 semantic values by reestructing not only the syntax of L1 but also its semantic values. Learners will have access to pragmatics, after semantics, as a fine-tuned meaning. / Nesta tese observa-se o papel que a semântica e a pragmática desempenham, na gramática inicial (early grammar) da interlingua de falantes de português, na compreensão de textos em inglês e em espanhol nos quais se relatam eventos passados e se empregam as oposições Present Perfect x Past Simple e Pretérito Perfecto x Pretérito Indefinido. Assumimos (Michaellis, 1998) que um dos valores mais fortes das formas compostas dessas duas línguas é o resultativo e que como o português, na maioria das vezes, expressa o resultado de outros modos, o aprendiz vê naquelas apenas uma maneira de expressar ações passadas. Em função disso, ao analisar a estrutura na língua estrangeira, acaba atribuindo aos tempos compostos de ambas os valores aspectuais das perífrases (TER+Particípio) e (ESTAR+Gerúndio) do português, que em muitos casos não coincide com os valores das formas perifrásticas das línguas que estão aprendendo. Enquanto as perífrases da língua estrangeira têm o aspecto perfectivo resultativo, as do português tem valor imperfectivo continuativo. Tal fato, que afeta a compreensão do texto, não é percebido pelos aprendizes. Estes analisam primeiramente a sintaxe da língua-alvo (top-drow procedure, Liceras, 2003a) uma vez que não tem acesso aos traços que desencadeiam a fixação de parâmetros para a realização do bottom-up. O padrão de atribuição dos valores das perífrases da L1 para a L2 aparece nas interlínguas do espanhol e do inglês, apontando para um mesmo processo, independente de a língua-alvo ser mais ou menos próxima do português. Testes com análise de variância comprovam que se trata de um mesmo processo para as duas línguas, que começa a partir da reestruturação da L1, sugerindo que a aquisição dessa é regida pelos princípios da GU, mas que a marcação de parâmetros não acontecerá como na L1, mas se dará via reestruturação de porções da L1. os valores semânticos utilizados na interlíngua, com a fonologia, a criança nasce com sensibilidade para acessar qualquer valor semântico, mas existe um período crítico que faz com que a aquisição da L2 ocorra por reestruturação não apenas sintática mas também semântica dos valores da L1. A pragmática, por sua vez, será acessada, após a semântica, como uma sintonia fina do sentido.

The Aspect Hypothesis (Andersen & Shirai, 1994; 1996) proposes that the inherent lexical aspect of verbs plays a major role in the acquisition of tense-aspect (TA) morphology in both first and second language. This has been attested in most studies on TA morphology conducted with past and present TA markers. The present study examined the acquisition of Present Perfect, a rather insufficiently studied TA form from a Prototype Account, in two of its four functions, Experiential Past and Persistent Situation. The subjects were 85 L1-Spanish English language learners at intermediate and advanced levels. All participants had received formal instruction in English grammar as part of their curriculum. The data was collected through a forced-choice task with 16 situations equally distributed between the two Present Perfect functions and between telic and atelic verbs of four semantic categories: stative, activities, achievements, and accomplishments. Participants had to choose the correct verb form out of three options (Present, Past or Present Perfect) that would best complete the sentences given. The results showed evidence of clear developmental stages in the acquisition of the Present Perfect. The stages were characterized by an important role of proficiency level and lexical aspect as the more proficient participants showed a more accurate use of the target form. In addition, both the intermediate and advanced groups showed a tendency towards employing Persistent Situation with atelic verb types, whereas they used Experiential Past with telic verbs. Contrary to the predictions of the AH, the use that seemed to be first acquired and easier to learn was Persistent Situation, which obtained higher correctness rates in both groups than Experiential Past. When the results were analyzed across each aspectual verb type, the pattern of acquisition was less clear and thereby partly met the claims of the AH. This irregular trend attested in the data encouraged the argument that the acquisition of the functions of the Present Perfect may not be solely influenced by lexical aspect and verb prototypicality but several other factors may be at stake, such as sentence-type effect, input distribution, L1 transfer and rote-learned forms. Therefore, developmental stages in the acquisition of the Present Perfect should be examined in view of an interplay of "multiple factors" as already proposed by Sugaya and Shirai (2007), which work simultaneously and in a complementary fashion in the acquisitional process of TA morphology.

Coordenação de Aperfeiçoamento de Pessoal de Nível Superior / Nesta dissertação, procuramos soluções exatas das equações de campo de Einstein em Relatividade Geral que descrevem um fluido perfeito em um espaço-tempo estático com simetria esférica. A técnica utilizada para encontrar essas soluções é o algoritmo de Kovacic, que pode ser aplicado a equações diferenciais ordinárias lineares e homogêneas de segunda ordem com coeficientes racionais. Esse algoritmo é capaz de nos dar soluções fechadas em termos de funções liouvillianas, se tal equação tiver esse tipo de solução. Para esse fim, vários sistemas de coordenadas foram investigados até encontrar o que fosse mais adequado à aplicação do algoritmo. Impondo que a função da métrica 11 g seja racional, ficamos com uma equação diferencial linear e homogênea de segunda ordem que tem coeficientes racionais. Nesse trabalho, as formas arbitradas foram: g11=-A/4x x-z1/x-Z1, g11=-A/4x x-z1/(x-Z1)(x-Z2), g11=-A/4x (x-z1) (x-z2)/x-Z1 e g11= -A/4x (x-z1) (x-z2)/ 4x(x-Z1) (x-Z2) onde x é uma coordenada espacial da métrica e Α, z1 , z2 , Z1 e Z2 são parâmetros dos modelos. Depois de obter soluções analíticas, verificamos se elas satisfazem determinadas condições físicas e, então, poderiam ser utilizadas como modelos de estrelas de nêutrons sem rotação (estrelas de alta densidade).

Coordenação de Aperfeiçoamento de Pessoal de Nível Superior / Nesta dissertação, procuramos soluções exatas das equações de campo de Einstein em Relatividade Geral que descrevem um fluido perfeito em um espaço-tempo estático com simetria esférica. A técnica utilizada para encontrar essas soluções é o algoritmo de Kovacic, que pode ser aplicado a equações diferenciais ordinárias lineares e homogêneas de segunda ordem com coeficientes racionais. Esse algoritmo é capaz de nos dar soluções fechadas em termos de funções liouvillianas, se tal equação tiver esse tipo de solução. Para esse fim, vários sistemas de coordenadas foram investigados até encontrar o que fosse mais adequado à aplicação do algoritmo. Impondo que a função da métrica 11 g seja racional, ficamos com uma equação diferencial linear e homogênea de segunda ordem que tem coeficientes racionais. Nesse trabalho, as formas arbitradas foram: g11=-A/4x x-z1/x-Z1, g11=-A/4x x-z1/(x-Z1)(x-Z2), g11=-A/4x (x-z1) (x-z2)/x-Z1 e g11= -A/4x (x-z1) (x-z2)/ 4x(x-Z1) (x-Z2) onde x é uma coordenada espacial da métrica e Α, z1 , z2 , Z1 e Z2 são parâmetros dos modelos. Depois de obter soluções analíticas, verificamos se elas satisfazem determinadas condições físicas e, então, poderiam ser utilizadas como modelos de estrelas de nêutrons sem rotação (estrelas de alta densidade).

Um importante fator que precisa ser considerado para alcançar alto desempenho em aplicações paralelas é a distribuição dos processos nos núcleos do sistema, denominada mapeamento de processos. Mesmo o mapeamento estático de processos é um problema NP-difícil. Por esse motivo, são utilizadas heurísticas que dependem da aplicação e do hardware no qual a aplicação será mapeada. Nas arquiteturas atuais, além da possibilidade de haver mais de um processador por nó do cluster, é possível haver mais de um núcleo de processamento por processador, assim, o mapeamento estático de processos pode considerar pelo menos três níveis de comunicação entre os processos que executam em um cluster multi-core: intra-chip, intra-nó e inter-nó. Este trabalho propõe a heurística MapEME (Mapeamento Estático MPI com Emparelhamento) que emprega o Emparelhamento Perfeito de Custo Máximo (EPCM) no cálculo do mapeamento estático de processos paralelos MPI em processadores multi-core. Os resultados alcançados pelo mapeamento gerado pela MapEME são comparados aos resultados obtidos pelo mapeamento gerado pela aplicação Scotch, que utiliza o Biparticionamento Recursivo Dual (BRD), já utilizado como heurística para mapeamento estático de processos. Ambas as heurísticas são comparadas à Busca Exaustiva (BE) para verificar o quanto estão próximas do ótimo. Os três métodos têm a complexidade e o ganho no tempo de execução em ralação à distribuição padrão da biblioteca MPICH2 comparados entre si. A principal contribuição deste trabalho é mostrar que a heurística EPCM apresenta ganho de até 40% equivalente a já difundida BRD, e possui uma complexidade menor ao ser aplicado em um cluster multi-core que compartilha cache nível 2 a cada dois núcleos. / An important factor that must be considered to achieve high performance on parallel applications is the mapping of processes on cores. However, since this is defined as an NP-Hard problem, it requires different mapping heuristics that depends on the application and the hardware on which it will be mapped. On the current architectures we can have more than one multi-core processors per node, and consequently the process mapping can consider three process communication types: intrachip, intranode and internode. This work propose the MapEME (Static Mapping MPI using Matching) that use the Maximum Weighted Perfect Matching (MWPM) to calculate the static process mapping and analyze its performance. The results provided by MapEME are compared with the results of application Scotch. It uses Dual Recursive Bipartitioning (DRB), an already used heuristics for static mapping. Both heuristics are compared with Exhaustive Search (ES) to verify how much the two heuristics are near the optimum. The three methods have theirs complexities analyzed. Also the mapping gain when compared with the standard MPICH2 distribution was measured. The main contribution of this work is to show that the heuristic, EPCM, provides gain up to 40%, close of DRB gain. Furthermore, EPCM has a lower complexity when applied to a multicore cluster that shares L2 cache every two cores.

Um importante fator que precisa ser considerado para alcançar alto desempenho em aplicações paralelas é a distribuição dos processos nos núcleos do sistema, denominada mapeamento de processos. Mesmo o mapeamento estático de processos é um problema NP-difícil. Por esse motivo, são utilizadas heurísticas que dependem da aplicação e do hardware no qual a aplicação será mapeada. Nas arquiteturas atuais, além da possibilidade de haver mais de um processador por nó do cluster, é possível haver mais de um núcleo de processamento por processador, assim, o mapeamento estático de processos pode considerar pelo menos três níveis de comunicação entre os processos que executam em um cluster multi-core: intra-chip, intra-nó e inter-nó. Este trabalho propõe a heurística MapEME (Mapeamento Estático MPI com Emparelhamento) que emprega o Emparelhamento Perfeito de Custo Máximo (EPCM) no cálculo do mapeamento estático de processos paralelos MPI em processadores multi-core. Os resultados alcançados pelo mapeamento gerado pela MapEME são comparados aos resultados obtidos pelo mapeamento gerado pela aplicação Scotch, que utiliza o Biparticionamento Recursivo Dual (BRD), já utilizado como heurística para mapeamento estático de processos. Ambas as heurísticas são comparadas à Busca Exaustiva (BE) para verificar o quanto estão próximas do ótimo. Os três métodos têm a complexidade e o ganho no tempo de execução em ralação à distribuição padrão da biblioteca MPICH2 comparados entre si. A principal contribuição deste trabalho é mostrar que a heurística EPCM apresenta ganho de até 40% equivalente a já difundida BRD, e possui uma complexidade menor ao ser aplicado em um cluster multi-core que compartilha cache nível 2 a cada dois núcleos. / An important factor that must be considered to achieve high performance on parallel applications is the mapping of processes on cores. However, since this is defined as an NP-Hard problem, it requires different mapping heuristics that depends on the application and the hardware on which it will be mapped. On the current architectures we can have more than one multi-core processors per node, and consequently the process mapping can consider three process communication types: intrachip, intranode and internode. This work propose the MapEME (Static Mapping MPI using Matching) that use the Maximum Weighted Perfect Matching (MWPM) to calculate the static process mapping and analyze its performance. The results provided by MapEME are compared with the results of application Scotch. It uses Dual Recursive Bipartitioning (DRB), an already used heuristics for static mapping. Both heuristics are compared with Exhaustive Search (ES) to verify how much the two heuristics are near the optimum. The three methods have theirs complexities analyzed. Also the mapping gain when compared with the standard MPICH2 distribution was measured. The main contribution of this work is to show that the heuristic, EPCM, provides gain up to 40%, close of DRB gain. Furthermore, EPCM has a lower complexity when applied to a multicore cluster that shares L2 cache every two cores.

Nesta tese consideramos uma nova classe de sistemas markovianos de partículas com infinitas componentes interagentes. O sistema representa a evolução temporal dos potenciais de membrana de um conjunto infinito de neurônios interagentes. Provamos a existência e unicidade do processo construindo um pseudo-algoritmo de simulação perfeita e mostrando que este algoritmo roda em um número finito de passos quase certamente. Estudamos também o comportamento do sistema quando consideramos apenas um conjunto finito de neurônios. Neste caso, construímos um procedimento de simulação perfeita para o acoplamento entre o processo limitado a um conjunto finito de neurônios e o processo que considera todos os neurônios do sistema. Como consequência encontramos um limitante superior para a probabilidade de discrepância entre os processos. / We consider a new class of interacting particle systems with a countable number of interacting components. The system represents the time evolution of the membrane potentials of an infinite set of interacting neurons. We prove the existence and uniqueness of the process, by the construction of a perfect simulation procedure. We show that this algorithm is successful, that is, we show that the number of steps of the algorithm is finite almost surely. We also study the behaviour of the system when we consider only a finite number of neurons. In this case, we construct a perfect simulation procedure for the coupling of the process with a finite number of neurons and the process with a infinite number of neurons. As a consequence we obtain an upper bound for the error we make when sampling from a finite set of neurons instead of the infinite set of neurons.

Orientador: Célia Picinin de Mello / Tese (doutorado) - Universidade Estadual de Campinas, Instituto de Computação / Made available in DSpace on 2018-08-19T10:47:23Z (GMT). No. of bitstreams: 1 Pedrotti_Vagner_D.pdf: 2015411 bytes, checksum: 4a6917f5811bde65dedbf0f7ab2577c5 (MD5) Previous issue date: 2011 / Resumo: Nesta tese de doutoramento sáo considerados três problemas em grafos, para os quais sáo obtidos resultados quando a entrada é restrita a algumas classes. Todos os problemas sáo problemas de otimização combinatória sobre grafos simples e apresentam diferentes classificações de complexidade. Em dois casos, o estudo focou classes de grafos com "poucos iYs" e ° uso da decomposição modular. No último caso, considerou-se uma subclasse dos grafos de intervalos e a aplicação de uma técnica conhecida como pullback. O primeiro problema estudado é o Problema dos Separadores Minimais, para o qual são conhecidos algoritmos polinomiais em toda classe de grafos que possuir um número polinomial de separadores minimais. Serão dados, como contribuição deste trabalho, um algoritmo linear para listar os separadores minimais de grafos P4-carregados estendidos e limitantes justos no número e tamanho dos separadores minimais destes grafos, bem como de algumas de suas subclasses, P4-carregada, P4-arrumada e P4-íeve. Estes resultados estendem um algoritmo anterior para grafos P4-esparsos, ao mesmo tempo que incluem estas classes de grafos entre as que possuem um número de separadores minimais limitado por um função linear no número de vértices do grafo. Em seguida, será tratado o Problema de Empacotamento de Cliques, uma extensão do problema de emparelhamento máximo. Para a maioria das classes de grafos mais importantes, o problema é NP-Difícil. A contribuição apresentada resolve este problema em tempo polinomial (para qualquer tamanho fixo de clique) em grafos P4-arrumados, através de uma técnica similar a utilizada para os cografos. Infelizmente, para as superclasses mais estudadas da classe P4-arrumada, este problema é NP-Difícil, o que é um indício de que a técnica utilizada foi totalmente aproveitada em relação ás classes com poucos _P4's. Por fim, será estudado o Problema da Coloração Total Forte, uma variação do problema clássico da coloração total, que foi introduzido há pouco tempo e ainda tem sua complexidade computacional desconhecida. Como esperado, existem algoritmos polinomiais apenas para classes bastante simples de grafos. Além da complexidade, outro importante ponto em aberto para o problema é a conjectura de que o número de cores necessárias na solução do problema para um grafo G seria limitado por A(G) + 3. A técnica do pullback, já utilizada para os Problemas de Coloração de Arestas e Coloração Total em grafos dualmente cordais será estendida, resultando em um algoritmo linear para grafos indiferença (também conhecido como grafos de intervalos próprios). Este algoritmo produz uma solução que valida a conjectura nesta classe de grafos. Estas contribuições confirmam a importância da decomposição modular em algoritmos para classes de grafos com "poucos iYs" e ampliam o uso da técnica do pullback para variações dos problemas clássicos de coloração / Abstract: In this doctoral thesis, three problems on graphs are considered and results are given for them when the input is resctricted to some graph classes. All the problems are combinatorial optimization problems on simple graphs and have distinct classihcations of complexity. In two of them, the research focused on graph classes known as graphs with "few iVs" and on the use of modular decomposition on such graphs. In the last problem, a subclass of interval graphs was studied with respect to the application of the technique known as pullback. The first problem studied is the Minimal Separator Problem. For this problem, there exists polynomial time algorithms for every class of graphs which has a polynomial number of minimal separators. A linear-time algorithm, that lists all minimal separators of extended iVladen graphs, is presented. Moreover, tight bounds on the number and on the total size of minimal separators are given for extended iVladen graphs and for some of their subclasses: the iVladen, iVtidy, and iVlite graphs. This result extends a previous algorithm for iVspai'se graphs and gives, for the above classes, better bounds on the number of minimal separators that were already known to be polynomial. Then, the Clique Packing Problem is analyzed. The problem is an extension of the classical Maximum Matching Problem and is NP-Hard for almost all graph classes. The contribution presented solves the problem in polynomial time (for any fixed clique size) in iVtidy graphs through a technique similar to that used for cographs. However, the most well-known superclasses of iVtidy graphs contains split graphs, for which this problem is NP-Hard. This is an evidence that the technique was fully explored with respect of graph classes with few iVs. At last, the Strong Total Coloring Problem is considered. It is a recently introduced variation of the classical Total Coloring Problem and its complexity is still unknown. As expected, there are quite few graph classes for which the problem has a polynomial time algorithm. Besides its complexity, another important open question for this problem is a conjecture which states that A(G) + 3 colors are sufficient for coloring any graph G. A known technique, called pullback, used for edge and total coloring of dually chordal graphs is extended to derive a linear time algorithm for indifference graphs (also known as proper interval graphs). This algorithm produces solutions that validate the conjecture for this graph class. These contributions assert the importance of modular decomposition in algorithms for graph classes with "few P4's" and broaden the pullback technique to variations of classical coloring problems / Doutorado / Ciência da Computação / Doutor em Ciência da Computação