Profile cover photo
Profile photo
Shimizu Nobutaka
8 followers
8 followers
About
Posts

Post has attachment
グラフの Spanner と Erdős Girth Conjecture
1. Introduction 離散アルゴリズム・理論計算機科学の界隈で数年前からホットな話題がいくつかありますが, 今回はそのうちの一つである Spanner を取り上げたいと思います. Spannerと聞くとなんとなく「spanning tree」などを思い浮かべるかもしれませんが, 雰囲気は似ています. グラフ $G=(V,E)$ の 全域 部分グラフ $H=(V,F)$ (ただし $F\subseteq E$) が $G$の $(\alpha, \beta)$-spannerであるとは, 任意の頂点ペ...
Add a comment...

Post has attachment
単著論文がSODAに通りました
The Diameter of Dense Random Regular Graphs という単著の論文がSODA18に採択されました. SODAは Symposium on Discrete Algorithms という理論的な国際会議で, コンピュータ科学において「トップカンファレンス」と呼ばれるもので, なかなか通すのが難しいと言われています. 今年のSODA17には通した日本人が1,2人しかいなかったと記憶しています. 今年はバルセロナでの開催でしたが, 来年のSODAはニューオリンズです. 他にもF...
Add a comment...

Post has attachment
三角形・四角形を含まないグラフ(極値グラフ理論)
0. 概要 グラフ理論の中に「極値グラフ理論 (extremal graph theory)」と呼ばれる分野があります. 極値グラフ理論では, 「与えられた性質$\mathcal{P}$を満たすグラフのうち, 最大辺数を求める」ことを考えます. 極値グラフ理論で最も有名な結果はおそらくTuranの定理でしょう. これは, 性質$\mathcal{P}$を「サイズ$r$の完全グラフ$K_r$を含まない」としたとき, 辺数が最大のグラフは$r-1$部完全グラフであるという結果です. 気持ちとしては, 「どれほどの...
Add a comment...

Post has attachment
強正則グラフのスペクトル解析と未解決問題への応用
0. 背景 グラフ理論とは文字通り, グラフについて解析する分野です. グラフ理論のモチベーションとしては, 「最小全域木」「最大マッチング」「最大フロー」などのアルゴリズムを考える際に対象となるオブジェクト(この例で言えば全域木, マッチング, フロー)に対する「良い」特徴付けや性質(例えばHallの結婚定理, グラフマトロイドの基, 交互増加道, 残余ネットワークに関するものなど)を与えるという, アルゴリズム上のモチベーションが最も大きいんじゃないかと思います. しかしそれとは別に純粋数学寄りな一面もあ...
Add a comment...

Post has attachment
高速な全点対最短経路アルゴリズム
1. 全点対最短経路問題の計算量の外観  グラフ $G$ が与えられたときに 全点対最短経路 ( APSP : all pair shortest paths)を求めたいときがあります. そんなときはほとんどの人がワーシャル・フロイド法または各点ダイクストラなどを使うかと思います. しかしこれらのアルゴリズムは頂点数 $n$ に対して最悪 $O(n^3)$ 時間かかってしまうので, $n=1000$くらいでもちょっと厳しい感じがあります.  実は辺重み付きグラフのAPSPの計算量には多くの歴史があり、ワーシャ...
Add a comment...

Post has attachment
問題を解きやすいグラフクラスとその拡張
NP-困難な問題はP≠NPの仮定のもとでは多項式時間で解けません. しかしNP-困難な問題を解きたいという場面が少なからずあります. そのようなときには近似を考えたり入力インスタンスのクラスを制限する、ということを考えることが多々あります. 今回のトピックはグラフに対するNP-困難問題に対し, 「グラフクラスを制限することによって多項式時間で解く」アプローチについて広く浅く列挙します. - 樹状幅を制限したグラフクラス (bounded tree-width)  樹状幅とはもともと, Robertson・Se...
Add a comment...

Post has attachment
問題を解きやすいグラフクラスとその拡張
NP-困難な問題はP≠NPの仮定のもとでは多項式時間で解けません. しかしNP-困難な問題を解きたいという場面が少なからずあります. そのようなときには近似を考えたり入力インスタンスのクラスを制限する、ということを考えることが多々あります. 今回のトピックはグラフに対するNP-困難問題に対し, 「グラフクラスを制限することによって多項式時間で解く」アプローチについて広く浅く列挙します. - 樹状幅を制限したグラフクラス (bounded tree-width)  樹状幅とはもともと, Robertson・Se...
Add a comment...

Post has attachment
グラフが平面的であることの必要十分条件一覧
グラフ$G$を考える. 単射 $\phi:\,V\to\mathbb{R}^2$ 及びジョルダン曲線の族 $(J_e)_{e\in E}$ が存在し, 次の性質を満たすとき, $G$ は平面的であると定義します. 特に$G$が平面的グラフであるとき, 組 $(\phi,(J_e)_{e\in E})$を$G$の埋め込みと呼びます. 性質: $G$ の各辺 $e=\{u,v\}\in E$に対し, $J_e$ は 点 $\phi(u)$ と点 $\phi(v)$ を結ぶ. $J_e\backslash \{\p...
Add a comment...

Post has attachment
(計算が)ヤバイ級数
は有名です(前者はバーゼル問題で後者は部分分数分解で計算できます)。それでは はどうなるのでしょうか?? 収束するのは明らかです。計算してみましょう。 (厳密な議論が欠けている箇所が幾つかあるので注意してください) 級数をグッと睨むと、 と変形出来そうな気がします。ここでおもむろに wikipedia を参照すると と書けるらしいので($B_k$はベルヌーイ数)、元の級数は となります。ここでおもむろに wikipedia を参照すると、 という双曲線関数の謎テイラー展開(ローラン展開)が得られるので、収束半...
(計算が)ヤバイ級数
(計算が)ヤバイ級数
lealgorithm.blogspot.com
Add a comment...

Post has attachment
古典的確率論から測度論的確率論へ (条件付き期待値)
0. 概要 条件付き確率は確率論における重要な概念あり, マルチンゲールを定義するために不可欠です. 従って測度論的確率論を勉強していくと必ずこの概念に出会いますが, その理解は非常に難解(気持ちが分かりにくい)で, 一つの大きな壁であるといえます. 本記事は 測度論的確率論を勉強してみたけど条件付き期待値のキモチがいまいち分からない. なんとなく言葉は知ってるけどちゃんとした定義はよく知らない. という人向けに, 直感的な説明とちゃんとした定義を織り交ぜて条件付き期待値について解説します. 本記事は測度論的...
Add a comment...
Wait while more posts are being loaded