08 2018/09 10
26272829303101
0203 04 05 060708
0910 1112131415
16171819202122
2324 25 26 272829
30010203040506
Click セミナー

過去のセミナー

開催日2018年7月2日(月曜日)
開催時間16時30分-17時30分
発表者堀山 貴史 
発表者の紹介埼玉大学
タイトルメンバー紹介・開催趣旨・パッキングとガジェット 
発表の概要
SSSW2018.07の参加メンバーおよび開催趣旨を説明した後、パッキングとガジェットに関する最近の興味について講演する。
開催場所VBL 301B
接続サイト神田ラボ, 京大ラボ
 
開催日2018年7月2日(月曜日)
開催時間17時30分-18時30分
発表者上原 隆平 
発表者の紹介北陸先端科学技術大学院大学
タイトル(1) 展開図の切り出し問題
(2) (n^2-1)パズルの最長最短手数 
発表の概要
(1) 展開図の切り出し問題
大きな紙から,多くのパッケージを作り出す問題を考える.カットにコストがかかるため,なるべくカットの長さを短くしたい.また資源削減のため,ゴミは出したくない.こうした場合,パッケージの展開図をタイリングに限定するとよいだろう.ここではさらに,パッケージは4単面体とする.4単面体の展開図で,なるべくカットが短く,かつ,なるべく容積を大きくするには,どういった展開図を選べばよいかという問題について現状を発表する.なおこれは Erik Demaine, Martin Demaine との共同研究である.

(2) (n^2-1)パズルの最長最短手数
古来より,15パズルを一般化した(n^2-1)パズルは非常によく研究されている.特に,二つの配置が与えられたときに,次の結果が知られている.(a)互いに行き来できるかどうかは,パリティをチェックすれば線形時間で判定できる.また,互いに行き来できる場合においては,(b-1)O(n^3)回のスライドで十分である.(b-2)Ω(n^2)回のスライドが必要な配置がある.(c)最短手数を求める問題はNP完全である.(c)については,最近,単純な証明がDemaineたちによって示されている.ところで湊と上原は,最近,(b'-1)互いに行き来できる場合は,実際にはO(n^2 log n)回のスライドで十分であることに気づいた.これを最長最短手数の計算に活用できないだろうか.n=4,つまり元の15パズルでの,最長最短手数は80手であるが,この記録を例えば(4×5)-1=19パズルに拡張したい.
開催場所VBL301B
接続サイト神田ラボ,京大ラボ