伊藤大雄研究室の紹介
2014年11月20日
11/29/2014
1
伊藤大雄研究室の研究
• 離散アルゴリズムで
– ビッグデータ
– グラフ・ネットワーク
– 計算困難性
– パズル・ゲーム
• などに挑む！
11/29/2014
2
ビッグデータに劣線形時間で挑む！
11/29/2014
3
JST CREST ビッグデータ時代に向けた革新的アルゴリズム基盤
• ビッグデータに「劣線形時間パラダイム」※をキーワードに
挑む。（※伊藤の造語）
• 総勢24名（京大、電通大、東大、東北大、NII、九大、北大、
神戸大 他）
• 期間: 2014.10〜2020.03(予定)
• 予算総額: 約３億円（予定）
• 英語名：Foundations of Innovative Algorithms for Big Data
• 略称：ABD14
11/29/2014
4
ジャンケンの研究 [CGGA 10, 北京] etc.
殿
石
紙
鋏
蚤
11/29/2014
5
折り紙の研究
[CGGA10, 北京][COCOA 11, 張家界][CCCG2014, Halifax][WALCOM2015, Dhaka] etc.
Making Polygons by Simple Folds and One Straight Cut
• Erik D. Demaine*, Martin L. Demaine*, Andrea Hawksley*, Hiro Ito, Po‐Ru Loh*, Shelly Manber* and Omari Stephens*,
• *MIT
11/29/2014
Easy!
Difficult!
6
ゲームの必勝法の研究
[HERCMA 09, アテネ][EuroCG 11, スイス][CCCG 11, トロント] etc.
Ex. Objective Animal
90k° rotation
and reflection
are allowed.
• Partial 2 player game Played on the Infinitely large chess board.
• Fix an animal (=polyomino).
• Alice chooses one cell in each turn.
• Bob puts a whole copy of the animal in each turn.
• Alice wins if she constructs a copy of the animal. 11/29/2014
Alice wins!
• Bob’s objective is to prevent Alice.
7
川渡り問題の研究 [FUN 12, ベネチア]
• [From Alcuin of York, “Problems to Sharpen the Young”]
• Three men, each with a sister, must cross a river using a boat which can carry only two people, so that a woman whose brother is not present is never left in the company of another man. How do they?
11/29/2014
8
グリーンアルゴリズム
（家電エコ・マネッジメント）[WAOA 11, ドイツ]
I don’t know when the next user arrives…
Shutdown?
Keep standby?
Minimize the cost!!!
11/29/2014
Panasonic共同研究 (2008〜2011）→Wolf Bein (UNLV, USA)と継続中
9
伊藤大雄研究室の大雑把なまとめ
• 研究室のコンセプト
–
–
–
–
研究と学生生活を楽しんで
国内外の一流の研究者や同世代の仲間と交流し
国際的に通用する高水準の成果（定理）を出し
海外の国際会議で成果を発表しよう！
• 標語
11/29/2014
10
11/29/2014
11