< ご注意 >
・難易度に関しては完全に個人の主観となります。
参考までに僕個人のスペックを記載しておくと、高校2年の数2Bまで終わってるくらいのレベル感です。アカデミックな数学はパッパラパーです。
・また、各Exerciseの難易度に関しては そのExerciseの所まで勉強した時点でのスキルセット・理解度を想定した難易度を書くようにしています( つまり、既に後の章も勉強して記述に慣れた状態での難易度ではないので、前の章の★3つと後の章の★3つのレベル感が大きく異なります )。
第1章 難易度リスト
第2章 難易度リスト
第3章 難易度リスト
第4章 難易度リスト
第5章 難易度リスト
1.1 プログラムの要素
1.1.6 条件式と述語
1.1 ★ (これまでの部分ちゃんと読んでればしゅんころ)
1.2 ★★ (見た目程怖くない.括弧の組み合わせに慣れるには良い問題)
1.3 ★★ (これまで学んだ部分の応用)
1.4 ★★ (これまで学んだ部分の応用)
1.5 ★★★ (両方のパターンの処理を丁寧に追う。紙に書くのも良い)
【概観】
・括弧を使った演算に慣れる意味合いで、ちゃんと問題を解いておいた方がよい。
・特にifとかcondとかに関しては最初のうちは慣れないと括弧の数を間違えて「???」となるので、両者については繰り返し演習を積んだ方がよい。
—
1.1.7 例: Newton法による平方根
1.6 ★★ (教科書を読んで原理をしっかり理解すること)
1.7 ★★★ (教科書を読んで原理をしっかり理解すること)
1.8 ★★ (一度原理さえ理解してしまえば実はそこまで難しくない)
【概観】
・「最初に予測値を立てる→実際の値を確認する→予測値と値の平均値を取る→平均値を次の予測値とする」
これを 予測値と実際の値との変化が十分小さくなるまで実行し続ける という考え方、及びそのSchemeにおける実装方法をここでしっかり理解しておく必要がある。
・上記の概念は後の節を解いて行く上で度々出てくるので、ここを面倒くさいからと言って軽く流すと、一章のもうちょっと後の場所で爆死します。
—
1.2 手続きとその生成するプロセス
1.2.1 線形再帰と反復
1.9 ★★★ (再帰と反復の理解度が重要。最初は紙にプロセスを書いてみよう)
1.10 ★★★★★ (理解していても複雑。泣きべそかきながら紙にプロセスを書こう)
【概観】
・滅茶苦茶大事な所です。ここを理解せずに進むと後の章で必ず爆死する。理解できるようになるまでそれなりの時間がかかるので覚悟すること。
・最初のうちは よほど頭が良い人でなければまず頭の中でイメージできず混乱するので、面倒でも紙に書きながらやった方が良い。
・リソース
・慣れるとどんな感じで再帰が起こるかイメージがつくようになってくる。
1.2.2 木構造再帰
1.11 ★★★★ (反復の独特の書き方に慣れるまでは苦労する)
1.12 ★★ (何を引数として取り何を返すか考えよう)
1.13 ★★★★ (数学の証明的な要素が強い)
【概観】
・線形再帰と線形反復の違いに慣れるの大事。
このあたりだけだと、何故線形再帰が線形反復より悪いのかまだ若干ぼんやりしてるけど、すぐにわかるので もし一章を進めていく中で両者の違いが分からなくなってきたら戻ってちゃんと学習しよう。
・黄金比、count-changeは後々何度か出てくるので、しっかり写経して理解しておくことをオススメする。
—
1.2.3 増加の程度
1.14 ★★★★ (慣れるまでイメージが難しい。しっかり紙に書くこと)
1.15 ★★★ ( 1.1.7の考え方を理解していることが前提 )
【概観】
・「スペース」と「ステップ数」の違いを理解することは、線形再帰と線形反復を理解する上での大きな鍵。ここで「スペース」「ステップ数」と言われて「はて何のことか」と感じた場合は前の節に戻って、必要に応じてWebで調べてしっかり理解する必要がある。
・1.15が分からなかった人は一旦1.1.7に戻ること。僕のように理系ではない人は 一瞬sinとかにビビると思うけど、これは数学的な複雑さから来る類の難しさではない。
—
1.2.4 べき乗
1.16 ★★★ (反復プロセスに慣れるための良問)
1.17 ★★★ (面倒だけど問題を丁寧に読み解けばできる)
1.18 ★★★★ (不変量のイメージ+それをコードに落とし込むのが割と複雑)
1.19 ★★★★ (変換のイメージが持てれば。問題を丁寧に読む必要あり)
【概観】
・「こうすればこれだけのオーダーの実行ステップをこれぐらいまで押さえることができますよ」というのを理解する上で大事な部分。
—
1.2.5 最大公約数
1.20 ★★★★ (紙に書きながらやると理解が早い)
【概観】
・「どうせ問題一つだけだし、面倒だから飛ばしてもいいっしょ」→×。
GCDが後の部分で何度か出てくるので、面倒でも丁寧に読み込んでおいた方が良い。
・正規順序、作用的順序がわからない場合は一度戻って必ず確認すること。
—
1.2.6 例: 素数性のテスト
1.21 ★ (しゅんころ)
1.22 ★★★ (runtime準備するのがちょっと面倒)
1.23 ★★★★
1.24 ★★★★
1.25 ★★★★
1.26 ★★★
1.27 ★★★
1.28 ★★★★
【概観】
・使っている処理系によっては「runtimeが無いよ」って怒られるやつもあるので、その場合はもじもじしながらGoogle先生に聞いてみよう。
・考察、時間計測がメインとなるので割とヘビーです。モチベーションキラーになりうるので まとまった時間で一気に解いちゃった方が良いかも。
—
1.3.1 引数としての手続き
1.29 ★★ (見かけの数式の割に結構普通に解ける)
1.30 ★★ (線形再帰を理解していれば臆することはない)
1.31 ★★★ (書き換えが面倒なくらい)
1.32 ★★★★ (書き換えが面倒なくらい)
1.33 ★★★
【概観】
・線形反復 <--> 線形再帰的な問題が多いので 両者を自在に書き換えられるようになるための良い練習になる。
・楽しくなってきました。
—
1.3.2 lambdaを使う手続きの構築
1.34 ★★ (ゆっくりと処理を追っていけば解ける)
【概観】
・lambdaきました。
・正直この段階ではlambdaに書き換えるメリットがよくわかりませんが、2章でmapを扱うあたりになってくると重宝するのでお楽しみに。
—
1.3.3 一般的方法としての手続き
1.35 ★★★ (不動点を理解していれば割と楽)
1.36 ★★★
1.37 ★★★ (“逆”の方から考えればよい)
1.38 ★★★ (まずは「数列」をつくるところから)
1.39 ★★★ (符号が「+」じゃなくて「-」だから気をつけて)
【概観】
・平均緩和法、不動点探索が要になってくるので、この二つの概念をしっかり理解すること。
・不動点探索に関しては、Newton法を抽象化したものであり、これを使用して実に様々な問題が解けるようになっている。ここから手続き抽象の素晴らしさが伺える。
—
1.3.4 値として返される手続き
1.40 ★★
1.41 ★★★★ (地味に面倒くさいので、紙に書くのをおすすめ)
1.42 ★ (しゅんころ)
1.43 ★★
1.44 ★★ (問題自体は単純。「平滑化」に関してはGoogle先生)
1.45 ★★★
1.46 ★★★ (ちょっと面倒くさいくらい)
【概観】
・基本的に教科書の内容を写経していれば解ける内容になっている。
・ただ、地味に写経する量が多いのでちょっと時間がかかる。
・lambda式特有の書き方に慣れるまではちょっと苦戦する。
・今のところ、やはりまだlambda式を使うメリットがいまいちわからないが、lambda式の真価が発揮されるのは二章からなので期待。
Written by Nisei Kimura ( 木村 仁星 )
