Submitted by Caroline Xavier (caroline.xavier@pucrs.br) on 2017-06-26T14:49:22Z No. of bitstreams: 1 DIS_JONAS_PEREIRA_ANDRADE_PARCIAL.pdf: 141765 bytes, checksum: 99338991681873f9d3d7028d9e7cdfa9 (MD5) / Made available in DSpace on 2017-06-26T14:49:22Z (GMT). No. of bitstreams: 1 DIS_JONAS_PEREIRA_ANDRADE_PARCIAL.pdf: 141765 bytes, checksum: 99338991681873f9d3d7028d9e7cdfa9 (MD5) Previous issue date: 2017-01-19 / Coordena??o de Aperfei?oamento de Pessoal de N?vel Superior - CAPES / The aim of the study was to evaluate, in vitro, the fracture resistance of occlusal veneers, made by CAD/CAM, with Lava Ultimate, e.max CAD and Vita Enamic materials in thicknesses of 0.6 mm and 1.5 mm. Seventy third human sound molars were randomly divided into seven groups (n = 10) according to the variables material and thickness, with the sound teeth as control. The root of the teeth was embedded into a self-cured acrylic resin and the teeth were prepared to simulate advanced erosion of the occlusal surface. The occlusal veneers were made using CAD-CAM technology, being luted to the preparation with adhesive systems and resin cements. After storage in distilled water at 37 ?C for 24 h, the samples were submitted to mechanical cyclic loading (1 million cycles at 100 N load). Subsequently, the sound teeth and the samples with the occlusal veneers were submitted to the fracture resistance test in a universal testing machine with crosshead speed of 1 mm/min. The failures were classified as reparable and irreparable. According to two-way ANOVA, the interaction between material and thickness was significant (p=0.013). The highest fracture resistance was obtained for the e.max CAD in the thickness of 1.5 mm (4995 N), being statistically superior to the other groups (p <0.05). The lowest fracture resistance was obtained for Vita Enamic at 0.6 mm thickness (2973 N), not being significantly different from e.max CAD 0.6 mm (3067 N), Lava Ultimate 0.6 mm (3384 N), Vita Enamic 1.5 mm (3540 N) and Lava Ultimate 1.5 mm (3584 N) (p>0.05). According to one- way ANOVA, the fracture resistance of the sound teeth (3991 N) did not differ significantly from the teeth with occlusal veneers (p> 0.05). The failures were predominantly repairable, except for sound teeth and Lava Ultimate 1.5 mm. The Lava Ultimate, e.max CAD and Vita Enamic occlusal veneers, in the thicknesses of 0.6 mm and 1.5 mm, showed fracture resistance exceeding the maximum masticatory forces. / O objetivo do estudo foi avaliar, in vitro, a resist?ncia ? fratura de facetas oclusais, confeccionadas por CAD/CAM, com os materiais Lava Ultimate, e.max CAD e Vita Enamic nas espessuras de 0,6 mm e 1,5 mm. Setenta terceiros molares humanos h?gidos foram aleatoriamente divididos em sete grupos (n=10) de acordo com as vari?veis material e espessura, tendo os dentes h?gidos como controle. A raiz dos dentes foi inserida em resina acr?lica quimicamente ativada e os dentes receberam um preparo para simular eros?o avan?ada da superf?cie oclusal. As restaura??es oclusais foram confeccionadas por meio da tecnologia CAD-CAM, sendo cimentadas ao preparo com sistemas adesivos e cimentos resinosos. Ap?s armazenagem em ?gua destilada a 37 ?C por 24 h, as amostras foram submetidas ? ciclagem mec?nica (1 milh?o de ciclos com carga de 100 N). Na sequ?ncia, os dentes h?gidos e as amostras com as facetas oclusais foram submetidas ao ensaio de resist?ncia ? fratura em m?quina de ensaio universal com velocidade de 1 mm/min. As falhas foram classificadas em repar?veis e irrepar?veis. De acordo com ANOVA de duas vias, a intera??o entre material e espessura foi significativa (p=0,013). A maior resist?ncia ? fratura foi obtida para o e.max CAD na espessura de 1,5 mm (4995 N), sendo estatisticamente superior aos demais grupos (p<0,05). A menor resist?ncia ? fratura foi obtida para o Vita Enamic na espessura de 0,6 mm (2973 N), n?o diferindo estatisticamente do e.max CAD 0,6 mm (3067 N), Lava Ultimate 0,6 mm (3384 N), Vita Enamic 1,5 mm (3540 N) e Lava Ultimate 1,5 mm (3584 N) (p>0,05). De acordo com ANOVA de uma via, a resist?ncia ? fratura dos dentes h?gidos (3991 N) n?o diferiu estatisticamente dos dentes com facetas oclusais (p>0,05). As falhas foram predominantemente do tipo repar?vel, com exce??o dos dentes h?gidos e Lava Ultimate 1,5 mm. As facetas oclusais em Lava Ultimate, e.max CAD e Vita Enamic, nas espessuras de 0,6 mm e 1,5 mm, demonstraram resist?ncia ? fratura que excede as for?as mastigat?rias m?ximas.

O objetivo deste estudo foi avaliar a prevalência de lesões cervicais não cariosas (LCNC), além de observar possíveis fatores de risco relacionados ao seu desenvolvimento. Pacientes de ambos os gêneros e com idade a partir de 18 anos, da Clínica Integrada da Faculdade de Odontologia do Recife, foram examinados, totalizando 1110 dentes, onde se buscou a presença de LCNC, facetas de desgaste e prematuridades oclusais. Os pacientes também foram investigados quanto a presença de problemas gastrintestinais, hipersensibilidade dentinária, hábitos parafuncionais e a dieta utilizada. A presença de LCNC foi observada com auxílio de sonda periodontal posicionada paralela ao longo eixo do dente, e a severidade, medida pelo índice de desgaste dental (IDD) de Smith e Knight, utilizando a mesma sonda, porém, perpendicular ao longo eixo do dente. Posteriormente foi observada a presença de contatos prematuros em RC ou interferência nos movimentos de lateralidade e protrusão. A presença de LCNC foi encontrada em 72,5% dos indivíduos, com maior freqüência no primeiro pré-molar, seguido do segundo prémolar e primeiro molar. Foi observada relação entre LCNC e a presença de facetas de desgaste, de contatos prematuros e interferências. Nos dados referentes ao questionário, não foram encontradas diferenças significantes, entre os grupos com e sem lesão, quanto a idade, gênero, dieta, problemas gastrintestinais, hábito parafuncional ou hipersensibilidade dentinária. Concluiu-se que as LCNC estão associadas à facetas de desgaste e contatos oclusais parafuncionais, embora, novos estudos sejam necessários para esclarecer seu complexo desenvolvimento. / The aim of this study was to observe the prevalence of noncarious cervical lesions (NCL),and the risk factors involved in this development. Patients of both genders and over eighteen years old, were examined, with 1110 teeth where the presence of NCL, wear facets and oclusal prematuritiess were sought. The patients also given a questionnaire about age, gender, gastrointestinal problems, diet, dentin hipersensitivity and parafunctional habits. The NCL was detected by a periodontal probing located parallel to the long axis of the tooth, and its severity was evaluated by the Smith and Knight tooth wear index (TWI) by using the same periodontal probe, but perpendicular to the long axis. Later, the presence of premature contacts at centric relation (CR) or interference in lateral and protrusive movements was observed. NCL was found in 72,5% of the individuals, with greater frequency in the first premolars, followed by seconds premolars and then first molars. It was observed relationship between NCL and wear facets and between NCL and premature or interferents contacts. In the data gotten fron the questionnaire, no significant diference for age, gender, diet, gatrointestinals problems, parafunctional habits or dentin hipersensitiveness, between the groups with and without lesions. We conclude that NCL are associate with wear facet and parafunctional oclusal contacts, inspite of new studies must to be necessary to explain their complex development.

Tendo em vista a freqüente constatação clínica da reprodução protética inadequada da face vestibular dos dentes permanentes, o presente estudo teve como objetivo avaliar a reconstrução anatômica do perfil de emergência vestibular do canino superior esquerdo, após confecção, por técnica indireta, de faceta estética executada por três técnicos em prótese dentária. Para este fim, foram fornecidos a cada um dos profissionais quatro modelos obtidos a partir da moldagem de um de arco superior de um manequim odontológico. Cada modelo continha uma réplica do canino superior esquerdo com preparo protético para faceta estética, em forma de troquel removível, para que fossem confeccionadas as facetas em resina. Numa segunda etapa, cada profissional recebeu outros quatro modelos idênticos, porém acompanhados do dente artificial removido do manequim odontológico, que serviu de referência para a reconstrução do elemento dentário. Após a confecção destas outras facetas, todas foram cimentadas nos troquéis e suas faces vestibulares submetidas a traçados de perfil, em aparelho para medição tridimensional. Os traçados obtidos foram comparados ao traçado previamente realizado sobre a face vestibular do dente artificial, objetivando verificar se os técnicos reproduziram o perfil de emergência de forma fiel e se houve diferença entre as facetas confeccionadas com e sem o modelo anatômico de referência. Os dados obtidos foram estatisticamente analisados com o uso dos aplicativos Bioestat 2.0 e SPSS 11.0, por meio dos testes: 1) teste t; 2) ANOVA e teste t de student. Foi utilizado nível de significância de 5%. / In view of the frequent clinical evidence of inadequate prosthetic reproduction of the buccal face of permanent teeth, the present study aimed to evaluate the anatomical reconstruction of the buccal emergence profile of the left upper canine, after confection, for indirect technic, of aesthetic veneer restoration executed by three dental prosthetic technicians. For this, the professionals received four casts gotten from the molding of an odontologic dummy of superior arch. Each model contained a reply of the left upper canine prepared for receive an aesthetic veneer restoration, in form of removable die, for that were confectioned veneers in resin. In one second stage, each professional received others four models identicals, however followed of the artificial tooth removed of the odontologic dummy, that served of reference for the reconstruction of the dental element. After the confection of these others veneers, all were cemented in the dies and its buccal faces submitted the tracings of profile, in device for three-dimensional measurement. The gotten tracings were compared with the tracing previously carried on the buccal face of the artificial tooth, objectifying to verify if the technician they had reproduced the emergence profile of faithful form and if occurred difference between the veneers with and without the anatomical model of reference. The gotten data were submitted to the analysis statistics, using t test, ANOVA and t Student test. Level of significance of 5% was used.

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 Fabio Sobreira Campos da Costa (fabio.sobreira@ufpe.br) on 2016-06-13T13:02:47Z No. of bitstreams: 2 license_rdf: 1232 bytes, checksum: 66e71c371cc565284e70f40736c94386 (MD5) Dissertação Erica Andrade Borges.pdf: 4139502 bytes, checksum: c80b9b1a5c5ba294663e2fd676cb075a (MD5) / Made available in DSpace on 2016-06-13T13:02:47Z (GMT). No. of bitstreams: 2 license_rdf: 1232 bytes, checksum: 66e71c371cc565284e70f40736c94386 (MD5) Dissertação Erica Andrade Borges.pdf: 4139502 bytes, checksum: c80b9b1a5c5ba294663e2fd676cb075a (MD5) Previous issue date: 1201-02-11 / CAPEs / O objetivo deste estudo foi validar o uso da técnica da tomografia por coerência óptica através de experimento in vitro para avaliar a cimentação e a linha de união laminado-cimento-dente antes e depois da termociclagem, visando a aplicação clínica deste instrumento. Além de comparar diferentes modalidades de materiais e protocolos de cimentação. A técnica da tomografia por coerência óptica (TCO) é um método não invasivo, quantitativo e qualitativo, e foi utilizado para avaliação da qualidade póscimentação do laminado, minimizando possíveis erros, e proporcionando acompanhamento clínico sem exposição a radiação ou qualquer procedimento invasivo. Foram feitas imagens em 2D e 3D dos laminados e das superfícies dentais antes e depois da cimentação e do processo de ciclagem térmica. Os laminados (20) foram cimentados na superfície de esmalte bovino de acordo com uma distribuição aleatória em 4 grupos (n=05): FA – cimento resinoso dual com fotoativação prévia do adesivo; FC – cimento resinoso dual sem fotoativação prévia do adesivo; AF - cimento resinoso autocondicionante dual com fotoativação; AQ - cimento resinoso autocondicionante dual com polimerização química. Os laminados foram fabricados em porcelana modificada por dissilicato de lítio, na espessura de 0,5 mm. As análises foram feitas através de imagens 2D e 3D com o TCO. Os resultados mostraram claramente a presença de bolhas com dimensões típicas que variaram de 146 μm a 1427 μm, além de falhas como a presença de gap e até a desadaptação do laminado. Parte dessas falhas, já estavam presentes imediatamente após o processo de cimentação e após a ciclagem térmica mantiveram-se estáveis ou foram acentuadas. Os resultados indicam que um acompanhamento periódico de pacientes que utilizam laminados cerâmicos é de fundamental importância para garantia da manutenção da qualidade do procedimento, bem como evitar problemas na saúde bucal. Propomos então a técnica de TCO como padrão para este procedimento. / The aim of this study was to validate the use of optical coherence tomography (OCT) through in vitro experiment to evaluate the cementing and the union line of lumineer-cement-tooth before and after the thermal cycling. In addition to comparing different types of materials and cementation protocols. The technique of optical coherence tomography (OCT) is a noninvasive, quantitative and qualitative method, and was used to evaluate the postcementation quality of the lamina, minimizing potential errors, and providing clinical follow-up without exposure to radiation or any invasive procedure. Were made in both 2D and 3D imaging of tooth surfaces and the laminate before and after the cementing and the thermocycling process. 20 specimens of lumineers-teetth were prepared in bovine teeth and randomly allocated in 4 experimental groups (n=5) with two different cementation techniques and two different types of cementing agent: FA - dual resin cement with prior photo activation of the adhesive; FC - dual resin cement without curing the adhesive; AF - self-etching resin cement with photoactivation; AQ - selfetching resin cement with chemical polymerization. The lumineers were made of lithium disilicate and obtained using a vacuum injection technique, thickness of 0.5 mm. The analysis was performed by using 2D and 3D OCT images, obtained before and after the thermal cycling. The results showed the presence of bubbles with typical size ranging from 146 μm to 1427 μm, and faults as the presence of gap and laminate mismatch. Some of these faults were already present immediately after the process of cementing and after thermal cycling remained stable or were marked. The results indicate that regular monitoring of patients using lumineers is of fundamental importance for ensuring the maintenance of the quality of the procedure and how to avoid problems in oral health. Then we propose the OCT technical default for this in vivo to follow-up.

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.

A análise dos sistemas de classificação do conhecimento na Filosofia e na Biblioteconomia sob um ponto de vista histórico-conceitual crítico com enfoque nos conceitos de classe, categoria e faceta foi desenvolvida a partir dos objetivos específicos de acompanhar e delinear a trajetória das classificações dos saberes (classes) e dos seres (categorias) à luz da Filosofia; averiguar as possíveis influências que as classificações filosóficas historicamente exerceram sobre as classificações bibliográficas tradicionais; e verificar de que modo os conceitos específicos de categoria, de classe e de faceta têm sido definidos no âmbito das classificações biblioteconômicas tradicionais. Trata-se de uma pesquisa do tipo exploratório-descritivo, embasada na literatura pertinente, oriunda de ambas as áreas do conhecimento em questão. A partir do levantamento bibliográfico construiu-se o referencial teórico, conduzindo à objetivação, análise, discussão e o aprofundamento do objeto. É possível afirmar que tanto os princípios das classificações filosóficas em relação aos saberes e em relação aos seres, quanto as próprias classificações que dividem os saberes e os seres, apresentam-se como construtos destinados a conhecer e disciplinar o conhecimento do ser e do saber. A influência das classificações filosóficas sobre as classificações bibliográficas reside no fato de que as classificações bibliográficas são adaptações das classificações do conhecimento ou das ciências. As bibliográficas, frequentemente, utilizam termos originários das filosóficas, ressignificando-os e transformando-os em ferramentas. Em síntese, pode-se afirmar que, a partir da Filosofia, absorvida em explicações teóricas, até a Biblioteconomia, preocupada com soluções instrumentais e aplicativas (pragmáticas), os esquemas de classificação bibliográfica propostos tem se beneficiado da aproximação dessas duas áreas de conhecimento. A revisão conceitual com respeito às noções de classe, categoria e faceta aponta, por parte dos estudiosos da Classificação, para a necessidade de um cuidado maior no desenho, no planejamento e na estruturação de sistemas de classificação, na modificação e especificação de tabelas de classificação e até de linguagens de indexação, com vista à sua adequação e relevância. As contribuições daí resultantes, delineadas numa perspectiva funcional-instrumental, poderão ajudar os profissionais a reconsiderar os seus sistemas de idéias e procedimentos em relação à construção e avaliação de linguagens de indexação e à classificação habitual de documentos. Caberá à Ciência da Informação avançar na fundamentação teórica do seu campo de aplicação, discutindo criticamente a sua base conceitual, atenta às práticas de uso em voga na Biblioteconomia e Documentação com relação a termos e conceitos. O estudo valida as hipóteses inicialmente levantadas, determinando que a consistência terminológica de termos como categoria, classe ou faceta contribui para aperfeiçoar a operacionalização do processamento do conhecimento em Ciência da Informação e que aos esquemas categoriais não cabe um valor neutro, uma vez que sempre favoreceram uma determinada concepção de mundo, em que pese a sua natureza objetivamente pragmática. Por fim, apresentam-se algumas perspectivas decorrentes da investigação, selecionando-se questões relevantes e de interesse para futuras pesquisas. / The analysis of knowledge classification systems in Philosophy and Librarianship by a critical historical-conceptual point of view with an approach in the concepts of class, category and facet was developed from specific objectives to accompany and outline the path of knowledge (classes) and beings (categories) classification in relation to Philosophy; to investigate the possible influences that the philosophical classification historically exerted on traditional bibliographical classifications; and to verify in which way the specific concept of category, class and facet have been defined in the ambit of traditional librarianship classifications. This research is of exploratory-descriptive type, based upon pertinent literature, resulting from both areas of knowledge in discussion. From the studied bibliographical material, a theoretical reference was built, leading to objectivation, analysis, discussion and a profound study of the object. Its possible to affirm that even the principles of philosophical classifications in relation to knowledge and beings, as well as the classifications that divide knowledge and beings, are presented as constructs, purposed to understand and to train the information of beings and knowledge. The influence of philosophical classifications on bibliographical classification is settled by bibliographical classifications, which are adaptations of knowledge or science. The bibliographical ones, frequently utilize terms originated from philosophical that are modified and transformed into tools. In synthesis, it may be stated that, from Philosophy, absorbed in theoretical explanations, even Librarianship, worried with instrumental and application (pragmatic) solutions, the proposed plans of bibliographical classifications have been beneficiated from the approximation of this two areas of knowledge. The conceptual review in relation to notions of class, category and facet needs a better attention in design, planning and in the structuring of classification systems, as pointed out by experts on Classification, in the modification and specification of classification tables and also indexation languages, aiming its adequacy and significance. The resulting contributions, outlined by a functional-instrumental perspective, would help professionals to reconsider their systems of ideas and procedures in relation to construction and evaluation of indexation languages and regular classification of documents. The information science will be responsible to develop theory fundamentation of its application field, discussing critically its conceptual basis, with attention to the practices in use by Librarianship and Documentation in relation to terms and concepts. The study validates the hypothesis initially described, determining that the terminological consistency of terms as category, class or facet contribute to improve the operacionalization of knowledge processing in Information Science and that to category schemes it doesnt fit a neuter value, since that always favored a certain conception of the world, in which predominates its pragmatic nature As result of the investigation, some perspectives are presented, selecting questions of extreme relevancy and interest for future researches.

Neste trabalho, estudamos o problema a recoloração convexa de grafos, denotado por RC. Dizemos que uma coloração dos vértices de um grafo G é convexa se, para cada cor tribuída d, os vértices de G com a cor d induzem um subgrafo conexo. No problema RC, é dado um grafo G e uma coloração de seus vértices, e o objetivo é recolorir o menor número possível de vértices de G tal que a coloração resultante seja convexa. A motivação para o estudo deste problema surgiu em contexto de árvores filogenéticas. Sabe-se que este problema é NP-difícil mesmo quando G é um caminho. Mostramos que o problema RC parametrizado pelo número de mudanças de cor é W[2]-difícil mesmo se a coloração inicial usa apenas duas cores. Além disso, provamos alguns resultados sobre a inaproximabilidade deste problema. Apresentamos uma formulação inteira para a versão com pesos do problema RC em grafos arbitrários, e então a especializamos para o caso de árvores. Estudamos a estrutura facial do politopo definido como a envoltória convexa dos pontos inteiros que satisfazem as restrições da formulação proposta, apresentamos várias classes de desigualdades que definem facetas e descrevemos os correspondentes algoritmos de separação. Implementamos um algoritmo branch-and-cut para o problema RC em árvores e mostramos os resultados computacionais obtidos com uma grande quantidade de instâncias que representam árvores filogenéticas reais. Os experimentos mostram que essa abordagem pode ser usada para resolver instâncias da ordem de 1500 vértices em 40 minutos, um desempenho muito superior ao alcançado por outros algoritmos propostos na literatura. / In this work we study the convex recoloring problem of graphs, denoted by CR. We say that a vertex coloring of a graph G is convex if, for each assigned color d, the vertices of G with color d induce a connected subgraph. In the CR problem, given a graph G and a coloring of its vertices, we want to find a recoloring that is convex and minimizes the number of recolored vertices. The motivation for investigating this problem has its roots in the study of phylogenetic trees. It is known that this problem is NP-hard even when G is a path. We show that the problem CR parameterized by the number of color changes is W[2]-hard even if the initial coloring uses only two colors. Moreover, we prove some inapproximation results for this problem. We also show an integer programming formulation for the weighted version of this problem on arbitrary graphs, and then specialize it for trees. We study the facial structure of the polytope defined as the convex hull of the integer points satisfying the restrictions of the proposed ILP formulation, present several classes of facet-defining inequalities and the corresponding separation algorithms. We also present a branch-and-cut algorithm that we have implemented for the special case of trees, and show the computational results obtained with a large number of instances. We considered instances which are real phylogenetic trees. The experiments show that this approach can be used to solve instances up to 1500 vertices in 40 minutes, comparing favorably to other approaches that have been proposed in the literature.

A análise dos sistemas de classificação do conhecimento na Filosofia e na Biblioteconomia sob um ponto de vista histórico-conceitual crítico com enfoque nos conceitos de classe, categoria e faceta foi desenvolvida a partir dos objetivos específicos de acompanhar e delinear a trajetória das classificações dos saberes (classes) e dos seres (categorias) à luz da Filosofia; averiguar as possíveis influências que as classificações filosóficas historicamente exerceram sobre as classificações bibliográficas tradicionais; e verificar de que modo os conceitos específicos de categoria, de classe e de faceta têm sido definidos no âmbito das classificações biblioteconômicas tradicionais. Trata-se de uma pesquisa do tipo exploratório-descritivo, embasada na literatura pertinente, oriunda de ambas as áreas do conhecimento em questão. A partir do levantamento bibliográfico construiu-se o referencial teórico, conduzindo à objetivação, análise, discussão e o aprofundamento do objeto. É possível afirmar que tanto os princípios das classificações filosóficas em relação aos saberes e em relação aos seres, quanto as próprias classificações que dividem os saberes e os seres, apresentam-se como construtos destinados a conhecer e disciplinar o conhecimento do ser e do saber. A influência das classificações filosóficas sobre as classificações bibliográficas reside no fato de que as classificações bibliográficas são adaptações das classificações do conhecimento ou das ciências. As bibliográficas, frequentemente, utilizam termos originários das filosóficas, ressignificando-os e transformando-os em ferramentas. Em síntese, pode-se afirmar que, a partir da Filosofia, absorvida em explicações teóricas, até a Biblioteconomia, preocupada com soluções instrumentais e aplicativas (pragmáticas), os esquemas de classificação bibliográfica propostos tem se beneficiado da aproximação dessas duas áreas de conhecimento. A revisão conceitual com respeito às noções de classe, categoria e faceta aponta, por parte dos estudiosos da Classificação, para a necessidade de um cuidado maior no desenho, no planejamento e na estruturação de sistemas de classificação, na modificação e especificação de tabelas de classificação e até de linguagens de indexação, com vista à sua adequação e relevância. As contribuições daí resultantes, delineadas numa perspectiva funcional-instrumental, poderão ajudar os profissionais a reconsiderar os seus sistemas de idéias e procedimentos em relação à construção e avaliação de linguagens de indexação e à classificação habitual de documentos. Caberá à Ciência da Informação avançar na fundamentação teórica do seu campo de aplicação, discutindo criticamente a sua base conceitual, atenta às práticas de uso em voga na Biblioteconomia e Documentação com relação a termos e conceitos. O estudo valida as hipóteses inicialmente levantadas, determinando que a consistência terminológica de termos como categoria, classe ou faceta contribui para aperfeiçoar a operacionalização do processamento do conhecimento em Ciência da Informação e que aos esquemas categoriais não cabe um valor neutro, uma vez que sempre favoreceram uma determinada concepção de mundo, em que pese a sua natureza objetivamente pragmática. Por fim, apresentam-se algumas perspectivas decorrentes da investigação, selecionando-se questões relevantes e de interesse para futuras pesquisas. / The analysis of knowledge classification systems in Philosophy and Librarianship by a critical historical-conceptual point of view with an approach in the concepts of class, category and facet was developed from specific objectives to accompany and outline the path of knowledge (classes) and beings (categories) classification in relation to Philosophy; to investigate the possible influences that the philosophical classification historically exerted on traditional bibliographical classifications; and to verify in which way the specific concept of category, class and facet have been defined in the ambit of traditional librarianship classifications. This research is of exploratory-descriptive type, based upon pertinent literature, resulting from both areas of knowledge in discussion. From the studied bibliographical material, a theoretical reference was built, leading to objectivation, analysis, discussion and a profound study of the object. Its possible to affirm that even the principles of philosophical classifications in relation to knowledge and beings, as well as the classifications that divide knowledge and beings, are presented as constructs, purposed to understand and to train the information of beings and knowledge. The influence of philosophical classifications on bibliographical classification is settled by bibliographical classifications, which are adaptations of knowledge or science. The bibliographical ones, frequently utilize terms originated from philosophical that are modified and transformed into tools. In synthesis, it may be stated that, from Philosophy, absorbed in theoretical explanations, even Librarianship, worried with instrumental and application (pragmatic) solutions, the proposed plans of bibliographical classifications have been beneficiated from the approximation of this two areas of knowledge. The conceptual review in relation to notions of class, category and facet needs a better attention in design, planning and in the structuring of classification systems, as pointed out by experts on Classification, in the modification and specification of classification tables and also indexation languages, aiming its adequacy and significance. The resulting contributions, outlined by a functional-instrumental perspective, would help professionals to reconsider their systems of ideas and procedures in relation to construction and evaluation of indexation languages and regular classification of documents. The information science will be responsible to develop theory fundamentation of its application field, discussing critically its conceptual basis, with attention to the practices in use by Librarianship and Documentation in relation to terms and concepts. The study validates the hypothesis initially described, determining that the terminological consistency of terms as category, class or facet contribute to improve the operacionalization of knowledge processing in Information Science and that to category schemes it doesnt fit a neuter value, since that always favored a certain conception of the world, in which predominates its pragmatic nature As result of the investigation, some perspectives are presented, selecting questions of extreme relevancy and interest for future researches.

Neste trabalho, estudamos o problema a recoloração convexa de grafos, denotado por RC. Dizemos que uma coloração dos vértices de um grafo G é convexa se, para cada cor tribuída d, os vértices de G com a cor d induzem um subgrafo conexo. No problema RC, é dado um grafo G e uma coloração de seus vértices, e o objetivo é recolorir o menor número possível de vértices de G tal que a coloração resultante seja convexa. A motivação para o estudo deste problema surgiu em contexto de árvores filogenéticas. Sabe-se que este problema é NP-difícil mesmo quando G é um caminho. Mostramos que o problema RC parametrizado pelo número de mudanças de cor é W[2]-difícil mesmo se a coloração inicial usa apenas duas cores. Além disso, provamos alguns resultados sobre a inaproximabilidade deste problema. Apresentamos uma formulação inteira para a versão com pesos do problema RC em grafos arbitrários, e então a especializamos para o caso de árvores. Estudamos a estrutura facial do politopo definido como a envoltória convexa dos pontos inteiros que satisfazem as restrições da formulação proposta, apresentamos várias classes de desigualdades que definem facetas e descrevemos os correspondentes algoritmos de separação. Implementamos um algoritmo branch-and-cut para o problema RC em árvores e mostramos os resultados computacionais obtidos com uma grande quantidade de instâncias que representam árvores filogenéticas reais. Os experimentos mostram que essa abordagem pode ser usada para resolver instâncias da ordem de 1500 vértices em 40 minutos, um desempenho muito superior ao alcançado por outros algoritmos propostos na literatura. / In this work we study the convex recoloring problem of graphs, denoted by CR. We say that a vertex coloring of a graph G is convex if, for each assigned color d, the vertices of G with color d induce a connected subgraph. In the CR problem, given a graph G and a coloring of its vertices, we want to find a recoloring that is convex and minimizes the number of recolored vertices. The motivation for investigating this problem has its roots in the study of phylogenetic trees. It is known that this problem is NP-hard even when G is a path. We show that the problem CR parameterized by the number of color changes is W[2]-hard even if the initial coloring uses only two colors. Moreover, we prove some inapproximation results for this problem. We also show an integer programming formulation for the weighted version of this problem on arbitrary graphs, and then specialize it for trees. We study the facial structure of the polytope defined as the convex hull of the integer points satisfying the restrictions of the proposed ILP formulation, present several classes of facet-defining inequalities and the corresponding separation algorithms. We also present a branch-and-cut algorithm that we have implemented for the special case of trees, and show the computational results obtained with a large number of instances. We considered instances which are real phylogenetic trees. The experiments show that this approach can be used to solve instances up to 1500 vertices in 40 minutes, comparing favorably to other approaches that have been proposed in the literature.