2024年度 秋学期 月曜2時限(10:55〜12:35)
授業形態: 対面授業
登録コードSCT63600
アルゴリズムの記述
最大値を求める問題に対するアルゴリズム(Google colabによるコード例)
アル・フアリズミーによる(?)乗算(Google colabによるコード例)
総当たり戦スケジュールを出力するcircle method(Google colabによるコード例)
素数列挙三種(Google colabによるコード例)
アルゴリズムの正当性の確認
最大公約数を求める問題に対するユークリッドの互除法(Google colabによるコード例)
平方根の見積もりのための2分法(Google colabによるコード例)
アルゴリズムの性能と計算複雑度
多項式関数と指数関数の増加の比較(Google colabによるコード例)
前回のつづき
アルゴリズムの時間複雑度
Gale-Shapleyアルゴリズム(Google colabによるコード例)
前回の続き
グラフ探索の続き
深さ優先探索アルゴリズムの再帰版とスタック版の比較(Google colabによるコード例)
分割統治法
マージソート(再帰版)(Google colabによるコード例)
付録(ハノイの塔)
動的計画法
ナップサック問題に対する動的計画法のコード例(Google colabによるコード例)
単始点最短路問題とダイクストラ法のコード例(Google colabによるコード例)
全点間最短路問題とFloyd-Warshall法のコード例(Google colabによるコード例)
前回の続き
貪欲アルゴリズム
Kruskalのアルゴリズム(付録扱い)
最小全域木とKruskalのアルゴリズムとunion find tree(Google colabによるコード例)
ネットワーク・フロー
付録
エドモンズ・カープのアルゴリズムのコード例(NetworkX使用,NetworkX不使用)
計算困難問題に対するアプローチ(解答例なし)
おまけのパズル(乱択アルゴリズムと関連して)