Orientador: João Paulo Papa / Banca: José Remo Ferreira Brega / Banca: Estevam Rafael Hruschka Júnior / Resumo: Em problemas convencionais de reconhecimento de padrões, dado um conjunto de classes, cada instância do problema e associada a uma e somente uma classe. No entanto, alguns problemas reais de classificaço apresentam instâncias que podem ser associadas a mais de uma classe simultaneamente, esses problemas são denotados como classificação com múltiplos rótulos. Entre problemas dessa natureza, podemos destacar categorização de filmes e músicas, classificação de documentos, análise funcional de genes etc. Contudo, os problemas de classificação com múltiplos rótulos não são diretamente tratáveis por técnicas convencionais, o que justifica o interesse da comunidade de reconhecimento de padrões nesses tipos de problemas. Embora muitos métodos tenham sido propostos na literatura, há ainda muito a ser explorado, principalmente no uso de novos algoritmos convencionais de aprendizado de máquinas adaptados ou não aos problemas com múltiplos rótulos. O classificador supervisionado Floresta de Caminhos Otimos (Optimum- Path Forest - OPF) e um algoritmo determinístico aplicado a problemas convencionais de classificação, no entanto, ainda não foi investigado em problemas com múltiplos rótulos. Nesse contexto, investigamos neste trabalho a aplicação de classificadores baseados em OPF em problemas de múltiplos rótulos. Analisamos duas versões do classificador OPF: (i) a tradicional baseada em grafo completo e (ii) a versão baseada no grafo k-vizinhos mais próximos (OPFkNN). Para manipulação das bases com múltiplos rótulos, utilizamos dois métodos de transformação de problemas, o Binary Relevance e Label Powerset. Propusemos também algumas modificações nas fases de treinamento e classificação do OPFkNN com o objetivo de melhor os resultados desse classificador combinado a métodos de transformação de problemas. Os experimentos realizados em sete bases de dados públicas mostraram que as modifica ções ... / Abstract: In conventional problems of pattern recognition, given a set of classes, each instance of the problem is associated with one and only one class. However, some real classification problems have instances that can be associated with more than one class at the same time, these problems are denoted as classification with multilabel. Among such problems, we highlight movies and music categorization, document classification, functional gene analysis etc. Nevertheless, the classification problems with multilabel are not directly treatable by conventional techniques, which explains the interest of pattern recognition community in these types of problems. Although many methods have been proposed in the literature, there is still much to be explored, especially in the use of novel conventional machine learning algorithms adapted or not to problems with multlabels. The Optimum-Path Forest (OPF) classifier is a supervised and deterministic algorithm applied to conventional classification problems, however, it has been not investigated in problems with multilabel. In this context, we investigated in this work the application of OPF-based classifiers on multilabel problems. We analyzed two versions of OPF-based classi ers: (i) the traditional one based on complete graph and (ii) the one based on k-nearest neighbors graph (OPFkNN). For manipulation of multilabel datasets, we used two transformation methods, the Binary Relevance and Label Powerset. We also proposed some changes in the training and classification phases of OPFkNN aiming to achieve better results when combined it with transformation methods. Experiments performed in seven public datasets showed that changes in OPFkNN improve outcomes. Comparison with the J48 classifier, ... / Mestre

Orientador: João Paulo Papa / Resumo: A modelagem do problema de classificação como um problema de busca em um grafo fornece uma estrutura elegante, rica em algoritmos eficientes e comprovadamente corretos. A abordagem Floresta de Caminhos Ótimos reduz o problema de classificação para o cálculo de uma floresta de cami- nhos ótimos relativa a uma função de conectividade, a qual atribui um valor a qualquer caminho no grafo. Considerando o valor máximo entre todos os caminhos possíveis com término em cada vértice, o caminho ideal é trivial para alguns vértices, chamados raízes, e para os vértices restantes, a minimi- zação da função de conectividade atribui a cada vértice um caminho de custo mínimo a partir de sua raiz mais fortemente conectada. Não obstante, para a classificação de novos conjuntos de dados, assume-se que cada amostra compõe um vértice pertecente ao grafo e calcula-se a afinidade deste vértice às árvores geradoras mínimas respectivas a cada classe. Este procedimento não utiliza a estrutura inerente da aplicação que pode ser fundamental para uma melhor precisão dos resultados. Dentro desse contexto, este trabalho avalia a contribuição de técnicas de modelagem contextual como os campos aleatórios Markovianos e as abordagens de empilhamento de classificado- res. A modelagem do campo aleatório sumariza o comportamento global do sistema através de suas interações locais. Os métodos baseados em empilha- mento de classificadores interpretam as interações entre as amostras como uma análise no espaço escala, capturando as interações de longa distância de forma eficiente através da definição das regiões de vizinhança em múltiplas escalas. Resultados obtidos para a classificação de estruturas anatômicas do cérebro em imagens de ressonância magnética e de coberturas do solo em imagens multi-espectrais de sensoriamento remoto monstram que a inclusão da informação contextual é de fato capaz de melhorar ... / Abstract: The interpretation of classification problem as a graph search provides a rich framework with correct and efficient algorithms. The Optimum-Path Fo- rest classifier can reduce classification to the the computation of an optimum- path forest according to a connectivity function, which assigns a value to any path in the graph. Considering the maximum value among all possible paths with terminus at each node, the optimum path is trivial for some nodes, cal- led roots, and the remaining nodes will have an optimum path coming from their most strongly connected root, partitioning the graph into an optimum- path forest (disjoint sets of optimum-path trees). Notwithstanding, to clas- sify out-of-sample, we assume that each sample in the new dataset composes one node in the graph and we compute their most strongly connected root within all spanning trees. As one can see, this procedure do not take advan- tage of the problem structure information, which can be fundamental for a better precision of the results. In this context, the purpose of this work is to evaluate the contribution of contextual modelling techniques, such as Mar- kov random fields and stacked classifiers. The first approach, called Markov random fields, sumarizes the system overall behavior through its local inte- ractions. The second approach, based on combination of classifiers, model the interaction between samples in the space scale, which provides effici- ent implementations of long interaction by defining neighborly relations in multiple scales. The results for brain tissue segmentation of magnetic reso- nance images and land-cover classification of multi-spectral satellite images show that the contextual information can improve the effectiveness of the Optimum-Path Forest classifier / Mestre

São Paulo, metrópole global e do terciário avançado, tem conhecido, sobretudo nas últimas três décadas, a efetivação de operações urbanas em praticamente todas as regiões da cidade. Na escala municipal, a região compreendida pelos distritos do Butantã, Rio Pequeno, Morumbi e Vila Sônia torna-se objeto da composição desse instrumento urbanístico, a partir da chamada Operação Urbana Consorciada Vila Sônia (OUCVS). As reestruturações e modificações postas nos variados projetos da OUCVS estão francamente relacionadas ao lugar que a região ocupa na metrópole, cuja forma e conteúdo são herdeiros dos caminhos e fronteiras pregressos (reafirmando formas pregressas da propriedade), tanto em relação aos fluxos viários quanto às possibilidades econômicas do contemporâneo mercado imobiliário e seu crescente interesse por certas áreas consideradas estratégicas no município de São Paulo. Discernindo tal estratégia do espaço, trata-se também em considerar a reprodução das relações sociais de produção, assentando-se a espacialidade desse fenômeno nas tessituras do quotidiano; este, em sua materialidade, conduz ao necessário tratamento, neste trabalho, das camadas e classes sociais, bem como suas complexas tramas de relações. Assim, admitindo o desnível constante entre a(o) política(o) e a economia política, operados no corpo da reprodução das relações sociais de produção, sugerimos a consideração da política média como o devir dessa forma social, cujo fundamento se ancora em reiterativa alienação, mistificação, reificação e fetichização. Reconhecendo tais fundamentos, poder-se-ia abrir vias no intento da urgente superação do discurso, do pensamento e das práticas ancoradas ao Estado e a essa economia. / São Paulo, global metropolis and including the advanced tertiary sector, has known, especially in the last three decades, the realization of urban operations in virtually all regions of the city. At the municipal level, the region comprising the districts of Butantã, Rio Pequeno, Morumbi and Vila Sônia becomes the object for the composition of this urban instrument, from the called Operação Urbana Consorciada Vila Sônia (OUCVS). The restructurings and changes which are put in varied projects for the OUCVS are frankly related to the place occupied by the region in the metropolis, whose form and content are the heirs of the paths and borders of its previous history (reaffirming stunted forms of ownership); that is both in relation to road flows as the economic possibilities of contemporary housing market and its growing interest in certain areas considered strategic in São Paulo. Discerning such a strategy space, it is also to consider the reproduction of social relations of production, bottoming spatiality of this phenomenon in everyday tessitura, who, in its materiality, leading to necessary treatment, in this work, for the layers and social classes as well as their complex webs of relationships. Thus, assuming the constant gap between the political and the political economy, both operated in the body of the reproduction of social relations of production, we suggest consider the middle politics as the average social becoming in this way, whose foundation is anchored in reiterative alienation, mystification, reification and fetishization. Recognizing such foundations, we should pave the way with the intent of the urgent overcoming of the speech, thought and practices anchored to this State and economy.

Submitted by Geandra Rodrigues (geandrar@gmail.com) on 2018-03-27T13:16:05Z No. of bitstreams: 1 fabriciodeoliveiracoelho.pdf: 19075776 bytes, checksum: 5f9c07d95c6d348d64825d66fda1c6f3 (MD5) / Approved for entry into archive by Adriana Oliveira (adriana.oliveira@ufjf.edu.br) on 2018-03-27T13:40:24Z (GMT) No. of bitstreams: 1 fabriciodeoliveiracoelho.pdf: 19075776 bytes, checksum: 5f9c07d95c6d348d64825d66fda1c6f3 (MD5) / Made available in DSpace on 2018-03-27T13:40:24Z (GMT). No. of bitstreams: 1 fabriciodeoliveiracoelho.pdf: 19075776 bytes, checksum: 5f9c07d95c6d348d64825d66fda1c6f3 (MD5) Previous issue date: 2018-02-08 / CAPES - Coordenação de Aperfeiçoamento de Pessoal de Nível Superior / Esse trabalho apresenta uma metodologia para a concepção de missões autônomas utilizando robôs móveis com tração diferencial em ambientes internos. As missões consistem em deslocar o robô até uma posição objetivo partindo de uma pose inicial. Para que as missões ocorram com sucesso, são implementados algoritmos de localização e planejamento de caminhos. Para localização, foi utilizado Filtro de Kalman Estendido (do inglês, Extended Kalman Filter EKF) para fundir a odometria com visão computacional. A visão é responsável por encontrar marcadores artificiais conhecidos como Ar codes que são alocados no ambiente. O planejamento é caracterizado por uma forma híbrida que corresponde a união de um método deliberativo e reativo. No Planejamento deliberativo, foi proposto e utilizado o método Direct-DRRT* cuja base é oriunda do RRT (Rapidly Exploring Random Tree). Além do RRT, esse planejador também apresenta características de dois outros métodos já presentes na literatura: RRT* e DRRT. O planejador deliberativo enviará para o reativo um conjunto de sub-objetivos que conecta a posição em que o robô se encontra até o objetivo final. O planejamento reativo é aplicado durante a missão e é o responsável pelo desvio de obstáculos dinâmicos que não foram mapeados. No Reativo, é utilizado o método dos Campos Potenciais Artificiais (CPA), que também se comporta como o controlador do robô durante a navegação. Para encontrar os obstáculos, utilizou-se o sensor de profundidade Asus Xtion, pois, a partir das imagens geradas por esse sensor, é possível encontrar as distâncias que os bloqueios se encontram. As informações desse sensor também será de grande valia na atualização do mapa. O sistema é integrado através da framework ROS (Robot Operating System). Todos os algoritmos foram implementados por meio da linguagem de programação Python. Os resultados do trabalho foram apresentados por meio do simulador Gazebo e testes práticos a partir da plataforma P3DX. Foram analisados o comportamento do robô em alguns problemas que podem ocorrer durante a navegação, como o sequestro e aparecimento mínimos locais. Ao final desse trabalho, apresentou-se a melhoria nos resultados do planejador de caminhos Direct-DRRT*, onde foi possível constatar a queda no tempo para obter um caminho, a quantidade de iterações, de nós e do comprimento do caminho em comparação aos outros métodos. No que tange à localização, essa dissertação obteve significativas melhoras comparado com o método que utiliza somente a odometria. Além desse resultado, esse trabalho também obteve sucesso em apresentar uma solução para a implementação de missões autônomas. / This work presents a design methodology for autonomous missions using mobile robots with differential traction in indoor environments. The missions consist of moving the robot to a goal position starting from an initial pose. For missions success, it is necessary to implement localization and path planning algorithms. For localization, Extended Kalman Filters (EKF) used to fuse odometry with computational vision. The view is responsible for finding artificial markers known as Ar codes that are presented in the environment. The planning is characterized by a hybrid form that corresponds to the union of a deliberative and reactive methods. In the Deliberative Planning, the Direct-DRRT * method, whose base is derived from the Rapidly Exploring Random Tree (RRT), is proposed and used. In addition to the RRT, this planner also presents characteristics of two other methods already presented in the literature, i.e. RRT * and DRRT. The deliberative planner sends to the reactive a set of sub-objectives that connects the initial position to the final goal. Reactive planning is applied during the mission and it is responsible for the dynamic obstacles avoidance that have not been mapped. In the reactive, the Artificial Potential Fields (APF) method is used, which also behaves as the robot controller during navigation. To find the obstacles, we use the sensor Asus Xtion, due to the possibility to find the distances that the locks are in the images generated by this sensor. All the algorithms were implemented through the programming language Python. The results of the work were presented through the simulator Gazebo and practical tests using the P3DX platform. We analyzed the robot behavior in some problems that may occur during navigation, such as kidnapped and local minimum appearance. At the end, the improvement in the results of the Direct-DRRT * path planner is also presented. It is possible to verify the decrease in the time to obtain a path, the number of iterations of nodes and the path length in comparison to other methods. Regarding the location, this dissertation has obtained significant improvements when compared to the methods that use only odometry. Besides, the work was also successful in presenting a solution for the autonomous missions implementation.

Orientadores: Anderson de Rezende Rocha, Ricardo da Silva Torres / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação / Made available in DSpace on 2018-08-25T19:52:29Z (GMT). No. of bitstreams: 1 MendesJunior_PedroRibeiro_M.pdf: 10648148 bytes, checksum: 314a33c9bb6fb8a188bfa762899107e8 (MD5) Previous issue date: 2014 / Resumo: Em reconhecimento de padrões, um cenário aberto é aquele em que não há amostras de treinamento para algumas classes que podem aparecer durante o teste. Normalmente, muitas aplicações são inerentemente de cenário aberto. Consequentemente, as soluções bem sucedidas da literatura para cenário fechado nem sempre são adequadas para problemas de reconhecimento na prática. Nesse trabalho, propomos um novo classificador multiclasse para cenário aberto, que estende o classificador Optimum-Path Forest (OPF). O OPF é um classificador de padrões baseado em grafos, simples, independente de parâmetros, multiclasse e desenvolvido para para problemas de cenário fechado. O método que propomos, o Open-Set OPF (OSOPF), incorpora a capacidade de reconhecer as amostras pertencentes às classes que são desconhecidas no tempo de treinamento, sendo adequado para reconhecimento em cenário aberto. Além disso, propomos novas medidas para avaliação de classificadores propostos para problemas em cenário aberto. Nos experimentos, consideramos seis grandes bases de dados com diferentes cenários de reconhecimento e demonstramos que o OSOPF proposto supera significativamente as abordagens existentes na literatura / Abstract: An open-set recognition scenario is the one in which there are no a priori training samples for some classes that might appear during testing. Usually, many applications are inherently open set. Consequently, the successful closed-set solutions in the literature are not always suitable for real-world recognition problems. Here, we propose a novel multiclass open-set classifier that extends upon the Optimum-Path Forest (OPF) classifier. OPF is a graph-based, simple, parameter independent, multiclass, and widely used classifier for closed-set problems. Our proposed Open-Set OPF (OSOPF) method incorporates the ability to recognize samples belonging to classes that are unknown at training time, being suitable for open-set recognition. In addition, we propose new evaluation measures for assessing the effectiveness performance of classifiers in open-set problems. In experiments, we consider six large datasets with different open-set recognition scenarios and demonstrate that the proposed OSOPF significantly outperforms its counterparts of the literature / Mestrado / Ciência da Computação / Mestre em Ciência da Computação

Conselho Nacional de Desenvolvimento Científico e Tecnológico / This research brings its contribution to support the Physical Education teachers in their initial and permanent processes of education, as it pictures the reality they live in their daily work routine at public schools. The methodological paths which were adopted followed the principles of case study qualitative approach. The study field of this research was a public school of Santa Maria, RS, having the information collected through semi-structured interview, done with three elementary school Physical Education teachers who were in effect working full time and who had at least five years of their career in a full-time effective job with Physical Education. To analyze the collected information, content analysis was used. It was concluded that the possibilities and limitations faced by teachers are the most diverse and that are much more prevalent negative aspects than positive. The main going astray found are lack of physical space and equipment, depreciation of physical education, lack of unity and fellowship among teachers, low salaries, limitations as to how the teacher developing lessons, indiscipline and violence among students and difficulties do not have time to reflect and exchange experiences. The paths indicated by the teachers were happy to teach, be in contact with students exchanging knowledge, affection between them, they are loved and valued by students. / Este estudo está inserido na Linha de Pesquisa Formação, Saberes e Desenvolvimento Profissional (PPGE/CE/UFSM) e teve como objetivo analisar quais são as possibilidades (caminhos) e as limitações (descaminhos) encontrados na prática pedagógica dos professores de Educação Física Escolar de uma escola pública de Santa Maria (RS). Este trabalho traz sua contribuição no apoio aos processos de formação inicial e permanente dos professores de Educação Física, na medida em que retrata a realidade em que os docentes convivem em seu trabalho diário nas escolas públicas. Os caminhos metodológicos que foram adotados seguiram os pressupostos da abordagem qualitativa do tipo estudo de caso. O campo de estudo da pesquisa foi uma escola pública de Santa Maria, RS, tendo as informações coletadas através da entrevista semi-estruturada, realizada com três professores de Educação Física do ensino fundamental em efetivo exercício de sua atividade docente e que tinham no mínimo cinco anos de carreira em efetivo trabalho com a disciplina. Para analisar as informações coletadas foi utilizada à análise de conteúdo. Concluiu-se que as possibilidades e limitações encontradas pelos professores são as mais diversas e o que prevalece são muito mais aspectos negativos do que positivos. Os principais descaminhos encontrados são a falta de espaço físico e material, desvalorização da Educação Física, falta de união e companheirismo entre os professores, os baixos salários, limitações quanto à maneira do professor desenvolver suas aulas, indisciplina e violência entre os alunos e dificuldades de não disporem de tempo para refletir e trocar experiências. Os caminhos apontados pelos professores são satisfação em dar aula, estar em contato com os alunos trocando conhecimentos, afetividade entre ambos, serem queridos e valorizados pelos alunos.

Uma decomposição de um grafo G é um conjunto D = {H_1,... , H_k } de subgrafos de G dois-a-dois aresta-disjuntos que cobre o conjunto das arestas de G. Se H_i é isomorfo a um grafo fixo H, para 1<=i<=k, então dizemos que D é uma H-decomposição de G. Neste trabalho, estudamos o caso em que H é um caminho de comprimento fixo. Para isso, primeiramente decompomos o grafo dado em trilhas, e depois fazemos uso de um lema de desemaranhamento, que nos permite transformar essa decomposição em trilhas numa decomposição somente em caminhos. Com isso, obtemos resultados para três conjecturas sobre H-decomposição de grafos no caso em que H=P_\\ell é o caminho de comprimento \\ell. Dois desses resultados resolvem versões fracas das Conjecturas de Kouider e Lonc (1999) e de Favaron, Genest e Kouider (2010), ambas para grafos regulares. Provamos que, para todo inteiro positivo \\ell, (i) existe um inteiro positivo m_0 tal que se G é um grafo 2m\\ell-regular com m>=m_0, então G admite uma P_\\ell-decomposição; (ii) se \\ell é ímpar, existe um inteiro positivo m_0 tal que se G é um grafo m\\ell-regular com m>=m_0, e G contém um m-fator, então G admite uma P_\\ell-decomposição. O terceiro resultado diz respeito a grafos altamente aresta- conexos: existe um inteiro positivo k_\\ell tal que se G é um grafo k_\\ell-aresta-conexo cujo número de arestas é divisível por \\ell, então G admite uma P_\\ell-decomposição. Esse resultado prova que a Decomposition Conjecture de Barát e Thomassen (2006), formulada para árvores, é verdadeira para caminhos. / A decomposition of a graph G is a set D = {H_1,...,H_k} of pairwise edge-disjoint subgraphs of G that cover the set of edges of G. If H_i is isomorphic to a fixed graph H, for 1<=i<=k, then we say that D is an H-decomposition of G. In this work, we study the case where H is a path of fixed length. For that, we first decompose the given graph into trails, and then we use a disentangling lemma, that allows us to transform this decomposition into one consisting only of paths. With this approach, we tackle three conjectures on H-decomposition of graphs and obtain results for the case H=P_\\ell is the path of length \\ell. Two of these results solve weakenings of a conjecture of Kouider and Lonc (1999) and a conjecture of Favaron, Genest and Kouider (2010), both for regular graphs. We prove that, for every positive integer \\ell, (i) there is a positive integer m_0 such that, if G is a 2m\\ell-regular graph with m>=m_0, then G admits a P_\\ell-decomposition; (ii) if \\ell is odd, there is a positive integer m_0 such that, if G is an m\\ell-regular graph with m>=m_0 containing an m-factor, then G admits a P_\\ell-decomposition. The third result concerns highly edge-connected graphs: there is a positive integer k_\\ell such that if G is a k_\\ell-edge-connected graph whose number of edges is divisible by \\ell, then G admits a P_\\ell-decomposition. This result verifies for paths the Decomposition Conjecture of Barát and Thomassen (2006), on trees.

O tema central deste trabalho é o estudo de problemas sobre caminhos mais longos em grafos, de pontos de vista tanto estrutural como algorítmico. A primeira parte tem como foco o estudo de problemas motivados pela seguinte questão levantada por T. Gallai em 1966: é verdade que em todo grafo conexo existe um vértice comum a todos os seus caminhos mais longos? Hoje, já se conhecem diversos grafos conexos cuja intersecção de todos os seus caminhos mais longos é vazia. Entretanto, existem classes de grafos para as quais a resposta à pergunta de Gallai é afirmativa. Nessa linha, apresentamos alguns resultados da literatura e duas novas classes que obtivemos: os grafos exoplanares e as 2-árvores. Motivado por esse problema, nos anos 80, T. Zamfirescu formulou a seguinte pergunta que permanece em aberto: é verdade que em todo grafo conexo existe um vértice comum a quaisquer três de seus caminhos mais longos? Apresentamos, além de alguns resultados conhecidos, uma prova de que a resposta é afirmativa para grafos em que todo bloco não trivial é hamiltoniano. Notamos que esse último resultado e o acima mencionado para grafos exoplanares generalizam um teorema de M. Axenovich (2009) que afirma que quaisquer três caminhos mais longos em um grafo exoplanar têm um vértice em comum. Finalmente, mencionamos alguns outros resultados da literatura relacionados com o tema. Na segunda parte, investigamos o problema de encontrar um caminho mais longo em um grafo. Este problema é NP-difícil para grafos arbitrários. Isto motiva investigações em duas linhas a respeito da busca de tais caminhos. Pode-se procurar classes especiais de grafos para as quais existem algoritmos polinomiais, ou pode-se abrir mão da busca de um caminho mais longo, e projetar um algoritmo eficiente que encontra um caminho cujo comprimento esteja próximo do comprimento de um mais longo. Nesse trabalho estudamos ambas as abordagens e apresentamos alguns resultados da literatura. / The central theme of this thesis is the study of problems related to longest paths in graphs, both from a structural and an algorithmic point of view. The first part focuses on the study of problems motivated by the following question raised by T. Gallai in 1966: is it true that every connected graph has a vertex common to all its longest paths? Today, many connected graphs in which all longest paths have empty intersection are known. However, there are classes of graphs for which Gallais question has a positive answer. In this direction, we present some results from the literature, as well as two new classes we obtained: outerplanar graphs and 2-trees. Motivated by this problem, T. Zamfirescu, in the 80s, proposed the following question which remains open: is it true that every connected graph has a vertex common to any three of its longest paths? We present, in addition to some known results, a proof that the answer to this question is positive for graphs in which all non-trivial blocks are Hamiltonian. We note that this result and the one mentioned above for outerplanar graphs generalize a theorem of M. Axenovich (2009) that states that any three longest paths in an outerplanar graph have a common vertex. Finally, we mention some other related results from the literature. In the second part, we investigate the problem of finding a longest path in a graph. This problem is NP-hard for arbitrary graphs. This motivates investigations in two directions with respect to the search for such paths. We can look for special classes of graphs for which the problem is polynomially solvable, or we can relinquish the search for a longest path and design an efficient algorithm that finds a path whose length is close to that of a longest path. In this thesis we study both approaches and present some results from the literature.

O Problema dos K Menores Caminhos é uma generalização do Problema do Menor Caminho, em que desejamos encontrar os K caminhos de menor custo entre dois vértices de um grafo. Estudamos e implementamos algoritmos que resolvem esse problema em grafos dirigidos, com peso nos arcos e que permitem apenas caminhos sem repetição de vértices na resposta. Comparamos seus desempenhos utilizando grafos do 9th DIMACS Implementation Challenge. Identificamos os pontos fortes e fracos de cada algoritmo, e propusemos uma variante híbrida dos algoritmos de Feng e de Pascoal. Essa variante proposta obteve desempenho superior aos algoritmos base em alguns grafos, e resultado superior a pelo menos um deles na grande maioria dos testes. / The K-Shortest Path Problem is a generalization of the Shortest Path Problem, in which we must find the K paths between two vertices in a graph that have the lowest costs. We study some K-Shortest Path Problem algorithms applied to weighted directed graphs, allowing only paths with no repeated vertices. We compare empirically implementation of some algorithms, using instance graphs from the 9th DIMACS Implementation Challenge. We identify the strengths and weaknesses of each algorithm, and we propose a hybrid version of Feng\'s and Pascoal\'s algorithms. This proposed variant achieve better perfomance compared to both base algorithms in some graphs, and it is better than at least one of them in most cases.

A detecção de furtos e fraudes nos sistemas de energia provocados por consumidores irregulares é o principal alvo em análises de perdas não-técnicas ou comerciais pelas empresas de energia. Embora a identificação automática de perdas nãotécnicas tenha sido amplamente estudada, a tarefa de selecionar as características mais representativas em um grande conjunto de dados a fim de aumentar a taxa de acerto da identificação, bem como para caracterizar possíveis consumidores irregulares como um problema de otimização, não tem sido muito explorada neste contexto. Neste trabalho, visa-se o desenvolvimento de algoritmos híbridos baseados em técnicas evolutivas a fim de realizar a seleção de características no âmbito da caracterização de perdas não-técnicas, comparando as suas taxas de acerto e verificando as características selecionadas. Vários classificadores são comparados, com destaque para a técnica Floresta de Caminhos Ótimos por sua robustez, sendo ela a técnica escolhida para o cálculo da função objetivo das técnicas evolutivas, analisando o desempenho das mesmas. Os resultados demonstraram que a seleção de características mais representativas podem melhorar a taxa de acerto da classificação de possíveis perdas não-técnicas quando comparada à classificação sem o processo de seleção de características em conjuntos de dados compostos por perfis de consumidores industriais e comerciais. Isto significa que existem características que não são pertinentes e podem diminuir a taxa de acerto durante a classificação dos consumidores. Através da metodologia proposta com o processo de seleção de características, é possível caracterizar e identificar os perfis de consumidores com mais precisão, afim de minimizar os custos com tais perdas, contribuindo para a recuperação de receita das companhias de energia elétrica. / The detection of thefts and frauds in power systems caused by irregular consumers is the most actively pursued analysis in non-technical losses by electric power companies. Although non-technical losses automatic identification has been massively studied, the task of selecting the most representative features in a large dataset, in order to boost the identification accuracy, as well as characterizing possible irregular consumers as a problem of optimization, has not been widely explored in this context. This work aims at developing hybrid algorithms based on evolutionary algorithms in order to perform feature selection in the context of non-technical losses characterization. Although several classifiers have been compared, we have highlighted the Optimum-Path Forest (OPF) technique mainly because of its robustness. Thus, the OPF classifier was chosen to compute the objective function of evolutionary techniques, analyzing their performances. This procedure with feature selection is compared with the procedure without feature selection in datasets composed by industrial and commercial consumers profiles. The results demonstrated that selecting the most representative features can improve the classification accuracy of possible non-technical losses. This means that there are irrelevant features and they can reduce the classification accuracy of consumers. Considering the methodology proposed with feature selection procedure, it is possible to characterize and identify consumer profiles more accurately, in order to minimize costs with such losses, contributing to the recovery of revenue from electric power companies.