【研究テーマ】情報学基礎

【研究種目】基盤研究(A)

【研究期間】2011-04-01 - 2015-03-31

【研究代表者】今井 浩 東京大学, 情報理工学(系)研究科, 教授 (80183010)

【キーワード】量子計算理論 / 量子グラフ理論 / 量子コンピュータ / 計算量理論 / グラフマイナー理論 (他11件)

【概要】量子計算能力の限界解明を目指して、研究分担者・連携研究者らにより多角的に研究を進め、次のような成果をあげた。 (1) 測定ベース量子計算等の量子計算モデルの離散・物理構造に着目し、量子回路最適化や状態変換可能性・測定の汎用実装法・周期グラフ状態の万能計算性について成果を得た。(2) グラフの点マイナー理論を適用して、量子情報の観点からイジング分配関数の効率的計算法を考察し、量子グラフ彩色について量...

【研究テーマ】情報学基礎

【研究種目】基盤研究(A)

【研究期間】2011-04-01 - 2015-03-31

【研究代表者】今井 浩 東京大学, 情報理工学(系)研究科, 教授 (80183010)

【キーワード】量子計算理論 / 量子グラフ理論 / 量子コンピュータ / 計算量理論 / グラフマイナー理論 (他11件)

【概要】量子計算能力の限界解明を目指して、研究分担者・連携研究者らにより多角的に研究を進め、次のような成果をあげた。 (1) 測定ベース量子計算等の量子計算モデルの離散・物理構造に着目し、量子回路最適化や状態変換可能性・測定の汎用実装法・周期グラフ状態の万能計算性について成果を得た。(2) グラフの点マイナー理論を適用して、量子情報の観点からイジング分配関数の効率的計算法を考察し、量子グラフ彩色について量...

【研究テーマ】情報学基礎

【研究種目】基盤研究(A)

【研究期間】2011-04-01 - 2015-03-31

【研究代表者】今井 浩 東京大学, 情報理工学(系)研究科, 教授 (80183010)

【キーワード】量子計算理論 / 量子グラフ理論 / 量子コンピュータ / 計算量理論 / グラフマイナー理論 (他11件)

【概要】量子計算能力の限界解明を目指して、研究分担者・連携研究者らにより多角的に研究を進め、次のような成果をあげた。 (1) 測定ベース量子計算等の量子計算モデルの離散・物理構造に着目し、量子回路最適化や状態変換可能性・測定の汎用実装法・周期グラフ状態の万能計算性について成果を得た。(2) グラフの点マイナー理論を適用して、量子情報の観点からイジング分配関数の効率的計算法を考察し、量子グラフ彩色について量...

【研究テーマ】情報学基礎

【研究種目】基盤研究(A)

【研究期間】2011-04-01 - 2015-03-31

【研究代表者】今井 浩 東京大学, 情報理工学(系)研究科, 教授 (80183010)

【キーワード】量子計算理論 / 量子グラフ理論 / 量子コンピュータ / 計算量理論 / グラフマイナー理論 (他11件)

【概要】量子計算能力の限界解明を目指して、研究分担者・連携研究者らにより多角的に研究を進め、次のような成果をあげた。 (1) 測定ベース量子計算等の量子計算モデルの離散・物理構造に着目し、量子回路最適化や状態変換可能性・測定の汎用実装法・周期グラフ状態の万能計算性について成果を得た。(2) グラフの点マイナー理論を適用して、量子情報の観点からイジング分配関数の効率的計算法を考察し、量子グラフ彩色について量...

【研究テーマ】情報学基礎

【研究種目】基盤研究(A)

【研究期間】2011-04-01 - 2015-03-31

【研究代表者】今井 浩 東京大学, 情報理工学(系)研究科, 教授 (80183010)

【キーワード】量子計算理論 / 量子グラフ理論 / 量子コンピュータ / 計算量理論 / グラフマイナー理論 (他11件)

【概要】量子計算能力の限界解明を目指して、研究分担者・連携研究者らにより多角的に研究を進め、次のような成果をあげた。 (1) 測定ベース量子計算等の量子計算モデルの離散・物理構造に着目し、量子回路最適化や状態変換可能性・測定の汎用実装法・周期グラフ状態の万能計算性について成果を得た。(2) グラフの点マイナー理論を適用して、量子情報の観点からイジング分配関数の効率的計算法を考察し、量子グラフ彩色について量...

【研究テーマ】情報学基礎

【研究種目】基盤研究(A)

【研究期間】2011-04-01 - 2015-03-31

【研究代表者】今井 浩 東京大学, 情報理工学(系)研究科, 教授 (80183010)

【キーワード】量子計算理論 / 量子グラフ理論 / 量子コンピュータ / 計算量理論 / グラフマイナー理論 (他11件)

【概要】量子計算能力の限界解明を目指して、研究分担者・連携研究者らにより多角的に研究を進め、次のような成果をあげた。 (1) 測定ベース量子計算等の量子計算モデルの離散・物理構造に着目し、量子回路最適化や状態変換可能性・測定の汎用実装法・周期グラフ状態の万能計算性について成果を得た。(2) グラフの点マイナー理論を適用して、量子情報の観点からイジング分配関数の効率的計算法を考察し、量子グラフ彩色について量...

【研究テーマ】情報学基礎

【研究種目】基盤研究(A)

【研究期間】2011-04-01 - 2015-03-31

【研究代表者】今井 浩 東京大学, 情報理工学(系)研究科, 教授 (80183010)

【キーワード】量子計算理論 / 量子グラフ理論 / 量子コンピュータ / 計算量理論 / グラフマイナー理論 (他11件)

【概要】量子計算能力の限界解明を目指して、研究分担者・連携研究者らにより多角的に研究を進め、次のような成果をあげた。 (1) 測定ベース量子計算等の量子計算モデルの離散・物理構造に着目し、量子回路最適化や状態変換可能性・測定の汎用実装法・周期グラフ状態の万能計算性について成果を得た。(2) グラフの点マイナー理論を適用して、量子情報の観点からイジング分配関数の効率的計算法を考察し、量子グラフ彩色について量...

【研究テーマ】社会システム工学

【研究種目】一般研究(C)

【研究期間】1991 - 1993

【研究代表者】平澤 茂一 早稲田大学, 理工学部, 教授 (30147946)

【キーワード】知識情報処理 / 情報理論 / 経営工学 / 推論 / 学習 (他15件)

【概要】近年,曖昧性や矛盾を含んだ知識の推論や学習等の,より人間的で複雑な判断をめざした新しい知識情報処理の基礎研究も様々な分野で盛んに行われている.しかしながら従来の論理学を中心としたエキスパートシステムに比べて基礎理論が不完全であり評価基準も不明確であるため得られる結果が理論的に明快に保証されずシステム化が進んでいないのが現状である.本研究ではこれら新しい知識情報処理のために今までの個別的な研究ではな...

【研究テーマ】

【研究種目】挑戦的研究(萌芽)

【研究期間】2018-06-29 - 2022-03-31

【研究代表者】今井 浩 東京大学, 大学院情報理工学系研究科, 教授 (80183010)

【キーワード】量子計算 / 量子優越性 / グラウ最適化 / グラフ不変量 / 計算量理論 (他19件)

【概要】グラフのIsing分配関数の計算に対して、グラフ構造の複雑さを表すパラメタの中で枝幅・ランク幅に着目し、そのパラメタを用いた計算量で効率的なものを構成した。特に、パラメタが定数で抑えられるなどの場合に有効である。Ising分配関数からPotts分配関数、そして2変数グラフ不変多項式のTutte多項式へと展開し、有効閉路なしグラフ枝向き付け数に関する成果も得た。Tutte多項式の単峰性が満たされない...

【研究テーマ】

【研究種目】挑戦的研究(萌芽)

【研究期間】2018-06-29 - 2022-03-31

【研究代表者】今井 浩 東京大学, 大学院情報理工学系研究科, 教授 (80183010)

【キーワード】量子計算 / 量子優越性 / グラウ最適化 / グラフ不変量 / 計算量理論 (他19件)

【概要】グラフのIsing分配関数の計算に対して、グラフ構造の複雑さを表すパラメタの中で枝幅・ランク幅に着目し、そのパラメタを用いた計算量で効率的なものを構成した。特に、パラメタが定数で抑えられるなどの場合に有効である。Ising分配関数からPotts分配関数、そして2変数グラフ不変多項式のTutte多項式へと展開し、有効閉路なしグラフ枝向き付け数に関する成果も得た。Tutte多項式の単峰性が満たされない...

【研究テーマ】情報学基礎

【研究種目】基盤研究(C)

【研究期間】2003

【研究代表者】岩間 一雄 京都大学, 情報学研究科, 教授 (50131272)

【キーワード】離散アルゴリズム / 離散最適化 / 品質保証 / 近似アルゴリズム / オンラインアルゴリズム (他8件)

【概要】最近のIT社会の大規模化と多様化に伴って、従来から常識のように言われていた正確な計算を速く実行するというパラダイムが必ずしも実情に合わなくなってきている。現実的な時間内に限られたメモリ量で問題を解決することは依然として重要であるが、それだけではなく、非確実性をいかに扱うかが主要な課題になっている。したがって、正確さや決定性を犠牲にしても高速に近似最適解を得る、スケーラビリティを重視した情報処理技術...

【研究テーマ】

【研究種目】挑戦的研究(萌芽)

【研究期間】2018-06-29 - 2022-03-31

【研究代表者】今井 浩 東京大学, 大学院情報理工学系研究科, 教授 (80183010)

【キーワード】量子計算 / 量子優越性 / グラウ最適化 / グラフ不変量 / 計算量理論 (他19件)

【概要】グラフのIsing分配関数の計算に対して、グラフ構造の複雑さを表すパラメタの中で枝幅・ランク幅に着目し、そのパラメタを用いた計算量で効率的なものを構成した。特に、パラメタが定数で抑えられるなどの場合に有効である。Ising分配関数からPotts分配関数、そして2変数グラフ不変多項式のTutte多項式へと展開し、有効閉路なしグラフ枝向き付け数に関する成果も得た。Tutte多項式の単峰性が満たされない...

【研究テーマ】

【研究種目】挑戦的研究(萌芽)

【研究期間】2018-06-29 - 2022-03-31

【研究代表者】今井 浩 東京大学, 大学院情報理工学系研究科, 教授 (80183010)

【キーワード】量子計算 / 量子優越性 / グラウ最適化 / グラフ不変量 / 計算量理論 (他19件)

【概要】グラフのIsing分配関数の計算に対して、グラフ構造の複雑さを表すパラメタの中で枝幅・ランク幅に着目し、そのパラメタを用いた計算量で効率的なものを構成した。特に、パラメタが定数で抑えられるなどの場合に有効である。Ising分配関数からPotts分配関数、そして2変数グラフ不変多項式のTutte多項式へと展開し、有効閉路なしグラフ枝向き付け数に関する成果も得た。Tutte多項式の単峰性が満たされない...

【研究テーマ】

【研究種目】挑戦的研究(萌芽)

【研究期間】2018-06-29 - 2022-03-31

【研究代表者】今井 浩 東京大学, 大学院情報理工学系研究科, 教授 (80183010)

【キーワード】量子計算 / 量子優越性 / グラウ最適化 / グラフ不変量 / 計算量理論 (他19件)

【概要】グラフのIsing分配関数の計算に対して、グラフ構造の複雑さを表すパラメタの中で枝幅・ランク幅に着目し、そのパラメタを用いた計算量で効率的なものを構成した。特に、パラメタが定数で抑えられるなどの場合に有効である。Ising分配関数からPotts分配関数、そして2変数グラフ不変多項式のTutte多項式へと展開し、有効閉路なしグラフ枝向き付け数に関する成果も得た。Tutte多項式の単峰性が満たされない...

【研究テーマ】

【研究種目】挑戦的研究(萌芽)

【研究期間】2018-06-29 - 2022-03-31

【研究代表者】今井 浩 東京大学, 大学院情報理工学系研究科, 教授 (80183010)

【キーワード】量子計算 / 量子優越性 / グラウ最適化 / グラフ不変量 / 計算量理論 (他19件)

【概要】グラフのIsing分配関数の計算に対して、グラフ構造の複雑さを表すパラメタの中で枝幅・ランク幅に着目し、そのパラメタを用いた計算量で効率的なものを構成した。特に、パラメタが定数で抑えられるなどの場合に有効である。Ising分配関数からPotts分配関数、そして2変数グラフ不変多項式のTutte多項式へと展開し、有効閉路なしグラフ枝向き付け数に関する成果も得た。Tutte多項式の単峰性が満たされない...

【研究テーマ】

【研究種目】挑戦的研究(萌芽)

【研究期間】2018-06-29 - 2022-03-31

【研究代表者】今井 浩 東京大学, 大学院情報理工学系研究科, 教授 (80183010)

【キーワード】量子計算 / 量子優越性 / グラウ最適化 / グラフ不変量 / 計算量理論 (他19件)

【概要】グラフのIsing分配関数の計算に対して、グラフ構造の複雑さを表すパラメタの中で枝幅・ランク幅に着目し、そのパラメタを用いた計算量で効率的なものを構成した。特に、パラメタが定数で抑えられるなどの場合に有効である。Ising分配関数からPotts分配関数、そして2変数グラフ不変多項式のTutte多項式へと展開し、有効閉路なしグラフ枝向き付け数に関する成果も得た。Tutte多項式の単峰性が満たされない...

【研究テーマ】

【研究種目】挑戦的研究(萌芽)

【研究期間】2018-06-29 - 2022-03-31

【研究代表者】今井 浩 東京大学, 大学院情報理工学系研究科, 教授 (80183010)

【キーワード】量子計算 / 量子優越性 / グラウ最適化 / グラフ不変量 / 計算量理論 (他19件)

【概要】グラフのIsing分配関数の計算に対して、グラフ構造の複雑さを表すパラメタの中で枝幅・ランク幅に着目し、そのパラメタを用いた計算量で効率的なものを構成した。特に、パラメタが定数で抑えられるなどの場合に有効である。Ising分配関数からPotts分配関数、そして2変数グラフ不変多項式のTutte多項式へと展開し、有効閉路なしグラフ枝向き付け数に関する成果も得た。Tutte多項式の単峰性が満たされない...

【研究テーマ】

【研究種目】挑戦的研究(萌芽)

【研究期間】2018-06-29 - 2022-03-31

【研究代表者】今井 浩 東京大学, 大学院情報理工学系研究科, 教授 (80183010)

【キーワード】量子計算 / 量子優越性 / グラウ最適化 / グラフ不変量 / 計算量理論 (他19件)

【概要】グラフのIsing分配関数の計算に対して、グラフ構造の複雑さを表すパラメタの中で枝幅・ランク幅に着目し、そのパラメタを用いた計算量で効率的なものを構成した。特に、パラメタが定数で抑えられるなどの場合に有効である。Ising分配関数からPotts分配関数、そして2変数グラフ不変多項式のTutte多項式へと展開し、有効閉路なしグラフ枝向き付け数に関する成果も得た。Tutte多項式の単峰性が満たされない...

【研究テーマ】

【研究種目】挑戦的研究(萌芽)

【研究期間】2018-06-29 - 2022-03-31

【研究代表者】今井 浩 東京大学, 大学院情報理工学系研究科, 教授 (80183010)

【キーワード】量子計算 / 量子優越性 / グラウ最適化 / グラフ不変量 / 計算量理論 (他19件)

【概要】グラフのIsing分配関数の計算に対して、グラフ構造の複雑さを表すパラメタの中で枝幅・ランク幅に着目し、そのパラメタを用いた計算量で効率的なものを構成した。特に、パラメタが定数で抑えられるなどの場合に有効である。Ising分配関数からPotts分配関数、そして2変数グラフ不変多項式のTutte多項式へと展開し、有効閉路なしグラフ枝向き付け数に関する成果も得た。Tutte多項式の単峰性が満たされない...

【研究テーマ】

【研究種目】挑戦的研究(萌芽)

【研究期間】2018-06-29 - 2022-03-31

【研究代表者】今井 浩 東京大学, 大学院情報理工学系研究科, 教授 (80183010)

【キーワード】量子計算 / 量子優越性 / グラウ最適化 / グラフ不変量 / 計算量理論 (他19件)

【概要】グラフのIsing分配関数の計算に対して、グラフ構造の複雑さを表すパラメタの中で枝幅・ランク幅に着目し、そのパラメタを用いた計算量で効率的なものを構成した。特に、パラメタが定数で抑えられるなどの場合に有効である。Ising分配関数からPotts分配関数、そして2変数グラフ不変多項式のTutte多項式へと展開し、有効閉路なしグラフ枝向き付け数に関する成果も得た。Tutte多項式の単峰性が満たされない...

【研究テーマ】情報学基礎

【研究種目】基盤研究(C)

【研究期間】2003

【研究代表者】岩間 一雄 京都大学, 情報学研究科, 教授 (50131272)

【キーワード】離散アルゴリズム / 離散最適化 / 品質保証 / 近似アルゴリズム / オンラインアルゴリズム (他8件)

【概要】最近のIT社会の大規模化と多様化に伴って、従来から常識のように言われていた正確な計算を速く実行するというパラダイムが必ずしも実情に合わなくなってきている。現実的な時間内に限られたメモリ量で問題を解決することは依然として重要であるが、それだけではなく、非確実性をいかに扱うかが主要な課題になっている。したがって、正確さや決定性を犠牲にしても高速に近似最適解を得る、スケーラビリティを重視した情報処理技術...

【研究テーマ】情報学基礎

【研究種目】基盤研究(C)

【研究期間】2003

【研究代表者】岩間 一雄 京都大学, 情報学研究科, 教授 (50131272)

【キーワード】離散アルゴリズム / 離散最適化 / 品質保証 / 近似アルゴリズム / オンラインアルゴリズム (他8件)

【概要】最近のIT社会の大規模化と多様化に伴って、従来から常識のように言われていた正確な計算を速く実行するというパラダイムが必ずしも実情に合わなくなってきている。現実的な時間内に限られたメモリ量で問題を解決することは依然として重要であるが、それだけではなく、非確実性をいかに扱うかが主要な課題になっている。したがって、正確さや決定性を犠牲にしても高速に近似最適解を得る、スケーラビリティを重視した情報処理技術...

【研究テーマ】数学一般(含確率論・統計数学)

【研究種目】若手研究(B)

【研究期間】2003 - 2005

【研究代表者】小田 芳彰 慶應義塾大学, 理工学部, 講師 (90325043)

【キーワード】応用数学 / 組合せ論 / アルゴリズム / 巡回セールスマン問題 / 計算量理論 (他8件)

【概要】巡回セールスマン問題(以下、TSP)とは与えられた複数の都市をすべて1回ずつ通り、出発点に戻ってくるような最短経路を見つける問題である。この問題はNP困難のクラスに属し、都市数が増えたとき実用的な時間(多項式時間)で最短経路(最適解)を求めるのは不可能と予想される代表例になっている。そこで、実社会での応用の観点から、実用的は時間で最適解に近い解を求める近似解法の研究がさかんに行われてきた。 TSP...

【研究テーマ】

【研究種目】挑戦的研究(萌芽)

【研究期間】2018-06-29 - 2022-03-31

【研究代表者】今井 浩 東京大学, 大学院情報理工学系研究科, 教授 (80183010)

【キーワード】量子計算 / 量子優越性 / グラウ最適化 / グラフ不変量 / 計算量理論 (他19件)

【概要】グラフのIsing分配関数の計算に対して、グラフ構造の複雑さを表すパラメタの中で枝幅・ランク幅に着目し、そのパラメタを用いた計算量で効率的なものを構成した。特に、パラメタが定数で抑えられるなどの場合に有効である。Ising分配関数からPotts分配関数、そして2変数グラフ不変多項式のTutte多項式へと展開し、有効閉路なしグラフ枝向き付け数に関する成果も得た。Tutte多項式の単峰性が満たされない...

【研究テーマ】社会システム工学

【研究種目】一般研究(C)

【研究期間】1991 - 1993

【研究代表者】平澤 茂一 早稲田大学, 理工学部, 教授 (30147946)

【キーワード】知識情報処理 / 情報理論 / 経営工学 / 推論 / 学習 (他15件)

【概要】近年,曖昧性や矛盾を含んだ知識の推論や学習等の,より人間的で複雑な判断をめざした新しい知識情報処理の基礎研究も様々な分野で盛んに行われている.しかしながら従来の論理学を中心としたエキスパートシステムに比べて基礎理論が不完全であり評価基準も不明確であるため得られる結果が理論的に明快に保証されずシステム化が進んでいないのが現状である.本研究ではこれら新しい知識情報処理のために今までの個別的な研究ではな...

【研究テーマ】社会システム工学

【研究種目】一般研究(C)

【研究期間】1991 - 1993

【研究代表者】平澤 茂一 早稲田大学, 理工学部, 教授 (30147946)

【キーワード】知識情報処理 / 情報理論 / 経営工学 / 推論 / 学習 (他15件)

【概要】近年,曖昧性や矛盾を含んだ知識の推論や学習等の,より人間的で複雑な判断をめざした新しい知識情報処理の基礎研究も様々な分野で盛んに行われている.しかしながら従来の論理学を中心としたエキスパートシステムに比べて基礎理論が不完全であり評価基準も不明確であるため得られる結果が理論的に明快に保証されずシステム化が進んでいないのが現状である.本研究ではこれら新しい知識情報処理のために今までの個別的な研究ではな...

【研究テーマ】情報学基礎

【研究種目】基盤研究(C)

【研究期間】2003

【研究代表者】岩間 一雄 京都大学, 情報学研究科, 教授 (50131272)

【キーワード】離散アルゴリズム / 離散最適化 / 品質保証 / 近似アルゴリズム / オンラインアルゴリズム (他8件)

【概要】最近のIT社会の大規模化と多様化に伴って、従来から常識のように言われていた正確な計算を速く実行するというパラダイムが必ずしも実情に合わなくなってきている。現実的な時間内に限られたメモリ量で問題を解決することは依然として重要であるが、それだけではなく、非確実性をいかに扱うかが主要な課題になっている。したがって、正確さや決定性を犠牲にしても高速に近似最適解を得る、スケーラビリティを重視した情報処理技術...

【研究テーマ】

【研究種目】挑戦的研究(萌芽)

【研究期間】2018-06-29 - 2022-03-31

【研究代表者】今井 浩 東京大学, 大学院情報理工学系研究科, 教授 (80183010)

【キーワード】量子計算 / 量子優越性 / グラウ最適化 / グラフ不変量 / 計算量理論 (他19件)

【概要】グラフのIsing分配関数の計算に対して、グラフ構造の複雑さを表すパラメタの中で枝幅・ランク幅に着目し、そのパラメタを用いた計算量で効率的なものを構成した。特に、パラメタが定数で抑えられるなどの場合に有効である。Ising分配関数からPotts分配関数、そして2変数グラフ不変多項式のTutte多項式へと展開し、有効閉路なしグラフ枝向き付け数に関する成果も得た。Tutte多項式の単峰性が満たされない...

【研究テーマ】ソフトコンピューティング

【研究種目】基盤研究(B)

【研究期間】2016-04-01 - 2019-03-31

【研究代表者】三村 和史 広島市立大学, 情報科学研究科, 教授 (40353297)

【キーワード】情報理論 / 情報統計力学 / 信号処理 / 計算量理論 / 非線形観測 (他9件)

【概要】圧縮センシングのような線形観測に基づくスパース推定の枠組みを，非線形観測の場合に拡張した場合についての解析手法を開発し，具体的な課題に適用した．既存の解析手法では得られない非線形性に由来する性質を明らかにした．さらに，線形観測の場合を含む関連の深い諸問題についての解析や，非線形性を利用した機械学習的手法の推定手法への適用などを行ない，応用上でも重要な知見を得た． ...

【研究テーマ】社会システム工学

【研究種目】一般研究(C)

【研究期間】1991 - 1993

【研究代表者】平澤 茂一 早稲田大学, 理工学部, 教授 (30147946)

【キーワード】知識情報処理 / 情報理論 / 経営工学 / 推論 / 学習 (他15件)

【概要】近年,曖昧性や矛盾を含んだ知識の推論や学習等の,より人間的で複雑な判断をめざした新しい知識情報処理の基礎研究も様々な分野で盛んに行われている.しかしながら従来の論理学を中心としたエキスパートシステムに比べて基礎理論が不完全であり評価基準も不明確であるため得られる結果が理論的に明快に保証されずシステム化が進んでいないのが現状である.本研究ではこれら新しい知識情報処理のために今までの個別的な研究ではな...

【研究テーマ】

【研究種目】挑戦的研究(萌芽)

【研究期間】2018-06-29 - 2022-03-31

【研究代表者】今井 浩 東京大学, 大学院情報理工学系研究科, 教授 (80183010)

【キーワード】量子計算 / 量子優越性 / グラウ最適化 / グラフ不変量 / 計算量理論 (他19件)

【概要】グラフのIsing分配関数の計算に対して、グラフ構造の複雑さを表すパラメタの中で枝幅・ランク幅に着目し、そのパラメタを用いた計算量で効率的なものを構成した。特に、パラメタが定数で抑えられるなどの場合に有効である。Ising分配関数からPotts分配関数、そして2変数グラフ不変多項式のTutte多項式へと展開し、有効閉路なしグラフ枝向き付け数に関する成果も得た。Tutte多項式の単峰性が満たされない...

【研究テーマ】ソフトコンピューティング

【研究種目】基盤研究(B)

【研究期間】2016-04-01 - 2019-03-31

【研究代表者】三村 和史 広島市立大学, 情報科学研究科, 教授 (40353297)

【キーワード】情報理論 / 情報統計力学 / 信号処理 / 計算量理論 / 非線形観測 (他9件)

【概要】圧縮センシングのような線形観測に基づくスパース推定の枠組みを，非線形観測の場合に拡張した場合についての解析手法を開発し，具体的な課題に適用した．既存の解析手法では得られない非線形性に由来する性質を明らかにした．さらに，線形観測の場合を含む関連の深い諸問題についての解析や，非線形性を利用した機械学習的手法の推定手法への適用などを行ない，応用上でも重要な知見を得た． ...

【研究テーマ】ソフトコンピューティング

【研究種目】基盤研究(B)

【研究期間】2016-04-01 - 2019-03-31

【研究代表者】三村 和史 広島市立大学, 情報科学研究科, 教授 (40353297)

【キーワード】情報理論 / 情報統計力学 / 信号処理 / 計算量理論 / 非線形観測 (他9件)

【概要】圧縮センシングのような線形観測に基づくスパース推定の枠組みを，非線形観測の場合に拡張した場合についての解析手法を開発し，具体的な課題に適用した．既存の解析手法では得られない非線形性に由来する性質を明らかにした．さらに，線形観測の場合を含む関連の深い諸問題についての解析や，非線形性を利用した機械学習的手法の推定手法への適用などを行ない，応用上でも重要な知見を得た． ...

【研究テーマ】ソフトコンピューティング

【研究種目】基盤研究(B)

【研究期間】2016-04-01 - 2019-03-31

【研究代表者】三村 和史 広島市立大学, 情報科学研究科, 教授 (40353297)

【キーワード】情報理論 / 情報統計力学 / 信号処理 / 計算量理論 / 非線形観測 (他9件)

【概要】圧縮センシングのような線形観測に基づくスパース推定の枠組みを，非線形観測の場合に拡張した場合についての解析手法を開発し，具体的な課題に適用した．既存の解析手法では得られない非線形性に由来する性質を明らかにした．さらに，線形観測の場合を含む関連の深い諸問題についての解析や，非線形性を利用した機械学習的手法の推定手法への適用などを行ない，応用上でも重要な知見を得た． ...

【研究テーマ】社会システム工学

【研究種目】一般研究(C)

【研究期間】1991 - 1993

【研究代表者】平澤 茂一 早稲田大学, 理工学部, 教授 (30147946)

【キーワード】知識情報処理 / 情報理論 / 経営工学 / 推論 / 学習 (他15件)

【概要】近年,曖昧性や矛盾を含んだ知識の推論や学習等の,より人間的で複雑な判断をめざした新しい知識情報処理の基礎研究も様々な分野で盛んに行われている.しかしながら従来の論理学を中心としたエキスパートシステムに比べて基礎理論が不完全であり評価基準も不明確であるため得られる結果が理論的に明快に保証されずシステム化が進んでいないのが現状である.本研究ではこれら新しい知識情報処理のために今までの個別的な研究ではな...

【研究テーマ】ソフトコンピューティング

【研究種目】基盤研究(B)

【研究期間】2016-04-01 - 2019-03-31

【研究代表者】三村 和史 広島市立大学, 情報科学研究科, 教授 (40353297)

【キーワード】情報理論 / 情報統計力学 / 信号処理 / 計算量理論 / 非線形観測 (他9件)

【概要】圧縮センシングのような線形観測に基づくスパース推定の枠組みを，非線形観測の場合に拡張した場合についての解析手法を開発し，具体的な課題に適用した．既存の解析手法では得られない非線形性に由来する性質を明らかにした．さらに，線形観測の場合を含む関連の深い諸問題についての解析や，非線形性を利用した機械学習的手法の推定手法への適用などを行ない，応用上でも重要な知見を得た． ...

【研究テーマ】ソフトコンピューティング

【研究種目】基盤研究(B)

【研究期間】2016-04-01 - 2019-03-31

【研究代表者】三村 和史 広島市立大学, 情報科学研究科, 教授 (40353297)

【キーワード】情報理論 / 情報統計力学 / 信号処理 / 計算量理論 / 非線形観測 (他9件)

【概要】圧縮センシングのような線形観測に基づくスパース推定の枠組みを，非線形観測の場合に拡張した場合についての解析手法を開発し，具体的な課題に適用した．既存の解析手法では得られない非線形性に由来する性質を明らかにした．さらに，線形観測の場合を含む関連の深い諸問題についての解析や，非線形性を利用した機械学習的手法の推定手法への適用などを行ない，応用上でも重要な知見を得た． ...

【研究テーマ】数学一般(含確率論・統計数学)

【研究種目】基盤研究(A)

【研究期間】1996 - 1998

【研究代表者】河原 康雄 (河原 泰雄) 九州大学, 大学院・システム情報科学研究科, 教授 (90091181)

【キーワード】カテゴリー論 / 計算機科学 / 計算論理学 / 関係計算 / 人工知能 (他8件)

【概要】本研究は、総合的観点からカテゴリー論的計算機数学の基盤研究として行い、以下のような研究成果を得た。 (1) 関係代数、デデキント圏の応用として、新しいプログラミング言語のパラダイムとして注目されている関係型プログラミングの意味論を発展させ、「関係集合論」の基礎理論を構築し、また、並列アルゴリズムのプロセス代数による基礎理論を発展させた。(河原、溝口、大塚) (2) データマイニングの基礎理論を計算...

【研究テーマ】ソフトコンピューティング

【研究種目】基盤研究(B)

【研究期間】2016-04-01 - 2019-03-31

【研究代表者】三村 和史 広島市立大学, 情報科学研究科, 教授 (40353297)

【キーワード】情報理論 / 情報統計力学 / 信号処理 / 計算量理論 / 非線形観測 (他9件)

【概要】圧縮センシングのような線形観測に基づくスパース推定の枠組みを，非線形観測の場合に拡張した場合についての解析手法を開発し，具体的な課題に適用した．既存の解析手法では得られない非線形性に由来する性質を明らかにした．さらに，線形観測の場合を含む関連の深い諸問題についての解析や，非線形性を利用した機械学習的手法の推定手法への適用などを行ない，応用上でも重要な知見を得た． ...

【研究テーマ】数学一般(含確率論・統計数学)

【研究種目】若手研究(B)

【研究期間】2009 - 2011

【研究代表者】小田 芳彰 慶應義塾大学, 理工学部, 准教授 (90325043)

【キーワード】離散数学 / 組合せ論 / 巡回セールスマン問題 / アルゴリズム / 計算量理論

【概要】巡回セールスマン問題はNP困難に属することで知られる有名な問題の1つである.本研究では,この問題とその一般化である車両配送問題および複数の倉庫を持つ車両配送問題について,特に「交差」の条件に着目して取り組み,これらの問題に対する多項式時間で解けるクラスに関していくつかの結果を得た.また,平面上のn点凸状配置に対するハミルトン閉路のフリップによる「交差」の解消に関する問題およびそれに類似する問題につ...

【研究テーマ】数学一般(含確率論・統計数学)

【研究種目】若手研究(B)

【研究期間】2006 - 2008

【研究代表者】小田 芳彰 慶應義塾大学, 理工学部, 講師 (90325043)

【キーワード】組合せ論 / 離散数学 / アルゴリズム論 / 巡回セールスマン問題 / 計算量理論 (他12件)

【概要】巡回セールスマン問題は与えられた複数の都市をすべて1回ずつ通り、出発点に戻ってくるような最短経路を見つける問題である。この問題は板の穴あけなど実社会の問題にも直結する有名な最適化問題の1つである。しかし、都市数が増えるにつれ、コンピュータを利用しても計算にかる時間が指数的に増大する。そこで、問題がどのような条件をみたしていれば、実用的な時間で解が得られるかという研究がなされてきた。研究では、この効...

【研究テーマ】数学一般(含確率論・統計数学)

【研究種目】若手研究(B)

【研究期間】2003 - 2005

【研究代表者】小田 芳彰 慶應義塾大学, 理工学部, 講師 (90325043)

【キーワード】応用数学 / 組合せ論 / アルゴリズム / 巡回セールスマン問題 / 計算量理論 (他8件)

【概要】巡回セールスマン問題(以下、TSP)とは与えられた複数の都市をすべて1回ずつ通り、出発点に戻ってくるような最短経路を見つける問題である。この問題はNP困難のクラスに属し、都市数が増えたとき実用的な時間(多項式時間)で最短経路(最適解)を求めるのは不可能と予想される代表例になっている。そこで、実社会での応用の観点から、実用的は時間で最適解に近い解を求める近似解法の研究がさかんに行われてきた。 TSP...

【研究テーマ】ソフトコンピューティング

【研究種目】基盤研究(B)

【研究期間】2016-04-01 - 2019-03-31

【研究代表者】三村 和史 広島市立大学, 情報科学研究科, 教授 (40353297)

【キーワード】情報理論 / 情報統計力学 / 信号処理 / 計算量理論 / 非線形観測 (他9件)

【概要】圧縮センシングのような線形観測に基づくスパース推定の枠組みを，非線形観測の場合に拡張した場合についての解析手法を開発し，具体的な課題に適用した．既存の解析手法では得られない非線形性に由来する性質を明らかにした．さらに，線形観測の場合を含む関連の深い諸問題についての解析や，非線形性を利用した機械学習的手法の推定手法への適用などを行ない，応用上でも重要な知見を得た． ...

【研究テーマ】社会システム工学

【研究種目】一般研究(C)

【研究期間】1991 - 1993

【研究代表者】平澤 茂一 早稲田大学, 理工学部, 教授 (30147946)

【キーワード】知識情報処理 / 情報理論 / 経営工学 / 推論 / 学習 (他15件)

【概要】近年,曖昧性や矛盾を含んだ知識の推論や学習等の,より人間的で複雑な判断をめざした新しい知識情報処理の基礎研究も様々な分野で盛んに行われている.しかしながら従来の論理学を中心としたエキスパートシステムに比べて基礎理論が不完全であり評価基準も不明確であるため得られる結果が理論的に明快に保証されずシステム化が進んでいないのが現状である.本研究ではこれら新しい知識情報処理のために今までの個別的な研究ではな...

【研究テーマ】数学一般(含確率論・統計数学)

【研究種目】基盤研究(A)

【研究期間】1996 - 1998

【研究代表者】河原 康雄 (河原 泰雄) 九州大学, 大学院・システム情報科学研究科, 教授 (90091181)

【キーワード】カテゴリー論 / 計算機科学 / 計算論理学 / 関係計算 / 人工知能 (他8件)

【概要】本研究は、総合的観点からカテゴリー論的計算機数学の基盤研究として行い、以下のような研究成果を得た。 (1) 関係代数、デデキント圏の応用として、新しいプログラミング言語のパラダイムとして注目されている関係型プログラミングの意味論を発展させ、「関係集合論」の基礎理論を構築し、また、並列アルゴリズムのプロセス代数による基礎理論を発展させた。(河原、溝口、大塚) (2) データマイニングの基礎理論を計算...

【研究テーマ】社会システム工学

【研究種目】一般研究(C)

【研究期間】1991 - 1993

【研究代表者】平澤 茂一 早稲田大学, 理工学部, 教授 (30147946)

【キーワード】知識情報処理 / 情報理論 / 経営工学 / 推論 / 学習 (他15件)

【概要】近年,曖昧性や矛盾を含んだ知識の推論や学習等の,より人間的で複雑な判断をめざした新しい知識情報処理の基礎研究も様々な分野で盛んに行われている.しかしながら従来の論理学を中心としたエキスパートシステムに比べて基礎理論が不完全であり評価基準も不明確であるため得られる結果が理論的に明快に保証されずシステム化が進んでいないのが現状である.本研究ではこれら新しい知識情報処理のために今までの個別的な研究ではな...

【研究テーマ】社会システム工学

【研究種目】一般研究(C)

【研究期間】1991 - 1993

【研究代表者】平澤 茂一 早稲田大学, 理工学部, 教授 (30147946)

【キーワード】知識情報処理 / 情報理論 / 経営工学 / 推論 / 学習 (他15件)

【概要】近年,曖昧性や矛盾を含んだ知識の推論や学習等の,より人間的で複雑な判断をめざした新しい知識情報処理の基礎研究も様々な分野で盛んに行われている.しかしながら従来の論理学を中心としたエキスパートシステムに比べて基礎理論が不完全であり評価基準も不明確であるため得られる結果が理論的に明快に保証されずシステム化が進んでいないのが現状である.本研究ではこれら新しい知識情報処理のために今までの個別的な研究ではな...

【研究テーマ】社会システム工学

【研究種目】一般研究(C)

【研究期間】1991 - 1993

【研究代表者】平澤 茂一 早稲田大学, 理工学部, 教授 (30147946)

【キーワード】知識情報処理 / 情報理論 / 経営工学 / 推論 / 学習 (他15件)

【概要】近年,曖昧性や矛盾を含んだ知識の推論や学習等の,より人間的で複雑な判断をめざした新しい知識情報処理の基礎研究も様々な分野で盛んに行われている.しかしながら従来の論理学を中心としたエキスパートシステムに比べて基礎理論が不完全であり評価基準も不明確であるため得られる結果が理論的に明快に保証されずシステム化が進んでいないのが現状である.本研究ではこれら新しい知識情報処理のために今までの個別的な研究ではな...

【研究テーマ】社会システム工学

【研究種目】一般研究(C)

【研究期間】1991 - 1993

【研究代表者】平澤 茂一 早稲田大学, 理工学部, 教授 (30147946)

【キーワード】知識情報処理 / 情報理論 / 経営工学 / 推論 / 学習 (他15件)

【概要】近年,曖昧性や矛盾を含んだ知識の推論や学習等の,より人間的で複雑な判断をめざした新しい知識情報処理の基礎研究も様々な分野で盛んに行われている.しかしながら従来の論理学を中心としたエキスパートシステムに比べて基礎理論が不完全であり評価基準も不明確であるため得られる結果が理論的に明快に保証されずシステム化が進んでいないのが現状である.本研究ではこれら新しい知識情報処理のために今までの個別的な研究ではな...

【研究テーマ】社会システム工学

【研究種目】一般研究(C)

【研究期間】1991 - 1993

【研究代表者】平澤 茂一 早稲田大学, 理工学部, 教授 (30147946)

【キーワード】知識情報処理 / 情報理論 / 経営工学 / 推論 / 学習 (他15件)

【概要】近年,曖昧性や矛盾を含んだ知識の推論や学習等の,より人間的で複雑な判断をめざした新しい知識情報処理の基礎研究も様々な分野で盛んに行われている.しかしながら従来の論理学を中心としたエキスパートシステムに比べて基礎理論が不完全であり評価基準も不明確であるため得られる結果が理論的に明快に保証されずシステム化が進んでいないのが現状である.本研究ではこれら新しい知識情報処理のために今までの個別的な研究ではな...

【研究テーマ】社会システム工学

【研究種目】一般研究(C)

【研究期間】1991 - 1993

【研究代表者】平澤 茂一 早稲田大学, 理工学部, 教授 (30147946)

【キーワード】知識情報処理 / 情報理論 / 経営工学 / 推論 / 学習 (他15件)

【概要】近年,曖昧性や矛盾を含んだ知識の推論や学習等の,より人間的で複雑な判断をめざした新しい知識情報処理の基礎研究も様々な分野で盛んに行われている.しかしながら従来の論理学を中心としたエキスパートシステムに比べて基礎理論が不完全であり評価基準も不明確であるため得られる結果が理論的に明快に保証されずシステム化が進んでいないのが現状である.本研究ではこれら新しい知識情報処理のために今までの個別的な研究ではな...

【研究テーマ】数学一般(含確率論・統計数学)

【研究種目】基盤研究(A)

【研究期間】1996 - 1998

【研究代表者】河原 康雄 (河原 泰雄) 九州大学, 大学院・システム情報科学研究科, 教授 (90091181)

【キーワード】カテゴリー論 / 計算機科学 / 計算論理学 / 関係計算 / 人工知能 (他8件)

【概要】本研究は、総合的観点からカテゴリー論的計算機数学の基盤研究として行い、以下のような研究成果を得た。 (1) 関係代数、デデキント圏の応用として、新しいプログラミング言語のパラダイムとして注目されている関係型プログラミングの意味論を発展させ、「関係集合論」の基礎理論を構築し、また、並列アルゴリズムのプロセス代数による基礎理論を発展させた。(河原、溝口、大塚) (2) データマイニングの基礎理論を計算...

【研究テーマ】数学一般(含確率論・統計数学)

【研究種目】若手研究(B)

【研究期間】2009 - 2011

【研究代表者】小田 芳彰 慶應義塾大学, 理工学部, 准教授 (90325043)

【キーワード】離散数学 / 組合せ論 / 巡回セールスマン問題 / アルゴリズム / 計算量理論

【概要】巡回セールスマン問題はNP困難に属することで知られる有名な問題の1つである.本研究では,この問題とその一般化である車両配送問題および複数の倉庫を持つ車両配送問題について,特に「交差」の条件に着目して取り組み,これらの問題に対する多項式時間で解けるクラスに関していくつかの結果を得た.また,平面上のn点凸状配置に対するハミルトン閉路のフリップによる「交差」の解消に関する問題およびそれに類似する問題につ...

【研究テーマ】数学一般(含確率論・統計数学)

【研究種目】若手研究(B)

【研究期間】2006 - 2008

【研究代表者】小田 芳彰 慶應義塾大学, 理工学部, 講師 (90325043)

【キーワード】組合せ論 / 離散数学 / アルゴリズム論 / 巡回セールスマン問題 / 計算量理論 (他12件)

【概要】巡回セールスマン問題は与えられた複数の都市をすべて1回ずつ通り、出発点に戻ってくるような最短経路を見つける問題である。この問題は板の穴あけなど実社会の問題にも直結する有名な最適化問題の1つである。しかし、都市数が増えるにつれ、コンピュータを利用しても計算にかる時間が指数的に増大する。そこで、問題がどのような条件をみたしていれば、実用的な時間で解が得られるかという研究がなされてきた。研究では、この効...

【研究テーマ】数学一般(含確率論・統計数学)

【研究種目】若手研究(B)

【研究期間】2003 - 2005

【研究代表者】小田 芳彰 慶應義塾大学, 理工学部, 講師 (90325043)

【キーワード】応用数学 / 組合せ論 / アルゴリズム / 巡回セールスマン問題 / 計算量理論 (他8件)

【概要】巡回セールスマン問題(以下、TSP)とは与えられた複数の都市をすべて1回ずつ通り、出発点に戻ってくるような最短経路を見つける問題である。この問題はNP困難のクラスに属し、都市数が増えたとき実用的な時間(多項式時間)で最短経路(最適解)を求めるのは不可能と予想される代表例になっている。そこで、実社会での応用の観点から、実用的は時間で最適解に近い解を求める近似解法の研究がさかんに行われてきた。 TSP...

【研究テーマ】数学一般(含確率論・統計数学)

【研究種目】若手研究(B)

【研究期間】2006 - 2008

【研究代表者】小田 芳彰 慶應義塾大学, 理工学部, 講師 (90325043)

【キーワード】組合せ論 / 離散数学 / アルゴリズム論 / 巡回セールスマン問題 / 計算量理論 (他12件)

【概要】巡回セールスマン問題は与えられた複数の都市をすべて1回ずつ通り、出発点に戻ってくるような最短経路を見つける問題である。この問題は板の穴あけなど実社会の問題にも直結する有名な最適化問題の1つである。しかし、都市数が増えるにつれ、コンピュータを利用しても計算にかる時間が指数的に増大する。そこで、問題がどのような条件をみたしていれば、実用的な時間で解が得られるかという研究がなされてきた。研究では、この効...

【研究テーマ】数学一般(含確率論・統計数学)

【研究種目】若手研究(B)

【研究期間】2009 - 2011

【研究代表者】小田 芳彰 慶應義塾大学, 理工学部, 准教授 (90325043)

【キーワード】離散数学 / 組合せ論 / 巡回セールスマン問題 / アルゴリズム / 計算量理論

【概要】巡回セールスマン問題はNP困難に属することで知られる有名な問題の1つである.本研究では,この問題とその一般化である車両配送問題および複数の倉庫を持つ車両配送問題について,特に「交差」の条件に着目して取り組み,これらの問題に対する多項式時間で解けるクラスに関していくつかの結果を得た.また,平面上のn点凸状配置に対するハミルトン閉路のフリップによる「交差」の解消に関する問題およびそれに類似する問題につ...

【研究テーマ】数学一般(含確率論・統計数学)

【研究種目】若手研究(B)

【研究期間】2006 - 2008

【研究代表者】小田 芳彰 慶應義塾大学, 理工学部, 講師 (90325043)

【キーワード】組合せ論 / 離散数学 / アルゴリズム論 / 巡回セールスマン問題 / 計算量理論 (他12件)

【概要】巡回セールスマン問題は与えられた複数の都市をすべて1回ずつ通り、出発点に戻ってくるような最短経路を見つける問題である。この問題は板の穴あけなど実社会の問題にも直結する有名な最適化問題の1つである。しかし、都市数が増えるにつれ、コンピュータを利用しても計算にかる時間が指数的に増大する。そこで、問題がどのような条件をみたしていれば、実用的な時間で解が得られるかという研究がなされてきた。研究では、この効...

【研究テーマ】数学一般(含確率論・統計数学)

【研究種目】若手研究(B)

【研究期間】2003 - 2005

【研究代表者】小田 芳彰 慶應義塾大学, 理工学部, 講師 (90325043)

【キーワード】応用数学 / 組合せ論 / アルゴリズム / 巡回セールスマン問題 / 計算量理論 (他8件)

【概要】巡回セールスマン問題(以下、TSP)とは与えられた複数の都市をすべて1回ずつ通り、出発点に戻ってくるような最短経路を見つける問題である。この問題はNP困難のクラスに属し、都市数が増えたとき実用的な時間(多項式時間)で最短経路(最適解)を求めるのは不可能と予想される代表例になっている。そこで、実社会での応用の観点から、実用的は時間で最適解に近い解を求める近似解法の研究がさかんに行われてきた。 TSP...

【研究テーマ】数学一般(含確率論・統計数学)

【研究種目】基盤研究(A)

【研究期間】1996 - 1998

【研究代表者】河原 康雄 (河原 泰雄) 九州大学, 大学院・システム情報科学研究科, 教授 (90091181)

【キーワード】カテゴリー論 / 計算機科学 / 計算論理学 / 関係計算 / 人工知能 (他8件)

【概要】本研究は、総合的観点からカテゴリー論的計算機数学の基盤研究として行い、以下のような研究成果を得た。 (1) 関係代数、デデキント圏の応用として、新しいプログラミング言語のパラダイムとして注目されている関係型プログラミングの意味論を発展させ、「関係集合論」の基礎理論を構築し、また、並列アルゴリズムのプロセス代数による基礎理論を発展させた。(河原、溝口、大塚) (2) データマイニングの基礎理論を計算...

【研究テーマ】数学一般(含確率論・統計数学)

【研究種目】基盤研究(A)

【研究期間】1996 - 1998

【研究代表者】河原 康雄 (河原 泰雄) 九州大学, 大学院・システム情報科学研究科, 教授 (90091181)

【キーワード】カテゴリー論 / 計算機科学 / 計算論理学 / 関係計算 / 人工知能 (他8件)

【概要】本研究は、総合的観点からカテゴリー論的計算機数学の基盤研究として行い、以下のような研究成果を得た。 (1) 関係代数、デデキント圏の応用として、新しいプログラミング言語のパラダイムとして注目されている関係型プログラミングの意味論を発展させ、「関係集合論」の基礎理論を構築し、また、並列アルゴリズムのプロセス代数による基礎理論を発展させた。(河原、溝口、大塚) (2) データマイニングの基礎理論を計算...

【研究テーマ】数学一般(含確率論・統計数学)

【研究種目】若手研究(B)

【研究期間】2009 - 2011

【研究代表者】小田 芳彰 慶應義塾大学, 理工学部, 准教授 (90325043)

【キーワード】離散数学 / 組合せ論 / 巡回セールスマン問題 / アルゴリズム / 計算量理論

【概要】巡回セールスマン問題はNP困難に属することで知られる有名な問題の1つである.本研究では,この問題とその一般化である車両配送問題および複数の倉庫を持つ車両配送問題について,特に「交差」の条件に着目して取り組み,これらの問題に対する多項式時間で解けるクラスに関していくつかの結果を得た.また,平面上のn点凸状配置に対するハミルトン閉路のフリップによる「交差」の解消に関する問題およびそれに類似する問題につ...

【研究テーマ】数学一般(含確率論・統計数学)

【研究種目】若手研究(B)

【研究期間】2006 - 2008

【研究代表者】小田 芳彰 慶應義塾大学, 理工学部, 講師 (90325043)

【キーワード】組合せ論 / 離散数学 / アルゴリズム論 / 巡回セールスマン問題 / 計算量理論 (他12件)

【概要】巡回セールスマン問題は与えられた複数の都市をすべて1回ずつ通り、出発点に戻ってくるような最短経路を見つける問題である。この問題は板の穴あけなど実社会の問題にも直結する有名な最適化問題の1つである。しかし、都市数が増えるにつれ、コンピュータを利用しても計算にかる時間が指数的に増大する。そこで、問題がどのような条件をみたしていれば、実用的な時間で解が得られるかという研究がなされてきた。研究では、この効...

【研究テーマ】数学一般(含確率論・統計数学)

【研究種目】若手研究(B)

【研究期間】2003 - 2005

【研究代表者】小田 芳彰 慶應義塾大学, 理工学部, 講師 (90325043)

【キーワード】応用数学 / 組合せ論 / アルゴリズム / 巡回セールスマン問題 / 計算量理論 (他8件)

【概要】巡回セールスマン問題(以下、TSP)とは与えられた複数の都市をすべて1回ずつ通り、出発点に戻ってくるような最短経路を見つける問題である。この問題はNP困難のクラスに属し、都市数が増えたとき実用的な時間(多項式時間)で最短経路(最適解)を求めるのは不可能と予想される代表例になっている。そこで、実社会での応用の観点から、実用的は時間で最適解に近い解を求める近似解法の研究がさかんに行われてきた。 TSP...

【研究テーマ】数学一般(含確率論・統計数学)

【研究種目】基盤研究(A)

【研究期間】1996 - 1998

【研究代表者】河原 康雄 (河原 泰雄) 九州大学, 大学院・システム情報科学研究科, 教授 (90091181)

【キーワード】カテゴリー論 / 計算機科学 / 計算論理学 / 関係計算 / 人工知能 (他8件)

【概要】本研究は、総合的観点からカテゴリー論的計算機数学の基盤研究として行い、以下のような研究成果を得た。 (1) 関係代数、デデキント圏の応用として、新しいプログラミング言語のパラダイムとして注目されている関係型プログラミングの意味論を発展させ、「関係集合論」の基礎理論を構築し、また、並列アルゴリズムのプロセス代数による基礎理論を発展させた。(河原、溝口、大塚) (2) データマイニングの基礎理論を計算...

【研究テーマ】数学一般(含確率論・統計数学)

【研究種目】若手研究(B)

【研究期間】2006 - 2008

【研究代表者】小田 芳彰 慶應義塾大学, 理工学部, 講師 (90325043)

【キーワード】組合せ論 / 離散数学 / アルゴリズム論 / 巡回セールスマン問題 / 計算量理論 (他12件)

【概要】巡回セールスマン問題は与えられた複数の都市をすべて1回ずつ通り、出発点に戻ってくるような最短経路を見つける問題である。この問題は板の穴あけなど実社会の問題にも直結する有名な最適化問題の1つである。しかし、都市数が増えるにつれ、コンピュータを利用しても計算にかる時間が指数的に増大する。そこで、問題がどのような条件をみたしていれば、実用的な時間で解が得られるかという研究がなされてきた。研究では、この効...

【研究テーマ】

【研究種目】挑戦的研究(萌芽)

【研究期間】2018-06-29 - 2022-03-31

【研究代表者】今井 浩 東京大学, 大学院情報理工学系研究科, 教授 (80183010)

【キーワード】量子計算 / 量子優越性 / グラウ最適化 / グラフ不変量 / 計算量理論 (他19件)

【概要】グラフのIsing分配関数の計算に対して、グラフ構造の複雑さを表すパラメタの中で枝幅・ランク幅に着目し、そのパラメタを用いた計算量で効率的なものを構成した。特に、パラメタが定数で抑えられるなどの場合に有効である。Ising分配関数からPotts分配関数、そして2変数グラフ不変多項式のTutte多項式へと展開し、有効閉路なしグラフ枝向き付け数に関する成果も得た。Tutte多項式の単峰性が満たされない...

【研究テーマ】社会システム工学

【研究種目】一般研究(C)

【研究期間】1991 - 1993

【研究代表者】平澤 茂一 早稲田大学, 理工学部, 教授 (30147946)

【キーワード】知識情報処理 / 情報理論 / 経営工学 / 推論 / 学習 (他15件)

【概要】近年,曖昧性や矛盾を含んだ知識の推論や学習等の,より人間的で複雑な判断をめざした新しい知識情報処理の基礎研究も様々な分野で盛んに行われている.しかしながら従来の論理学を中心としたエキスパートシステムに比べて基礎理論が不完全であり評価基準も不明確であるため得られる結果が理論的に明快に保証されずシステム化が進んでいないのが現状である.本研究ではこれら新しい知識情報処理のために今までの個別的な研究ではな...

【研究テーマ】数学一般(含確率論・統計数学)

【研究種目】基盤研究(A)

【研究期間】1996 - 1998

【研究代表者】河原 康雄 (河原 泰雄) 九州大学, 大学院・システム情報科学研究科, 教授 (90091181)

【キーワード】カテゴリー論 / 計算機科学 / 計算論理学 / 関係計算 / 人工知能 (他8件)

【概要】本研究は、総合的観点からカテゴリー論的計算機数学の基盤研究として行い、以下のような研究成果を得た。 (1) 関係代数、デデキント圏の応用として、新しいプログラミング言語のパラダイムとして注目されている関係型プログラミングの意味論を発展させ、「関係集合論」の基礎理論を構築し、また、並列アルゴリズムのプロセス代数による基礎理論を発展させた。(河原、溝口、大塚) (2) データマイニングの基礎理論を計算...

【研究テーマ】数学一般(含確率論・統計数学)

【研究種目】若手研究(B)

【研究期間】2006 - 2008

【研究代表者】小田 芳彰 慶應義塾大学, 理工学部, 講師 (90325043)

【キーワード】組合せ論 / 離散数学 / アルゴリズム論 / 巡回セールスマン問題 / 計算量理論 (他12件)

【概要】巡回セールスマン問題は与えられた複数の都市をすべて1回ずつ通り、出発点に戻ってくるような最短経路を見つける問題である。この問題は板の穴あけなど実社会の問題にも直結する有名な最適化問題の1つである。しかし、都市数が増えるにつれ、コンピュータを利用しても計算にかる時間が指数的に増大する。そこで、問題がどのような条件をみたしていれば、実用的な時間で解が得られるかという研究がなされてきた。研究では、この効...

【研究テーマ】情報学基礎

【研究種目】基盤研究(A)

【研究期間】2011-04-01 - 2015-03-31

【研究代表者】今井 浩 東京大学, 情報理工学(系)研究科, 教授 (80183010)

【キーワード】量子計算理論 / 量子グラフ理論 / 量子コンピュータ / 計算量理論 / グラフマイナー理論 (他11件)

【概要】量子計算能力の限界解明を目指して、研究分担者・連携研究者らにより多角的に研究を進め、次のような成果をあげた。 (1) 測定ベース量子計算等の量子計算モデルの離散・物理構造に着目し、量子回路最適化や状態変換可能性・測定の汎用実装法・周期グラフ状態の万能計算性について成果を得た。(2) グラフの点マイナー理論を適用して、量子情報の観点からイジング分配関数の効率的計算法を考察し、量子グラフ彩色について量...

【研究テーマ】

【研究種目】挑戦的研究(萌芽)

【研究期間】2018-06-29 - 2022-03-31

【研究代表者】今井 浩 東京大学, 大学院情報理工学系研究科, 教授 (80183010)

【キーワード】量子計算 / 量子優越性 / グラウ最適化 / グラフ不変量 / 計算量理論 (他19件)

【概要】グラフのIsing分配関数の計算に対して、グラフ構造の複雑さを表すパラメタの中で枝幅・ランク幅に着目し、そのパラメタを用いた計算量で効率的なものを構成した。特に、パラメタが定数で抑えられるなどの場合に有効である。Ising分配関数からPotts分配関数、そして2変数グラフ不変多項式のTutte多項式へと展開し、有効閉路なしグラフ枝向き付け数に関する成果も得た。Tutte多項式の単峰性が満たされない...

【研究テーマ】数学一般(含確率論・統計数学)

【研究種目】若手研究(B)

【研究期間】2003 - 2005

【研究代表者】小田 芳彰 慶應義塾大学, 理工学部, 講師 (90325043)

【キーワード】応用数学 / 組合せ論 / アルゴリズム / 巡回セールスマン問題 / 計算量理論 (他8件)

【概要】巡回セールスマン問題(以下、TSP)とは与えられた複数の都市をすべて1回ずつ通り、出発点に戻ってくるような最短経路を見つける問題である。この問題はNP困難のクラスに属し、都市数が増えたとき実用的な時間(多項式時間)で最短経路(最適解)を求めるのは不可能と予想される代表例になっている。そこで、実社会での応用の観点から、実用的は時間で最適解に近い解を求める近似解法の研究がさかんに行われてきた。 TSP...

【研究テーマ】情報学基礎

【研究種目】基盤研究(A)

【研究期間】2011-04-01 - 2015-03-31

【研究代表者】今井 浩 東京大学, 情報理工学(系)研究科, 教授 (80183010)

【キーワード】量子計算理論 / 量子グラフ理論 / 量子コンピュータ / 計算量理論 / グラフマイナー理論 (他11件)

【概要】量子計算能力の限界解明を目指して、研究分担者・連携研究者らにより多角的に研究を進め、次のような成果をあげた。 (1) 測定ベース量子計算等の量子計算モデルの離散・物理構造に着目し、量子回路最適化や状態変換可能性・測定の汎用実装法・周期グラフ状態の万能計算性について成果を得た。(2) グラフの点マイナー理論を適用して、量子情報の観点からイジング分配関数の効率的計算法を考察し、量子グラフ彩色について量...

【研究テーマ】

【研究種目】挑戦的研究(萌芽)

【研究期間】2018-06-29 - 2022-03-31

【研究代表者】今井 浩 東京大学, 大学院情報理工学系研究科, 教授 (80183010)

【キーワード】量子計算 / 量子優越性 / グラウ最適化 / グラフ不変量 / 計算量理論 (他19件)

【概要】グラフのIsing分配関数の計算に対して、グラフ構造の複雑さを表すパラメタの中で枝幅・ランク幅に着目し、そのパラメタを用いた計算量で効率的なものを構成した。特に、パラメタが定数で抑えられるなどの場合に有効である。Ising分配関数からPotts分配関数、そして2変数グラフ不変多項式のTutte多項式へと展開し、有効閉路なしグラフ枝向き付け数に関する成果も得た。Tutte多項式の単峰性が満たされない...

【研究テーマ】情報学基礎

【研究種目】基盤研究(A)

【研究期間】2011-04-01 - 2015-03-31

【研究代表者】今井 浩 東京大学, 情報理工学(系)研究科, 教授 (80183010)

【キーワード】量子計算理論 / 量子グラフ理論 / 量子コンピュータ / 計算量理論 / グラフマイナー理論 (他11件)

【概要】量子計算能力の限界解明を目指して、研究分担者・連携研究者らにより多角的に研究を進め、次のような成果をあげた。 (1) 測定ベース量子計算等の量子計算モデルの離散・物理構造に着目し、量子回路最適化や状態変換可能性・測定の汎用実装法・周期グラフ状態の万能計算性について成果を得た。(2) グラフの点マイナー理論を適用して、量子情報の観点からイジング分配関数の効率的計算法を考察し、量子グラフ彩色について量...

【研究テーマ】

【研究種目】挑戦的研究(萌芽)

【研究期間】2018-06-29 - 2022-03-31

【研究代表者】今井 浩 東京大学, 大学院情報理工学系研究科, 教授 (80183010)

【キーワード】量子計算 / 量子優越性 / グラウ最適化 / グラフ不変量 / 計算量理論 (他19件)

【概要】グラフのIsing分配関数の計算に対して、グラフ構造の複雑さを表すパラメタの中で枝幅・ランク幅に着目し、そのパラメタを用いた計算量で効率的なものを構成した。特に、パラメタが定数で抑えられるなどの場合に有効である。Ising分配関数からPotts分配関数、そして2変数グラフ不変多項式のTutte多項式へと展開し、有効閉路なしグラフ枝向き付け数に関する成果も得た。Tutte多項式の単峰性が満たされない...

【研究テーマ】数学一般(含確率論・統計数学)

【研究種目】若手研究(B)

【研究期間】2006 - 2008

【研究代表者】小田 芳彰 慶應義塾大学, 理工学部, 講師 (90325043)

【キーワード】組合せ論 / 離散数学 / アルゴリズム論 / 巡回セールスマン問題 / 計算量理論 (他12件)

【概要】巡回セールスマン問題は与えられた複数の都市をすべて1回ずつ通り、出発点に戻ってくるような最短経路を見つける問題である。この問題は板の穴あけなど実社会の問題にも直結する有名な最適化問題の1つである。しかし、都市数が増えるにつれ、コンピュータを利用しても計算にかる時間が指数的に増大する。そこで、問題がどのような条件をみたしていれば、実用的な時間で解が得られるかという研究がなされてきた。研究では、この効...

【研究テーマ】数学一般(含確率論・統計数学)

【研究種目】若手研究(B)

【研究期間】2006 - 2008

【研究代表者】小田 芳彰 慶應義塾大学, 理工学部, 講師 (90325043)

【キーワード】組合せ論 / 離散数学 / アルゴリズム論 / 巡回セールスマン問題 / 計算量理論 (他12件)

【概要】巡回セールスマン問題は与えられた複数の都市をすべて1回ずつ通り、出発点に戻ってくるような最短経路を見つける問題である。この問題は板の穴あけなど実社会の問題にも直結する有名な最適化問題の1つである。しかし、都市数が増えるにつれ、コンピュータを利用しても計算にかる時間が指数的に増大する。そこで、問題がどのような条件をみたしていれば、実用的な時間で解が得られるかという研究がなされてきた。研究では、この効...

【研究テーマ】情報学基礎

【研究種目】基盤研究(C)

【研究期間】2003

【研究代表者】岩間 一雄 京都大学, 情報学研究科, 教授 (50131272)

【キーワード】離散アルゴリズム / 離散最適化 / 品質保証 / 近似アルゴリズム / オンラインアルゴリズム (他8件)

【概要】最近のIT社会の大規模化と多様化に伴って、従来から常識のように言われていた正確な計算を速く実行するというパラダイムが必ずしも実情に合わなくなってきている。現実的な時間内に限られたメモリ量で問題を解決することは依然として重要であるが、それだけではなく、非確実性をいかに扱うかが主要な課題になっている。したがって、正確さや決定性を犠牲にしても高速に近似最適解を得る、スケーラビリティを重視した情報処理技術...

【研究テーマ】数学一般(含確率論・統計数学)

【研究種目】若手研究(B)

【研究期間】2003 - 2005

【研究代表者】小田 芳彰 慶應義塾大学, 理工学部, 講師 (90325043)

【キーワード】応用数学 / 組合せ論 / アルゴリズム / 巡回セールスマン問題 / 計算量理論 (他8件)

【概要】巡回セールスマン問題(以下、TSP)とは与えられた複数の都市をすべて1回ずつ通り、出発点に戻ってくるような最短経路を見つける問題である。この問題はNP困難のクラスに属し、都市数が増えたとき実用的な時間(多項式時間)で最短経路(最適解)を求めるのは不可能と予想される代表例になっている。そこで、実社会での応用の観点から、実用的は時間で最適解に近い解を求める近似解法の研究がさかんに行われてきた。 TSP...

【研究テーマ】情報学基礎

【研究種目】基盤研究(C)

【研究期間】2003

【研究代表者】岩間 一雄 京都大学, 情報学研究科, 教授 (50131272)

【キーワード】離散アルゴリズム / 離散最適化 / 品質保証 / 近似アルゴリズム / オンラインアルゴリズム (他8件)

【概要】最近のIT社会の大規模化と多様化に伴って、従来から常識のように言われていた正確な計算を速く実行するというパラダイムが必ずしも実情に合わなくなってきている。現実的な時間内に限られたメモリ量で問題を解決することは依然として重要であるが、それだけではなく、非確実性をいかに扱うかが主要な課題になっている。したがって、正確さや決定性を犠牲にしても高速に近似最適解を得る、スケーラビリティを重視した情報処理技術...

【研究テーマ】数学一般(含確率論・統計数学)

【研究種目】若手研究(B)

【研究期間】2006 - 2008

【研究代表者】小田 芳彰 慶應義塾大学, 理工学部, 講師 (90325043)

【キーワード】組合せ論 / 離散数学 / アルゴリズム論 / 巡回セールスマン問題 / 計算量理論 (他12件)

【概要】巡回セールスマン問題は与えられた複数の都市をすべて1回ずつ通り、出発点に戻ってくるような最短経路を見つける問題である。この問題は板の穴あけなど実社会の問題にも直結する有名な最適化問題の1つである。しかし、都市数が増えるにつれ、コンピュータを利用しても計算にかる時間が指数的に増大する。そこで、問題がどのような条件をみたしていれば、実用的な時間で解が得られるかという研究がなされてきた。研究では、この効...

【研究テーマ】情報学基礎

【研究種目】基盤研究(C)

【研究期間】2003

【研究代表者】岩間 一雄 京都大学, 情報学研究科, 教授 (50131272)

【キーワード】離散アルゴリズム / 離散最適化 / 品質保証 / 近似アルゴリズム / オンラインアルゴリズム (他8件)

【概要】最近のIT社会の大規模化と多様化に伴って、従来から常識のように言われていた正確な計算を速く実行するというパラダイムが必ずしも実情に合わなくなってきている。現実的な時間内に限られたメモリ量で問題を解決することは依然として重要であるが、それだけではなく、非確実性をいかに扱うかが主要な課題になっている。したがって、正確さや決定性を犠牲にしても高速に近似最適解を得る、スケーラビリティを重視した情報処理技術...

【研究テーマ】数学一般(含確率論・統計数学)

【研究種目】若手研究(B)

【研究期間】2006 - 2008

【研究代表者】小田 芳彰 慶應義塾大学, 理工学部, 講師 (90325043)

【キーワード】組合せ論 / 離散数学 / アルゴリズム論 / 巡回セールスマン問題 / 計算量理論 (他12件)

【概要】巡回セールスマン問題は与えられた複数の都市をすべて1回ずつ通り、出発点に戻ってくるような最短経路を見つける問題である。この問題は板の穴あけなど実社会の問題にも直結する有名な最適化問題の1つである。しかし、都市数が増えるにつれ、コンピュータを利用しても計算にかる時間が指数的に増大する。そこで、問題がどのような条件をみたしていれば、実用的な時間で解が得られるかという研究がなされてきた。研究では、この効...

【研究テーマ】社会システム工学

【研究種目】一般研究(C)

【研究期間】1991 - 1993

【研究代表者】平澤 茂一 早稲田大学, 理工学部, 教授 (30147946)

【キーワード】知識情報処理 / 情報理論 / 経営工学 / 推論 / 学習 (他15件)

【概要】近年,曖昧性や矛盾を含んだ知識の推論や学習等の,より人間的で複雑な判断をめざした新しい知識情報処理の基礎研究も様々な分野で盛んに行われている.しかしながら従来の論理学を中心としたエキスパートシステムに比べて基礎理論が不完全であり評価基準も不明確であるため得られる結果が理論的に明快に保証されずシステム化が進んでいないのが現状である.本研究ではこれら新しい知識情報処理のために今までの個別的な研究ではな...