スケジュール

10:30 ～ 18:00

PythonによるZDDを用いたグラフ処理入門 -組合せ爆発を乗り越える- 西野 正彬 (NTTコミュニケーション科学基礎研究所 特別研究員) 石畠 正和 (NTTコミュニケーション科学基礎研究所 研究主任)

セミナー内容

PythonによるZDDを用いたグラフ処理入門 -組合せ爆発を乗り越える-

ゼロサプレス型二分決定図 (ZDD) は, 京都大学情報学研究科 湊真一教授が考案 したデータ構造です．ZDDには，組合せ集合を圧縮して表現し，かつ ，圧縮したままで様々な計算を効率よく実行できるという特徴があり，大規模グラフデータを対象とした最適化や数え上げ問題を解くための強力な道具として注目を集めています．京都賞受賞者であるD. Knuth先生が執筆された教科書にも大きく取り上げられています．今回のスクールではZDDとそのグラフ処理への 応用を中心に説明します．演習では実際にPython言語を使って，ZDDを用いたグラフを処理する手続きを体験して、具体的な問題解決方法の理解を深めてもらいます。

受講要件

京都大学に所属する学生・教職員に限ります。

前提知識

Pythonの基本を習得済みのこと（必須）。

コンピュータサイエンスの基礎知識があれば理解しやすいが必須とはせず、必要な知識をセミナー中に復習します。

演習事前準備

Google Colaboratoryを利用するためにはGoogleアカウントが必要

Pythonの基本，Google Colaboratoryの使い方に慣れていなければ Kubar上の演習キット で予習しておくこと

教材は右記にあるので，目を通しておくことhttps://github.com/nsnmsak/graphillion_tutorial

講師情報