情報工学概論（アルゴリズムとデータ構造）
2023年度 夏学期 水曜5時限（16:50〜18:35（105分授業））
対面講義
第1回（4月5日）
アルゴリズムとは？データ構造とは？
言葉による説明
総当たり戦スケジュール表の作成，演習問題の解答例
安定マッチング，演習問題の解答例
アル・フアリズミー（Al Kwarizmi）と乗算，演習問題の解答例
アルゴリズムとデータ構造を学ぶ目的や意義，この講義の狙い
第2回（4月19日）
アルゴリズムの記述と正当性の確認
計算問題とアルゴリズム
アルゴリズムの記述と再帰表現，演習問題の解答例
最大値を求める問題に対するアルゴリズム（Google colabによるコード例）
アル・フアリズミーによる（？）乗算（Google colabによるコード例）
総当たり戦スケジュールを出力するcircle method（Google colabによるコード例）
素数列挙三種（Google colabによるコード例）
ユークリッドの互除法
最大公約数を求める問題に対するユークリッドの互除法（Google colabによるコード例）
平方根の見積もりのための2分法
平方根の見積もりのための2分法（Google colabによるコード例）
安定マッチング問題に対するGale-Shapleyアルゴリズム，演習問題の解答例
第3回（4月26日）
アルゴリズムの性能と計算複雑度
アルゴリズムの評価法
漸近的解析とO記法，演習問題の解答例
第4回（5月10日）
アルゴリズムの計算複雑度の続き
ユークリッドの互除法の時間複雑度，演習問題の解答例
Gale-Shapleyアルゴリズムの時間複雑度
Gale-Shapleyアルゴリズム（Google colabによるコード例）
無向グラフと有向グラフ
無向グラフと有向グラフの定義
第5回（5月17日）
グラフ探索
部分グラフ，パス，閉路
連結グラフ，隣接・後続・先行頂点集合，森，木
グラフ探索と頂点隣接リスト
PythonとGoogle colabによるコード例
第6回（5月24日）
グラフ探索の続き
スタックと深さ優先探索
キューと幅優先探索
有向グラフとアルゴリズム
第7回（5月31日）
有向グラフとアルゴリズム
トポロジカル・オーダー
バケットソート，基数ソート，選択ソート，ヒープソート
第8回（6月7日）
貪欲アルゴリズム
最小全域木問題
Primのアルゴリズム
Kruskalのアルゴリズム
Huffman木の構成
PythonとGoogle colaboratoryによるコード例
第9回（6月14日）
分割統治法
ハノイの塔
マージソート，演習問題の解答例
Strassenの行列積，演習問題の解答例
その他分割統治法に関して，演習問題の解答例
PythonとGoogle colaboratoryによるコード例
第10回（6月21日）
動的計画法
ナップサック問題
ナップサック問題に対する動的計画法
編集距離と動的計画法
単始点最短路問題に対するダイクストラ法
動的計画法の演習問題
PythonとGoogle colaboratoryによるコード例
第11回（6月28日）
ネットワークフロー
最大流問題問題
最大流問題に対する増加道アルゴリズム
最大流・最小カット定理
最大流の整数性とその応用
最大流問題の演習問題
PythonとGoogle colaboratoryによるコード例
第12回（7月5日）
計算困難問題に対するアプローチ
ナップサック問題に対する分枝限定法
ナップサック問題に対する近似解法
第13回（7月12日）
その他のトピックス