2016年10月29日土曜日

「Land of Lisp」7章の "dot->png"関数をSBCLで書く

「Land of Lisp」を読み始めている。

第7章まで読み終わったのだが、この章の最後の方(P.115)に、DOTファイルをPNGファイルに変換する dot->png という関数が紹介されている。この本ではLISP処理系にはCLISPを使っているので、この関数の中でシェルを呼び出す部分もCLISP独自の関数を使っている。

私はLISP処理系にSBCLを使っているので、以下にSBCLでdot->png関数を書いてシェルを呼び出す方法を備忘録として書いておく。

(defun dot->png (fname thunk)
  (with-open-file (*standard-output*
                   fname
                   :direction :output
                   :if-exist :supersede)
    (funcall thunk))
  (sb-ext:run-program "/bin/sh"
                      (list "-c"
                          (concatenate 'string "dot -Tpng -O "
                                       fname))))

sb-ext:run-program の後に、呼び出したいプログラムへのパスを文字列にしたものと、そのプログラムに渡すコマンドを文字列にしたリストを与えればいいのだが、-cオプションも書かなければいけないことがわからなくて、かなり悩んでしまった。シェルスクリプトは全然知らない。

-c string

-c オプションが指定されると、コマンドが string から読み込まれます。 string の後に引き数があれば、これらは 位置パラメータ (positional parameter: $0 から始まるパラメータ) に代入されます。
(出典:Man page of BASH

-cのようなオプションはコマンドとは別の文字列として渡す必要がある。

(list (concatenate 'string "-c dot -Tpng -O " fname))

などのようにオプションをコマンドの文字列に含めてしまうとうまくいかない。

また、このdot->png関数には誤植ではないが冗長と思われる箇所があったので指摘しておく。

本書のP.115では

(defun dot->png (fname thunk)
  (with-open-file (*standard-output*
                   (concatenate 'string fname ".dot") ;; (1)

  (以下省略)

となっているが、(1)の部分は、

(defun dot->png (fname thunk)
  (with-open-file (*standard-output*
                   fname ;; (1)'
(以下省略)

と、(1)’のようにfnameだけでよいと思う。

graph->pngを呼び出す際に、

(graph->png "wizard.dot" *wizard-nodes* *wizard-edges*)

というようにwizard.dotと拡張子まで含めて引数として渡しているため、(1)のコードでは出力されるDOTファイル名がwizard.dot.dotとなってしまう。

2016年10月19日水曜日

文系プログラマーが算数・数学をやり直すための6冊+α

数学に自信がない人は小学校の頃から苦手意識があった人が多いのではないでしょうか?

私は特に文章問題が大の苦手でした。

国語の現代文の読解問題は得意だったのに、算数の文章問題となると頭が真っ白になって何も考えられなくなり、ひどい点数ばかりとっていて、その苦手意識は中学校、高校、大学と変わりませんでした。

大学卒業後、あらゆることに対して自信を失くしていた私は、自信を取り戻すには何か苦手なものを克服すればいいんじゃないかと思い、Amazonとかのレビューを参考にして、良さそうな参考書は片っ端から買って算数・数学をやり直してみることにしました。

その甲斐もあって数学大好きとまではいきませんが、算数・数学に対する苦手意識、特に文章問題に対する苦手意識はほぼ解消しました(生きていくことに自信がないのは相変わらずですが)

特に、数学の復習と同時に始めたプログラミングの勉強は、自分で考えることを身につけるのに大変役に立ちました。本を読んで演習問題を解くときに、最初は、模範解答通りのコードが書けないとダメだ、と変に潔癖なところがあったのですが、ある時から「なんだ、自分の考えたコードでもいいんだ」となり、さらに「自分のコードのほうがいいじゃん」と思えるようになってから、プログラミングが楽しくなってきました。もちろん勘違いしていたこともありますが(笑)。そしてこの頃から、数学の文章問題に対しても、問題文を読み、そこから判ることと判らないことを抜き出して、式に書き出す、ということが苦ではなくなってきました。

また、目標があったほうが続けられる気がしたので、基本情報技術者試験に挑戦することを決め、一発で合格できました。文系人間だと思っていた私が、理系寄りの資格に合格できるなんて思ってもみませんでした。

自分がやってみて感じたのは、大人になってからやってみると、学生のときに理解できなかったことが意外と理解できるようになっているものだ、ということです。歳をとっていい感じでいい加減になったのだと思います(笑)。

今はわかりやすい参考書がたくさん出版されているので、独学でも教科書に出てくる基礎的な数学を理解できるようになるくらいなら十分可能だと思います。

そこで今回は、自分が勉強する際に使ってみてよかった算数・数学の本を6冊紹介します。



【小学生レベル】


「この算数、できる?」 計算編・図形編 小学校の算数を楽しむ会 (中経の文庫)

この二冊で小学校1年生から6年生までの算数が復習できる優れもの。

四則計算、単位、重さ、時間、図形、面積・体積、表・グラフ、百分率、比例など基礎的なことを手取り足取り本当に丁寧に説明してくれます。

一通り説明した後すぐに練習問題が各項目ごとに設けられているので、飽きずに勉強が続けられました。

とにかく小学校の算数が数学の基礎だと思うので、この本を何回でも苦手意識がなくなるまでしっかりと勉強してください。





【中学生レベル】


「語りかける中学数学」 高橋一雄 ベレ出版

これもたった一冊で中学校の三年分の数学が復習できるというとても便利な参考書です。

結構ぶ厚いのですが、その代わりにきちんと省略なしで計算過程が書かれているで、「どうしてあの式からこの式になるのか」ということで悩まなくて済むという、独学する人には至れり尽くせりな本です。

そして、この段階で特に声を大にして言っておきたいのは、「等式の変形」についてきちんと理解しておくべきだ、ということです。

自分は四則計算と並んでもっとも大切な事項だと思っています。

これが理解できれば、計算過程が省略してある数式も読み解くことが出来るようになるからです。

この本を最後までやり通せれば数学に対する苦手意識はほとんどなくなっていると思います。





【高校生レベルに行く前に】


「はじめまして数学 リメイク」 吉田武 東海大学出版部

今までの復習プラス数学の面白さや奥の深さを、やさしい文章で教えてくれる名著。

無限、素数、ベクトル、虚数、場合の数、帰納法などかなり高度な話題についても、一つ一つ順を追って丁寧に説明してくれます。

「この算数、できる」と「語りかける中学数学」をやってからのほうが、この本を面白いと感じることが出来ると思ったのでここで紹介しました。

時間が無い人はこのシリーズだけでも読んだほうがいいというくらいオススメです。





【高校生レベル】


「語りかける高校数学 Ⅰ ・ Ⅱ」 高橋一雄 ベレ出版

これを全部やり遂げるのはかなり時間が掛かりますが、丁寧な説明は「語りかける中学数学」と変わりが無く、きちんと公式の証明などの計算過程が書かれているので、「語りかける中学数学」をやり遂げた人ならば独学でも十分理解できると思います。





「長岡先生の授業が聞ける高校数学の教科書」  長岡 亮介 旺文社

高校数学に関してはこの長岡先生の本のもお薦めです。

「教科書ってこんなにわかり易かったんだ」と思うくらいよくできています。

数学Ⅰ・Ⅱ・Ⅲ・A・B・Cの全部が一冊にまとまっていて、長岡先生がこのテキストを解説している講義の音声ファイルも付属DVDに収録されています。また、DVDには教科書内の問題に対する詳解やちょっと難しめの章末問題もPDFファイルで収録されているので、自分のレベルに合わせた使い方が可能です。

ほとんどの定理にはきちんと証明があるので、理解できなくて悩むことはそれほどないと思います。ただ、教科書の性質上、以前学習した箇所は知っているものとして説明が省かれているため、解説があっさりしすぎていて「どうしてそうなるのか?」がわかりづらい箇所もあるので、そのときは関係有りそうなところを復習したり、ネットを検索したり、Yahoo知恵袋などを参考にしてなんとか理解しています。

書店で予備校系の参考書と同じ箇所について解説を比較してみたのですが、私には長岡先生の教科書の解説のほうがわかり易かったです。

完璧な参考書なんて無いのですから、わかりにくいところはネット上の情報で補いつつ、この一冊を何回も繰り返す方が力がつくと思います。

最後に誤植を見つけたので指摘しておきます。

数学Ⅱの対数関数のところで、p.161 問21の解答が教科書のp.247にあるのですが、その解答の最後から二行目に

logaM^r = (logaM)^r

と書かれていますが、正しくは

logaM^r = (logaM)・r

です。PDFファイルの詳解の方は正しく書かれています。





【プログラマーのための基礎数学】


「これだけはおさえたい 文系プログラマーの数学知識 基礎の基礎」 メディックエンジニアリング・谷尻豊寿・谷尻かおり 技術評論社

上記の本で一通り数学を復習しても、その知識をどのようにしてプログラミングに結びつけたらいいのか分からない、という悩みに答えてくれるのがこの一冊です。

単なるの数学の復習ではなく、身近な生活のなかで数学がどのように役立っているのかということを、デジタルカメラのスマイルシャッターの原理などを通じてわかりやすく説明してくれます。

日常よく使っているデジタル技術を例に挙げているので最後まで興味をもって読み続けられました。

数学をやり直そうと意気込んで参考書を買ってみたけど、最初の方だけやってあとで読む状態になってしまうことが一度や二度ではない私でも、最後まで読み終えることができるくらいのページ数と内容です。

基数変換、三角関数、微分・積分、統計、確率、行列などの重要項目の基礎を一通り丁寧に説明していて、基本情報技術者試験を受けようと思っている人が、本格的に勉強を始める前に読んでおくというのもいいかもしれません。

数学とプログラミングとをつなげくれるいい本だと思います。

ただし、プログラムを少し突っ込んでやり始めるとアルゴリズムを勉強することになると思うのですが、そのアルゴリズムの計算量の算出に必要な対数が紹介されていないのがマイナスかな。





【最後の一冊】


「プログラマーの数学」 結城浩 ソフトバンクパブリッシング

書名の通り、プログラミングをする上で欠かせない2進法、論理学、再帰、階乗、順列、組み合わせなどの数学知識について図をふんだんに用いて説明しています。

この本で一番よかったのは、対数についての説明が素晴らしく分かりやすかったことです。色々な本を見ましたがこの本が一番スッキリと理解できました。

これだけでも買う価値があると思います。





【番外】


アルゴリズムとデータ構造(第2版) (情報工学レクチャーシリーズ) 藤原 暁宏 森北出版

私が持っているのはこの本の第1版ですが、計算量などの説明がとてもわかりやすく、アルゴリズムを基礎から学びたい人にはオススメです。





「初歩から学べて合格できる 真図解 基本情報技術者」 福嶋宏訓 日本経済新聞社

この本のいいところは「なぜそうなるのか?」についてちゃんと理由が書かれているところです。

基数変換の説明は抜群にわかりやすかったです。

図表もわかりやすくてオススメできます。

「初歩から学べて合格できる」という売り文句は伊達じゃありません。

私の基本情報技術者試験の参考書はこの本だけで大丈夫でした。

順列のアルゴリズム

という3個の要素を持つリストから2個取り出す順列()は

の6通りある。

これを先頭要素であるを含んでいると、を含まないに分けて考えてみる。

まずを含む方からを除いてみると、となる。このは、から先頭要素を取り除いた残りのから一つを取り出すときの順列である。そして、の先頭に挿入したものであり、また、の右隣りに挿入したものとなっていることがわかる。も同様である。このことから、の結果には、先頭要素を取り除いた残りのリストから個を取り出す順列の結果のそれぞれに、取り除いておいた元のリストの先頭要素を左から順に位置を変えて挿入したものが含まれているといえる。

次に、を含まない方を見てみると、は、から2つを取り出すときの順列となっている。

これを関数(第一引数として挿入する値、第二引数としてリストを取り、値を左から順に異なる位置に挿入したリストのリストを返す。関数(渡された関数をリストの各要素に適用した結果をリストにまとめる関数)を使って式に表してみると以下のようになる関数はリストのリストを返すので、それをした結果はリストのリストを要素として持つリストになる。そのため実際のコードを書くときには、一番外側のリスト減らすためにconcat関数を適用する必要があるが、ここでは見やすさのために省略してある。最後の方にHaskellで書いたコードにはconcat関数を使ってある)

を結果のリストに置き換えると

となる。

これを一般化してみる。

はリストの先頭要素

この式を基にして、n個の要素を持つリストで考えた場合、(n個からr個取り出す順列)を求めるアルゴリズムを文章化すると次のようになる。

  1. 先頭要素を除いた個のリストから個を取り出す順列を作る。そして、それぞれの結果に対して最初に取り除いておいた元のリストの先頭要素を挿入する。
  2. 次に、先頭要素を除いた個のリストから、今度は個を取り出す順列を作る。の場合とは異なり、この結果には取り除いておいた先頭要素は挿入しない。
  3. のリストとのリストをつなぎあわせたリストが最終的な結果となる

手順およびはそれぞれ再帰処理となるが、その際の場合分けは次の通り。

  • が空リストのときは空リストを返す。
  • のときは選び方は通りあるので、引数として受け取ったリストの各要素をそれぞれリストにして、ネストしたリストを返す。(例: ならにして返す)

これをHaskellで書くとこうなる。

-- 引数nはリスト ex:[1,2,3,4,5]
-- 引数rはnから取り出す要素数

nPr :: [a] -> Int -> [[a]]
nPr [] _ = []
nPr n 1 = map (:[]) n
nPr (x:xs) r = (concat $ map (insertion x) $ nPr xs $ r - 1) ++ (nPr xs r)

insertion :: a -> [a] -> [[a]] 
insertion x xs = [insertion' x xs n | n <- [0..(length xs)]]

insertion' :: a -> [a] -> Int -> [a]
insertion' x xs n = take n xs ++ [x] ++ drop n xs

ghciで5個から3個を取り出す順列を求める

ghci> nPr [1..5] 3
[[1,2,3],[2,1,3],[2,3,1],[1,3,2],[3,1,2],[3,2,1],[1,2,4],[2,1,4],[2,4,1],[1,4,2],[4,1,2],[4,2,1],[1,2,5],[2,1,5],[2,5,1],[1,5,2],[5,1,2],[5,2,1],[1,3,4],[3,1,4],[3,4,1],[1,4,3],[4,1,3],[4,3,1],[1,3,5],[3,1,5],[3,5,1],[1,5,3],[5,1,3],[5,3,1],[1,4,5],[4,1,5],[4,5,1],[1,5,4],[5,1,4],[5,4,1],[2,3,4],[3,2,4],[3,4,2],[2,4,3],[4,2,3],[4,3,2],[2,3,5],[3,2,5],[3,5,2],[2,5,3],[5,2,3],[5,3,2],[2,4,5],[4,2,5],[4,5,2],[2,5,4],[5,2,4],[5,4,2],[3,4,5],[4,3,5],[4,5,3],[3,5,4],[5,3,4],[5,4,3]]

length関数で何通りあるか数える

ghci> length $ nPr [1..5] 3
ghci> 60

順列の公式: で答えが合っているか調べる

ghci> (product [1..5]) `div` (product [1..2]) 
ghci> 60

2016年10月16日日曜日

組み合わせのアルゴリズム

という3個の要素を持つリストから2個取り出す組み合わせ()は

の3通りある。

これをに分けて考えてみる。

まず最初の2つのリストは、元のリストから先頭の1を取り除いた残りのリストから1個を取り出す組み合わせ()の結果であるのそれぞれ要素に、取り除いておいた元のリストの先頭要素を加えたものとなっていることがわかる。

次に、は、元のリストから先頭要素を取り除いた残りのリストから2個を取り出す組み合わせ()の結果であるとなっている。

これをHaskellの(引数として渡された関数をリストの各要素に適用して、その結果をリストにまとめる関数)と(リストに要素を追加する関数)を使って式に表してみると以下のようになる。

を結果のリストに置き換えると

となる。

これを一般化してみる。

はリストの先頭要素

この式を基にして、n個の要素を持つリストで考えた場合、(n個からr個取り出す組合せ)を求めるアルゴリズムを文章化すると次のようになる。

  1. 先頭要素を除いた個のリストから個を取り出す組み合わせを作る。そして、それぞれの結果に対して最初に取り除いておいた元のリストの先頭要素を加える。
  2. 次に、先頭要素を除いた個のリストから、今度は個を取り出す組合せのリストを作る。の場合とは異なり、この結果には取り除いておいた先頭要素は加えない
  3. のリストとのリストをつなぎあわせたリストが最終的な結果となる

手順およびはそれぞれ再帰処理となるが、その際の場合分けは次の通り。

  • またはのときは空リストを返す。
  • のときは一つの空リストを要素とするリストを返す。
  • が空リストのときは一つの空リストを要素とするリストを返す。
  • のときは選び方は一つなので、引数として受け取ったリストをリストにして返す。(例: なら にして返す)
  • r = 1 のときは選び方はn通りあるので、引数として受け取ったリストの各要素をそれぞれリストにして、ネストしたリストを返す。(例: ならにして返す)

これをHaskellで書くとこうなる。

-- 引数nはリスト ex:[1,2,3,4,5]
-- 引数rはnから取り出す要素数
nCr n r
    | r < 0 = []
    | length n < r = []  
    | r == 0 = [[]]
    | length n == r = [n]
    | r == 1 = map (:[]) n
nCr (x:xs) r = (map (x:) (nCr xs $ r - 1) ++ (nCr xs r)

ghciで5個から3個を取り出す組み合わせを求める

ghci> nCr [1..5] 3
ghci> [[1,2,3],[1,2,4],[1,2,5],[1,3,4],[1,3,5],[1,4,5],[2,3,4],[2,3,5],[2,4,5],[3,4,5]]

length関数で何通りあるか数える

ghci> length $ nCr [1..5] 3
ghci> 10

組み合わせの公式: で答えが合っているか調べる

ghci> product [1..5] `div` (product [1..3] * product [1..(5 - 3)]) 
ghci> 10