2020/7/18
期末レポートの提出期限を7/31(金)の24:00とします．

2020/7/6
期末レポートの提出方法を公開しました．レポート提出方法

2020/6/23
期末レポートの詳細を公開しました．

2020/6/22
期末試験を期末レポートに置き換えたことにより，評価のための点数配分を変更しました．詳細は以下のページをご覧ください．

2020/5/27
感染症拡大予防のため，期末試験は期末レポートに置き換える予定です．レポート課題の詳細な内容は6月中〜下旬に公開予定です．

2020/4/3
講義の配信はzoom webinarで行います．また，URLはこの講義ホームページに記載します．ログインにECCSアカウントが必要です．


本講義では情報科学の重要な基礎となっているアルゴリズムとデータ構造に関して学習します．具体的には，

• アルゴリズムとデータ構造に関する基礎知識を習得する
• Pythonを用いて代表的なアルゴリズム・データ構造を実装する
• 講義内で学習した内容を元に応用的なコーディング課題に取り組む

ことを目的としています．この講義を通して

• 代表的なアルゴリズムの考え方を理解する
• その考え方をコードに落とし込む力を養う
• 競技プログラミング等，様々なコーディング課題に取り組める知識を積み上げる

ことができるように授業が設計されています．

本授業は全てオンラインで実施する予定です． 講義はZoom webinarにて配信する予定です．講義の配信動画を視聴するためには，インターネット環境，およびブラウザが必要です．なお，従量課金制による通信費がかからないよう，無料で使えるWifi環境がある場所や定額制のインターネット接続環境で視聴することを強く推奨します．

講義配信用Zoom webinarのURLは以下のスプレッドシートに記載します．なお，ECCSアカウントでログインする必要があります．URLは毎回変わりますので，必ずご確認ください．

https://docs.google.com/spreadsheets/d/1UOkDbt2UC1EaECyN29dbuNu27DtL20geRHzxoxewmek/edit?usp=sharing

本講義を受講希望の方は以下のフォームより登録を行ってください．また，単位習得のためにこの講義を受講する方はUTASでの登録を別途行ってください．

https://iis-lab.org/algorithms-entry

本講義を受講する場合，以下の知識，経験，および実験機器があることを想定しています．

• 基礎的なPythonに関するプログラミング技術がある．
• trackでコーディングを行えるPC環境がある．OSに関しては問わない．ブラウザはChromeおよびFirefoxを推奨する．
• slackを使うことができる．講義内でアナウンスはこのホームページの他，slackでも行います．
• zoomを使うことができる．講義の配信はzoomにて行います．なお，ECCSアカウントが必要です．

本講義の受講にはECCSアカウント（xxxx@g.ecc.u-tokyo.ac.jp）が必須です．セットアップ後使用できるようになるまで少し時間がかかりますので，自分のアカウントの詳細がわからない，という人は以下の動画を確認し，講義開始までに準備をしておいてください．

https://www.youtube.com/watch?v=89_fjWDdzQ4&feature=youtu.be

成績の評価は以下のように行います．

• 35 34点: コードチャレンジ 基本課題
• 35 30点: コードチャレンジ Extra課題
• 30 36点: 期末試験 期末レポート，レポート提出方法

ただし，状況に応じて点数配分を数点程度変更することがあります．また，期末試験はレポート等の形式に変更する可能性があります．なお，出席はとりません．

期末レポートを提出しない場合，原則未受験として扱います．ただし，コードチャレンジに参加しており，期末レポートを提出せずに成績をつけることを希望する場合には，矢谷まで7/15正午までに連絡をしてください．

この講義は毎回2つのパートに分かれています．

• スライドを使った講義パート
• trackを利用したコードチャレンジパート

この講義では両パートに積極的に参加することが求められています．

矢谷が行う講義は全てZoom webinarを通して配信されます．ECCSアカウントでログインする必要がありますので，予めアカウント情報を確認しておいてください．

配信された講義は，配信終了後もオンラインで視聴できるようにします．詳細はこの講義のページ，およびITC-LMSをチェックしてください．

もし，Zoom webinarを見ることが出来ないネットワーク環境（例えば使用するネットワークの制限でZoom webinarにアクセスできないなど）しか利用できず，この講義を受講したい，という学生さんは，矢谷及びTAさんにメールで連絡をお願いします．

授業中及びその後の授業内容に関する質問は，zoom内のQ&A機能を使って行ってください．

本講義のコードチャレンジではtrackというシステムを使います．trackはオンライン上でプログラミングに関する学習を行ったり，指定された課題に対して自分のコードを提出したりすることが出来ます．またコーディング自体をブラウザ上でできるようになっているため，コーディングに必要な環境構築等を行う必要がありません．

本講義ではPython3を使用します．trackではPython3.6.1がサポートされています（2020年3月現在）．それ以外の言語の使用は認めません．また，track以外のシステムを用いた課題提出も認めません．

コードチャレンジには2種類あります．

• 基本課題: 講義内で紹介された擬似コードの実装や変更を行うもの．授業の内容をしっかり追えばできるようになっており，受講者のほぼ全員に出来てほしい課題．
• Extra課題：授業の内容を踏まえた発展的な課題．競技プログラミングとかにも出てくる内容を含んだ，頑張ればできる腕試し的課題．

基本課題はぜひしっかりと取り組み，解いてください．その上でExtra課題にも取り組んでもらえればと思います．

講義パート終了後すぐ，google formにより登録していただいたメールアドレスに対して，trackからのメールを配信します．そのメールに該当する回の課題を行うページへのリンクが記載されています．track上でのコーディング・デバッグ方法，および課題提出方法はこちらのPDFを参照してください．

メールはnoreply@tracks.runより配信されますので，メールクライアント等においてフィルタリング機能を設定している場合には，このメールアドレスからのメールを受信できるように予め設定をしてください．また，アドブロッカーなどを使用していると，ブラウザ上でうまく表示できなかったり，エラーを起こしたりすることがあります．この場合には，アドブロッカーを一時的に停止させてみてください．

trackにおけるトラブルが発生した場合は，slackにてTAさんに連絡をしてください．

コードチャレンジではいくつかのテストケースが予め設定されています．それらテストケースの通った数を元に，原則[配点]*[テストケース合格率]で点数を計算します．採点に特別な扱いがある場合には，その旨を問題文に記します．

頻繁にテストケースを実行し，デバッグを行ってください．これにより提出間際でのミスを防ぐことができる他，コードが自動保存されるので，万が一提出作業を行えなくても，最終保存されたコードを元に採点が行われます．

採点は最終提出物に対してのみ行われます．したがって，途中でどれだけミスをしていてもペナルティはありません．

Extra課題に関しては提出されたコードに対して後日類似度チェック等を行い，明らかに類似したコードがあった場合は，その全てに対してペナルティを課します．基本課題に関してはほぼ同じようなコードになるはずですので，このルールを直接は適用しませんが，類似度チェックは行う予定です．

講義で使うシステムではコードをテストケースにかけた時点で，自動でバージョン管理します．コピペ等を行なった場合には，不自然にコード行数が増えたり，テストケースにパスする回数が突然増えたりするので，その辺りもチェックします．不自然な編集があった提出に関してはペナルティを適用することがありますので，十分気をつけてください．

与えられた基本課題においては，入出力や問題文で指示がある場合を除き，実装すべき処理において標準ライブラリや問題で指定されていない外部の関数やライブラリ等を使用しないでください． そのような提出物はテストケースに合格していても，採点されませんで注意してください．Extra課題においては，適宜外部の関数等を使っても良いものとします．

コードチャレンジの課題によってはコードの一部分（コーディング画面の初期コードとは別のコード）があらかじめ与えられている場合があります． その場合，問題文に明記してありますので，指示に従ってください．

コードチャレンジの課題を見ながら，本やWeb上の情報を参考にすることは問題ありません．ただし，記載されているコードなどをそのまま使うことのないようにしてください．また，友達同士で教え合うのも積極的に行ってください（教えることができる，というのは十分に理解できている証拠でもあります）．ただし，書いたコードを直接見せ合うのではなく，考え方だけを共有するようにしてください．

この講義で重要なのは，「自分で手を動かす」ことを大切にすることです．アルゴリズムやコーディングに自信がなくても，授業で紹介されている内容を理解し，努力すれば一定の評価につながるようになっていますので，後から誤解を招きかねない行為をしないようにお願いいたします．

提出物に対しては後日類似度チェックを行います．以下のような提出物は該当するものすべてに対して採点を取り消します．

• 提出物間でほぼ同一のコード
• Webや参考書に記載されているものとほぼ同一であることが判明したコード
• track上での課題取り組み時間（終了時刻 - 開始時刻）が極端に短い
• 与えられたテストケースに通るようにだけ設計されたコード
• その他，明らかに不正行為の証拠があるもの

悪質な場合にはより大きなペナルティになることがあります．十分気をつけてください．

以下の情報をメールにて，algorithms “at-mark” iis-lab.orgに送ってください．可能な限り事前に，事後でも速やかにお願いします．

• 病欠，公欠を希望する授業日
• 病欠，公欠の理由
• 理由が正当なものであることを裏付けるもの（診断書，処方箋，出席する学会のプログラム等のスキャンデータ，感染症に関係するホットラインへの相談記録）

認められた場合，課題提出期限をこちらが指定する日時まで延長します．

大きな怪我や病気などの例外を除き，病欠，公欠を希望する授業日から1週間以上を経過した場合は，認めないものとします．

剽窃や不適切な引用，改竄などはAcademic Misconductとして重い処分を受けます．この講義ではコードチャレンジにおける提出物や，期末試験での答案における不正行為により不当に評価を得ようとする行為に対して特に厳重に処罰します．例えば，

• インターネット上にあるライブラリやサンプルのソースコードを引用することなく用いた，
• 他人が書いたソースコードを無断かつ引用なしに転用した，
• ほかの学生が書いた回答を盗み見て利用した．

などが挙げられます．特に重大なAcademic Misconductが発見された場合，その影響度の大きさに応じて以下の罰則を与えることになります．

• 不正が見つかった課題を不採点(0点扱い，既採点の場合は採点取り消し)，
• 今までに提出されたすべての課題を不採点，
• 今までに提出されたすべての課題を不採点，かつ以降の課題提出を認めない．

レポートやソースコードは誤解の生じないように十分注意して作成・管理してください．

以下の書籍・リンクはこの講義の資料を作る際に参考にさせていただいたり，講義内容に関する大きな刺激を受けたものになります．以下に挙げているもの以外にも参考になる様々な情報がありますので，興味を持ったトピックに関して色々とご自身で調べていただければと思います．

• プログラミングコンテストチャレンジブック 第2版．秋葉拓哉，岩田陽一，北川宜稔．
• プログラミングコンテスト攻略のためのアルゴリズムとデータ構造．渡部有隆，Ozy，秋葉拓哉．
• 新・明解Pythonで学ぶアルゴリズムとデータ構造．柴田望洋．
• 典型的な DP (動的計画法) のパターンを整理 Part 1 ～ ナップサック DP 編 ～.
  • https://qiita.com/drken/items/a5e6fe22863b7992efdb
• プログラミングコンテストでの動的計画法
  • https://www.slideshare.net/iwiwi/ss-3578511
• 累積和を何も考えずに書けるようにする！
  • https://qiita.com/drken/items/56a6b68edef8fc605821
• Candies [Educational DP Contest / DP まとめコンテスト M]
  • https://www.hamayanhamayan.com/entry/2019/01/10/235150
• Union-Find木の解説と例題
  • https://qiita.com/ofutonfuton/items/c17dfd33fc542c222396
• ソートを極める！ 〜 なぜソートを学ぶのか 〜
  • https://qiita.com/drken/items/44c60118ab3703f7727f
• 競技プロ的なアルゴリズムのスライドのまとめ
  • https://yukicoder.me/wiki/slide
• Atcoder tags
  • https://atcoder-tags.herokuapp.com/explain
• ICPC Challenge　実践的プログラミング (全学自由研究ゼミナール)
  • http://www.graco.c.u-tokyo.ac.jp/icpc-challenge/

またpythonの基礎の学習には様々なオンラインコースがありますので，それを活用することをおすすめします．

• https://www.python.ambitious-engineer.com/introduction-index#i-4
• https://www.python-izm.com/introduction/
• https://docs.python.org/3/
• https://www.learnpython.org/

ここでは講義中に出た講義に関係する質問とその返答を取り上げています．

• 数学2Dの演習の授業も同じ曜限に開講されていて、どちらも履修したいのですがそれは可能でしょうか？
  • 残念ながら認められません．EEICでは情報よりの興味をお持ちであれば「数学2G＋アルゴリズム」を，物理よりの興味であれば「数学2D (講義+演習)」を取るように授業が設計されていますので，そのようにしてください．
• 大学院生ですが単位取得のために講義を受講することは可能ですか？
  • 所属する研究科，専攻に単位取得が可能かどうかを確認した上で，UTASでの登録をしてください．

• スライドとは違うアルゴリズムで提出してしまったのですが減点等はありますか？
  • スライドや問題文の指定と違うアルゴリズムで提出した場合は，テストケースに通っていても今後は採点されないことがありますので，問題文の指示をよくお読みください．
• 聞き逃したかもしれないのですが、採点結果はITC-LMSなどで見れますか？
  • 採点は[配点]*[テストケース合格率]が原則ですので，それで自分の点数がわかります．採点を取り消すケースなどが発生する場合は個別に連絡します．
• 採点のフィードバックはありますか
  • システム上，私達からの個別のフィードバックが難しいので，テストケースに通ったかどうかが一応のフィードバックになるようにしてます．
• 受講者フォームの単位習得の項目で「聴講のみ」を選択したのですが，この回答を撤回して単位習得をするために行わなければならないことはありますか？(UTASでの履修登録をするだけで大丈夫でしょうか)
  • 今後のコードチャレンジで「単位取得」の方を選んでおいてください．
• 課題を終えるまでにかかった時間は評価に入りますか？
  • 考慮しません．
• 翌週に模範解答的なものは公開されますか
  • その予定です．
• 課題についてWEB上のコードを参照して、そっくりじゃなくても似ているコードはいけませんか？
  • 自分自身で咀嚼した上で書いたコードだと判断してよいと第三者が見て言えるレベルにしてもらえればと思います．
• dequeやheapqなどは使用しない方が良いということでしょうか？
  • 基本課題ではその類のものは使用できません．

• ネットワーク接続（コンテンツサーバー）の異常で受験できません
  • adblock解除で接続できた報告がありましたので，試してみてください．それでもエラーが出る場合はこちらに連絡をください．
• テスト実行で一度保存すればブラウザを一度閉じてもコードが保存されるということでしょうか
  • はい．そうです．不安ならローカルにコピーしておいてください．
• SyntaxError: Non-ASCII character ‘\xe3’ in file main.py on line 4, but no encoding declared というエラーが出る
  • どこかに日本語が入っているためだと考えられます． # coding: UTF-8を入れるといけるはずです．
• 「解答を完了」したあと、「試験を提出する」を押さないと、採点されなかったりますか？前回は「試験を提出する」を押し忘れたようなきがするのですが
  • 期限が来ると自動で提出はされますが，押してもらうほうが確実です．
• デフォルトで書いてあるコードは、特に気にしなくていいものですか？それとも理解しないといけない内容が書かれていますか？
  • 気にしなくてよいです．このコードを利用せずに提出しても問題ありません．
• sys.stdin やdefを使わずに、inputなどだけを用いて提出したのですが(テストケースには正解)、それでもよかったでしょうか
  • 問題ありません．デフォルトのテンプレートを消した上で，提出してもらって問題ありません．
• Ctrl+sでテスト実行されました
  • こちらも便利ですね！
• 後から復習できるようにtrack上の問題文をローカルに保存する方法はありますか？
  • とりあえずwebページをPDFとかに保存してもらえればと思います．（何かしらの方法で公開できないか検討中）
• コードを初めからやり直したいときにリセットする方法はありますか？
  • 右上の歯車のところにテスト環境を初期化というボタンがあります．

• 課題1では，授業中に紹介された例や計算時間のデータなどは同じものを使っても良いものなのでしょうか．
  • 使っても構いませんが，レポートではどのような創意工夫があるか，という点も評価対象であるので，そのあたりとの兼ね合いをよく考えた上で判断していただければと思います．
• レポートを書く際に授業スライド内の図を使いたいのですが構わないでしょうか？
  • こちらも禁止はしませんが，上記質問と同じく，自分なりの創意工夫との兼ね合いをよく考えた上で判断してください．また，slideshare等にて公開することを考えておられる場合には，使用しないほうが安全かと思います．
• 紹介するアルゴリズム（テーマ）は他の人と被らないようにしたほうが良いですか？
  • テーマに関しては他人と重複しても問題はありません．内容や説明の仕方は個々人で違うと思いますので，皆さんなりの解説に期待しております．
• 他の人が書いた課題2を読みたいのですが共有されますか？
  • 課題提出締め切り後，各人がslideshare等にて公開することを推奨したいと思いますが，あくまで自主的なご判断によるものとさせてください．公開していただいたものは，このページ内でも紹介しようと思います．
• 課題2で選んだテーマに関して，証明事項が多く厳密に全部やると90分におさまりません．きちんとした証明をappendixとして記しておいたほうが方が良いのでしょうか．
  • 授業と同じく，厳密な証明よりは，理解に必要なコンセプトを分かりやすく伝えることと，具体的な実装例を重視してもらえれば良いかと思います．その上で証明を補足資料にしてもらうのはよいかと思います．
• 課題1について，中学生にアルゴリズムの面白さを伝えることを重視したいため，2分野にまたがるスライドになるかもしれず，その分一分野あたりの濃度が薄くなってしまうかもしれないのですが、大丈夫でしょうか？
  • 課題に関しては，それでも構いません．ただし，単に「アルゴリズムでこんなことできるよ！わーすごい」というショーケース的に見せるのではなく，あくまで授業として，ある特定のことを理解してもらうことを目的としてもらえればと思います．
• 学部三年生向けのスライドテーマとして挙げられていた連続最適化問題には確率的勾配降下法などのように，機械学習のパラメータ最適化で使われるアルゴリズムが含まれていると思いますが，この確率的勾配降下法は機械学習に使われるアルゴリズムとして扱わない方が良いのでしょうか？
  • 機械学習に特化した最適化方法とかは避けてもらいたいと思いますが，機械学習に限らず使える最適化手法であれば問題ありません．