第155回アルゴリズム研究会プログラム

日時・会場

日程2015年11月20日(金),21日(土)
会場指宿市民会館
住所指宿市東方12000
交通案内こちらを御覧ください
現地世話人小野 廣隆先生(九州大学)

発表題目

11月20日(金) 10:00-18:00
発表番号時間題目著者(○は発表者)など
AL キャンセル 局所郵便切手問題に関する多項式時間還元の比較 ○松原 俊一(青山学院大学)
AL 10:00-10:25 Independent Set Reconfiguration Problem on Caterpillars ○Takeshi Yamada (JAIST),Ryuhei Uehara (JAIST)
AL 10:25-10:50 Better Online Steiner Trees on Outerplanar Graphs ○Akira Matsubayashi(Kanazawa Univ.)
10:50-11:00  休憩(10分)
CAS 11:00-11:25 不可分フロー平滑化問題に対するタイセットを用いた分散アルゴリズムの考察 ○山田 正史,石垣 原野,篠宮 紀彦(創価大)
CAS 11:25-11:50 On composing a disruption tolerant tree in a network with intermittent links based on stress centrality ○Genya Ishigaki,Norihiko Shinomiya(Soka Univ.)
CAS 11:50-12:15 電子回路CPGネットワークを用いた四肢歩行パターン切り替え現象の再現 ○丸山 陽央,小宅 智史,笹川 成輝(新潟大),市村 智康(群馬高専),前田 義信(新潟大)
12:15-13:55  昼休み(100分)
MSS 13:55-14:20 Application of Quadratic Placement to Intensity Modulated Proton Therapy ○Yasuhiro Takashima(Univ. of Kitakyushu),Shohei Mizutani(Univ. of Tsukuba), Kenji Hotta,Ryosuke Kohno(National Cancer Center Hospital East),Yuichi Nakamura(NEC)
MSS 14:20-14:45 分散アルゴリズムの実行列からプログラム合成とそのプログラム検証討 ○山根 智(金沢大)
MSS 14:45-15:10 ヘテロジニアス環境下における並列処理パターンのペトリネットモデリング ○島袋 梓,名嘉村 盛和(琉大)
15:10-15:20  休憩(10分)
AL キャンセル Weighted Efficient Dominating Set Problem in Two-Directional Orthogonal Ray Graphs (Short talk) ○Asahi Takaoka(Tokyo Tech.)
AL 15:20-15:45 Degree-Constrained Orientation for Graphs with Polynomially Many Potentially Maximal Cliques ○Hirotaka Ono(Kyushu Univ.),Yota Otachi (JAIST)
AL 15:45-16:10 頂点被覆数が小さいグラフの最適消去木の計算について ○小林 靖明(学習院大学),玉木 久夫(明治大学)
16:10-16:20  休憩(10分)
CAS 16:20-16:45 On Evasion Games on Graphs ○Satoshi Tayu,Shuichi Ueno(Tokyo Tech)
CAS 16:45-17:10 ビットの照合順序を考慮したトライに基づくパケット分類手法 ○小林 由人,高橋 俊彦,三河 賢治(新潟大),田中 賢(神奈川大)
CAS 17:10-17:35 集中化と多様化を交互に繰り返すPSOによるIIRフィルタ設計 ○山本 健造,西村 勇司,陶山 健仁(東京電機大)
CAS 17:35-18:00 継続的探索を行う0-1PSOによるCSD係数FIRフィルタ設計 ○檀原 嵩博,北原 清貴,陶山 健仁(東京電機大)
19:00- 懇親会


11月21日(土) 9:00-15:00
発表番号時間題目著者(○は発表者)など
AL 09:00-09:25 One-line hack of Knuth's algorithm for minimal hitting set computation with ZDDs ○Takeo Imai(Univ. of Tokyo)
AL 09:25-09:50 複数のエージェントによるオンライン木探索アルゴリズム ○八神 貴裕(九大),山内 由紀子(九大),来嶋 秀治(九大),山下 雅史(九大)
AL 09:50-10:15 Formation problems for synchronous mobile robots in the three dimensional Euclidean space ○Yukiko Yamauchi(Kyushu Univ.),Taichi Uehara(Kyushu Univ.),Masafumi Yamashita(Kyushu Univ.)
10:15-10:25  休憩(10分)
CAS 10:25-10:50 人工学級シミュレーションを用いたスケープゴート現象に関する研究 ○山本 幸樹,前田 義信(新潟大),松本 慎平,加藤 浩介,山岸 秀一(広島工大)
CAS 10:50-11:15 ハードウェア神経回路モデルを用いた輝度差変化がシュブルール錯視にもたらす影響の検討 ○齋藤 元喜,前田 義信(新潟大),秋田 純一(金沢大),塚田 章(富山高専)
CAS 11:15-11:40 負数演算機能を備えたビットシリアル積和演算器 ○岡本 大地(岡山県立大),近藤 真史(川崎医療福祉大),瀬島 吉裕,佐藤 洋一郎,横川 智教,有本 和民(岡山県立大)
11:40-13:00  昼休み(80分)
AL 13:00-14:00 [招待講演] 分散(計算)論 ○山下 雅史(九大)
14:00-14:10  休憩(10分)
MSS 14:10-14:35 類似度の階層関係を用いた類似検索の高速化とその応用 ○劉 健全,西村 祥治,荒木 拓也,中村 祐一(NEC)
MSS 14:35-15:00 静的マルチカーエレベータ運行計画問題のためのトリップに基づく整数線形計画モデルに関する一検討 ○稲元 勉,樋上 喜信(愛媛大)

今回は,一般発表25分(発表20分+質疑5分),ショートトーク20分(発表15分+質問5分)で行います.
(本研究会は無査読で実施しています)

[招待講演]

題目: 分散(計算)論
講演者: 山下 雅史(九州大学)

概要: 生体分子の機能発現, 分散ロボットの相互位置制御, LANの資源管理, 人間社会の選挙など, 広範な領域の問題から領域固有の事由を捨象し, 内在する分散計算構造に着目すると, 合意形成問題が共通して出現する. この事実に着目し, 巨大分散システムを分散計算能力の観点から統一的に理解すること, すなわち, 異なるモデル(仮定)の下で構築される分散計算理論の間の関係を統一的に 理解することが分散論の目的である. 本講演では, (分子のように)記憶や識別子を 持たない構成要素から構成され, (自然界のような)不安定なゆらぎの下で働く (生物のような)分散システムに自律性が豊富に見出されるにも係わらず, はるかに有利な条件の下で設計される人工分散システムへの自律性の付与が 困難である理由を検討する.

結果を大胆にまとめる. (1)決定的かつ匿名(識別子がない)な分散システムの自己組織化能力に 記憶と同期は寄与しない. かえって, (2)匿名性と無記憶性には自己安定性をシステムに付加する というメリットがある. また, (3)決定的かつ匿名なシステムが持てない万能性はアルゴリズムの ランダム化によって獲得できる. 以上から, (3)のアルゴリズムのランダム化が環境のゆらぎと同じ効果を システムに与えるという仮説の下ではあるが, 自然分散システムの弱点である, 匿名性, 無記憶性, 非同期性(ゆらぎ)が その高い自己組織化能力の源泉であることが理解できる.