0から始める 東大情報理工 創造情報学専攻 修士 対策[夏院試](その2)
本記事は、東大情報理工 創造情報学専攻 院試験 対策に関しての記事となります。記事全体が長くなるので、内容に応じ数パートに分けて記事を作成しています。
本記事はそのうちの$${2}$$番目の記事であり、以下の事柄について記述しています。
一般科目[プログラミング]の対策法
それでは、記事本体の内容に入ります。
2.一般科目[プログラミング]の対策法
この章では、試験科目のうち、対策がなかなか取りづらい科目の一つである
一般科目[プログラミング]
に関する対策や勉強法について紹介させて頂きたく思います。
早速、本題に入っていきましょう！
唐突ですが、皆さんは「プログラミング」という言葉を耳にしたとき、どういったイメージを持たれるでしょうか？
「ハッカーが使ってるなんかすごい難しいやつ」
というようなイメージを持たれる方が多いのではないでしょうか。
いいえ。そんなことはありません。
プログラミングは思っている以上に簡単です。
ある程度の水準のタッチタイピング技術さえあれば、基本的な処理をプログラミングで実現する上で必要なことは、せいぜい30個程度の英単語で構成される基本文法を覚え、それを適切に組み合わせることだけです。その気になれば、数日もあれば基本的なコードを書くことは可能です。
プログラミングが上記のような性質を持っている以上、プログラミング試験で問われることも、基本的な事柄の組み合わせだけで解答できるようになっていることがほとんどです。
ですが、いくつかの英単語と基本文法を覚えるだけで、プログラミングの試験に対応できるか？と聞かれたら、残念ながら答えはNOです。
なぜなら、プログラミング試験において上記の事柄はあくまでも前提に過ぎず、主に問われる能力が他にあるからです。
それは、以下に述べる「アルゴリズム」に関する理解 です。
問われる「アルゴリズム」の実装能力と正確性
では、一体「アルゴリズム」とはどのようなものなのでしょうか？
それは、
「プログラムにより決定される、計算機上での計算実行手順のプロセスのフロー」
のことを指します。
同じ課題に対してコードを記述する上でも、十人十色、さまざまな書き方があると思います。この際、どのような書き方をするかによって、そのプログラムの使用するメモリ領域や実行時間速度は大きく変わってきます。
イメージをつかむ上では、具体例があった方がわかりやすいと思うので、以下のような問題を考えてみましょう。
Question.
自然数nが与えられる。
1からnまでの自然数の総和をSとするとき、Sを求めよ。
以下の二つは、いずれもQuestionに対する解答コードですが、その実行速度には大きく差があります。具体的には、前者は$${n}$$に比例した実行時間を要するのに対し、後者はnに依らず常に一定の実行時間で済みます。
$${n}$$が小さいうちはその差は分かりにくいのですが、nが$${10^7や10 ^8}$$といった非常に大きい値になってくるとその差は絶望的なまでに大きくなります。
[Pythonによる実装例1]
def func1(n : int) -> int:
s = 0
for i in range(1, n + 1):
s += i
return s
[Pythonによる実装例2]
def func2(n : int) -> int:
return n * (n + 1) // 2良いプログラミングを行う上で、アルゴリズムが必要不可欠な要素であることがなんとなくわかっていただけたでしょうか。
これをやれば大丈夫！教材2選
では、アルゴリズムを学ぶ上でおすすめの教材2つを紹介します。
それは、
(1)理論学習 → アルゴリズムイントロダクション第3版 [上巻/下巻]
(2)実装練習 → プログラミングコンテスト攻略のためのアルゴリズムとデータ構造
です！
これらを両方読みさえすれば、プログラミングの試験で困ることは事実上ないといっても過言ではないと思います。
それでは、順にその進め方について説明していこうと思います。
(1)理論学習
何かを新しく学ぶ上で、一番難しいことは、おそらくその対象を体系的に学ぶための教科書を探すことだと思います。プログラミングにおけるアルゴリズム手法においてもそれは例外ではないです。しかし、闇雲に探したところで、世に溢れる幾多の教科書の中から、そのような要望を満たす本を見つけ出すことは難しいです。
そこで、幾つかアルゴリズムに関する教科書を読んで、筆者が最も良かったと感じた教科書を以下に紹介します。
それは、
の2冊です。
そこそこ値が張りますが、MITで標準教科書として使用されているだけあって、それに見合うだけの内容が詰め込まれている名著です。また、ここで学んだ内容は専門科目においても役立つ内容ですので、頑張って読み進めると後々とても役に立ちます。
難易度に関しては、簡単過ぎず難し過ぎずといったところで、2冊合わせて1.5~2ヶ月くらいで読み終えることができるかと思います。
（例外的に、教科書の一部には☆がついている箇所があり、この箇所は難しいです。ですが、この部分は内容が高度で理解するのが大変な上に、読まなくても大筋の理解に影響はないので、興味があって読みたい場合以外は、飛ばしてしまって良いと思います。）
(2)実装練習
さて、理論的な学習を終えた上で次に大切なことは、そこで得た知識や応用をコードとして具現化する練習を積むことです。
頭では理解していても、いざそれをコーディングしてみようとすると、意外と詰まってしまうということが多々あります。
では、そのギャップをなくすためにはどうするのが良いでしょうか？
その答えは、
とにかく自分でいろいろと実装してみて、場数を踏む
ことです。地道な作業ですが、これしかないです。
そして、そのための教科書は
がベストです。
この本の良いところは、与えられたタスクに対してどのようなアプローチで取り組むかの流れが具体的なコード例や図を通して、分かりやすく紹介されているところです。
また、この教科書で扱われている課題の内容は、先ほど紹介した「アルゴリズムイントロダクション」の内容に準拠しており、そこで扱われたトピックを中心とした
課題構成となっています。したがって、上記の理論学習を終えた流れで実装練習に移るとスムーズに取り組めるかと思います。
ですが、この本の一番の目玉は他にあります。
それは、
オンラインジャッジシステムを利用したコーディング練習環境の存在
があることです。
オンラインジャッジシステム AOJのススメ
AOJというサイトでは、以下に記されるように、プログラムを用いて解決を試みる課題が幾つも掲載されており、複数の言語のうち任意の一つを選択し課題に取り組み、コードを提出した後、その正誤をテストケースの入出力を通して、自身のコードの正誤を確認しながら学習することができます。
上で述べた教科書に掲載されている課題は全てここに収録されているものとなっています。
AizuOnlineJudgeはオンラインジャッジシステムのひとつ。愛称は「AOJ」。会津大学が運営を行っている。ICPCやパソコン甲子園などで過去に出題された問題が掲載されている。2015年12月現在、C, C++, Java, C++11, C#, D, Ruby, Python, Python3, PHP, JavaScript, Scala, Haskell, OCaml の14言語[1]に対応している。
以下そのリンクになります。
また、実際に正解と判定されるコードを作成した課題に関しては、以下の画像に示すようにチェックマークがつきます。
自身の学習成果が視覚的に認識しやすく、モチベーション維持の上でもナイスです。
各課題は、扱われるテーマに応じていくつかのセクションに分かれており、
(ex.)組み合わせと最適化、データ構造、数学、計算幾何学、etc…
といったように、
自身の学習したいトピックに応じて柔軟に学習を進めることができます。
加えて、各課題にはその課題に取り組んだ人たちの正誤率や、実際の正解者数なども記載されているため、取り組む上での指標も分かりやすいです。これにより、その時々の自身のレベルに応じた演習を行うことができます。
AOJを通して実装練習を積めば、実装で苦労するということはなくなるでしょう。
以上長くなってしまいましたが、プログラミングの試験に臨む上での学習法及びオススメの教科書を紹介させていただきました。
これらが、皆さんのプログラミング学習に役立つようなことがあれば筆者としては嬉しい限りです！
次回予告
ここまで読んでくださり、ありがとうございます。
さて次の記事にあたる、
0から始める 東大情報理工 創造情報学専攻 修士 対策[夏院試](その3)
に関する予告になりますが、今のところ
試験科目のうち、対策がなかなか取りづらいと思われる科目の2つ目、
専門科目[創造情報学]
に関する対策や勉強法についての記事となる予定です。
それでは、次回の更新をお待ちください！<(_ _)>