講義・演習‎ > ‎秋・冬学期‎ > ‎

SCT63600 データ構造とアルゴリズム

  • 2017年度 秋学期 月曜2時限(11:00〜12:30)
  • 四ツ谷キャンパス 1号館 403室
日付 内容  備考 
10月2日  ガイダンスアルゴリズムとは?データ構造とは? (完全版 完全版には演習問題の解答例も含まれます.

10月9日  アルゴリズムの記述と正当性完全版 最大値,最大公約数,平方根のコード例
スライドの量が多めだったので心配したのですが,ちょうど90分くらいで終わりました.

10月16日  アルゴリズムの性能と計算複雑度完全版
Circle method,アル・フアリズミの乗算,素数列挙のコード例
10月30日 再帰アルゴリズム完全版 Gale-Shapleyアルゴリズムのコード例
11月6日  分割統治法完全版 ユークリッドの互除法(再帰版)とマージソートのコード例記号と用語
11月13日  グラフ理論入門とグラフ探索完全版 グラフ探索のコード例
11月20日 有向グラフ完全版
11月27日  バケット,ハッシュ,ヒープ完全版)←講義後に指摘された完全版のミスを赤で修正しました. 最後は駆け足になってしまいました.ヒープの図を予め用意しておけばよかったかも.
12月4日 動的計画法完全版 単始点最短路問題とダイクストラ法全点間最短路問題とFloyd-Warshall法
今回は「単始点最短路問題に対するダイクストラ法」まで説明しました.
少し欲張りすぎたかもしれません.
12月11日 ネットワークフロー演習問題の解答例の板書演習問題の解答例を含むコード例 今回は「動的計画法」の「編集距離」から説明します.
Technobabbleの解説Technobabbleのコード例
12月18日貪欲アルゴリズム完全版
↑一応資料をアップロードしますが,ここまで到達しないかもしれません.
今回は,もう一度Edmonds-karpアルゴリズムから説明します.
第1回レポート課題
1月15日
Kruskal's algorithmのコード例
今回は貪欲アルゴリズムから説明します.
1月22日 計算困難問題に対するアプローチ
付録: 乱択アルゴリズムオンラインアルゴリズム
計算時間の比較
おまけのパズル
授業アンケート
ACM ICPC(興味があったら宮本まで連絡下さい)
補講 第2回レポート課題 おまけのパズルの解答例

1月29日 期末試験 試験会場は12-302,時間はいつもの時間(90分),持込不可

授業時間外の学修課題