データ構造とアルゴリズム
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不使用)
計算困難問題に対するアプローチ(解答例なし)
おまけのパズル(乱択アルゴリズムと関連して)