Conselho Nacional de Desenvolvimento CientÃfico e TecnolÃgico / Os problemas de coloraÃÃo estÃo entre os mais estudados dentro da Teoria dos Grafos devido a sua grande importÃncia teÃrica e prÃtica. O problema da L(2,1)-coloraÃÃo, por exemplo, pode ser aplicado na atribuiÃÃo de frequÃncias de rÃdio a torres de transmissÃo visando a diminuiÃÃo de interferÃncias nas transmissÃes. No entanto a maior parte das coloraÃÃes de Grafos à de difÃcil resoluÃÃo(NP-DifÃceis). Nesta dissertaÃÃo, estudamos os problemas de L(2,1)-coloraÃÃo, coloraÃÃo harmÃnica e M-partiÃÃo. Tendo em vista que os problemas de coloraÃÃo abordados nesta dissertaÃÃo sÃo todos NP-difÃceis, decidimos estudar as restriÃÃes destes problemas a (q,q-4)-grafos , com q fixo. As soluÃÃes utilizam a decomposiÃÃo primeval destes grafos. Ressaltamos ainda que esta classe contÃm os cografos e os grafos P4-esparsos. Os algoritmos encontrados desta maneira sÃo chamados de Fixed Parameter Tractable(FPT), pois sÃo polinomiais quando consideramos um determinado parÃmetro como um valor fixo. AlÃm da obtenÃÃo de algoritmos para diversos problemas de coloraÃÃo restritos aos (q,q-4)-grafos, com q fixo, tambÃm avaliamos a Conjectura de Griggs-Yeh com relaÃÃo aos grafos P_4-Esparsos e P_4-Laden. / The coloring problems are among the most studied in the graph theory due to its great theoretical and practical importance. The L(2;1)-labeling problem, for instance, can be applied to the frequency assignment of transmission towers in order to decrease interference in transmissions. However most of the graph coloring problems are difficult to solve (NP-hard). In this thesis, we study the L(2;1)-coloring, the harmonious coloring and M-partition of graphs. Considering that the coloring problems addressed in this thesis are all NP-hard, we decided to study the restrictions of these problems to (q;q􀀀4)-graphs, with q fixed. The solutions use the Primeval decomposition of these graphs. We also emphasize that this class contains the cographs and P4-sparse graphs. The algorithms found in this way are called Fixed parameter tractable (FPT), because they run on polynomial time if we consider a certain parameter as a fixed value. Besides obtaining algorithms for several coloring problems restricted to (q;q􀀀4)-graphs, with q fixed, we also evaluated Conjecture of Griggs-Yeh graphs with respect to P4-Sparse and P4-Laden graphs.

O crescimento de cursos a distância oferecidos através da Web tem promovido uma grande reflexão sobre como acompanhar a evolução do aluno através deste curso. Em um curso presencial o docente possui meios mais seguros e concretos de observar e gerenciar o processo de aprendizagem já que os participantes estão em contato físico constante. Além disto, normalmente em um curso a distância, o aluno faz seu horário de estudo o que resulta num esforço ainda maior por parte do docente para acompanhar os alunos, pois terá que analisar momentos diferentes do curso ao mesmo tempo. A escolha de métodos para acompanhar a evolução do estudante em um curso on-line é sempre muito difícil de ser realizada e deve ser adequada as necessidades específicas do contexto estudado. Este trabalho apresenta além de conceitos pedagógicos relacionados a avaliação da aprendizagem presencial ambientes de gerenciamento de cursos a distância através da Web, sendo estes os alicerces das propostas realizadas nesta dissertação. As alternativas apresentadas, dentro de um ambiente interativo e através de testes objetivos, para realização de uma avaliação formativa tem como principal objetivo acompanhar o desenvolvimento do aluno no processo de aprendizagem. Como resultado da aplicação da metodologia para a construção de testes objetivos obteve-se uma ferramenta denominada AvaliaOnline, cuja finalidade é criar e aplicar questões do tipo múltipla-escolha em problemas que possuem valores numéricos e fórmulas ou algoritmos relacionados a sua resolução. A ferramenta permite que os valores numéricos que constituem o enunciado de uma questão sejam modificados toda vez que a mesma é apresentada, através do sorteio aleatório destes valores que serão utilizados para resolução do problema. Ou seja, a resposta correta da questão é gerada no momento da exibição da mesma. Além disto, é possível realizar uma dependência entre as questões que constituem o teste, construíndo uma árvore de questões onde o docente verifica o “caminho" percorrido pelo aluno durante o teste, dando subsídios para um acompanhamento mais detalhado sobre a resolução do estudante. Finalizando este trabalho, são apresentados exemplos práticos da utilização das ferramentas interativas para acompanhamento do aluno e da criação e aplicação de um teste desenvolvido através da ferramenta AvaliaOnline. / The increase in the number of distance courses in the Web has caused much reflection on how to track the student’s evolution through this course. In a live course it is possible for the teacher to observe and manage the learning process through safer and more concrete ways, once the participants are in constant physical contact. In addition, in a distance course the student usually determines how many hours he must study as well as when he will be studying. This will demand a bigger effort on the part of the teacher to track students once he may have to analyse different moments of the course at the same time. The choice of methods to track the stucent’s evolution in an on-line course is always very difficult to be made and it must be suitable to the specific needs of the studied context. This work presents pedagogical concepts related to tradicional learning evaluation as well as distance course managing environments through the Web, having these as the foundations of the proposals made in this dissertation. The alternatives presented, in an interactive environment and through objective tests, in order to have a formative evaluation, have as their main goal to track the development of the student in the learning process. As a result of the application of methodology for the construction of objective tests, a tool named AvaliaOnline was obtained, whose aim is to create and apply multiple-choice type questions to problems that have numerical values and formulas or algorithms related to their resolution. The tool allows the numerical values in the description of a question to be modified every time it is presented, through random sorting out of these values, which will be used for the resolution of the problem, that is, the correct answer of the question is produced at the moment of its exhibition. Besides, it is possible to establish dependence among the test questions, building a tree of questions where the teacher verifies the “path" followed by the student during the test, providing support for more detailed tracking on the resolution of the student. At the end of this work, practical examples are presented on the use of interactive tools to track the student and on the creation and application of a test developed through the tool AvaliaOnline. The experiments made show the potencial of such alternatives once they are used in a suitable context and under teacher tracking with.

O crescimento de cursos a distância oferecidos através da Web tem promovido uma grande reflexão sobre como acompanhar a evolução do aluno através deste curso. Em um curso presencial o docente possui meios mais seguros e concretos de observar e gerenciar o processo de aprendizagem já que os participantes estão em contato físico constante. Além disto, normalmente em um curso a distância, o aluno faz seu horário de estudo o que resulta num esforço ainda maior por parte do docente para acompanhar os alunos, pois terá que analisar momentos diferentes do curso ao mesmo tempo. A escolha de métodos para acompanhar a evolução do estudante em um curso on-line é sempre muito difícil de ser realizada e deve ser adequada as necessidades específicas do contexto estudado. Este trabalho apresenta além de conceitos pedagógicos relacionados a avaliação da aprendizagem presencial ambientes de gerenciamento de cursos a distância através da Web, sendo estes os alicerces das propostas realizadas nesta dissertação. As alternativas apresentadas, dentro de um ambiente interativo e através de testes objetivos, para realização de uma avaliação formativa tem como principal objetivo acompanhar o desenvolvimento do aluno no processo de aprendizagem. Como resultado da aplicação da metodologia para a construção de testes objetivos obteve-se uma ferramenta denominada AvaliaOnline, cuja finalidade é criar e aplicar questões do tipo múltipla-escolha em problemas que possuem valores numéricos e fórmulas ou algoritmos relacionados a sua resolução. A ferramenta permite que os valores numéricos que constituem o enunciado de uma questão sejam modificados toda vez que a mesma é apresentada, através do sorteio aleatório destes valores que serão utilizados para resolução do problema. Ou seja, a resposta correta da questão é gerada no momento da exibição da mesma. Além disto, é possível realizar uma dependência entre as questões que constituem o teste, construíndo uma árvore de questões onde o docente verifica o “caminho” percorrido pelo aluno durante o teste, dando subsídios para um acompanhamento mais detalhado sobre a resolução do estudante. Finalizando este trabalho, são apresentados exemplos práticos da utilização das ferramentas interativas para acompanhamento do aluno e da criação e aplicação de um teste desenvolvido através da ferramenta AvaliaOnline. / The increase in the number of distance courses in the Web has caused much reflection on how to track the student’s evolution through this course. In a live course it is possible for the teacher to observe and manage the learning process through safer and more concrete ways, once the participants are in constant physical contact. In addition, in a distance course the student usually determines how many hours he must study as well as when he will be studying. This will demand a bigger effort on the part of the teacher to track students once he may have to analyse different moments of the course at the same time. The choice of methods to track the stucent’s evolution in an on-line course is always very difficult to be made and it must be suitable to the specific needs of the studied context. This work presents pedagogical concepts related to tradicional learning evaluation as well as distance course managing environments through the Web, having these as the foundations of the proposals made in this dissertation. The alternatives presented, in an interactive environment and through objective tests, in order to have a formative evaluation, have as their main goal to track the development of the student in the learning process. As a result of the application of methodology for the construction of objective tests, a tool named AvaliaOnline was obtained, whose aim is to create and apply multiple-choice type questions to problems that have numerical values and formulas or algorithms related to their resolution. The tool allows the numerical values in the description of a question to be modified every time it is presented, through random sorting out of these values, which will be used for the resolution of the problem, that is, the correct answer of the question is produced at the moment of its exhibition. Besides, it is possible to establish dependence among the test questions, building a tree of questions where the teacher verifies the “path” followed by the student during the test, providing support for more detailed tracking on the resolution of the student. At the end of this work, practical examples are presented on the use of interactive tools to track the student and on the creation and application of a test developed through the tool AvaliaOnline. The experiments made show the potencial of such alternatives once they are used in a suitable context and under teacher tracking with.

[pt] A teoria de Morse relaciona a topologia de um espaço aos elementos críticos de uma função escalar definida nele. Isso vale tanto para a teoria clássica quanto para a versão discreta proposta por Forman em 1995. Essas teorias de Morse permitem caracterizar a topologia do espaço a partir de funções definidas nele, mas também permite estudar funções a partir de construções tipológicas derivadas dela, como por exemplo o complexo de Morse-Smale. Apesar da teoria de Morse discreta se aplicar para complexos celulares gerais de forma inteiramente combinatória, o que torna a teoria particularmente bem adaptada para o computador, as funções usadas na teoria não são amostragens de funções contínuas, mas casamentos especiais no grafo que codifica as adjacências no complexo celular, chamadas de casamentos de Morse. Quando usar essa teoria para estudar um espaço topológico, procura- se casamentos de Morse ótimos, i.e. com o menor número possível de elementos críticos, para obter uma informação topológica do complexo sem redundância. Na primeira parte desta tese, investiga-se a complexidade parametrizada de encontrar esses casamentos de Morse ótimos. Por um lado, prova-se que o problema ERASABILITY, um problema fortemente relacionado à encontrar casamentos de Morse ótimos, é W [P ]-completo. Por outro lado, um algoritmo é proposto para calcular casamentos de Morse ótimos em triangulações de 3-variedades, que é FPT no parâmetro do tree- width de seu grafo dual. Quando usar a teoria de Morse discreta para estudar uma função escalar definida no espaço, procura-se casamentos de Morse que capturam a informação geométrica dessa função. Na segunda parte é proposto uma construção de casamentos de Morse baseada em casamentos estáveis. As garantias teóricas sobre a relação desses casamentos com a geometria são elaboradas a partir de provas surpreendentemente simples que aproveitam da caracterização local do casamento estável. A construção e as suas garantias funcionam em qualquer dimensão. Finalmente, resultados mais fortes são obtidos quando a função for suave discreta, uma noção definida nesta tese. / [en] Morse theory relates the topology of a space to the critical elements of a scalar function defined on it. This applies in both the classical theory and a discrete version of it defined by Forman in 1995. Those Morse theories permit to characterize a topological space from functions defined on it, but also to study functions based on topological constructions it implies, such as the Morse-Smale complex. While discrete Morse theory applies on general cell complexes in an entirely combinatorial manner, which makes it suitable for computation, the functions it considers are not sampling of continuous functions, but special matchings in the graph encoding the cell complex adjacencies, called Morse matchings. When using this theory to study a topological space, one looks for optimal Morse matchings, i.e. one with the smallest number of critical elements, to get highly succinct topological information about the complex. The first part of this thesis investigates the parameterized complexity of finding such optimal Morse matching. On the one hand the Erasability problem, a closely related problem to finding optimal Morse matchings, is proven to be W[P]-complete. On the other hand, an algorithm is proposed for computing optimal Morse matchings on triangulations of 3-manifolds which is fixed parameter tractable in the tree-width of its dual graph. When using discrete Morse theory to study a scalar function defined on the space, one looks for a Morse matching that captures the geometric information of that function. The second part of this thesis introduces a construction of Morse matchings based on stable matchings. The theoretical guarantees about the relation of such matchings to the geometry are established through surprisingly simple proofs that benefits from the local characterization of the stable matching. The construction and its guarantees work in any dimension. Finally stronger results are obtained if the function is discrete smooth on the complex, a notion defined in this thesis.