科目ナンバー

SE-AN4-1B53

履修条件・関連科目等

授業で使用する言語

日本語

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

授業の概要

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

科目目的

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

到達目標

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

授業計画と内容

第1回 全探索
第2回 2進法
第3回 累積和
第4回 二分探索
第5回 動的計画法（1次元）
第6回 動的計画法（2次元）
第7回 素数判定法
第8回 ユークリッドの互除法
第9回 フェルマーの小定理
第10回 包除原理
第11回 ヒューリスティック
第12回 データ構造
第13回 深さ優先探索
第14回 幅優先探索

授業時間外の学修の内容

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

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

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

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

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

成績評価の方法・基準

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

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

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

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

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

実施しない

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

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

実施しない

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

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

いいえ

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

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

テキスト・参考文献等

米田優峻，競技プログラミングの鉄則 アルゴリズム力と思考力を高める77の技術，マイナビ出版，2022年，ISBN 978-4-8399-7750-4

その他特記事項

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

参考URL