7,289 research outputs found
A low-cost neural sorting network with O(1) time complexity
Full text link[[abstract]]In this paper, we present an O(1) time neural network with O(n1 + var epsilon) neurons and links to sort n data, var epsilon > 0. For large-size problems, it is desirable to have low-cost hardware solutions. In order to solve the sorting problem in constant time and with less hardware-cost, we adopt Leighton's column sort [5] as the main architecture. Then we use Chen and Hsieh's neural network [3] with O(n3) complexity as the lowest-level sub-networks. By using recursive techniques properly, we are able to explore constant-time, low-complexity neural sorting networks.
[[alternative]]The Study of Improving Chinese Input Methods and The Implementation of NTNU-Master Input Method
No full text[[abstract]]Chinese Character Input on computers is the basic ability in the east, especially in Taiwan, Hong Kong and China. If someone can input Chinese characters quickly, then he can improve his ability in using computers to do many things.
In this study, we stand on some famous input methods, like ChangJie, and other input methods based on ChangJie’s method. We try to develop some techniques, such as rearranging the ChangJie alphabets, encoding the characters with 3 codes, reducing the numbers of strokes using space bar, etc. We compare our results with ChangJie and Dy-Sin-Cang-Jie by statistical techniques in typing lots of articles. We named this method as NTNU-Master input method. The basic concept was originally designed by Dr. Shun-Shii Lin. This study is the first one to implement the system and analyze it.
After some experiments, we get some encouraging results. Successfully, we are able to reduce the average number of strokes for typing Chinese characters.
Cylindroeme shii Wang, Xie & Wang 2022
No full textCylindroeme shii Wang, Xie & Wang, 2022 石氏åfihk牛 Cylindroeme shii Wang, Xie & Wang, 2022: 130, figs. 3–8, 10–11, 13–24. TL: China: Qinghai. TD: YU. Distribution China: Qinghai. Remarks. This species is distinguished from other two congeners by the upper eye lobes widely separated.Published as part of Lin, Mei-Ying & Li, Kai-Qin, 2022, A new species, Cylindroeme yunnanensis sp. nov. from China (Coleoptera, Cerambycidae, Cerambycinae), pp. 294-300 in Zootaxa 5159 (2) on page 300, DOI: 10.11646/zootaxa.5159.2.7, http://zenodo.org/record/677733
[[alternative]]The Designs and Analyses of Parallel Algorithms for Some Problems on Special Graphs
No full text[[abstract]]A processor array with reconfigurable bus system (abbreviated to PARBS) is a parallel computation model that consists of a processor array and a reconfigurable bus system. In this model, we can dynamically setup the configurations of all processors in order to form different sub-buses in the processor array. There are a lot of researchers that develop efficient or constant-time algorithms based on this parallel computation model in order to solve many complicated problems, because in a sub-bus the data can be broadcasted in fixed units of time.
In this thesis, we will propose a new algorithm to find all bridges of a general graph in O(1)-time on a 3D-O(n^3) or 2D-O(n^4) PARBS. We also develop some related graph algorithms to find all connected components, articulation points, bridges, biconnected components and a spanning tree of an interval graph or a circular graph in O(1)-time on a 2D-O(n^2) PARBS.
[[alternative]]Solving Eigenvalues and the Eigenvector Corresponding to the Largest Eigenvalue of a Positive Definite Matrix Using Neural Networks
No full text[[abstract]]In the areas of real-time signal processing, it's important to
solve the eigenvalue decomposition problem of a positive defi-
nite matrix. For processing the signal in time, we must derive
the eigenvalues and eigenvectors in fixed units of time. This
problem can be solved by a sequential algorithm in O(n^4) time,
but this takes too long time for a real-time system to satisfy
the requirement. In this paper, we will propose a parallel sch-
eme that can solve all eigenvalues and the eigenvector corres-
ponding to the largest eigenvalue of a positive definite matrix
on the neural networks in O(n(log n + m)) time by using O(n^3)
neurons and O(n^3) links, where the size of the matrix is n*n
and the number of time clocks for the system to be convergent
is m.
[[alternative]]A Research and Implementation for Computer-Assisted Mnemonic System:Research of Automatic Sentence Composition
No full text[[abstract]]In this thesis, we develop a system called Computer-Assisted Mnemonic System (CAMS), which can assist people to memorize some meaningless numeric strings with Chinese sentences. We analyze phonetics of the numbers from 0 to 9 and find out 114 rules of similar syllables. The rules are matched with the lexicons corpora established by CKIP (Chinese Knowledge Information Processing) Group of Academia Sinica in the Republic of China. Our system finds 12680 lexicons that can be used in composing sentences. We use a transformation mechanism to segment a series of numbers and thus compose sentences.
In the research, we use dynamic programming to implement the unification process of CAMS in O(n3*(m+y)) time by using O(n2*m) space of memory, where n is the length of the input numeric stings and m is the number of compositional sentences that we want to output, y is the times that our system gets unsatisfied composition results. Among the satisfied composition results, we utilize evaluation function to judge whether each of those composition sentences is suitable for us to memorize or not. In this process, the system will generate a binary parsing tree of sentences for further research in the future. Experimental results show that our system has a high degree of mnemonic effect for most users.
[[alternative]]The Designs and Analyses of Parallel Algorithms for Some Problems on Permutation and Interval Graphs
No full text[[abstract]]ABSTRACT
The Designs and Analyses of Parallel Algorithms for Some
Problems on Permutation and Interval Graphs
A processor array with reconfigurable bus system (abbreviated to PARBS) is a parallel computation model that consists of processor array and a reconfigurable bus system. In this model, we can dynamically setup the configurations of all processors in order to form different sub-buses in the processor array. In a sub-bus, the data can be broadcasted in fixed units of time. There are a lot of researchers that develop parallel algorithms on this computation model in order to solve many complicated problems.
In this thesis, we propose algorithms for computing prefix maxima, suffix minima and prefix sum in O(n/p+log p) time on a 1D PARBS with O(p) processors. We also design an algorithm to filter out duplicate data in a nondecreasing sequence in O(n/p) time on a 1D PARBS with O(p) processors.
In addition, we develop algorithms for finding all connected components, articulation points, and a spanning tree of a permutation graph. We also develop algorithms for finding all connected components, articulation points, bridges, and a spanning tree of an interval graph. These algorithms take O(n/p + log p) time on a 1D PARBS with O(p) processors. If p = O(n/log n), they all become cost optimal.
Keyword: PARBS (Processor Arrays with Reconfigurable Bus Systems), cost optimal algorithm, prefix maxima, suffix minima, prefix sum, filter out duplicate data, permutation graph, interval graph, connectivity test problem, connected component problem, articulation point problem, bridge problem, spanning tree problem.
[[alternative]]Schedulability Analyses for EDkL Scheduling on Real-Time Multiprocessor Systems
No full text[[abstract]]There has been an increasing demand for real-time scheduling on multiprocessor systems. With the decreasing cost of hardware, multiprocessor architecture becomes more popular nowadays. However, a multiprocessor real-time system may not provide a performance speedup proportional to the number of processors. Choosing a suitable scheduling algorithm is very important in order to get good performance. In this paper, we study some efficient real-time scheduling algorithms for multiprocessor systems. The first is EDZL (Earliest Deadline first until Zero Laxity). Then we extend the cases to the condition of k laxities. We also try to replace the EDF module with other heuristics in EDZL algorithm. We find that EDkL could not improve processor utilization and other heuristics are not good enough as EDF in EDZL. Using a special task set we got from experiments, we disprove the conjecture that the utilization bound of EDZL is 3m/4. Finally, we also get a property that the utilization bound of EDZL is not greater than m(1-1/e) where e is the natural logarithm. Although the bound of EDZL is not ideal enough, EDZL is still an efficient and practical scheduling algorithm for real-time multiprocessor systems.
[[alternative]]Optimal Algorithms for Constructing Knight's Tours on Rectangular Chessboards
No full text[[abstract]]The knight's tour problem has been studied for a very long period of time. The main purpose of the knight's tour problem is to find out how to construct a series of moves made by a knight visiting every square of a chessboard exactly once. In 1992, Takefuji and Lee state that they are unsure whether the problem of finding a knight's tour is NP-complete. In previous works, all researchers partially solve this problem by offering algorithms for a partial subset of chessboards. For example, among the prior studies, Ian Parberry proposes a divided-and-conquer algorithm that can build a closed knight's tour on an n x n, an n x (n+1) or an n x (n+2) chessboard in O(n^2) (i.e. linear) time on a sequential processor. In this paper, we completely solve this problem and answer the question of Takefuji and Lee by presenting a new method that can construct a closed knight's tour or an open knight's tour on an arbitrary n m chessboard if they exist. Our algorithm runs in linear time (O(nm)) on a sequential processor.
- …
