Дисертації з теми "NUMEROUS ALGORITHMS"

CoordenaÃÃo de AperfeÃoamento de Pessoal de NÃvel Superior
Desde o advento da escrita, o envio de mensagens secretas tem sido uma importante maneira de guardar sigilo de informaÃÃes confidenciais. A arte de elaborar mensagens a partir de cÃdigos secretos surge na figura da criptografia que, com o passar do tempo, estende os seus serviÃos Ãs transaÃÃes comerciais realizadas pela internet. O principal algoritmo utilizado pela internet recebe o nome de RSA. Assim, a criptografia RSA codifica nÃmeros de cartÃes de crÃditos, senhas de bancos, nÃmeros de contas e utiliza para isso elementos de uma importante Ãrea da MatemÃtica: a Teoria dos NÃmeros.
Since the advent of writing, sending secret messages has been an important way to maintain confidentiality of sensitive information. The art of crafting messages from secret codes appears in the figure of encryption that over time extends its services to commercial transactions over the Internet. The main algorithm used by the internet is called RSA. Thus, the RSA Encryption encodes credit card numbers, bank passwords, account numbers and uses for that elements of an important area of mathematics: number theory.

Orientador: Lee Luan Ling
Dissertação (mestrado) - Universidade Estadual de Campinas, Faculdade de Engenharia Eletrica
Made available in DSpace on 2018-07-21T03:38:05Z (GMT). No. of bitstreams: 1 Gomes_NatanaelRodrigues_M.pdf: 3843291 bytes, checksum: ea1c445465616bedc519575e7960e649 (MD5) Previous issue date: 1996
Resumo: A principal dificuldade em reconhecimento de caracteres manuscritos está em desenvolver métodos que possibilitem um ótimo índice de reconhecimento, apesar da grande variabilidade dos caracteres. Este trabalho apresenta um sistema para reconhecimento de numerais manuscritos desconectados, baseado na análise da topologia e distribuição pictorial de numerais e no emprego da rede de Hopfield discreta como memória associativa. O processo de classificação de numerais é dividido em dois estágios. No primeiro estágio, o numeral desconhecido é classificado de acordo com características extraídas de sua topologia e distribuição pictorial. Caso isto não seja possível, devido a distorções e ruídos na imagem do numeral desconhecido, a classificação é efetuada no segundo estágio de classificação do sistema, via rede de Hopfield. A rede de Hopfield é implementada de dois modos. No primeiro modo, a rede tem seus pesos calculados pelo método da projeção, no segundo modo, a rede tem os pesos calculados pelo método de síntese para sistemas lineares operando em modo saturado (LSSM). O sistema é testado com 1500 numerais manuscritos, sendo obtido uma taxa de 85% de reconhecimento com o sistema utilizando, no segundo estágio, a rede de Hopfield implementada conforme o primeiro modo. Uma taxa de reconhecimento de 84,4% é obtida com o sistema utilizando, no segundo estágio, a rede de Hopfield implementada de acordo com o segundo modo
Abstract: The main difficultyin handwritten character recognition consists in developing methods that provide a high recognition rate, although of the large degree of variability of the characteres. This work presents a system for recognition of disconnected handwritten numeraIs, based in analysis of the topology and distribution of pixels from the numerals, and application of a discrete Hopfield neural net used as associative memory. ln the system, the process of classification is divided in two stages. ln the first stage, the unknown numeral is classified considering features extracted from its topology and distribution of pixels. lf it is not possible, due to distortions and noise in numeral image, the classificationis effectuated in the second stage, via Hopfield netoThe Hopfield net is implemented of two manners. ln the first manner, the net has weights calculated by projection method and, in the second manner, the net has weights calculated by sinthesis procedures to linear systems operating in the saturated mode (LSSM systems). The system is tested with 1500 handwritten numerals. A recognition rate over 85% is obtained with the system making use in the second stage of the Hopfield net implemented by the first manner. A recognition rate over 84,4% is obtained with the system making use in the second stage of the Hopfield net implemented by the second manner
Mestrado
Mestre em Engenharia Elétrica

Orientador: Fabio Violaro
Tese (doutorado) - Universidade Estadual de Campinas, Faculdade de Engenharia Eletrica e de Computação
Made available in DSpace on 2018-08-06T10:44:21Z (GMT). No. of bitstreams: 1 Yared_GlaucoFerreiraGazel_D.pdf: 5774867 bytes, checksum: 49a79d9495ce25c8a69ca34858a956ee (MD5) Previous issue date: 2006
Resumo: Atualmente os sistemas de reconhecimento de fala baseados em HMMs são utilizados em diversas aplicações em tempo real, desde telefones celulares até automóveis. Nesse contexto, um aspecto importante que deve ser considerado é a complexidade dos HMMs, a qual está diretamente relacionada com o custo computacional. Assim, no intuito de permitir a aplicação prática do sistema, é interessante otimizar a complexidade dos HMMs, impondo-se restrições em relação ao desempenho no reconhecimento. Além disso, a otimização da topologia é importante para uma estimação confiável dos parâmetros dos HMMs. Os trabalhos anteriores nesta área utilizam medidas de verossimilhança para a obtenção de sistemas que apresentem um melhor compromisso entre resolução acústica e robustez. Este trabalho apresenta o novo Algoritmo para Eliminação de Gaussianas (GEA), o qual é baseado em uma análise discriminativa e em uma análise interna, para a determinação da complexidade mais apropriada para os HMMs. O novo método é comparado com o Critério de Informação Bayesiano (BIC), com um método baseado em medidas de entropia, com um método discriminativo para o aumento da resolução acústica dos modelos e com os sistemas contendo um número fixo de Gaussianas por estado
Abstract: Nowadays, HMM-based speech recognition systems are used in many real time processing applications, from cell phones to auto mobile automation. In this context, one important aspect to be considered is the HMM complexity, which directly determines the system computational load. So, in order to make the system feasible for practical purposes, it is interesting to optimize the HMM size constrained to a minimum acceptable recognition performance. Furthermore, topology optimization is also important for reliable parameter estimation. Previous works in this area have used likelihood measures in order to obtain models with a better compromise between acoustic resolution and robustness. This work presents the new Gaussian Elimination Algorithm (GEA), which is based on a discriminative analysis and on an internal analysis, for determining the more suitable HMM complexity. The new approach is compared to the classical Bayesian Information Criterion (BIC), to an entropy based method, to a discriminative-based method for increasing the acoustic resolution of the HMMs and also to systems containing a fixed number of Gaussians per state
Doutorado
Telecomunicações e Telemática
Doutor em Engenharia Elétrica

Automatinis transporto priemonių registracijos numerio atpažinimas atlieka svarbų vaidmenį daugelyje programinių paketų, taikomų tiek valstybinėse institucijose, tiek ir privačiose kompanijose, kuriuose yra naudojamos įvairios atpažinimo algoritmų technologijos. Tačiau net ir dabar neįmanoma sukurti idealiai veikiančios sistemos, kuri palieka laisvę efektyviausių algoritmų paieškai. Šio tiriamojo darbo tikslas yra išanalizuoti alternatyvius automobilio numerio lokalizacijos ir kitų atpažinimo etapų algoritmus, jų efektyvumą bei adaptyvumą. Analizė atliekama juos realizuojant ir atliekant tyrimus su testiniais duomenimis bei iš jų gautais rezultatais. Iš realizuotos alternatyvių atpažinimo algoritmų sistemos gauti rezultatai parodė, kad kiekviena atpažinimo proceso grandis yra jautri įvairiems faktoriams, kurių kitimas lemia tarpinių bei galutinių rezultatų variaciją.
Automatic license plate recognition plays an important role in numerous applications and a number of techniques have been proposed for public institutions or private companies. However, even now it is impossible to design a perfect and operational recognition system. It still leaves a space for creativity and research of the most effective algorithms. The main objective of this dissertation is to analyze alternatives of licese plate localization and other stages of recognition, their efficiency and adaptability. Selected means of this research are such as implementation of algorithms, analysis of testing data and test results. Every stage of recognition process is extremely sensitive to different factors which determinate variation of transitional and final results. This was proven by analysis of alternative algorithms functionality.

Automatinis transporto priemonių registracijos numerio atpažinimas atlieka svarbų vaidmenį daugelyje programinių paketų, taikomų tiek valstybinėse institucijose, tiek ir privačiose kompanijose, kuriuose yra naudojamos įvairios atpažinimo algoritmų technologijos. Tačiau net ir dabar neįmanoma sukurti idealiai veikiančios sistemos, kuri palieka laisvę efektyviausių algoritmų paieškai. Šio tiriamojo darbo tikslas yra išanalizuoti alternatyvius automobilio numerio lokalizacijos ir kitų atpažinimo etapų algoritmus, jų efektyvumą bei adaptyvumą. Analizė atliekama juos realizuojant ir atliekant tyrimus su testiniais duomenimis bei iš jų gautais rezultatais. Iš realizuotos alternatyvių atpažinimo algoritmų sistemos gauti rezultatai parodė, kad kiekviena atpažinimo proceso grandis yra jautri įvairiems faktoriams, kurių kitimas lemia tarpinių bei galutinių rezultatų variaciją.
Automatic license plate recognition plays an important role in numerous applications and a number of techniques have been proposed for public institutions or private companies. However, even now it is impossible to design a perfect and operational recognition system. It still leaves a space for creativity and research of the most effective algorithms. The main objective of this dissertation is to analyze alternatives of licese plate localization and other stages of recognition, their efficiency and adaptability. Selected means of this research are such as implementation of algorithms, analysis of testing data and test results. Every stage of recognition process is extremely sensitive to different factors witch determinate variation of transitional and final results. This was proven by analysis of alternative algorithms functionality.

Submitted by Luciana Ferreira (lucgeral@gmail.com) on 2015-10-22T13:38:57Z No. of bitstreams: 2 Dissertação - Lourival Carlos Cunha Junior - 2015.pdf: 8702813 bytes, checksum: 307cfb19927718cfa7a667f109f4768f (MD5) license_rdf: 23148 bytes, checksum: 9da0b6dfac957114c6a7714714b86306 (MD5)
Approved for entry into archive by Luciana Ferreira (lucgeral@gmail.com) on 2015-10-22T13:42:02Z (GMT) No. of bitstreams: 2 Dissertação - Lourival Carlos Cunha Junior - 2015.pdf: 8702813 bytes, checksum: 307cfb19927718cfa7a667f109f4768f (MD5) license_rdf: 23148 bytes, checksum: 9da0b6dfac957114c6a7714714b86306 (MD5)
Made available in DSpace on 2015-10-22T13:42:02Z (GMT). No. of bitstreams: 2 Dissertação - Lourival Carlos Cunha Junior - 2015.pdf: 8702813 bytes, checksum: 307cfb19927718cfa7a667f109f4768f (MD5) license_rdf: 23148 bytes, checksum: 9da0b6dfac957114c6a7714714b86306 (MD5) Previous issue date: 2015-05-25
Coordenação de Aperfeiçoamento de Pessoal de Nível Superior - CAPES
This dissertation aims to analyze how the use of mathematical tricks, educational games and alternative algorithms for multiplication and Division of integers contribute to learning of multiplication and Division operations between positive integers. Research participants were students of a class of adult and youth education of the 2o segment of the Central Penitentiary Progression of Distrito Federal (CPP-DF). The analysis of the results was made from questionnaires answered by the students and observations by the teacher during class. The introduction of mathematical operations took place initially by mathematical tricks, then were presented alternative ways to perform them later manipulation of new algorithms, unraveling the tricks and finally organizing with mathematical games. The participants demonstrated commitment, dedication and interest in the tricks, games and alternative algorithms. The objective of this work was achieved. We realized that there was in fact an improvement in pupils ’ learning.
Esta dissertação tem como objetivo analisar como o uso de truques matemáticos, jogos pedagógicos e algoritmos alternativos para a multiplicação e divisão de números inteiros contribuem para o aprendizado das operações multiplicação e divisão entre números inteiros positivos. Os participantes da pesquisa foram alunos de uma turma de Educação de Jovens e Adultos do 2o Segmento do Centro de Progressão Penitenciária do Distrito Federal (CPP-DF). A análise dos resultados foi feita a partir de questionários respondidos pelos alunos e observações realizadas pelo professor durante as aulas. A introdução das operações matemáticas ocorreu inicialmente por truques matemáticos, em seguida foram apresentadas formas alternativas de realizá-las, posteriormente a manipulação dos novos algoritmos, desvendando os truques e finalmente sistematizando com jogos matemáticos. Os participantes demonstraram empenho, dedicação e interesse em relação aos truques, jogos e aos algoritmos alternativos. O objetivo do trabalho foi alcançado. Percebemos que houve de fato uma melhoria na aprendizagem dos alunos.

Made available in DSpace on 2014-06-11T19:27:09Z (GMT). No. of bitstreams: 0 Previous issue date: 2013-08-16Bitstream added on 2014-06-13T20:35:15Z : No. of bitstreams: 1 sousa_anl_me_rcla.pdf: 535933 bytes, checksum: 76cd9ddeb4c3e3c566bae5395dfcaa14 (MD5)
Este trabalho apresenta a criptografia, que é estudada desde a antiguidade e suas técnicas hoje consistem basicamente em conceitos matemáticos. Os números inteiros prestam um papel importante na criptografia de chave pública RSA, onde são apresentados alguns conceitos importantes, propriedades e resultados desse conjunto, destacando as relações com os números primos, a função de Euler e a operação módulo, conhecida como problema do logaritmo discreto. Apresentam-se os fundamentos da Criptografia de Chave Pública RSA, em que a base é a cifra assimétrica, mostrando a garantia da privacidade e assinatura das mensagens. Finaliza-se com a ideia do protocolo de criptografia RSA, a construção de um sistema de correios eletrônico, cuja essência é o método para estabelecer uma criptografia de chave pública RSA, baseada no conceito apresentado por Diffie e Hellman
This dissertation presents Cryptography, which is studied since the ancient times and whose techniques consist basically of mathematical concepts. The integers play an important role on the Public Key Cryptography RSA, for which are presented some important results and properties of this set, emphasizing its relations with prime numbers, Euler’s totient function and the modulo operation, also known as the problem of discrete logarithm. We present the foundations of the Public Key Cryptography RSA, whose basis is the asymmetric cipher, showing the privacy security of the messages. It ends with the idea of the RSA cryptography protocol, a construction of an electronic mail system, whose gist lies in the method used to establish a Public Key Criptography system RSA, based on the concept presented by Diffie and Hellman

Orientador: Eliris Cristina Rizziolli
Banca: Aldicio José Miranda
Banca: Henrique Lazari
Resumo: Este trabalho apresenta a criptografia, que é estudada desde a antiguidade e suas técnicas hoje consistem basicamente em conceitos matemáticos. Os números inteiros prestam um papel importante na criptografia de chave pública RSA, onde são apresentados alguns conceitos importantes, propriedades e resultados desse conjunto, destacando as relações com os números primos, a função de Euler e a operação módulo, conhecida como problema do logaritmo discreto. Apresentam-se os fundamentos da Criptografia de Chave Pública RSA, em que a base é a cifra assimétrica, mostrando a garantia da privacidade e assinatura das mensagens. Finaliza-se com a ideia do protocolo de criptografia RSA, a construção de um sistema de correios eletrônico, cuja essência é o método para estabelecer uma criptografia de chave pública RSA, baseada no conceito apresentado por Diffie e Hellman
Abstract: This dissertation presents Cryptography, which is studied since the ancient times and whose techniques consist basically of mathematical concepts. The integers play an important role on the Public Key Cryptography RSA, for which are presented some important results and properties of this set, emphasizing its relations with prime numbers, Euler's totient function and the modulo operation, also known as the problem of discrete logarithm. We present the foundations of the Public Key Cryptography RSA, whose basis is the asymmetric cipher, showing the privacy security of the messages. It ends with the idea of the RSA cryptography protocol, a construction of an electronic mail system, whose gist lies in the method used to establish a Public Key Criptography system RSA, based on the concept presented by Diffie and Hellman
Mestre

Orientador: Alice Maria B. H. Tokarnia
Dissertação (mestrado) - Universidade Estadual de Campinas, Faculdade de Engenharia Eletrica e de Computação
Made available in DSpace on 2018-08-07T23:40:08Z (GMT). No. of bitstreams: 1 Silva_RogerioSigrist_M.pdf: 816659 bytes, checksum: 206ce45bc9176489805fd6c7f8f0e260 (MD5) Previous issue date: 2006
Resumo: Este trabalho descreve três algoritmos para a síntese de sistemas embutidos atendendo à restrição de desempenho representada pela taxa de chegada dos dados, através de uma estrutura de pipeline de processadores para execução das tarefas, ao mesmo tempo em que minimizam diferentes parâmetros de qualidade dos sistemas: número de processadores; custo e latência total. Os algoritmos realizam o particionamento hardware-software das tarefas, a alocação dos processadores, o mapeamento e escalonamento das tarefas. A alocação de processadores e o mapeamento e escalonamento de tarefas são problemas classificados como NP-Completo e, portanto, foram aplicados métodos heurísticos para suas resoluções. Como exemplos de aplicação são apresentados os pipelines sintetizados pelos algoritmos para grafos sintéticos e para um compressor de áudio digital (AC3). Os pipelines sintetizados atingem métricas de qualidade superiores a outros algoritmos publicados
Abstract: This work presents three heuristics for sinthesizing pipelined embedded systems that satisfy a throughput constraint derived from the maximum input data are adopting a pipeline structure of processors while minimizing system quality parameters: cost, number of processors, or number of stages. The algorithms perform tasks hardware-software partitioning, processors allocation and task mapping and scheduling. Since processors allocation and task mapping and scheduling are NP-Complete problems, heuristics methods were applied. The examples present the pipelines synthesized by the algorithms for large synthetic systems comparing the quality parameters minimization results and for a real audio compressor (AC3) application. The pipelines reached quality metrics higher than other published algorithms
Mestrado
Engenharia de Computação
Mestre em Engenharia Elétrica

Orientador: Rita de Cássia Pavan Lamas
Banca: Rúbia Barcelos Amaral Schio
Banca: Évelin Meneguesso Barbaresco
Resumo: No decorrer dos anos, pelas experiências vivenciadas em sala de aula, nos Anos Finais do Ensino Fundamental e no Ensino Médio, cada vez mais foram observadas dificuldades dos alunos nos cálculos simples, em problemas na matemática e na física. Erros conceituais, nos algoritmos, motivaram-nos a escrever este trabalho para auxiliar professores no processo ensino e aprendizagem das quatro operações no conjunto dos números naturais, a fim de amenizar as dificuldades dos alunos. O objetivo do trabalho é avaliar e diagnosticar dificuldades nos cálculos que envolvem as operações fundamentais e básicas da matemática, aprimorando a forma de ensiná-las aos alunos. Conceitos importantes serão apresentados, como o sistema de numeração decimal, a definição do conjunto dos números naturais e as quatro operações matemáticas. Os algoritmos da decomposição e usual serão explorados com o uso do ábaco de papel e com o material dourado, destacando-se as propriedades associativa e comutativa da adição, assim como as distributiva, associativa e comutativa da multiplicação. Considerando as dificuldades apresentadas no diagnóstico, propõem-se atividades com o material dourado explorando conceitos e instigando o uso dos algoritmos para a compreensão das trocas das ordens, quando necessário. Em síntese, este trabalho apresenta uma metodologia alternativa para melhorar o desempenho dos alunos nos cálculos que envolvem as quatro operações
Abstract: Over the years, experiences in the classroom, the Final Years of Elementary School and High School have seen more and more difficulties for students in simple calculations, problems in mathematics and in physics. Conceptual errors in the algorithms motivated us to write this work to help teachers in the teaching and learning process of the four operations in the set of natural numbers in order to ease the students' difficulties. The purpose of this paper is to evaluate and diagnose difficulties in calculations involving fundamental and basic mathematical operations, improving the way students are taught. Important concepts will be presented, such as the decimal numbering system, the definition of the set of natural numbers and the four mathematical operations. The usual decomposition algorithms will be explored with the use of the paper abacus and the gold material, emphasizing the associative and commutative properties of addition, as well as the distributive, associative and commutative multiplication. Considering the difficulties presented in the diagnosis, activities are proposed with the golden material exploring concepts and instigating the use of the algorithms to understand the order exchanges, when necessary. In summary, this paper presents an alternative methodology to improve students' performance in the calculations involving the four operations
Mestre

Submitted by Divisão de Documentação/BC Biblioteca Central (ddbc@ufam.edu.br) on 2018-04-06T15:56:31Z No. of bitstreams: 2 Dissertação - Daniel Sombra.pdf: 863251 bytes, checksum: 2067dbe00da7848645ffcf735b6a3068 (MD5) license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5)
Approved for entry into archive by Divisão de Documentação/BC Biblioteca Central (ddbc@ufam.edu.br) on 2018-04-06T15:56:42Z (GMT) No. of bitstreams: 2 Dissertação - Daniel Sombra.pdf: 863251 bytes, checksum: 2067dbe00da7848645ffcf735b6a3068 (MD5) license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5)
Made available in DSpace on 2018-04-06T15:56:42Z (GMT). No. of bitstreams: 2 Dissertação - Daniel Sombra.pdf: 863251 bytes, checksum: 2067dbe00da7848645ffcf735b6a3068 (MD5) license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) Previous issue date: 2018-03-22
CAPES - Coordenação de Aperfeiçoamento de Pessoal de Nível Superior
Number theory is branch from Mathematics hardly ever explored in elementary and middle school, almost nonexistent in high school. Its implementations and features in elementary and middle school narrow in divisibility principals, greatest common factor (GCF) and Euclidean algorithm. All presented in a plain and timid way. Nevertheless, number theory is a vast field in Mathematics, tightly related to algebra results. It consists of powerful tools to the resolutions of problems such as: Olympics, properties display and indirect implementations in other sciences. In this paper, it will be presented in a fair and concise, the most fundamental outcome related to number theory which do not need further studies to be understood. One familiarity with the properties of integers, the aspects of divisibility seen in elementary and middle school and notions of mathematical proof are sufficient to the knowledge of the main idea of this paper. The major results presented were: Euclidean algorithm, fundamental theorem of arithmetic, Fermat, Wilson and Euler’s theorem and Euler’s totient function . During demos, it will be presented exercises that exemplifies theory. Besides, there are 2 chapters concerning the resolution of Olympics problems, with the intentions to explore, in a smart way, the concepts presented during theory.
A teoria dos números é um ramo da Matemática praticamente inexplorado no ensino básico e quase inexistente Ensino Médio. As aplicações e propriedades no Ensino Fundamental se restringem aos critérios de divisibilidade, ao máximo divisor comum e ao Algoritmo de Euclides, apresentados de forma bastante elementar e tímida. Contudo a teoria dos números é um ramo bastante vasto dentro da Matemática, fortemente relacionada à resultados da Álgebra. Nela constituem-se ferramentas muito poderosas para a resolução de problemas de olimpíadas, demonstração de propriedades e aplicações indiretas em outras ciências. Neste trabalho são apresentados e demonstrados, de forma clara e concisa, os resultados mais fundamentais referentes à teoria dos números, os quais não precisam de estudos avançados na área para serem compreendidos. Uma familiaridade com as propriedades dos números inteiros, os aspectos de divisibilidade vistos na educação básica e noções de demonstração matemática são suficientes para que o leitor compreenda o escopo deste trabalho. Os principais resultados apresentados são: o Algoritmo de Euclides, o Teorema Fundamental da Aritmética, os Teoremas de Fermat, Wilson e Euler e a função de Euler. No transcorrer das demonstrações são apresentados exercícios que exemplificam a teoria. Além disso, são dedicados dois capítulos para resolução de problemas olímpicos, com a intenção de explorar de forma inteligente os conceitos apresentados no transcorrer da teoria.

With the exponential increase in the data available on the internet for a single domain, it is difficult to understand the gist of a whole document without reading the whole document. Automatic Text Summarization reduces the content of the document by presenting important key points from the data. Extracting the major points from the document is easier and requires less machinery than forming new sentences from the available data. Research in this domain started nearly 50 years ago from identifying key features to rank important sentences in a text document. The main aim of text summarization is to obtain human quality summarization, which is still a distant dream. Abstractive Summarization techniques uses dynamic wordnet corpus to produce coherent and succinct summaries. Automatic text summarization has applications in various domains including medical research, legal domain, doctoral research, documents available on internet etc. To serve the need of text summarization, numerous algorithms based on different content selection and features using different methodologies are made in last half century. Research started from Single document summarization has shifted to Multi-document summarization in last few decades in order to save more time and compressing the same domain documents at once. Here, An analysis is presented on the Single document and Multi-document summarization algorithms on different domain datasets.

碩士
國立成功大學
資訊工程學系碩博士班
101
Pattern matching plays an important role in Network Intrusion Detection System (NIDS) which is widely used in protecting computers from malicious attacks. With the rapid expansion of the network, the traditional single-core single-threaded CPU based algorithms have been unable to load demand, so it is necessary to accelerate pattern matching algorithm through hardware. GPU is a low cost and high scalability choice. With the development of Compute Unified Device Architecture (CUDA) technique by Nvdia, CUDA can promote the programmability of GPU program and let the role of GPU not only in executing graphical computing, but support the Single Instruction Multiple Thread (SIMT) big data computation. It can accelerate the speed of pattern matching effectively. In this thesis, we propose Multi-Byte Multi-Thread AC (MBMTAC) algorithm which is based on the famous Aho-Corasick (AC) algorithm and the Parallel Failureless-AC (PFAC) algorithm that improves the AC algorithm on GPU. (1) Base on the concept that let each byte of input stream as a start position and assign one thread for a start position to execute pattern matching, we extend it to matching multiple characters at once. The offset of each pattern does not need to be considered when establishing the data structure. Therefore, the problem of large amounts of additional states and transitions on CPU is solved. (2) Based on the concept, we do not need to consider the backward transitions, self-loops and the failure functions. Hence, the transition table becomes very sparse. We use a perfect hash scheme to compress the transition table. The memory usage of MBMTAC is only 0.19% of the PFAC needs. (3) By utilizing the characteristic of CUDA, we optimize the MBMTAC data structure so that the throughput can reach 33.4 Gb/s.

In this work we calculate the binding energies and root-mean-square radii for A−body nuclear bound state systems, where A ≥ 3. To study three−body systems, we employ the three−dimensional differential Faddeev equations with nucleon-nucleon semi-realistic potentials. The equations are solved numerically. For this purpose, the equations are transformed into an eigenvalue equation via the orthogonal collocation procedure using triquintic Hermite splines. The resulting eigenvalue equation is solved using the Restarted Arnoldi Algorithm. Ground state binding energies of the 3H nucleus are determined. For A > 3, the Potential Harmonic Expansion Method is employed. Using this method, the Schr¨odinger equation is transformed into coupled Faddeev-like equations. The Faddeevlike amplitudes are expanded on the potential harmonic basis. To transform the resulting coupled differential equations into an eigenvalue equation, we employ again the orthogonal collocation procedure followed by the Gauss-Jacobi quadrature. The corresponding eigenvalue equation is solved using the Renormalized Numerov Method to obtain ground state binding energies and root-mean-square radii of closed shell nuclei 4He, 8Be, 12C, 16O and 40Ca.
Physics
M. Sc. (Physics)