アルゴリズム教育研究分野 （ES4) 研究室紹介 研究室の教職員，大学院生 教授 准教授 助教 技術職員 博士1年生 修士2年生 修士1年生 増田 山口 斎藤 山中 1名 7名 6名 研究分野（キーワード） アルゴリズム データ構造，データ検索 組合せ最適化 グラフ・ネットワーク パターン情報処理 配属定員と卒研テーマ分類 配属定員10名（早期配属者1名を含む） A 情報表示のためのアルゴリズム 4名 B グラフアルゴリズムとその応用 3名 C 幾何的特徴を持つグラフに対する アルゴリズム 3名 A 情報表示のためのアルゴリズム 複雑な情報を，人間にとって分かりやすく 表示するためのアルゴリズム ・ グラフで表現できる構造や関係の描画 ・ 図中への文字列の配置（ラベル配置） A1 グラフの描画アルゴリズム 階層描画の例 科目間関係図 科目 (頂点) 科目間の 関係 (辺) 辺交差数 1282 A1 グラフの描画アルゴリズム 複雑なグラフを 見やすく自動描画 する方法の開発 辺の描き方を 工夫 辺交差数 59 A2 デフォルメ路線図作成アルゴリズム 大阪市営地下鉄 グラフ描画の手法を応用した結果 路線の形状をより簡潔にしたい． ⇒ 新しい方法の開発 より複雑な路線図も扱いたい． A3 地図ラベル配置アルゴリズム ラベルの縦書きなど，多様なラベル配置を可能に B グラフアルゴリズムと その応用に関する研究 • B2 テキスト分析に関する研究 • B1 部分グラフの抽出に関する研究 • 技術者のすべきこと • 本テーマの応用，意義 B2 テキスト分析に関する研究 • 「良いものを作れば売れる」 – 良いものはみんな欲しいはず – みんなが欲しいものは売れる • 「お客様のニーズに応える」 – ユーザが欲しいものは売れる • 「ユーザが欲しいもの」は何？ × 分からないからとりあえず良いものを作る × 考えるのは営業の仕事．技術者には無関係 B2 テキスト分析に関する研究 • 「情報を制するものは世界を制す」 • 情報源 – 掲示板，ブログ，SNS – パブリックコメント，消費者窓口 – 情報の多くはテキスト • 書き込みの内容 – 評判，欲しい機能 – 不満，改善すべき点 テキスト分析で情報を抽出 B グラフアルゴリズムとその応用 会 • B2 テキスト分析に関する研究 – 情報を自動的に入手 • 単語の出現回数 – 話題の抽出，絞り込み • 単語のつながり 23 25 教育 14 委員 3 8 行政 長 – 単語同士を線で結ぶ – テーマB1 部分グラフの抽出に関する研究 • トピック毎に単語を分類 • ユーザの興味，嗜好の変化を追跡 B1 のある問題の解法で世界一 C 幾何的特徴を持つグラフに対するア ルゴリズムの開発とその応用 • 幾何的特徴を持つグラフ：幾何構造でグラフが表現できる – 例：区間グラフ • 各区間はグラフの頂点と対応 • ２つの区間に重なり ⇔ 対応する頂点間に辺がある この工程表には何人の 作業員が必要か？ 区間グラフの彩色問題 1. 省領域アルゴリズムの開発と実装 2. タンパク質の機能解析のためのアルゴリズムの開発 3. 組合せゲーム・パズルに対するアルゴリズムの開発 C1 省領域アルゴリズムの開発と実装 • 至るところにビッグデータがある – 購買履歴，SNS，道路ネットワーク など • ビッグデータに対する効率的な処理が必要 – データサイズはあまりにも巨大 – データを一度にメモリに格納できない 多項式領域アルゴリズムは動作しない！ 線形未満の計算領域で動作するアルゴリズムの開発 C2 タンパク質の機能解析のためのアルゴリズム • タンパク質 – 複数のアミノ酸が鎖状に連結し てできた化合物 • タンパク質をグラフで表現 – コンタクトマップグラフ – ディスクインターセクショングラフ C-PMTの立体構造 http://www.kyoto-u.ac.jp/notice/05_news/documents/070308_1.htm 問題例：２つのタンパク質の共通の部分構造を求める •毒性を持つ構造を調べる •新種タンパク質の機能を計算機によって解析する 1. 最大共通部分グラフの抽出アルゴリズムの開発 2. 組合せ剛性理論を用いた機能構造解明 C3 組合せゲーム・パズルに対するアルゴリズム • 組合せゲーム・パズル – – – – – ペンシルパズル（数独，スリザーリンク，ナンバーリンクなど） ボードゲーム（将棋，オセロなど） 落ちゲー（ぷよぷよ，テトリスなど） 詰め込みパズル（ペントミノ，DeeCubeなど） 陣取りゲーム（ボロノイゲームなど） • 研究テーマ – 高速なパズルソルバー – ゲーム・パズルの完全解析 – パズル問題の自動生成 年間スケジュール 5月 4月 研 究 テ ー マ 説 明 研 究 室 配 属 研 究 環 境 の 整 備 グ ル ー プ 分 け 7月 8月 1月 2月 卒 業 論 文 執 筆 卒 論 提 出 ・ 発 表 卒業研究 院試勉強 本読みゼミ プレゼン プログラミング課題 ・アルゴリズム技法の習得 1.プログラミング課題 2.本読み（AHUゼミ） 中 間 発 表 （ 数 回 ） 正しく動作する効率の よいプログラムの開発 充実した1年を過ごせます!! 期待する学生像 • プログラミングが好きな人 – 効率的なプログラムを書きたい！ – コンピュータで解きたい問題がある！ • 離散の世界が好きな人 – グラフが好き！ – パズル・ゲームが好き！ • やる気・元気のある人 研究室見学 2E-402 • 場所：４階 ２E-402 （学科事務室の１階上） • 日時：本日15時～17時 B-404 （山口） B-402 （増田）
© Copyright 2024 ExpyDoc
