計算できるもの、計算できないもの
計算機による計算とは何か、計算できるものとできないものの境界はどこにあるのか―それを明らかにする計算理論は、計算機科学においてもっとも基本的、かつ重要なものです。本書では、概念の説明や、結果の証明にPythonプログラムを利用する実践的なアプローチにより、計算可能問題と計算不能問題、扱いやすい問題と扱いにくい問題があること、文章では簡単に表現できても計算機には解けない重要な問題が数多くあること、効率よく解ける問題と解けない問題があることなどを、計算理論の礎を築いたアラン・チューリングとリチャード・カープの論文の抜粋とともに解明します。チューリングマシン、有限オートマトン、万能計算、非決定性、チューリング還元、計算量クラス、NP完全性などのトピックをカバーしています。 謝辞 まえがき:教科書として使う方へ 全体像 1章 はじめに:計算できるもの, できないものとは 1.1 扱いやすい問題 1
ゼロから作るDeep Learning
ディープラーニングの本格的な入門書。外部のライブラリに頼らずに、Python 3によってゼロからディープラーニングを作ることで、ディープラーニングの原理を楽しく学びます。ディープラーニングやニューラルネットワークの基礎だけでなく、誤差逆伝播法や畳み込みニューラルネットワークなども実装レベルで理解できます。ハイパーパラメータの決め方や重みの初期値といった実践的なテクニック、Batch NormalizationやDropout、Adamといった最近のトレンド、自動運転や画像生成、強化学習などの応用例、さらには、なぜディープラーニングは優れているのか？ なぜ層を深くすると認識精度がよくなるのか？ といった“Why”に関する問題も取り上げます。 関連ファイル サンプルコード 正誤表 ここで紹介する正誤表には、書籍発行後に気づいた誤植や更新された情報を掲載しています。以下のリストに記載の年月は、正
algorithm - mapBetween - 配列の隣接する2項にそれぞれ演算を施した配列 : 404 Blog Not Found
2012年01月04日21:00 カテゴリLightweight Languages algorithm - mapBetween - 配列の隣接する2項にそれぞれ演算を施した配列 言語を増やしたかったのと、そういう関数に名前を付けたかったのとで1 entry割くことにしました。 等差数列 - タイトル 配列の隣接する2項にそれぞれ演算を施した配列を得たい。つまり、 f (+) [1,2,3,4,5] = [3,5,7,9] のような f が欲しい。 名前 もちろん等差数列を作るのにもこの関数は使えるのですが、この一般的に使える関数に使う名前としてはあまりに局所的。というわけで mapBetween としてみました。使いどころはかなり多そうです。各言語に標準装備されていないのがちょっと不思議なほど。 JavaScriptによる実装 Array.prototype.mapで滅多に使われない第
モダン並列・並行プログラミング ～ Concurrent Revisions による実装と現実 ～ - Preferred Networks Research & Development
本日社内向けのTechTalkにて、並列・並行プログラミングに関する話を行いました。 昨今、プログラムの並列化はなくてはならないものとなっています。しかし、そのプログラミング環境は依然としてロックを用いたものが主流です。今回の発表の主張を端的に申し上げますと、 “Locks must go！” ということになります。並列プログラミングに銀の弾丸はありません。しかし、ロックは別の何らかの安全性を確保したプログラミングモデルで置き換えられなければいけません。そうでなければ、再現しにくいバグに苦しめられ、終電を逃す日々と決別することはできないでしょう。また、ロックによるプログラミングの抱える本質的問題にも言及しています。 この界隈の最新の動向として、去年OOPSLA’10にて発表されたConcurrent Revisionsについての解説も行なっております。また、弊社研究開発において、先日Con
アルゴリズムの勉強のしかた - きしだのHatena
この記事で、アルゴリズムの勉強はアルゴリズムカタログを覚えることじゃないよということを書きました。 プログラムの理論とはなにか アルゴリズムの勉強というのは、スポーツで言えば腕立て伏せや走り込みみたいな基礎体力を養うようなもので、「ソートなんか実際に自分で書くことないだろう」とかいうのは「サッカーは腕つかわないのに腕立ていらないだろう」とか「野球で1kmも走ることなんかないのに長距離の走り込みいらないだろう」とか言うようなものです。 Twitterでアルゴリズムの勉強とはなにかと尋ねられて、「アルゴリズムの基本的なパターンを知って、それらの性質の分析のしかたをしって、いろいろなアルゴリズムでどのように応用されているか知って、自分が組むアルゴリズムの性質を判断できるようになることだと思います。 」と答えたのですが、じゃあ実際どういう本で勉強すればいいか、ぼくの知ってる本からまとめてみました。
Google Developer Day (GDD) 2011 DevQuiz 回答スクリプト
Google Developer Day 2011 Japan DevQuiz 通称 GDD 2011 DevQuiz に挑戦してました。 結局まとまった時間は先週の夜と週末だけだったので、なかなか思うように進みませんでした。 まず手始めにウォームアップクイズから始めたのですが、google が公開している API とか詳しくないので満点を取るのには思いのほか苦労しました。クイズは Web Game と一人ゲームを解きました。 この２つは比較的難易度が低かったので時間はかかりませんでした。そして最後の難関のスライドパズルは良案が終了１時間前に思い浮かぶも時間切れ。結局 2355 問しか提出することができませんでした。というわけで採点結果は下記の通りとなりました。 最近はプログラミングから離れていたので良い刺激になりました。 さて、以下回答例を晒しておきます。必ずしも良案ではないのであしから
なぜRubyをPythonよりもPHPよりも高速化できたか - 方向
最も有名なベンチマークサイト "The Computer Language Benchmarks Game" における最新のランキングで Ruby 1.9 は Python3, PHP, JRuby を追い抜きスクリプト言語としてトップクラスの値を叩き出しました。 5/4の時点では最下位に近かったので大きく前進しています。 1つのパッチで520%の高速化を達成 この高速化は私がfastaというベンチマークのプログラムを改善したことにより実現しました。 少し前Rubyのベンチマークを書くことにハマっていました。 他の人のプログラムや統計を眺めていたとき、fastaに関してPythonが異常に速いことに気づきました。 他のスクリプト言語のおよそ50倍速く、アルゴリズムが改良されていました。 fasta #6 fasta #7 この2つのコードを比較するとわかるのですが、処理が重複している箇所に
常識を覆すソートアルゴリズム！その名も"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 なん…だと
4chan BBS - Genius sorting algorithm: Sleep sort
1 Name: Anonymous : 2011-01-20 12:22 Man, am I a genius. Check out this sorting algorithm I just invented. #!/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 Oh god, it works. But I don't like to wait 218382 seconds to sort '(0 218382)
livedoor Techブログ : decision tree (決定木) でユーザエージェント判定器を作ってみる
アクセスログのユーザエージェント(UA)からブラウザを判別するのって，みんな何使ってますか？ 自分が作ったアクセス解析システムでは HTTP::BrowserDetect と HTTP::MobileAgent にそれぞれ独自パッチをあてたものを使っています。これらはルールベースの判定器なので，新しいブラウザや新種の bot が登場するたびに手作業でルールを追加し，パッチを作って配布するという作業が必要になります。 この更新作業が大変面倒くさくて対応が遅れがちになるので，「このUA文字列はこのブラウザですよ、という例を大量に与えたら、自分で勝手に判定ルールを学習してくれるようになったら便利なのになぁ」と思い，decision tree (決定木)を使ってみることを思い立ちました。 目標は， "Mozilla/5.0 (Windows; U; Windows NT 6.1; ja; rv:1
プログラミングコンテストチャレンジブックを読みながらダイクストラ法を実装したよ - nokunoの日記
前回のベルマンフォード法から時間があいてしまいましたが、プログラミングコンテストチャレンジブック（通称アリ本）を読みながらグラフの最短経路を求めるためのアルゴリズム、ダイクストラ法を実装しました。 ベルマンフォード法 - nokunoの日記ダイクストラ法 - Wikipedia ダイクストラ法ではグラフ中のノードを次の3つに分類します。 未探索 探索済み 次の探索候補この「次の探索候補」の中から最もコストの小さいノードを選んで探索済みとし、その隣接ノードのコストを更新するというのがダイクストラ法の根本のアルゴリズムとなります。 最初の実装それでは実装を見ていきましょう。まず最初の実装では次に探索済みとなる要素を線形探索しているためあまり効率的ではありません。 #include using namespace std; #define MAX_E 20 #define MAX_V 7 #d
きれいなおねいさんのあつめかた：Bijostagramのはなし。 - TMBのおぼえがき
Bijostagram（びじょすたぐらむ）というWebサービスを作ってみました。 Bijostagram - Cute Girls on Instagram きれいなおねいさんは、好きですか？ Bijostagramとは？ Bijostagramは、きれいなおねいさんの画像がたくさん眺められるサービスです（個人的に作りました）。一番の大きな特徴は、Instagramから自動的にきれいなおねいさんの画像を集めてくる、というところです。Bijostagramでは、集めてきたおねいさん画像をランダムに表示しています。 Instagramは写真版Twitterで、しかも撮影した画像をオサレな感じで加工できてツイートできるというサービス。２月末に公式のAPIが公開されたので、いじってみました。→インスタグラムのAPIについてはこちら Bijostagramは、画像抽出と画像配置のアルゴリズムをPer
開発メモ: Kyoto Cabinetのロック機構の改善
Kyoto CabinetはIO負荷が高い場合にCPU負荷も高くなりがちだという指摘を受けて、それを解決すべくロック機構を見直したという話。 スロットロック ハッシュテーブルの操作はハッシュバケット毎に完全に独立して実行できるのが強みだ。ハッシュテーブルは計算量が有利なだけでなく、並列性にも優れるということ。実際には下層のファイルIOで実装依存の排他制御が行われることになるが、ハッシュ層だけ見れば理想的な並列性を備えている。ただし、同じバケットに連なるレコード群の操作は互いに依存関係があるので、それらは一括して排他制御してやる必要がある。となると、バケット毎にロックを用意するのが理想だが、実際にはメモリを節約するために、予め決めた数のロックを用意して、ここのロックに複数のバケットを割り当てる構成をとる。リソース空間をスロットに分けるというイメージから、これをスロットロックと呼ぼう。 スロッ
平方根のアルゴリズム
平方根である。sqrtである。私の数学知識は非常に乏しく、かろうじて平方根の何たるかを解するばかりであるが、ふと、平方根を計算するアルゴリズムが知りたくなった。理由は、constexprなsqrtを実装してみたくなったからだ。 日本語では、いい情報がWeb上に存在しないので、ここに書いておく次第。この説明は、私のように数学の知識を持たない人間にも理解できるはずである。 ここで使うのは、バビロニア人の方法（Babylonian method）と呼ばれている、歴史あるアルゴリズムである。この方法は、手動でも、プログラミングでも、非常に簡単に計算できる、大変便利で汎用的なアルゴリズムである。しかも、速度もそれほど遅くない。 √Sに対して、 任意の正の整数を初期値X0と定める（できるだけ平方根に近い値が望ましい） Xn+1を、Xnと S / Xnの平均値とする（平均値は相加平均で求める） 必要な精
perlで高速な類似検索エンジンを構築できるようにしてみた - download_takeshi’s diary
すみません。タイトルはやや釣り気味です。 類似検索エンジンというか、そのアイデア程度の話なんですが、以前から考えていた類似検索エンジン風のネタがあったので、ちょっとperlで書いてみたので、そいつを晒してみます。 Luigi https://github.com/miki/Luigi 類似検索なのでLuigi。ルイージとか読みたい人はそう読んじゃっても良いです。（冷） 考え方と仕組み 類似文書の検索、となりますと一般的には超高次元での空間インデックスとかが必要になります。 昔からR-TreeやSR-Treeなど、いろいろと提案されていますが、より高次元になると「次元の呪い」によりパフォーマンスが出なくなる、なんて言われていますね。 そこで最近ではLSHに代表されるような、より高度な「近似」型のインデキシング手法が人気を集めているようです。 で、今回考えたLuigiも実は近似型のインデッ
美しすぎるプログラムを解読せよの巻 - やねうらおブログ(移転しました)
#include <iostream> #include <cstring> using namespace std; long long dp[18][4][4][4][4][4][4][4][4][4][4]; #define FORN( n ) for ( int i##n = 0; i##n < 4; i##n ++ ) int main() { memset( dp, 0, sizeof( dp ) ); FORN( 0 ) FORN( 1 ) FORN( 2 ) FORN( 3 ) FORN( 4 ) FORN( 5 ) FORN( 6 ) FORN( 7 ) FORN( 8 ) FORN( 9 ) dp[0][i0][i1][i2][i3][i4][i5][i6][i7][i8][i9] = 1; for ( int r = 1; r <= 17; r ++ ) { FORN
[VM][JIT]Brainf*ckで学ぶスクリプト言語処理系高速化。インタプリタ→VMインタプリタ→JITコンパイラ。 - hogelogの日記
スクリプト言語処理系を高速化したくてしたくてたまらない少年少女に届け。表題の通りスクリプト言語処理系の高速化について書きます。対象言語はBrainf*ckにします。Brainf*ckというのは Brainf*ck Brainfuck - Wikipedia というような言語です。要は処理系を実装するのが簡単なおもちゃ言語。おもちゃ言語ゆえに他のどんな実用的スクリプト言語処理系にも出てくるような基本的な処理だけでできているので、Brainf*ck処理系の高速化で有用なテクニックは他の処理系でもうんたらかんたら。 じゃあまず叩き台になるような処理系を書いてみましょう。言語はC++です。JavaだのPythonだので高速な処理系を記述するテクニックやらなんやらというのもありますけども、まずはごく簡単にCPUやらメモリといったものと仲の良い言語で記述することで理解を深めましょう。本当はC言語の方が
![[VM][JIT]Brainf*ckで学ぶスクリプト言語処理系高速化。インタプリタ→VMインタプリタ→JITコンパイラ。 - hogelogの日記](https://cdn-ak-scissors.b.st-hatena.com/image/square/2769bb4727fa549a477e8806ecae7ad9c2303ec3/height=288;version=1;width=512/https%3A%2F%2Fogimage.blog.st-hatena.com%2F12704346814673895633%2F12921228815733205071%2F1411114774)
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
プログラミングに興味があれば、つい入れてみたくなるアプリ「アルゴリズム図鑑」
Amazon CAPTCHA
XXmallocのメモリ管理アルゴリズムについてわかりやすい記事 - Qiita
