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

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

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

2 研究室の教員，大学院生 教授 増田 准教授 山口 博士3年生 1名 修士2年生 8名 修士1年生 4名

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

4 配属定員と卒研テーマ分類 配属定員8名 A　情報表示のためのアルゴリズム 4名 B　組合せ最適化問題に関する 　　基礎研究

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

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

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

8 A2 サイズの大きなグラフに対する描画法 2つのアプローチ 頂点の周辺に関係の 弱い頂点を置かない 注目頂点を含む部分 グラフを適切に描画
　 頂点が数百個以上 ⇒ 描画が複雑になる ⇒ 特定の頂点の周辺の 　 状況を把握しづらい 2つのアプローチ 頂点の周辺に関係の 弱い頂点を置かない 注目頂点を含む部分 グラフを適切に描画 頂点数200, 辺数250

9 A3　ラベル配置アルゴリズム 地図への地名配置が典型的 今年度の卒論では，グラフ描画へのラベル配置

10 デフォルメ路線図への駅名配置 Osaka Metro （大阪市営地下鉄） 描画領域の制限がある場合 広島電鉄
領域の制限を満たしながら駅名表示

11 グラフ描画への辺ラベルの配置 ES4研究室で開発したアルゴリズムの改良

12 B 組合せ最適化問題に関する 基礎研究 問題の解法を設計する． 性能を他の研究と競う． B1 部分グラフの抽出に関する研究
競技プログラミングとほぼ同じ B1　部分グラフの抽出に関する研究 B2　集合の分割に関する研究 B3　要素の順序付けに関する研究

13 Ｐ vs ＮＰ問題と組合せ最適化 Stephen A. Cook Richard M. Karp 1982 Turing賞受賞
７つのミレニアム懸賞のうちの一つ 賞金１００万ドル（クレイ数学研究所） ホームページに載せるだけでOK! Stephen A. Cook 1982 Turing賞受賞 NP完全問題の存在を示した（計算が困難な問題の１種） Richard M. Karp 1985 Turing賞受賞 組合せ最適化問題の多くがNP完全であることを証明

14 Karp の21の問題（1972） 赤字：研究テーマ 計算機の性能向上（速度は10億倍以上） マルチコアプロセッサの普及
SAT 0–1 IP Clique (B1) Set packing Vertex cover (B1) Set covering (B1) Feedback node set Feedback arc set (B3) Directed Hamilton circuit Undirected Hamilton circuit 3-SAT Graph Coloring (B2) Clique cover (B2) Exact cover (B1, B2) Hitting set Steiner tree 3-dimensional matching Knapsack Job sequencing Partition Max cut 赤字：研究テーマ 　計算機の性能向上（速度は10億倍以上） 　マルチコアプロセッサの普及 電子情報通信学会誌2018年3月号特集 「グラフアルゴリズムの最先端」

15 B1 部分グラフの抽出に関する研究 受賞など： クリーク＝辺で繋がっている頂点の集まり 最大クリークを求める右図の正解は２，５，７ ３ ２
１，２，８ ２，３，８ ４，８ 受賞など： ２ ５ ８ ７ １ ４ KJCEE 優秀論文発表賞(2011, 2017), 奨励賞(2012), ACS 2013 (selected 30%) Discrete Applied Mathematics vol.223, pp , May 2017 世界最速：Optimal Table 法　（ライバルが少ない？）

16 B2 集合の分割に関する研究 学生を研究室に配属 彩色問題 多くの学生の希望通りに割り当てたい どうなれば幸せ？計算法？
応用：　資源配分，仕事割当 彩色問題 ４色定理「あらゆる地図は４色で塗り分けられる」 グラフを少ない色数で塗る 応用：　処理の並列化 計算の干渉を回避する 出典：2018 Beagle Science Corp. HP

17 B3 要素の順序付けに関する研究 1位：豊島 7位：佐藤 大会の順位 残りの人の順位？ データ分析 大会の順位付け 産業連関表
因果関係の推定 大会の順位 出典：日本将棋連盟ホームページ 　　　第67期王将リーグ

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

19 言語別給与ランキング（2017年版） Java Scala 求人数最多：Java ・サーバ，基幹業務， アプリ，組み込み， データ分析など
　アプリ，組み込み， 　データ分析など 給与　　　：Scala ※ 急成長　　：Python 　　　　　　Kotlin ※☆ ※ Java派生言語 ☆Android 開発言語として正式に採用（2017年) Java 出典：Hrog.net HP

20 期待される学生像 考えることが好きな人（パズルが好き） プログラミングが好きな人，仕事にする人 Java に興味のある人
競技プログラミング参加者 こっそり世界一になりたい人 古くて有名　　　　　　（誰も手を出さない） 新しい研究分野

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