User Tools

Site Tools


2020algorithms:start

アルゴリズム(2020年度)



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



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

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

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

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

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


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

場所 オンラインで実施予定.
時間水曜日3限(13:00 - 14:45),ただし講義の動画,およびPDFは後からでも見ることが可能.
講義担当者相田 仁,矢谷 浩司 (koji “at-mark” iis-lab.org)
TA 杉山 悠司,鈴木 凌斗 (algorithms “at-mark” iis-lab.org)



講義スケジュール


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

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

日程 講義内容
#04/8プレイントロ,授業で使うシステムの紹介,general Q&A
trackの利用方法
#14/15イントロダクション,計算量
trackの利用方法
#24/22累積和,データ構造
#35/7 (木)探索(サーチ)
#45/13文字列照合
#55/20整列(ソート)
#65/27動的計画法1(フィボナッチ数列,最大和問題,ナップサック問題)
#76/3動的計画法2(その他のDP問題)
#86/10整数関連
#96/17BFS,DFS
#106/24グラフアルゴリズム1(最短経路問題)
#117/1グラフアルゴリズム2(最大流問題,最小費用流問題)
#127/8グラフアルゴリズム3(二部グラフのマッチング問題,最小全域木)



講義を受講するにあたり


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

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

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

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

ECCSアカウント

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

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



成績評価


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

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

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



講義形式


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

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

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



講義パートの配信方法


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

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

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



Q&A


授業中及びその後の授業内容に関する質問は講義で使用するzoomにてお願いします.



コードチャレンジ


本講義のコードチャレンジでは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として重い処分を受けます.この講義ではコードチャレンジにおける提出物や,期末試験での答案における不正行為により不当に評価を得ようとする行為に対して特に厳重に処罰します.例えば,

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

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

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

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



参考資料・文献


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

2020algorithms/start.txt · Last modified: 2020/04/08 00:43 by Koji Yatani