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