[pt] A análise de complexidade clássica para problemas NP-difíceis é geralmente orientada para cenários de pior caso, considerando apenas o comportamento assintótico. No entanto, existem algoritmos práticos com execução em um tempo razoável para muitos problemas clássicos. Além disso, há evidências que apontam para algoritmos polinomiais no modelo de árvore de decisão linear para resolver esses problemas, embora não muito explorados. Neste trabalho, exploramos esses resultados teóricos anteriores. Mostramos que a solução ótima para problemas combinatórios 0-1 pode ser encontrada reduzindo esses problemas para uma Busca por Vizinho Mais Próximo sobre o conjunto de vértices de Voronoi correspondentes. Utilizamos os hiperplanos que delimitam essas regiões para gerar sistematicamente uma árvore de decisão que repetidamente divide o espaço até que possa separar todas as soluções, garantindo uma resposta ótima. Fazemos experimentos para testar os limites de tamanho para os quais podemos construir essas árvores para os casos do 0-1 knapsack, weighted minimum cut e symmetric traveling salesman. Conseguimos encontrar as árvores desses problemas com tamanhos até 10, 5 e 6, respectivamente. Obtemos também as relações de adjacência completas para os esqueletos dos politopos do knapsack e do traveling salesman até os tamanhos 10 e 7. Nossa abordagem supera consistentemente o método de enumeração e os métodos baseline para o weighted minimum cut e symmetric traveling salesman, fornecendo soluções ótimas em microssegundos. / [en] Classical complexity analysis for NP-hard problems is usually oriented to worst-case scenarios, considering only the asymptotic behavior. However, there are practical algorithms running in a reasonable time for many classic problems. Furthermore, there is evidence pointing towards polynomial algorithms in the linear decision tree model to solve these problems, although not explored much. In this work, we explore previous theoretical results. We show that the optimal solution for 0-1 combinatorial problems can be found by reducing these problems into a Nearest Neighbor Search over the set of corresponding Voronoi vertices. We use the hyperplanes delimiting these regions to systematically generate a decision tree that repeatedly splits the space until it can separate all solutions, guaranteeing an optimal answer. We run experiments to test the size limits for which we can build these trees for the cases of the 0-1 knapsack, weighted minimum cut, and symmetric traveling salesman. We manage to find the trees of these problems with sizes up to 10, 5, and 6, respectively. We also obtain the complete adjacency relations for the skeletons of the knapsack and traveling salesman polytopes up to size 10 and 7. Our approach consistently outperforms the enumeration method and the baseline methods for the weighted minimum cut and symmetric traveling salesman, providing optimal solutions within microseconds.

O presente trabalho tem por objetivo divulgar e explorar as Provas sem Palavras no âmbito do Ensino Fundamental e Médio para, posteriormente, servir de possível material de consulta por parte de professores, na busca de melhores métodos de explicação sobre importantes assuntos desenvolvidos em sala. Dessa forma, imagina-se que a compreensão dos alunos através da visualização fortalecerá de maneira significativa a aquisição do conhecimento. Para tanto, são sugeridos diversos temas onde a visualização é desenvolvida e explicada, seja através de relato, seja através de demonstrações matemáticas. / The aim of the present work is to disseminate and explore the Proof Without Words in the scope of elementary and high school to be used later as a possible reference material for teachers in the search for better methods of explanation on important subjects developed in the classroom. In this way, it is imagined that students’ comprehension through visualization will significantly strengthen the acquisition of knowledge. In order to do so, several themes are suggested where the visualization is developed and explained, either through storytelling or through mathematical demonstrations.

Globular clusters are tracers of the formation and evolution of their host galaxies. Kinematics, chemical abundances, age and position of the clusters allows tracing interactions between Milky Way and surrounding galaxies and outlines their chemical enrichment history. In this thesis we analyse mid-resolution spectra of about 800 red giant stars in 51 Galactic globular clusters. It is the first time that [Fe/H] and [Mg/Fe] derived in a consistent way are published for such a huge sample of globular clusters, almost 1/3 of the total number of catalogued clusters. Our metallicities are showed to be more precise than previous works based on mid-resolution spectroscopy. A turnover at [Fe/H] ~ -1.0 is found in the plot [Fe/H] vs. [Mg/Fe] for bulge and halo, although bulge seems to have a more metal-rich turnover, i.e, bulge has more efficient formation than the halo. Comparing the abundances with age the timescale for SNIa to start to become important is 1Gyr. [Fe/H] vs. age corroborates the different star formation efficiency of bulge and halo while [Mg/Fe] does not follow that. Halo was formed in mini halos or dwarf galaxies, and two multiple population clusters had their origin analysed to check it. M 22 seems to have been formed in the Milky Way while NGC 5824 possibly was originated in a dwarf galaxy, although our results are inconclusive for NGC 5824. The Galactic bulge seems to have been formed fast i.e., probably the oldest globular cluster is there. In fact HP 1 has a bluer horizontal branch than expected for its metallicity and we interpret that as an age effect. We determine its distance using light curves of variable stars in order to constrain future age determinations via colour-magnitude diagram. Finally, we investigate interaction between Milky Way and its neighbour galaxy SMC. We find that some star clusters are being stripped out of the SMC main body, which is consistent with tidal stripping scenario for the interaction between the galaxies, instead of ram pressure that would only affect gas. / Aglomerados globulares são traçadores da formação e evolução de suas galáxias. Cinemática, abundâncias químicas, idades e posições dos aglomerados permitem traçar interações entre Via Láctea e galáxias vizinhas e suas histórias de enriquecimento químico. Nesta tese analisamos espectros de média resolução de mais de 800 estrelas gigantes vermelhas em 51 aglomerados globulares Galácticos. É a primeira vez que [Fe/H] and [Mg/Fe] determinados de modo consistente são publicados para uma amostra desse porte, ~1/3 dos objetos catalogados. Nossas metalicidades são mais precisas que trabalhos anteriores similares. Uma quebra em [Fe/H] ~ -1.0 é encontrada no gráfico [Fe/H] vs. [Mg/Fe] para o bojo e halo, embora bojo parece ter uma quebra em [Fe/H] maior, i.e, bojo tem formaçãao mais eficiente que o halo. Comparando abundâncias com idade, a escala de tempo para SNIa ficar importante é 1Gano. [Fe/H] vs. idade corrobora diferentes eficiências de formação do bojo e halo, mas [Mg/Fe] vs. idade não mostra isso. O halo foi formado em mini halos ou galáxias anãs, e dois aglomerados com dispersão em [Fe/H] tiveram suas origens analisadas. M 22 parece ter sido formado na Via Láctea e NGC 5824 possivelmente foi originado em uma galáxia anã, embora os resultados são inconclusivos para NGC 5824. O bojo parece ter sido formado rapidamente e deve possuir o aglomerado mais velho. De fato, HP 1 tem um ramo horizontal mais azul que o esperado para sua metalicidade e vemos isso como um efeito da idade. Determinamos sua distância usando curvas de luz de RR Lyrae de maneira a restringir futuras determinações de idade via diagrama cor-magnitude. Finalmente, investigamos a interação entre Via Láctea e sua galáxia vizinha SMC. Encontramos aglomerados sendo removidos do corpo central da SMC, consistente com cenário de remoção por força de maré para a interação entre as galáxias, em vez de ``ram pressure\'\' que afeta só gás.

Globular clusters are tracers of the formation and evolution of their host galaxies. Kinematics, chemical abundances, age and position of the clusters allows tracing interactions between Milky Way and surrounding galaxies and outlines their chemical enrichment history. In this thesis we analyse mid-resolution spectra of about 800 red giant stars in 51 Galactic globular clusters. It is the first time that [Fe/H] and [Mg/Fe] derived in a consistent way are published for such a huge sample of globular clusters, almost 1/3 of the total number of catalogued clusters. Our metallicities are showed to be more precise than previous works based on mid-resolution spectroscopy. A turnover at [Fe/H] ~ -1.0 is found in the plot [Fe/H] vs. [Mg/Fe] for bulge and halo, although bulge seems to have a more metal-rich turnover, i.e, bulge has more efficient formation than the halo. Comparing the abundances with age the timescale for SNIa to start to become important is 1Gyr. [Fe/H] vs. age corroborates the different star formation efficiency of bulge and halo while [Mg/Fe] does not follow that. Halo was formed in mini halos or dwarf galaxies, and two multiple population clusters had their origin analysed to check it. M 22 seems to have been formed in the Milky Way while NGC 5824 possibly was originated in a dwarf galaxy, although our results are inconclusive for NGC 5824. The Galactic bulge seems to have been formed fast i.e., probably the oldest globular cluster is there. In fact HP 1 has a bluer horizontal branch than expected for its metallicity and we interpret that as an age effect. We determine its distance using light curves of variable stars in order to constrain future age determinations via colour-magnitude diagram. Finally, we investigate interaction between Milky Way and its neighbour galaxy SMC. We find that some star clusters are being stripped out of the SMC main body, which is consistent with tidal stripping scenario for the interaction between the galaxies, instead of ram pressure that would only affect gas. / Aglomerados globulares são traçadores da formação e evolução de suas galáxias. Cinemática, abundâncias químicas, idades e posições dos aglomerados permitem traçar interações entre Via Láctea e galáxias vizinhas e suas histórias de enriquecimento químico. Nesta tese analisamos espectros de média resolução de mais de 800 estrelas gigantes vermelhas em 51 aglomerados globulares Galácticos. É a primeira vez que [Fe/H] and [Mg/Fe] determinados de modo consistente são publicados para uma amostra desse porte, ~1/3 dos objetos catalogados. Nossas metalicidades são mais precisas que trabalhos anteriores similares. Uma quebra em [Fe/H] ~ -1.0 é encontrada no gráfico [Fe/H] vs. [Mg/Fe] para o bojo e halo, embora bojo parece ter uma quebra em [Fe/H] maior, i.e, bojo tem formaçãao mais eficiente que o halo. Comparando abundâncias com idade, a escala de tempo para SNIa ficar importante é 1Gano. [Fe/H] vs. idade corrobora diferentes eficiências de formação do bojo e halo, mas [Mg/Fe] vs. idade não mostra isso. O halo foi formado em mini halos ou galáxias anãs, e dois aglomerados com dispersão em [Fe/H] tiveram suas origens analisadas. M 22 parece ter sido formado na Via Láctea e NGC 5824 possivelmente foi originado em uma galáxia anã, embora os resultados são inconclusivos para NGC 5824. O bojo parece ter sido formado rapidamente e deve possuir o aglomerado mais velho. De fato, HP 1 tem um ramo horizontal mais azul que o esperado para sua metalicidade e vemos isso como um efeito da idade. Determinamos sua distância usando curvas de luz de RR Lyrae de maneira a restringir futuras determinações de idade via diagrama cor-magnitude. Finalmente, investigamos a interação entre Via Láctea e sua galáxia vizinha SMC. Encontramos aglomerados sendo removidos do corpo central da SMC, consistente com cenário de remoção por força de maré para a interação entre as galáxias, em vez de ``ram pressure\'\' que afeta só gás.

[ES] La fabricación aditiva, de sus siglas en inglés AM (Additive Manufacturing) es un proceso que construye objetos sólidos tridimensionales mediante la superposicióon de materiales basados en un modelo de diseño asistido por ordenador. La AM está llamada a convertirse en la próxima revolución industrial, transformando el panorama del desarrollo y la producción. La AM ofrece numerosas ventajas, como posibilidades de diseño complejas y flexibles, la eliminación de procesos intermedios como el mecanizado, la independencia de los costes de producción del tamaño de los lotes, la reducción de los residuos de material, las estructuras ligeras, las reparaciones personalizadas de las máquinas y la capacidad de desarrollar nuevos materiales, entre otras ventajas. En las tecnologías de fabricación aditiva que emplean un rayo láser como fuente de energía, la materia prima inicial (en forma de polvo o cable) es fundida por la fuente de calor láser de forma controlada, capa a capa, hasta crear un componente con dimensiones finales o casi finales. Estas tecnologías implican someter el material impreso a un proceso térmico único, en el que el material se funde en un área muy específica y luego se enfría rápidamente a velocidades extremadamente altas de hasta 10^6 K/s. Por lo tanto, las microestructuras que surgen de los procesos de fabricación en AM difieren significativamente de las que se consiguen en los procesos tradicionales. Además, los materiales que se emplean principalmente en la AM no se han diseñado explícitamente para estas tecnologías. Las características específicas de los procesos de AM pueden utilizarse para lograr microestructuras y propiedades distintas en aceros que han sido adaptados para aprovechar las rápidas velocidades de enfriamiento y la historia térmica del proceso, entre otros factores. Por el momento, el número de calidades de acero comerciales disponibles en el mercado de la AM es limitado. Diversas industrias demandan nuevos grados de acero con menor densidad para disminuir el peso sin comprometer las propiedades mecánicas. Los aceros con alto contenido en manganeso se consideran materiales muy prometedores para aplicaciones estructurales debido a su excepcional combinación de resistencia y ductilidad, con una baja densidad. Sin embargo, a pesar de sus excepcionales propiedades, los aceros con alto contenido en manganeso se enfrentan a diversas limitaciones o retos durante las técnicas de procesado convencionales. Afortunadamente, la solidificación rápida puede resolver estos problemas. En este sentido, las tecnologías de AM basadas en láser proporcionan velocidades de enfriamiento rápidas, así como flexibilidad en términos de diseño geométrico. Los nuevos retos de estas tecnologías implicarán la microsegregación y el agrietamiento en caliente o hot cracking en inglés, que se producen durante la solidificación. Esta tesis está dedicada a explotar el método CALPHAD para realizar cálculos termodinámicos con el fin de diseñar varios aceros con alto contenido en manganeso que puedan prevenir eficazmente los problemas de solidificación rápida en AM. Las composiciones de acero diseñadas se produjeron en forma de polvo para AM mediante atomización con gas. Se analizaron los polvos para determinar su microestructura en relación con la química y la velocidad de enfriamiento. Ajustando adecuadamente los parámetros de impresión, estos polvos de acero con alto contenido en manganeso se imprimieron con éxito en AM, dando lugar a densidades relativas superiores al 99.9%. Se analizó la microestructura de estas muestras totalmente densas y se comparó con sus respectivos polvos, con el fin de identificar cualquier diferencia resultante de las variaciones en la velocidad de enfriamiento y los ciclos térmicos. Por último, tras definir el mejor conjunto de condiciones de impresión para cada composición de polvo, se produjeron varias muestras para evaluar las propiedades mecánicas. / [CA] La fabricació additiva, de les seues sigles en anglés AM (Additive Manufacturing) és un procés que construïx objectes sòlids tridimensionals mitjançant la superposició de materials basats en un model de disseny assistit per ordinador. L'AM està cridada a convertir-se en la pròxima revolució industrial, transformant el panorama del desenvolupament i la producció. L'AM oferix nombrosos avantatges, com a possibilitats de disseny complexes i flexibles, l'eliminació de processos intermedis com el mecanitzat, la independència dels costos de producció de la grandària dels lots, la reducció dels residus de material, les estructures lleugeres, les reparacions personalitzades de les màquines i la capacitat de desenvolupar nous materials, entre altres avantatges. En les tecnologies de fabricació additiva que empren un raig làser com a font d'energia, la matèria primera inicial (en forma de pols o filferro) és fosa per la font de calor làser de manera controlada, capa a capa, fins a crear un component amb dimensions finals o quasi finals. Estes tecnologies impliquen sotmetre el material imprés a un procés tèrmic únic, en el qual el material es funde en una àrea molt específica i després es refreda ràpidament a velocitats extremadament altes de fins a 10^6 K/s. Per tant, les microestructures que sorgixen dels processos de fabricació en AM diferixen significativament de les que s'aconseguixen en els processos tradicionals. A més, els materials que s'empren principalment en l'AM no s'han dissenyat explícitament per a estes tecnologies. Les característiques específiques dels processos d'AM poden utilitzar-se per a aconseguir microestructures i propietats diferents en acers que han sigut adaptats per a aprofitar les ràpides velocitats de refredament i la història tèrmica del procés, entre altres factors. De moment, el nombre de qualitats d'acer comercials disponibles en el mercat de l'AM és limitat. Diverses indústries demanden nous graus d'acer amb menor densitat per a disminuir el pes sense comprometre les propietats mecàniques. Els acers amb alt contingut en manganés es consideren materials molt prometedors per a aplicacions estructurals a causa de la seua excepcional combinació de resistència i ductilitat, amb una baixa densitat. No obstant això, malgrat les seues excepcionals propietats, els acers amb alt contingut en manganés s'enfronten a diverses limitacions o reptes durant les tècniques de processament convencionals. Afortunadament, la solidificació ràpida pot resoldre estos problemes. En este sentit, les tecnologies d'AM basades en làser proporcionen velocitats de refredament ràpides, així com flexibilitat en termes de disseny geomètric. Els nous reptes d'estes tecnologies implicaran la microsegregació i l'esquerdament en calent, o hot cracking en anglés, que es produïxen durant la solidificació. Esta tesi està dedicada a explotar el mètode CALPHAD per a realitzar càlculs termodinàmics amb la finalitat de dissenyar diversos acers amb alt contingut en manganés que puguen previndre eficaçment els problemes de solidificació ràpida en AM. Les composicions d'acer dissenyades es van produir en forma de pols per a AM mitjançant atomització amb gas. Es van analitzar les pólvores per a determinar la seua microestructura en relació amb la química i la velocitat de refredament. Ajustant adequadament els paràmetres d'impressió, estes pólvores d'acer amb alt contingut en manganés es van imprimir amb èxit en AM, donant lloc a densitats relatives superiors al 99.9%. Es va analitzar la microestructura d'estes mostres totalment denses i es va comparar amb les seues respectives pólvores, amb la finalitat d'identificar qualsevol diferència resultant de les variacions en la velocitat de refredament i els cicles tèrmics. Finalment, desprès de definir el millor conjunt de condicions d'impressió per a cada composició de pols, es van produir diverses mostres per a avaluar les propietats mecàniques. / [EN] Additive manufacturing (AM) is a process that builds three-dimensional solid objects by layering materials based on a computer-aided design model. AM is set to become the next industrial revolution, transforming the landscape of development and production. AM provides numerous benefits, including complex and flexible design possibilities, the elimination of intermediate processes like machining, production cost independence from batch size, reduced material waste, lightweight structures, customized machine repairs, and the ability to develop new materials, among other advantages. In additive manufacturing technologies that employ a laser beam as an energy source, the initial raw material (in the form of powder or wire) is melted by the laser heat source in a controlled manner, layer by layer, until a component with final or nearly final dimensions is created. These technologies involve subjecting the printed material to a unique thermal process, where the material is melted in a very specific area and then rapidly cooled at extremely high rates of up to 10^6 K/s. Hence, the microstructures that arise from the manufacturing processes in AM differ significantly from those achieved in traditional processes. Moreover, the materials predominantly employed in AM have not been explicitly designed for these technologies. The specific characteristics of AM processes can be utilized to achieve distinct microstructures and properties in steels that have been tailored to take advantage of the rapid cooling rates and thermal history of the process, among other factors. For the moment, the number of commercial steel grades available in the AM market is limited. Various industries are demanding new steel grades with lower density to decrease weight without compromising mechanical properties. High manganese steels are regarded as highly promising materials for structural applications due to their exceptional combination of strength and ductility, with low density. Nevertheless, despite the exceptional properties of high manganese steels, they encounter various limitations or challenges during conventional processing techniques. Fortunately, rapid solidification may solve these issues. In this sense, laser-based AM technologies provide rapid cooling rates, as well as flexibility in terms of geometric design. The new challenges of these technologies will involve micro-segregation and hot cracking occurring during solidification. This thesis is dedicated to exploiting the CALPHAD method to perform thermodynamic calculations in order to design various high manganese steels that can effectively prevent fast solidification issues in AM. The steel compositions designed were produced in the form of powder for AM using gas atomization. Powders were analyzed to determine their microstructure in relation to the chemistry and cooling rate. By adjusting properly, the printing parameters, these high manganese steel powders were successfully printed in AM, resulting in relative densities exceeding 99.9%. The microstructure of these fully dense samples was analyzed and compared to their respective powders, in order to identify any difference resulting from variations in cooling rate and thermal cycling. Lastly, after defining the best set of printing conditions for each powder composition, various samples were produced to evaluate the mechanical properties, to determine the correlation between the composition, microstructure and properties of these steels. In addition, lattice structures that are close to final part geometries were constructed to quantify the energy absorbed during compression by one of these high manganese steels. The results were then compared to those of 316L, revealing that the high manganese steel absorbs roughly twice as much the specific energy in compression. This finding demonstrates the potential of these novel AM steels for use in industrial applications. / Sánchez Poncela, M. (2024). Design of High Mn Fe-Mn-Al-C Low Density Steels for Additive Manufacturing [Tesis doctoral]. Universitat Politècnica de València. https://doi.org/10.4995/Thesis/10251/205174