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
150
不変量
(若手)エンジニアもくもく会 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
970
Pros and Cons で考える Vue 2 Composition API
mascii
4
1.1k
Joy-ConをJavaScriptでプレゼンリモコンにした話
mascii
0
530
TypeScript で Optional Chaining を使ってみた
mascii
1
710
Vue.jsでCSS Modulesを使ってみた
mascii
0
140
Nuxt.js+Firebaseで個人サービスを作るまで
mascii
1
2.3k
JavaScriptのバージョンの話
mascii
1
2.2k
あなたのお家に眠るラズパイを救出したい
mascii
4
3k
Other Decks in Science
See All in Science
Cross-Media Information Spaces and Architectures (CISA)
signer
PRO
3
31k
学術講演会中央大学学員会大分支部
tagtag
0
130
The thin line between reconstruction, classification, and hallucination in brain decoding
ykamit
1
1.3k
山形とさくらんぼに関するレクチャー(YG-900)
07jp27
1
280
構造設計のための3D生成AI-最新の取り組みと今後の展開-
kojinishiguchi
0
990
Explanatory material
yuki1986
0
130
WCS-LA-2024
lcolladotor
0
200
05_山中真也_室蘭工業大学大学院工学研究科教授_だてプロの挑戦.pdf
sip3ristex
0
250
サメのはなし / How Sharks are born
naospon
0
2.5k
論文紹介: PEFA: Parameter-Free Adapters for Large-scale Embedding-based Retrieval Models (WSDM 2024)
ynakano
0
230
Visual Analytics for R&D Intelligence @Funding the Commons & DeSci Tokyo 2024
hayataka88
0
150
03_草原和博_広島大学大学院人間社会科学研究科教授_デジタル_シティズンシップシティで_新たな_学び__をつくる.pdf
sip3ristex
0
240
Featured
See All Featured
Creating an realtime collaboration tool: Agile Flush - .NET Oxford
marcduiker
28
2k
How to Create Impact in a Changing Tech Landscape [PerfNow 2023]
tammyeverts
50
2.4k
RailsConf 2023
tenderlove
29
1k
Git: the NoSQL Database
bkeepers
PRO
429
65k
Speed Design
sergeychernyshev
28
860
The Pragmatic Product Professional
lauravandoore
33
6.5k
The Invisible Side of Design
smashingmag
299
50k
Building an army of robots
kneath
304
45k
Chrome DevTools: State of the Union 2024 - Debugging React & Beyond
addyosmani
4
470
Producing Creativity
orderedlist
PRO
344
40k
BBQ
matthewcrist
88
9.5k
The Language of Interfaces
destraynor
156
24k
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