アルゴリズムと計算量
金庫破りと計算量膨張 n 桁の番号をもつ暗証ロックがあるとします。 2 桁であれば 00 〜 99 の 100 個の正解があるわけで、 0 番から順に入力していく解き方では、 最悪の場合は 100 手目に開きます。 99 が正解とは限らないので、平均的にはこれより早く解き終わります。 0 であるときの確率は 1/100 で、このときの手数は 1 手です。 1 であるときの確率は 1/100 で、このときの手数は 2 手です。 2 であるときの確率は 1/100 で、このときの手数は 3 手です。 3 であるときの確率は 1/100 で、このときの手数は 4 手です。 : 99 であるときの確率は 1/100 で、このときの手数は 100 手です。 つまり、平均手数は により、100 手目の約半分です。 ここでいう解き方をアルゴリズムといい、 問題を解くための手数 (てかず) のことを計
データ量を操る圧縮／展開を究めよう
というふうに変換します。 文字数で比較してみると、圧縮前は14文字でしたが圧縮後は6文字と半分以下になっています。圧縮後のデータから元のデータに戻すことも容易にできます。 ランレングス法の実装 それでは早速、ランレングス法を実装してみましょう。サンプルデータは某巨大掲示板から引用しました。 <html> <head> <script type="text/javascript"> function getStringById(id) { var element = document.getElementById(id); return element.innerHTML; } </script> </head> <body> <div id="area1"> <pre> ＿＿＿＿＿＿＿＿ ＿＿＿＿＿＿＿＿ （＿＿＿＿＿ ＼ ⊂⊃ ／ ＿＿＿
大規模データを基にした自然言語処理 - DO++
人工知能基本問題研究会 (SIG-FPAI)でタイトルの題目で一時間ほど話してきました。 発表資料 [pptx] [pdf] 話した内容は - 自然言語処理における特徴ベクトルの作り方と、性質 - オンライン学習, Perceptron, Passive Agressive (PA), Confidence Weighted Learning (CW) 確率的勾配降下法 (SGD) - L1正則化, FOLOS - 索引を用いた効率化, 全ての部分文字列を利用した文書分類 で、スライドで70枚ぐらい。今までの発表とかぶっていないのはPA CW SGD FOLOSあたりでしょうか オンライン学習、L1正則化の話がメインになっていて、その両方の最終形の 確率的勾配降下法 + FOLOSの組み合わせは任意の損失関数に対してL1/L2正則化をかけながらオンライン学習をとても簡単にできるという一昔前
ダイクストラ法（最短経路問題）
ダイクストラ法 (Dijkstra's Algorithm) は最短経路問題を効率的に解くグラフ理論におけるアルゴリズムです。 スタートノードからゴールノードまでの最短距離とその経路を求めることができます。 アルゴリズム 以下のグラフを例にダイクストラのアルゴリズムを解説します。 円がノード，線がエッジで，sがスタートノード，gがゴールノードを表しています。 エッジの近くに書かれている数字はそのエッジを通るのに必要なコスト（たいてい距離または時間）です。 ここではエッジに向きが存在しない（＝どちらからでも通れる）無向グラフだとして扱っていますが， ダイクストラ法の場合はそれほど無向グラフと有向グラフを区別して考える必要はありません。 ダイクストラ法はDP（動的計画法）的なアルゴリズムです。 つまり，「手近で明らかなことから順次確定していき，その確定した情報をもとにさらに遠くまで確定していく
まつもとゆきひろ氏が語る「ビューティフルコード」セミナーに行って来た - LukeSilvia’s diary
まつもとゆきひろが語る「ビューティフルコード」×「プログラマ35歳定年説」に行ってきました〜。今年初めて行ったイベントなのですが、とてもいいお話を聞くことができました。美しいコードとはどのようなものか、またそのようなコードを書けるようになるためにはどうすればいいのかというお話でした。 以下、まとめになります。僕のメモを元にしたので、まつもとさんが話された内容と多少ズレがあるかもしれません。 そもそもコードとは何か 「コードの美しさとは」という前に、そもそも「コード」とは何か。 ソフトウェアの作成はものづくりではない コードは工業製品ではない。コードは、車とかと同じ工業製品だと思われることが多く、例えば次のような勘違いがある。 日本は「ものづくり」が得意だ。だからソフトウェアも「ものづくり」として取り組めばいい 車のように、ソフトウェアも部品をどんどんコピーして組み合わせばできる 違うよ！全
HatebuFriends の仕組み - もしかして: blog.iron’s.jp
学生時代に研究・卒論からの現実逃避の一環で作り、去年の10月頃公開（1度移転）した HatebuFriends について今更書いてみたいと思います。 HatebuFriends とは はてなブックマークのブックマーク情報を利用して、好みが似ているユーザや、興味がありそうなページを推薦します。 棒グラフをクリックすると共通のブックマーク一覧が表示されます。同じページをブックマークしたユーザをハイライトすることもできます。 興味がありそうなページを推薦してくれる機能もあります。 人によって精度の差はあると思いますが、自分ではいい感じに推薦されてきていると思っています。 ユーザ間の関連度計算 同じページをブックマークしていることが多いユーザ同士は、似た嗜好を持っていると考えられます。 特に、ブックマークユーザ数が少ないページのほうが、誰もがブックマークするようなページよりも、ブックマークが
はてなブックマーク全文検索機能の裏側
そろそろ落ち着いて来たころ合いなので、はてなブックマーク全文検索機能の裏側について書いてみることにします。 PFI側は、8月ぐらいからバイトに来てもらっているid:nobu-qと、id:kzkの2人がメインになって進めました(参考: 制作スタッフ)。数学的な所は他のメンバーに色々と助言をしてもらいました。 はてな側は主にid:naoyaさんを中心に、こちらの希望や要求を聞いて頂きました。開発期間は大体1〜2か月ぐらいで、9月の上旬に一度id:naoyaさんにオフィスに来て頂いて合宿をしました。その他の開発はSkypeのチャットで連絡を取りながら進めてました。インフラ面ではid:stanakaさん、契約面ではid:jkondoさん、id:kossyさんにお世話になりました。 全文検索エンジンSedue 今回の検索エンジンはSedue(セデュー)という製品をベースにして構築しています。Sedu
正規表現エンジンを作ろう （2）〜NFAとDFAを実装する〜：CodeZine
はじめに こんにちは。hirataraです。 本稿は、正規表現エンジン作成の第2回目です。前回は正規表現の数学的な側面を説明しました。今回は正規表現エンジンの実際の評価器となる、NFAとDFAを実装します。 対象読者 正規表現をもっと知りたい方 情報科学分野に興味がある方 正規表現エンジンを実装する必要がある方 必要な環境 サンプルはPython2.5で開発しましたが、2.4の環境でも動くはずです。 Python2.5 が動作する環境 実装する正規表現の仕様 今回から正規表現エンジンの実装に入りますが、実際に手を動かし始める前に、到達すべきゴールを明確にしておきましょう。まず、連載中に実装する正規表現の仕様を決定します。この連載では数学的な定義である3つの正規表現のみを実装し、正規表現が本当にDFAと等価であり、DFAをシミュレートすることで実装できることを確かめます。 文法 これから作る
サーチのアルゴリズムを学ぶ
サーチ（探索）でPHPの基礎を学ぼう 「【一気に覚えるPHP！】アルゴリズムで頭の体操（http://www.thinkit.co.jp/article/62/）」では、定石と呼べる基本的なソートのアルゴリズムを勉強することで、より本質的なプログラムの考え方を身につけることを目指しました。今回は、好評だったこの連載の続編として、サーチ（探索）のアルゴリズムをPHPで書いてみましょう。 前回も説明しましたように「いまさら」サーチのプログラムをPHPで書く必要はありません。実際のプロジェクトを戦いとするならば、アルゴリズムを学ぶことは、戦う自分の基礎となる「筋力」を鍛えることです。そして、これを鍛えるには、先人たちの知恵に学び、また、すでにあるものでもそれを自分で（＝独力で）作ってみることが一番です。プログラミング言語やライブラリ関数がカバーしてくれる範囲のものを手作りすることで、考え方の基本
講義資料 配列解析アルゴリズム特論I 情報生命科学基礎/演習 他 -渋谷哲朗
平成20年度 東京大学大学院 情報理工学系研究科・コンピュータ科学専攻 配列解析アルゴリズム特論I 4/10 4/17 4/24 5/1 5/8 5/15 5/22 5/29 (The problem to be reported - in English) 6/5 6/12 6/19 7/3 7/10 7/17 東京大学 理学部・情報科学科 情報科学特別講義３ （情報科学とバイオインフォマティクス） 6/10 7/15 7/22 東京大学大学院 新領域創成科学研究科・情報生命科学専攻 情報生命科学基礎/演習 5/27 6/17 京都大学大学院 薬学研究科・医薬創成情報科学専攻 情報科学概論 6/3 中央大学大学院 理工学系研究科・物理学専攻 物理学特別講義第二 TBA 創価大学工学部 生命情報工学科 TBA TBA 戻る Copyright (c) 2004- Tetsuo
ハフマン符号化法
ハフマン符号化法は文字だけで説明したので、この場で読むことが出来るようにいたします。 ファイル圧縮技術 －ハフマン符号化法の紹介－ LHAってソフト、知ってますよね。ファイル圧縮ソフトです。たとえばフロッピーディスク２枚分のデータを、フロッピーディスク１枚に納まるようにしてしまいます。 なぜそんなことができるのでしょうか。 LHA付属のドキュメント・ファイルを読んでみます。 吉崎 栄泰「ＬＨＡ取り扱い説明書」Ver.2.13 1991/07/20 NIFTY-Serve SDI00506 の 「0. はじめに」には >>アルゴリズムを動的ハフマン法から静的ハフマン法に変更したので、・・・・ という一文が書いてあります。 ハフマン法って何だろう。きっと、ものすごい数学的技術を使っているんだろうな・・・と思っていたときに、たまたま読んだのがＡ・Ｋ・デュードニー「チューリング・オムニバス 第１巻
高速な算術圧縮を実現する「Range Coder」
はじめに 本記事では、全体のサイズが最小となる算術圧縮を高速に実現するRange Coder（以下RC）を紹介します。 算術圧縮は、各文字の出現確率が分かっている場合にそのデータを最小長で表現可能な符号法です。各文字に固定の符号を割り当てるHuffman法とは違い、符号化を状態更新とみなし、すべての文字を符号し終わった後の状態を保存することで符号化を実現します。これにより1文字単位の符号長を1bitより細かく調整することが可能となります。 算術符号は圧縮率が高い反面、ビット単位の演算処理が大量に発生するため、符号化、復号化ともにHuffman符号に比べ遅いという問題点があります。今回紹介するRCは、算術符号の処理をバイト単位で行うことで高速な処理を可能にします。 また、算術圧縮については概要から説明します。 対象読者 C++の利用者を対象としています。データ圧縮の基礎を知っていることが望ま
Spaghetti Source - 各種アルゴリズムの C++ による実装
ACM/ICPC（プログラミングコンテスト）系列の問題を解くことを目標にして，各種アルゴリズムを C++ で実装してみた．極めて意地が悪い類の問題には対応していないし，特定の入力に対して高速に動くということもない．計算量も最良とは限らない． これらを参考にする方への注意とお願い： これらの記述は正確とは限りません．参考文献を参照することを強く推奨します．間違っている場合は是非教えてください． これらのプログラムは間違っているかもしれません．各人で検証することを強く推奨します．バグがあれば是非教えてください． 分類が怪しいので，これはこっちだろう，ということがあればコメントを下さると助かります． 注意！ 現在書き換え中 TODO 分類を正しく行う． 全体的に説明と使い方を詳しく． Verify していないものを Verify． ボロノイ図（いつになることやら……） 基本 テンプレート グラフ
ガベージコレクションの実装法と評価
1.はじめに プログラミング言語とはシステム化する対象物を抽象化し、コンピュータで処理可能なコードを記述するために用いる人工言語である。プログラミング言語はコンピュータの機械語と一対一の対応をもったアセンブラから始まり、コンパイラを用いて機械語に翻訳することを前提としたコンパイラ言語、インタプリタと呼ばれるプログラムがソースコードを解釈し実行するスクリプト言語と、記述できる抽象度を高める方向へと進化してきた。 プログラミング言語はその存在理由から、より抽象度の高い記述が行えること、すばやい開発を行える事が求められる。抽象度の高い記述とは、プログラムがどういう処理を行うか(HOW)ではなく何の処理を行うか(WHAT)を記述しやすい構文、機能を持っていることを、すばやい開発とは記述性の高さ、コードの密度の高さ、バグの発生しにくい構文、機能を持っていることをさす。 この抽象度の高い記述、すばやい
アルゴリズムとデータ構造演習
本演習の目的は、プログラミング言語C及びSchemeの基礎を習得し、 それらの言語を通じて、講義「アルゴリズムとデータ構造」の理解を深めることにあります。 重要なお知らせ 特に重要な連絡事項はここに掲載されます。 課題について 課題には、A課題とB課題があります。（課題番号の末尾が種類を表します。） B課題が基礎的な課題で、A課題が発展的な課題となっています。 B課題を全問解くことが、単位取得の目安です。 C入門第1回（10月10日） C入門第2回（10月17日） C入門第3回（10月24日） C入門第4回（10月31日） C第1回（11月7日） C第2回（11月14日） C第3回（11月21日） C第4回（11月28日） C第5回（12月5日） Scheme第1回（12月12日） Scheme第2回（12月19日） Scheme第3回（1月9日） Scheme第4回（1月16日） C補講
GC - GCアルゴリズム詳細解説 - livedoor Wiki（ウィキ）
GCアルゴリズム詳細解説 日本語の資料がすくないGCアルゴリズムについて詳細に解説します トップページページ一覧メンバー編集 × GC 最終更新： author_nari 2010年03月14日(日) 20:47:11履歴 Tweet このWikiが目指す所 GCとは？ GCを学ぶ前に知っておく事 実行時メモリ構造 基本アルゴリズム編 Reference Counter Mark&Sweep Copying 応用アルゴリズム編 IncrementalGC 世代別GC スナップショット型GC LazySweep TwoFinger Lisp2 Partial Mark and Sweep -Cycle Collection- Mostly Parallel GC train gc MostlyCopyingGC(Bartlett 1989) TreadmillGC(Barker 1992)
404 Blog Not Found:プログラマーでなくても名前ぐらい覚えておきたいアルゴリズムx10
2007年11月26日18:15 カテゴリMathLightweight Languages プログラマーでなくても名前ぐらい覚えておきたいアルゴリズムx10 ぎくっ あなたが一番好きなアルゴリズムを教えてください。 また、その理由やどんな点が好きなのかも教えてください。 - 人力検索はてな なぜぎくってしているかというと、実はすでにアルゴリズム本の発注を受けているからなのだ。いつまでも伏せておくのもなんなので、ここにえいやっとdiscloseしてしまうことにする。 アルゴリズム大募集! C&R研究所 - トップページ その下書きもかねて、そこでも紹介しないわけに行かないメジャーなアルゴリズムをとりあえず10個紹介しておくことにする。 ユークリッドの互除法(Euclidean algorithm) その昔(数百年ほど前)は「アルゴリズム」といえば、「手順一般」を指すのではなく、この「互除法
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
[Think IT] 【一気に覚えるPHP！】アルゴリズムで頭の体操
データ圧縮の基礎
http://www-masu.ist.osaka-u.ac.jp/~kakugawa/lecture/2006/fcs/note/slide1/index.html