浅野（哲夫）研究室

質問:浅野（哲夫）研究室ではどんな研究を行っていますか？
回答：ここをクリック

質問：情報系以外の出身ですが，アルゴリズムの研究を行う上で必須の知識は何でしょうか？どんな講義課目を取得しておく必要がありますか？
回答:ここをクリック

質問：研究室内のゼミについて教えて下さい．
回答：ここをクリック


質問：修士研究の進め方（指導方針など）について教えて下さい
回答：ここをクリック

質問：研究室の雰囲気はどうですか？
回答：ここをクリック

平成２２年度研究テーマ

アルゴリズムに関する研究の基本姿勢

　アルゴリズムは理論計算機科学の中でも最も基礎的でしかも重要な研究分野です．アルゴリズムの研究というと，高速化が主要なテーマのように思われがちですが，研究の醍醐味は別にあります．高速化というのは，他人が考案したアルゴリズムを改良することでしかありません．もっと大事なことは，まったくどのようにして解けばよいかが分からなかった問題に対して新たな解法，すなわちアルゴリズムを考案することです．このとき，幾つかの例題に対してうまく行くというだけでは不十分で，どんな入力に対しても必ず解が求まることを証明できなければなりません．また，実行時間と作業領域（メモリ量）の解析も重要です．アルゴリズムの解析は難しいことが多いのですが，ここをしっかりとしておかないとアルゴリズムに説得力がなくなります．
　もっと詳細はここをクリック

テーマ１．メモリ制約付きアルゴリズムの開発

　最近ではメモリが安価になったためにパーソナルコンピュータでも大容量の記憶装置が使えるようになりました．そのために，メモリのことを考えずにプログラムを作ってしまうという風潮も見受けられます．しかし，扱うデータのサイズも急激に増大しており，大きな作業領域を使わないプログラミングが重要であることは確かです．また，最近ではハードディスクの代わりにフラッシュメモリを使ったコンピュータも発売されていますが，フラッシュメモリというのはデータの読み出しに比べてデータ書き込みに時間がかかるという特徴があり，フラッシュメモリを作業領域に使ったプログラムの場合，作業領域をできるだけ小さくすることが肝要です．さらに，最近ではディジタルカメラのように，装置の中にかなり高度なソフトウェアが組み込まれるようになりました．そのようなソフトウェアを総称して「組み込みソフト」と呼んでいますが，組み込みソフトでも作業領域が限定されていることが多いので，やはり大きな作業領域を使わないアルゴリズムの開発が求められています．
　続きはここをクリック

例１：簡単な例を考えて見ましょう．正整数 n を与えて，その逆数 1/n を正確に求めるという問題です．整数 n が2または5で割り切ることができなければ，1/nは必ず循環小数になります．たとえば，
1/7 = 0.(142857)
1/23 = 0.(0434782608695652173913)
1/28 = 0.03(571428)
1/29 = 0.(0344827586206896551724137931)
1/34 = 0.0(2941176470588235)
1/36 = 0.02(7)
などです．()を用いているのは，循環部分の最初と最後を示すためです．
　続きはここをクリック

例２：計算幾何学の主要問題の一つに三角形分割問題があります．これは，平面上にn点が与えられたとき，それらの点をすべて包み込む最小の凸多角形（凸包と呼んでいます）の内部を，与えられた点だけを頂点とする三角形に分割せよという問題です．
　続きはここをクリック

さらにもっと知りたい人はここをクリック
もっともっと知りたい人はここをクリック

 

テーマ２．計算幾何学に関する研究

　以前から計算幾何学に関する様々な問題に取り組んで来ました．ここで取り上げるのはその一部です．

テーマ：既存点集合への新たな要素の挿入

　平面上にn個の点が既に配置されているものとします．ここに新たに１点を挿入するのですが，その点から既存の点までの距離がなるべく入力で指定された距離に近くなるように，新たな１点の場所を求めよという問題です．具体的には，入力で指定された距離と実際の距離の差の2乗の和を最小にするという問題です．単に距離の差の絶対値の和で誤差を評価すると，平方根で表現される項の和を最小にする問題ということになり，最適解を求めることは絶望的になりますが，差の2乗和であれば平方根が入らないので，最適解を求めることができそうです．決して単純な問題ではありませんが，計算幾何学の基礎知識が身につけば難しくないでしょう．





テーマ３．画像処理への応用に関する研究

テーマ：プリンタモデルを考慮した ２値画像の分類

　計算機で構成した２値画像をレーザビームプリンタのような形式のプリンタで出力するとき，どのような画像が出力されるかを予測して，予測画像に近いものが出力されるように元の２値画像（インクを置くか置かないかの区別）を構成しなければなりません．ある場所にインクを置くことにすると，その場所にレーザビームを当てます．このようにして数行分のレーザ照射が終わると，そこにトナーを散布します．もし十分な電荷が帯電していればトナーが定着することになります．プリンタモデルとは，レーザ出力と帯電の様子を決めるモデルのことです．
　続きはここをクリック

テーマ：ディジタル・ハーフトーニングのための最適なマスクの設計

　ディジタル・ハーフトーニングとは，ディジタル・カメラなどで撮影した多値の画像を画質を劣化させないように２値画像に変換する技術のことです．簡単な例として白黒の写真を黒のインクだけをもつインクジェット・プリンタで出力することを考えて見ましょう．簡単のため，1000x1000のサイズの写真を考えましょう．更に簡単のため，これを1000x1000のドットとして表現するものとします．つまり，1000x1000のグリッドを考えて，それぞれのグリッド点にインクを置くか置かないかを決めて画像を表現しようというわけです．それぞれの画素の明るさは256段階で表現されるものとします．最も簡単な２値化の方法は，各画素の輝度値を中間の値128と比較して，それより大きいときは白（つまり黒インクを置かない），小さいときは黒（つまり黒インクを置く）と定めるという固定閾値法です．こんな簡単な方法でも，何とか判別できる画像が得られることもありますが，ひどい結果になることもあります．たとえば，どの画素についても輝度値が127なら，本来は灰色なのに真っ白な画像になってしまいます．
　中略
　下に示したのは，どの3x3の（連続）領域をとっても要素の総和が一定であるような行列です．このような行列を求めるのは簡単なことではありませんが，行列のサイズが近傍のサイズで割り切れる場合については，そのような性質をもつ行列を構成する方式が知られています（浅野らの方法）．もっと大きなサイズで同様の行列を構成するというのが問題です．

0	1	2	6	7	8	3	4	5
3	4	5	0	1	2	6	7	8
6	7	8	3	4	5	0	1	2
2	0	1	8	6	7	5	3	4
5	3	4	2	0	1	8	6	7
8	6	7	5	3	4	2	0	1
1	2	0	7	8	6	4	5	3
4	5	3	1	2	0	7	8	6
7	8	6	4	5	3	1	2	0

　このテーマの詳細についてはここをクリック

テーマ４：大学院教育イニシアティブセンター関係の研究テーマ

　浅野は平成２２年４月から大学院教育イニシアティブセンターのセンター長を務めることになりました．その関係で全く新たな分野の研究も始めることになりました．以下に述べるのは，その一部です．

テーマ：教材の話題に最も適合する文献を求めるアルゴリズム

　学部の講義では指定された教科書の内容を理解することが必要かつ十分な場合が多かったが，大学院の講義では，学生の勉学意欲に応えて発展的な学習を指導することも重要である．言い換えると，講義の内容の一部をより深く勉強してみたいという学生のために，どのテキスト，あるいはどの文献を参照すればよいかのポインタを与えることが重要である．しかし，教員の知識には限度があるために，自動化の方向を探りたい．
　具体的には，前もって講義に関係ありそうなテキストブックあるいは参考文献をスキャナなどを用いてテキスト化しておく．この作業は教育センターのアルバイトを利用する予定である．ページごとに参照可能な形に整理できているとして，講義で使われているパワーポイントなどのテキストデータを入力する．テクニカルタームを検出できれば，後はデータベースにおいて教科書などのページごとのデータで最もよくマッチするものを選んでくるということになる．つまり，講義のページの内容とテキストのあるページの内容がどの程度マッチするのかを評価し，最もよくマッチするものを選ぶことになる．

テーマ：問題データベースの作成と問題の難しさの定量的評価

　良い講義とは何だろう？もちろん，内容が良くて，教え方も上手であることが望ましい．しかし，学生にとっては試験問題が最大の関心事であろう．では理想的な試験問題とはどんなものだろうか？まず，最低限大切なことは，年度によって問題の難しさが変化しないことであろう．しかし，多くの場合，試験問題は教員が個人的に作るので，その教員にとっての難しさの基準で同程度のものが作られるということが考えられる．ある程度の主観評価は避けられないが，度を越すと良くない．
　本研究テーマでは，今まで主観的にしか評価されてこなかった試験問題の難しさの評価に定量的な尺度を導入しようという大胆なものである．入力として考えられるのは，対象となる講義に関連するテキストブックである．できれば多数のテキストブックをテキストとして電子的に持っておき，そこからテクニカルターム（技術用語）を抜き出す．このとき，インターネットの検索などで用いられている技術が参考になろう．それらのテクニカルタームは，出現頻度や出現場所などの情報と関連付けて計算機内に蓄える．たとえば，アルゴリズムの分野であれば，定理や補題などで頻出する用語は非常に重要だと考えられる．また，定理などには出現しないが，証明の中ではよく出てくる用語も別の意味で重要である．このような情報を予め計算しておいて，現実の問題が，その解答例と共に与えられたとき，解答に現れるテクニカルタームのレベルの高さを評価することによって問題の難しさを評価しよう，というのが基本的な考え方である．そのために，解答例は不可欠である．チャレンジングなテーマであるが，是非真剣に取り組みたいと考えている重点テーマの一つである．