データ構造とアルゴリズム
2023年度 秋学期 月曜2時限（10:55〜12:35）
授業形態: 対面授業
登録コードSCT63600
第1回（10月2日）
アルゴリズムとは？データ構造とは？
総当たり戦スケジュール表の作成，演習問題の解答例
安定マッチング，演習問題の解答例
アル・フアリズミー（Al Kwarizmi）と乗算，演習問題の解答例
第2回（10月9日）
アルゴリズムの記述
計算問題とアルゴリズム，演習問題の解答例
アルゴリズムの記述と再帰表現，演習問題の解答例
最大値を求める問題に対するアルゴリズム（Google colabによるコード例）
アル・フアリズミーによる（？）乗算（Google colabによるコード例）
総当たり戦スケジュールを出力するcircle method（Google colabによるコード例）
素数列挙三種（Google colabによるコード例）
第3回（10月16日）
アルゴリズムの正当性の確認
最大公約数を求める問題に対するユークリッドの互除法（Google colabによるコード例）
第4回（10月23日）
アルゴリズムの正当性の確認の続き
平方根の見積もりのための2分法（Google colabによるコード例）
安定マッチング問題に対するGale-Shapleyアルゴリズム，演習問題の解答例
アルゴリズムの性能と計算複雑度
第5回（10月30日）
アルゴリズムの性能と計算複雑度の続き
漸近的解析とO記法，演習問題の解答例
第6回（11月6日）
これまでに紹介したアルゴリズムの時間複雑度
Gale-Shapleyアルゴリズム（Google colabによるコード例）
第8回（11月20日）
グラフ探索アルゴリズム（Google colabによるコード例）
第9回（11月27日）
深さ優先探索アルゴリズムの再帰版とスタック版の比較（Google colabによるコード例）
第10回（12月4日）
有向グラフとアルゴリズム
トポロジカル・オーダー，演習問題の解答例
並べ替え
第11回（12月11日）
分割統治法
マージソート，演習問題の解答例
マージソート（再帰版）（Google colabによるコード例）
Strassenの行列積，演習問題の解答例
その他分割統治法に関して，演習問題の解答例
第12回（12月18日）
動的計画法
ナップサック問題に対する動的計画法のコード例（Google colabによるコード例）
単始点最短路問題とダイクストラ法のコード例（Google colabによるコード例）
全点間最短路問題とFloyd-Warshall法のコード例（Google colabによるコード例）
第13回（1月15日）
前回の続き
第14回（1月22日）
貪欲アルゴリズム
Kruskalのアルゴリズム（union find tree以降は付録扱い）
最小全域木とKruskalのアルゴリズムとunion find tree（Google colabによるコード例）
ヒープとヒープソート，演習問題の解答例
付録
ネットワーク・フロー
エドモンズ・カープのアルゴリズムのコード例（NetworkX使用，NetworkX不使用）
計算困難問題に対するアプローチ（解答例なし）
おまけのパズル（乱択アルゴリズムと関連して）