Vzporedni algoritmi za iskanje nizov

Abstract

Keywords

Data

Language:	Slovenian
Year of publishing:	2012
Typology:	2.11 - Undergraduate Thesis
Organization:	UL FRI - Faculty of Computer and Information Science
Publisher:	[T. Hočevar]
UDC:	004.021(043.2)
COBISS:	9390420
Views:	66
Downloads:	3
Average score:	0 (0 votes)
Metadata:

Other data

Secondary language:	English
Secondary title:	Parallel string matching algorithms
Secondary abstract:	This thesis presents different string searching algorithms. The string searching or string matching problem is one of the most basic problems on strings. It resurfaced with the development of bioinformatics and the need for DNA sequence analysis. It also presents a foundation for solving other, more complex string problems. First, we describe classical algoritms with linear time complexity such as Knuth-Morris-Pratt and Rabin-Karp. Then we turned our attention to the possibilites of parallelization. We present a simple parallelization scheme which finds the pattern in a string of size N in O(sqrt(N)) time on O(sqrt(N)) processors and a more complex Vishkin algoritm which solves it in O(log(N)) time. The algorithms were compared on real as well as on degenerate test cases. They were implemented in C++ and with the use of OpenMP library for parallelization. We determined that the basic algorithms were sufficient for most practical purposes. The degenerate cases can also be solved efficiently with sequential linear time algorithms. However, the experiments on parallelization showed that multicore computers these days differ too much from computation models to reach the expected theoretic speedup.
Secondary keywords:	string;substring;search;algorithm;parallel;hash;computer science;diploma;
File type:	application/pdf
Type (COBISS):	Undergraduate thesis
Thesis comment:	Univ. v Ljubljani, Fak. za računalništvo in informatiko
Pages:	48 str.
ID:	24142492