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
170
不変量
(若手)エンジニアもくもく会 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.8k
WebHID API でリングコン のセンサー値を取得してみた
mascii
1
1k
Pros and Cons で考える Vue 2 Composition API
mascii
4
1.1k
Joy-ConをJavaScriptでプレゼンリモコンにした話
mascii
0
550
TypeScript で Optional Chaining を使ってみた
mascii
1
730
Vue.jsでCSS Modulesを使ってみた
mascii
0
140
Nuxt.js+Firebaseで個人サービスを作るまで
mascii
1
2.4k
JavaScriptのバージョンの話
mascii
1
2.2k
あなたのお家に眠るラズパイを救出したい
mascii
4
3k
Other Decks in Science
See All in Science
04_石井クンツ昌子_お茶の水女子大学理事_副学長_D_I社会実現へ向けて.pdf
sip3ristex
0
460
深層学習を用いた根菜類の個数カウントによる収量推定法の開発
kentaitakura
0
150
メール送信サーバの集約における透過型SMTP プロキシの定量評価 / Quantitative Evaluation of Transparent SMTP Proxy in Email Sending Server Aggregation
linyows
0
900
証明支援系LEANに入門しよう
unaoya
0
1.1k
統計的因果探索: 背景知識とデータにより因果仮説を探索する
sshimizu2006
4
880
機械学習 - ニューラルネットワーク入門
trycycle
PRO
0
750
白金鉱業Meetup Vol.15 DMLによる条件付処置効果の推定_sotaroIZUMI_20240919
brainpadpr
2
820
機械学習 - 決定木からはじめる機械学習
trycycle
PRO
0
930
統計学入門講座 第4回スライド
techmathproject
0
140
[第62回 CV勉強会@関東] Long-CLIP: Unlocking the Long-Text Capability of CLIP / kantoCV 62th ECCV 2024
lychee1223
1
940
As We May Interact: Challenges and Opportunities for Next-Generation Human-Information Interaction
signer
PRO
0
500
トラブルがあったコンペに学ぶデータ分析
tereka114
2
1.6k
Featured
See All Featured
ピンチをチャンスに:未来をつくるプロダクトロードマップ #pmconf2020
aki_iinuma
123
52k
Learning to Love Humans: Emotional Interface Design
aarron
273
40k
Speed Design
sergeychernyshev
30
980
個人開発の失敗を避けるイケてる考え方 / tips for indie hackers
panda_program
106
19k
Distributed Sagas: A Protocol for Coordinating Microservices
caitiem20
331
22k
Fantastic passwords and where to find them - at NoRuKo
philnash
51
3.3k
Building an army of robots
kneath
306
45k
Practical Orchestrator
shlominoach
188
11k
Optimizing for Happiness
mojombo
379
70k
Art, The Web, and Tiny UX
lynnandtonic
299
21k
Why You Should Never Use an ORM
jnunemaker
PRO
56
9.4k
Understanding Cognitive Biases in Performance Measurement
bluesmoon
29
1.7k
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