大会名称
2010年 情報科学技術フォーラム(FIT)
大会コ－ド
F
開催年
2010
発行日
2010/8/20
セッション番号
14
セッション名
組合せパズルの数理とコンピュテーション
講演日
2010/9/9
講演場所(会議室等)
第3イベント会場
講演番号
14-1
タイトル
組合せパズルの数理とコンピュテーション
著者名
上原　隆平, 
キーワード
抄録
迷路やクロスワード、数独など、パズルは人間の知性の結晶であるが、その背後にある理論は組合せ理論を基盤にした計算理論の範疇にある。近年、これらを含むパズルの計算量の研究が進み、更に計算の立場から、パズルの求解や生成の困難性が数理的に議論できるようになってきた。世界的にも数理、計算、さらにアートを融合したプロジェクトが注目を集めている。わが国でも例えば出力が任意の絵になるような迷路の生成、与えられた図形を組み上げる折り紙の自動生成などの困難に見える問題を解くアルゴリズムの開発も進み、計算理論のコミュニティーでも組合せパズルのプロジェクトが立ち上がっている。本企画では、これらの組合せパズルの最先端研究の一部をわかりやすく、実演を含めて紹介する。