2021年7月27日火曜日

講義を完走した感想

人生で初めて講義(教える側)をしたのですが、とても濃い経験になったので備忘録として残そうかと思います。大学で講義を「する」という経験は一般的に見ればなかなかない経験であまり想像がつかないと思いますので、どういう感じなのかを説明します。講義資料の準備で意識したことや悩んだことなども綴っていくので、これから講義をする機会のある方には参考になる部分もあるんじゃないかと思います。既に幾つも講義を受け持っているプロフェッショナルな方々には自身の経験を思い出して温かい目で見守っていただけたら幸いです。コロナ禍という特殊な環境ではあったものの初の対面講義で奮闘した一人の助教の記録です。


0. 背景

自分が担当した講義はプログラミングの発展的な内容を扱うもので、学部2年生向けの講義です。まだ学部2年生の前期なのでまだあまり専門分野を学んでいない状態です。とはいえプログラミングの基礎的な部分はある程度学んでいてPythonは少しは分かるという状態です。また、必修科目というわけでもないので、受講者はある程度プログラミングに興味を持っているという想定です。また、ORなどに興味を持ちそうな理系向けの講義になっています。


1. 講義内容と形式の決定

自分が最初に苦労したのはこの部分です。特に何をすべきかが厳密に定まっておらず、内容はほとんどを任されていましたが、昨年度までの資料を見る限りでは基礎的なアルゴリズムをやっていたためその方向性は守ろうと思いました。他の先生に話を聞くと「ダイクストラ法はやってほしい」みたいな声も聞いたので、この辺りはちゃんと取り込もうと思いました(もちろんダイクストラは元々やるつもりでしたが)。昨年度までは本当に幅広く(平面幾何、乱択アルゴリズム、組合せ最適化など)さまざまなアルゴリズムを軽く紹介するという感じだったので、組合せ最適化の内容を主に扱い、最後に自分の趣味(ランダムグラフ、ランダムウォークなど)を少し取り入れた感じにしようと考えていました。

私の所属する大学はクォーター制度を導入していたため、講義は全7回です (6月頭〜7月末)。週1回講義と演習の時間がそれぞれ100分ずつあります(なので計200分あります!)。また、2020年度はコロナ禍の影響でオンライン講義になっていたようですが、私が赴任した2021年度は演習ということもあり対面授業になるとのことでした。

私がD3だった2020年度はコロナ禍が始まった年ということもあり仕方のないことですが対面講義と比べるとオンライン講義はあまり楽しいものではありませんでした。なので対面で講義できるというのは嬉しく思いました。特に受講生の顔で反応を見ながらインタラクティブに教えたりするのは教育の楽しい部分だと個人的に思います。

とはいえ緊急事態宣言が発出されている状況なのでいつオンライン講義に変更になっても対応できるように、昨年度と同様に google colab (jupyter notebookをブラウザ上で動かすgoogleのサービス) のドキュメントを講義資料とすることにしました。特にgoogle colabだと学生のPCにpythonを動かすためのソフトを入れる必要もなく, googleアカウントさえあれば誰でも動かせるのもあって導入が非常に簡単です (今の時代だとほとんどの人がYouTubeを観たりするのでgoogleアカウントは持っています). ipynbファイルを講義資料として配布し、受講生は自分のPCを持参してもらえれば普通に講義を行うことができます。

2. 講義資料の準備 (第1回〜第3回)

4月に着任して早々に講義をどうするかが頭をよぎったので、かなり前もって準備をすることにしました。今思えばこの選択はかなり良かったです(何事も余裕を持って準備しておくことは非常に大切です)。

講義資料を作る前に自分の中ではグラフアルゴリズムをメインに据えるということを意識しました。グラフ理論やグラフアルゴリズムは自分が非常に得意とする分野であり、何度も実装したことがあるからです。そこで、当初は次の二つの事項を講義で扱おうと考えました:

1. Pythonを用いて基礎的なアルゴリズムを理解

  キーワード: 再帰, DFS, BFS, 貪欲法, 最短経路問題 (Dijkstra, Warshall—Floyd), DP.

2. 応用を知る: ネットワーク解析

  キーワード: ランダムウォーク, ランダムグラフ (BAモデル),  ネットワーク中心性 (PageRank, 媒介中心性) など.

ひとまず第1回の講義はPythonの復習を行い、その後は基礎的なアルゴリズムをひたすら紹介していき、最後の第7回講義で自分の趣味を交えた講義を行うという計画を立てました。

この方向で講義を組み立てて実際に講義資料を作り始めたのが4月の中旬 (講義開始2ヶ月前) でした。初回の講義資料が完成したので見返しました。初回はPythonの文法の復習だけやって「1から1000までの7の倍数の和を求めるコード」とかを1時間やるものだったので、純粋に「これはツマランな」と心配になりました。そこで少しでも退屈を紛らわそうと再帰関数の紹介を行いました。再帰を使ってフィボナッチ数列や階乗の計算のプログラムを書き、最後に非自明な例として分割数の漸化式を示しつつ分割数を計算するコードも紹介しました。

第1回の課題は「与えられた自然数が素数かどうか判定せよ」みたいな問題を出していましたが、なんとなく味気ないのでコラッツ予想を絡めた問題も出題してみました。こんな感じです。


この調子で第2回講義資料も取り掛かり、計算量とグラフの定義を行いました。グラフの隣接行列や隣接リストを紹介し、「グラフの次数列を計算せよ」「三角形(長さ3の閉路)の個数を求める関数を書け」といった課題を出していました。

課題を考える時に意識したのはデキる人でも退屈しない内容にしたいということです。講義そのものは流石に集中が散ったりするのでしょうがない部分もあるかもしれませんが、せめて競技プログラミングのように、問題を解く部分に楽しみを見出して楽しんでもらいたいと思っていました。第2回講義以降は毎週の課題の中に一つだけ学部2年生向けの講義にしてはありえないくらレベルの高い難問を設けることにしました (難問はチャレンジ課題枠としてあり、解けなくても成績に影響は出ないことを明言した上で出題しました)。

ちなみに第2回講義で出題した難問は以下の問題です:

要するに長さ4の閉路の判定を$O(n^2)$時間で行えという問題で、この記事にも紹介したように鳩の巣原理を使うと計算量が抑えられるという問題です。これを計算量の概念とグラフの定義を学んだばかりの学部2年生に出すのは正気の沙汰とは思えません。こんなん知らない状態から解けるやつおらんやん...

第1回と第2回の講義資料と課題の準備が一通り終わったので、他の先生や学生TAに難易度や分量を含めて確認してもらい、大丈夫そうとのことだったのでここでようやく一息つきました。ここまでの講義の内容は必須事項だったのであまり迷いはありませんでしたが、以降の構成に頭を悩ませることになりました。

ひとまず考えた計画としては残りの5回で

・可視化ライブラリ(matplotlibとnetworkx)の紹介、幅優先探索、深さ優先探索
・貪欲法、クラスカル法
・動的計画法
・Dijkstra、Warshall--Floyd、Bellman--Ford
・フロー (Ford--Fulkerson) 

をやるか、または最後のフローはやらずに代わりに自分の趣味(ランダムグラフなど)を紹介するか、どちらかにしようと決めました。

いずれにしてもグラフアルゴリズムをやることは決まっていたので、せっかくなのでアルゴリズムの可視化を行うことを思いつきました。ひとまずgoogle colab上でのアニメーションの方法を学び、試しにDFSやBFSのアニメーションを書いて遊びつつ講義資料の準備を進めました。

ちなみにこんな感じのアニメーションを作りました。受講生はgoogle colabで開いている講義資料にあるPythonコードを実行するとこのようなアニメーションが出てくるというようになっています。アルゴリズム自体を可視化しているのでグラフは自由に変えられます。また、ボタンを押した時に一コマだけ進ませるというようなことも可能です。


ちなみにこの動画のソースコードは本記事の5章で公開しています。

この調子でクラスカル法やダイクストラ法もアニメーションプログラムを作っていこうと決めていくうちに、とうとう初回講義の日がやってきました。

3. 対面講義初回


結論からいうと初回講義は機器の不調なども重なって非常に大変でした。そもそも自分の担当は講義100分+演習100分だったのですが、実は当時の自分は勘違いをしていて講義100分の中に演習が組み込まれているものと思っていました(なので実際の講義は想定の倍あったということになります)。

元々70分程度の想定の下で準備していた講義を緊張もあって少し早口で進めていき、めちゃ早く終わっちゃうと内心焦っていたら、突然PCの調子が悪くなり学生TAのPCを急遽借りて講義を再開して案の定めちゃくちゃ早く講義部分が終わって演習時間がものすごく長くなるなど、思い返しても大変な1日になってしまいました。結局初回は課題が簡単だったのでほとんどの学生がすぐに帰る感じになっていました。

今にして思えばもっとやりようはあっただろうとも思えますが、2ヶ月弱前から準備していたしやれることはやったのであまり気にせずとりあえず講義を進めていくことになります。

第2回講義は使用PCも変えたので第1回と比べるとかなりスムーズに終えられました。第2回課題には第1回とは違い難問も用意していましたが、これは予想以上に反応が良かったです。計算量を気にしてプログラムを書くということをあまり経験してこなかった学生がほとんどだと思うので四角形の高速な判定にどこまで取り組んでくれるか心配したのですが、10人弱の学生が18時くらいまで残って議論しながら取り組んでくれました。これには教員側からしてもとても嬉しかったです。


4. 講義の改善点の洗い出し


まだ2回ではあるもののここまで講義をやってきていくつか変更点が見えました。まず、そもそも講義時間を勘違いしたまま準備していたので単純問題として内容は倍にできる。どうするか?

また、学生の質問を受け付けていくうちに色々改善した方がいいかもなぁというものも多く出てきました。例えば

  • google colabのインデント幅の設定が人によって違う
  • 自身が書いたコードがちゃんと正しく動いてるかを確認するのが面倒(学生が自分でテストケースを用意して確認しなければならないが、グラフアルゴリズムだと自分で隣接リストなどを用意しなければならない)
  • printfデバッグみたいなことを教えた方がいいのか?
などです。printfデバッグは質問してきた学生に「こうしてprintをするとどこで詰まったか分かるよ」と直接教えることにしました。

インデントなど、全体に連絡すべき事項はちゃんと講義冒頭にスライドを使って説明するようにしました。

課題プログラムの自己チェックを可能にするために、Checkerというものを導入しました。これはつまるところ競技プログラミングのサンプルケースとその答えを事前にこちらで用意しておき、学生が書いたコードがこれらのサンプルケースで正しい答えを出すかどうかをチェックするプログラムを講義資料に入れておいたのです。こんな感じです。





*)完全に問題がAtCoder感があるかもしれませんが、こういう文章題は少なくて、普通の問題はグラフ理論の用語を使った問題文になっています。

また、課題の採点を楽にするためにテストケースを用意しました。基本的にはテストケースで正解していて大丈夫そうなコードを書いていたらその課題を満点にするという感じにしました。これのおかげで採点は劇的に楽になりました。

もちろん、サンプルケース, Checker, テストケースによる自動採点の準備はかなり大変でこれを講義資料の準備と並行して行うのは非常に時間がかかり大変でした。しかし、特にCheckerの導入は受講生にはかなり高評価だったようで、さらに「Checkerを走らせたらエラーが出た/Wrong answerだった」という類の質問がきてくれたことは良かったです(Checker導入以前はあまり質問をしてくれる学生がいなくて寂しかったです)。やはり、自分の書いたプログラムがちゃんと動いているかの確認が簡単にできるということは準備の大変さに目を瞑ればメリットしかありません。


5. 以降の講義資料の準備と講義


ここまで来ると講義自体も少しずつ慣れてきて、講義内容も固まってくるので特に悩むこともなくなってきます。以前立てた計画通り

・貪欲法、クラスカル法
・Dijkstra、Warshall--Floyd、Bellman--Ford
・動的計画法
・フロー (Ford--Fulkerson) 

の順番で講義資料を準備していきました。結局最終回はフローと最大二部マッチングをやることにしました。

ちなみに講義資料のために作ったアルゴリズムのアニメーションは

https://colab.research.google.com/drive/1ed0fAC6rUMcScJYxv0Kc0Ox-wDBf2FSR

で閲覧することができます(ダウンロードすれば誰でも編集とかができるので、講義などで使ってみたいという方ご自由にどうぞ。ソースコードの下から二行目のanim.save(...)の部分をコメントアウトすると動画をmp4ファイルで保存できます)。

ちなみに細かい講義内容は

第4回:

  • 貪欲法 (コイン支払い問題, 区間スケジューリング問題)
  • 最小全域木問題
  • クラスカル法


第5回

  • 最短経路問題
  • ダイクストラ
  • ベルマンフォード
  • ワーシャルフロイド


第6回

  • 動的計画法
  • 最長共通部分列問題
  • ナップザック問題
  • 重み付き区間スケジューリング問題
  • Held—Karp のTSP


第7回

  • フロー
    • 残余グラフ
    • Ford—Fulkerson
    • Edmonds—Karp
  • 二部マッチング
    • 割り当て問題

という感じになりました。難問枠としてmeet-in-the-middleなどを出題しました。

反省点は幾つもあります。
  • 第5回以外は意外と早く講義が終わってしまったというのがあります。アルゴリズムを広く浅く紹介して課題で問題を解きながら理解を深めてもらうというスタンスだったので、内容としてはちょうど良いのかもしれませんが講義自体は説明は割と早めに終わってしまいました。この辺りは説明をもっとゆっくりやればちょうど良くなりそうな気配があるので、経験を積むと感覚が掴めてくるのかもしれません。
  • 初回の講義についてはPythonの復習にたくさん時間を割くよりも、エラトステネスの篩、ユークリッドの互助法、二分探索などの軽いアルゴリズムの紹介などが出来た気がしています。復習に時間を割くよりもコードで出てくる度に「リストはこうやって要素を追加するよ」と言えば良さそうです。
  • 課題の提出についても注意喚起が足りなかった部分があります。課題を解いたのに保存で失敗して白紙の状態で提出してしまったという学生もいました。こういった不運な事故を防ぐ努力(注意喚起)はもうちょっとすべきだったと思います(流石に初めての講義でそこまで気が回らなかったのもしょうがない気がしますが。。。)

このように、色々と改善点はまだまだあるものの、初めてやったにしては上出来なんじゃないかと開き直ることにしています。

なお、講義資料の準備段階では他の先生の講義動画などが非常に参考になりました。説明の順序やその問題を考える動機などが自然に導入されており、流石だなぁと思いました(もはやこの動画が講義資料でいいじゃんと思っちゃうくらい)

6. 感想


元々自分は人に教えるのが好きだったので、とても楽しく完走することができました(もちろん準備はかなり大変でしたが。。。)来年度以降はゼロからアニメーションコードを開発したりまではしなくて良いのである程度苦労は減ることを期待していますが、今年度できなかった内容も取り入れたいし、実は少し楽しみにしています。例えば乱択アルゴリズムを取り入れて難問枠としてcolor codingを入れたりとかを妄想しています笑

一方でコロナ禍での対面授業ということもあり、感染拡大の防止にものすごく気をつけました。対面講義をするというのもあって、4月の緊急事態宣言以降は今もなお一度も人と一緒に外食をしておらず、そもそも食事はほとんど全てをテイクアウトか自炊で済ましています(講義が終わった今後も同様の生活を続けていくつもりです)

受講生自身からも対面授業が嬉しいというコメントがきている一方で彼らも感染防止にはかなり気を遣ってくれていて、もちろん完全に会話をゼロにするには流石に無理ですが、それでも常にマスクをつけて暑い中換気のために窓を開けるのに協力してくれたり、入室時には必ず手の消毒をしてくれていました。

私が担当した2年生は昨年度はコロナ禍でほとんど大学に来れなかったということもあり、対面授業で盛り上がって大声で話し出したらどうしようと危惧していて(実際そうなったとしたら流石に注意せざるを得ないが彼らの心情を考えると非常に心苦しい)悩んでいた時期もありましたが、基本的には近くの2~3人組で相談し、意欲のある学生は難問の相談を行う感じになってくれており、当初危惧していたようなこともなかったため非常に安堵しています。

私の周りや受講生で感染者が出たという話は今のところなく、おそらく2週間後くらいまでは完全に安心できないですが、ひとまず講義中にこのような問題が起きなかったことが一番ホッとしています。



0 件のコメント:

コメントを投稿

Håstadのスイッチング補題

回路計算量の理論における重要な結果の一つである Håstadのスイッチング補題 を紹介します. 簡潔にいうとこの補題は, 99%の変数をランダムに固定することによってDNFの決定木が小さくなることを主張する結果です. 応用としてparity関数に対する$\mathrm{AC}^0...