ナカナカピエロ おきらくごくらく

写真付きで日記や趣味を書くならgooブログ

すうがくぶんかさんの「グレブナー基底入門」講座に参加❣☺

2021-12-26 19:37:12 | 日記
すうがくぶんかさんの「グレブナー基底入門」講座に参加❣☺

今日は、日曜日。晴れときどき曇り。

7時起床。

今日は10時から以下のオンライン講座に参加予定。

=====
講座名: グレブナー基底入門
授業日時: 2021年12月26日(日) 10:00-17:00 (休憩1時間)
講師:神戸祐太先生
詳細ページ: https://sugakubunka.com/grobner-free/
=====

とりあえずもろもろ雑事をこなして、8時。

朝食。

「たのしい2Dゲームの作り方」のChapter6(P.209/417)まで終わらせた。

そして昨日購入した「トコトンやさしい量子コンピュータの本」を読んでいた。

10時前にZoomから入って待機。

10時~グレブナー基底入門講座開始。

以下は個人的なメモなので分かりずらいかもしれない処はご容赦。

まずはグレブナー基底のイメージを掴むために実計算を例で説明。

Sageという特別な言語でグレブナー基底の計算デモをまずやった。

SageはPythonベースの上、数学を使う上でサポートが豊富であるとのこと。

純粋にPythonとかでグレブナー基底を使用できるか?という質問をしたら、

以下のURLを紹介された。

Coding in Python for Sage

またRisa/Asirでもグレブナー基底の計算デモもやった。

パラメタで、順序(辞書式順序、次数つき辞書式順序、逆辞書式順序)を指定する

引数があって、多項式の計算を解くには辞書順でないと駄目とのこと。

グレブナー基底は、基本的に多次元多変数の方程式を解くために、一変数の

多項式イデアル、二変数の多項式イデアル、・・・に分解して解く

ブッフバーガーアルゴリズムでできているとうことらしい。

11時~Conti-Traversoアルゴリズムで整数計画法への応用の話をしていた。

普通は動的計画法を使ってやると思っていたので、グレブナー基底でできる

とは驚き。受講者からこんな論文を紹介されていた。

グレブナー基底と整数計画問題

計算関連の書籍としては「グレブナー道場」がお薦め本とのこと。

グレブナー道場 JST CREST 日比チーム

特に第4章が統計学との関係でお勧めとのこと。

次は、数理編・発展編の講義。

多項式環の定義と変数消去法の話の講義を聴講した。

私のお勧めの本は「グレブナー基底と代数多様体」がお勧め。

グレブナ基底と代数多様体入門・上 D.コックス
グレブナ基底と代数多様体入門〈下〉イデアル・多様体・アルゴリズム デビッド コックス

お昼休憩。(12:15~13:05)

昼食を食べた後、「トコトンやさしい量子コンピュータの本」を読書(P.49/156)。

13:05~午後は続きの数理編・発展編の講義。

まずは消去法の話の続きから。

消去法では、まずどの項からどう消すかが問題。

そこで出てくるのが"項順序"で、これで優先順位を決めるということ。

多項式に出てくる変数の全てに指数を付けてn変数の多項式順序の順序(項順序)

を定義して全順序関係を導入する。

順序として辞書式順序、次数つき辞書式順序、逆辞書式順序などがあるとのこと。

より複雑なものから消去しようというのが消去法のコンセプト。

で、多項式環に項順序を導入すると消去法ができるというが仕掛け。

ここで疑問を提起。必ず解は存在するか、どの順序が最適か、計算量はどうか?

この疑問を明らかにするために数学的な定式化が必要。

という訳で代数的集合とイデアルの講義。

代数的集合は多項式環の解の集合(V(f1,f2,・・・,fr)と書く)のこと。

グレブナー基底の解が同じとは、f1=f2=・・・=fr=0について、g1=g2=・・・=gs=0

が成り立つということ。以下は、その定式化。

g1,g2,・・・,gsをf1,f2,・・・,frで生成されるイデアルのグレブナー基底とする。

このときV(f1,f2,・・・,fr)=V(g1,g2,・・・,gs)となる。

この場合のイデアルとは、以下を満たすことである。

(I-1) Iは0を含む。
(I-2) fとgがIの元ならf+gもIに含まれる。
(I-3) fがIの元でgがn変数多項式ならgfもIに含まれる。

まさに(I-2)(I-3)は消去法でやった操作に該当する。なるほどねと思った。

がf1,f2,・・・,frで生成されるイデアルの記号で最小イデアルとなる。

消去法はの中で行われる。

解が存在しない場合にもイデアルやグレブナー基底も存在し、解の存在判定にも重要な

役割を果たす(らしい)。

いよいよグレブナー基底の定義。まず=を満たすこと。

後はイニシャルイデアルが生成できること。

イニシャルイデアルとは項順序を1つ設定しておき、多項式fのイニシャル(項順序で最大のもの)

イデアルを決めること。イニシャルとは簡単に言えば、解きたい多項式から消去法を使うのですが、

複雑なものから消去しましょうというのがイニシャル。

その複雑な項を特定するために定式化するのだということ。

このイニシャルたちが蠢く多項式の集合(で生成されるイデアル)をイニシャルイデアルという。

で、グレブナー基底の定義は、G={g1,g2,・・・,gs}がIのグレブナー基底であるとは

・I=
・Iのイニシャルイデアルとg1のイニシャルイデアル・・・gsのイニシャルイデアルから生成される
 イデアルに等しい。

を満たすこと。何となく、方法と定義が逆転しているようだけど、この順序で良いらしい。

ブッフバーガーさんがうまいことグレブナー基底の判定方法をやっているとのこと。

ただ、ブッフバーガーの判定法で、try and errorでグレブナー基底を求めるということになるので、

組み合わせの数が爆発してコンピュータで求めると著しく遅くなることがありうるとのことで、

それが次の実用化に向けての課題なるのかもということでした。

なので、イニシャルイデアルが先ではなくて、まずグレブナー基底を求めて、それから

イニシャルイデアルが分かるらしい。

以降は、消去定理、計算困難性のお話。

まずは消去定理から。

命題:V(f1,f2,・・・,fr)=V(g1,g2,・・・,gs)の解全体の集合は等しい。

で、それを前提すると消去定理によりグレブナー基底があり、解が求めやすいことが分かる。

消去定理はグレブナー基底により(自動的に)変数削減できるみたいなものなのかな。

で、消去定理は消去順序でのみ成り立つ。ということなので辞書式順序以外は消去定理を

満たさないので、多項式の解をグレブナー基底で求めるときには、辞書式順序を指定するのが

適切だということ(らしい)。

ただ代数幾何や射影幾何を扱う時には次数付きの順序を選択するケースがあるとのこと。

最後は計算困難性の話。

最悪計算量を考慮すると次数dの生成系から次数2^2^dのグレブナー基底が作れるという定理。

かつグレブナー基底計算はNP完全問題(要は多項式時間で解けるかという未解決問題)を

孕んでいるとのこと。(いわゆるP=NP?というミレニアム問題に関わる。)

そりゃ、実用化はまだまだ難しいかも。

でも逆手にとって暗号に利用することも考えられているらしい。

最後に代数幾何との関わりについての話。

(広義の)代数多様体V(f1,f2,・・・,fr)の次元がいくつかを求める問題に使えるとのこと。

定理としてのイニシャルイデアルをJとすると、

dim V(f1,f2,・・・,fr)=dim V(J)となるものがあり、グレブナー基底が求まれば、

イニシャルイデアルも分かり、次元はすぐに求まるとのことでした。

この代数多様体のイニシャルイデアルへの変形をグレブナー変形というらしい。

ちょっとトポロジーとの関連もあるみたい。

最後の質疑応答で、グレブナー基底で主成分分析への応用とかもあるらしい。

以下がその論文らしい。

Vanishing Component Analysis

また非線形にも強いらしい。。。すごいな。。。

これで全講義終了❣☺

全講義を通じて、なんとなーくお気持ちだけはわかったような気がします。とても面白かった。

夕飯は家で済ませた。

その後、まっちゃんのワイドナショーを観た。

これからお風呂にも入って洗濯して寝る。

今日一日のコロナ感染数は全国で263人、神奈川県は36人、東京都は43人。。。

明日は、年休だけど、UnityとWebAssemblyの勉強をする予定。

やっぱり左肩痛い。。。五十肩だ。。。(´;ω;`)ウッ…

【今後の予定】
・2021年11月~ 職業訓練校Java&Python&Web技術者(3か月)
・2022年01月~ 職業訓練校Java&DB&Web技術者(3か月)
・2022年02月~ 職業訓練校(2か月)

【詳細TODOリスト】
・訓練校11月生対応

・01/18 訓練校11月生(データベースとWeb)メイン  (Python-DB連携/HTML復習)
・01/19 訓練校11月生(データベースとWeb)メイン  (JavaScript)
・01/20 訓練校11月生(データベースとWeb)メイン  (JavaScript)
・01/21 訓練校11月生(データベースとWeb)メイン  (Servlet&JSP)
・01/24 訓練校11月生(データベースとWeb)メイン  (Servlet&JSP)
・01/25 訓練校11月生(Webシステム演習) メイン  (Servlet&JSP)
・01/26 訓練校11月生(Webシステム演習) メイン  (Servlet&JSP)
・01/27 訓練校11月生(Webシステム演習) メイン  (総合演習)
・01/28 訓練校11月生(Webシステム演習) メイン  (総合演習)

・02/04 訓練校01月生(プログラミング概論)メイン PM (Java文法復習-Bronze問題集から)
・02/07 訓練校01月生(プログラミング概論)メイン   (データ構造とアルゴリズム)
・02/08 訓練校01月生(プログラミング概論)メイン   (基本文法演習)
・02/09 訓練校01月生(プログラミング概論)メイン   (制御構文演習)
・02/10 訓練校01月生(プログラミング概論)メイン   (メソッド演習)   
・02/14 訓練校01月生(プログラミング概論)メイン AM (じゃんけんプログラム演習)
・02/15 訓練校01月生(プログラミング概論)メイン   (配列・挿入ソート)

・02/16 訓練校01月生(Java演習)サブ
・02/17 訓練校01月生(Java演習)サブ
・02/18 訓練校01月生(Java演習)サブ
・02/21 訓練校01月生(Java演習)サブ
・02/22 訓練校01月生(Java演習)サブ
・02/24 訓練校01月生(Java演習)サブ
・02/25 訓練校01月生(Java演習)サブ

・02/28 訓練校01月生(データベースとSQL)メイン   (1章~6章)
・03/01 訓練校01月生(データベースとSQL)メイン   (7章~12章)
・03/02 訓練校01月生(データベースとSQL)メイン   (mySQL/JDBC)
・03/04 訓練校01月生(データベースとSQL)メイン   (演習)

・03/07 訓練校01月生(アルゴリズム演習)メイン    (単方向・双方向リスト)
・03/08 訓練校01月生(アルゴリズム演習)メイン    (スタック・キュー)
・03/09 訓練校01月生(アルゴリズム演習)メイン    (ハッシュテーブル)
・03/10 訓練校01月生(アルゴリズム演習)メイン    (ナップザック問題:動的計画法)
・03/14 訓練校01月生(アルゴリズム演習)メイン    (二分木・チャレンジ問題)
・03/15 訓練校01月生(アルゴリズム演習)メイン    (オセロプログラム)
・03/16 訓練校01月生(アルゴリズム演習)メイン    (オセロプログラム)

・03/17 訓練校01月生(Webシステム構築)メイン    (HTML)
・03/18 訓練校01月生(Webシステム構築)メイン    (HTML フォーム)
・03/22 訓練校01月生(Webシステム構築)メイン    (Servlet&JSP)
・03/23 訓練校01月生(Webシステム構築)メイン    (MVCモデル・スコープ)
・03/24 訓練校01月生(Webシステム構築)メイン    (その他の講義)
・03/25 訓練校01月生(Webシステム構築)メイン    (総合演習)
・03/28 訓練校01月生(Webシステム構築)メイン    (総合演習)
・03/29 訓練校01月生(Webシステム構築)メイン    (総合演習/Tomcatデプロイ)

・高度な教育講座の検討ww(笑)

・Unity講座の検討

【今日の読書】
■ Unity関連
スラスラ読める Unity C#ふりがなプログラミング リブロワークス(読了)
Unityの寺子屋 定番スマホゲーム開発入門 いたのくまんぼう(読了)
たのしい2Dゲームの作り方 Unityではじめるゲーム開発入門 STUDIO SHIN
Unity2021入門 最新開発環境による簡単3D&2Dゲーム制作 荒川巧也
Unityの教科書 Unity 2021完全対応版 2D&3Dスマートフォンゲーム入門講座 北村 愛実
Unity2021 3D/2Dゲーム開発実践入門 吉谷 幹人

■WebAssembly関連
入門WebAssembly Rick Battagline(P.27/285読了)

■Web関連
Bootstrap 5 入門: 基礎から実演まで Web開発入門 原田 けいと

■確率・統計・機械学習関連
統計学を拓いた異才たち(日経ビジネス人文庫) デイヴィッド・サルツブルグ
ディープラーニングと物理学 原理がわかる、応用ができる (KS物理専門書) 田中 章詞
5日でわかるOpenCVプログラミング入門 日経ソフトウエア
ビジュアルテキスト パターン認識 荒井 秀一(P.88/256読了)
多変量統計解析法 田中 豊
心を知るための人工知能: 認知科学としての記号創発ロボティクス (越境する認知科学) 谷口 忠大
統計学への確率論、その先へ―ゼロからの測度論的理解と漸近理論への架け橋 清水 泰隆
ランダム行列の数理と科学 渡辺澄夫
認知バイアス 心に潜むふしぎな働き (ブルーバックス) 鈴木 宏昭
ベイズ統計の理論と方法 渡辺 澄夫
経済・ファイナンスのための カルマンフィルター入門 (統計ライブラリー) 森平 爽一郎
数理科学 2020年 11 月号 [雑誌]
人工知能 機械学習はどこまで進化するのか (別冊日経サイエンス239) 竹内郁雄
データ分析の力 因果関係に迫る思考法 (光文社新書) 伊藤 公一朗
応用に役立つ50の最適化問題 (応用最適化シリーズ) 藤澤 克樹

■量子力学・量子コンピュータ関連
今日からモノ知りシリーズ トコトンやさしい量子コンピュータの本 山﨑耕造
みんなの量子コンピュータ Chris Bernhardt
入門講義 量子コンピュータ (KS物理専門書) 渡邊 靖志

■数学関連
代数幾何学入門:代数学の基礎を出発点として 永井 保成

■その他
フォン・ノイマンの哲学 人間のフリをした悪魔 (講談社現代新書) 高橋昌一郎
物理学者のすごい思考法 (インターナショナル新書) 橋本 幸士
絵で見てわかるSQL Serverの仕組み 平山 理(P.84/314読了)
コメント
  • X
  • Facebookでシェアする
  • はてなブックマークに追加する
  • LINEでシェアする