情報工学概論(アルゴリズムとデータ構造)

  • 2021年度 夏学期 水曜5時限(17:05〜18:35(90分授業))

  • オンライン講義 (ZoomミーティングのIDとパスコードなどはシラバスに記載しています)

第1回(4月7日)

  • ガイダンス

  • アルゴリズムとは?データ構造とは?

    • 講義資料(解答例なし解答例あり

      • 解答例なしの講義資料は「演習問題の解答例がいきなり見えたら興ざめだ」という受講生のためのものです.

    • Q&A

      • 講義の中で「一般に与えられた好みに対して,安定マッチングは複数ある」と言いましたが,安定マッチングの個数を数えるアルゴリズムはありますか?

        • 数えること自体は,完全マッチングを列挙してそのそれぞれの安定性を確認することで,できます.ただしそのやり方だと男女の人数が増えると,計算の手間が膨大になります.効率的な数え方があるか否かに関しては,「安定マッチングの数え上げは#P-complete」であることが知られています.

      • 3グループ以上の安定マッチングはありますか?

        • 3グループ以上の安定マッチングに関しては,Knuthがその著書の中で「3-dimensional stable matching」を論じているようです(が私はその本を読んでいません).代わりに別の参考文献を挙げておきます.これによると3-dimansional stable matchingがあるかどうかの判定はNP-completeのようです.

第2回(4月14日)

第3回(4月21日)

第4回(4月28日)

第5回(5月12日)

第6回(5月19日)

第7回(5月26日)

  • 前回の続き

    • 今回は「グラフ理論入門とグラフ探索」の「グラフ探索問題とグラフ探索アルゴリズム」から説明します.

(6月2日はお休み)

第8回(6月9日)

  • 有向グラフ

    • 講義資料(解答例なし解答例あり

    • 前回は(演習問題はきちんと説明しなかったものの)「グラフ理論入門とグラフ探索」の説明をちょうど終えたので,「有向グラフ」の最初からお話したいと思います.

第9回(6月16日)

  • バケット・ハッシュ・ヒープ

第10回(6月23日)

第11回(6月30日)

  • かなりずれてしまいましたが,今回は「動的計画法」の8ページ目から(再び)説明したいと思います.

第12回(7月7日)

  • ネットワーク・フロー

    • 講義資料 ← 今回は解答例はありません.最大流・最小カット定理を知っているならば,自分で確かめ算をできますからね.

    • PythonとGoogle colaboratoryによるコード例

第13回(7月14日)

  • 貪欲アルゴリズム

    • 講義資料(解答例なし解答例あり

      • 講義資料に書き忘れましたが,

        • プリムのアルゴリズムの時間複雑度は一般にO(m + n^2)(ただしnは頂点数,mはエッジ数)です.そして優先度付きキュー(priority queue)を工夫して使うとO(m log n)にできます.

        • クラスカルのアルゴリズムの正当性の証明にはcycle property定理の適用が素直です.Cut property経由ですと,少し頭を使う必要があります.

    • PythonとGoogle colaboratoryによるコード例

  • 計算問題の難しさの測り方

期末試験(2021年7月21日実施予定)あるいはレポートによる評価

期末試験の実施に関しては,様々な情勢を考慮した上で決定します.

社会情勢次第では,オンライン期末試験やレポートによる評価を検討します.

2021年度はオンライン試験あるいはレポートによる評価とします.

レポート課題の詳細は7月7日にお知らせしました.

レポート課題