NP完全問題を解くDNAコンピュータ

ネットワーク研究室 担当教官 坂本直志准教授 03KC091 藤原久敬 目次 第一章.はじめに 第二章.準備 NP完全 グラフ 多項式時間 多項式時間で解けない問題の構造とNP P=NP問題 帰着 NP完全(NPの性質) P=NP問題の現状 DNA DNAの構成 DNA間の結合 DNAの実験装置 第三章.本研究の内容 Leonard M.Adleman Molecular computation of solution to combinational problemのレビュー 要約 有向ハミルトンパス問題 Adlemanのアルゴリズム まとめ A Sticker-Based Model for DNA Computation のレビュー 要約 情報の表現方法 基本演算 最小被覆問題 stickers modelを使ったアルゴリズム 基本演算の実装 初期化と解の検出 stickers ma