【C S授業紹介】アルゴリズムってなんだ？
前回までは、USCコンピューターサイエンスの全般的なカリキュラムについて、紹介しました。今回は、私が受講した講義内容について、具体的に紹介したいと思います。まずは、全コンピューターサイエンス修士学生の必修科目である、アルゴリズム解析（Analysis of Algorithms）の授業です。
そもそもアルゴリズムってなんだ？？
エンジニア経験のない私にとって、いまいちピンとこなかった「アルゴリズム」という言葉。そもそもアルゴリズムとは何でしょうか。私なりに言い換えると、「処理の順番」だと考えています。
プログラムというのは、ある問題解決（計算するとか、自動でメッセージ送るとか）のために、プログラミング言語によって書かれるものです。目の前の問題に対して、どのような処理をどのような手順で行えば、解決するか。この手順の集合体がアルゴリズムです。つまり、問題解決の道筋を考えるということなのだと思います。
実際、私が受講した担当教授も、アルゴリズムの授業のことを「This is not the programming practice. It is the course for problem solving.」(これは、プログラミングの練習ではなく、問題解決を学ぶ講義だ)とおっしゃっており、なるほどと思いました。
というのも、私自身、プログラミングを学び始めた頃、入門書を購入して、一通りの文法を学びましたが、いまいち上達できなかった経験があったからです。簡単な関数作りならできるけど、それらが複合的に機能するプログラムが書けない。なぜか？それは、アルゴリズムを考えることに慣れていなかったからなのです。
簡単な例に例えてみましょう。いまあなたは、カレーライスを作ろうとしています。言い換えると、あなたは、カレーライス作りという課題を解決したい状態です。では、どうすれば作れるでしょうか？当然、材料を揃えて、ジャガイモを切ったり、肉を炒めたり、煮込んだりする必要がありますよね。これらの料理の手順が、アルゴリズムなのです。
私は、大学院でのアルゴリズム解析の講義を経て、プログラミングをする力が格段に高まったと実感しています。もし、この記事をお読みのあなたが、プログラミング入門書を読み終えて、伸び悩んでいるならば、アルゴリズムの訓練を積むと良いかもしれません。
授業の進め方
大学院での講義に話を戻します。講義は、週に１回、３時間半程度の長さで実施されます。学期通して合計１５回です。担当教授は、Shamsian先生という方で、過去受講した学生からも、”授業がわかりやすい”と評判でしたし、私もその通りだと感じました。
教科書は、アルゴリズム分野において、昔から名著として名高い、「Algorithm Design (Jon Kleinberg, Eva Tardos著)」でした。
ちなみに、日本語翻訳されたものをネット検索したら、かなり高い価格でした。。。代わりに、下記の日本語文献は、Algorithm Designも参考にしつつ、わかりやすくまとまった参考書だと考えています。初学者にもおすすめです！
授業スタイルについては、教科書のトピックに沿って、毎週１つの有名アルゴリズムを取り上げて、先生が解説し、最後に例題を解いて、そのアルゴリズムの使い方に慣れる、という方法で行われました。
私にとって意外だったのは、講義や課題、試験において、PCやプログラミング言語を使わずに、紙とペン(iPad含む)によって行われたことです。先生曰く、PCでプログラミング言語を用いて実装すると、言語固有の文法ミスや環境設定起因のバグなどに囚われやすくなるので、まずアルゴリズムの訓練を積むためには、紙に、考えをデザインすることが大事だとおっしゃっていました。
課題や試験、成績評価など
＜宿題＞
授業を聞いたら、翌週までに宿題の問題を解き、提出します。後日、採点されて電子データで返却される仕組みです。この講義の成績評価は、ほとんど試験結果によって、決まるものだったので、宿題の採点結果には、一喜一憂せずに済みました。宿題の例は、こんな問題でした。
あなたは、Lリットルの液体が入るボトルを持っています。今、N種類の液体があり、それぞれの体積はL1,L2,,,,Lnリットルとします。このN種類の液体には、それぞれ数値V1, V2, ,,,,Vnの値がセットで付与されています。あなたのボトルに、これらの液体を混ぜて入れ、数値(V1〜Vn)の合計が最も大きくなる入れ方のアルゴリズムを考えなさい
これは、貪欲法(Greedy Algorithm)というアルゴリズムを学んだときに解いた問題です。解答例としては、次の通りです。液体を入れる前に、N種類の液体に対して、各値Vを各体積Lで割り、リットルあたりのVを算出し、その値の大きい方から並べ、その順番にボトルに入れていく、というものです。
このように、実際の問題を目の前にして、解決への道筋を考える訓練を積んでいきます。これが、実際のプログラムを書く場面でも活きてくるのです。
講義では、貪欲法の他にも、マッチング、グラフアルゴリズム、動的計画法、ネットワークフローアルゴリズムなどを扱いました。
＜試験について＞
試験については、中間テスト２回と期末テスト１回が、行われます。従って、３回の試験結果によって、成績評価が決まります。 この頃は、まだコロナが流行っている時期だったので、オンライン形式で実施されました。Open-book形式であったので、教科書や参考書を読みながら受けてオッケーな試験でした。
ちなみに、他のアメリカの大学においても同様だと思いますが、私の大学院でも、成績評定の平均がB以上でないと卒業資格を得られません。多くの授業評価は、相対評価なので、どの授業においてもB以上を取るために、必死になって努力する必要があります。私は、ただでさえC Sバックグラウンドがないし、特別数学ができるわけではないので、毎回死に物狂いで勉強しています。
それでも毎回のテストはこんな成績です。
見よ、この無様な結果を。。。でも、全力で戦って、この結果なので、仕方ありません。インド人が優秀過ぎるだけなんだ、と自分に言い聞かせないと、やってられません。はあ。
ちなみに、だいたいどの授業でも、毎回の試験の度に標準偏差や平均点、自分のクラス内での位置などが、明示されます。私は、もれなく毎回凹んでいます。
私なりの学び
成績評価や、無事卒業できるかについて考えていると、思わず暗い気持ちになるので、私なりの学びを最後にまとめます。
まず、アルゴリズムを考えることが、楽しいことだと気づきました。今までは、プログラミングの細かな文法やバグに囚われてばかりでしたが、今は、プログラムを書く前に、アルゴリズムのデザインに時間をとり、紙に描きながら、その時間を楽しむようにしています。
そして、紙とペンを使ってアルゴリズムを書く訓練が、プログラミングの実装力に繋がるということが、私にとっては新鮮でした。このようなことを、アメリカで教わる、というのも意外でした。日本で、このようなことを教えてもらったことがなかったからです。
最後に、この授業を踏まえて、僕自身も、プログラミングを学ぶ人向けに、オンラインで「アルゴリズム勉強会」を実施するようになりました。時折活動しているCode for AICHIの活動として、今は、小学生向けに、様々な形でアルゴリズムを楽しんでもらう会を実施しています。（このような活動も今度紹介しますね！）
以上、今回は、アルゴリズムの講義について紹介しました。参考になりましたでしょうか。
それでは！
