t.dvi
Purely Functional Data Structures Chris Okasaki September 1996 CMU-CS-96-177 School of Computer Science Carnegie Mellon University Pittsburgh, PA 15213 Submitted in partial fulfillment of the requirements for the degree of Doctor of Philosophy. Thesis Committee: Peter Lee, Chair Robert Harper Daniel Sleator Robert Tarjan, Princeton University Copyright c 1996 Chris Okasaki This research was sponso
de Bruijn Graph を使った de novo アセンブリの発想がすごい件 - ほくそ笑む
Velvet や ABySS などの代表的な de novo アセンブリツールでは、アルゴリズムに de Bruijn Graph というのを使っているそうです。どうやってアセンブルしているんだろう？と興味を持っていたので、元ネタの An Eulerian path approach to DNA fragment assembly を読んでみたんですが、その発想のすごさに度肝を抜かれました。せっかくなので、ここで簡単に説明してみたいと思います。 ケーニヒスベルクの橋 まずはグラフ理論の説明から。グラフ理論は、18世紀にオイラーという数学者が「ケーニヒスベルクの橋」という問題を解くために考え出したといわれています。 「ケーニヒスベルクの橋」は、次のような問題です。 18世紀の初めごろにプロイセン王国の首都であるケーニヒスベルクという大きな町があった。この町の中央には、プレーゲル川という大き
ssh/SSHプロトコル概要/メッセージとパケット - 春山征吾のWiki
春山征吾のWiki トップページページ一覧メンバー編集 × ssh/SSHプロトコル概要/メッセージとパケット 最終更新： haruyama_seigo 2014年06月24日(火) 20:32:07履歴 SSHクライアントとサーバの間のやりとりは, SSHのメッセージを利用します. ただし, SSHのメッセージをそのまま(TCPなどの)基底のトランスポート上で通信するわけではありません. パディングやMACの付与, 暗号化, 圧縮をメッセージに対して行なったパケットを実際にはやりとりします. SSHのパケットは, TCPのパケットとは異なるものです. 以下での, メッセージ, パケットという表記は, それぞれSSHのものを意味します. メッセージ メッセージの構成 メッセージは, メッセージID(byte) とメッセージ固有の情報で構成されます. メッセージID 各メッセージには, 番号
プログラム=データ=遺伝子？ Lispは無慈悲な言語の女王 - masatoi’s blog
(Lisp Advent Calendar 2013 18日目の記事) しばしばLispの特徴として「プログラムを生成するプログラムを書ける」ということが言われるわけだが、普通の人はこれを聞いてどう解釈したらよいものか悩むと思う。字面通りに受け取ると、あたかも勝手に世の中の問題を把握してそれを解決するプログラムを出力してくれる真の人工知能のようなものを想像してしまうかもしれない。しかし残念ながら、そうした所謂「強いAI」は人工知能研究における聖杯であり、いまだにSFの範疇から出るものではない。 LISPerの言う「プログラムを生成するプログラム」とは普通もっと限定された意味である。そしてそれはほとんどの場合マクロによって実現される。 evalとマクロ Lispではプログラムとデータが同じ形をしているので、それまでプログラムとして扱っていたものを突如データとみなして操作することができる。逆に
なぜBTreeがIndexに使われているのか - maru source
※この内容は個人的な考察なので、間違っている箇所もあると思います。そういう部分を見つけた際はぜひ教えて下さい。 RDBMSの検索を早くするためにIndexって使いますよね。例えばこんなテーブル CREATE TABLE user ( id INT UNSIGNED NOT NULL, name VARCHAR(255) NOT NULL, UNIQUE INDEX (id) ); idカラムにIndexを張っています。これはidでの検索を高速にするためです。ここでidカラムにIndexが貼っていない場合と比べると検索時間が大幅に変わってきてしまいます（特にレコードが多くなった時) ではなぜIndexを貼ると検索が早くなるんでしょう？？ Indexとはその名の通り索引を意味します。特定のカラムの索引を作成しておくことで検索を高速化します。 (本の最後によみがな順で単語が並べられたりしています
When Random Isn't Random Enough: Lessons from an Online Poker Exploit - Laura Diane Hamilton
When Random Isn't Random Enough: Lessons from an Online Poker Exploit Today I am going to retell a story from 1999, a story in which developers of a popular online poker platform implemented card-shuffling software with a handle of subtle but critical bugs. Image credit: David Wells on Flickr Although this story is 15 years old, the lessons it holds for algorithm developers are still relevant. It'
再帰的な無名関数 - ヒビノキロク
次の関数は再帰的な関数だ。 (define fact (lambda (n) (if (= n 0) 1 (* n (fact (- n 1)))))) この関数は内部で自分自身を呼び出しているので、普通の方法では無名関数として定義できない。 こういう場合、不動点オペレータというものを使うと以下のようにしてfactを定義することができる。（fact関数の中で直接factという名前を使っていない所がポイント） (define fact (let ((Y (lambda (F) ((lambda (s) (F (lambda (x) ((s s) x)))) (lambda (s) (F (lambda (x) ((s s) x)))))))) (Y (lambda (f) (lambda (n) (if (= n 0) 1 (* n (f (- n 1))))))))) ここで天下り的に出て
Data Structure Visualization
Currently, we have visualizations for the following data structures and algorithms: Basics Stack: Array Implementation Stack: Linked List Implementation Queues: Array Implementation Queues: Linked List Implementation Lists: Array Implementation (available in java version) Lists: Linked List Implementation (available in java version) Recursion Factorial Reversing a String N-Queens Problem Indexing
information
アルゴリズムと計算量 [教科書6.1.1] 同じ処理結果が求まるプログラムはいろいろあり得るが、本質的に違うなやり方としてどのようなものがあるのか、とそれらの計算の大変さの違いを知りたい。 そこでプログラムを抽象化してアルゴリズムというものを考える。 アルゴリズム: 問題を解くための手順で、いつか止まることが保証されているもの。 プログラムの細い違いは無視してしまう。 アルゴリズムの重要性 アルゴリズムによって性能に大きな違いがある 同じ処理結果が求まる複数のアルゴリズムがある アルゴリズムによって計算時間が桁違いに変わることがある アルゴリズムは類型化されている 全く違う問題を解くアルゴリズムが同じものになることがある 性能に関する考察・プログラミングを共通化することができる 一見簡単そうに見えて大変な問題の例 ハノイの塔のシミュレーターで試してみよ。 ルール 大きさの異なる穴のあいた円
計算量を具体的に見てみる 2009-01-06 - きしだのはてな
アルゴリズムの話では、計算量の解析がかかせません。 計算量はオーダー記法で表されますが、これは、データの入力量に対してどのくらい時間がかかるかをあらわしたものです。 こういった話はどのアルゴリズムの本にも載ってるはずですが、具体的にどのようなプログラムを書くとそのオーダーになるかという記述はあまりありません。 ということで、やってみました。 計算時間表示のための共通処理を行うクラスは、一番最後に書いてます。 O(1) 計算時間がO(1)のアルゴリズムは、処理が入力の量によらない場合です。 配列の要素のアクセスや、ハッシュテーブルによるデータ検索、連結リストへの追加削除などがこれにあたります。 コードには入力量でのループが含まれません。 public class O1 extends ViewCompFrame{ @Override void compute(int n) { proc();
)
Blowfish (cipher) - Wikipedia
Four rounds of Blowfish are susceptible to a second-order differential attack (Rijmen, 1997);[2] for a class of weak keys, 14 rounds of Blowfish can be distinguished from a pseudorandom permutation (Vaudenay, 1996). Blowfish is a symmetric-key block cipher, designed in 1993 by Bruce Schneier and included in many cipher suites and encryption products. Blowfish provides a good encryption rate in sof
計算論的神経科学と機械学習 - Qiita
Deleted articles cannot be recovered. Draft of this article would be also deleted. Are you sure you want to delete this article? @torotoki です。Machine Learning Advent Calendar 2012 7日目は、俗に言う脳科学とよばれる神経科学（neuroscience）の中でも計算論的神経科学（computational neuroscience）という分野です。学問的な入門書ではまず、脳の神経細胞の仕組みや、多々のニューロンの数理モデルを学びますが、そういったものは参考文献の良書にまかせて、計算論的神経科学とは何であるか、ということについて書きたいと思います。 計算論的神経科学とは 神経科学の目標として脳のしくみを理解するというも
Hey Judy, don't make it bad
AI & MLLearn about artificial intelligence and machine learning across the GitHub ecosystem and the wider industry. Generative AILearn how to build with generative AI. GitHub CopilotChange how you work with GitHub Copilot. LLMsEverything developers need to know about LLMs. Machine learningMachine learning tips, tricks, and best practices. How AI code generation worksExplore the capabilities and be
最近のtrieの話（xbwなど） - Preferred Networks Research & Development
ブログの更新がとまっていましたが、また少しずつ更新してきたいと思います。 今回はtrie（トライ）の最近の話をしたいと思います。 trieはキー集合を扱うためのデータ構造の一種です。例えば、単語集合からなる辞書であったり、クロールしたURL情報を扱ったり、最近だと、KVS（Key Value Store)のようにキーを介してデータを保存、読み込みをしたりと様々な場面で利用されます。 同じようにキー集合を格納するデータ構造としてハッシュを利用する方法があります。キーからハッシュ値を計算し、その場所に文字列へのポインタを格納しておくデータ構造です。ハッシュを利用した場合とtrieを利用した場合の一番の大きな違いは、trieの場合だと、ある文字列から始まるキーを全て列挙する、いわゆる接頭辞探索ができることです。例えば”te”で始まる文字列を網羅的に調べることができます。木をたどって、”te”の下
中学生にもわかるウェーブレット行列 - アスペ日記
id:echizen_tm さんの記事「ウェーブレット木の効率的で簡単な実装 "The Wavelet Matrix"」から始まったウェーブレット行列ブームから半年以上が過ぎ、すでに枯れた技術として確立されつつある感があります。 …嘘です。 日本以外ではあんまり来ていません。 理由としては、やはりアルファベット圏では単語境界が明確であるため、こちらの記事で書かれているような「キーワード分割の難易度」といったことがあまり問題にならないということがあるかもしれません。 まあ、そういうわけで局所的に来ているウェーブレット行列ですが、日本語をはじめとする単語境界のない言語圏にとっては重要なネタであると思うため、解説記事を書き直して*1みようと思います。 ウェーブレット行列でできること 主となる操作は、文字列に対する 定数時間の rank() と select()*2 です。 rank() は、「文
2009-03-05
はてなフォトライフなど大量の画像データを無料で預かるサービスが多い。そこで画像データとしてプログラムをはじめバイナリデータやテキストデータを保存するプログラムを作ってみた。コンセプトしては昔からあるので別に新しいものでもないし、Windowsでは色々なフリーソフトがるようだ。ここでは、あくまで個人が気楽に使う意味で（お遊びで）、簡単なシェルスクリプトとして組んでみた。 まだ、完成度がかなり低く、ブログに載せるのはどうかな、と思ったのだが、ちょっと忙しくなりそうで、今書いておかないと忘れてしいそうなので。まだまだバグが潜んでいそうだが、それは御愛嬌で。 ■ 概要 tar（tape archive）をもじって“bar”（bitmap archive）という名前で作ったみた。例えば、 $ bar -cf files.png file1 file2 file3 ....という風に使う。勿論、ディレ
Key size - Wikipedia
In cryptography, key size or key length refers to the number of bits in a key used by a cryptographic algorithm (such as a cipher). Key length defines the upper-bound on an algorithm's security (i.e. a logarithmic measure of the fastest known attack against an algorithm), because the security of all algorithms can be violated by brute-force attacks. Ideally, the lower-bound on an algorithm's secur
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
Cybersecurity as a Service Delivered | Sophos
GitHub - marcandre/fruity: Cool performance comparison tool
The Hash Function Zoo - The ECRYPT Hash Function Website