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
190
不変量
(若手)エンジニアもくもく会 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
560
TypeScript で Optional Chaining を使ってみた
mascii
1
740
Vue.jsでCSS Modulesを使ってみた
mascii
0
140
Nuxt.js+Firebaseで個人サービスを作るまで
mascii
1
2.4k
JavaScriptのバージョンの話
mascii
1
2.3k
あなたのお家に眠るラズパイを救出したい
mascii
4
3.1k
Other Decks in Science
See All in Science
NASの容量不足のお悩み解決!災害対策も兼ねた「Wasabi Cloud NAS」はここがスゴイ
climbteam
0
110
Gemini Prompt Engineering: Practical Techniques for Tangible AI Outcomes
mfonobong
2
150
地表面抽出の方法であるSMRFについて紹介
kentaitakura
1
840
AIに仕事を奪われる 最初の医師たちへ
ikora128
0
920
モンテカルロDCF法による事業価値の算出(モンテカルロ法とベイズモデリング) / Business Valuation Using Monte Carlo DCF Method (Monte Carlo Simulation and Bayesian Modeling)
ikuma_w
0
240
データベース02: データベースの概念
trycycle
PRO
2
890
科学で迫る勝敗の法則(電気学会・SICE若手セミナー講演 2024年12月) / The principle of victory discovered by science (Lecture for young academists in IEEJ-SICE))
konakalab
0
120
mathematics of indirect reciprocity
yohm
1
170
My Favourite Book in 2024: Get Rid of Your Japanese Accent
lagenorhynque
1
110
[Paper Introduction] From Bytes to Ideas:Language Modeling with Autoregressive U-Nets
haruumiomoto
0
120
ド文系だった私が、 KaggleのNCAAコンペでソロ金取れるまで
wakamatsu_takumu
2
1.2k
ttl2html (RDF/Turtle to HTML)
masao
0
110
Featured
See All Featured
Balancing Empowerment & Direction
lara
2
590
VelocityConf: Rendering Performance Case Studies
addyosmani
332
24k
Cheating the UX When There Is Nothing More to Optimize - PixelPioneers
stephaniewalter
283
13k
個人開発の失敗を避けるイケてる考え方 / tips for indie hackers
panda_program
110
20k
Producing Creativity
orderedlist
PRO
347
40k
Measuring & Analyzing Core Web Vitals
bluesmoon
9
570
A Tale of Four Properties
chriscoyier
160
23k
RailsConf 2023
tenderlove
30
1.2k
How to train your dragon (web standard)
notwaldorf
96
6.2k
How To Stay Up To Date on Web Technology
chriscoyier
790
250k
How to Ace a Technical Interview
jacobian
279
23k
We Have a Design System, Now What?
morganepeng
53
7.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