Upgrade to Pro
— share decks privately, control downloads, hide ads and more …
Speaker Deck
Features
Speaker Deck
PRO
Sign in
Sign up for free
Search
Search
不変量
Search
Masaki Koyanagi
April 27, 2019
Science
1
150
不変量
(若手)エンジニアもくもく会 vol.12 @CrowdWorks
https://youth-engineer-mokumoku.connpass.com/event/126962/
Masaki Koyanagi
April 27, 2019
Tweet
Share
More Decks by Masaki Koyanagi
See All by Masaki Koyanagi
Vitestを使った型テストの始め方
mascii
6
2.7k
WebHID API でリングコン のセンサー値を取得してみた
mascii
1
960
Pros and Cons で考える Vue 2 Composition API
mascii
4
1.1k
Joy-ConをJavaScriptでプレゼンリモコンにした話
mascii
0
520
TypeScript で Optional Chaining を使ってみた
mascii
1
700
Vue.jsでCSS Modulesを使ってみた
mascii
0
130
Nuxt.js+Firebaseで個人サービスを作るまで
mascii
1
2.3k
JavaScriptのバージョンの話
mascii
1
2.2k
あなたのお家に眠るラズパイを救出したい
mascii
4
3k
Other Decks in Science
See All in Science
理論計算機科学における 数学の応用: 擬似ランダムネス
nobushimi
1
400
Tensor Representations in Signal Processing and Machine Learning (Tutorial at APSIPA-ASC 2020)
yokotatsuya
0
110
機械学習を支える連続最適化
nearme_tech
PRO
1
250
はじめての「相関と因果とエビデンス」入門:“動機づけられた推論” に抗うために
takehikoihayashi
17
7.3k
[第62回 CV勉強会@関東] Long-CLIP: Unlocking the Long-Text Capability of CLIP / kantoCV 62th ECCV 2024
lychee1223
1
840
Valuable Lessons Learned on Kaggle’s ARC AGI LLM Challenge (PyDataGlobal 2024)
ianozsvald
0
210
WCS-LA-2024
lcolladotor
0
180
地表面抽出の方法であるSMRFについて紹介
kentaitakura
1
300
Celebrate UTIG: Staff and Student Awards 2024
utig
0
580
WeMeet Group - 採用資料
wemeet
0
4.4k
拡散モデルの原理紹介
brainpadpr
3
5.8k
Pericarditis Comic
camkdraws
0
1.5k
Featured
See All Featured
Done Done
chrislema
182
16k
The Art of Delivering Value - GDevCon NA Keynote
reverentgeek
10
1.3k
Practical Orchestrator
shlominoach
186
10k
Speed Design
sergeychernyshev
27
790
I Don’t Have Time: Getting Over the Fear to Launch Your Podcast
jcasabona
32
2.1k
CSS Pre-Processors: Stylus, Less & Sass
bermonpainter
356
29k
[RailsConf 2023 Opening Keynote] The Magic of Rails
eileencodes
28
9.3k
Navigating Team Friction
lara
183
15k
10 Git Anti Patterns You Should be Aware of
lemiorhan
PRO
656
59k
Build your cross-platform service in a week with App Engine
jlugia
229
18k
Fashionably flexible responsive web design (full day workshop)
malarkey
406
66k
The World Runs on Bad Software
bkeepers
PRO
67
11k
Transcript
不変量
自己紹介 小柳 昌生 (Koyanagi Masaki) Twitter: @mascii_k 株式会社ビザスク エンジニア
Wikipedia 不変量(ふへんりょう、invariant)とは、数学的対象を特 徴付ける別種の数学的対象のことである。一般に、不変 量は数や多項式など、不変量同士の同型性判定がもと の対象の同型性判定より簡単であるものをとる。良い不 変量とは、簡単に計算でき、かつなるべく強い同型性判 別能力をもつものである。
None
例 https://www.ap-siken.com/kakomon/26_haru/q2.html
答え:AはCと同形であるが,Bとは同形でない。 Animation GIF: https://www.ap-siken.com/kakomon/26_haru/img/02a.gif
A,C と B が同型でない理由 説明できますか???
A,C と B が同型でない理由 最小部分サイクルのサイズを与える関数 f を考える f(A) = 4,
f(B) = 3, f(C) = 4 ※この f はグラフ理論において「内周」と呼ばれる不変量で、 gで表すことが多い
A,C と B が同型でない理由 他にも、頂点の数・辺の数・次数列といった不変量がある (今回の A,B,C は全て一致してしまう)
同じではないことを示す方が簡単だったりする グラフの同型に関する問題は、 頂点数が増えると一気に難しくなることが知られています。 等しくないことは、いい感じの不変量が等しくないことを示せればOK x, y が等しい ⇒ f(x) と
f(y) が等しい ↓(対偶) f(x), f(y) が等しくない ⇒ x と y が等しくない
SHA-1 (ハッシュ関数) の例 ファイル x, y の ハッシュ値 SHA-1(x) と
SHA-1(y) が等しくなけ れば x と y は異なるファイルである: ◯ ファイル x, y の ハッシュ値 SHA-1(x) と SHA-1(y) が等しいなら ば x と y は同じファイルである: ×
反例 PDF1 https://qiita.com/rana_kualu/items/53368eeec521013f0c11 PDF2