01 / 読書ガイド
読書ガイド
対象読者
プログラミングとデータ構造の後の本科算法課程向け。著者も最初の算法入門とは区別する。設計、正しさ、実行時間をそれぞれ説明し、証明と計算量を混同しない練習になる。
前提知識
離散数学、帰納法、再帰、基本データ構造が前提。グラフ、漸近記法、漸化式を復習する。キュー、ハッシュ表、平衡木を初めから教える本ではない。
扱う内容
再帰とバックトラックから動的計画、貪欲法、グラフ探索、全域木、最短路、フロー、カット、NP困難性へ進む。同じページの追加講義録は補助資料であり、主巻とは範囲が異なる。
使い方
実装の前に入力と出力を定め、誤った直感を示す小例を作る。部分問題や貪欲な選択を正確に記し、正しさと計算量を別々に示す。同じ問題の二つの解法を比べ、失敗する改善案には反例を作る。最後に小規模の全探索で実装を確かめる。
版と出典
著者による全文第一版は2019年6月、472頁。教科書はCC BY 4.0、同じサイトの追加講義録はCC BY-NC-SA 4.0なので、再利用するファイルごとに区別する。
