乱択データ構造の最新事情 －MinHash と HyperLogLog の最近の進歩－MinHash, b-bit MinHash, HyperLogLog, Odd Sketch, HIP Estimator の解説です．
アルゴリズムパズル
大学で計算機科学を教える著者が、「パズルを解くことで、アルゴリズム的思考を鍛える」というコンセプトに基づいて、古今東西150の「アルゴリズム的」な数学パズルを収録。優れたアルゴリズム設計戦略と分析テクニックを通して、アルゴリズム的思考と柔軟な発想を育てます。また、近年では、入社試験にパズル的な難問を出す企業も増えており、その対策としても役立つ一冊です。 質問形式の序文 謝辞 パズル一覧 チュートリアルのパズル 本編のパズル 墓碑銘パズル 第1章 チュートリアル 一般的なアルゴリズム設計戦略 魔方陣（Magic Square） nクイーン問題（The n-Queens Problem） 有名人の問題（Celebrity Problem） 数当てゲーム（Number Guessing）（別名20の扉（Twenty Questions）） トロミノ・パズル（Tromino Puzzle） アナグ
BDD/ZDDを基盤とする 離散構造と演算処理系の最近の展開 Recent Topics on Discrete Structures and Algebraic Operations Based on BDDs/ZDDs 湊 真一 Shin-ichi MINATO アブストラクト 二分決定グラフ（BDD: Binary Decision Di
BDD/ZDDを基盤とする 離散構造と演算処理系の最近の展開 Recent Topics on Discrete Structures and Algebraic Operations Based on BDDs/ZDDs 湊 真一 Shin-ichi MINATO アブストラクト 二分決定グラフ（BDD: Binary Decision Diagram）は，論理関数を効率良く表現するデータ構造の一種であ る．BDD に関する処理技法は主に VLSI 設計技術の分野で 1990 年代に発展したものであるが，近年ではデータマイニング や知識発見の分野でも効果的に活用されるようになってきている．中でも，ゼロサプレス型 BDD（ZDD: Zero-suppressed BDD）と呼ばれる BDD の変化形は，データベース解析の多くの問題で見られるような「疎な組合せの集合」を扱う場合に 特に効果
中学生にもわかるウェーブレット行列 - アスペ日記
id:echizen_tm さんの記事「ウェーブレット木の効率的で簡単な実装 "The Wavelet Matrix"」から始まったウェーブレット行列ブームから半年以上が過ぎ、すでに枯れた技術として確立されつつある感があります。 …嘘です。 日本以外ではあんまり来ていません。 理由としては、やはりアルファベット圏では単語境界が明確であるため、こちらの記事で書かれているような「キーワード分割の難易度」といったことがあまり問題にならないということがあるかもしれません。 まあ、そういうわけで局所的に来ているウェーブレット行列ですが、日本語をはじめとする単語境界のない言語圏にとっては重要なネタであると思うため、解説記事を書き直して*1みようと思います。 ウェーブレット行列でできること 主となる操作は、文字列に対する 定数時間の rank() と select()*2 です。 rank() は、「文
サービス終了のお知らせ - NAVER まとめ
サービス終了のお知らせ NAVERまとめは2020年9月30日をもちましてサービス終了いたしました。 約11年間、NAVERまとめをご利用・ご愛顧いただき誠にありがとうございました。
d.y.d.
21:42 11/09/12 一番下に追記あります。 最遅ソート 最遅ソートアルゴリズム研究会 (beyond the bogosort) http://twitter.com/#!/y_benjo/status/112915204546887680 というつぶやきを見て、最も遅いソートアルゴリズムは何だろう、ということが気になりはじめました。 もちろん Bogosort や Stooge sort や Permutation sort は遅いです。遅いんですが、これらのソートアルゴリズムは、 明らかに完全に無駄な操作を繰り返すことで時間を稼いでいる面があります。これはズルい。チートです。 ズルくなくて、しかも遅いアルゴリズムは何でしょうか。 フォーマルに 自分の疑問をきちんと定義します。 wikipedia:比較ソートの理論限界 にあるように、「比較演算の回数」に着目することで、最速のソ
高速な安定ソートアルゴリズム "TimSort" の解説 - Preferred Networks Research & Development
先日、TimSortというソートアルゴリズムが話題になりました。TimSortは、高速な安定ソートで、Python(>=2.3)やJava SE 7、およびAndroidでの標準ソートアルゴリズムとして採用されているそうです。 C++のstd::sort()よりも高速であるというベンチマーク結果1が話題になり(後にベンチマークの誤りと判明)、私もそれで存在を知りました。実際のところ、ランダムなデータに対してはクイックソート(IntroSort)ほど速くないようですが、ソートというシンプルなタスクのアルゴリズムが今もなお改良され続けていて、なおかつ人々の関心を引くというのは興味深いものです。 しかしながら、オリジナルのTimSortのコードは若干複雑で、実際のところどういうアルゴリズムなのかわかりづらいところがあると思います。そこで今回はTimSortのアルゴリズムをできるだけわかりやすく解
Timsort - Wikipedia
Timsort is a hybrid, stable sorting algorithm, derived from merge sort and insertion sort, designed to perform well on many kinds of real-world data. It was implemented by Tim Peters in 2002 for use in the Python programming language. The algorithm finds subsequences of the data that are already ordered (runs) and uses them to sort the remainder more efficiently. This is done by merging runs until
Java 7のArrays.sort(Object[])
Java 7のEarly Access版をダウンロードしました。昨日、Joshua Bloch氏にProject Coinへ彼が提案している言語仕様の変更はすでに実装されているのかと聞いたところ、まだプロトタイプされていないということでした。で、その話のついでに、ソートの話になり、Java 7にはTimSortが入っているということで、調べてみました。 従来、コレクションフレームワークのArraysクラスのsort(Object[])は、今まではマージソートで実装されていました。しかし、Java 7にはパッケージプライベート宣言されているTimSortクラス（TimSort.java）が追加されており、Arrays.sort(Object[])（と関連する他のsortメソッド）はデフォルトでTimSortクラスのsortメソッドを使用するように書き換えられています。 TimSort.jav
![Java 7のArrays.sort(Object[])](https://cdn-ak-scissors.b.st-hatena.com/image/square/9e8c09ea9460f3808b77c6e2c7f8494dd977be03/height=288;version=1;width=512/https%3A%2F%2Fblog.so-net.ne.jp%2F_common%2Fimg%2Fsonet_logo_l.png){kind=logo}
頻出典型アルゴリズムの演習問題としてよさげなやつ - kyuridenamidaのチラ裏
効率的な別解とか存在する問題もあるけど演習によさそうなやつをピックアップ。そのアルゴリズムじゃないと解けないわけではないって問題も多いので注意。(ただ演習するのには都合が良いかなと)※個人的難易度をつけてみました。とても主観的な難易度付けなので気にせず解いてみてください。深さ優先探索・Balls[☆]・Sum of Integers[☆]・The Number of Island[☆]・Block[★]幅優先探索・Mysterious Worm[★]・Cheese[★]・Seven Puzzle[★☆]・Stray Twins[★★]・Deven-Eleven[★★]・Summer of Phyonkichi[★★☆]ワーシャルフロイド法(For 全点対最短路問題)・Traveling Alone: One-way Ticket of Youth[★]・A reward for a Car
矢沢久雄の情報工学“再”入門
ITエンジニアの皆さんなら，一度は「情報工学」を学んだことがあるかもしれない。しかし，その知識をしっかり身に付けている人は少ないのではないだろうか。本連載では，プロフェッショナルの必須知識と言える情報工学の様々な理論について解説していく。 第1回 アルゴリズムと計算量---「計算量理論」を理解し，アルゴリズムを評価する 第2回 形式言語とオートマトン---「文」のルールを知り，機械に解釈させる 第3回 符号化理論---あらゆる情報を数値で扱う「符号化」理論を知る 第4回 ブール代数---論理を「1」と「0」で表す「ブール代数」を理解する 第5回 グラフ理論---要素同士のつながり方を「点」と「辺」で分析する 第6回 オペレーションズ・リサーチ(OR)---数学モデルを駆使して，経営戦略を立案する 第7回 集合論---数学の「集合論」にRDBの正体を見る 第8回 RDBの正規化理論---から
アルゴリズムの勉強のしかた - きしだのHatena
この記事で、アルゴリズムの勉強はアルゴリズムカタログを覚えることじゃないよということを書きました。 プログラムの理論とはなにか アルゴリズムの勉強というのは、スポーツで言えば腕立て伏せや走り込みみたいな基礎体力を養うようなもので、「ソートなんか実際に自分で書くことないだろう」とかいうのは「サッカーは腕つかわないのに腕立ていらないだろう」とか「野球で1kmも走ることなんかないのに長距離の走り込みいらないだろう」とか言うようなものです。 Twitterでアルゴリズムの勉強とはなにかと尋ねられて、「アルゴリズムの基本的なパターンを知って、それらの性質の分析のしかたをしって、いろいろなアルゴリズムでどのように応用されているか知って、自分が組むアルゴリズムの性質を判断できるようになることだと思います。 」と答えたのですが、じゃあ実際どういう本で勉強すればいいか、ぼくの知ってる本からまとめてみました。
常識を覆すソートアルゴリズム！その名も"sleep sort"！ - Islands in the byte stream (legacy)
TwitterのTLで知ったのだが、少し前に海外の掲示板で"sleep sort"というソートアルゴリズムが発明され、公開されたようだ。このアルゴリズムが面白かったので紹介してみる。 Genius sorting algorithm: Sleep sort 1 Name: Anonymous : 2011-01-20 12:22 諸君！オレは天才かもしれない。このソートアルゴリズムをみてくれ。こいつをどう思う？ #!/bin/bash function f() { sleep "$1" echo "$1" } while [ -n "$1" ] do f "$1" & shift done wait example usage: ./sleepsort.bash 5 3 6 3 6 3 1 4 7 2 Name: Anonymous : 2011-01-20 12:27 >>1 なん…だと
3SAT問題を多項式時間で解くアルゴリズムが発表される。P=NP証明に？ | スラド サイエンス
This is not a P=NP paper. The paper solves a problem of a related data structure in polynomial time (quartic time), then shows that it can be used to solve some cases of 3SAT. The 3 outputs the algorithm can give are "the formula is not satisfiable", "the formula is satisfiable" (and the solution is given), and "failure of classification" -- it couldn't solve the problem. The important question we
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
ウェーブレット木の世界 - Preferred Networks Research & Development
http://harthur.github.io/kittydar/
Engadget | Technology News & Reviews
サービス終了のお知らせ