実践・最強最速のアルゴリズム勉強会 第一回 講義資料(ワークスアプリケーションズ & AtCoder)Similar to 実践・最強最速のアルゴリズム勉強会 第一回 講義資料(ワークスアプリケーションズ & AtCoder) (20)
ピックの定理 - Wikipedia
頂点が全て格子点上にある多角形 ピックの定理（-ていり、Pick's theorem）は等間隔に点が存在する平面上にある多角形の面積を求める公式である。この場合の多角形の頂点は全て右図のように、最も近い点同士の間隔を1とする正方格子点（等間隔に配置されている点）上にあり、内部に穴は開いていないものとする。多角形の内部にある格子点の個数を i、辺上にある格子点の個数を b とするとこの種の多角形の面積 S は以下の式で求められる。 例えば図の六角形なら内部にある点が i = 39 個、辺上にある点が b = 14 個なので S = 39 + 14/2 − 1 = 45 と簡単に計算できる。 この定理は 1899 年に ゲオルグ・アレクサンダー・ピックによって初めて示され、エルハート多項式により三次元以上に拡張して一般化することができる。 同公式はまた、多面体上の図形に対して一般化することもで
Random Forestで計算できる特徴量の重要度 - なにメモ
(pixabay.comより) １．背景とか Random Forest[1]とは、ランダムさがもつ利点を活用し、大量に作った決定木を効率よく学習させるという機械学習手法の一種です。SVMなどの既存の手法に比べて、特徴量の重要度が学習とともに計算できること、学習が早いこと、過学習が起きにくいこと（追記注釈１）などの利点が挙げられます。Kinectの姿勢推定に使われているらしいです。 最近、Random Forestをカジュアルに使う例が多く（特にうちの研究室）、一部パラメータやら出力やらがわからない人も多いと思います。使い方はTJOさんの資料[2]を読んでもらえれば理解できると思うし、詳細は波部先生の資料[3]をよんでもらえればわかると思います。 それで、いろいろな日本語の資料をいくら読んでも、Random Forestがもつ特徴の１つである、特徴量の重要度の詳細に関してはほとんどノータッ
高校生がスーパーコンピュータを使って5×5魔方陣の全解を求めることに成功 | 筑波大学 計算科学研究センター
概要 筑波大学計算科学研究センターは、全国共同利用施設として、一般公募による「学際共同利用プログラム」※1を実施しています。平成25年度に、茨城県立並木中等教育学校4年次（高校1年）の杉﨑行優（すぎざき・ゆきまさ）君の申請が採択されました。杉﨑君は筑波大学計算科学研究センターの朴泰祐教授と共同研究を進めた結果、スーパーコンピュータ「T2K-Tsukuba」※2を使った並列計算により、5×5の魔方陣の全ての解を求めることに成功しました。 魔方陣とは、正方形のマス目に、縦・横・斜めの合計が同じになるよう数字を置いたものです。5×5の魔方陣の全解は2億7530万5224通りあることがすでにわかっています。杉﨑君は「枝刈り法」を改良した求解アルゴリズムを考案し、スパコンに並列計算させるためのプログラムを開発しました。朴教授は、並列データの収集や並列化に関する詳細なアドバイスを行いました。並列計算
ビットコインの応用で、電子書籍を譲渡可能にするアルゴリズム
サトウヒロシ🐰 @satobtc (1)今日は、ビットコインの経済的側面ではなく、技術的側面から可能になる未来像について、連続ツイートします。 ビットコインのP2Pネットワークは、あるデジタルデータ（コインでは残高＝お金としている）の所有権を中央の認証機関なしに移転することができるというものです。 2014-02-24 15:42:36 サトウヒロシ🐰 @satobtc (2)これは、計算機科学的にいうとビザンチン将軍問題というもので、だれか管理者がいなくても分散型のコンピュータはお互いに故障や正しいデータを識別できるか、といったような問題です。これに対する実用的なはじめての回答がビットコイン的な仕組みです。 2014-02-24 15:43:49
直積量子化(Product Quantization)を用いた近似最近傍探索についての簡単な解説
"aka motsu-nabe" by chatani 概要 冬の寒さも一段と厳しくなってまいりました。おでんや鍋が恋しくなる季節です。 さて、最近ようやっと一仕事が終わりまして、長ったらしい記事が書けるようになりました。ですので、今回は2011年にTPAMIで発表された、近似最近傍探索についての論文『Product quantization for nearest neighbor search』について簡単に紹介したいと思います。 この論文は2011年に発表された、最近傍探索アルゴリズムの決定打です。シンプルな理論でありながら既存手法を打ち破るほどの強力な性能を有し、速度も非常に高速、かつ省メモリなのでスマートフォンに載せ、リアルタイムで動作させることも可能です。 以前この手法はCV勉強会@関東で紹介されたらしいのですが、具体的に紹介しているページは(最近すぎるので当たり前ですが)現在
Cluster Analysis 徳山研究室M2 鈴木 晶子 発表内容 ・ クラスタリングとは ・ 大量のデータを操作するために、クラスタリン グメソッドに要求されること ・ クラスタリング技術の紹介 ‐ 分割
Cluster Analysis 徳山研究室M2 鈴木 晶子 発表内容 ・ クラスタリングとは ・ 大量のデータを操作するために、クラスタリン グメソッドに要求されること ・ クラスタリング技術の紹介 ‐ 分割法、階層的手法、密度に基づく方法、 格子に基づく方法、モデルに基づく方法 ・ Outlier detection 1 クラスタリングとは ・ クラスタリング(Clustering) ‐ データをクラス(class)またはクラスタ (cluster)にグループ化すること ‐ 同じクラスタに属するオブジェクトを比較し た時には、互いに高い類似性をもつ ‐ 異なるクラスタに属するオブジェクトを比較 した時には、高い相違性をもつ ‐ 非類似度(dissimilarity)は、オブジェクトを 記述する属性値に基づいて評価される クラスタリングの応用(1/2) ・ クラスタリングは多く
Zobrist hashing - Wikipedia
Zobrist hashing (also referred to as Zobrist keys or Zobrist signatures [1]) is a hash function construction used in computer programs that play abstract board games, such as chess and Go, to implement transposition tables, a special kind of hash table that is indexed by a board position and used to avoid analyzing the same position more than once. Zobrist hashing is named for its inventor, Albert
Finding the Majority Item in a Stream
Going through old CACM issues I discovered a paper (PDF) on stream processing. A common problem in this field is to find frequent items in a data stream when you only get one pass through the data and you need answers in real time. This is interesting in situations where you don't have enough memory to store counters for each distinct item you see in the stream. One example is keeping track of the
mod p の逆元
おめ @omeometo @ut_math 特に名前とかはなさそうですがrng-hos法とかrng-hos-ome法とか呼ぼうとしてたこともありました たとえば23^-1 mod 97を計算するなら23*4=-5 5*19=-2 2*49=1より23^-1=(-1)^2*4*19*49=38とやるだけです 2012-01-09 21:45:44
「大きなナップサック」問題解説＆最終成績発表～神級到達者30名！ #アルゴリズム｜CodeIQ MAGAZINE
出題者Ozyさんによる「大きなナップサック」問題の解説記事です。 最適解を導くためのアルゴリズムについてわかりやすい図解付きで説明してくれています。 そして、神級到達者はなんと30名！ニックネームを公開していますよ！ by CodeIQ運営事務局 はじめに 出題者のOzyです。大きなナップサック問題解説です。 今回解説するのは、ナップサック問題の中でも“単一制約の01ナップサック問題”と呼ばれる種類のものです。ちょっと長いですから、今後は単に“ナップサック問題”と表記します。ナップサックに入れる品物には、値段と重量の2要素があり、重量が“制約”に相当します。また、品物1つひとつについては、ナップサックの中に、入れる／入れないという2つの状態がありますので、これは0と1で表現できることから、“01”と呼ばれています。 大きめのナップサック問題を解く場合に用いられる手法として有名なものは、動的
高速素因数分解 - メモ用紙2.0 | 日記 - 2013-10
2013-10-27 まどか☆マギカ 劇場版まどか☆マギカ観てきました。感想。 とても良い話だった。 色紙は杏さやでした。杏子かわいい！ 2013-10-25 研究 前回の記事にツッコミが入ったので更新しました。 なんかやりたいことは溜まってるんですが、研究してPOJ解いてアニメ観ると1日が終わっているのでなかなか進捗のない1週間でした。 まあ、研究している分だけ良いとも言いますが。 でも今やってる作業は、自分の研究に関わってくるかというと半々くらいのとこなので、手放しで喜べない感じもします。楽しいけど。 2013-10-17 高速素因数分解 知ってしまえば当たり前の話ですが、意外と蟻本にも載っていない話なので。 しばらく前に、Project Eulerの問題で素因数分解をする必要に迫られました。 素因数分解をするには、当然ながら素数を求めなくてはいけません。 これはエラトステネスの篩など
Deflate (gzip) のアルゴリズムを視覚化してみた
のような感じにエンコードされることが分かります。 自分の好きなデータで試すことができて便利！という話でした。 PS. 以下は実行結果です。 % make % gzip < alice.txt > alice.txt.gz % ./puff -10 alice.txt.gz puff() succeeded uncompressing 1328 bytes 8 compressed bytes unused inpos=406,inbits=224,outpos=0,outbytes=45 41 6c 69 63 65 20 77 61 73 20 62 65 67 69 6e 6e 69 6e 67 20 74 6f 20 67 65 74 20 76 65 72 79 20 74 69 72 65 64 20 6f 66 20 73 69 74 74 A l i c e w a s b
株式会社NTTデータ数理システム
概要 数理最適化とは 汎用数理最適化パッケージ「Nuorium Optimizer」は、“データ”と“やり方（ルール）”がわかっていながら、 解決策が導き出せない現実の問題に対し、最適解を提供するツールです。 最適化ソリューションは様々な分野で広く利用されています。 数理計画法と呼ばれる様々な解法（アルゴリズム）を駆使して現実の問題を解決するというアプローチです。 数理最適化とは？最適化による効果や導入プロセスを紹介 主な特徴 数理最適化問題を解く際にモデルとなる数式をコンピューターに入力することは、意外に骨の折れる作業です。 Nuorium Optimizer には C++ をベースとしたモデリング言語 C++SIMPLE、Python をベースとしたモデリング言語 PySIMPLE、 R をベースとしたモデリング言語 RSIMPLE が付属しています。 これらのモデリング言語を用いると
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
実践・最強最速のアルゴリズム勉強会
Amazon.com: Combinatorial Optimization (Algorithms and Combinatorics, 24): Schrijver, Alexander: Books
信号処理 | ぼくのあたまのしくみ
Wikispaces
機械学習の Python との出会い — 機械学習の Python との出会い
recursion-drill/drill/6.md at main · kazu-yamamoto/recursion-drill
