ワークショップ「離散アルゴリズムの最先端」

「離散アルゴリズムの最先端」というワークショップを東工大でやるので，ぜひお越しください．

ワークショップ「離散アルゴリズムの最先端」
日時：2月23日 (月) 13:30〜17:30

開催地：東京工業大学 大岡山キャンパス 西8号館W棟10階W1008号室

プログラム
13:30〜14:15 講演1 玉置 卓 氏 (京都大学) Hajos Calculusの計算複雑さ
14:30〜15:15 講演2 清見 礼 氏 (北陸先端科学技術大学院大学) 1次元折り紙の難しさ
15:30〜16:15 講演3 定兼 邦彦 氏 (九州大学) レベル祖先と区間最小値問題
16:30〜17:15 講演4 全 眞嬉 氏 (東北大学) デジタル線分とその応用

終了後に懇親会を予定しています．

講演者

玉置 卓 氏 (京都大学大学院情報学研究科通信情報システム専攻)

講演題目： Hajos Calculusの計算複雑さ
講演要旨： Hajos Calculus (以下HC) はルールに基づいてk彩色不能なグラフを生成する系である. HCは任意のk彩色不能なグラフを生成可能であり, 生成される全てのグラフはk彩色不能である. HCによるグラフの生成はk彩色不能性のNP証明とみなすことができる. 本講演ではHCと証明の複雑さの理論との関係について述べる.

清見 礼 氏 (北陸先端科学技術大学院大学情報科学研究科)

講演題目： 1次元折り紙の難しさ
講演要旨： 本講演では細長い紙を用いた折り紙(1次元折り紙)について述べる. 1次元折り紙の実現可能性は多項式時間で判定可能なことが知られている. 我々は1次元上で等間隔に折り目をつける問題の難しさについて考える. とくに折り目が "山谷山谷..." と交互につくようにするのにどのくらいの回数だけ紙を折ればいいか, という問題を中心に考えていく.

定兼 邦彦 氏 (九州大学大学院システム情報科学研究院情報工学部門)

講演題目：　レベル祖先と区間最小値問題
講演要旨：　文字列検索，領域探索，根付木の操作等の問題のいくつかはレベル祖先 (木の節点の祖先で指定された深さのもの) 問題と区間最小値 (1次元配列の部分区間の最小値) 問題と関連がある．これらの関連と効率的データ構造について解説する．

全 眞嬉 氏 (東北大学大学院情報科学研究科システム情報科学専攻)

講演題目： デジタル線分とその応用
講演要旨： $d$-次元グリッド上の中心点$o$から各グリッド点$p$へ向かうデジタル直線$\dig(op)$の集合の数学的に整合的な定義を与える．各デジタル直線は$\dig(op)$は点$o$と点$p$の間のユークリッド線分$\seg{op}$を近似し、すべてのデジタル直線の集合がユークリッド公理に類似した公理系を満たす． デジタル直線と対応するユークリッド線分の間の近似誤差は最大ハウスドルフ距離で評価し、$n\times n$グリッド平面内での誤差に対し、漸近的に最適な$\Theta(\log n)$の誤差限界を与える．
誤差限界の証明はディスクレパンシー理論とシンプルな構築アルゴリズムに基づいている．さらに、デジタル直線の単調性がなければ、誤差限界は$O(1)$に抑えられることを示す．