科目ナンバー

SE-AN4-1B53

履修条件・関連科目等

授業で使用する言語

日本語

授業で使用する言語（その他の言語）

授業の概要

計算の複雑さについて講義する．
特に，グラフ理論や代数学や他の数学的問題の計算の複雑さについて議論する．
その過程において，計算量やアルゴリズムやデータ構造について理解し，数学的問題を解くことをアルゴリズムやデータ構造の問題に対応付けることについて議論する．
また，計算量を評価することによって計算時間を見積もり，実際に高速に動作する効率の良いプログラムを実装する．

科目目的

基本的なアルゴリズムやデータ構造について理解し，数学的問題に対して計算量の評価をしつつプログラミングに応用できることを目的とする．

到達目標

数学的問題に対して，計算時間を見積もり，アルゴリズムやデータ構造を用いて正しく実装できることを目標とする．

授業計画と内容

第1回 計算量
第2回 全探索（深さ優先探索，幅優先探索）
第3回 貪欲法（区間スケジューリング問題など）
第4回 動的計画法（ナップサック問題など）
第5回 動的計画法（最長増加部分列問題など）
第6回 木（ヒープ，Union-Find）
第7回 グラフアルゴリズム（二部グラフ判定）
第8回 グラフアルゴリズム（最短路問題，最小全域木）
第9回 代数学の問題（ユークリッドの互除法，素数，剰余）
第10回 問題演習
第11回 二分探索，尺取り法
第12回 半分全列挙，座標圧縮
第13回 セグメント木，Binary Indexed Tree
第14回 バケット法と平方分割

授業時間外の学修の内容

指定したテキストやレジュメを事前に読み込むこと／授業終了後の課題提出

授業時間外の学修の内容（その他の内容等）

授業で扱った問題，アルゴリズム，データ構造，計算量について復習し，プログラミングすること．
特に，授業時に指示する課題に取り組むこと．

授業時間外の学修に必要な時間数／週

・毎週１回の授業が半期（前期または後期）または通年で完結するもの。１週間あたり４時間の学修を基本とします。
・毎週２回の授業が半期（前期または後期）で完結するもの。１週間あたり８時間の学修を基本とします。

成績評価の方法・基準

成績評価の方法・基準（備考）

課題や試験のフィードバック方法

授業時間内で講評・解説の時間を設ける

課題や試験のフィードバック方法（その他の内容等）

アクティブ・ラーニングの実施内容

実施しない

アクティブ・ラーニングの実施内容（その他の内容等）

授業におけるICTの活用方法

実施しない

授業におけるICTの活用方法（その他の内容等）

実務経験のある教員による授業

いいえ

【実務経験有の場合】実務経験の内容

【実務経験有の場合】実務経験に関連する授業内容

テキスト・参考文献等

開講時に指示する。

その他特記事項

授業ではmanabaを用いるためIDとパスワードを確認しておくこと．

参考URL