ウェブリ/ブログログイン

[   ]

トップ  プロフ  フレンド  サークル

(1)人工知能 もともと機械に知的なふるまいをさせようという目的で始まった研究分野です。 つまり人工知能とは「考える機械」を作ることを目的としている。 考えるということは、ある種の情報処理というものができる事である。 簡単な計算から、さまざまな問題に対し、問題を認識し、推理や判断を行ったり、知識を学習したり整理する能力などさまざまなものが考えられます。 このため、人工知能の研究は、認知科学や知識工学など、様々な分野に派生してきた。 (2)よいアルゴリズム よいアルゴリズムとは、同じ計算結果が出るのであれば、コストがもっとも少なくて済む方法のこと (3)良性問題と非良性問題の違いは 良性問題とは、ソフトウエアでの解決方法の一種である。そしてそれは解析的に 解けるものでその解析解の結果を利用する。または数値演算で求められるものをさし ている。その場合はループを減らすことなどがそれにあたる。非良性問題とは、数値 計算では判断が困難なため実際上解が求められないもの。 良性問題と非良性問題の 違いは、良性問題は、はっきりとした解決策があり、非良性問題には、はっきりとし た解決策がない。 (4)遺伝的アルゴリズム 遺伝的アルゴリズムとは、ある問題に対する最適な解を求めるための手法といえる。 この手法はもともと、生物の世界にある遺伝の法則をまねて作られたもので、 複数の解を、遺伝的に変化させながら、より良い解を求めていくものである。 参考文献 (5)ニュートラルネットワーク 人間の脳の情報処理を計算機で実現しようとするもの。規則などの法則をコンピュー タに認識させるのではなく、人間の脳そのものの処理をコンピュータで表現しようと いうのが ニューラルネットワーク。 ニューラルネットワークには、階層型と相互結合型がある。階層型の代表的なものに はパーセプトロン、バックプロパゲーション（ＢＰ）学習型、ネオコグニトロンなど で、相互結合型には、アソシアトロン、ホップフィールドネットワーク、ボルツマン マシンなどがある。このほかにも実に様々なニューラルネットワークが提唱されてい る。 (6)事例ベース推論 事例ベース推論(CBR)は，経験・過去の事例を使って問題を解くという推論モデルである。CBRでは，特定の問題とその解決方法の対からなる過去の事例が多数事例ベースに格納されている。解くべき問題を与えられると，過去の事例からその問題に類似のものをもってくる。解くべき問題と選択された過去の問題の間の差を調べてその差に対応して，選択された事例の解決方法の部分を変更して，それを与えられた問題に対する解決方法として出力する。CBRの性能は事例ベースの大きさと内容に依存する。また，過去の類似の事例をみつける為の類似度の計算手法にも依存する。 (7)DB利用業務システムにおける良いアルゴリズム 業務システムはデータを加工しつつ転記する動作が極めて多い特徴がある。ディスクアクセスの時間が処理時間のボトルネックとなりやすいので、アクセス回数を減少させることが最良のアルゴリズムとなることが多い。 (8)単純文字列照合、KMP法、BM法 ・単純文字列照合について 照合される文字列(以下「テキスト」と略記)の頭から順に照合文字列(以下「パターン」と略記)と比較して、違っていたら1文字ずつ後ろへずれながら処理を繰り返すこと。 文字列比較の場合、処理が終わるまでに文字コードを比較する回数がアルゴリズムの性能を左右する。テキストとパターンのそれぞれの文字数がn,mで、かつnがmに対して十分大きいとすると、上記のアルゴリズムの場合最悪m×n回近く文字を比較する必要がある。例えば、単一の文字がn個並んだ文字列から、同じ文字の並びの末尾に1文字だけ違う文字コードを付加したm個の文字列を検索した場合、m-1文字まで検索して最後のm文字目で不一致を検出する処理をn回近く繰り返すことになる。 しかし、現実にはこのような「最悪の」場面というのはまずないと言えるので心配する必要はないのである。 ・KMP法について 最悪の場合の計算量はmnに比例するところに改良の余地が残っている。計算量がこれほどになるのは、ある位置にパターンをおいて比較した際に得られる情報を十分活用していないため。 そのために、照合を始める前に準備をしておくことが必要。すなわち、k 文字だけ一致した後で不一致が見つかったときに、テキストのどの文字と、パターンのどの文字の比較から照合を続ければよいかをあらかじめ調べておく。不一致となった位置から左側 k文字がわかっていることを利用して、ここは違うとわかっている部分を飛ばし検索時間を短くする方法である。無駄な比較を避けるように設定する。KMPアルゴリズムの比較回数は、最大 2n 回。つまり計算量は O(n) 。n はテキストの長さ。しかし、BM法による文字列照合アルゴリズム に比べると、実用上の性能で劣る。 なお、ＫＭＰは考案者　Ｋnuth、Ｍorris、Ｐratt　３氏の頭文字を表す。 ・BM法について Boyer-Mooreのアルゴリズム、略してBMアルゴリズムは、 KMPアルゴリズムよりもさらに高速。照合パターンがある程度以上（普通５文字以上くらい）の長さをもつ場合には、最も速い文字列照合アルゴリズムだと言われている。KMPアルゴリズムと同様、計算量は最悪の場合でも O(n) 。 BMアルゴリズムの長所は、テキスト中の文字の大部分を調べずにすむ可能性があること。BMアルゴリズムでは n/m 個（nはテキストの長さ、mは照合パターンの長さ）の文字とだけ比較すればよい。これによって、特に照合パターンが長いときに、計算時間の大幅な短縮が期待できる。 この特徴から、BMアルゴリズムは、実用上きわめて重要なアルゴリズムと見なされている。 BMアルゴリズムも、素朴なアルゴリズムと同様、テキストを左から順に調べていく。しかし、いったんテキスト上の位置がきまったら、照合パターンについては、逆に右から左に向かって調べる。照合パターンを逆向きに調べることがBMアルゴリズムの要点である。もちろん、照合を進めるにあたっては、それ以前に行った比較の結果として得られた情報をできるだけ活用して、比較の回数を減らすように努める。これはKMPアルゴリズムと同じである。　 参考文献： 講義録９＜１０＞ http://www2.starcat.ne.jp/~fussy/algo/algo7-3.htm http://bal4u.dip.jp/mt/program/archives/2004/09/kmpkmpmatch.html http://kyu.pobox.ne.jp/softcomputing/ga/ga1.html http://www.ne.senshu-u.ac.jp/~n140237/dm/1029.htm http://agrinfo.narc.affrc.go.jp/fs/cdrom/3syou/305st/t05.htm http://metalbrain.piroo.com/about.html http://kyu.pobox.ne.jp/softcomputing/neuro/words.html http://kyu.pobox.ne.jp/softcomputing/ga/ga1.html http://kyu.pobox.ne.jp/softcomputing/ai/ai1.html 人工知能や遺伝アルゴリズムなど興味深い単語が出てきました。できればこれからの授業でもっと取り上げて欲しいなと思いました。また、人間の脳にかぎりなく近づけるように機械の発明もされていてまだまだ進歩していくんだなぁと実感しました。

<< 前記事（2005/11/18）

トップへ

後記事（2005/12/05）>>

<< 前記事（2005/11/18）

トップへ

後記事（2005/12/05）>>