Submitted by Julio Frederico Hruza Alqueres (julio.alqueres@gmail.com) on 2015-06-30T15:53:58Z No. of bitstreams: 1 Tese Final - Julio Alqueres.pdf: 5909230 bytes, checksum: 9cda987329a8e563391dae65ea6d53b0 (MD5) / Approved for entry into archive by Janete de Oliveira Feitosa (janete.feitosa@fgv.br) on 2015-07-02T13:29:27Z (GMT) No. of bitstreams: 1 Tese Final - Julio Alqueres.pdf: 5909230 bytes, checksum: 9cda987329a8e563391dae65ea6d53b0 (MD5) / Approved for entry into archive by Marcia Bacha (marcia.bacha@fgv.br) on 2015-07-03T16:48:46Z (GMT) No. of bitstreams: 1 Tese Final - Julio Alqueres.pdf: 5909230 bytes, checksum: 9cda987329a8e563391dae65ea6d53b0 (MD5) / Made available in DSpace on 2015-07-03T16:49:01Z (GMT). No. of bitstreams: 1 Tese Final - Julio Alqueres.pdf: 5909230 bytes, checksum: 9cda987329a8e563391dae65ea6d53b0 (MD5) Previous issue date: 2015-04-06 / Nos últimos anos, a relevância da Teoria dos Grafos na descrição da rela ção entre indiví duos cresceu signifi cativamente, contribuindo para a ascensão do fenômeno das redes sociais. Sua importância tem permitido a explora ção polí tico-econômica de informa ções escondidas em sua estrutura. Assumindo que um parlamentar maximiza sua utilidade ao fortalecer o seu partido e o estado que representa, construímos uma rede política baseada no Congresso Brasileiro, o que permite a identificação de elementos da Teoria do Seletorado. Através de técnicas de Processamento de Linguagem Natural aplicadas à diferentes fontes de notícia, é possível atualizar a rede de forma a identificar alterações na estrutura de poder do sistema político brasileiro.

Orientador: Érika Capelato / Banca: Thiago de Melo / Banca: Camila Fernanda Bassetto / Resumo: 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 / Abstract: 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 / Mestre

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.

Made available in DSpace on 2015-04-14T13:56:33Z (GMT). No. of bitstreams: 1 463003.pdf: 2663394 bytes, checksum: 0158a49caa9b116197cb1f3a76c44980 (MD5) Previous issue date: 2014-08-22 / Resting State functional Magnetic Resonance Imaging (rs-fMRI) provides information about the functional connectivity of brain areas. However, prior to calculating the functional connectivity of the brain, there is a choice of several preprocessing steps that need to be selected. A critical source of variation between studies arises from distinct preprocessing approaches prior to the functional connectivity analysis. Therefore, a study to examine the reliability of different methods for pre-processing data from rs-fMRI is necessary. In this study, seven preprocessing strategies were tested and the reliability was evaluated between them in Graph Theoretical (GT). The sample used in this study is from a public database and consists of control subjects. Measures of GT were calculated using different strategies, after applying a method of subdividing the brain into 190 regions of interest. The following measures were calculated: global efficiency, characteristic path length, clustering coefficient and local efficiency. The results indicate that there is a significant difference in measurements of GT depending on the preprocessing strategy selected. It was also found that noise estimation parameters are correlated with GT measures. Moreover, it is observed that the level of thresholding chosen in the connectivity matrix can affect the measurements of GT, therefore further studies regarding this topic are needed. It was concluded, based on the sample used in this work that the method of scrubbing by outliers could increase the reliability of measurements of GT and reduce dependence on the movement of the patient's head. / A Resson?ncia Magn?tica Funcional no estado de repouso (rs-fMRI, do ingl?s resting state functional Magnetic Resonance) permite obter informa??es a respeito das ?reas de conectividade funcional do c?rebro. Por?m, a visualiza??o dessa conectividade s? ? poss?vel ap?s aplicar uma s?rie de etapas de processamento de imagens antes que se possa avaliar a conectividade cerebral. Considerando a limita??o na quantifica??o dos dados de rs-fMRI, e sabendo que uma fonte de varia??o cr?tica para a compara??o entre os estudos ? o fato de cada um deles remover, incluir ou mudar par?metros nos passos de pr?-processamento de rs-fMRI, ? necess?rio um estudo para analisar a confiabilidade de diferentes metodologias de pr?processamento de dados de rs-fMRI. Para tanto, a Teoria dos Grafos (TG) foi utilizada como par?metro final para avaliar a conectividade. Neste presente trabalho, foram testadas sete estrat?gias de pr?-processamento e foi avaliada a confiabilidade entre elas quando s?o feitas medidas de TG. A amostra utilizada neste trabalho ? de uma base de dados p?blica e ? composta por indiv?duos controle. As medidas de TG foram calculadas nas diferentes estrat?gias, ap?s aplicar um m?todo de parcelamento do c?rebro em 190 regi?es. Foram calculadas as seguintes medidas: efici?ncia global, comprimento do caminho caracter?stico, coeficiente de agrupamento e efici?ncia local. Os resultados indicaram que existe uma diferen?a significativa nas medidas de teoria dos grafos quando o pr?-processamento ? feito de diferentes maneiras. Foi encontrado tamb?m que par?metros de estimativa de ru?do s?o correlacionados com as medidas de TG. Al?m disso, observa-se que o n?vel de limiariza??o escolhido na matriz de conectividade pode afetar significativamente as medidas de TG, sendo necess?rio um estudo mais aprofundado a respeito deste tema. Concluiu-se, baseado na amostra utilizada neste trabalho, que o m?todo de scrubbing por outliers pode aumentar a confiabilidade das medidas de TG e reduzir a sua depend?ncia com o movimento da cabe?a do paciente.

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.