計算できるもの、計算できないもの
計算機による計算とは何か、計算できるものとできないものの境界はどこにあるのか―それを明らかにする計算理論は、計算機科学においてもっとも基本的、かつ重要なものです。本書では、概念の説明や、結果の証明にPythonプログラムを利用する実践的なアプローチにより、計算可能問題と計算不能問題、扱いやすい問題と扱いにくい問題があること、文章では簡単に表現できても計算機には解けない重要な問題が数多くあること、効率よく解ける問題と解けない問題があることなどを、計算理論の礎を築いたアラン・チューリングとリチャード・カープの論文の抜粋とともに解明します。チューリングマシン、有限オートマトン、万能計算、非決定性、チューリング還元、計算量クラス、NP完全性などのトピックをカバーしています。 謝辞 まえがき:教科書として使う方へ 全体像 1章 はじめに:計算できるもの, できないものとは 1.1 扱いやすい問題 1
計算機プログラムの構造と解釈 第二版
[ 目次, 前節, 次節, 索引 ] 目次 目次 序文 第二版への前文 第一版への前文 謝辞 1 手続きによる抽象の構築 1.1 プログラムの要素 1.1.1 式 1.1.2 名前と環境 1.1.3 組合せの評価 1.1.4 合成手続き 1.1.5 手続き作用の置換えモデル 1.1.6 条件式と述語 1.1.7 例: Newton法による平方根 1.1.8 ブラックボックス抽象としての手続き 1.2 手続きとその生成するプロセス 1.2.1 線形再帰と反復 1.2.2 木構造再帰 1.2.3 増加の程度 1.2.4 べき乗 1.2.5 最大公約数 1.2.6 例: 素数性のテスト 1.3 高階手続きによる抽象 1.3.1 引数としての手続き 1.3.2 lambdaを使う手続きの構築 1.3.3 一般的方法としての手続き 1.3.4 値として返される手続き 2 データ
perlbrew + cpanminus + local::lib で環境構築 - Webtech Walker
local::libとかcpanmとか便利になってきたなーと思っていたところにperlbrewというまた新たなツールがでてきたので一度ここら辺でperlの環境構築についてまとめときます。 システムにインストールされているperlを使うとOSのアップデートなどの影響を受けてしまうので、それらを使わずホームディレクトリ以下にperlもCPANモジュールも全部インストールしていきます。 perlbrewはperlをバージョン毎にインストールしたり、それらをswitchして使えたりすることができるコマンドです。 App::perlbrew - search.cpan.org まずperlbrewをインストールします。 $ curl -LO http://xrl.us/perlbrew $ chmod +x perlbrew $ ./perlbrew install これで$HOME/perl5にp
Sublime Text 3 Beta - News - Sublime HQ
The first beta of Sublime Text 3 is now available to download for registered users. Some feature highlights are below, followed by our new pricing and upgrade policies, and system compatibility for Sublime Text 3. Symbol Indexing. Sublime Text now scans the files in your project, and builds an index of which files contain which symbols. This backs the new features Goto Definition and Goto Symbol i
The OMake build system
News Version 0.9.8.6 Release Candidate 1 (October 26, 2010) Version 0.9.9 Prerelease (June 20, 2007) Overview OMake is a build system designed for scalability and portability. It uses a syntax similar to make utilities you may have used, but it features many additional enhancements, including the following. Support for projects spanning several directories or directory hierarchies. Fast, reliable,
わたしがprintf()デバッグをしない理由 2009-03-22 - 未来のいつか/hyoshiokの日記
プログラマという職業について、もう25年くらいになるのであるが、その間にコンピュータのコストパフォーマンスは、それこそムーアの法則に従って、10万倍〜100万倍くらい向上した。にもかかわらづ、デバッグの方法というものの劇的な変化はほとんどみられない。 プログラミング入門書では、デバッグについて、ほとんど議論されていないし、仮にふれられていても、おざなりな方法というか、かなり邪険にあつかわれていたりする。プログラマの多くの時間がデバッグについやされていたとしてもだ。 たまたま手元にあった、C実践プログラミング(ISBN4-900900-64-8)という10年くらい前に買った参考書では、450ページのうちデバッガの利用については、4行ほど記述がある。たった4行である。診断用のprintf()を挿入するということは3ページにわたって記述されているのにだ。 流石に21世紀になってprintf()デ
最強最速アルゴリズマー養成講座：アルゴリズマーの登竜門、「動的計画法・メモ化再帰」はこんなに簡単だった (1/5) - ITmedia エンタープライズ
動的計画法とメモ化再帰 今回は、非常によく用いられるアルゴリズムである、「動的計画法」「メモ化再帰」について説明します。この2つはセットで覚えて、両方使えるようにしておくと便利です。 なお、メモ化再帰に関しては、第5・6回の連載の知識を踏まえた上で読んでいただけると、理解が深まります。まだお読みになっていない方は、この機会にぜひご覧ください。 中学受験などを経験された方であれば、こういった問題を一度は解いたことがあるのではないでしょうか。小学校の知識までで解こうとすれば、少し時間は掛かるかもしれませんが、それでもこれが解けないという方は少ないだろうと思います。 この問題をプログラムで解こうとすると、さまざまな解法が存在します。解き方によって計算時間や有効範囲が大きく変化しますので、それぞれのパターンについて考えます。 以下の説明では、縦h、横wとして表記し、プログラムの実行時間に関しては、
MITの開発した、画像処理用プログラミング言語「Halide」【サイエンスニュース】 ｜ ガジェット通信 GetNews
パソコンを始めとして、様々な電子機器で、高度な画像処理が求められるようになってきている。 スマートフォンのアプリやデジカメでも、本格的なフォトレタッチ機能が搭載されており、これらを利用している人も多いだろう。 こうした画像処理プログラムの開発でキーとなるのが「並列化」だ。画像を処理する場合、大量のデータに対して同じ変換処理を行っていくことが多い。こうした処理を行う際、画像を細かな単位に分割して、同時に処理を行うことができれば実行時間を短くできる。今ではスマートフォンにも搭載されているGPUは、処理を同時並列的に、実行するために設計された画像処理用のプロセッサだ。しかし、並列処理に最適化されたプログラムコードを書くのは、非常に手間がかかる。プログラマーは、どのようなアルゴリズム（計算方法）で画像処理を行うかということに加え、それをどう並列化するかということまで考えないといけないからだ。 MI
The Julia Programming Language
Fast Julia was designed for high performance. Julia programs automatically compile to efficient native code via LLVM, and support multiple platforms. Dynamic Julia is dynamically typed, feels like a scripting language, and has good support for interactive use, but can also optionally be separately compiled. Reproducible Reproducible environments make it possible to recreate the same Julia environm
なぜ僕らはJuliaを作ったか（翻訳） - 丸井綜研
僕は言語を作るきっかけとか思想とかに興味があるので、日頃から新言語を見つけてはニヤニヤしてるんですが、つい昨日Juliaという新言語のリリース記事を読んで、面白そうだったので、紹介がてら粗く翻訳してみました。 なぜ僕らはJuliaを作ったか（原文：Why We Created Julia） 2012年2月14日(火) | Viral Shah, Jeff Bezanson, Stefan Karpinski, Alan Edelman 端的に言えば、僕らは欲張りだからだ。 僕らはMatlabのパワーユーザーだ。LispハッカーやPython使いやRuby使いもPerlハッカーもいる。髭が生える前からMathematicaを使っていたのもいるし、未だに髭が生えてない仲間もいる。常識的な人にはオススメしないくらい多くのグラフをR言語で描いてきた。そしてC言語は僕らのユートピアだ。 いま挙げた言
Bashで覚えておくとよいデータ構造 - 配列 - いろいろ解析日記
Bashで必要なデータ構造の覚書です。 目次 配列 配列を生成する。 配列にデータを追加する。 配列にデータを格納する。 配列からデータを取得する。 配列中のすべてのデータに同じ処理をする。 関連記事 配列 配列は複数件のデータを扱うためのデータ構造です。 ■配列を生成する。 配列の生成は以下のように行います。 配列の名前=() 配列の名前=("データ" "データ" "データ")配列の生成では、配列の名前を指定します。 もし、生成時にデータを格納する場合に、()内にデータを指定します。 例えば、空の配列ARRAY1を生成するには、以下のように書きます。 ARRAY1=()例をもう一つ。データを３つ格納した配列ARRAY2を生成するには、以下のように書きます。 ARRAY2=("history" "japanese" "math") ■配列にデータを追加する。 配列へのデータの追加は以下のよ
型推論 - Wikipedia
型推論（かたすいろん、英: type inference）とはプログラミング言語の機能の1つで、静的な型付けを持つ言語において、変数や関数シグネチャの型を明示的に宣言しなくても、変数宣言における初期化のための初期値や、関数呼び出しにおける実引数などといった、周辺情報および文脈などから自動的に（暗黙的に）各々の型を決定する機構のこと。言語によってはtype deductionと呼ばれることもある。 推論に失敗するとその時点でエラーを報告できるため、少なくとも誤った型を用いることによるバグは回避できる。また、アルゴリズムの記述に集中できるのでプログラムの抽象度が上がるというメリットもある。型名が長大な場合に、型推論による省略によってコード全体の見通しをよくすることにもつながるが、一方で統合開発環境による支援（コードエディター上のツールチップなど）が得られない環境では、一見して型が分からないこと
Think Stats
本書は「プログラミングのスキルを統計の理解に役立てよう」というコンセプトで書かれたものです。数学的な観点から語られることが多い統計について、計算処理の観点から説明。実際にPythonのコードを示し、実データを分析しながら統計の基礎を解説しています。日本語版では豊富な数学関数ライブラリを提供するPythonの科学技術計算用モジュールNumPyとSciPyに関する解説を付録として追加。NumPy/SciPyが持つ統計関数の解説のほか、本書に登場した問題をNumPy/SciPyを使って解く方法を紹介します。Pythonで書かれたサンプルコードを使って実際に手を動かしながら統計が学べる、プログラマのための統計入門の決定版です。 はじめに 1章 プログラマのための統計的な考え方 1.1 第一子は出産予定日よりも遅れるか？ 1.2 統計的なアプローチ 1.3 全米世帯動向調査 1.4 テーブルとレコー
統計的テキスト解析(13)～テキストのクラスター分析～
図書館の図書は何らかの特徴別にグループ分けしており、新聞の紙面は総合、社会、経済、国際、生活、料理、スポーツ、地域などに分けられている。図書は図書館の管理者が、新聞の紙面は編集者たちがグループ分けしている。しかし、インターネット上の大量のテキストを何らかの特徴別にグループ分けする場合、すべての内容を読み、グループ分けすることは現実的ではない。また、人為的にグループ分けすることは読む側の主観の印象や認識などに左右されるため、客観的なグループ分けが求められている。 本稿では、テキストがどのグループに属するかに関する情報(外的規準とよぶ)を用いずにグループ分けする方法を説明する。このようなグループ分け方法をクラスター分析と呼ぶ。テキストのクラスター分析は、主に次のようなアプローチ多用されている。 (１)個体の特徴の情報に基づいて、平面や立体空間上で散布図を作成し、分布状況からクラスターの形成状況
MapReduce - naoyaのはてなダイアリー
"MapReduce" は Google のバックエンドで利用されている並列計算システムです。検索エンジンのインデックス作成をはじめとする、大規模な入力データに対するバッチ処理を想定して作られたシステムです。 MapReduce の面白いところは、map() と reduce() という二つの関数の組み合わせを定義するだけで、大規模データに対する様々な計算問題を解決することができる点です。 MapReduce の計算モデル map() にはその計算問題のデータとしての key-value ペアが次々に渡ってきます。map() では key-value 値のペアを異なる複数の key-value ペアに変換します。reduce() には、map() で作った key-value ペアを同一の key で束ねたものが順番に渡ってきます。その key-values ペアを任意の形式に変換すること
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
http://www.sat.t.u-tokyo.ac.jp/~omi/random_variables_generation.html
Computer smash
Google for Developers
Bret Victor - Inventing on Principle on Vimeo
http://kobitoapp.com/