Informe de Seminario para optar al grado de Licenciado en Lengua y Literatura Hispánica mención Literatura / Pretendemos introducirnos a una escritura que posee un valor incalculable, y que sin embargo, ha carecido de la relevancia que merece en el contexto de la literatura chilena e hispanoamericana. Eduardo Anguita se ha mantenido como un nombre en la reserva y la indeterminación crítica a pesar de la particularidad con que son tratados temas y formas en su poesía; y la claridad con la que son expuestas sus reflexiones en ensayos y notas. Respecto a esto, cabe aclarar una cuestión de suma importancia. La escritura de Anguita se ha visto sometida a través de los años a una paradójica y cruel dualidad: irradia una tremenda admiración en los entendidos, pero también un silencio crítico atípicamente desidioso, que se diría casi inentendible para una obra tan rica en temáticas y perspectivas. En este sentido, la gran mayoría de los estudios existentes sólo han reparado en temas específicos o lecturas de alguno de los más renombrados poemas del autor, sino en breves reseñas o en la incorporación del autor a tales o cuales generaciones y grupos literarios. Por supuesto, no se trata negar el valor de estos estudios, sino más bien, de hacer notar que se ha obviado significativamente la estrecha relación que existe entre la obra poética de Anguita y las reflexiones que él mismo formuló para la poesía. De hecho, podríamos aseverar a través de la lectura de su obra, que Anguita es un sujeto sumamente apegado a sus preceptos morales, y que tanto sus poemas como sus ideas en torno a la poesía se desarrollan en este margen. Por esto, desde nuestro punto de vista, ignorar estas relaciones existentes entre poesía y reflexiones poéticas, y de éstas con los preceptos morales del autor de Venus en el pudridero, ha dificultado aún más los acercamientos críticos a la escritura de este autor. Por todo lo anterior, un estudio como éste postula que al incorporar las reflexiones poéticas de Anguita a una lectura analítica de un poema específico, se podrá proceder con mayor precisión en el proyecto poético del autor, determinando los alcances de los temas en el contexto específico del texto poético estudiado. Esto, por supuesto, siempre a la luz que otorga el contexto en el que se desenvuelve el autor; que digamos, en este caso, estará directamente relacionado con la moralidad de Anguita, que ya hemos mencionado antes y será desarrollada pertinentemente a través del estudio.

Neste trabalho iremos apresentar uma releitura de um resultado clássico da topologia, na visão da topologia algébrica e em sua notação atual. A demonstração deste, apresentada por Cauchy (1813), é comentada de maneira crítica em Lima (1985a) e para esta apresentação destacaremos as definições, teoremas e entes básicos para o seu entendimento. / In this work we will present a rereading of a classic topology result, in the view of the algebraic topology in its current notation. The proof of this, presented by Cauchy (1813), is critically commented on Lima (1985a) for which we will present the definitions, theorems, basic entities for their understanding.

Made available in DSpace on 2016-06-02T20:28:31Z (GMT). No. of bitstreams: 1 DissCS.pdf: 762215 bytes, checksum: d3e016bba7e01e919bb3bc4e78b15d5d (MD5) Previous issue date: 2006-02-24 / Financiadora de Estudos e Projetos / In this work, we study the relation between Milnor's number and the Newton's number of a formal series. The former is always greater than or equal to the latter and equality occurs whan the formal series f has non-degenerate newtonian principal part at the origin. / Neste trabalho, estudamos a relação que existe entre o número de Milnor de uma série formal com o número de Newton. O número de Milnor de uma série formal é sempre maior ou igual ao número de Newton e a igualdade entre os números é obtida sempre que a série formal f possui parte principal Newton não-degenerada na origem.

This dissertation presents an educational software which explores Virtual Reality techniques (VR) through the development of virtual educational environments. 3D Geometry has been taken as a case study. The objective of this work is the extension of the cut for convex and non-convex polyhedron. The virtual environment and the interaction techniques have been developed using the VRML (Virtual Reality Modeling Language) and JavaScript languages. After making the system available to potential users, they were able to do some experiments and confirmed that the techniques proposed are satisfactory and helpful in the learning process and in the visualization of non-convex polyhedron. / Esta dissertação apresenta um software educacional que explora técnicas de Realidade Virtual (RV) através do desenvolvimento de ambientes virtuais educacionais. Utiliza-se a Geometria Espacial como estudo de caso. O objetivo deste trabalho é a extensão do corte para poliedros convexos e não-convexos. O ambiente virtual e as técnicas de interação propostas foram desenvolvidas utilizando-se a linguagem VRML (Virtual Reality Modeling Language) e JavaScript. Após disponibilizar o sistema para potenciais usuários, estes puderam realizar alguns experimentos e identificaram que as técnicas propostas auxiliam, de forma satisfatória, no processo de aprendizado da visualização de poliedros não-convexos, graças ao uso das técnicas de RV propostas. / Mestre em Ciências

Neste trabalho iremos apresentar uma releitura de um resultado clássico da topologia, na visão da topologia algébrica e em sua notação atual. A demonstração deste, apresentada por Cauchy (1813), é comentada de maneira crítica em Lima (1985a) e para esta apresentação destacaremos as definições, teoremas e entes básicos para o seu entendimento. / In this work we will present a rereading of a classic topology result, in the view of the algebraic topology in its current notation. The proof of this, presented by Cauchy (1813), is critically commented on Lima (1985a) for which we will present the definitions, theorems, basic entities for their understanding.

O foco central desta tese é o desenvolvimento de algoritmos para o problema de recoloração convexa de caminhos. Neste problema, é dado um caminho cujos vértices estão coloridos arbitrariamente, e o objetivo é recolorir o menor número possível de vértices de modo a obter uma coloração convexa. Dizemos que uma coloração de um grafo é convexa se, para cada cor, o subgrafo induzido pelos vértices dessa cor é conexo. Sabe-se que este problema é NP-difícil. Associamos a este problema um poliedro, e estudamos sua estrutura facial, com vistas ao desenvolvimento de um algoritmo. Mostramos várias inequações válidas para este poliedro, e provamos que várias delas definem facetas. Apresentamos um algoritmo de programação dinâmica que resolve em tempo polinomial o problema da separação para uma classe grande de inequações que definem facetas. Implementamos um algoritmo branch-and-cut baseado nesses resultados, e realizamos testes computacionais com instâncias geradas aleatoriamente. Apresentamos adicionalmente uma heurística baseada numa formulação linear que obtivemos. Estudamos também um caso especial deste problema, no qual as instâncias consistem em caminhos coloridos, onde cada cor ocorre no máximo duas vezes. Apresentamos um algoritmo de 3/2-aproximação para este caso, que é também NP-difícil. Para o caso geral, é conhecido na literatura um algoritmo de 2-aproximação. / The focus of this thesis is the design of algorithms for the convex recoloring problem on paths. In this problem, the instance consists of a path whose vertices are arbitrarily colored, and the objective is to recolor the least number of vertices so as to obtain a convex coloring.Acoloring of a graph is convex if, for each color, the subgraph induced by the vertices of this color is connected. This problem is known to be NP-hard. We associate a polyhedron to this problem and investigate its facial structure. We show various classes of valid inequalities for this polyhedron and prove that many of them define facets.We present a polynomial-time dynamic programming algorithm that solves, in polynomial time, the separation problem for a large class of facet-defining inequalities.We report on the computational experiments with a branch-and-cut algorithm that we propose for the problem. Additionally, we present a heuristic that is based on a linear formulation for the problem. We also study a special case of this problem, restricted to instances consisting of colored paths in which each color occurs at most twice. For this case, which is also NP-hard, we present a 3/2-approximation algorithm. For the general case, it is known a 2-approximation algorithm.

Submitted by Erika Demachki (erikademachki@gmail.com) on 2014-08-29T20:47:14Z No. of bitstreams: 2 Poliedros_E_Teorema_de_Euler.pdf: 4810573 bytes, checksum: f1f57ad45cfd7dc575fe3c3e963b24c6 (MD5) license_rdf: 23148 bytes, checksum: 9da0b6dfac957114c6a7714714b86306 (MD5) / Made available in DSpace on 2014-08-29T20:47:14Z (GMT). No. of bitstreams: 2 Poliedros_E_Teorema_de_Euler.pdf: 4810573 bytes, checksum: f1f57ad45cfd7dc575fe3c3e963b24c6 (MD5) license_rdf: 23148 bytes, checksum: 9da0b6dfac957114c6a7714714b86306 (MD5) Previous issue date: 2014-03-21 / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior - CAPES / This work aims is to demonstrate the Euler's Theorem for polyhedra, given by the equation V 􀀀 A + F = 2, where V; A and F are the numbers of vertices, edges and faces, respectively, the polyhedron. A historical survey of the main characters who contributed to the theme was elaborated. De nitions and properties of polygons and polyhedra were given. The statements were constructed in three distinct ways. The rst by Cauchy, commented by Professor Elon Lages Lima. This statement is valid for any polyhedron homeomorphic to a sphere and has the path planning of the polyhedron withdrawing one of its faces. The second statement was prepared by the professor Zoroastro Azambuja Filho, valid for any convex polyhedron, and its path projection of the polyhedron on a plane and comparison of the internal angles of polygons with projection angles of the polygon faces. The third statements was presented by Legendre, also valid for any convex polyhedron, and its path in the projection of a spherical polyhedron surface. We use the Girard's Formula, the sum of the interior angles of a spherical triangle, to complete the demonstration. This work also suggests methods of applying the proof of Euler's Theorem in the classroom for high school students, and resolution of vestibular exercises involving the subject. / Este trabalho tem por objetivo a demonstra c~ao do Teorema de Euler para poliedros, dado pela equa ção V 􀀀 A + F = 2, onde V; A e F são os n úmeros de v értices, arestas e faces, respectivamente, do poliedro. Foi elaborada uma pesquisa hist orica dos principais personagens que contribuiram para o tema. Foram dadas de ni ções e propriedades de pol ígonos e poliedros. As demonstra ções foram constru ídas em três caminhos distintos. A primeira por Cauchy, comentada pelo professor Elon Lages Lima. Esta demonstra ção é v álida para qualquer poliedro homeomorfo a uma esfera e tem como caminho a plani fica ção do poliedro retirando-se uma de suas faces. A segunda demonstra c~ao foi elaborada pelo professor Zoroastro Azambuja Filho, v álida para qualquer poliedro convexo e tem como caminho a proje ção do poliedro num plano e a compara c~ao dos ângulos internos dos pol ígonos da proje ção com os ângulos dos pol gonos das faces. A terceira demonstra c~ao foi apresentada por Legendre, tamb ém v álida para qualquer poliedro convexo e tem como caminho a projeção do poliedro em uma superf ície esf érica. Utiliza-se a F ormula de Girard, da soma dos ângulos internos de um tri^angulo esf érico, para concluir a demonstra ção. Este trabalho tamb ém sugere metodologias de aplica ção da demonstração do Teorema de Euler em sala de aula, para alunos do Ensino M édio, e resolu ção de exercí cios de vestibulares envolvendo o tema.

O foco central desta tese é o desenvolvimento de algoritmos para o problema de recoloração convexa de caminhos. Neste problema, é dado um caminho cujos vértices estão coloridos arbitrariamente, e o objetivo é recolorir o menor número possível de vértices de modo a obter uma coloração convexa. Dizemos que uma coloração de um grafo é convexa se, para cada cor, o subgrafo induzido pelos vértices dessa cor é conexo. Sabe-se que este problema é NP-difícil. Associamos a este problema um poliedro, e estudamos sua estrutura facial, com vistas ao desenvolvimento de um algoritmo. Mostramos várias inequações válidas para este poliedro, e provamos que várias delas definem facetas. Apresentamos um algoritmo de programação dinâmica que resolve em tempo polinomial o problema da separação para uma classe grande de inequações que definem facetas. Implementamos um algoritmo branch-and-cut baseado nesses resultados, e realizamos testes computacionais com instâncias geradas aleatoriamente. Apresentamos adicionalmente uma heurística baseada numa formulação linear que obtivemos. Estudamos também um caso especial deste problema, no qual as instâncias consistem em caminhos coloridos, onde cada cor ocorre no máximo duas vezes. Apresentamos um algoritmo de 3/2-aproximação para este caso, que é também NP-difícil. Para o caso geral, é conhecido na literatura um algoritmo de 2-aproximação. / The focus of this thesis is the design of algorithms for the convex recoloring problem on paths. In this problem, the instance consists of a path whose vertices are arbitrarily colored, and the objective is to recolor the least number of vertices so as to obtain a convex coloring.Acoloring of a graph is convex if, for each color, the subgraph induced by the vertices of this color is connected. This problem is known to be NP-hard. We associate a polyhedron to this problem and investigate its facial structure. We show various classes of valid inequalities for this polyhedron and prove that many of them define facets.We present a polynomial-time dynamic programming algorithm that solves, in polynomial time, the separation problem for a large class of facet-defining inequalities.We report on the computational experiments with a branch-and-cut algorithm that we propose for the problem. Additionally, we present a heuristic that is based on a linear formulation for the problem. We also study a special case of this problem, restricted to instances consisting of colored paths in which each color occurs at most twice. For this case, which is also NP-hard, we present a 3/2-approximation algorithm. For the general case, it is known a 2-approximation algorithm.

Let G be a connected graph and k be a positive integer. A vertex subset D of G is a k-hop connected dominating set if the subgraph of G induced by D is connected, and for every vertex v in G, there is a vertex u in D such that the distance between v and u in G is at most k. We study the problem of finding a minimum k-hop connected dominating set of a graph (Mink-CDS). We prove that Mink-CDS is NP-hard on planar bipartite graphs of maximum degree 4. We also prove that Mink-CDS is APX-complete on bipartite graphs of maximum degree 4. We present inapproximability thresholds for Mink-CDS on bipar- tite and on (1, 2)-split graphs. Interestingly, one of these thresholds is a parameter of the input graph which is not a function of its number of vertices. We also discuss the complex- ity of computing this graph parameter. On the positive side, we show an approximation algorithm for Mink-CDS. When k = 1, we present two new approximation algorithms for the weighted version of the problem, one of them restricted to graphs with a poly- nomially bounded number of minimal separators. Finally, also for the weighted variant of the problem where k = 1, we discuss an integer linear programming formulation and conduct a polyhedral study of its associated polytope. / Seja G um grafo conexo e k um inteiro positivo. Um subconjunto D de vértices de G é um conjunto dominante conexo de k-saltos se o subgrafo de G induzido por D é conexo e se, para todo vértice v em G, existe um vértice u em D a uma distância não maior do que k de v. Estudamos neste trabalho o problema de se encontrar um conjunto dominante conexo de k-saltos com cardinalidade mínima (Mink-CDS). Provamos que Mink-CDS é NP-difícil em grafos planares bipartidos com grau máximo 4. Mostramos que Mink-CDS é APX-completo em grafos bipartidos com grau máximo 4. Apresentamos limiares de inaproximabilidade para Mink-CDS para grafos bipartidos e (1, 2)-split, sendo que um desses é expresso em função de um parâmetro independente da ordem do grafo. Também discutimos a complexidade computacional do problema de se computar tal parâmetro. No lado positivo, propomos um algoritmo de aproximação para Mink-CDS cuja razão de aproximação é melhor do que a que se conhecia para esse problema. Finalmente, quando k = 1, apresentamos dois novos algoritmos de aproximação para a versão do problema com pesos nos vértices, sendo que um deles restrito a classes de grafos com um número polinomial de separadores minimais. Além disso, discutimos uma formulação de programação linear inteira para essa versão do problema e provamos resultados poliédricos a respeito de algumas das desigualdades que constituem o politopo associado à formulação.

The vertex coloring problem is a classic problem in graph theory that asks for a partition of the vertex set into a minimum number of stable sets. This thesis presents our studies on three vertex (re)coloring problems on graphs and on a problem related to a long-standing conjecture on subdivision of digraphs. Firstly, we address the convex recoloring problem in which an arbitrarily colored graph G is given and one wishes to find a minimum weight recoloring such that each color class induces a connected subgraph of G. We show inapproximability results, introduce an integer linear programming (ILP) formulation that models the problem and present some computational experiments using a column generation approach. The k-fold coloring problem is a generalization of the classic vertex coloring problem and consists in covering the vertex set of a graph by a minimum number of stable sets in such a way that every vertex is covered by at least k (possibly identical) stable sets. We present an ILP formulation for this problem and show a detailed polyhedral study of the polytope associated with this formulation. The last coloring problem studied in this thesis is the proper orientation problem. It consists in orienting the edge set of a given graph so that adjacent vertices have different in-degrees and the maximum in-degree is minimized. Clearly, the in-degrees induce a partition of the vertex set into stable sets, that is, a coloring (in the conventional sense) of the vertices. Our contributions in this problem are on hardness and upper bounds for bipartite graphs. Finally, we study a problem related to a conjecture of Mader from the eighties on subdivision of digraphs. This conjecture states that, for every acyclic digraph H, there exists an integer f(H) such that every digraph with minimum out-degree at least f(H) contains a subdivision of H as a subdigraph. We show evidences for this conjecture by proving that it holds for some particular classes of acyclic digraphs. / O problema de coloração de grafos é um problema clássico em teoria dos grafos cujo objetivo é particionar o conjunto de vértices em um número mínimo de conjuntos estáveis. Nesta tese apresentamos nossas contribuições sobre três problemas de coloração de grafos e um problema relacionado a uma antiga conjectura sobre subdivisão de digrafos. Primeiramente, abordamos o problema de recoloração convexa no qual é dado um grafo arbitrariamente colorido G e deseja-se encontrar uma recoloração de peso mínimo tal que cada classe de cor induza um subgrafo conexo de G. Mostramos resultados sobre inaproximabilidade, introduzimos uma formulação linear inteira que modela esse problema, e apresentamos alguns resultados computacionais usando uma abordagem de geração de colunas. O problema de k-upla coloração é uma generalização do problema clássico de coloração de vértices e consiste em cobrir o conjunto de vértices de um grafo com uma quantidade mínima de conjuntos estáveis de tal forma que cada vértice seja coberto por pelo menos k conjuntos estáveis (possivelmente idênticos). Apresentamos uma formulação linear inteira para esse problema e fazemos um estudo detalhado do politopo associado a essa formulação. O último problema de coloração estudado nesta tese é o problema de orientação própria. Ele consiste em orientar o conjunto de arestas de um dado grafo de tal forma que vértices adjacentes possuam graus de entrada distintos e o maior grau de entrada seja minimizado. Claramente, os graus de entrada induzem uma partição do conjunto de vértices em conjuntos estáveis, ou seja, induzem uma coloração (no sentido convencional) dos vértices. Nossas contribuições nesse problema são em complexidade computacional e limitantes superiores para grafos bipartidos. Finalmente, estudamos um problema relacionado a uma conjectura de Mader, dos anos oitenta, sobre subdivisão de digrafos. Esta conjectura afirma que, para cada digrafo acíclico H, existe um inteiro f(H) tal que todo digrafo com grau mínimo de saída pelo menos f(H) contém uma subdivisão de H como subdigrafo. Damos evidências para essa conjectura mostrando que ela é válida para classes particulares de digrafos acíclicos.