本講義では情報科学の重要な基礎となっているアルゴリズムとデータ構造に関して学習します．具体的には，
ことを目的としています．この講義を通して
ことができるように授業が設計されています．
本授業はハイブリッド形式で実施する予定です． 講義はZoomにて配信する予定です．講義の配信動画を視聴するためには，インターネット環境，およびブラウザが必要です．なお，従量課金制による通信費がかからないよう，無料で使えるWifi環境がある場所や定額制のインターネット接続環境で視聴することを強く推奨します．
| 場所 | 工学部２号館４階246教室，zoomミーティングルーム（ハイブリッド形式で実施） |
|---|---|
| 講義室にて受講を希望する方はモバイルアプリMOCHAで入室予約を行ってください． | |
| 時間 | 水曜日3限（13:00 - 14:45），ただし講義の動画，およびPDFは後からでも見ることが可能． |
| 講義担当者 | 矢谷 浩司 (koji “at-mark” iis-lab.org) |
| TA | 加賀谷 昂輝，廣澤 佑亮，利根 悠司 (algorithms “at-mark” iis-lab.org) |
| ITC-LMS | https://itc-lms.ecc.u-tokyo.ac.jp/lms/course?idnumber=2022FEN-EE3d08L10F01 |
講義配信用ZoomのURLは以下のドキュメントに記載します．ECCSアカウントでログインする必要があります．
https://docs.google.com/document/d/1AOyeNwbEqCOH-jNFO2pG8DROUDPC8FIkn6uLz6D0zRo/edit?usp=sharing
講義終了後の録画を見るためのURLも上記ドキュメントに記載してありますので，授業後に確認してください（授業終了から数時間後には共有する予定です）．
| 回 | 日程 | 講義内容 |
|---|---|---|
| #1 | 4/6 | イントロダクション，計算量 |
| trackの利用方法 | ||
| #2 | 4/13 | 累積和，整数関連 |
| #3 | 4/20 | データ構造 |
| #4 | 4/27 | 探索（サーチ） |
| #5 | 5/11 | 整列（ソート） |
| #6 | 5/18 | 文字列照合 |
| #7 | 5/25 | 動的計画法1（基本のDP） |
| #8 | 6/8 | 動的計画法2（いろいろなDP） |
| #9 | 6/15 | BFS，DFS |
| #10 | 6/22 | グラフアルゴリズム1（最短経路問題） |
| #11 | 6/29 | グラフアルゴリズム2（最小全域木，トポロジカルソート） |
| #12 | 7/6 | グラフアルゴリズム3（最大流問題） |
| #13 | 7/13 | グラフアルゴリズム4（最小費用流問題），「難しい問題」とは，さいごに |
本講義を受講希望の方は以下のフォームより登録を行ってください．ECCSアカウントでログインしておく必要があります．また，単位習得のためにこの講義を受講する方はUTASでの登録を別途行ってください．
[受講の受付は終了しています．]
本講義を受講する場合，以下の知識，経験，および実験機器があることを想定しています．
本講義では，工学部2号館246教室でオフラインでの講義を行い，同時にオンラインでの配信を行います．246教室で受講を希望する方は，モバイルアプリMOCHAをご自身のスマートフォンにインストールし，事前に入室予約を行ってください．
事前に入室予約を行っていない方には，教室の混雑状況によってその場で退室をお願いすることがあります．どうぞよろしくお願い致します．
本講義のオンラインでの受講にはECCSアカウント（xxxx@g.ecc.u-tokyo.ac.jp）が必須です．セットアップ後使用できるようになるまで少し時間がかかりますので，自分のアカウントの詳細がわからない，という人は以下の動画を確認し，講義開始までに準備をしておいてください．
https://www.youtube.com/watch?v=89_fjWDdzQ4&feature=youtu.be
成績の評価は以下のように行います．
ただし，以下の制約に1つでも引っかかる場合，この講義の成績は「未受験」という扱いになります．もし，上記制約に引っかかる場合であっても自分の成績をつけてほしい場合は，個別に期末試験前日までに連絡をしてください．（もちろん成績は総得点によりますので，連絡をしたら必ず単位が来る， ということではありません．）
病欠，公欠等の理由により期限内の提出ができない場合，講義担当者へメールにて連絡をして，対応を相談してください．事前の相談がない場合は救済措置が難しいことをご承知おきください．
この講義は毎回2つのパートに分かれています．
この講義では両パートに積極的に参加することが求められています．
講義はzoomを利用した配信します．授業開始5分前くらいからミーティングを開始させますので，準備ができ次第お入りください．
質問等がある場合は，授業のslackでコメントをしてください．
授業のzoom meetingに接続できない場合，utacのアカウントでzoomにログインしていることを確認してください．以下の方法でzoomのクライアントアプリでログインを先に行ってから，接続をすると問題なくいくとはずですので，お試しください．
Zoomの通常のサインイン画面からサインインする方法（アプリからサインインする場合はこの方法です）
1. Zoomの通常のサインイン画面で，「SSO」または「SSOでサインイン」と書かれた文字を探して押してください．
・この画面のメールアドレス・パスワード欄にUTokyo Accountの情報を入力してもサインインできません．
2. 表示される画面によって手順が異なります．
・「会社のメール」という欄が表示されたら，[UTokyo Account] を入力してください．
・「会社のドメイン」という欄が表示されたら，u-tokyo-ac-jp と入力してください．
3. UTASなどと同じような東京大学のユーザ名とパスワードを入力する画面（安田講堂の画面）が出たら，UTokyo Account（10桁の共通ID）または xxxxxxxxxx@utac.u-tokyo.ac.jp の情報を入力してください
授業中及びその後の授業内容に関する質問は，slackで行ってください．
コマンドを利用することで匿名でメッセージを送ることができます．名前を出したくない場合は，その機能を使ってください．
また，講義担当者からは授業の理解度を図るために，授業中にslackで呼びかけを行いますので，リアクションしてもらえると嬉しいです．
成績のうち約1/3は，Extra課題を毎週提出するか，以下に示すレポート課題を期限までに提出することで与えられます．レポート課題を提出した上で，Extra課題を提出している方は，より点数の高い方を成績評価に利用します．
レポート課題の具体的な内容は以下のPDFを参照してください．
https://yatani.jp/teaching/lib/exe/fetch.php?media=2022algorithms:report.pdf
レポート課題の提出にはTurnitinを利用します． Turnitin以外での提出方法は認められません．Turnitinによる提出方法に関しては後日説明いたします．具体的な提出方法は，以下のページを確認してください．
https://yatani.jp/teaching/lib/exe/fetch.php?media=2022algorithms:submission.pdf
本講義のコードチャレンジではtrackというシステムを使います．trackはオンライン上でプログラミングに関する学習を行ったり，指定された課題に対して自分のコードを提出したりすることが出来ます．またコーディング自体をブラウザ上でできるようになっているため，コーディングに必要な環境構築等を行う必要がありません．
本講義ではPython3を使用します．trackではPython3.6.1がサポートされています（2021年3月現在）．それ以外の言語の使用は認めません．また，track以外のシステムを用いた課題提出も認めません．
コードチャレンジには2種類あります．
基本課題はぜひしっかりと取り組み，解いてください．その上でExtra課題にも取り組んでもらえればと思います．Extra課題はレポート課題との選択肢気になっており，どちらか一方を提出していただければ問題ありません．Extra課題を提出した上でレポート課題を提出した場合は，より点数の高い方を成績評価に利用します．
講義パート終了後すぐ，google formにより登録していただいたメールアドレスに対して，trackからのメールを配信します．そのメールに該当する回の課題を行うページへのリンクが記載されています．track上でのコーディング・デバッグ方法，および課題提出方法はこちらのPDFを参照してください．
メールはnoreply@tracks.runより配信されますので，メールクライアント等においてフィルタリング機能を設定している場合には，このメールアドレスからのメールを受信できるように予め設定をしてください．また，アドブロッカーなどを使用していると，ブラウザ上でうまく表示できなかったり，エラーを起こしたりすることがあります．この場合には，アドブロッカーを一時的に停止させてみてください．
trackにおけるトラブルが発生した場合は，slackにてTAさんに連絡をしてください．
コードチャレンジではいくつかのテストケースが予め設定されています．それらテストケースの通った数を元に，原則[配点]*[テストケース合格率]で点数を計算します．採点に特別な扱いがある場合には，その旨を問題文に記します．
頻繁にテストケースを実行し，デバッグを行ってください．これにより提出間際でのミスを防ぐことができる他，コードが自動保存されるので，万が一提出作業を行えなくても，最終保存されたコードを元に採点が 行われます．
採点は最終提出物に対してのみ行われます．したがって，途中でどれだけミスをしていてもペナルティはありません．また，提出までにかかった時間の長短は採点に考慮されません．
Extra課題に関しては提出されたコードに対して後日類似度チェック等を行い，明らかに類似したコードが あった場合は，その全てに対してペナルティを課します．基本課題に関してはほぼ同じようなコードになるはずですので，このルールを直接は適用しませんが，類似度チェックは行います．また，指示に従った提出物になっているかのチェックも行います．
講義で使うシステムではコードをテストケースにかけた時点で，自動でバージョン管理します．コピペ等を行なった場合には，不自然にコード行数が増えたり，テストケースにパスする回数が突然増えたりするので，その辺りも必要に応じてチェックします．不自然な編集があった提出に関してはペナルティを適用することがありますので，十分気をつけてください．
与えられた基本課題においては，入出力や問題文で指示がある場合を除き，実装すべき処理において標準ライブラリや問題で指定されていない外部の関数やライブラリ等を使用しないでください． そのような提出物はテストケースに合格していても，採点されませんで注意してください．Extra課題においては，適宜外部の関数等を使っても良いものとします．
コードチャレンジの課題によってはコードの一部分（コーディング画面の初期コードとは別のコード）があらかじめ与えられている場合があります． その場合，問題文に明記してありますので，指示に従ってください．
コードチャレンジの課題を見ながら，本やWeb上の情報を参考にすることは問題ありません．ただし， 記載されているコードなどをそのまま使うことのないようにしてください．また，友達同士で教え合うのも積極的に行ってください（教えることができる，というのは十分に理解できている証拠でもあります）．ただし，書いたコードを直接見せ合うのではなく，考え方だけを共有するようにしてください．
この講義で重要なのは，「自分で手を動かす」ことを大切にすることです．アルゴリズムやコーディングに自信がなくても，授業で紹介されている内容を理解し，努力すれば一定の評価につながるようになっていますので，後から誤解を招きかねない行為をしないようにお願いいたします．
提出物に対しては後日類似度チェックを行います．以下のような提出物は該当するものすべてに対して採点を取り消します．
悪質な場合にはより大きなペナルティになることがあります．十分気をつけてください．
コードチャレンジの締め切り後はシステムの仕様上，提出したコードにアクセスすることができません．後日こちらからgoogle drive経由で提出されたコードを返却します．テストケースも共有しますので，ご自身での自習に活用してください．
また，Extra課題に関しては，解答例と簡単な解説をその次の講義回にて共有します．基本課題は授業のスライドにある情報で実装できるようになっていますので，授業のスライドをよく確認してください．
手元，もしくはtrack上でより細かくどのテストケースでうまく行っていないかを確認するためには以下のようなコマンドを使用すると良いです．
python3 main.py < ./test/in/basic/[入力するファイル名] | (cat ./test/out/basic/[想定出力結果のファイル名] | diff /dev/fd/3 -) 3<&0
期末試験は原則対面です．期末試験の実施方法に関しては，ここで詳細を連絡をします．
過去の期末試験は，こちらに置いてあります．自習の参考にしてください．ただし，試験時間，大問・小問の数，解答形式，出題範囲，問題の難易度などは年度により変更がある可能性があります．授業中のアナウンスを十分よく確認してください．
https://drive.google.com/drive/folders/1Coxpw6JYwA09npRfTwq-Aa_XwlRTviq8?usp=sharing
期末試験座席表はこちらのとおりです．もし，受験予定で，自分の学籍番号がない場合は，至急矢谷まで連絡をしてください．
https://drive.google.com/file/d/1Y1Zuj9S2siGyqwQyXRGspjqmkVdZR8C2/view?usp=sharing
以下の情報をメールにて，algorithms “at-mark” iis-lab.orgに送ってください．可能な限り事前に，事後でも速やかにお願いします．
認められた場合，課題提出期限をこちらが指定する日時まで延長します．
大きな怪我や病気などの例外を除き，病欠，公欠を希望する授業日から1週間以上を経過した場合は，認めないものとします．
剽窃や不適切な引用，改竄などはAcademic Misconductとして重い処分を受けます．この講義ではコードチャレンジにおける提出物や，期末試験での答案における不正行為により不当に評価を得ようとする行為に対して特に厳重に処罰します．例えば，
などが挙げられます．特に重大なAcademic Misconductが発見された場合，その影響度の大きさに応じて以下の罰則を与えることになります．
レポートやソースコードは誤解の生じないように十分注意して作成・管理してください．
以下の書籍・リンクはこの講義の資料を作る際に参考にさせていただいたり，講義内容に関する大きな刺激を受けたものになります．以下に挙げているもの以外にも参考になる様々な情報がありますので，興味を持ったトピックに関して色々とご自身で調べていただければと思います．
またpythonの基礎の学習には様々なオンラインコースがありますので，それを活用することをおすすめします．
ここでは講義中に出た講義に関係する質問とその返答を取り上げています．
import sys
import resource
resource.setrlimit(resource.RLIMIT_STACK, (-1, -1)) # スタック領域を拡大
sys.setrecursionlimit(1000000) # 再帰回数の上限を拡大