2022年度

• 野崎 雄太 (広島大学, C01班) が，電子情報通信学会コンピュテーション研究会にて招待講演を行います．

   

  2023年3月2日 (木) 13:30-14:30

  野崎 雄太 「組合せ遷移におけるトポロジーの視点」

   

  参加お申込み等の詳細は，研究会のWebサイトをご覧ください．

  電子情報通信学会コンピュテーション研究会

  2023.03.02 Thu.

  電子情報通信学会コンピュテーション研究会にて招待講演
  話者： 題目： 概要：
• 科研費・学術変革領域研究(B)「組合せ遷移の展開に向けた計算機科学・工学・数学によるアプローチの融合」では，下記の通り，2022年度「組合せ遷移」の学生シンポジウム及び最終報告会を開催致します．全て一般公開しておりますので，ご参加頂ければ幸いです（参加申込が必要です．後述の詳細をご覧ください）

  開催概要（印刷用）

   

  • 会場

  東北大学 大学院情報科学研究科棟 ２階大講義室

  (〒980-8579 仙台市青葉区荒巻字青葉6-3-09)

  アクセス情報

  ＊ 対面を主としますが，一部オンライン中継も致します

   

  • プログラム概要

  2月20日(月)	2022年度「組合せ遷移」の学生シンポジウム
  10:00～10:30 10:30～12:00 13:20～14:50 15:10～16:40	オープニング セッション１（発表3件） セッション２（発表3件） セッション３（発表3件）
  	（プログラム詳細と発表概要はこちら）
  2月21日(火)	学術変革領域研究(B)「組合せ遷移」最終報告会
  9:30～  9:50	本研究領域の目的と計画
  9:50～10:40	A-1. 計画研究A01班の報告（伊藤 健洋） A-2. アルゴリズム基盤：組合せ遷移のアルゴリズム的メタ定理（大舘 陽太） A-3. アルゴリズム基盤の隣接分野への展開 A-3.1. 組合せ遷移と列挙（和佐 州洋） A-3.2. 組合せ遷移と分散計算（山内 由紀子）
  11:00～11:50	B-1. 計画研究B01班の報告（川原 純） B-2. 実装技術基盤：組合せ遷移ソルバーとその技術 B-2.1. GUI 実演（川原 純） B-2.2. ZDDベースソルバー（川原 純） B-2.3. BMCベースソルバー（戸田 貴久） B-2.4. SATベースソルバー（宋 剛秀） B-3. 実装技術基盤の配電制御への展開 （飯岡 大輔，鈴木 顕）
  13:10～14:00	C-1. 計画研究C01班の報告（岡本 吉央） C-2. 数学基盤：組合せ遷移の研究に資する数理手法 C-2.1. 組合せ遷移と離散構造（小林 佑輔） C-2.2. 組合せ遷移と不変量（岩政 勇仁） C-2.3. 組合せ遷移とトポロジー（野崎 雄太） C-3. 数学基盤のアルゴリズム的ゲーム理論への展開（神山 直之）
  14:20～15:20 15:20～15:30	領域全体の報告，外部評価者による講評 集合写真撮影（現地）

   

  • 参加申込

  下記からお願い致します．ご欠席でも，ニュースレター等のために，ご回答頂ければ助かります．なお，オンライン参加URLは，お申込み頂いた方へ 2/17(金)午後 にメール致します．
  https://forms.gle/75XG6xZFbDKJreez5

   

  申込締切
  【対面を含むご参加の場合】2023年2月6日(月) 正午まで． 2023年2月17日(金) 正午まで．

  （両日とも若干名の余裕がございますので，対面参加の申込締切を延長しました）

   

  【オンラインのみのご参加・ご欠席の場合】2023年2月17日(金) 正午まで．

  
   

  参加費

  無料

   

  2023.02.20 Mon. - 21 Tue.

  2022年度「組合せ遷移」の学生シンポジウム＋最終報告会
  話者： 題目： 概要：
• 現実社会に現れる多くの問題が組合せ最適化問題として定式化できる．そのような問題はNP困難であることが多く，規模の大きい問題例を厳密に解くことは困難である．そこで，実践的な解決策として，最適性の保証はなくとも，良い解を速く求めようとする手法が研究されている．代表的なものとして，欲張り法や局所探索法などの基本戦略があり，また，それらを高度に組み合わせるなどの方法によってより良い解を得ようとするメタ戦略がある．本講演では，そのような手法に基づいて効率的なアルゴリズムを構築するために行ってきた研究について紹介する．

  2023.02.06 Mon. 10:00-12:00

  第35回セミナー・勉強会
  話者：柳浦 睦憲（名古屋大学，招待講演） 題目：組合せ最適化問題に対する実践的解法 概要：
• あみだくじは，1 から n を表す n 本の縦線と，縦線 2 本の間を結ぶ横棒からなる．横棒を，その横棒が結ぶ２本の縦線のラベルを交換する互換とみなすことで，あみだくじ (つまり横棒と縦線からなるネットワーク) は置換を表すことになる．横棒を比較器とみてソーティングネットワーク (sorting network) として研究されることも多く，特に，隣り合う縦線 2 本の間の互換のみに横棒を制限した場合には primitive sorting network と呼ばれる．菱形タイリングは，辺の長さが同じ菱形を，隙間なく重なりなく敷き詰めたものである．本講演では，あみだくじと菱形タイリングの関係について説明し，逆探索や ZDD (Zero-Suppressed Binary Decision Diagrams; 零抑制型二分決定グラフ) による列挙や，その後の広がりについて述べる．

  2023.01.16 Mon. 10:00-12:00

  第34回セミナー・勉強会
  話者：堀山 貴史（北海道大学，招待講演） 題目：あみだくじと菱形タイリングの列挙 概要：
• 2022.12.12 Mon.

  Workshop "Combinatorial Reconfiguration and Fixed-Parameter Tractability"
  話者： 題目： 概要：
• 発表者が学生時代から十数年来取り組んでいる分散計算理論がどのような分野であるのか，最近の研究事例2つを通してご紹介いたします．具体的には，
   (i) 個体群モデルにおけるリーダ選挙問題，および，
   (ii) モバイルエージェントによるビザンチン集合問題
  について，問題設定やこれまでに発見されたいくつかのアルゴリズムをご解説いたします．

   

  個体群モデルとは，消極移動（自分で制御できない移動）を絶えず行う微小で計算資源に乏しい計算機で構成するネットワークを表現する分散計算のモデルです．このモデルは2004年にAngluinらによって提案されて以来，盛んに研究が行われてきました．とりわけ，リーダ選挙問題と多数決問題のふたつは大変良く研究されている問題で，前者については，2020年にBerenbrinkらによってついに時間最適かつ空間最適なアルゴリズムが発見されました．本講演では，このリーダ選挙問題について解説します．

   

  モバイルエージェントとは，計算機ネットワーク上を自律的に移動するソフトウェアのことです．ネットワーク上に存在するすべてのエージェントをひとつの計算機に集める集合問題は基本的かつ重要な問題で，分散計算理論のコミュニティでは大変よく研究されています．本講演では，ネットワーク上の一部のエージェントが任意の敵対的な行動を取る場合にも正常なエージェントをひとつの計算機に集合させることを目的としたビザンチン集合問題を紹介します．
   

  2022.12.05 Mon. 10:00-12:00

  第33回セミナー・勉強会
  話者：首藤 裕一（法政大学，招待講演） 題目：分散計算理論の世界 概要：
• 電力・エネルギー分野において，私は再生可能エネルギー電源の主力電源化を目指し，安全性と安定供給・経済性・環境保全を確保することを大前提として，最大限導入するための仕組みについて研究している．再生可能エネルギー電源を増加させることの課題の一つは，電力システムから供給される電力の品質劣化であり，社会生活に悪影響を及ぼす可能性がある．本講演では，再生可能エネルギー電源に起因する電力品質劣化のメカニズムと対策について述べ，再生可能エネルギー電源の導入可能量を拡大するための研究について紹介する．

  2022.11.28 Mon. 10:00-12:00

  第32回セミナー・勉強会
  話者：飯岡 大輔（中部大学，B01班） 題目：再生可能エネルギーを主体とする電力システムの構築 概要：
• 離散時間論理型有限力学系モデル（DT-BFDS）は、力学系モデル（dynamical systems）に離散時間で動作する、頂点が一定でその状態が論理値であるという制限を加えて、単純化したものである。DT-BFDSは離散時間で変化する社会現象、あるいはタンパク質間や遺伝子間の相互作用ネットワークのシミュレーションの道具として使われており、また、DT-BFDSの性質に関する問題が計算量理論を用いて研究されている。DT-BFDSは従来決定性のモデルであり、非決定的な動きをするモデルの体系はまだ確立されていない。確率的なモデルを使用したDT-BFDSモデルが幾つか提案されているが、そこに於ける確率的選択の使用は、初期値の生成など、動作の一部に限られている。

   

  本研究の目的は、このDT-BFDSに不確定要素を導入する方法を提案し、それによって生じるモデルの計算力を調べる事である。ここでは二つの独立した方式を不確定性の導入方を提案する。その一つは、状態の更新に使われる関数に、頂点毎に選択肢を与える事であり、もう一つは、頂点が各時刻において順々に状態の更新を行うと仮定し、その順序に選択肢を与える事である。この二つの方式をそれぞれ何種類かに分け、それらを組み合わせる事により、多岐のモデルが定義できる。本講演では、この試みの初期の結果を発表する。まず、モデルの多項式時間埋め込み可能性の概念を定義し、このようなモデルの相互関係を立証する。さらには、いくつかのモデルの計算能力を到達可能性問題の計算量理論的分析により、明らかにする。

  2022.11.14 Mon. 10:00-12:00

  第31回セミナー・勉強会
  話者：荻原 光徳（マイアミ大学，招待講演） 題目：離散時間論理型有限力学系の不確定性モデル 概要：
• 学変(A)「社会変革の源泉となる革新的アルゴリズム基盤の創出と体系化」（領域代表 湊真一 教授）の2022年度第2回領域集会において，伊藤 健洋 (東北大学，領域代表) が招待講演を行います．

  詳しくは，Webサイトをご覧ください．

  2022.11.07 Mon.

  学変(A)「アルゴリズム基盤」にて招待講演
  話者： 題目： 概要：
• k彩色遷移問題とは，無向グラフとその２つのk頂点彩色が与えられた際に，片方の彩色からもう片方の彩色へ，k頂点彩色であることを保ったまま，一度に一つの頂点の色を変えながら遷移することが可能であるか否かを判定する問題である．本講演では，ある色からある色へは直接変えることが出来ないという遷移可能性制約を考える．この制約は色を頂点とし，直接変えることのできる色の順序対を辺とする有向グラフにより与えることができる．本講演では，この有向グラフが有向サイクルであるかマルチツリーのある部分クラスに含まれる場合に，k彩色遷移問題が線形時間で解けることを示す．本講演は，藤井宗一郎氏，岩政勇仁氏，鈴木顕氏との共同研究に基づく．

  2022.10.31 Mon. 10:00-12:00

  第30回セミナー・勉強会
  話者：木村 慧（九州大学，招待講演） 題目：遷移可能性制約をもつ彩色遷移問題 概要：