本講義では情報科学の重要な基礎となっているアルゴリズムとデータ構造に関して学習します．具体的には，
ことを目的としています．この講義を通して
ことができるように授業が設計されています．
本講義は，学部横断型プログラム「数理・データサイエンス教育プログラム」の対象になっています．
http://www.mi.u-tokyo.ac.jp/mds-oudan/
本授業は原則対面形式で行いまが，メタバース工学部生はオンラインで受講することを許可します． 講義終了後には講義の録画を提供します．
講義の配信動画を視聴したり，プログラミング課題に取り組むためには，インターネット環境，およびブラウザが必要です．なお，従量課金制による通信費がかからないよう，無料で使えるWifi環境がある場所や定額制のインターネット接続環境で受講することを強く推奨します．
本授業はメタバース工学部においても同時開講されます．受講形式，評価基準が本学学生とメタバース工学部生では異なります． どちらの受講生も本ページで提供されている情報をよく確認して受講してください．
| 場所 | 工学部2号館4階241講義室，およびオンライン（Youtube Live） |
|---|---|
| 時間 | 水曜日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=2023FEN-EE3d08L10F01 |
講義終了後の録画を見るためのURLは下記ドキュメントに記載してありますので，授業後に確認してください． ECCSアカウントでのログインが必要です．
https://docs.google.com/document/d/1gw3Bf1bl6nrafvzH8wyxBilnSXHNtVOWXhJ5hhILAmw
講義終了後の録画はYoutubeにて共有しますので，リアルタイム配信と同じURLを使用することができます． Slackの#metaverseチャネルにてGoogle docの共有ドキュメントの情報をお送りしています．その中で動画配信のURLをお知らせしますので，確認してください．
講義で使用するスライドのPDFは以下の講義スケジュールからリンクしています．講義当日の12時ごろまでにはアップロードする予定ですが，遅れることもあります．CC BY-SAライセンスで一般に公開しています．
| 回 | 日程 | 講義内容・キーワード |
|---|---|---|
| #1 | 4/10 | イントロダクション，計算量，trackの利用方法 |
| 計算量 | ||
| #2 | 4/17 | 累積和，整数関連 |
| 累積和，しゃくとり法，ユークリッドの互除法，素数判定，エラストてネスのふるい，繰り返し自乗法，剰余の四則演算 | ||
| #3 | 4/24 | データ構造 |
| スタック，キュー，デック，連結リスト，二分木，ヒープ，セグメント木，BIT | ||
| #4 | 5/1 | 探索（サーチ） |
| 線形探索，二分探索，二分探索木，平衡木，ハッシュ | ||
| #5 | 5/8 | 整列（ソート） |
| ボゴソート，挿入ソート，ツリーソート，バブルソート，シェーカーソート，シェルソート，クイックソート，マージソート，ヒープソート，バケットソート | ||
| #6 | 5/22 | 文字列照合 |
| 力任せ法，KMP法，BM法，BMH法，ローリングハッシュ | ||
| #7 | 5/29 | 動的計画法1（基本のDP） |
| メモ化再帰，フィボナッチ数，最大和問題，コイン問題，ナップサック問題 | ||
| #8 | 6/5 | 動的計画法2（いろいろなDP） |
| レーベンシュタイン距離，動的時間伸縮法（DTW），配るDP・貰うDP | ||
| #9 | 6/12 | 幅優先探索，深さ優先探索 |
| 隣接リスト，隣接行列，BFS,DFS，オイラーツアー，LCA，橋の検出 | ||
| #10 | 6/19 | グラフアルゴリズム1（最短経路問題） |
| ダイクストラ法，ベルマン・フォード法，SPFA，ワーシャル・フロイド法 | ||
| #11 | 6/26 | グラフアルゴリズム2（最小全域木，トポロジカルソート） |
| クラスカル法，プリム法，素集合データ構造（Union-Find木），有向非巡回グラフ（DAG），Kahnのトポロジカルソート，Tarjanのトポロジカルソート，DAGでの最短経路 | ||
| #12 | 7/3 | グラフアルゴリズム3（最大流問題） |
| フロー，フォード・ファルカーソン法，グラフのカット，最大流・最小カット定理，二部グラフの最大マッチング問題 | ||
| #13 | 7/10 | グラフアルゴリズム4（最小費用流問題），「難しい問題」とは，さいごに |
| プライマル・デュアル法，重み付き二部グラフの最大マッチング問題，P・NP問題，多項式時間還元，NP完全，NP困難 |
本講義を受講する場合，以下の知識，経験，および実験機器があることを想定しています．
本講義を受講希望の方は以下のフォームより登録を行ってください．ECCSアカウントでログインしておく必要があります．また，単位習得のためにこの講義を受講する方はUTASでの登録を別途行ってください．
https://forms.gle/yjhQq32V1FemVeWi8
特段の手続きはありません．
本学学生とメタバース工学部生で成績評価方法が大きく異なります．自分に当てはまる方の評価方法をよく理解した上で受講してください．
病欠，公欠等の理由により期限内に課題が提出ができない場合，講義担当者へメールにて連絡をして，対応を相談してください．事前の相談がない場合は救済措置が難しくなる可能性があることをご承知おきください．
成績の評価は以下のように行います．
ただし，期末試験を受験しなかった場合，この講義の成績は「未受験」という扱いになります．もし，期末試験を受験しないが成績をつけてほしい場合には，個別に期末試験前日までに連絡をしてください．（もちろん成績は総得点によりますので，連絡をしたら必ず単位が来る， ということではありません．）
修了基準は以下のとおりです．
Extra課題は提出しなくても成績に対するペナルティはありませんが，提出された場合は0.5を乗じた上で総得点に加算することとします．例えば，基本課題で10点，Extra課題で10点を取った場合，10 + 0.5 * 10 = 15となり，点数に関する修了基準を満たすことになります．
講義はハイブリッド形式で行います．また，各回の講義は録画しており，講義終了後でも視聴が可能です．
授業中及びその後の授業内容に関する質問は，slackで行ってください．
コマンドを利用することで匿名でメッセージを送ることができます．名前を出したくない場合は，その機能を使ってください．
また，講義担当者からは授業の理解度を図るために，授業中にslackで呼びかけを行いますので，リアクションしてもらえると嬉しいです．
成績のうち約1/3は，Extra課題を毎週提出するか，以下に示すレポート課題を期限までに提出することで与えられます．レポート課題を提出した上で，Extra課題を提出している方は，より点数の高い方を成績評価に利用します．
レポート課題の具体的な内容は以下のPDFを参照してください．
https://yatani.jp/teaching/lib/exe/fetch.php?media=2024algorithms:report.pdf
レポート課題の提出にはTurnitinを利用します． Turnitinへの招待は6月末頃〜7月頭に行う予定です．
メタバース工学部生はレポート課題の提出は必要ありません．
本講義のコードチャレンジではtrackというシステムを使います．trackはオンライン上でプログラミングに関する学習を行ったり，指定された課題に対して自分のコードを提出したりすることが出来ます．またコーディング自体をブラウザ上でできるようになっているため，コーディングに必要な環境構築等を行う必要がありません．
本講義ではPython3を使用します．それ以外の言語の使用は認めません．また，track以外のシステムを用いた課題提出も認めません．
コードチャレンジには2種類あります．
基本課題はぜひしっかりと取り組み，解いてください．その上でExtra課題にも取り組んでもらえればと思います．Extra課題はレポート課題との選択肢気になっており，どちらか一方を提出していただければ問題ありません．Extra課題を提出した上でレポート課題を提出した場合は，より点数の高い方を成績評価に利用します．
なお，メタバース工学部生に対してもExtra課題に取り組むことはオプションとなっていますが，本学学生の場合と違う扱いとなり，提出した場合は加点対象となります（成績評価のところを参照のこと）．
本講義で利用するtrackのURLはこちらです．
https://eeic-algorithms.train.tracks.run/auth/login
上記ページにアクセスし，右下にある「受験環境を確認する」を押し，すべての項目で問題なしになることを事前に確認してください．
アカウント名，初期パスワードは以下のように設定されています．
trackから届いているメールに従い，登録作業を完了させてください．
アドブロッカーなどを使用していると，ブラウザ上でうまく表示できなかったり，エラーを起こしたりすることがあります．この場合には，アドブロッカーを一時的に停止させてみてください．
trackにおけるトラブルが発生した場合は，slackにてヘルプリクエストを出してください．
コードチャレンジではいくつかのテストケースが予め設定されています．それらテストケースの通った数を元に，原則[配点]*[テストケース合格率]で点数を計算します．採点に特別な扱いがある場合には，その旨を問題文に記します．
頻繁にテストケースを実行し，デバッグを行ってください．これにより提出間際でのミスを防ぐことができる他，コードが自動保存されるので，万が一提出作業を行えなくても，最終保存されたコードを元に採点が 行われます．
採点は最終提出物に対してのみ行われます．したがって，途中でどれだけミスをしていてもペナルティはありません．また，提出までにかかった時間の長短は採点に考慮されません．
Extra課題に関しては提出されたコードに対して後日類似度チェック等を行い，明らかに類似したコードが あった場合は，その全てに対してペナルティを課します．基本課題に関してはほぼ同じようなコードになるはずですので，このルールを直接は適用しませんが，類似度チェックは行います．また，指示に従った提出物になっているかのチェックも行います．
講義で使うシステムではコードをテストケースにかけた時点で，自動でバージョン管理します．コピペ等を行なった場合には，不自然にコード行数が増えたり，テストケースにパスする回数が突然増えたりするので，その辺りも必要に応じてチェックします．不自然な編集があった提出に関してはペナルティを適用することがありますので，十分気をつけてください．
与えられた基本課題においては，入出力や問題文で指示がある場合を除き，実装すべき処理において標準ライブラリや問題で指定されていない外部の関数やライブラリ等を使用しないでください． そのような提出物はテストケースに合格していても，採点されませんで注意してください．Extra課題においては，適宜外部の関数等を使っても良いものとします．
コードチャレンジの課題によってはコードの一部分（コーディング画面の初期コードとは別のコード）があらかじめ与えられている場合があります． その場合，問題文に明記してありますので，指示に従ってください．
コードチャレンジの課題を見ながら，本やWeb上の情報を参考にすることは問題ありません．ただし， 記載されているコードなどをそのまま使うことのないようにしてください．また，友達同士で教え合うのも積極的に行ってください（教えることができる，というのは十分に理解できている証拠でもあります）．ただし，書いたコードを直接見せ合うのではなく，考え方だけを共有するようにしてください．
この講義で重要なのは，「自分で手を動かす」ことを大切にすることです．アルゴリズムやコーディングに自信がなくても，授業で紹介されている内容を理解し，努力すれば一定の評価につながるようになっていますので，後から誤解を招きかねない行為をしないようにお願いいたします．
提出物に対しては後日類似度チェックを行います．以下のような提出物は該当するものすべてに対して採点を取り消します．
悪質な場合にはより大きなペナルティになることがあります．十分気をつけてください．
コードチャレンジの締め切り後もtrack上で自分のコードにアクセスすることができますので，適宜自習に活用してください．ただし，提出期限後の変更や得点の変化は採点には反映されません．
また，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
期末試験座席表はこちらのとおりです．もし，受験予定で，自分の学籍番号がない場合は，至急矢谷まで連絡をしてください．
https://drive.google.com/file/d/12-gmjZ9j8CQ5XHTB4XOknTwd3Jxzqcxo/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) # 再帰回数の上限を拡大
python3 main.py < ./test/in/basic/[入力するファイル名] | (cat ./test/out/basic/[想定出力結果のファイル名] | diff /dev/fd/3 -) 3<&0