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
140
不変量
(若手)エンジニアもくもく会 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
950
Pros and Cons で考える Vue 2 Composition API
mascii
4
1k
Joy-ConをJavaScriptでプレゼンリモコンにした話
mascii
0
510
TypeScript で Optional Chaining を使ってみた
mascii
1
690
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
機械学習による確率推定とカリブレーション/probabilistic-calibration-on-classification-model
ktgrstsh
2
330
化学におけるAI・シミュレーション活用のトレンドと 汎用原子レベルシミュレーター: Matlantisを使った素材開発
matlantis
0
370
学術講演会中央大学学員会大分支部
tagtag
0
110
20分で分かる Human-in-the-Loop 機械学習におけるアノテーションとヒューマンコンピューターインタラクションの真髄
hurutoriya
5
2.6k
(Forkwell Library #48)『詳解 インシデントレスポンス』で学び倒すブルーチーム技術
scientia
2
1.5k
眼科AIコンテスト2024_特別賞_6位Solution
pon0matsu
0
240
局所保存性・相似変換対称性を満たす機械学習モデルによる数値流体力学
yellowshippo
1
140
Analysis-Ready Cloud-Optimized Data for your community and the entire world with Pangeo-Forge
jbusecke
0
120
Iniciativas independentes de divulgação científica: o caso do Movimento #CiteMulheresNegras
taisso
0
650
2024-06-16-pydata_london
sofievl
0
570
3次元点群を利用した植物の葉の自動セグメンテーションについて
kentaitakura
2
760
The Incredible Machine: Developer Productivity and the Impact of AI
tomzimmermann
0
450
Featured
See All Featured
The Cost Of JavaScript in 2023
addyosmani
46
7.2k
Designing on Purpose - Digital PM Summit 2013
jponch
116
7.1k
Fight the Zombie Pattern Library - RWD Summit 2016
marcelosomers
232
17k
Faster Mobile Websites
deanohume
305
30k
Visualizing Your Data: Incorporating Mongo into Loggly Infrastructure
mongodb
44
9.4k
Distributed Sagas: A Protocol for Coordinating Microservices
caitiem20
330
21k
Designing Dashboards & Data Visualisations in Web Apps
destraynor
230
52k
10 Git Anti Patterns You Should be Aware of
lemiorhan
PRO
656
59k
実際に使うSQLの書き方 徹底解説 / pgcon21j-tutorial
soudai
172
50k
Scaling GitHub
holman
459
140k
The Illustrated Children's Guide to Kubernetes
chrisshort
48
49k
Responsive Adventures: Dirty Tricks From The Dark Corners of Front-End
smashingmag
251
21k
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