高知大学大学院総合人間自然科学研究科
理学専攻応用理学コース情報科学分野

2011年度修士論文要旨

1

辺彩色完全グラフの 頂点の次数和を指定した異色全域木
応用理学コース

情報科学分野白川洋介

数学の一分野であるグラフ理論は，頂点の集合とそれらをつなぐ線の集合からなる グラフ と呼ばれる構造の性質について研究する学問である．頂点と頂点をつなぐ線を辺と呼ぶ．グラフ理論は、ネットワーク理論やアルゴリズムとデータ構造など、情報科学分野で広く応用されている．身近なものには鉄道路線図がある．鉄道路線図は，駅を頂点，駅と駅をつなぐ路線を辺とみなせばグラフの一種である．
鉄道路線図では，駅と駅の間の距離や配置，線路の曲がり具合などは，実際のそれを正確に反映していない．利用者にとっては駅と駅の「つながり方」，つまり，駅（頂点）がどの路線（辺）で結ばれているかが重要であるため，線路が実際にどのような曲線を描いているかといった幾何的情報は捨象されている．
このように，「つながり方」に着目して抽象化された「点とそれをむすぶ線」の概念がグラフであり，グラフが持つ様々な性質を探求するのがグラフ理論である．つながり方だけではなく，「どちらからどちらへ向かってつながっているか」をも問題にする場合は，辺に矢印をつける．そのようなグラフを有向グラフと呼び，矢印のないグラフを無向グラフと呼ぶ．本研究では無向グラフのみを扱う．
グラフ理論の一分野として，グラフ着色分野がある．これは，ある条件を満たすようにグラフの頂点や辺に色を塗ることができるかを調べたり，既に頂点や辺に色が塗られたグラフが与えられた時に，どのような構造が潜んでいるのかを調べる研究分野である．前者は，「どのような地図も隣国どうしの色が異なるように４色で塗り分けることが出来る」という四色定理が有名である．後者は，「６人いれば互いに知り合いの３人組か，互いに知り合いではない３人組のどちらかが存在する」というラムゼー定理が有名である．ラムゼー定理は，「６頂点の完全グラフにおいて，それらの１５本の辺が赤と青で塗り分けられているときに，どこかに赤い三角形か青い三角形のどちらかが存在する」と言い換えることが出来る．ここで，完全グラフとは，全ての２頂点間を辺でつないだグラフのことである．
ラムゼー定理は３本とも色が同じ三角形の存在を示す定理である．一方，全ての辺の色が異なる部分構造の存在に関する研究がある．全ての辺の色が異なる辺着色グラフのことを異色グラフと呼ぶ．
年にとは，「色で辺彩色された個の頂点の完全グラフは， 個の辺素な予想と呼ぶ．辺彩色とは，同じ頂点か異色全域木に分解できる」と予想した．本稿ではこの予想をら出る辺の色が全て異なるように辺に着色することである．グラフ同士が辺素であるとは，それらのグラフが共通の辺をもたないということである．異色全域木とは，基のグラフの全ての頂点を持ち、全ての辺の色が異なる木のことである．これまでに，異色全域木に関する様々な研究が行われている．
が存在することから明らかで辺彩色された完全グラフに異色全域木が存在することは，異色全域とは，中心となる つの頂点から他の全ての頂点へ辺が１本ずつ出ているだけのグラある．ここで，フである．辺彩色の定義より，辺彩色された完全グラフには任意の頂点を中心点とする異色全域がは，予想において分解される異色全域木の候補には成り得ない．な存在する．しかし異色全域を候補に選んでしまえば，その中心点 に接続する全ての辺をその異色全域ぜなら，異色全域が使いきってしまい，分解される他の異色全域木はその中心点 をつなぐ辺を持てないからである．
予想において分解されるそれぞれの異色全域木の最大次数には制限がある．そこで，したがって，予想の解決にとって重要であろう．同研究室の永田，次数を制限した異色全域木の存在を示すことは
周は任意の 点 と任意の整数又はに対し， の次数が となる異色全域木の存在を示した．本研究はその結果を利用して，任意の 頂点の次数の和を指定できることを示した．すとする．
を の２つの頂点とする． を，なわち， を辺彩色完全グラフ又はを満たす整数とする．このとき， にはの次数の和が となる異色全域木が存在することを証明した．

2

複数のプレゼンテーション・リハーサル結果を比較検討するためのデータ閲覧方法
応用理学コース

情報科学分野白山 裕美子近年，大学などの教育機関や企業における知的生産の場では，仲間内によるフィードバックを得て，発表者の知識を洗練化したり，発表スキルの向上を図ることを目的として，プレゼンテーション・リハーサルが行われることが多い．それに伴い，各コミュニティーには，発表スライドやレビュアからの指摘，議論結果など，多様なデータが作成・蓄積される傾向にある．本研究では，このデータをプレゼンテーション・データとよぶ．
発表者の知識の洗練化や，メンバ間の知識の共有や継承を行うには，プレゼンテーション・データを適切に学習リソースとして有効活用することが望ましい．しかし，発表者はスライドを作成する際に，自身の行った前回のリハーサルに関するデータのみを参照するなど，蓄積されたデータのごく一部を参照するに留まることが多い．また，連続した複数回のリハーサルを単位とする活用を想定していないため，最終的なプレゼンテーションがどのような経緯で完成に至ったかなどを参考にできないのが現状である．
本研究では，これらの問題を解決するために，複数のプレゼンテーション・データをユーザのニーズに応じた視点で比較して見比べることで，発表者の知識状態の変遷や，他者との違いを確認させることが有効ではないかと考えた．そこで本研究では，同一の発表者による複数回のプレゼンテーション・データを関連づけて管理し，発表者の活用目的に応じてデータを横断的に比較・検討できるデータ閲覧方法の提案を行った．
さらに，本研究では，提案した方法にもとづき，ユーザの利用目的に応じたの多様な視点から，プレゼンテーション・データを比較・検討を可能とする「プレゼンテーション・データ閲覧システム」の設計と試作を行った．本システムのインタフェースには，左側に文字情報によるプレゼンテーション・データの概要，右側にリハーサル実施時期を表した
年表，各プレゼンテーションにおけるスライド画像の列やスライド切り替えタイミングなどを図的に表現する複数の情報提示パターンを定義し，左右の情報の組み合わせにより1つのプレゼンテーション・データをレコード表現する方式を考案した．本表現を用いることで，ユーザは発表者名や発表目的などのキーワードをもとに検索を行い，その結果を各々の差異を認識し易い状態で複数並べて比較することが可能となった．また，インタフェース上に提示する各レコードには，文脈的に予測されるユーザのニーズに対応するためのリンクを埋め込むことで，マウスクリックにより複数の視点を行き来しながら横断的なデータブラウジングを可能とするナビゲーション機能もあわせて実装した．
以上より，本研究では，従来の一般的なデータベースに見られる一覧性を主としたデー
タ参照方法に比べ，蓄積されたデータをより有効に活用できる方法を実現できた．これにより，初学者に対するプレゼンテーション教育に関して，スライド作成における典型的な作例やリハーサルを通じた改善方法などの例示による支援の可能性を示すことができた．

3

プレゼンテーション・リハーサルにおけるレビュアの指摘を収集・整理・検討するための議論支援システム
応用理学コース

情報科学分野徳永 勝也

近年，コンピュータを用いたプレゼンテーションは，他者に対する情報伝達の手段として，社会において幅広く実施されている．また，大学などの高等教育機関では，プレゼンテーションを通じたコミュニケーション能力の訓練を目的として，発表練習としてプレゼンテーション・リハーサルを実施する場合も多い．
プレゼンテーション・リハーサルは，仲間内による批評・批判を通じた能力向上を図るという点において，ピアレビューとよばれる作業の一種である．リハーサルでは，聴衆であるレビュアは発表に対する評価を行い，発表後にそれらの意見にもとづいた議論を通じて，プレゼンタの知識の改善を行う．このように，議論はプレゼンタにとって，レビュアからの指摘を受けることで自身の知識の問題点を認識し，それらの検討を通じて問題点に対する改善案を得るための重要な過程である．しかし，実際にはレビュアが発表の問題点に気づかず指摘を得られない，指摘された問題の原因を特定できないなどの理由から，その問題に対する改善案を得られないまま検討を終えてしまう場合があり，リハーサルの効果を十分に得られないことも多い．
本研究では，先に挙げた問題を解決するため，レビュアの指摘を効果的に収集・整理・検討する議論支援方法を提案した．通常の議論ではレビュアが指摘する毎に指摘の検討を行うが，本支援方法では，まず，発表に関する情報を必要に応じて各レビュアに与え，より詳しい指摘を各レビュアごとにすべて書き出させ,収集する．次に収集された指摘を各指摘が指す原因の箇所ごとに分類・整理することで検討箇所を特定する．そして，検討箇所ごとに発表に関する情報を参照しながら検討を行う．この検討を全ての検討箇所に対して行うことにより，参加者が感じた問題点をすべて網羅した上で，適切な改善方法を議論から得られる．
本研究では以上の方法を実現する為の議論支援システムの開発を行った．本システムは,プレゼンタのPCの画面をスクリーンに投影し，参加者全員がノート型PCを用いてLAN環境に接続しながら，以下の３つの過程を経て議論を進行させるための支援環境である．
(1) 指摘の収集：収集には，先行研究として筆者の所属する研究室で開発されているレビュー支援システムを用いる．本システムでは，LAN環境を利用して，発表の様子を撮影したムービや使用したスライド画像などの情報を活用し，レビュアに指摘をコメント文として作成させ，それらを収集・蓄積する．
(2) 知識の整理：各レビュアは，レビュー支援システムで得た情報を読み込んだ本システムのサーバシステムにクライアントアプリケーションからログインすることで，自らが作成したコメントと発表に関する情報を取得する．プレゼンタも同様にサーバにログインし，取得したスライド画像を用いてプレゼンテーション構造を作成する．プレゼンテーション構造は各スライドに上位構造として役割レベルや全体レベルを関連づけ，発表全体の構成を階層的に表現したものである．これに各レビュアがコメントをマッピングすることで，同一箇所へのコメントがまとめられ，検討箇所ごとに整理される．
(3) 改善案の検討：この段階では，全体構成の確認やコメントの分布を把握するために，プレゼンテーション構造を主とした画面と，検討箇所に関するスライドや時間などの検討に必要な情報を表示する2つの画面を切り替えながら検討作業を行う．検討作業中は，全てのクライアントの画面を同期することにより，各レビュアが自身のクライアントで情報を表示させると同時に，プレゼンタの画面を投影したスクリーンにも情報を表示させ，参加者全員が同じ情報を参照しながら議論を進めることができる．
本システムを用いて，学会発表を控えた院生のリハーサルにおける運用実験を行ったところ，50件のコメントが収集され，議論を通じて34件の改善案が得られた．今回の運用実験では，50件あったコメントを30件の検討箇所に整理し，すべての検討箇所に対して検討を行うことにより29件の具体的な改善案としてまとめることができた．これにより従来の議論方法で起こっていた，指摘の原因となる箇所が特定できず改善案を得られないまま検討が終わってしまうという問題を解決できていることが確認できた．また，検討にリソースを与えてやることにより，指摘の段階で気付けなかった5件の問題点にも気付き，改善案を得ることができた．以上のことから，本システムを用いることで，収集された指摘を効果的に利用してリハーサルの有効性を高められることが確認できた．

4学習活動促進のための学習目標アウェアネスを提示するウェブ調べ学習環境の構築
応用理学コース

情報科学分野田所 亮

学習中に知識や理解不足から生じる行き詰まりを解決するためには，教材や文献などを参考にその問題への知識や理解を深めようとする調べ学習がよく行われる．その中でもウェブ上のリソースを参考に行う調べ学習を本研究ではウェブ調べ学習と呼ぶ．本研究ではウェブ調べ学習を補助するツールとしてソーシャルブックマークに着目している．ソーシャルブックマークとはユーザが興味・関心を持ったウェブページをウェブ上にブックマークするウェブサービスである．複数のユーザのブックマークが集まることで集合知が形成され，今話題となっているページを得ることや自分と似た嗜好を持つユーザをお気に入りにしてそのユーザのブックマークも取得し有用なページを得ることができる．ソーシャルブックマークを用いることで日常的に興味・関心のある情報を取得でき，またウェブ調べ学習で知り得たページをブックマークとして整理できる．しかし一般的なソーシャルブックマークはウェブ調べ学習のために開発されたツールではないためウェブ調べ学習にそのまま利用すると以下の2つの問題が生じる．問題点⑴：ブックマークすることしかできないため知識の定着が期待できない．ウェブ調べ学習で知り得た情報への知識や理解を深めるには行き詰まりを解決した手順を振り返らせ，まとめさせることが重要であるが，他のツールを利用しない限り難しい．問題点⑵：学習目標を意識していないブックマークが存在する．本研究において学習目標とは学習目的を達成するための具体的な目標であり，例えば“ウェブアプリケーションを作る”という学習目的を持った学習者に“Cookieの取得方法が分からない”という行き詰まりが生じた場合，学習者はそれを解決するため“Cookieの取得方法を知りたい”という学習目標をもつ．ブックマークはこのような学習目標を基に行われたウェブ調べ学習中に登録されるものだけではない．友人やTwitterから知り得た情報で“何かに役立つかもしれない”という思いからブックマークされるものもある．このようなブックマークには学習目標が意識されておらず何に役立つ情報なのかがはっきりしていないため，それが明らかにならない限り活用されない．
これらの問題を解決するため，本研究では以下の2つの提案を行う．提案⑴：逆引きリファレンス作成環境を提供する．逆引きリファレンスとは目的からそれを達成するための方法や手段を探す辞典である．学習者には学習目標を表す文を逆引きリファレンス項目の見出しとして登録させ，参考になったブックマークや引用を整理させ，学習目標を達成する方法をまとめさせる．ウェブ調べ学習により知り得た知識をまとめさせることで学習内容の深い理解が期待でき，問題点⑴を解決する．提案⑵：学習目標アウェアネス提示ツー
ルを提供する．学習者のブックマーク履歴から現在の学習目標や学習者に潜在する学習目標を推測し，推測した学習目標とともにそれに関連するブックマークを学習者に提示する．現在の学習目標を提示する目的は学習目標を持っているにも関わらずブックマークするだけでまとめが書かれていない状況を防ぐことであり，これにより提案⑴の環境の利用を促す．潜在的な学習目標を提示する目的は問題点⑵のような学習目標を意識していないブックマークが“何に役立つ”情報なのかを意識させることであり，ブックマークを振り返るきっかけを与え学習活動を促す．
本論文では主に提案⑵のアウェアネスを提示する手法とそれを実装したツールについて述べる．提示する
学習目標とそれに関連するブックマークを算出するアルゴリズムや提示を行うタイミングなどアウェアネス提示に関する手法やそれを実装した本ツールの構成，また本ツールの評価実験とその考察について述べる．
評価実験は本ツールを情報系の学生と教員合わせて10名に利用してもらい行った．評価実験の目的は提案⑴の逆引きリファレンス作成環境の利用を促進できるかどうかと問題点⑵のようなブックマークを振り返るきっかけを与え学習活動を促すことができるかどうかを検証することである．実験期間中アウェアネス提示を受けた被験者は4名おり，ブックマークの再訪問や逆引きリファレンス項目作成がアウェアネス提示をきっかけに行われる事例が確認できた．また，アウェアネス提示を受けなかった被験者に比べると継続的に逆引きリファレンス項目作成やブックマーク登録が行われた．以上により本研究で提案するアウェアネス提示を行うことで提案⑴の逆引きリファレンス作成環境の利用の促進や問題点⑵のようなブックマークを振り返るきっかけを与え学習活動を促すことができると考えられる．

5

VLSI ߣ SiP ࡟ࠗࠕ࠙࠻⸳⸘ߦ߅ߌࠆ⥄േ㈩⟎㈩✢ߩ⎇ⓥ㩷㩷ᔕ↪ℂቇࠦ࡯ࠬ㩷 㩷 㩷 ᖱႎ⑼ቇಽ㊁㩷 㩷 㩷 㩷 㩷 㩷 㩷 㩷 㩷 ኹ ↰ ⠍ ᄥ㩷㩷ㄭᐕ㧘㜞ᕈ⢻ߢ቟ଔߥ㔚ሶᯏེ߇Ꮢ႐ߢ᳞߼ࠄࠇ㧘ߘߩࠦࠕㇱຠߢ޽ࠆ VLSI ߿ SiP ߩ㜞ᕈ⢻ൻᛛⴚ߇ᦸ߹ࠇߡ޿ࠆ㧚VLSI㧔Very Large Scale Integration㧕ߣߪ㧘࠻࡜ࡦࠫࠬ࠲⚛ሶࠍ࠴࠶ࡊ਄
ߦᢙం⒟ᐲ߹ߢ㓸Ⓧߒߚ㔚ሶ࿁〝ߩߎߣߢ㧘ᄙᯏ⢻࡮㜞ᕈ⢻ߩߚ߼ߩ⵾ㅧᓸ⚦ൻᛛⴚ߇㊀ⷐߢ޽ࠆ㧚
SiP(System in a Package)ߣߪ㧘ࠪࠬ࠹ࡓ࡟ࡌ࡞ࠍ᭴ᚑߔࠆᄙᢙߩ VLSI ࠴࠶ࡊࠍ 1 ߟߦߒߚታⵝㇱຠߩߎߣߢ㧘ᄙᢙߩ࠴࠶ࡊ㈩✢ࠍ㈩⟎ߒᕈ⢻଻⸽ߔࠆᛛⴚ߇㊀ⷐߢ޽ࠆ㧚
VLSI ߣ SiP ߦߪ㧘୘೎ߩ⸳⸘⺖㗴߇޽ࠆ㧚VLSI ߩ⸳⸘⺖㗴ߣߒߡߪ㧘ାภຠ⾰଻⸽໧㗴߇᜼ߍࠄࠇࠆ㧚VLSI ߩ⵾ㅧᓸ⚦ൻᛛⴚߦߣ߽ߥ޿㧘ାภ㈩✢㑆ߩㄭធߦࠃࠆାภᐓᷤ㧔ࠢࡠࠬ࠻࡯ࠢ㧕߇ේ࿃ߣߥࠅᕈ⢻଻⸽߇ߢ߈ߥߊߥߞߡ޿ࠆ㧚߹ߚ SiP ߩ⸳⸘⺖㗴ߣߒߡߪ㧘⥄േ㈩✢ᛛⴚ߇਄ߍࠄࠇࠆ㧚SiP ߢߪ⇣ߥࠆ․ᕈߩ VLSI ࠍታⵝߦ઻߁㔚᳇․ᕈߩ⠨ᘦ߇ਇนᰳߢ㧘ᓥ᧪ߪੱᚻߢ⸳⸘ߒߡ޿ࠆ߇㧘࠴࠶ࡊ㓸ⓍᢙߩჇᄢߢ㈩✢ᢙ߇Ⴧ߃੹ᓟߪੱᚻ㈩✢߇࿎㔍ߣ੍ᗐߐࠇߡ޿ࠆ㧚ߎࠇࠄߩ⸳⸘⺖㗴ߦኻߔࠆᓥ᧪ᛛⴚߣ໧㗴ὐߪ㧘ᰴߩߣ߅ࠅߢ޽ࠆ㧚߹ߕ VLSI ߩࠢࡠࠬ࠻࡯ࠢߩ࿁ㆱᛛⴚߢߪ㧘ߘߩේ࿃߇㈩✢ᒻ⁁ߢ޽ࠆߎߣ߆ࠄ㈩✢⸳⸘ߩୃᱜᛛⴚ߇ਛᔃߢ㧘㈩✢㑆㓒ࠍᐢߍࠆߎߣ߿㧘ࠪ࡯࡞࠼㈩✢ߩᝌ౉ߥߤ߇޽ࠆ㧚ߒ߆ߒ㜞ኒᐲߥ㈩✢ߢߪߎࠇࠄߩ㗔ၞ⏕଻߇ߢ߈ߕ㧘߹ߚ㈩✢⚻〝ᄌᦝߢᣂߚߦାภㆃᑧࠍ↢ߓࠆ⺖㗴߇ᱷࠆ㧚ᰴߦ SiP ⥄േ㈩✢ᛛⴚߢߪ㧘BGA
㧔Ball-Grid-Array㧕߿ CSP㧔Chip-Scale-Package㧕ߥߤ᭴ㅧߦ․ൻߒߚᚻᴺ߇ਛᔃߢ㧘㔚᳇⊛ᓇ㗀ࠍ⠨ᘦߒߚ㈩✢ᚻᴺߪឭ᩺ߐࠇߡ޿ߥ޿㧚ᧄ⺰ᢥߪ㧘ߎࠇࠄ VLSI ߩࠢࡠࠬ࠻࡯ࠢ࿁ㆱᛛⴚߩ⺖㗴ߣ SiP ⥄േ㈩✢ߩ㔚᳇⊛ᓇ㗀ࠍ෻ᤋߔࠆ⥄േ㈩✢ᚻᴺߦߟ޿ߡឭ᩺ߔࠆ߽ߩߢ޽ࠆ㧚ឭ᩺ߔࠆࡠࠬ࠻࡯ࠢ࿁ㆱᛛⴚߪ㧘㈩⟎࡟ࡌ࡞߆ࠄߩᡷༀᚻᴺߢ㧘߹ߕ㈩✢ᒻ⁁ផቯߣࠢࡠࠬ࠻࡯ࠢ⹏ଔ㑐ᢙࠍᣂߚߦዉ౉ߒ㧘ߎࠇࠄߦࠃࠅ㈩⟎ᡷༀߔࠆ㧚ᧄᚻᴺࠍㆡ↪ߒߚታ࿁〝㧔8 ࡆ࠶࠻ CPU㧕ߢߪ㧘⚂ 75%ߩਗ⿛〒㔌ࠍ࿁ㆱߔࠆߎߣ߇್᣿ߒߡ޿ࠆ㧚߹ߚߎࠇࠄࠍࠃࠅല₸ࠃߊ߅ߎߥ߁ߚ߼ߩ ECO㧔৻ㇱᡷༀᴺ㧕ᴺ߽ឭ᩺ߒ㧘ಣℂᤨ㑆ߩ⍴❗
߇࿑ࠇࠆߎߣࠍ᣿ࠄ߆ߦߒߚ㧚ឭ᩺ߔࠆ SiP ⥄േ㈩✢ᛛⴚߪ㧘㈩⟎ᚻᴺࠍࡌ࡯ࠬߣߒߚ㈩✢ᚻᴺߢ㧘⏕₸⺰⊛㈩⟎ᚻᴺߦၮߠ߈㈩✢㐳߿㈩✢੤Ꮕ㧘㈩✢⋧੕ߩࠬࡍ࡯ࠪࡦࠣߥߤߩ⹏ଔ㑐ᢙߢ㔚᳇⊛೙⚂߇෻ᤋߢ߈ࠆ㈩✢ᚻᴺߢ޽ࠆ㧚޿ߊߟ߆ߩ SiP ㈩✢଀ߢታ㛎ߒߚߣߎࠈ㧘ઁߩ㈩✢ᚻᴺߢߪᓧࠄࠇߥ޿㈩✢⋧੕ߩ೙⚂ࠍ෻ᤋߒߚ㈩✢ᒻ⁁ࠍ૞ࠅ಴ߔߎߣ߇್᣿ߒߚ㧚ߥ߅ᱷߐࠇߚ⺖㗴ߣߒߡߪ㧘8.5+ ࠢࡠࠬ࠻࡯ࠢ࿁ㆱ㈩✢ᚻᴺߢߪ㧘ߐࠄߥࠆታ㛎ߦࠃࠆᬌ⸽ߩታᣉߣ㧘SiP ㈩✢ᚻᴺߢߪ㧘ࠃࠅታ↪⊛ߥ 5K2 ࿁〝ߢᄙጀ㈩✢ߦࠃࠆ⹏ଔࠍⴕ߁ߎߣߢ޽ࠆ㧚એ਄㧘ᧄ⎇ⓥߦࠃࠅ㧘VLSI ⵾ㅧ෸߮ SiP ⵾ㅧߦ߅޿ߡ㜞ᕈ⢻ൻ㧘ૐࠦࠬ࠻ൻ߇ᦼᓙߢ߈㧘ㄭᐕߩ⸳⸘ᛛⴚߩ㧝ߟ߇⸃᳿ߐࠇߚߣ⠨߃ࠄࠇࠆ㧚6