Alexander A. Razborov (2007) developed the theory of flag algebras to compute the minimum asymptotic density of triangles in a graph as a function of its edge density. The theory of flag algebras, however, can be used to study the asymptotic density of several combinatorial objects. In this dissertation, we present two original results obtained in the theory of tournaments through application of flag algebra proof techniques. The first result concerns minimization of the asymptotic density of transitive tournaments in a sequence of tournaments, which we prove to occur if and only if the sequence is quasi-random. As a byproduct, we also obtain new quasi-random characterizations and several other flag algebra elements whose density is minimized if and only if the sequence is quasi-random. The second result concerns a class of equivalent properties of a sequence of tournaments that we call quasi-carousel properties and that, in a similar fashion as quasi-random properties, force the sequence to converge to a specific limit homomorphism. Several quasi-carousel properties, when compared to quasi-random properties, suggest that quasi-random sequences and quasi-carousel sequences are the furthest possible from each other within the class of almost balanced sequences. / Alexander A. Razborov (2007) desenvolveu a teoria de álgebras de flags para calcular a densidade assintótica mínima de triângulos em um grafo em função de sua densidade de arestas. A teoria das álgebras de flags, contudo, pode ser usada para estudar densidades assintóticas de diversos objetos combinatórios. Nesta dissertação, apresentamos dois resultados originais obtidos na teoria de torneios através de técnicas de demonstração de álgebras de flags. O primeiro resultado compreende a minimização da densidade assintótica de torneios transitivos em uma sequência de torneios, a qual provamos ocorrer se e somente se a sequência é quase aleatória. Como subprodutos, obtemos também novas caracterizações de quase aleatoriedade e diversos outros elementos da álgebra de flags cuja densidade é minimizada se e somente se a sequência é quase aleatória. O segundo resultado compreende uma classe de propriedades equivalentes sobre uma sequência de torneios que chamamos de propriedades quase carrossel e que, de uma forma similar às propriedades quase aleatórias, forçam que a sequência convirja para um homomorfismo limite específico. Várias propriedades quase carrossel, quando comparadas às propriedades quase aleatórias, sugerem que sequências quase aleatórias e sequências quase carrossel estão o mais distantes possível umas das outras na classe de sequências quase balanceadas.

Uma almost disjoint family é uma coleção infinita de subconjuntos infinitos de números naturais tal que a interseção de quaisquer dois de seus elementos distintos é finita. Almost disjoint families podem ser utilizadas para construir um espaço topológico associado chamado de Psi-espaços, também conhecido como espaços de Mrówka. As propriedades topológicas deste espaço topológico dependem das propriedades combinatórias da família que o deu origem, e estes espaços podem ser utilizados para responder perguntas sobre topologia geral, muitas vezes não inicialmente relacionadas com almost disjoint families ou seus respectivos espaços de Mrówka. Neste documento, exploramos diversas construções envolvendo estes objetos utilizando combinatória infinita e princípios combinatórios como diamante, Axioma de Martin e técnicas como Forcing e tratamos de problemas envolvendo compactificações de Stone-Cech, espaços sequenciais, a propriedade de Lindelöf em espaços de funções, hiperespaços de Vietoris, dentre outros. O primeiro capítulo contém diversos pré-requisitos necessários para a leitura desta dissertação a fim de torná-la o mais autocontida possível. O segundo capítulo introduz as almost disjoint families e seus Psi-espaços associados, provando diversas propriedades importantes. Os demais capítulos são independentes entre si e tratam de problemas de Topologia Geral que podem ser solucionados com estes conceitos, ou de problemas que derivam destes conceitos. / An almost disjoint family is an infinite collection of infinite subsets of natural numbers such that the intersection of any two of its elements is finite. Almost disjoint families may be used to construct an associated topological space called psi space, also know as Mrówka space. The topological properties of this topological space depends on the combinatorical properties of the family that originated it, and these spaces may be used to answer questions in general topology, many times initially unrelated to almost disjoint families or to their Mrówka spaces. In this document, we explore several constructions involving these objects by using infinitary combinatorics and combinatorical principles like diamond, Martin\'s Axiom, forcing techniques and we treat abour problems regardins Stone-Cech compactifications, sequencial spaces, the property of Lindelöf on spaces of functions, hyperspaces of Vietoris, among others. The first chapter contains several pre requirements that are neccessary to read this dissertation in order to make it as self contained as possible. The second chapter introduces almost disjoint families and their associated Psi spaces, proving several important properties. The following chapters are independent from each other and treat about problems on General Topology that may be solved by using these concepts, or about problems that arises from these concepts.

O presente estudo discorre sobre o uso de atividades lúdicas como alternativa no processo de ensino-aprendizagem de Matemática, em destaque, um jogo de cartas como atividade de revisão no ensino de Análise Combinatória e Probabilidade. Atividades como jogos, desafios e outros são fundamentais para que o discente possa aprender de forma efetiva e satisfatória alguns conteúdos de Matemática, uma vez que o gosto por essa disciplina não é unânime entre os discentes. Atividades com jogos é uma importante ferramenta para motivar e auxiliar no estudo desta matéria. Objetivando esclarecer a influência desse jogo matemático no desenvolvimento do discente durante o processo de ensino-aprendizagem, neste estudo utilizamos um jogo de cartas na Escola Estadual Hercília Carvalho da Silva, localizada no Município de Gurupi – TO. Esse trabalho relata a aplicação de um jogo envolvendo cartas que foi aplicado no 2o ano do ensino médio, em um período de 2 meses, como uma forma de demonstrar a potencialidade da atividade lúdica enquanto metodologia inovadora das ações pedagógicas, buscando aulas mais diversificadas para conduzir os discentes envolvidos neste grupo a uma aprendizagem significativa nos conteúdos de Análise Combinatória e Probabilidade. Posteriormente foi aplicado um questionário ao grupo de discentes, este com 11 questões de múltipla escolha, a atividade (questionário) fora realizada no dia 14 de março de 2017, durante a aula de Matemática. Pelos dados coletados, fora possível verificar que a aplicação do jogo de cartas facilita o entendimento dos discentes em referência às matérias de Análise Combinatória e Probabilidade, o que não seria integralmente possível apenas com a exposição teórica e listas de exercícios. A pesquisa, quanto aos procedimentos, delineia como uma de campo e levantamento de dados. Quanto aos objetivos, teve como base o estudo descritivo e exploratório, focalizando em identificar a percepção que o discente possui acerca do conteúdo de Análise Combinatória e Probabilidade por meio de um jogo de cartas como atividade para revisar, aprofundar ou motivar o estudo destes conteúdos. / The present study discusses the use of play activities as a facilitator in the teachinglearning process of Mathematics, in particular, a game of cards as a review activity in the teaching of Combinatorial Analysis and Probability. Activities such as games, challenges and others are fundamental so that the student can learn effectively and satisfactorily some contents of Mathematics, since the taste for this discipline is not unanimous for the students. For this, the use of games activities is an important tool to motivate and assist in the study of this matter. In order to clarify the influence of this mathematical game on the student’s development during the teaching-learning process, in this study we used a game of cards at the Hercília Carvalho da Silva State School, located in the Municipality of Gurupi-TO. This paper reports on the application of a game involving letters that was applied in the second year of high school in a period of two months as a way of demonstrating the potential of playful activity as an innovative methodology of pedagogical actions, seeking more diversified classes to conduct The students involved in this group to a significant learning in the contents of Combinatorial Analysis and Probability. Later, a questionnaire was applied to the group of students, with eleven multiple choice questions, activity (research - questionnaire) was performed on March 14, 2017, during the Mathematics class. From the collected data, it was possible to verify that the application of the card game facilitates the understanding of the students in reference to the Matters of Combinatorial Analysis and Probability, which would not be entirely possible only with theoretical exposition and lists of exercises. The research, regarding the procedures, delineates as a field and data collection. Regarding the objectives, it was based on the descriptive and exploratory study, focusing on identifying the perception that the student has about the content of Combinatorial Analysis and Probability through a game of cards as an activity to review, deepen or motivate the study of these contents.

O problema de roteamento do ônibus escolar (PROE), é um importante problema de ordem prática, estudado em otimização combinatória. É formulado através de um conjunto de paradas, frotas de ônibus, escolas e garagem, onde a partir destes conjuntos, busca-se criar rotas otimizadas visando a redução do custo operacional do serviço. Este trabalho apresenta duas grandes contribuições para a melhoria da solução do PROE, sendo elas, o desenvolvimento de um algoritmo baseado na metaheurística GRASP + 2-Opt, para a geração de rotas otimizadas, e um sistema de apoio a decisão para o PROE, com a utilização de funções do Google Maps v3, para proporcionar uma visualização ágil da atual situação do problema para o administrador do sistema, isto, através do uso de marcadores de localizações para paradas de ônibus, escolas e garagem. O sistema foi testado de duas formas. A primeira, com a utilização de instâncias de referência da literatura e a segunda com uma simulação de um ambiente do mundo real. Os resultados são comparados com os principais trabalho da literatura do problema, assim conseguindo gerar soluções com uma redução significativa na quantidade de ônibus utilizados, bem como no tempo de processamento para a geração das rotas. / The school bus routing problem (SBRP) is an important practical problem, studied in combinatorial optimization. It is formulated through a set of stops, bus fleets, schools and garage, where from these sets, we seek to create optimized routes in order to reduce the operating cost of the service. This work presents two great contributions to the improvement of SBRP solution, are the following, the development of an algorithm based on GRASP + 2-Opt, for generating optimal routes and a system decision support for the SBRP, with the use of Google Maps v3 functions, to provide a agile view of the current situation of the problem to the system administrator, through the use of marker locations for bus stops, schools and garage. The system was tested in two ways. First, with the use of benchmark instances the literature and the second with a simulation of a real-world environment. The results are compared with the main work problem literature, thus achieving generate solutions with a significant reduction in the number of buses used and the computational time for generating the route.

This essay presents the construction of a two-steps approach using Weapon-Targeting Assignment (WTA) problem mathematical modeling and Analytical Hierarchy Process (AHP) addressing two phases of the the targeting cycle, concerning both targeting and weaponeering activities on the context of a small Joint Force Air Component, in order to support timely, feasible, and conflict-consistent decision-making on weapon-target assignments. It starts clarifying the motivation for this work, related to personal operational activities. It is assumed that this past experience allowed the perception of staff difficulties which are presented as effects whose causes led to scoping this essay into constructing a suitable approach for using WTA models and AHP for supporting Command and Control processes. The relevant concepts of Command and Control are introduced, and it follows with nsiderations about WTA and targeting on related work, as well as about AHP being suitable to support the addressed problem. At this point the asset-target evaluation and tradeoff assessment are assumed as risks and benefits of the possible alternatives. The WTA formulation is made to include doctrinal and restrain criteria to approximate the provided solutions to the needs of the decision-makers, pointing out to the advantage of defining few alternatives from the large combinatorial realm, which simplifies the use of AHP. This work also describes a case for the proposed approach which clarifies the concepts presenting their practical usage. The discussion of this case leads finally to the conclusions of the approach suitability and to suggested ideas for field evaluation.

Esta dissertação estuda o problema da programação de operações em sistemas job shop de manufatura onde itens com estruturas de materiais são produzidos a partir de componentes fabricados e montados. Tais sistemas são denominados assembly shops. O caso geral do problema de programação de operações em sistemas job shop, no qual não existem restrições quanto ao número de operações a serem programadas nem quanto ao número de máquinas a serem alocadas, é considerado, até o presente momento, intratável do ponto de vista computacional devido à explosão combinatória inerente ao processo de programação, independente da escolha do critério de desempenho. Isto significa dizer que não existe nenhum método eficiente de programação que resolva globalmente instâncias de porte real do problema dentro de um tempo computacional considerado satisfatório. Devido a este fato, nas últimas três décadas, diversos métodos aproximados e heurísticos foram propostos e avaliados para o problema. Nesta pesquisa, é proposto e avaliado um novo método heurístico de programação. Fundamentado na pressuposição de que a melhoria na sincronização de operações de montagem em sistemas assembly shop leva ao melhor atendimento de datas de entrega de pedidos, o método implementa duas abordagens de programação: uma abordagem backward que satisfaz completamente as datas de entrega e outra forward que satisfaz completamente a restrição de capacidade de máquina. Ambas trabalham iterativamente dentro de dois modelos de simulação do sistema de produção um determinístico e outro probabilístico na busca pela melhoria da sincronização das operações e no atendimento das datas de entrega. Os resultados experimentais demonstraram que o desempenho do novo método foi em média melhor que os dos métodos não iterativos (regras) avaliados e tão bom quanto o desempenho do melhor método não iterativo (regra) testado. / This dissertation studies the problem of scheduling operations in manufacturing job shop environments where items with bill of materials are made of many fabricated and assembled components. Such systems are known as assembly shops. The general job shop scheduling problem, which no restrictions exist neither for the number of operations to be scheduled nor for the number of machines to be allocated, is considered at the present date intractable from the computational point of view, whatever the performance criterion used, due to the combinatorial explosion inherent to the scheduling process. It means that there is not an efficient computational method that solves globally real size instances of the problem within a satisfactory period of time. Due to this fact, in the last three decades several approximated and heuristic methods were created and evaluated for the problem. This research proposes and evaluate a new heuristic method which is based on the assumption that the improvement in operations synchronization at the assembly stations brings forth better achievement of due dates. The method implements two scheduling approaches: a backward approach satisfying due date completely and a forward approach satisfying capacity restriction completely. The two approaches work iteratively within two different simulation models of the production system one deterministic e other probabilistic in searching for operations synchronization improvement and due date achievement. The experimental results have shown the new method was better than the single-pass methods (rules) on average and as good as the better single-pass method (rule) tested.

O problema de corte consiste no corte de objetos maiores para produção de peças menores, de modo que uma certa função objetivo seja otimizada, por exemplo, a perda seja minimizada. O problema de empacotamento pode também ser visto como um problema de corte, onde as peças menores são arranjadas dentro dos objetos. Uma abordagem em grafo E/OU para a resolução de problemas de corte e empacotamento foi proposta inicialmente por Morabito (1989) para problemas de corte bidimensionais e, mais tarde, estendida para problemas tridimensionais (Morabito, 1992). Nesta abordagem foi utilizada uma técnica de busca híbrida, onde se combinou a busca em profundidade primeiro com limite de profundidade e a busca hill-climbing, utilizando-se heurísticas baseadas nos limitantes superiores e inferiores. Experiências computacionais mostraram a viabilidade de uso na prática desta abordagem. Mais tarde, Arenales (1993) generalizou esta a abordagem em grafo E/OU mostrando como diferentes problemas de corte poderiam ser resolvidos, independentemente da dimensão, formas dos objetos e itens, baseado em simples hipóteses, sem realizar, entretanto, estudos computacionais. O presente trabalho tem por objetivo estender a abordagem em grafo E/OU para tratar outros casos não analisados pelos trabalhos anteriores, tais como situações envolvendo diferentes processos de corte, bem como a implementação computacional de métodos baseados na abordagem em grafo E/OU, mostrando, assim, a versatilidade da abordagem para tratar diversas situações práticas de problemas de corte e sua viabilidade computacional. / The cutting problem consists of cutting larger objects in order to produce smaller pieces, in such a way as to optimizing a given objective function, for example, minimizing the waste. The packing problem can also be seen as a cutting problem, where the position that each smaller piece is arranged inside of the objects can be seen as the place it was cut from. An AND/OR-graph approach to solve cutting and packing problems was initially proposed by Morabito (1989) for two-dimensional cutting problem and, later, extended to threedimensional problems (Morabito, 1992). That approach uses a hybrid search, which combines depth-first search under depth bound and hill-climbing strategy. Heuristics were devised based on upper and lower bounds. Computational experiences demonstrated its practical feasibility. The AND/OR-graph approach was later generalized by Arenales (1993) based on simple hypothesis. He showed that different cutting problems Gould be solved using the AND/ORgraph approach, independently of the dimension and shapes. The main objective of this thesis is the practical extension of the AND/OR-graph approach to handle other cases not considered by previous works. It was considered different cutting processes, as well as the analysis of computational implementation, showing how can it be adapted to many classes of practical cutting and packing problems.

Made available in DSpace on 2016-04-27T16:57:36Z (GMT). No. of bitstreams: 1 Carlos Alberto de Miranda Pinheiro.pdf: 3726604 bytes, checksum: 7f0acb671f10ca6a3f9af822c2232603 (MD5) Previous issue date: 2015-03-17 / This paper presents the development of a research, which proposed to investigate the knowledge of Combinatorial Analysis studied in the Brazilian schools during 1895 and 2009. This research articulates inside a project called Educação Estatística e Educação Financeira na Escola Básica (Statistical Education and Financial Education in Basic School), linked to the research group PEA-MAT. We analysed some didactic aspects and mathematicians present in seven textbooks used in Brazilian schools during that time, we also had a bibliographical and documental study in presuppositions of content analysis. We wanted to answer the following investigation question:what characteristics of knowledge insertion of Combinatorial Analysis are identified in textbooks during 1895 and 2009? The first phase of content analysis consisted in collecting and studying texts that would inform us what textbooks presented the knowledge of Combinatorial Analysis and some aspects of historical moments of these books, since the foundation of the Pedro II School. With this, we identified that the program of 1895 was the one with more insertion of textbooks and new school contents, before the main educational reforms occurred in the first decades of the XX century. We also tried to identify on the website of the Programa Nacional do Livro Didático (PNLD-Ensino Médio) (National Program of Textbooks-High School) the Mathematic book more used in Belémdo Pará schools, in the first phase of the program, 2004-2009. The second phase of content analysis was the material exploration. In this phase we analysed based on the Anthropological Theory of Didactic, specifically about the praxeological organizations not only mathematical but also didactic, together with the notion of didactic models proposed by Josep Gáscon. Among the results observed, we highlight that while in the first books the focus was only on presentation of formulas deduction, some years later, the task of calculating the values from those formulas was introduced, modifying the approach from theoretical to technical or classic. We can also observe the change in the techniques to calculate the Arrange and the Permutation in the book produced based on the Movement of Modern Mathematics and in a more recent book, approved by the PNLD-Ensino Médio. The tasks and the techniques related to the calculation of numbers of simple combinations will not undergo transformations as time goes by. That is, the praxeological organization identified in the block task/technique/technology/theory changed from a theoretical to a technical approach during the whole period studied / Este trabalho apresenta o desenvolvimento de uma pesquisa que se propôs a investigar os saberes da Análise Combinatória estudada nas escolas brasileiras, no período entre 1895 e 2009. Esta pesquisa articula-se no interior do projeto Educação Estatística e Educação Financeira na Escola Básica , vinculado ao grupo de pesquisa PEA-MAT. Analisamos alguns aspectos didáticos e matemáticos presentes em sete livros didáticos que circularam nas escolas brasileiras, no período em questão, realizando um estudo bibliográfico e documental fundamentado em pressupostos da análise de conteúdo. Buscamos responder à seguinte questão de investigação: que características de inserção dos saberes da Análise Combinatória nos livros didáticos podem ser identificadas no período 1895-2009? A primeira fase da análise de conteúdo consistiu em reunir e estudar textos que nos informassem quais livros escolares apresentavam os saberes da Análise Combinatória e alguns aspectos do momento histórico desses livros, desde a fundação do Colégio Pedro II. Com isso, identificamos que o programa de 1895 foi o que teve a maior inserção de livros didáticos e de novos conteúdos escolares, antes das principais reformas educacionais ocorridas nas primeiras décadas do século XX. Também procuramos identificar no site do Programa Nacional do Livro Didático (PNLD-Ensino Médio) o livro de Matemática mais utilizado nas escolas de Belém do Pará, na primeira fase de implantação desse programa, 2004-2009. A segunda fase da análise de conteúdo foi a exploração do material. Nesta fase foi realizada uma análise à luz da Teoria Antropológica do Didático, especificamente sobre as organizações praxeológica tanto matemáticas como didáticas, juntamente com a noção de modelos didáticos, proposta por JosepGáscon. Entre os resultados observados, destacamos que, enquanto nos primeiros livros o enfoque era apenas a apresentação da dedução das fórmulas, ao longo do tempo foi inserida a tarefa de calcular os valores a partir dessas fórmulas, passando, assim, de uma abordagem puramente teoricista para uma abordagem tecnicista ou clássica. Observa-se, também, uma mudança nas técnicas para calcular o Arranjo e a Permutação no livro produzido à luz das ideias do Movimento de Matemática Moderna e no livro mais recente, aprovado no PNLD-Ensino Médio. As tarefas e as técnicas, relativas ao cálculo do número de combinações simples, não sofreram transformações, ao longo do tempo. Ou seja, a organização praxeológica identificada no bloco tarefa/técnica/tecnologia/teoria passou de uma abordagem teoricista para uma abordagem tecnicista ou clássica ao longo de todo o período estudado

Submitted by Filipe dos Santos (fsantos@pucsp.br) on 2017-10-20T14:04:27Z No. of bitstreams: 1 Simone de Oliveira Andrade Silva.pdf: 2491360 bytes, checksum: 076e3d9c3f47be0c573b1d2a44f767da (MD5) / Made available in DSpace on 2017-10-20T14:04:27Z (GMT). No. of bitstreams: 1 Simone de Oliveira Andrade Silva.pdf: 2491360 bytes, checksum: 076e3d9c3f47be0c573b1d2a44f767da (MD5) Previous issue date: 2017-09-15 / Conselho Nacional de Pesquisa e Desenvolvimento Científico e Tecnológico - CNPq / The aim was to identify possible relationship between logical reasoning and mathematical reasoning in children between 9 and 10 years old. Twenty-six children were recruited from an elementary school. They were distributed in two different groups: high and low performance in arithmetic mathematics. An instrument was applied to collecting data. It was composed of five set of problems: two to assess mathematical reasoning and three to assess logical reasoning. Three descriptions for analyses: participants performance outcomes; categorization of participants explanation about their reasoning to solving those problems and; instrument. The results evidenced strong correlation between logical reasoning and mathematical reasoning. The categorization of participants explanation indicated strong incorrect control by presence/absence of number in the mathematics problems and strong incorrect control by statement in problems that involve logic. The instrument was useful to register and analyze difficulties of the participants in solving the items. It is suggested insert qualitative analysis in the teacher assessment to understand student performance. It is advised to add to elementary school education and to teacher training the teaching of logic / O objetivo dessa pesquisa foi de identificar as possíveis relações entre o desempenho em problemas que envolvem raciocínio lógico e raciocínio matemático (de aritmética) em crianças entre 9 e 10 anos. O campo da pesquisa foi uma escola municipal de ensino fundamental de São Paulo, alunos do 5.º ano do ciclo I. Os 26 participantes foram distribuídos em dois grupos (fortes e fracos, com relação ao seu desempenho em matemática – aritmética). Para a coleta de dados, aplicou-se um instrumento composto de cinco conjuntos de problemas (dois avaliaram o raciocínio matemático e três avaliaram o raciocínio lógico). A análise dos dados contou com três etapas: análise quantitativa dos resultados do desempenho dos participantes; a análise e categorização das justificativas dadas pelas ao inquérito e; análise do instrumento. Os resultados sugerem que há correlação entre o raciocínio lógico (sentenças verbais – lógica não formal) e o raciocínio matemático (atividades de aritmética). A categorização das justificativas indicou forte controle incorreto da presença/ausência de número nos problemas matemáticos, forte controle incorreto do enunciado nos problemas que envolvem lógica. A análise do instrumento indicou que, apesar de alguns ajustes necessários, ele serviu para registrar e analisar dificuldades dos participantes na solução dos itens. Diante dos resultados, indica-se que a análise qualitativa seja inserida na avaliação que os professores realizam sobre o desempenho dos alunos em matemática. Recomenda-se, ainda, que o estudo de lógica verbal não formal seja inserido nos currículos da educação básica e na formação inicial de professores

Nesta dissertação estudamos --- do ponto de vista algorítmico --- o seguinte problema, conhecido como problema da partição conexa balanceada. Dado um grafo conexo G com pesos atribuídos a seus vértices, e um inteiro q >= 2, encontrar uma partição dos vértices de G em q classes, de forma que cada classe da partição induza um grafo conexo e que, ao considerar as somas dos pesos dos vértices de cada classe, a menor das somas seja o maior possível. Em outras palavras, o objetivo é encontrar q classes cujos pesos sejam tão balanceados quanto possível. Sabe-se que este problema é NP-difícil. Mencionamos alguns resultados sobre complexidade computacional e algoritmos que são conhecidos para este problema. Apresentamos algumas heurísticas que desenvolvemos, todas elas baseadas no uso do algoritmo polinomial para árvores, devido a Perl e Schach, que apresentamos com detalhe. Implementamos quatro heurísticas e um algoritmo de 3/4-aproximação conhecido para o caso q=2. Exibimos os resultados obtidos com os vários testes computacionais conduzidos com instâncias aleatórias, com grafos de diferentes pesos e densidades. Os resultados computacionais indicam que o desempenho dessas heurísticas --- todas elas polinomiais --- é bem satisfatório. No caso especial em que q=2, observamos que a heurística mais onerosa sistematicamente produziu soluções melhores ou iguais às do algoritmo de aproximação / In this dissertation we study algorithmic aspects of the following problem, known as the balanced connected partition. Given a connected graph G with weights defined on its vertices, and an integer q >= 2, find a partition of the vertices of G into q classes such that each class induces a connected graph, and furthermore, when we consider the sum of the weights of the vertices in each class, the smallest sum is as large as possible. In other words, the q classes must have weights that are as balanced as possible. This problem is known to be NP-hard. We mention some computational complexity and algorithmic results that are known for this problem. We present some heuristics that we designed, all of them based on the use of the polynomial algorithm for trees, due to Perl and Schach, which we show in detail. We implemented four heuristics and a 3/4-approximation algorithm that is known for q=2. We run tests on many random instances, of graphs with different weights and densities. The computational results indicate that the performance of these heuristics --- all of polynomial time complexity --- are very satisfactory. For q=2, we observed that the most expensive heuristic produced solutions with values which are systematically better or equal to those produced by the approximation algorithm.