池上大介

J-GLOBALへ         更新日: 18/01/14 10:32
 
アバター
研究者氏名
池上大介
eメール
ikegami.dagmail.com
学位
博士(工学)

研究分野

 
 

経歴

 
2010年4月
 - 
2010年9月
産業技術総合研究所 産学官連携推進部門関西産学官連携センター組込みシステム技術連携研究体[任期付き常勤研究員](兼)情報技術研究部門[研究部門付]
 
2008年4月
 - 
2010年3月
産業技術総合研究所 組込みシステム技術連携研究体 (併任) 任期付き常勤研究員(プロジェクト型)
 
2005年10月
 - 
2010年3月
産業技術総合研究所 システム研究センター 任期付き常勤研究員(プロジェクト型)
 
2005年1月
 - 
2005年3月
スウェーデン Chalmers 工科大学(共同研究開発のための滞在) 戦略的創造推進事業 CREST ポスドク
 
2003年4月
 - 
2005年9月
産業技術総合研究所システム検証研究ラボ 戦略的創造推進事業 CREST ポスドク 『検証における記述量爆発問題の構造変換による解決』 研究終了報告 : http://www.jst.go.jp/kisoken/crest/report/sh_heisei14/jyouhou/kinoshita.pdf
 

論文

 
Sennosuke Watanabe, Yoshihide Watanabe and Daisuke Ikegami
Japan Journal of Industrial and Applied Mathematics      2013年2月   [査読有り]
We give a formulation of the maximum flow problem as an integer programming problem in the standard form. We characterize elementary vectors of the kernel lattice of the matrix coefficient in our formulation in terms of the combinatorial property ...
Hidefumi OHSUGI, Daisuke IKEGAMI, Tomonori KITAMURA, Takayuki HIBI
Advances in Applied Mathematics   31 420-432   2003年8月   [査読有り]
The combinatorics of reduced Gröbner bases of certain zero-dimensional ideals, which arise when Gröbner basis technique is applied to the soft-decision maximum likelihood decoding of binary linear block codes, will be studied.
Daisuke IKEGAMI, Yuichi Kaji
IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences   E86-A(3) 643-651   2003年3月   [査読有り]
New algorithms for the soft-derision and the hard-derision maximum likelihood decoding (MLD) for binary linear block codes are proposed. It has been widely known that both MLD can be regarded as an integer programming with binary arithmetic condit...
Daisuke IKEGAMI
Doctoral Thesis      2003年3月
In the first half of this thesis, a new sub-optimum decoding algorithm is discussed; by combining techniques of maximum likelihood decoding (MLD) and Fossorier's algorithm. In the last half of this thesis, a novel MLD algorithm is proposed: extend...
池上大介
京都大学数理解析研究所講究録   1289 110-121   2002年9月
筆者が発見した、「グレブナ基底を用いた最尤復号アルゴリズム」についての紹介です。京都数理解析研究所での共同利用共同研究「グレブナー基底の理論的有効性と実践的有効性」で発表しました。
Daisuke IKEGAMI, Yuichi KAJI
Proceedings of the 2002 IEEE International Symposium on Information Theory (IEEE ISIT2002)   316   2002年2月   [査読有り]
The soft-decision maximum likelihood decoding belongs to integer programming with constraint linear equations to modular arithmetic. In this paper an algorithm to solve integer programming to modulus an arbitrary positive integer using Gröbner bas...
Yuichi KAJI, Daisuke IKEGAMI
Proceedings of the 2002 IEEE International Symposium on Information Theory (IEEE ISIT2002)   144   2002年2月   [査読有り]
A new algorithm for the soft-decision decoding of linear block codes is proposed. The algorithm uses the technique of the ordered-statistics decoding proposed by Fossorier and Lin (1995) to estimate a certain part of the transmitted code vector, w...
渡邊芳英, 吉武純子, 池上大介
同志社大学理工学研究報告   48(3) 35-42   2007年10月
グレブナー基底を用いた整数計画のアルゴリズムとして、コンティとトラベルソのアルゴリズムが有名である。池上と楫はグレブナー基底を用いた2元線形符号の最尤復号のアルゴリズムを提示したが、それはコンティとトラベルソのアルゴリズムの類似物である。本論文の目的は計算機実験により彼らのアルゴリズムの有効性を検証することである。我々は様々なパラメータをもつ(2元)BCH符号に対して符号に付随するイデアルのグレブナー基底を計算する。ここで用いられるアルゴリズムは二つあり、一つは池上と楫による最初のアルゴリ...
渡邊芳英, 野田良純, 加藤有己, 池上大介
同志社大学理工学研究報告   44(4) 217-226   2004年1月
代数幾何での主要な研究対象になっているトーリック多様体はトーリックイデアルにより定義され,トーリックイデアルは組合せ論や整数計画法などの離散最適化問題において登場し,注目されている。トーリックイデアルのGroebner基底計算は非常に多くの変数を必要とし時間がかかるため,本稿では,それを効率的に行うアルゴリズムの性能評価を行った。ここでは,Conti-Traversoのアルゴリズムと,Hosten-Sturmfelsのアルゴリズムを数式処理システムRisa/Asirに実装し,対象行列のサイ...
中村宗一, 池上大介, 鈴木譲
IEICE technical report. Information theory   99(235) 31-36   1999年7月
Feng-Rao復号法は任意の線型符号をO (n^3) のオーダの計算量である設計距離 (BCH符号ならBCH限界を下回らない値, Goppa符号ならGoppa限界を下回らない値) まで復号するアルゴリズムである. 本研究ではFeng-Rao復号法の種々の定式化のサーベイを行う.

Misc

 
池上大介
数式処理   9(3) 27-28   2003年3月
Traverso 先生のご講演『Carlo Traverso, Alberto Zanoni: Numerical stability and stabilization of Groebner basis computation.』を聞いた感想と、筆者との個人的な研究談話の紹介。

講演・口頭発表等

 
Agda2 による Pythagoras の定理の証明
池上大介
7th 定理証明及び定理証明系ミーティング   2011年11月   
Freek Wiedijk [2007]は、定理証明器の評価と比較のためのベンチマークとして、「√2 は無理数であること」の証明を集めた。 Thierry Coquand [2007] は Wiedijk の要求に応え、 Agda1/Alfa での証明を書いた。しかし、現在 Agda1/Alfa は開発が停止し、用いることができない。Agda1/Alfa の後継として開発されている Agda2 では文法の違いにより Coquand の証明譜を検査することができない。私の知るかぎり、Agda...
Sennosuke Watanabe, Yoshihide Watanabe and Daisuke Ikegami
International Council for Industrial and Applied Mathematics (ICIAM 2011)   2011年7月   http://www.iciam2011.com/
池上大介
RIMS共同研究『数式処理の新たな発展』   2010年7月   照井 章 (筑波大学 数理物質科学研究科)
Computer algebraic systems have a long history of being used for computation. One aspect of the systems which makes them powerful as a mathematical language is that it mixes efficient algorithms with computation. Other is graphical user interfaces...
渡辺扇之介, 渡邊芳英, 池上大介
日本応用数理学会年会(2008年)講演予稿集 pp.11-12   2008年9月   日本応用数理学会
本稿はネットワークの最大流問題に付随するトーリックイデアルの普遍Gröbner基底をグラフの性質により特徴づける。これにより、最大流問題に対する代数的な新しい知見を得た。
宮城奈津子, 渡邊芳英, 池上大介
日本応用数理学会年会   2007年9月   日本応用数理学会
与えられた整数行列に対し、整数核を求める問題はNP完全である。また、整数行列から決まるトーリックイデアルの生成元は有限個であることが Hilbertの基底定理から保証されるが、生成元を決定する問題もNP完全である。本発表では、ネットワークフロー最大流問題に付随する行列の整数核およびトーリックイデアルの生成系を計算せずに、命題として与えることができることを示す。

登壇者の宮城奈津子氏は日本応用数理学会第4回若手講演賞(2007年度)を受賞。
http://www.jsiam.org/mod...
齋藤正也, 高井利憲, 池上大介
第三回システム検証の科学技術シンポジウム   2006年10月   科学技術振興機構、産業技術総合研究所システム検証研究センター
Javaプログラムの例外処理の整合性をモデル検査器SPINを用いて検証する方法に付いて述べる。Javaでは、例外が発生するとただちに正常処理ブロックから例外処理ブロックに移動する。また、複数種類の例外をまとめてひとつの例外処理ブロックで処理することができる。この特長は、コードの可読性の向上と異常時処理の柔軟な記述に貢献する。しかし、一方でプログラム作成者に実行経路を誤解しやすくさせ、その結果、発生する例外と例外処理ブロックの内容に不整合が生じるという問題がある。本研究では、この不整合を発見...
宮城奈津子, 渡邊芳英, 池上大介
日本応用数理学会年会   2006年9月   日本応用数理学会
ネットワーク最適化問題の一つである最大流問題を解く新しいアルゴリズムを提案し、具体例の計算を通じて得た結果を報告する。最大流問題は特別な整数計画問題とみなすことができる。そこで、整数計画問題を解く Conti-Traverso アルゴリズムを最大流問題に応用することを考える。最大流問題は初期の実行可能解が既知の整数計画問題であるため、Conti-Traversoアルゴリズムを適用しやすい。
吉武純子, 渡邊芳英, 池上大介
日本応用数理学会年会   2006年9月   日本応用数理学会
最尤復号法の一つである池上-楫アルゴリズムを、実用上使われている BCH 符号に限定して適用する際の計算時間や計算できる符号長の限界について実験結果を述べる。
高井利憲, 池上大介
JAIST/TRUST - AIST/CVS joint workshop on VERIfication TEchnology (VERITE)   2005年9月   JAIST/TRUST - AIST/CVS
We are working with a company to research, design, develop and verify the network system. In the last year, we tried to prove security properties of the network system. In this year, we are trying to find bugs in the specifications of the system b...
池上大介
日本ソフトウェア科学会第22回大会   2005年9月   日本ソフトウェア科学会
Martin-Löf の型理論に基づく対話型定理証明支援系である Agda のプラグイン機構について述べる。ここで、プラグイン機構とは Agda の中で外部のツールを起動し、証明や型検査を外部のツールに代行させるためのインターフェースを言う。プラグイン機構により、モデル検査器や自動定理証明器と Agda を接続することができる。Agda とモデル検査器や自動定理証明システムを組み合わせた統合的検証環境の構築が本研究の目的であり課題である。
池上大介
計算機代数セミナー   2004年11月   横山和弘
トーリックイデアルが整数計画問題を解くアルゴリズムを導出するという既知の結果から類推して、整数格子状の線形重み最小元を求める問題を解くアルゴリズムを構成した。このアルゴリズムは、誤り訂正符号理論における、白色ガウス雑音通信路における軟判定最尤復号に相当することを述べた。
池上大介
システム検証の科学技術シンポジウム   2004年2月   科学技術振興機構・産業技術総合研究所システム検証研究ラボ
本発表では、単項二階論理とωオートマトン・様相μ計算についてよく知られた次の二つの結果を紹介する。
(1) [Buchi 1962] 文字列上の単項二階論理が表現する文字列のクラスと、ωオートマトンが受理する文字列のクラスは等しい。
(2) [Janin-Walukiewicz 1992] 遷移系上の単項二階論理が表現する遷移系のクラスと、様相μ計算が表現する遷移系のクラスは双模倣同値である。
池上大介
第20回「記号論理学と情報科学」研究集会 SLACS 2003   2003年9月   佐藤周行
非決定性オートマトンから、受理言語が等しい決定性オートマトンを変換することができる。しかし、変換されたオートマトンの状態数は変換前に比べて指数的に増大するのが問題である。そこで、非決定性オートマトンを(決定性オートマトンに変換せずに)扱うことができれば望ましい。一方、受理言語が等しい非決定性オートマトンは沢山あるので、その中から「扱いやすい非決定性オートマトンとは何か」を決める必要がある。本発表では、非決定性オートマトンを regular category で再定義し、非決定性オートマトン...
池上大介
2003年度 夏のLAシンポジウム   2003年7月   LAシンポジウム
池上大介
情報理論(IT)研究会 技術研究報告103(215) 33-37   2003年7月   電子情報通信学会
本稿では,著者によって提案されているグレブナ基底を用いた最尤復号法について議論する.この最尤復号法は軟判定ならびに硬判定に適用することができるが,どちらの場合においても計算量の評価はなされていなかった.この最尤復号法の計算量はグレブナ基底の個数によって決まるので,本研究ではグレブナ基底の個数の上界を与える.
池上大介
日本数式処理学会第11回大会   2002年9月   村尾裕一
渡邊芳英, 野田良純, 加藤有己, 池上大介
日本数式処理学会第11回大会 : 数式処理 9(4), 24-25, 2003-04-01   2002年9月   村尾裕一
池上大介, 楫勇一
第25回情報理論とその応用シンポジウム(SITA2002) Vol.1 pp.15-18   2002年12月   情報理論とその応用学会
池上-楫最尤復号アルゴリズムは計算量が大きいため実用にならない。そこで、アルゴリズムをヒューリスティックに停止させ、時間と尤度のトレードオフをとり、その計算機実験を行ったので報告する。
池上大介
第10回研究集会   2002年3月   Risa Consortium
P. Conti と C. Traverso は Gröbner 基底を用いて整数計画問題 (図 1) を解くアルゴリズムを構成した [2] ([1, 3] に整理された形でまとめられている)。一方、発表者のグループは Conti-Traverso アルゴリズムを修正して、正整数 q ≧ 2 を法とする整数計画問題 (図 2) を解くアルゴリズムを提案している [4]。本発表では、q を法とする整数計画問題を、ある 0 次元イデアルの Gröbner 基底を用いて解くアルゴリズムを紹介し、...
池上大介, 楫勇一
第24回情報理論とその応用シンポジウム(SITA2001) Vol.2 pp.545-548   2001年12月   情報理論とその応用学会
整数計画問題を解くConti-Traversoアルゴリズムを変形することにより、2 を法とする整数計画問題(ただし、重みは実数ベクトルと(0,1)ベクトルの内積をとる)を解くアルゴリズムを構築した。これにより、白色ガウス雑音通信路において任意の線形符号の最尤復号を行うことができることを示す。
Keong Tan Soon, 池上大介, 楫勇一
情報理論(IT)研究会 100(695) pp.91-97   2001年3月   電子情報通信学会
与えられた誤り訂正符号が,与えられた通信環境においてどの程度の誤り訂正能力を発揮するか評価することは,信頼性の高い通信系を実現するうえで不可欠なことである.誤り訂正能力の指標としては,その環境において最尤復号を行ったときの復号誤り率がしばしば用いられらが,規模の大きなブロック符号に対して実際に最尤復号を行うことは,計算量的に困難である.著者らの研究グループでは,従来法よりも効率的な最尤復号アルゴリズムとして,適応型最尤復号アルゴリズムを提案しているが,それでも最尤復号が可能な符号の規模には...
Sudanのリスト復号法の高速化に関する考察
池上大介, 鈴木譲, 三浦晋示
第22回情報理論とその応用シンポジウム vol.II pp.641-644   1999年12月   情報理論とその応用学会
It has been open problem whether the syndrome array for the key equation exists in the framework of Sudan's list decoding. If it does, the Berlekamp-Massey-Sakata(BMS) algorithm can be applied the decoding scheme. We solve this problem in the nega...
池上大介
言語,代数系および計算機システム : 京都大学数理解析研究所講究録 No.1106 pp.50-60   1999年7月   伊藤正美 (京都産業大学)
This paper introduces a procedure for decoding linear codes up to half the Feng-Rao bound which is defined by R.Pellikaan, G-L.Feng, K. K.Tzeng and T.R.N.Rao found the procedure, and they showed it was a generalization of the Berlekamp-Massey algo...

Works

 
統合検証環境
永山操, 池上大介, 武山誠   コンピュータソフト   2005年12月
情報社会を支える新しい高性能情報処理技術第2回公開シンポジウムにおけるデモンストレーション