Ｑ：これは何の構造を表しているでしょう？ グラフ理論 上の構造のように、頂点（ノードともいいます）の集まりと、２つの頂点をつなぐ辺（エッジともいいます）の集まりでできたもののことを「グラフ」あるいは「ネットワーク」と呼び*1、このような構造を研究する分野こそが「グラフ理論（Graph theory）」です。今回はそんなグラフを使うと、身近なものの新たな側面が見えてくる話。 （余談ですが「グラフ」という用語は、数学だと関数のグラフとか円グラフみたいなやつもあって検索精度が悪いです。グラフ理論に関してわからないことがあった場合に「グラフ ○○」や「グラフ理論 ○○」とググるよりも、「ネットワーク ○○」とググったほうが得たい情報にリーチしやすいというライフハックが知られています） さて、冒頭のグラフです。グラフ理論の知識なんかひとつもなくても、このグラフから読み取れることはいくつもあります。例
はてなグループの終了日を2020年1月31日(金)に決定しました 以下のエントリの通り、今年末を目処にはてなグループを終了予定である旨をお知らせしておりました。 2019年末を目処に、はてなグループの提供を終了する予定です - はてなグループ日記 このたび、正式に終了日を決定いたしましたので、以下の通りご確認ください。 終了日: 2020年1月31日(金) エクスポート希望申請期限:2020年1月31日(金) 終了日以降は、はてなグループの閲覧および投稿は行えません。日記のエクスポートが必要な方は以下の記事にしたがって手続きをしてください。 はてなグループに投稿された日記データのエクスポートについて - はてなグループ日記 ご利用のみなさまにはご迷惑をおかけいたしますが、どうぞよろしくお願いいたします。 2020-06-25 追記 はてなグループ日記のエクスポートデータは2020年2月28
http://www.math.pitt.edu/~thales/flyspeck/index.html いわゆる球の最密充填率に関するKeplerの予想(1998年ごろ解決)のformal proofを与えようというプロジェクト。定理証明系HOLを使ってるらしいので、勉強してみようかなー http://www.neubert.net/FSOIntro.html オーダーNのソーティングアルゴリズム。抽象的な理論ばっか勉強してたので、リハビリ代わりにSchemeで書いてみようと思ったけど、原理がよく分からない･･･。論文(?)読みづらいし。 まず、全体を大雑把な大きさ(=key value)でグループに分けてグループをソートして(partial-sort)、更に、そうやって、分けた各グループを再帰的にソートして(要素数が十分小さいときは、挿入ソートを使うのは定石通り)、最後にくっつけるとい
文字「L」自体には特に意味が無い。プレースホルダーつうか変数つうか。適当な有限個の代数（広い意味の「代数」！）の集合上を走る変数がL。代数系の集合は {I, F1, F2, N, Z} あたりか。 I または I -- 自明なモノイド F1 または F1 -- 自明な零付きモノイド、通称一元体 F2 または F2 -- 二元体 B または B -- ブール半環 N または N -- 自然数半環 Z または Z -- 整数環 これらの代数を便宜的にL代数と呼ぶ。L代数上の加群、特に自由生成加群により既存の圏（主に集合圏の部分圏）を豊饒化するシナリオ。そのために事前にいくつかの概念と練習が必要。 自由構成 自由群が典型だろうが、自由モノイドのほうがわかりやすい。自由モノイドの要素は「語、文字列、列（シーケンス）、文、リスト」などと呼ばれる。自由モノイド構成は関手になる。モナドにもなる。 自由ベ
もともとの（かなり狭義の）フロイド／ウォーシャル法では、無向グラフ上の最短距離行列や最短経路を求める。 有向グラフにして、距離を非負値コストにしてもたいして事情はかわらない。[0, ∞] に min-plusをいれた加法的ベキ等半環を係数域とする行列計算になる。 Aのクリーネスター級数の打ち切り多項式を A[n] と書くことにする。A* = A[∞] 。フロイド／ウォーシャルのアルゴリズムとしてのキモは、累乗の計算を 2, 4, 8, 16 と2のベキで行うので速いことだろう。2のベキで済む根拠は次のこと。 An+1 = An となるようなnがあるとき、Aはベキ安定とでも呼ぶ（なんか用語があるのか？）。グラフの直達距離行列（あるいはコスト行列）Aはベキ安定である。 加法的ベキ等半環を係数とする行列では、A[n]×A[n] = A[2n] という公式が成立する。 最短経路（または最小コスト経
[追記] http://d.hatena.ne.jp/m-hiyama-memo/20110713/1310515189 とだぶっていた。[/追記] もともとの（かなり狭義の）フロイド／ウォーシャル法では、無向グラフ上の最短距離行列や最短経路を求める。 有向グラフにして、距離を非負値コストにしてもたいして事情はかわらない。[0, ∞] に min-plusをいれた加法的ベキ等半環が係数域とする行列計算になる。 Aのクリーネスター級数の打ち切り多項式を A[n] と書くことにする。A* = A[∞] 。フロイド／ウォーシャルのアルゴリズムとしてのキモは、累乗の計算を 2, 4, 8, 16 と2のベキで行うので速いことだろう。2のベキで済む根拠は次のこと。 An+1 = An となるようなnがあるとき、Aはベキ安定とでも呼ぶ（なんか用語があるのか？）。グラフの直達距離行列（あるいはコスト行列
17:19 08/11/27 TopCoder Code Jam の練習に……と思ってしばらく前から TopCoder のSRMに参加してたのですが、 せっかくなので cafelier@SRM に記録をつけることにしました。 どういう試行錯誤をしながら提出した時のコードにいたったのかを、 できるだけ詳細にメモろうと思っています。 426以前のは記憶から掘り起こして書いたのでちょい大ざっぱですが。 これまで何回かここで書いたような整然とした考え方を本当に自分がしているかいうと、 してないよなー、と薄々思ってしまっているので、じゃあどういう風にやっているんだろうかと。 自分のふり見て我がふり直す。 20:26 08/11/24 論文 PLAN-X 2009 通ったみたいです。ばんざい。 ただでさえD論まったく間に合う気がしないのに、camera ready版なんて作ってる時間が… オートマトン
The chapter links below will let you view the main text of the book. More features – index, navigational links, searchability – are included with the book's eBook edition. This comes in two formats: as the Standard eBook in freely installable PDF, which is available only here at a 60% discount off the Springer price, and in the book's iOS app. The full Professional edition costs the same as the pr
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く