[公告] 博士論文口試 歐家欣 (2014/6/10)

[ARDS]

嚙瞎嚙諍大嚙褒賂蕭T嚙線嚙緹嚙褒系嚙調士嚙論歹蕭f嚙踝蕭

嚙踝蕭 嚙談：嚙誹家嚙磐

嚙踝蕭伀訇癒G嚙踝蕭嚙窮嚙瞑嚙請授、嚙箱嚙璀嚙踝蕭嚙請梧蕭

嚙篆嚙調委嚙踝蕭G
嚙調外: 嚙踝蕭嚙窮嚙瞑嚙請授、嚙踝蕭禮嚙請梧蕭
嚙調歹蕭: 嚙踝蕭q嚙請授、嚙踝蕭嚙論教授、嚙箱嚙璀嚙踝蕭嚙請梧蕭

嚙踝蕭 嚙踝蕭嚙瘦103 嚙羯 6 嚙踝蕭 10 嚙踝蕭 (嚙瞑嚙踝蕭嚙瘦) 13:00 - 15:00

嚙窮 嚙瘢嚙瘦嚙踝蕭q嚙稽 550 嚙罵議嚙踝蕭

嚙瘩 嚙諍：On the Bit-Parallel Approaches to String Matching Problem

嚙論歹蕭K嚙緯嚙瘦

In this thesis, we consider two problems: (1) A systematical approach to
solve problems involving special properties of bit-vectors (2) A bit-parallel
approach to solve the nearest neighbor string matching problem. For problem 1,
suppose that we are given a vector consisting of only 1's and 0's and we are
interested in finding some special properties of this vector. These properties
all involve "for-all" or "there-exists" notations and we are interested in
bit-parallel processes to find these properties. In Myers' work, a sequence of
logical operations can be expressed as a logical formula: (?k?i, A(k) and
?x?[k, i嚙碾1]) = (((A & B) + B) ^ B) | A) which is by no means easy to be
obtained. The contribution of our research is to present a systematical method
to find such logical formulas to solve problems involving bit vectors with
"for-all" and "there-exists" notations. Using our way of thinking, the
equation in Myers' work can be deduced step by step. Five logical prototype
problems, "single-for-all", "single-there-exists", "multiple- for-all",
"multiple-there-exists" and "multiple-there-exists-and-for-all", are defined
in this thesis and are proved that all can be computed in using bit-parallel
operations in O(n/w) time, where w is the word size of the machine. We also
consider four variants of the five problems and show that their logical
formulas can be obtained using those of the five prototype problems system-
atically. The nearest neighbor string matching problem is defined as follows:
Given a text string T = t1t2嚙皺tn and a pattern string P = p1p2嚙皺pm, the
nearest neighbor string matching problem is to find all substrings of T whose
edit distances with P are the smallest, among all substrings of T. The nearest
neighbor string matching problem has useful applications in bioinformatics. The
nearest neighbor string matching problem can be straight-forwardly solved by
the Seller's Algorithm and the Myers Algorithm which are used to solve the
approximate string matching problem. Hyyro and Navarro proposed a filtering
algorithm to speed up the Myers Algorithm. However, Hyyro and Navarro's
filtering approach needs to perform a pre-processing based on the error bound k
which is given by the definition of approximate string matching problem. Hence,
it is not suitable to be used to solve the nearest neighbor string matching
problem which has no k. In this thesis, we present a modification of the Hyyro
and Navarro Algorithm, and also present a bit-parallel algorithm combining the
Myers Algorithm and the modified Hyyro and Navarro Algorithm. In experiments,
we show that our bit-parallel algorithm is efficient.


嚙諛作嚙瘠嚙踝蕭G

Journal Papers:

1. Chia Shin Ou, Chin Lung Lu and R.C.T. Lee. "A Systematical and Parallel
Approach to Solve Problems Involving Special Properties of Bit-vectors", the
Computer Journal, 2014. (published) (SCI, EI) [5-Year Impact Factor: 0.943]

Conference Papers:

1. Chia Shin Ou and R.C.T. Lee. "Bit-Parallel Operations to Investigate
Properties of Logical Vectors by Logical Operations", Proceedings of the 27th
Workshop on Combinatorial Mathematics and Computation Theory, April, pp.15-20,
2010.

2. Chia Shin Ou and R.C.T. Lee. "A Parallel Approach to Solve the Approximate
String Matching Problem", Proceedings of the 27th Workshop on Combinatorial
Mathematics and Computation Theory, April, pp.161-166, 2010.

3. Chia Shin Ou, Chin Lung Lu and R.C.T. Lee. "A Bit-Parallel Approach to
Solve the Approximate String Matching Problem for Unlimited Pattern Length",
Asian Association for Algorithms and Computation, May, 2011.

4. Chia Shin Ou and R.C.T. Lee. "A Bit-Parallel Algorithm to Solve the Nearest
Neighbor String Matching Problem", Proceedings of the 28th Workshop on
Combinatorial Mathematics and Computation Theory, pp.167-172, May, 2011.

5. Chia Shin Ou, Chin Lung Lu and R.C.T. Lee. "A Bit-Parallel Algorithm to
Solve the k-Nearest Neighbor String Matching Problem", Proceedings of the 29th
Workshop on Combinatorial Mathematics and Computation Theory, April, pp.208-216,
2012.

6. Chia Shin Ou, Chin Lung Lu and R.C.T. Lee. "Solving the Subcircuit Extraction
Problem by Using Bit-Parallel Filtering Algorithm", Proceedings of the 30th
Workshop on Combinatorial Mathematics and Computation Theory, April, 2013,
pp.116-123.

7. Chia Shin Ou and R.C.T. Lee. "Bit-Parallel Filtering Algorithm to Solve the
Approximate String Matching Problem", Proceedings of the 31th Workshop on
Combinatorial Mathematics and Computation Theory, April, pp.88-91, 2014.


--
嚙箴 嚙踝蕭 嚙箴嚙箴嚙箴 嚙箴嚙箴嚙箴 嚙箴 嚙箴嚙箴嚙箴 [1;37m 嚙瞎嚙篌嚙踝蕭u [m
[1;37;44m 嚙箠 嚙箠嚙踝蕭嚙踝蕭嚙箠 嚙箠嚙箴嚙箠 嚙箠嚙箴嚙箠 嚙箠 嚙箠嚙箴嚙箴 [33mards [37m 嚙緬 [33m 111.249.196.188 [m
嚙箠 嚙箠嚙踝蕭嚙踝蕭嚙箠 嚙箠 嚙箠 嚙箠 嚙箠嚙箴嚙箴 嚙箠嚙箴嚙箴 [1;37m嚙箠嚙踝蕭嚙踝蕭嚙賣站嚙篌 telnet://imaple.tw [m