KajiSemi Study

STUDY

Paper

[戻る]

Name Content

魚住　葉子『ファジィＡＨＰによる薄型デジタルテレビ購入意思決定問題における事例研究』

　2011年7月24日、地上アナログ放送は終了する。デジタル放送時代の到来までに、私たちはデジタル対応テレビもしくは専用チューナーの購入を余儀なくされた。そのため、家電メーカーは挙ってデジタル対応ＴＶの開発・商品化に力を注いでいる。しかし、あまりにも私たち消費者としては、商品の種類や特性が多くてどのＴＶを購入してよいかわからない。

　そこで、意思決定手法である"ファジィAHP"を用いて、私のデジタルＴＶ購入問題について考えたいと思う。
ファジィAHPとは、人間の意思決定を階層構造化して客観的に分析を行うことの出来るAHPと、人間特有の主観性を表現したファジィという考え方をミックスした分析方法である。また、ファジィAHPの分析には評価基準が用いられるのだが、この評価基準は定めるのが難しい。そのため、因子分析法を利用することとする。

王　濱『郵便配達人問題に関するアルゴリズムの構築』

　1962年、管梅谷（Mei－Gu Gwan）による、中国郵便配達人問題（Chinese postman problem）を提案した。その後、中国郵便配達人問題に関する研究が進められ、特に、Edmondsによる、最適なポストマン閉路は一般グラフ上の最小コスト完全マッチング問題と密接な関係があるという報告は、中国郵便配達人問題に対する最も重要な発表となる。

　今回私は最小コスト完全マッチング問題に対して、列挙法と幾つかの近似解法を提案し、それによる中国郵便配達人問題に関するアルゴリズムの構築を紹介したい。

大山　修平『メタヒューリスティックによるＮクィーン問題の解法』

　Ｎクィーン問題とは、チェスのクィーン(縦横斜めに幾マスでも進めるコマ)をＮ×Ｎの桝目の中にＮ個配置し、お互いに交差しないように配置するという問題である。このＮクィーン問題は、Ｎが大きくなればなるほど計算時間が莫大なものになってしまう。そこで、メタヒューリスティックである、遺伝的アルゴリズムとローカルサ－チと焼きなまし法を用いてこの問題を解いてみる。

　遺伝的アルゴリズムとは、生物が環境に適応して進化していく過程を工学的に模倣したアルゴリズムである。ローカルサーチとは、ランダムに生成した解を一部変化させ、解が改善されればそれに置き換えていく方法である。焼きなまし法とは、ローカルサーチで解が改善されない場合でもある確率によってその解に置き換える方法である。この３種類のアルゴリズムを用いて実験を行い、各アルゴリズムの性能を分析評価する。　

工藤　智弘『探索アルゴリズムにおけるハッシュ法の研究』

　探索とは、データの集合の中から目的とするデータを探し出すことである。探索で有名なアルゴリズムといえば線形探索や2分探索などであるが、他にも特殊な探索アルゴリズムとしてハッシュ法がある。データを順番に処理していく場合では線形探索や2分探索でも良いが、特定のデータを参照する場合にはハッシュ法の方が高速に探索することが可能である。
しかしながら、その分メモリを消費するという欠点もある。具体的にはUNIXのdiffコマンドや、CGIで使われるPerlのように実用的なプログラム言語で実装されている。また、ハッシュ法の仕組みで重要となるものはハッシュ関数であり、ハッシュ法全体の効率に大きく関連している。

　本研究ではハッシュ関数の研究に重点を置き、既存のハッシュ関数と作成したハッシュ関数を衝突回数と分散によって性能評価した。そして、素数がハッシュ法と密接に関わっていることにも焦点を当て、素数の有意性について分析した。

塚井　祐太『巡回セールスマン問題を解くためのアルゴリズムの構築と性能評価』

　巡回セールスマン問題（Traveling Salesman Problem-TSP）とは、N都市があり、セールスマンがある都市を出発点として、 N都市をすべて回ってまた出発点に戻るとき、複数ある巡回路から最短距離の巡回路を求める問題である。全巡回路の距離を計算すれば必ず解ける問題であるが、たった30都市程度でも何百兆年かかる。そこで、如何に効率よく解く方法を見つけるかがカギである。

　本研究では、Local Search(局所探索法）、Simulated Annealing（焼きなまし法）、遺伝的アルゴリズムを構築し、 TSPの性能評価をする。また、これらのアルゴリズムの性能を比較するために、 BorlandC++Builder5のアプリケーションを使って、グラフィックで表現する。グラフィックで表現することによって、第三者にも理解し易く、またその過程も分かりやすくなるということが目的である。

長野　啓太『制約付最短路問題におけるアルゴリズムの研究』

　制約付最短路問題とは、従来の最短路問題に、もうひとつの重みとそれに関する制約式を設けたものである。
例えば、札幌から東京へ行こうとする場合、新千歳空港から飛行機で羽田に向かう方法、寝台特急を使って向かう方法、フェリーを使う方法など、そこまでの経路と交通手段は多岐に渡るのがわかる。
最短路問題では、これらの問題を、最も早く目的地に辿り着く経路を選択すればよかったが、制約付最短路問題は、手持ちの予算と各経路の運賃を勘案しなければならない。制約付最短路問題は、最短路問題と比べて計算量的観点からより難しい問題であると知られている。最短路問題は、例えばダイクストラ法などの決定性アルゴリズムを持つが、制約付最短路問題ではそれを適用することができず、結果としてほとんどすべての経路について探索しなければならず、問題が大きくなるにつれて現実的時間で解を得ることができなくなる。

　そのため本論では、解の正確さよりも現実的時間で解く事を最優先した「近似解法」の立場から制約付最短路問題のアルゴリズムについて研究する。具体的には、制約式を何らかの超過を設けて目的式に組み込むラグランジュ緩和式、初期解から部分解を改善して行って全体的な解の向上を図る局所探索法、さらに局所探索法を物理学的観点において発展させた焼きなまし法を用い、この問題において最適なアルゴリズムや計算量の考察をする。

横石　瞬『ゲームプレイングアルゴリズムの研究』

　ゲームプレイングアルゴリズムの研究は1950年頃に始まった比較的新しい分野である。現在では6マス×6マスのオセロや5目並べなどは必勝法が判明している。しかし思考ゲームのほとんどは必勝法が判明していないか、必勝法は存在しない。それならばできるだけ最善の手をコンピュータで計算して求めようというのがゲームプレイングアルゴリズム研究の目的である。

　本論文では「三目並べ」・「戦艦ゲーム」・麻雀を単純化した「1人麻雀」の3つのゲームを取り上げ、それぞれのゲームのプレイングアルゴリズムを提案している。

渡辺　雅行『暗号理論の基礎とC++によるRSAの実用的且つ効果的な実装法』

古来より、情報の秘匿は主に軍事面において重要な技術の一部として様々な手法が考案され、用いられてきた。現代ではコンピュータネットワークによる通信の発展により、その秘匿手段が個人レベルでも重視されてきている。
また、日本では2005年4月の個人情報保護法の施行を機に、情報セキュリティ分野に対する世間の関心とその必要性は益々高まりつつある。技術の適用範囲も広がりを見せ、非接触型ICによる電子マネーやクレジットカード、無線LAN環境の進展などを始めとして、所謂IT分野を中心に多岐に渡るようになってきている。
その情報セキュリティの一分野である暗号理論において、総論的に基礎的な事柄を確認し、個別の方式についての背景やアルゴリズム等を明らかにすると共に、C言語によるシーザー暗号や C++によるRSAの実装などを通じて実用的な暗号プログラムの構築を行うに当たっての要件や効果的な利用法などを考察する。

　安全性を考慮した上でRSAの実装を行う場合、多倍長整数の導入が必要不可欠である。多倍長整数は長大な数値を表現・演算することを目的とするデータ構造やアルゴリズムの体系であるが、 C++の場合はこれが標準ライブラリに含まれていない。 Java等の言語を用いればこれは解決できるが、暗号の性質上ブラックボックスとなる部分は少ないほうが良い。そのため、一から原理を理解しつつこれらを構築していくことで、RSA本体のみならず周辺技術に関しても広く見ていきつつ安全性を検証していく。

[戻る]
Name	Content
魚住　葉子	『ファジィＡＨＰによる薄型デジタルテレビ購入意思決定問題における事例研究』　2011年7月24日、地上アナログ放送は終了する。デジタル放送時代の到来までに、私たちはデジタル対応テレビもしくは専用チューナーの購入を余儀なくされた。そのため、家電メーカーは挙ってデジタル対応ＴＶの開発・商品化に力を注いでいる。しかし、あまりにも私たち消費者としては、商品の種類や特性が多くてどのＴＶを購入してよいかわからない。　そこで、意思決定手法である"ファジィAHP"を用いて、私のデジタルＴＶ購入問題について考えたいと思う。ファジィAHPとは、人間の意思決定を階層構造化して客観的に分析を行うことの出来るAHPと、人間特有の主観性を表現したファジィという考え方をミックスした分析方法である。また、ファジィAHPの分析には評価基準が用いられるのだが、この評価基準は定めるのが難しい。そのため、因子分析法を利用することとする。
王　濱	『郵便配達人問題に関するアルゴリズムの構築』　1962年、管梅谷（Mei－Gu Gwan）による、中国郵便配達人問題（Chinese postman problem）を提案した。その後、中国郵便配達人問題に関する研究が進められ、特に、Edmondsによる、最適なポストマン閉路は一般グラフ上の最小コスト完全マッチング問題と密接な関係があるという報告は、中国郵便配達人問題に対する最も重要な発表となる。　今回私は最小コスト完全マッチング問題に対して、列挙法と幾つかの近似解法を提案し、それによる中国郵便配達人問題に関するアルゴリズムの構築を紹介したい。
大山　修平	『メタヒューリスティックによるＮクィーン問題の解法』　Ｎクィーン問題とは、チェスのクィーン(縦横斜めに幾マスでも進めるコマ)をＮ×Ｎの桝目の中にＮ個配置し、お互いに交差しないように配置するという問題である。このＮクィーン問題は、Ｎが大きくなればなるほど計算時間が莫大なものになってしまう。そこで、メタヒューリスティックである、遺伝的アルゴリズムとローカルサ－チと焼きなまし法を用いてこの問題を解いてみる。　遺伝的アルゴリズムとは、生物が環境に適応して進化していく過程を工学的に模倣したアルゴリズムである。ローカルサーチとは、ランダムに生成した解を一部変化させ、解が改善されればそれに置き換えていく方法である。焼きなまし法とは、ローカルサーチで解が改善されない場合でもある確率によってその解に置き換える方法である。この３種類のアルゴリズムを用いて実験を行い、各アルゴリズムの性能を分析評価する。
工藤　智弘	『探索アルゴリズムにおけるハッシュ法の研究』　探索とは、データの集合の中から目的とするデータを探し出すことである。探索で有名なアルゴリズムといえば線形探索や2分探索などであるが、他にも特殊な探索アルゴリズムとしてハッシュ法がある。データを順番に処理していく場合では線形探索や2分探索でも良いが、特定のデータを参照する場合にはハッシュ法の方が高速に探索することが可能である。しかしながら、その分メモリを消費するという欠点もある。具体的にはUNIXのdiffコマンドや、CGIで使われるPerlのように実用的なプログラム言語で実装されている。また、ハッシュ法の仕組みで重要となるものはハッシュ関数であり、ハッシュ法全体の効率に大きく関連している。　本研究ではハッシュ関数の研究に重点を置き、既存のハッシュ関数と作成したハッシュ関数を衝突回数と分散によって性能評価した。そして、素数がハッシュ法と密接に関わっていることにも焦点を当て、素数の有意性について分析した。
塚井　祐太	『巡回セールスマン問題を解くためのアルゴリズムの構築と性能評価』　巡回セールスマン問題（Traveling Salesman Problem-TSP）とは、N都市があり、セールスマンがある都市を出発点として、 N都市をすべて回ってまた出発点に戻るとき、複数ある巡回路から最短距離の巡回路を求める問題である。全巡回路の距離を計算すれば必ず解ける問題であるが、たった30都市程度でも何百兆年かかる。そこで、如何に効率よく解く方法を見つけるかがカギである。　本研究では、Local Search(局所探索法）、Simulated Annealing（焼きなまし法）、遺伝的アルゴリズムを構築し、 TSPの性能評価をする。また、これらのアルゴリズムの性能を比較するために、 BorlandC++Builder5のアプリケーションを使って、グラフィックで表現する。グラフィックで表現することによって、第三者にも理解し易く、またその過程も分かりやすくなるということが目的である。
長野　啓太	『制約付最短路問題におけるアルゴリズムの研究』　制約付最短路問題とは、従来の最短路問題に、もうひとつの重みとそれに関する制約式を設けたものである。例えば、札幌から東京へ行こうとする場合、新千歳空港から飛行機で羽田に向かう方法、寝台特急を使って向かう方法、フェリーを使う方法など、そこまでの経路と交通手段は多岐に渡るのがわかる。最短路問題では、これらの問題を、最も早く目的地に辿り着く経路を選択すればよかったが、制約付最短路問題は、手持ちの予算と各経路の運賃を勘案しなければならない。制約付最短路問題は、最短路問題と比べて計算量的観点からより難しい問題であると知られている。最短路問題は、例えばダイクストラ法などの決定性アルゴリズムを持つが、制約付最短路問題ではそれを適用することができず、結果としてほとんどすべての経路について探索しなければならず、問題が大きくなるにつれて現実的時間で解を得ることができなくなる。　そのため本論では、解の正確さよりも現実的時間で解く事を最優先した「近似解法」の立場から制約付最短路問題のアルゴリズムについて研究する。具体的には、制約式を何らかの超過を設けて目的式に組み込むラグランジュ緩和式、初期解から部分解を改善して行って全体的な解の向上を図る局所探索法、さらに局所探索法を物理学的観点において発展させた焼きなまし法を用い、この問題において最適なアルゴリズムや計算量の考察をする。
横石　瞬	『ゲームプレイングアルゴリズムの研究』　ゲームプレイングアルゴリズムの研究は1950年頃に始まった比較的新しい分野である。現在では6マス×6マスのオセロや5目並べなどは必勝法が判明している。しかし思考ゲームのほとんどは必勝法が判明していないか、必勝法は存在しない。それならばできるだけ最善の手をコンピュータで計算して求めようというのがゲームプレイングアルゴリズム研究の目的である。　本論文では「三目並べ」・「戦艦ゲーム」・麻雀を単純化した「1人麻雀」の3つのゲームを取り上げ、それぞれのゲームのプレイングアルゴリズムを提案している。
渡辺　雅行	『暗号理論の基礎とC++によるRSAの実用的且つ効果的な実装法』古来より、情報の秘匿は主に軍事面において重要な技術の一部として様々な手法が考案され、用いられてきた。現代ではコンピュータネットワークによる通信の発展により、その秘匿手段が個人レベルでも重視されてきている。また、日本では2005年4月の個人情報保護法の施行を機に、情報セキュリティ分野に対する世間の関心とその必要性は益々高まりつつある。技術の適用範囲も広がりを見せ、非接触型ICによる電子マネーやクレジットカード、無線LAN環境の進展などを始めとして、所謂IT分野を中心に多岐に渡るようになってきている。その情報セキュリティの一分野である暗号理論において、総論的に基礎的な事柄を確認し、個別の方式についての背景やアルゴリズム等を明らかにすると共に、C言語によるシーザー暗号や C++によるRSAの実装などを通じて実用的な暗号プログラムの構築を行うに当たっての要件や効果的な利用法などを考察する。　安全性を考慮した上でRSAの実装を行う場合、多倍長整数の導入が必要不可欠である。多倍長整数は長大な数値を表現・演算することを目的とするデータ構造やアルゴリズムの体系であるが、 C++の場合はこれが標準ライブラリに含まれていない。 Java等の言語を用いればこれは解決できるが、暗号の性質上ブラックボックスとなる部分は少ないほうが良い。そのため、一から原理を理解しつつこれらを構築していくことで、RSA本体のみならず周辺技術に関しても広く見ていきつつ安全性を検証していく。