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