情報幾何学講義 【チャンネルA】
甘利俊一先生 情報幾何学講義 （チャンネルA) 統計数理研究所 夏期大学院 の講義のうち 甘利俊一先生の担当部分を配信しました。 当分の間、録画を公開する予定です。 投影資料は http://www.ism.ac.jp/shikoin/summer-school/2013.html のリンクからダウンロード可能です。 なお、以下のうち、スマートフォンや一部のタブレットでは1のみしか視聴できません。2,3は配信時にブロードキャスターを使ったためで、これはUSTREAM側の仕様のようです。お手数ですがPC・マックからの視聴をお願いします。 【甘利先生講義１ 午前冒頭】 録画のトラブルで欠けていた最初の部分を別の録画から補充しました。配信技術未熟のため冒頭に空白が、また末尾にループして冒頭がそれぞれ少し入っておりますがご容赦ください。この冒頭部分では講師の表情をとらえることに主眼をおいた撮影をし
数え上げ問題集 ver.0 - tozangezan's diary
数え上げ問題集 数え上げの問題をある程度まとめます。といっても多すぎて面倒なので、まとまって存在するものはリンクを張ります。 また、検索の都合上「答えを1000000007で割った余りを求める」以外の形式の数え上げは見落とされがちなので、そこらへんは割り切ってください。 まとまって存在するリスト(数え上げをたくさん解きたい人用) http://codeforces.com/problemset/tags/combinatorics 数え上げばっかり集めてあります http://community.topcoder.com/tc 多すぎる上ローカルに保存してなくて調べるのが面倒なので、自分で調べてください。 参考までに、感じる難易度をTopCoder Div1の点数に換算して書いておきます。 良問には☆をいくつか付けます。 AOJ 2333 (500) ☆ AOJ 2335 (650) AO
クッキーの生産が下手な男の人は仕事も出来ない
IT企業に勤めてるせいか、昼休みに一部でブームになってる例のクッキーの話になった。 みんな結構はまってるみたいで、各々のcps(一秒間にできるクッキーの量らしい) を言い合うみたいな流れになったんだけど、驚いたのが、仕事の出来る男の人と そうでない人で全然cpsが違うってこと。なんかもう、すっごく大きい差がついてる。 私はツイッターで話題になってるのを知ってるぐらいで自分でプレイはしてなかったから、 なんでそんなに差がつくんだろうと思って色々と聞いてたら、人によってプレイの方法に 違いがあるってことに気づいた。 仕事が出来る人は、どういうルールのゲームなのかというのをちゃんと考えて戦略的に クッキーを増やすようにプレイしてるみたい。 反対に仕事が出来ない人は場当たり的に施設みたいなのをアップグレードしてるらしい。 同じゲームをプレイしてるはずなのに、cpsの大きい人と小さい人では全然見えて
PEGWiki
Hello, World! Welcome to PEGWiki! This is the informational part of the website of the Woburn C.I. Programming Enrichment Group (PEG); the functional part, our online judge, is located here. This wiki has the following aims: to contain all interesting information about our organization, including but not limited to our goals, members, upcoming events, up-to-date news, achievements, memories, and t
マルコフ連鎖モンテカルロ法を実装してみよう
"Chain Bridge, Budapest" by szeke 約2ヶ月ぶりということで、ご無沙汰しております。書きたいネタというのは結構あって書こう書こうとは思っているんですが、なにより書くとなるとあれもこれも伝えなきゃいけないみたいな思いになって、結局分量の多さから諦めてしまうというのが結構続いています。もう少し気を張らずに更新していきたいものです。 さて、最近の自分はマルコフ連鎖モンテカルロ法(Markov Chain Monte Carlo, MCMC)についておりました。何にも知らない方ににとってはよく分からないかもしれませんが、この手法はマルコフ連鎖が持つ簡明さとモンテカルロ法が持つ実用性が合わさった凄まじい手法なんです。そしてなによりとてもエレガント。 とりあえず知らない人のためにてきとーに解説しますと、与えられた適当な関数から確率変数をサンプリングするための公式です。べ
グラフ理論（Graph theory） - kanetaiの二次記憶装置
(無向)グラフの要素 要素が頂点(vertex), 点(point), 節点(node)の集合 辺(edge)と呼ばれる頂点の順序対の集合 隣接(adjacent) : 辺(u,v)が存在するとき頂点は隣接するという。 接続(incident) : が辺の端点(endpoint)であるとき、はに接続するという。 多重グラフ(multigraph) : 多重辺(multiple edges)または自己ループ(roop)を含むグラフ ※多重辺やループのない多重グラフをグラフと定義している。 部分グラフ(subgraph) : induced subgraph : 両端点がにある辺を全てが含むならば、をによって生成された(generated)部分グラフと呼ぶ。 次数(degree) 次数(degree) : に接続する辺の個数 孤立点(isolated vertex) : 次数0の頂点 の倍数
Wavelet Treeをもう一度 - 気ままなブログ
文字列本のメインであるウェーブレット木をもう一度素直に見直すことにした。 高速文字列解析の世界――データ圧縮・全文検索・テキストマイニング (確率と情報の科学) 作者: 岡野原大輔出版社/メーカー: 岩波書店発売日: 2012/12/27メディア: 単行本購入: 15人 クリック: 324回この商品を含むブログ (5件) を見る Wavelet Treeに関する著者のスライドは以下である。 http://www.slideshare.net/pfi/ss-15916040 ふらふらと論文を眺めていたら、Navarro神の「Wavelet Trees for All」というサーベイ論文が加筆されて更新されていた。内容自体はあまり変わっていないと思うが図が増えていた。以下がその論文である。 http://www.dcc.uchile.cl/~gnavarro/ps/jda13.pdf 大半の内
高速な文字列マッチング - 気ままなブログ
最近は、簡潔データ構造を中心に調べたりしていたけど、文字列マッチングを考えた場合、別のアプローチもあります。そう、grepのような逐次文字列検索ですね。以下の解説がおもしろいです。 http://www.i.kyushu-u.ac.jp/~takeda/papers/IPSJMagazineCPM.pdf CSAとかFM-Indexに隠れてしまっていますが、実はかなり強力です。特に、クエリが固定で、テキストが頻繁に変更されるようなケースでは有効です。中でも使いやすのは、Aho-Corasick法(AC法)ですね。複数のパターンを同時に検索することができます。KMPを拡張した方法です。 AC法については、日本語だと 情報検索アルゴリズム 作者: 北研二,津田和彦,獅々堀正幹出版社/メーカー: 共立出版発売日: 2002/01メディア: 単行本購入: 6人 クリック: 552回この商品を含むブ
拡張ユークリッド互除法について
「(省略) これは、a * x + b * y = 1 となる(x, y)を求める問題に他ならない。この式から明らかなようにgcd (a, b) != 1のときは、整数解(x, y)は存在しません。」
円と円の交点
半径r1 中心(x1,y1) の円と半径r2 中心(x2,y2) の円との交点。 連立方程式による解法 円の方程式は (x-x1)^2+(y-y1)^2-r1^2 = 0 …(1) (x-x2)^2+(y-y2)^2-r2^2 = 0 …(2) (1)-(2): (2 x2-2 x1)x + (2 y2 - 2 y1)y + (x1-x2)(x1+x2)+(y1-2)(y1+y2)-(r1-r2)(r1+r2) = 0 …(3) これは円と円の2つの交点を通る直線になっているので、円と直線の交点の問題に帰着できる。(3)の係数を a = 2(x2-x1) b = 2(y2-y1) c = (x1-x2)(x1+x2)+(y1-y2)(y1+y2)-(r1-r2)(r1+r2) と計算しておくとax+by+c = 0の形になる。 解法 : 直線と円の交点 JavaScript 若干計算量削減
4段階の思考スキルレベル - Chikirinの日記
将棋ソフトに関しておもしろかったのは、先日も書いた「探索」と「局面評価」という思考プロセスです。 １）探索＝とりうる選択肢を、自分の選択肢→相手の対応策（選択肢）→自分の選択肢、と深掘りしつつリストアップ ２）局面評価＝上記の過程で現れる局面を、どの程度、自分に有利か（不利か）評価する ３）その上で、自分にとって最も有利な局面につながる選択肢を選ぶ 探索とは、下記のような図＝探索木＝ツリーのイメージです。 （『人間に勝つコンピュータ将棋の作り方』より） この探索と局面評価というステップは、ビジネスや個人生活などあらゆる意思決定の場面で使われてます。 将棋のような完全情報ゲームでないため、より複雑ですが、ビジネスでは、 ・自社が値段を下げる→他社が対抗してくる→自社はどうする？・・・であったり、 ・自社が買収を提案する→第三者が価格を釣り上げる→公正取引委員会がいちゃっもんをつける→自社はど
暗記なんかで勝てたりしません - Chikirinの日記
今日は、将棋ソフトがどのように“将棋を学んできたのか”について、まとめておきます。 今から40年ほど前の 1975年頃、人工知能研究の一環として将棋ソフトの開発は始まったそうです。 その進化の流れは、ざっくり言えばこんな感じ？ １．ルールを覚えさせる ２．金言などをプログラム化する ３．探索と駒得で手を選ばせる ４．局面評価について、機械学習をさせる １の「ルールを覚えさせる」というのは、各駒の動ける場所を教え、“二歩”など反則となるルールを教えるってことです。 でも、駒の動かし方がわかるようになっただけでは勝てたりはしません。今の私と同じです。 ちなみに「反則にならない手」は合法手と呼ばれます。 次に「金言をプログラム化する」ってことが行われたみたいです。 将棋には勝ちやすくなるための格言がたくさんあります。 「玉飛接近すべからず」「二枚替えなら歩ともせよ」みたいな言葉ですが、そういうの
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
いしはた まさかず on Twitter: "おねえさん…。：“「おねえさんの問題」の最先端 -YouTube動画と世界記録-” http://t.co/2MRiipJ60M"
Numpla2
IBM Developer
一段階在庫管理（single stage inventory control）
就活分析録 Sudoku(数独)の問題自動生成アルゴリズム第2弾
WUPC2nd E問題
Sweep and prune - Wikipedia
Convex hull trick - PEGWiki