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

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

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

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

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

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

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

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

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

• 基礎的なPythonに関するプログラミング技術がある．
• trackでコーディングを行えるPC環境がある．OSに関しては問わない．ブラウザはChromeおよびFirefoxを推奨する．
• slackを使うことができる．講義内でアナウンスやコミュニケーションはslackで行います．

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

• 30点: コーディングチャレンジ 基本課題
• 30点: コーディングチャレンジ Extra課題
• 40点: 期末試験

ただし，状況に応じて点数配分を数点程度変更することがあります．出席はとりません．

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

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

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

矢谷が行う講義は全てYoutube Liveを通して配信されます．講義スケジュールのところに各回に使用する配信用URLが記載されていますので，確認しておいてください．

配信された講義は，配信終了後もオンラインで視聴できます．見逃してしまった人や見直したい人は各回のURLにアクセスすることで再視聴が可能です．

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

授業中及びその後の授業内容に関する質問は講義で使用するslackの各講義回のチャネルにてお願いします．

事前にYoutube Liveを講義で使用するPC環境で見ることができるかどうかを確認していただくと良いと思います．以下のリンクから動画を適当に選んで問題なく再生できるかどうかを確認してください．スマートフォンやタブレットで視聴する場合には，最新版にアップデートする必要がある場合がありますので，注意してください．

https://www.youtube.com/live?hl=ja&gl=JP

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

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

コードチャレンジの課題によってはコードの一部分（コーディング画面の初期コードとは別のコード）があらかじめ与えられている場合があります． その場合，問題文に明記してありますので，指示に従ってください．また，こちらが事前にインストールや用意しているもの以外のライブラリ，外部の関数等の利用はできません．そのような提出物はテストケースに合格していても，採点されませんで注意してください．

コードチャレンジの課題を見ながら，本や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/