アルゴリズム教育研究分野（ES4) 研究室紹介.

Presentation on theme: "アルゴリズム教育研究分野（ES4) 研究室紹介."— Presentation transcript:

1 アルゴリズム教育研究分野（ES4) 研究室紹介

2 研究室の教職員，大学院生 教授 増田 准教授 山口 助教 斎藤 技術職員 山中 博士1年生 1名 修士2年生 7名 修士1年生 6名

3 研究分野（キーワード） アルゴリズム データ構造，データ検索 組合せ最適化 グラフ・ネットワーク パターン情報処理

4 配属定員と卒研テーマ分類 配属定員10名（早期配属者1名を含む） A 情報表示のためのアルゴリズム 4名 B グラフアルゴリズムとその応用
3名 C　幾何的特徴を持つグラフに対する　 　　アルゴリズム

5 A 情報表示のためのアルゴリズム 複雑な情報を，人間にとって分かりやすく 表示するためのアルゴリズム ・ グラフで表現できる構造や関係の描画
・　グラフで表現できる構造や関係の描画 ・　図中への文字列の配置（ラベル配置）

6 A1　グラフの描画アルゴリズム 階層描画の例 　科目間関係図 科目 (頂点) 科目間の 関係 (辺) 辺交差数 　　1282

7 A1　グラフの描画アルゴリズム 複雑なグラフを 見やすく自動描画 する方法の開発 辺の描き方を 工夫 辺交差数 　　　59

8 A2 デフォルメ路線図作成アルゴリズム 路線の形状をより簡潔にしたい． より複雑な路線図も扱いたい． ⇒ 新しい方法の開発 大阪市営地下鉄
グラフ描画の手法を応用した結果 路線の形状をより簡潔にしたい． より複雑な路線図も扱いたい． ⇒ 新しい方法の開発

9 ラベルの縦書きなど，多様なラベル配置を可能に
A3　地図ラベル配置アルゴリズム ラベルの縦書きなど，多様なラベル配置を可能に

10 B グラフアルゴリズムと その応用に関する研究
技術者のすべきこと 本テーマの応用，意義

11 B2 テキスト分析に関する研究 「良いものを作れば売れる」 「お客様のニーズに応える」 「ユーザが欲しいもの」は何？
良いものはみんな欲しいはず みんなが欲しいものは売れる 「お客様のニーズに応える」 ユーザが欲しいものは売れる 「ユーザが欲しいもの」は何？ ×　分からないからとりあえず良いものを作る ×　考えるのは営業の仕事．技術者には無関係

12 B2 テキスト分析に関する研究 「情報を制するものは世界を制す」 情報源 書き込みの内容 掲示板，ブログ，SNS
パブリックコメント，消費者窓口 情報の多くはテキスト 書き込みの内容 評判，欲しい機能 不満，改善すべき点 テキスト分析で情報を抽出

13 B グラフアルゴリズムとその応用 単語の出現回数 単語のつながり B2 テキスト分析に関する研究 情報を自動的に入手 話題の抽出，絞り込み
会 B2 テキスト分析に関する研究 情報を自動的に入手 単語の出現回数 話題の抽出，絞り込み 単語のつながり 単語同士を線で結ぶ テーマB1　部分グラフの抽出に関する研究 トピック毎に単語を分類 ユーザの興味，嗜好の変化を追跡 23 25 委員 教育 3 8 14 行政 長 B1 のある問題の解法で世界一

14 C 幾何的特徴を持つグラフに対するアルゴリズムの開発とその応用
幾何的特徴を持つグラフ：幾何構造でグラフが表現できる 例：区間グラフ 各区間はグラフの頂点と対応 ２つの区間に重なり　⇔　対応する頂点間に辺がある 区間グラフの彩色問題 この工程表には何人の作業員が必要か？ 省領域アルゴリズムの開発と実装 タンパク質の機能解析のためのアルゴリズムの開発 組合せゲーム・パズルに対するアルゴリズムの開発

15 線形未満の計算領域で動作するアルゴリズムの開発
C1　省領域アルゴリズムの開発と実装 至るところにビッグデータがある 購買履歴，SNS，道路ネットワーク など ビッグデータに対する効率的な処理が必要 データサイズはあまりにも巨大 データを一度にメモリに格納できない 多項式領域アルゴリズムは動作しない！ 線形未満の計算領域で動作するアルゴリズムの開発

16 C2 タンパク質の機能解析のためのアルゴリズム
複数のアミノ酸が鎖状に連結してできた化合物 タンパク質をグラフで表現 コンタクトマップグラフ ディスクインターセクショングラフ C-PMTの立体構造 問題例：２つのタンパク質の共通の部分構造を求める 毒性を持つ構造を調べる 新種タンパク質の機能を計算機によって解析する 最大共通部分グラフの抽出アルゴリズムの開発 組合せ剛性理論を用いた機能構造解明

17 C3 組合せゲーム・パズルに対するアルゴリズム
ペンシルパズル（数独，スリザーリンク，ナンバーリンクなど） ボードゲーム（将棋，オセロなど） 落ちゲー（ぷよぷよ，テトリスなど） 詰め込みパズル（ペントミノ，DeeCubeなど） 陣取りゲーム（ボロノイゲームなど） 研究テーマ 高速なパズルソルバー ゲーム・パズルの完全解析 パズル問題の自動生成

18 年間スケジュール 正しく動作する効率のよいプログラムの開発 充実した1年を過ごせます!! 研究テーマ説明 研究室配属 研究環境の整備
4月 5月 7月 8月 1月 2月 研究テーマ説明 研究室配属 研究環境の整備 グループ分け 卒業研究 院試勉強 卒論提出・発表 中間発表（数回） 卒業論文執筆 本読みゼミ プレゼン プログラミング課題 ・アルゴリズム技法の習得 プログラミング課題 本読み（AHUゼミ） 正しく動作する効率のよいプログラムの開発 充実した1年を過ごせます!!

19 期待する学生像 プログラミングが好きな人 離散の世界が好きな人 やる気・元気のある人 効率的なプログラムを書きたい！
コンピュータで解きたい問題がある！ 離散の世界が好きな人 グラフが好き！ パズル・ゲームが好き！ やる気・元気のある人

20 研究室見学 2E-402 B-404 （山口） 場所：４階 ２E-402 （学科事務室の１階上） 日時：本日15時～17時 B-402
　　　　　（学科事務室の１階上） 日時：本日15時～17時 B-402 （増田）