書記の読書記録#69「コンピュータの数学」

GRAHAM/KNUTH/PATASHNIK著「コンピュータの数学」のレビューと読書記録

コンピュータの数学 第2版

レビュー

扱っている話題：漸化式，Σ計算，ガウス記号をはじめとした整数関数，mod，素数，二項係数，特別な数，母関数，離散的確率，漸近近似

コンピュータ分野によく出る離散数学についての分厚い教科書。表紙にあるΣは，その肝となる概念で，事前に高校数学レベルの知識は欲しい。

完璧に読むのは難しいので，必要なトピックをつまみながらゆっくり埋めていく感じで読む予定である。

読書記録

＃ 1p1〜151
・漸化式：ハノイの塔，平面の直線分割，ヨセフスの問題・レパートリー法・Σ記法・調和数・和の操作・摂動法・多重和・微分と差分，積分と和分・望遠鏡和・クイックソートの漸化式・無限和の収束性・切下げ関数と切上げ関数・スペクトル・mod・最大公約数・素数：メルセンヌ数，素数定理・階乗の因数・互いに素・スターンブロコット木：ファレイ数列・中国剰余定理・剰余数体系・鳩の巣原理・オイラーの位数関数，反転定理

＃ 2p152〜305
・二項係数・パスカルの三角形・加法公式・上インデックスに関する和・二項定理・上位負変換・多項係数・ヴァンデルモンドのたたみ込み・重複公式・ニュートン級数・反転公式・母関数・一般化二項級数，一般化指数級数・カタラン数・超幾何級数，修正ベッセル関数，合流型超幾何級数・ガンマ関数・クンマーの公式，ディクソンの公式，ザールシュッツの公式・反射則・ガウスの等式・ゴスパーツァイルバーガーのアルゴリズム・スターリング数・オイラー数：ウォーピツキーの公式，スターリング多項式・調和数：オイラーの定数・ベルヌーイ数・フィボナッチ数：ツェッケンドルフの定理，フィボナッチ数体系，黄金比・連分多項式

＃ 3p306〜476
・ドミノ理論，釣銭・母関数の基本操作，漸化式の解法・系列のたたみ込み・mラニー系列・指数母関数・ベルヌーイ多項式・ディリクレ母関数：乗法的関数，ゼータ関数・確率空間の定義・平均と分散・チェビシェフの不等式・確率母関数，キュムラント・負の二項分布・ハッシュ法・対数指数関数クラス・O記法：絶対誤差，相対誤差・ブートストラッピング・ベルカーブの関数

本記事のもくじはこちら：

書記の読書記録まとめ｜Writer_Rinka｜note