Submitted by PPG Letras (letraspg@pucrs.br) on 2018-06-12T13:10:31Z No. of bitstreams: 1 Disserta??o_ Joana Paim da Luz.pdf: 3695641 bytes, checksum: 6a5e3a119df6d2f32296071f3b7bf759 (MD5) / Approved for entry into archive by Sheila Dias (sheila.dias@pucrs.br) on 2018-06-22T17:17:03Z (GMT) No. of bitstreams: 1 Disserta??o_ Joana Paim da Luz.pdf: 3695641 bytes, checksum: 6a5e3a119df6d2f32296071f3b7bf759 (MD5) / Made available in DSpace on 2018-06-22T17:25:39Z (GMT). No. of bitstreams: 1 Disserta??o_ Joana Paim da Luz.pdf: 3695641 bytes, checksum: 6a5e3a119df6d2f32296071f3b7bf759 (MD5) Previous issue date: 2018-01-25 / Conselho Nacional de Pesquisa e Desenvolvimento Cient?fico e Tecnol?gico - CNPq / Dyslexia is a learning disorder of neurobiological origin, which is characterized by an unexpected difficulty when decoding written texts, due to an unsatisfactory learning of the alphabetical principle and a deficient graphological-phonemic association. The ways dyslexia affects writing skills have been scientifically explored so as to investigate linguistic aspects associated with spelling and classes of words used by subjects who suffer from dyslexia. Quantitative studies focused on measuring the structure of their texts are unknown. The main objective of this study was to identify patterns of textual connectivity in good readers, bad readers and dyslexic children, based on the analysis of graph measures extracted from their texts and Machine Learning techniques. Essentially, it sought to investigate (a) whether the type of transcription of the texts - corrected or original - and the normalization of the graph attributes by the number of words of each text interfere significantly in sorting the children in their fluency and schooling groups; (b) whether there is significant differences among good readers?, bad readers? and the dyslexic participants? graph attributes; (c) whether measures of each year of data collection converge to similar values and if they are significantly different among the years; (d) whether the graph attributes obtained with Speech Graphs, when associated with Machine Learning techniques, can predict reading fluency levels and, specifically, developmental dyslexia. The hypotheses for the questions listed were all affirmative. To verify them, texts produced by 181 children and adolescents from the ACERTA Project were transcribed and divided in two experimental groups: Ambulatory (N = 52, all dyslexic) and Schools (N = 129, subdivided into good, medium and bad readers). These transcribed texts served as input for Speech Graphs software, which extracted graph attributes representative of the structure of each text. Descriptive and inferential statistical analyzes revealed (a) the prevalence of significance among graphs attributes extracted from non-normalized original transcripts (63.07% significance between analyzes); (b) patterns of textual connectivity by each reading fluency group and (c) patterns of textual connectivity by year of data collection based on significant differences found in five graphs attributes - nodes, edges, largest connected component, density and average smallest path; (d) 2016 as the best year to sort the children in their reading fluency groups by making use of SVM classifiers, considering they reached the highest accuracy (85%), recall (83%), precision (85%) and F1 score (83%) when sorting good readers and dyslexic children texts, based on 2016 graph measures. These findings provide evidences that indicate the possibility to explore and improve a new methodological frame to assess reading fluency through written texts and based on Graph Theory. / A dislexia ? um transtorno de aprendizagem de natureza neurobiol?gica, caracterizado por uma inesperada dificuldade em decodificar e compreender textos escritos, decorrente de um aprendizado insatisfat?rio do princ?pio alfab?tico e de uma associa??o grafo-fon?mica deficit?ria. A explora??o cient?fica da express?o escrita de disl?xicos tem se dedicado, em grande medida, a investigar aspectos lingu?sticos associados ? ortografia e ?s classes de palavras empregadas por sujeitos com dislexia. Estudos de natureza quantitativa focados em mensurar a estrutura dos textos deste grupo cl?nico s?o desconhecidos. O principal objetivo do presente trabalho foi identificar padr?es de conectividade textual em bons leitores, maus leitores e disl?xicos, a partir da an?lise de medidas de grafo extra?das de suas produ??es textuais e de t?cnicas de Aprendizado de M?quina. Essencialmente, buscou-se investigar (a) se o tipo de transcri??o dos textos - corrigidos ou originais - e a normaliza??o das medidas de grafo pelo n?mero de palavras interferem significativamente na classifica??o das crian?as entre grupos de flu?ncia e escolaridade; (b) se h? diferen?as significativas entre os atributos do grafo dos bons leitores, maus leitores e disl?xicos; (c) se as medidas de cada ano de coleta de dados convergem para valores semelhantes e se s?o significativamente diferentes entre os anos; (d) se os atributos de grafo obtidos com a utiliza??o do Speech Graphs, quando associados ?s t?cnicas de Aprendizado de M?quina, podem prever n?veis de flu?ncia de leitura e, especificamente, a dislexia de desenvolvimento. As hip?teses, para as quest?es listadas, eram todas afirmativas. Para verific?-las, os textos produzidos por 181 crian?as e adolescentes do Projeto ACERTA foram transcritos e divididos em dois grupos experimentais: Ambulat?rio (N = 52, todos disl?xicos) e Escolas (N = 129, subdividido em leitores bons, m?dios e maus leitores). Esses textos transcritos serviram de entrada para o software Speech Graphs, que extraiu atributos de grafo representativos da estrutura de cada texto. As an?lises estat?sticas descritivas e inferenciais revelaram (a) a preval?ncia de signific?ncia dos atributos de grafo extra?dos de transcri??es originais n?o normalizadas (63,07% de signific?ncia entre an?lises); (b) padr?es de conectividade textual por grupo de flu?ncia de leitura e (c) padr?es de conectividade textual por cada ano de coleta de dados com base em diferen?as significativas encontradas em cinco atributos de grafo: n?s, arestas, maior componente conectado, densidade e caminho menor m?dio; (d) 2016 como o melhor ano para classificar as crian?as em seus grupos de flu?ncia de leitura fazendo uso de classificadores SVM, considerando que eles alcan?aram a maior acur?cia (85%), revoca??o (83%), precis?o (85%) e pontua??o F1 ( 83%) ao classificar textos de bons leitores e de crian?as disl?xicas, com base em medidas de grafo de 2016. Estas descobertas fornecem evid?ncias que indicam a possibilidade de se explorar e aprimorar um novo aparato te?rico-metodol?gico para avaliar a flu?ncia de leitura, a partir de textos escritos e com base na Teoria dos Grafos.

Esta tese de mestrado se propõe a resolver alguns problemas interessantes na área de Computação e Matemática, utilizando técnicas de Análise Combinatória, Teoria dos Grafos, Funções Geratrizes, Programação Dinâmica e Álgebra Linear. No decorrer da tese são abordados 3 problemas cujas soluções apresentam enfoque original, sob o ponto de vista da Teoria da Computação. O primeiro problema é o problema de Ulam (no capítulo referente a este problema, um novo algoritmo heurístico que interpreta o papel de um dos jogadores é apresentado). O segundo problema trata da contagem do número de matrizes de sinais alternantes e o último problema trata da contagem do número recobrimentos por dominós de uma dada figura plana (ou pareamentos perfeitos em grafos bipartidos).

O estudo de redes complexas vem se expandindo e se difundindo cada vez mais em áreas multidisciplinares, com contribuições em Biologia, Sociologia, Física e Computação, entre inúmeras outras. Nesta modelagem de redes que utiliza grafos, ligações executam o importante papel de representar as interações entre os elementos da rede. Particularmente, ligações fracas se destacam por realizar a conexão entre diferentes grupos da rede. Entretanto, nem sempre é desejável ou ao menos possível manter um grande número de ligações em redes complexas, devido ao custo de manutenção de ligações em redes tecnológicas reais, por exemplo. Embora não-intuitiva, a remoção de ligações pode gerar melhorias em algumas propriedades. Neste trabalho, propomos uma otimização de propriedades small-world em redes geométricas, isto é, a obtenção de um alto coeficiente de agrupamento e a manutenção de um baixo caminho mínimo médio. Tal otimização pode ocorrer a partir da remoção de ligações selecionadas e da emergência de ligações fracas nas redes. Para isso, utilizamos o método Reckful Roaming de controle local de topologias, que foca na criação de regiões altamente clusterizadas, através da remoção de ligações que não contribuam para o aumento do agrupamento local. Desenvolvemos um novo método de controle local de topologias, cuja probabilidade de remoção de ligação é baseada nas similaridades máxima e média entre cada ligação analisada. Algumas variantes híbridas, utilizando heurísticas Reckful Roaming e do método baseado em similaridades, também são desenvolvidas, a fim de obtermos uma combinação de propriedades e vantagens de ambos os métodos. Por fim, propomos a aplicação de um método para detecção de ligações fracas baseado no modelo de comunidades de ligações. O algoritmo de clusterização de comunidades de ligações realizou com sucesso a detecção de ligações fracas nas amostras testadas. As redes otimizadas através do método Reckful Roaming apresentaram diminuição do percentual de ligações fracas. Contudo, a aplicação dos métodos baseados em similaridades entre ligações resultou em redes com até 1/3 de ligações fracas, após a remoção de metade das ligações da rede. Os métodos propostos e estudados aqui podem ser aplicados a redes complexas de grande escala e testados em redes reais, para extensão dos resultados.

Esta tese é sobre otimização combinatória e nela aborda-se o problema de minimização de pilhas abertas. São apresentados dois novos métodos heurísticos simples para solução deste problema, baseados em algoritmos básicos da teoria de grafos aos quais associam-se duas simples regras de melhoria gulosas. Para aferição da qualidade dos métodos propostos, estes são comparados com os dois métodos que são o estado da arte do problema objeto de estudo, sendo um exato e outro, heurístico. Para que os experimentos computacionais fossem abrangentes, foram utilizados três conjuntos de instâncias: o primeiro, adotado amplamente pela comunidade acadêmica; o segundo, mais recente e de maior nível de dificuldade e o terceiro novo conjunto de instâncias, proposto neste mesmo trabalho, possuidor de problemas com maiores instâncias e nível de dificuldade maior que os dois anteriores. Os resultados reportados mostram que as duas heurísticas - HBF2r e Lookahead, superam o método heurístico de melhor desempenho da literatura em qualidade da solução e em regularidade. Ainda, Lookahead obtém grande quantidade de soluções ótimas, baixos índices de erros e soluções de qualidade próxima às soluções geradas pelo método exato nos três conjuntos de instâncias considerados, não obstante o fato de se tratar de uma heurística. Os tempos computacionais são considerados muito baixos em termos práticos. Espera-se que as contribuições aqui realizadas possam auxiliar uma maior compreensão do problema.

Consideramos nesta dissertação um problema, NP-difícil, de seqüenciamento de padrões, vizando minimizar o número máximo de pilhas abertas em torno de uma máquina industrial de corte. Estamos interessados em métodos frugais, os quais, seguindo à terminologia de Halldórson (91), são aqueles - métodos - que além de utilizar poucos recursos computacionais - tempo e espaço - possuem idéias de implementações simples. A modelagem do problema pela Teoria dos Grafos foi a escolhida para obtenção de tais métodos, na tentativa de se identificarem aspectos estruturais que, porventura, pudessem emergir e auxiliar na sua resolução. A partir daquela modelagem, descobrimos ser o grafo complementar bastante esparso e possuidor de um conjunto independente maximal surpreendentemente grande, se comparado ao número de vértices do grafo. Através da informação adicional, fornecida por estes dois aspectos estruturais encontrados no grafo modelada, um método geral, baseado no clique maximal, foi desenvolvido. A frugalidade do método está no uso de uma conhecida heurística gulosa, de tempo linear no número de vértices, para detecção de conjuntos independentes. A partir do método geral, duas heurísticas puderam ser desenvolvidas: a primeira, de detecção de circuitos hamiltonianos, obtidos através de uma versão do algoritmo extensão-rotação para grafos randônicos, com o circuito inicial composto pelos vértices do clique maximal; e a segunda, de contratação recursiva de cliques. Realizamos testes computacionais comparando as nossas heurísticas com aquelas pertencentes ao estado da arte encontrado na literatura. Os resultados demonstram que as duas heurísticas desenvolvidas através do método proposto são competitivas, tanto em termos de tempo e espaço como de erro médio, além da facilidade de implementação.

Focalizamos, nesta tese, o problema de minimizar o número máximo de pilhas abertas em torno de uma máquina de corte. Desenvolvemos métodos exatos para alguns casos especiais do problema, uma nova heurística e um novo limite inferior para o problema. Propomos, também, aperfeiçoamentos em um método enumerativo apresentado anteriormente na literatura. Testes computacionais com a heurística e métodos desenvolvidos, foram realizados, mostrando os ganhos conseguidos com os novos desenvolvimentos.

Relações min-max são objetos centrais em otimização combinatória. Elas basicamente afirmam que, numa dada estrutura, o valor ótimo de um certo problema de minimização é igual ao valor ótimo de um outro problema de maximização. Relações desse tipo fornecem boas caracterizações e descrições poliédricas para diversos problemas importantes, além de geralmente virem acompanhadas de algoritmos eficientes para os problemas em questão. Muitas vezes, tais algoritmos eficientes são obtidos naturalmente das provas construtivas dessas relações; mesmo quando isso não ocorre, essas relações revelam o suficiente sobre a estrutura combinatória dos problemas, levando ao desenvolvimento de algoritmos eficientes. O foco principal desta dissertação é o estudo dessas relações em grafos. Nossa ênfase é sobre grafos orientados. Apresentamos o poderoso arcabouço poliédrico de Edmonds e Giles envolvendo fluxos submodulares, bem como o algoritmo de Frank para um caso especial desse arcabouço: o teorema de Lucchesi-Younger. Derivamos também diversas relações min-max sobre o empacotamento de conectores, desde o teorema de ramificações disjuntas de Edmonds até o teorema de junções disjuntas de Feofiloff-Younger e Schrijver. Apresentamos também uma resenha completa sobre as conjecturas de Woodall e sua versão capacitada, conhecida como conjectura de Edmonds-Giles. Derivamos ainda algumas relações min-max clássicas sobre emparelhamentos, T-junções e S-caminhos. Para tanto, usamos um teorema de Frank, Tardos e Sebö e um arcabouço bastante geral devido a Chudnovsky, Geelen, Gerards, Goddyn, Lohman e Seymour. Ao longo do texto, ilustramos vários aspectos recorrentes, como o uso de ferramentas da combinatória poliédrica, a técnica do descruzamento, o uso de funções submodulares, matróides e propriedades de troca, bem como alguns resultados envolvendo subestruturas proibidas. / Min-max relations are central objects in combinatorial optimization. They basically state that, in a given structure, the optimum value of a certain minimization problem equals the optimum value of a different, maximization problem. Relations of this kind provide good characterizations and polyhedral descriptions to several important problems and, moreover, they often come with efficient algorithms for the corresponding problems. Usually, such efficient algorithms are obtained naturally from the constructive proofs involved; even when that is not the case, these relations reveal enough of the combinatorial structure of the problem, leading to the development of efficient algorithms. The main focus of this dissertation is the study of these relations in graphs. Our emphasis is on directed graphs. We present Edmonds and Giles\' powerful polyhedral framework concerning submodular flows, as well as Frank\'s algorithm for a special case of this framework: the Lucchesi-Younger Theorem. We also derive several min-max relations about packing connectors, starting with Edmonds\' Disjoint Branchings Theorem and ending with Feofiloff-Younger and Schrijver\'s Disjoint Dijoins Theorem. We further derive some classical min-max relations on matchings, T-joins and S-paths. To this end, we use a theorem due to Frank, Tardos, and Sebö and a general framework due to Chudnovsky, Geelen, Gerards, Goddyn, Lohman, and Seymour. Throughout the text, we illustrate several recurrent themes, such as the use of tools from polyhedral combinatorics, the uncrossing technique, the use of submodular functions, matroids and exchange properties, as well as some results involving forbidden substructures.

Este trabalho apresenta uma nova estrutura matemática para a álgebra de caminhos, que permite analisar a convergência dos algoritmos de roteamento multi-restritivos hop-by-hop e, sob o ponto de vista da engenharia de tráfego e da Qualidade de Serviço (QoS) na arquitetura Generalized Multiprotocol Label Switching (GMPLS), garantir de maneira confiável a incorporação de novas métricas de roteamento aos algoritmos de roteamento baseados em múltiplas restrições. Baseando-se nessa nova álgebra de caminhos, são analisadas as propriedades de monotonicidade, isotonicidade e liberdade, conhecidas por garantir a convergência dos algoritmos de roteamento e, ao contrário do indicado na literatura até o momento, verifica-se que a propriedade de monotonicidade não e condição necessária e nem suficiente para garantir a convergência dos algoritmos de roteamento multi-restritivos hop-by-hop. Sendo assim, este trabalho propõe uma nova propriedade, denominada coerência, para a garantia da convergência do roteamento hop-by-hop e um novo algoritmo de roteamento hop-by-hop com convergência garantida. Para avaliar os resultados teóricos obtidos, s~ao analisados dois estudos de casos de aplicação do roteamento multi-restritivos hop-by-hop com o uso de uma ferramenta de simulação desenvolvida em MATLAB e baseada no algoritmo Eliminação de Loop pelo Nó de Destino (ELND) também proposto. Como resultado das simulações desses estudos de casos, verifica-se que as diferentes estratégias de otimização, necessárias as redes (GMPLS), impõem a necessidade de trabalhar com algoritmos de roteamento que permitam a definição de mais de duas métricas de roteamento com diferentes critérios de otimização para cada uma delas, comprovando, portanto, a necessidade do desenvolvimento e da continuação deste trabalho. / This work presents a new mathematical structure for paths algebra that allows the convergence analysis of hop-by-hop multi-constrained routing algorithms and, under the traffic engineering and quality of service perspectives in the Generalized Multiprotocol Label Switching (GMPLS) architecture, trustily ensures the aggregation of new routing metrics in a constrained-based routing. Based on this new paths algebra, we analyze the monotonicity, isotonicity and freeness properties, known as ensuring routing algorithms convergence, and despite of what has been indicated in the literature, we verified that the monotonicity property is not sufficient to ensure the hop-by-hop routing convergence. Therefore, this work proposes a new property, called coherence, as a necessary and sufficient condition to ensure it, as well as, a new multi-constrained hop-by-hop routing algorithm with ensured convergence. In order to evaluate the theoretical results obtained, two study cases of the hop-by-hop multi-constrained routing applications are analyzed in the present thesis by using the Eliminação de Loop pelo Nó de Destino (ELND) simulation tool, developed in MATLAB and also presented as a product of this work. As result of these study cases simulations, we verified that different optimization strategies, requested by the (GMPLS) networks, compel the use of routing algorithms that allow the specification of more than two routing metrics with different optimization criteria for each one of them, thus proving the necessity of this work and its continuation.

Submitted by Rosivalda Pereira (mrs.pereira@ufma.br) on 2017-08-25T20:24:28Z No. of bitstreams: 1 JandersonFreitas.pdf: 2087995 bytes, checksum: e49b1008df3093f81aeb841870a06df9 (MD5) / Made available in DSpace on 2017-08-25T20:24:28Z (GMT). No. of bitstreams: 1 JandersonFreitas.pdf: 2087995 bytes, checksum: e49b1008df3093f81aeb841870a06df9 (MD5) Previous issue date: 2017-05-08 / The paper presents problem solving using Graph Theory and Euler’s Theorem. The research performs specific activities in high school involving graphs in various applications of the Euler relation as a problem solving method with Graph Theory. The relationship of Euler is presented in a Geometric view and by the graphs planning. The research proposes a link between the students ’daily problems with the modeling of problem situations by the Graph Theory, specifically the planar graphs solved with the implementation of Euler’ s Theorem focused on the teaching of basic mathematics. Applications of Graph Theory are shown in solving problems with the bridges of the city of Barra do Corda and the students’ school life. / O trabalho apresenta a resolução de problemas utilizando a Teoria dos Grafos e o Teorema de Euler. Uma pesquisa que executa atividades específicas no ensino médio envolvendo grafos em várias aplicações da relação de Euler como método de resolução de problemas com Teoria dos Grafos. A relação de Euler é apresentada em uma visão Geométrica e pela planificação dos grafos. Propondo um elo entre os problemas do cotidiano dos alunos com a modelagem de situações problema pela Teoria dos Grafos, especificamente os grafos planares resolvidos com a implementação do Teorema de Euler voltado ao ensino de matemática básica. São mostradas aplicações da Teoria dos Grafos na resolução de problemas com as pontes da cidade de Barra do Corda e da vida escolar dos alunos.

Submitted by FLAVIA FERNANDA FAVARO null (flaviafavaro@hotmail.com) on 2018-01-10T03:14:21Z No. of bitstreams: 1 A Teoria dos Grafos e sua abordagem na sala de aula com recursos educacionais digitais.pdf: 2731904 bytes, checksum: 49a548fa505952226f589c5471f9b496 (MD5) / Approved for entry into archive by Adriana Aparecida Puerta null (dripuerta@rc.unesp.br) on 2018-01-10T18:21:25Z (GMT) No. of bitstreams: 1 favaro_ff_me_rcla.pdf: 2692020 bytes, checksum: c889310c873cab619e98b36f809e81c0 (MD5) / Made available in DSpace on 2018-01-10T18:21:25Z (GMT). No. of bitstreams: 1 favaro_ff_me_rcla.pdf: 2692020 bytes, checksum: c889310c873cab619e98b36f809e81c0 (MD5) Previous issue date: 2017-12-18 / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior (CAPES) / Neste trabalho estudamos a Teoria dos Grafos compreendendo suas definições, resultados e algumas aplicações como O Problema das Pontes de Köningsberg, O Problema Chinês do Carteiro, O Problema do Caixeiro Viajante e O Teorema das Quatro e das Cinco Cores. Com o uso da Coleção M3 - Matemática Multimídia, que contém recursos educacionais em formatos digitais, aplicamos as atividades sugeridas aos alunos do segundo ano do Ensino Médio de uma escola particular localizado na cidade de São Pedro - SP. As atividades mostraram que, apesar da Teoria dos Grafos não constar no currículo regular do Ensino Médio, sua aplicação para este grupo de alunos foi positiva, uma vez que os alunos sentiram-se motivados com o conteúdo abordado na forma digital e com sua aplicação ao estudo de Matrizes. Concluímos assim que, nos dias atuais a ligação do processo de ensino aprendizagem com os softwares educacionais podem proporcionar, tanto para os professores quanto para os alunos, uma forma mais prazerosa e eficaz de obter conhecimento em Matemática. / In this work, we study Graph Theory, meaning its definitions, results e some applications such as the Köningsberg bridge problem, the chinese postman problem, the travelling salesman problem and the four color theorem as well as the five color theorem. By using the M3 - Matemática Multimídia Series, which contains educational resources in digital form, we applied the suggested activities to second year high school students form a private school located at the city of São Pedro – São Paulo State. The activities showed that, although Graph Theory is not part of the high school regular curriculum, its application to this group of students was positive, since the students felt themselves motivated by the digital approach to its contents and its applications to the study of Matrices. We conclude that, nowadays, the connection between the teaching processes and educational softwares can provide, to the teachers as well as to the students, a more pleasurable and efficient way to obtain knowledge in Mathematics.