コンピュータを用いて具体的な問題を解くための基礎

"2年次の科目「アルゴリズムとデータ構造Ⅰ」では、プログラミングによる問題解決の「定石」として、基本的なアルゴリズムとデータ構造について講義を行いました。本科目では、その基礎を踏襲した上で、より具体的な問題を解くためのモデル化、アルゴリズム、データ構造について学んでいきます。

・復習: コンピュータで問題を解くためには(アルゴリズムとデータ構造の必要性)
・グラフを使った問題のモデル化
・グラフアルゴリズムとデータ構造
・情報検索への応用
・配列解析"

"・現実の問題を解くためのモデル化、アルゴリズム、データ構造の必要性について理解するとともに、
具体的な問題について、それらがどのように適用されるかを理解する。
・本講義で扱う範囲の問題について、プログラミング言語を用いて解けるようになる
"

"以下を予定している。
1. 復習: 問題のモデル化、アルゴリズム、データ構造
2. グラフによる問題のモデル化: オイラー閉路と最短経路問題
3. グラフアルゴリズム: オイラー閉路と最短経路問題
4. 最短経路問題とデータ構造
5. アルゴリズムの設計手法(1): 分割統治法、貪欲法
6. アルゴリズムの設計手法(2): 動的計画法
7. 情報検索への応用(1); PageRank
8. 中間試験
9. 情報検索への応用(2); HITS
10. ネットワークフロー(1)
11. ネットワークフロー(2)
12. 配列解析(1): 配列アラインメントと生物情報学
13. 配列解析(2): 正規表現とオートマトンとアラインメントの関係
14. まとめと発展的話題
15. 期末試験"

各自がオンライン教材を用いた予習・復習を行うことを前提に、躓きやすい点の解説や、課題のフォローアップと解説を中心に実施します。

各回のトピックに対応した課題に、講義中および講義外の時間を活用して取り組むことが必須です。

講義中に複数回実施する試験の結果と、課題の提出内容により評価を行います。なお5回以上欠席した場合には、理由の如何を問わず、単位は習得できません。

「CS概論2」アルゴリズム編の内容を理解していることを前提とします。

各回の講義に対応したオンライン教材を事前に提供します。

授業中に紹介します。