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
180
不変量
(若手)エンジニアもくもく会 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.9k
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.3k
あなたのお家に眠るラズパイを救出したい
mascii
4
3k
Other Decks in Science
See All in Science
Symfony Console Facelift
chalasr
2
450
Transport information Geometry: Current and Future II
lwc2017
0
150
アナログ計算機『計算尺』を愛でる Midosuji Tech #4/Analog Computing Device Slide Rule now and then
quiver
1
180
データベース06: SQL (3/3) 副問い合わせ
trycycle
PRO
1
540
A Guide to Academic Writing Using Generative AI - A Workshop
ks91
PRO
0
110
データベース01: データベースを使わない世界
trycycle
PRO
1
650
機械学習 - K近傍法 & 機械学習のお作法
trycycle
PRO
0
1.1k
01_篠原弘道_SIPガバニングボード座長_ポスコロSIPへの期待.pdf
sip3ristex
0
530
機械学習 - 授業概要
trycycle
PRO
0
190
02_西村訓弘_プログラムディレクター_人口減少を機にひらく未来社会.pdf
sip3ristex
0
480
統計学入門講座 第1回スライド
techmathproject
0
340
機械学習 - ニューラルネットワーク入門
trycycle
PRO
0
790
Featured
See All Featured
RailsConf & Balkan Ruby 2019: The Past, Present, and Future of Rails at GitHub
eileencodes
138
34k
A better future with KSS
kneath
239
17k
The Web Performance Landscape in 2024 [PerfNow 2024]
tammyeverts
8
670
I Don’t Have Time: Getting Over the Fear to Launch Your Podcast
jcasabona
32
2.3k
Helping Users Find Their Own Way: Creating Modern Search Experiences
danielanewman
29
2.7k
Scaling GitHub
holman
459
140k
Music & Morning Musume
bryan
46
6.6k
Reflections from 52 weeks, 52 projects
jeffersonlam
351
20k
Exploring the Power of Turbo Streams & Action Cable | RailsConf2023
kevinliebholz
34
5.9k
GitHub's CSS Performance
jonrohan
1031
460k
How STYLIGHT went responsive
nonsquared
100
5.6k
How GitHub (no longer) Works
holman
314
140k
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