A01

• 分散システムとは，相互に通信しながら協調して動作する多数の計算主体が作りだすシステムである．個々の計算主体はシステム全体の状況を把握できず，局所的，非同期的，並列的に計算や通信を行う．本講演の前半では，分散システムの通信グラフ上に構成した離散構造の遷移問題を紹介する．近年，独立点集合 [ICALP2019]，頂点彩色 [DISC2018]，全域木 [SSS2021]の分散遷移問題が異なる設定の下で提案されており，これらの結果を紹介する．講演の後半では，モバイルロボットやエージェントなどの自律的に計算，移動を行うモバイル計算主体群が構成する分散システムの遷移問題を紹介する．このような分散システムでは，計算主体の幾何的な配置に着目し，パターン形成問題や再構成問題という名前で遷移可能性が議論されてきた．講演者は近年，遷移列の繰返しや組合せによって探索や脱出といった機能を実現する研究に取り組んでいる．講演後半ではモバイルロボット群のパターン形成問題，モジュールロボットの探索と脱出を紹介する．

  2022.05.16 Mon. 15:00-17:00

  第24回セミナー・勉強会
  話者：山内 由紀子（九州大学，A01班） 題目：分散計算と遷移問題 概要：
• 和佐 州洋 (豊橋技術科学大学，A01班) が，人工知能学会 第119回人工知能基本問題研究会 (SIG-FPAI) にて招待講演を行います．

   

  2022年1月28日 (金) 11:00 - 12:00
  和佐 州洋 (豊橋科学技術大学, A01班）「難しい列挙問題に対するアプローチ」

   

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

  第119回人工知能基本問題研究会

   

  2022.01.28 Fri.

  第119回人工知能基本問題研究会にて招待講演
  話者： 題目： 概要：
• 現実世界の問題を解決する一般的手法のひとつとして，問題を数理的にモデリングし，そのモデルに対して最適化アルゴリズムを適用するという方法がある．このような文脈においては，最適化アルゴリズムはひとつの (近似) 最適解を求めることが一般的である．しかしながら，このような数理的モデルは現実世界を正確には反映できておらず，モデルの上でひとつの最適解を得ても，現実世界の問題の解決につながるとは限らない．（近似）最適解を複数求めて，その中から実問題に適するものを選ぶことが考えられるが，一般にそのような解は類似していることが多く，このような目的にはあまり意味をなさない．このような現実世界の問題と数理モデルとの間のギャップを解消するために，複数の「多様な」解を求める研究が行われている．本講演では，組合せ最適化問題における「多様な解」を発見するための最近の取り組みについて紹介する．

  2022.01.20 Thu. 10:00-12:00

  第21回セミナー・勉強会
  話者：小林 靖明（京都大学，A01班） 題目：組合せ最適化問題に対する多様な最適解の計算について 概要：
• A01班の 小林 靖明（京都大学）と 大舘 陽太（名古屋大学）が，第33回RAMP数理最適化シンポジウム (RAMP 2021) にて講演します．

   

  小林 靖明（京都大学, A01班）「疎グラフに対するアルゴリズム的メタ定理」

  大舘 陽太（名古屋大学, A01班）「グラフの幅パラメータを用いたアルゴリズム設計について」

   

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

  第33回RAMP数理最適化シンポジウム (RAMP 2021)

   

  2021.11.18 Thu. - 19 Fri.

  第33回RAMP数理最適化シンポジウム (RAMP 2021) にて講演
  話者： 題目： 概要：
• 講演者は，グラフ最適化問題についての計算複雑性について研究を行っている．グラフ最適化問題の中で，特徴Pをもつ最大誘導部分グラフ探索問題 (Maximum Induced Subgraph with Property P) がある．例えば，特徴が独立集合であるとき，この問題は最大独立頂点集合問題としてみることができる．グラフGが特徴Pを持ち，グラフGにおいてどの誘導部分グラフも特徴Pを持つとき，その特徴Pは遺伝性があるという．この最大誘導部分グラフ探索問題は，特徴Pが遺伝性を持つとき，一般グラフにおいて近似困難であることが知られている．本講演では，遺伝性を持たない正則性などを特徴とした最大誘導部分グラフ探索問題に対して，入力グラフの構造を制限したときの計算複雑性について紹介する．

  2021.10.07 Thu. 10:00-12:00

  第15回セミナー・勉強会
  話者：江藤 宏（東北大学，A01班） 題目：最大誘導部分グラフ探索問題の計算困難性について 概要：
• 組合せ遷移の隣接分野の一つとして列挙問題が挙げられる．列挙問題とは，与えられた条件を満たす解を漏れなく重複なく出力する問題であり，理論計算機科学では基礎的な分野である．列挙問題を解くためのアルゴリズムを構成するためのいくつかのフレームワークがこれまで提案されてきたが，その一つとして超グラフ技法と呼ばれるものがある．超グラフ技法で構成されたアルゴリズムは，解を頂点とする解グラフ上を探索することで解を列挙するものであり，組合せ遷移とつながりが予想される．本講演では，超グラフ技法を用いた列挙アルゴリズムの構成方法について，その概要を紹介する．

  2021.05.10 Mon. 10:00-12:00

  第09回セミナー・勉強会
  話者：和佐 州洋（豊橋技術科学大学，A01班） 題目：解グラフに着目した列挙アルゴリズムの構成 概要：
• 主にグラフクラスと幅パラメータの視点から，独立集合遷移問題についての既存結果や未解決問題を紹介します．

  2020.12.18 Fri. 14:00-16:00

  第03回セミナー・勉強会
  話者：大舘 陽太（名古屋大学，A01班） 題目：独立集合の遷移について 概要：
• 組合せ遷移のアルゴリズムの手法について，代表的なところをいくつかご紹介します．前回の勉強会に参加していなくても構いません．

  2020.12.11 Fri. 15:00-17:00

  第02回セミナー・勉強会
  話者：伊藤 健洋（東北大学，A01班） 題目：組合せ遷移のアルゴリズム －アルゴリズム手法－ 概要：
• アルゴリズム理論の観点から見た「組合せ遷移」について，まずはフレームワーク (問題設定) について説明します．その後，今回は，計算困難性の証明について，いくつかご紹介します．

  2020.11.20 Fri. 15:00-17:00

  第01回セミナー・勉強会
  話者：伊藤 健洋（東北大学，A01班） 題目：組合せ遷移のアルゴリズム －計算困難性の証明－ 概要：