情報工学概論（アルゴリズムとデータ構造）
2024年度 夏学期 水曜5時限（16:50〜18:35（105分授業））
対面講義
第1回（4月10日）
第2回（4月17日）
アルゴリズムの記述と正当性の確認
最大値を求める問題に対するアルゴリズム（Google colabによるコード例）
アル・フアリズミーによる（？）乗算（Google colabによるコード例）
総当たり戦スケジュールを出力するcircle method（Google colabによるコード例）
素数列挙三種（Google colabによるコード例）
最大公約数を求める問題に対するユークリッドの互除法（Google colabによるコード例）
第3回（4月24日）
今回は，「ユークリッドの互除法」の3ページから説明し，前回の演習問題の解答例を概説し，続けて「平方根の見積もりのための2分法」以降を説明します．
平方根の見積もりのための2分法（Google colabによるコード例）
アルゴリズムの性能と計算複雑度
多項式関数と指数関数の増加の比較（Google colabによるコード例）
第4回（5月1日）
今回は「安定マッチング問題に対するGale-Shapleyアルゴリズムの演習問題の解答例」を概説し，続けて「漸近的解析とO記法」の2ページ目から説明します．
アルゴリズムの計算複雑度の続き
第5回（5月8日）
今回は「漸近的解析とO記法」と「ユークリッドの互除法の時間複雑度」の解答例を概説し，つづけて「Gale-Shapleyアルゴリズムの時間複雑度」からお話します．
アルゴリズムの計算複雑度の続き
Gale-Shapleyアルゴリズム（Google colabによるコード例）
無向グラフと有向グラフ
第6回（5月22日）
今回は「無向グラフと有向グラフの定義」の12ページからお話します．
グラフ探索
グラフ探索アルゴリズム（Google colabによるコード例）
グラフ探索と頂点隣接リストまでを学べば以下の問題を解けると思います．
第7回（5月29日）
今回はグラフ探索と頂点隣接リストの9ページから
深さ優先探索アルゴリズムの再帰版とスタック版の比較（Google colabによるコード例）
深さ優先探索までを学ぶと以下の問題を解けると思います．
第8回（6月5日）
幅優先探索までを学ぶと以下の問題を解けると思います．
有向グラフとアルゴリズム
第10回（6月19日）
分割統治法
マージソート（再帰版）（Google colabによるコード例）
ハノイの塔（付録）
第11回（6月26日）
今回は，Strassenの行列積，その他分割統治法の演習問題の解答例を概観して，続けて，ナップサック問題に対する動的計画法の5ページからお話します．
動的計画法
ナップサック問題に対する動的計画法（Google colabによるコード例）
第12回（7月3日）
動的計画法の続き
単始点最短路問題とダイクストラ法のコード例（Google colabによるコード例）
全点間最短路とFloyd-Warshall法（Google colabによるコード例）
貪欲アルゴリズム
Kruskalのアルゴリズム（union find tree以降は付録扱い）
最小全域木とKruskalのアルゴリズムとunion find tree（Google colabによるコード例）
Huffman木の構成（付録）
第13回（7月10日）
Kruskalのアルゴリズムから説明します．
ネットワークフロー
最大流の整数性とその応用（付録）
エドモンズ・カープのアルゴリズムのコード例（NetworkX使用，NetworkX不使用）
講義時間の都合上，以降はすべて付録扱いです．
計算困難問題に対するアプローチ
計算問題の難しさの測り方（付録）
ナップサック問題に対する分枝限定法（Google colabによるコード例）
ナップサック問題に対する近似解法（付録）
オンラインアルゴリズム（付録）
期末試験（2024年7月31日実施予定）
試験時間は16:50から18:35
試験範囲は上記講義資料の「付録」を除いたすべて