アルゴリズムの勉強のしかた - きしだのHatena
この記事で、アルゴリズムの勉強はアルゴリズムカタログを覚えることじゃないよということを書きました。 プログラムの理論とはなにか アルゴリズムの勉強というのは、スポーツで言えば腕立て伏せや走り込みみたいな基礎体力を養うようなもので、「ソートなんか実際に自分で書くことないだろう」とかいうのは「サッカーは腕つかわないのに腕立ていらないだろう」とか「野球で1kmも走ることなんかないのに長距離の走り込みいらないだろう」とか言うようなものです。 Twitterでアルゴリズムの勉強とはなにかと尋ねられて、「アルゴリズムの基本的なパターンを知って、それらの性質の分析のしかたをしって、いろいろなアルゴリズムでどのように応用されているか知って、自分が組むアルゴリズムの性質を判断できるようになることだと思います。 」と答えたのですが、じゃあ実際どういう本で勉強すればいいか、ぼくの知ってる本からまとめてみました。
プログラマになるための勉強をしている人の前で話をしてきた - きしだのHatena
イデアルITスクールというところで、１時間ほど話をしてきました。 プログラマとしてやっていくために大事なことというテーマ。 資料を作らずに、というか構想すら練らずにやってしまったので、ここで整理とまとめと補足を。実際にこれをしゃべったというのではなくて、だいたいこんなことをしゃべろうとしてたという内容をかなり盛って書いてます。 当然ですが、プログラマの仕事はプログラムを書くことです*1。 プログラマとしてやっていくためには、どこで動くプログラムを書くか、なにをするプログラムを書くかということを意識することが大事です。 ということで、まずはプログラムが動くところがどう変わったかという話。 1970年代ころは、デバイスを動かすためのプログラムが多かったのではないかと。 あと、ここには書いてないけど、業務アプリはほぼメインフレームで動いてたと思います。 それが、1980年代くらいからパソコンが出
2010-11-25 - きしだのはてな - 技術力をあげたいプログラマが読んでおかないと話にならない本10冊
ここにあげた本じゃなくてもいいので、同じ分野でなにか読むとか、本に書いてあるほど詳しくなくてもそれなりに知識をもっておくべき本。 アルゴリズムクイックリファレンス 作者: George T. Heineman,Gary Pollice,Stanley Selkow,黒川利明,黒川洋出版社/メーカー: オライリージャパン発売日: 2010/04/26メディア: 単行本（ソフトカバー）購入: 11人 クリック: 656回この商品を含むブログ (72件) を見る まずはアルゴリズム。クイックって書いてあるけどぜんぜんクイックじゃないｗ。各言語で書かれた入門書を読んでもいいと思う。 実際のプログラムにアルゴリズムの知識を活かすということを知りたいならプログラミングコンテストチャレンジブックがおすすめ。 プログラミングの基礎 ((Computer Science Library)) 作者: 浅井健一
一意なテスト用文字列データを適当に生成する方法 - 2010-01-12 - きしだのはてな
プログラムを作成するときに、メッセージの文字列などを適当にそれっぽく生成したい場合があります。 そういうとき、とりあえずこういうプログラムが考えられます。 public static void main(String[] args){ String[] users = {"nowokay", "higayasuo", "t_yano"}; String[] pre = {"ところで", "じつは", "さて、", "なかんずく、"}; String[] msg = {"こんにちは", "はらへ", "おはよう", "ねる", "きたく", "ビールのむ"}; for(int i = 0; i < users.length * pre.length * msg.length; ++i){ System.out.printf("|%s|%s%s|%n", users[i / (pre.leng
過去の状態のスナップショットを取れるMap - 2009-04-24 - きしだのはてな
時間を指定して、その時点での状態を取れるようなMapを作ってみた。 何に使うかとかは考えてない。 こういった、データの世代別管理をして過去のある時点をスナップショットとして取得できるようなデータ構造は、扱うデータが巨大になってバックアップのためにシステムを止めれないというときに重要になったりしますね。 あと、データを変更せず追記する一方なので、ストレージの仕組みとして使うと、変更回数の制限があるSSDと相性がいいとか。 使うとこんな感じ。 public static void main(String[] args) throws InterruptedException{ VersionedMap<String, Integer> vm = new VersionedMap<String, Integer>(); vm.put("abc", 3); vm.put("aaa", 6); vm
ラムダ計算とチューリングマシンの違い 2009-04-13 - きしだのはてな
ぼくもYコンビネータがわかるようになるまではそうだったのだけど、Yコンビネータを使うとどのような処理ができるのかがよくわからなくて悩んでいる人が多いように思う。他の人のブログを見ても、名前をつけずに再帰ができるのがすばらしいとか書いてあったりするのだけど、それによってどういう処理ができるのかわからずにいた。 結論をいえばYコンビネータには、なにかの処理を便利にする能力はない。関数であらゆる計算ができるということが示せれば、あとは用なしだ。理論の礎としてうまってしまえばいい。 結局、Yコンビネータによってどのような処理ができるかというのは、ラムダ計算の要素のメリットをチューリングマシンの中に見出そうとしてるといえる。 ラムダ計算とチューリングマシンは、どちらも計算モデルという点では一致しているけど、全く違う。 無限であるか有限かの違いといってもいい。 チューリングマシンでは、データの量と処理
Yコンビネータなんか要らない - きしだのHatena
「計算論なんかチューリングマシンで十分だし、おれはチャーチじゃなくチューリングについていくぜ！Yコンビネータくそくらえ！」 という人もいるんじゃないでしょうか。 やっぱチャーチよりチューリングですよね。 という人のために、われらがチューリング先生がコンビネータを用意してくださっています。 Θ=(λx.λy.y(xxy))(λx.λy.y(xxy)) Groovyで書くとこうですね。 def th = {x -> {y-> y(x(x)(y))}}({x -> {y -> y(x(x)(y))}}) ためしにフィボナッチを。 > println th({f -> {n -> n < 2 ? n : f(n - 1) + f(n - 2)}})(7) Exception in thread "main" java.lang.StackOverflowError むむ、スタックオーバーフロー と
おとうさん、ぼくにもYコンビネータがわかりましたよ！ - 2009-04-09 - きしだのはてな
やっと、Yコンビネータが何を意味するものなのか、どういう意義があるのかがわかりました。 名前を使わず再帰ができますよ！というだけのものじゃなかったのですね。 まずλありき 関数の話をしたいのです。 そのとき、いちいち hoge(x) = x * 2 としてhogeを・・・、とか名前をつけて話を進めるのがめんどうなので、関数を値としてあらわすと便利ということで、λという値を定義するのです。 そうすると、上のhoge関数なんかはλ(x)(x*2)などとあらわせますが、引数をあらわすのに()を使うといろいろまぎらわしいので、 λx.x*2 のように表記します。 というのがλ。 このとき、λになにかわたされたら、引数としてあらわされる部分を単純におきかえます。 (λx.x*2)y とあったら、xの部分をyでおきかえて (λx.x*2)y → y * 2 となります。λの引数部分を与えられた引数で置
情報系の技術者に一冊だけ読んでもらうならこの本 - 2009-03-30 - きしだのはてな
さて、いろんな本を取り上げたのだけど、かなり広い範囲を取り上げたので、それぞれそれなりに高い本だし、読む時間もないし、そもそもどこから手をつけていいやら、とか思った人も多いんじゃないだろうか。 今回取り上げたような内容を、1冊にまとめたような本はないだろうか。 しかし、そんな都合のよい本は存在するのか。 と思ったら、あった。いい本が。 しかも、ちゃんと勉強できたかどうか判定できるし、勉強した証を発行してもらえる。そして、その証で職につきやすくなるかもしれない。 ということで、情報系の技術者が一冊読むならこの本。 やさしい応用情報技術者講座 2009年版 やさしい講座シリーズ 作者: 高橋麻奈出版社/メーカー: ソフトバンククリエイティブ発売日: 2008/11/29メディア: 単行本 クリック: 10回この商品を含むブログ (8件) を見る なんだ麻奈タンかよ、とか、やさしいシリーズか！と
プログラムを動かす環境の本 2009-03-25 - きしだのはてな
プログラムをどう動かすというか、どうやって命令を発行するかという本を挙げて、プログラムをどう書くかという本もあげた。 これで、Seasarカンファレンスでの話での本の紹介は終わりなのだけど、ブログのエントリとしては、どうやって実際にプログラムが動くかを理解できるような本がないと完結しない。 ということで、プログラムを動かす環境の本を挙げることにする。 まだ読んでない本がほとんどなので、こういった分野の勉強も必要だという程度の意味でしかないけど。長いことプログラマやってれば、なんとなく知ってる分野ばっかりになってるはずだけど、系統的に勉強しなおすのもいいと思う。 このあたりの分野は「タネンバウム読んどけ」でだいたい大丈夫みたいなんだけど、いきなり読むのはつらいので、そこにたどりつくまでの本を。 コンピュータの仕組み まず、プログラムを動かす中心となるCPUとか周辺ハードウェアの本。パイプライ
プログラムの動かし方の本 - きしだのはてな
Seasarカンファレンスで、基礎としてプログラムの動かし方であげた本。と、それに加えて挙げれなかった本。 ちなみにSeasarカンファレンスでの内容はid:tanamonがまとめてくれてる。というか、手書きスライドの書き起こしをしてもらってます。 「手書きで書く→ソーシャルに清書してもらう」という、新しいプレゼン手法が生まれました！ 差のつく勉強法200のメモ - tanamonの日記 プレゼンや以前のエントリでは、プログラムというのは計算論と意味論に分かれると書いたけど、プログラム意味論という分野と混同してへんな議論になっちゃうので、「プログラムをどう動かすか」と「プログラムをどう書くか」に分かれるとします。命令的な側面と宣言的な側面だと言ってもいいかもしれない。今回は命令的な側面について。 まずは、基礎となる数学、離散数学について。 やさしく学べる離散数学 作者: 石村園子出版社/メ
プログラムの書き方の本 - きしだのHatena
今回は、プログラムの書き方の本。プログラムの宣言的な側面を扱うための本とでも言うか。id:t_yanoおまたせ。 ただ、こっち側はほんとに勉強を始めたばっかりなので、ちょっと目を通しただけで読んでない本もばかりだし、自分でもちゃんとわかってない部分も多い。そういうのを割り引いて見てもらえれば。 で、まずは、論理。プログラム書かなくても読んでほしい。 論理学 作者: 野矢茂樹出版社/メーカー: 東京大学出版会発売日: 1994/02/18メディア: 単行本購入: 24人 クリック: 175回この商品を含むブログ (80件) を見る これは全部読んだ。 この本読むと、かしこさが15くらいあがる。日本語がうまくなる。考えるとき、間違った結論をださなくなる。議論するとき、議論の骨子をみつけて、議論からそれる部分を省くことができるようになる。 1章「命題論理」2章「述語論理」を読めば、あとはヤル気が
観光客のように数学や物理を勉強する - きしだのHatena
最近いろんなことを中途半端に勉強して思うのは、なんだか観光客のようだなぁということだ。 現実的な問題として、専門家=その土地の住民にはなれない。 勉強するにしても、その分野の雰囲気を味わうことができるくらいで、まさしく観光のようだ。 そしてその観光地でパシャパシャ写真をとって怒られているのが僕だ。 その観光地も分野によっていろいろと特色がある。 文学なんかは大都会。住民も観光客も入り乱れている。中には電車で通りかかっただけの人もいる。住民に見えても実は最近引っ越してきてたり。ふらふら立ち寄ったとしても、だれもぼくを気にしない。 古くからの住民はひっそり居をかまえていて、住む世界が違う。 哲学はインドのように、一度ハマると帰ってこない人もいると聞く。という偏見。 数学などは、観光客のちらかすゴミに辟易しているようで、ちょっとでも変なものを持ち込んだら、こっぴどく怒られる。 観光スポットも地味
HadoopでのMapReduceを気軽に試すサンプル 2009-02-15 - きしだのはてな
Googleの分散処理技術であるMapReduceを、そのオープン実装のHadoopを使って試したいと思っても、なんか設定がめんどくさそうで二の足を踏んじゃう人は多いはず。 そこで、並列計算をせずにサーバーなしで動かせるサンプルを作ってみた。 ただ、設定は不要なんだけど、Windowsの場合はCygwinがやっぱり必要で、PATHにCYGWIN_HOME\binを追加しておく必要がある。残念。 今回は、Javaソース中のimportされたクラスを数えるっていう処理をMapReduceでやってみる。 Hadoopは、こっからダウンロード。0.17.2.1を使った。 http://hadoop.apache.org/core/releases.html コンパイル・実行には、解凍してできる次のJARをクラスパスに追加しておく必要がある。 HADOOP_HOME/hadoop-0.17.2.1-
計算量を具体的に見てみる 2009-01-06 - きしだのはてな
アルゴリズムの話では、計算量の解析がかかせません。 計算量はオーダー記法で表されますが、これは、データの入力量に対してどのくらい時間がかかるかをあらわしたものです。 こういった話はどのアルゴリズムの本にも載ってるはずですが、具体的にどのようなプログラムを書くとそのオーダーになるかという記述はあまりありません。 ということで、やってみました。 計算時間表示のための共通処理を行うクラスは、一番最後に書いてます。 O(1) 計算時間がO(1)のアルゴリズムは、処理が入力の量によらない場合です。 配列の要素のアクセスや、ハッシュテーブルによるデータ検索、連結リストへの追加削除などがこれにあたります。 コードには入力量でのループが含まれません。 public class O1 extends ViewCompFrame{ @Override void compute(int n) { proc();
[機械学習]サポートベクターマシンの本 - 2008-07-15 - きしだのはてな
うちにある本で、サポートベクターマシン(SVM)について書いてある本をあげてみます。 まずは、これ。機械学習ってなんなの？という人におすすめ。パーセプトロンからSVM、ニューラルネットワークときて、そうやってできた学習機械の評価方法についても書いてあります。 フリーソフトでつくる音声認識システム パターン認識・機械学習の初歩から対話システムまで 作者: 荒木雅弘出版社/メーカー: 森北出版発売日: 2007/10/01メディア: 単行本（ソフトカバー）購入: 45人 クリック: 519回この商品を含むブログ (39件) を見る SVM・カーネルに関しては記述が軽く、これも機械学習の入門書。けど、学習機械を組み合わせるブースティングなどの話が書いてある。 パターン認識と学習の統計学―新しい概念と手法 (統計科学のフロンティア 6) 作者: 甘利俊一,麻生英樹,津田宏治,村田昇出版社/メーカー
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
