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
130
不変量
(若手)エンジニアもくもく会 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
5
2.5k
WebHID API でリングコン のセンサー値を取得してみた
mascii
1
910
Pros and Cons で考える Vue 2 Composition API
mascii
4
970
Joy-ConをJavaScriptでプレゼンリモコンにした話
mascii
0
470
TypeScript で Optional Chaining を使ってみた
mascii
1
640
Vue.jsでCSS Modulesを使ってみた
mascii
0
130
Nuxt.js+Firebaseで個人サービスを作るまで
mascii
1
2.2k
JavaScriptのバージョンの話
mascii
1
2.1k
あなたのお家に眠るラズパイを救出したい
mascii
4
2.9k
Other Decks in Science
See All in Science
第4回ナレッジグラフ勉強会 Knowledge Graph Embedding
maruru0090
0
250
伊豆赤沢海洋深層水中からメラニン分解能を有する微生物の探索
eltociear
0
110
ECUACIÓN DE ESTADO DEL VIRIAL
borischicoma
0
100
プロダクト開発を通して学んだナレッジマネジメントの哲学
sonod
0
130
いまAI組織が求める企画開発エンジニアとは?
roadroller
2
1.2k
多次元展開法を用いた 多値バイクラスタリング モデルの提案
kosugitti
0
170
20分で分かる Human-in-the-Loop 機械学習におけるアノテーションとヒューマンコンピューターインタラクションの真髄
hurutoriya
4
2k
Machine Learning for Materials (Lecture 7)
aronwalsh
0
800
小杉考司(専修大学)
kosugitti
1
490
All-in-One Bioinformatics Platform Realized with Snowflake ~ From In Silico Drug Discovery, Disease Variant Analysis, to Single-Cell RNA-seq
ktatsuya
0
190
ざっと学んでみる確率過程 〜その1 : ブラウン運動〜
nearme_tech
PRO
0
290
Running llama.cpp on the CPU
ianozsvald
0
350
Featured
See All Featured
10 Git Anti Patterns You Should be Aware of
lemiorhan
653
58k
Designing Dashboards & Data Visualisations in Web Apps
destraynor
227
52k
A Philosophy of Restraint
colly
202
16k
Done Done
chrislema
180
16k
Why Our Code Smells
bkeepers
PRO
334
56k
RailsConf 2023
tenderlove
28
810
The Straight Up "How To Draw Better" Workshop
denniskardys
230
130k
Web development in the modern age
philhawksworth
205
10k
Mobile First: as difficult as doing things right
swwweet
221
8.8k
Code Review Best Practice
trishagee
62
16k
Templates, Plugins, & Blocks: Oh My! Creating the theme that thinks of everything
marktimemedia
26
2k
Designing Experiences People Love
moore
138
23k
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