情報工学概論(アルゴリズムとデータ構造)
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
試験範囲は上記講義資料の「付録と『少しだけ』」を除いたすべて