講義・演習‎ > ‎春・夏学期‎ > ‎

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

  • 2017年度 夏学期 水曜5時限(16:50〜18:35)
  • 本郷キャンパス 工学部2号館 1階 212号講義室
日付 内容  備考 
4月5日  ガイダンスアルゴリズムとは?データ構造とは? (完全版 完全版には講義前に空白になっていた箇所および演習問題の解答例も含まれています.
4月19日  アルゴリズムの記述,アルゴリズムの正当性完全版 記号と用語
最大値,最大公約数,2分探索のコード例
4月26日  アルゴリズムの性能と計算複雑度完全版
Circle method,アル・フアリズミの乗算,素数列挙のコード例
5月10日 再帰アルゴリズム完全版
Gale-Shapleyアルゴリズムのコード例
5月17日  分割統治法完全版 5月10日に分割統治法まで説明できるかもしれないという希望的観測に基づき挙げておきます.
ユークリッドの互除法(再帰版)とマージソートのコード例
5月24日  グラフ理論入門とグラフ探索完全版 グラフ探索アルゴリズムのコード例,本日は再び「グラフ探索問題」から説明します.
5月31日  有向グラフと最短路問題など完全版),バケット,ハッシュ,ヒープ完全版

6月7日 最適化問題,動的計画法完全版 本日は,バケット,ハッシュ,ヒープの20ページ目から説明します.
訂正: ナップサック問題のfを「『高々』cのときの最大価値」と定義したので,f(7) = max{f(6), f(5) +16, ...}でした.
6月14日  ネットワークフロー演習問題の解答例を含むコード例 レポート課題1
今回は,動的計画法の編集距離から説明します.
6月21日 貪欲アルゴリズム完全版 今回は,ネットワークフローの最大流・最小カット定理から説明します.
Kruskal's algorithmのコード例
6月28日 計算問題の難しさの測り方
7月5日 計算困難問題に対するアプローチ 今回は「計算問題の難しさの測り方」のNP完全の定義から説明します.
期末試験の過去問には解答例はつけないです.
おまけのパズル
7月12日  オンラインアルゴリズム 今回は「計算困難問題に対するアプローチ」の最初から説明します.
アンケートやります,
おまけのパズルの解答例
レポート課題2
7月19日 期末試験 いつもの時間(105分),いつもの場所,持込不可