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
160
不変量
(若手)エンジニアもくもく会 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
980
Pros and Cons で考える Vue 2 Composition API
mascii
4
1.1k
Joy-ConをJavaScriptでプレゼンリモコンにした話
mascii
0
540
TypeScript で Optional Chaining を使ってみた
mascii
1
710
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
白金鉱業Meetup Vol.15 DMLによる条件付処置効果の推定_sotaroIZUMI_20240919
brainpadpr
2
750
حبوب الاجهاض للبيع في الامارات - 00971547952044 - اتصل واتساب
cyt_gcc
0
110
01_篠原弘道_SIPガバニングボード座長_ポスコロSIPへの期待.pdf
sip3ristex
0
330
ガウス過程回帰とベイズ最適化
nearme_tech
PRO
1
300
観察研究における因果推論
nearme_tech
PRO
1
210
多次元展開法を用いた 多値バイクラスタリング モデルの提案
kosugitti
0
290
いまAI組織が求める企画開発エンジニアとは?
roadroller
2
1.5k
点群ライブラリPDALをGoogleColabにて実行する方法の紹介
kentaitakura
1
150
All-in-One Bioinformatics Platform Realized with Snowflake ~ From In Silico Drug Discovery, Disease Variant Analysis, to Single-Cell RNA-seq
ktatsuya
0
360
LIMEを用いた判断根拠の可視化
kentaitakura
0
500
Quelles valorisations des logiciels vers le monde socio-économique dans un contexte de Science Ouverte ?
bluehats
1
270
インフラだけではない MLOps の話 @事例でわかるMLOps 機械学習の成果をスケールさせる処方箋 発売記念
icoxfog417
PRO
2
770
Featured
See All Featured
Building Flexible Design Systems
yeseniaperezcruz
329
38k
The Illustrated Children's Guide to Kubernetes
chrisshort
48
49k
How to train your dragon (web standard)
notwaldorf
90
6k
CSS Pre-Processors: Stylus, Less & Sass
bermonpainter
357
30k
Sharpening the Axe: The Primacy of Toolmaking
bcantrill
41
2.2k
Typedesign – Prime Four
hannesfritz
41
2.6k
Design and Strategy: How to Deal with People Who Don’t "Get" Design
morganepeng
129
19k
Practical Tips for Bootstrapping Information Extraction Pipelines
honnibal
PRO
19
1.1k
Creating an realtime collaboration tool: Agile Flush - .NET Oxford
marcduiker
30
2k
How to Ace a Technical Interview
jacobian
276
23k
Put a Button on it: Removing Barriers to Going Fast.
kastner
60
3.8k
Optimising Largest Contentful Paint
csswizardry
36
3.2k
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