Dissertation > Excellent graduate degree dissertation topics show

Research and Application of an Scalable Model on DNA Computing

Author: ZhouXu
Tutor: LiKenLi
School: Hunan University
Course: Applied Computer Technology
Keywords: DNA computing Parallel computing Divide and Conquer Pruning technique NP-complete problems Figure 3 - Coloring Problem Clique problem Partitioning problem
CLC: TP301.6
Type: Master's thesis
Year: 2009
Downloads: 72
Quote: 0
Read: Download Dissertation

Abstract


Computer technology is considered the three scientific revolution of the 20th century, the computer has played a huge role in promoting the development of the society, but quantum physics has successfully predicted the chip micro-processing capabilities growth can not be long maintained. For this reason, scientists are looking for a brand new computer architecture, such as artificial neural network computers, quantum computers, optical computers, as well as DNA computer model which DNA computers in recent years much attention of the scientific community. Molecular computing operating a high degree of parallelism to the DNA computing and high-density mass storage and parallel computing capacity, theoretically overcome the lack of computer storage capacity and computing speed, the NP-complete problem and other intractable problems one of the potential solutions, and, in theory, have been successful in polynomial time to solve a number of well-known NP-complete problem. However, since almost all of the DNA-based supercomputing algorithms use completely exhaustive way. The direct consequence of this approach was the pure index middleweight growing number of DNA strands in DNA computing algorithm. With the gradual deepening of DNA computing research-based index of the solution space explosion problem exist in the brute-force method of DNA computing algorithm increasingly prominent has become a bottleneck restrictions DNA Supercomputing Applications. In this paper, the main line in order to reduce the solution space of the problem in DNA computing. Traditional parallel computing and parallel processing model computer, the combination of the traditional strategy of parallel processing and the characteristics of DNA computing, the graph coloring problem, the maximum clique problem and divided DNA computing model study. For graph coloring problem and the maximum clique problem, according to the characteristics of the problem itself and pruning strategies draw on traditional computer graph coloring problem and the maximum clique problem scalable DNA computer algorithms. For partitioning problem in computer-based the universal divide-and-conquer algorithm design technology design partitioning problem scalable DNA computer algorithms. Theoretical analysis shows that: propose new scalable algorithms without increasing the time complexity of the algorithm under the premise of solving graph coloring problem required number of DNA strands from the the exhaustive algorithm O (3 n ) DNA strand reduced to O (2 n ); maximum clique problem required number of DNA strands by O (of 2 n ) is reduced to O (n); partitioning problem reduce the number of O (2 n ) to O (2 n / 2 ).

Related Dissertations

  1. Research on Combinatorial Optimization Problem Based on DNA Self-Assemble,TP399-C8
  2. Research and Design of a High-Performance Scalable Public Key Cryptographic Coprocessor,TN918.1
  3. Research on Video Compression Algorithm Based on Multi-core Computing Platform,TN919.81
  4. Research of Finite Element Method on GPU,O241.82
  5. Numerical Simulation of Radiofrequency Waves in Magnetized Plasma,TL612
  6. The Algorithm Researches of Novel Wide Area Backup Protection for Power Grid,TM774
  7. The Research on Online Adaptive Settings,TM77
  8. Fault Tolerance for MapReduce in the Cloud Environment,TP302.8
  9. High dynamic SINS navigation solution algorithm and parallelization of,TN966
  10. Image retrieval method and system for parallel computing,TP391.3
  11. GPU-accelerated particle filter PET image reconstruction algorithm,TP391.41
  12. GPU-based parallel search algorithm for time series,TP391.41
  13. CPU-based inverse algorithm source strength,TP18
  14. Parallel computing for data-intensive reconfigurable linear array processor architecture design,TP332
  15. Large-scale approximation paragraph fingerprint - based page detection algorithm research,TP393.092
  16. Parallel and Dual-systems Cooperative Co-evolutionary Differential Evolution Algorithms and Their Application,TP18
  17. Research on Fault-Tolerant Parallel Skyline Query Technology in Cloud Computing Environment,TP311.13
  18. A Study on Diagonal Computing Model for GPGPU Platform,TP391.41
  19. Algorithm Study on Accelerate CV Image Segmentation and Exterior Industrial Image Reconstruction by CUDA,TP391.41
  20. The Study on the UAV Digital Remote Sensing & Survey System Integration and Images Data Processing,P237
  21. Application of Parallel FDTD and MPSTD Algorithm in EM Scattering,O441.4

CLC: > Industrial Technology > Automation technology,computer technology > Computing technology,computer technology > General issues > Theories, methods > Algorithm Theory
© 2012 www.DissertationTopic.Net  Mobile