独習コンピュータ科学基礎I 離散構造（神林 靖 神林 靖 ジェームズ・ハイン）｜翔泳社の本
  1. ホーム >
  2. 書籍 >
  3. 独習コンピュータ科学基礎I 離散構造

独習コンピュータ科学基礎I 離散構造

翻訳
原著
著

形式：
書籍
発売日：
ISBN：
9784798120638
定価：
3,520円（本体3,200円＋税10%）
仕様：
B5変・360ページ
カテゴリ：
プログラミング・開発
キーワード：
#プログラミング,#開発環境,#開発手法,#Web・アプリ開発
シリーズ：
独習

購入はこちら

情報科学の隠れた名著が翻訳刊行に

原著は米国ポートランド大学を中心に幅広く教科書として採用され、3rd Editionを重ねるまでになっています。本書は全3分冊でコンピュータ数学の基礎分野を網羅する新しい独習シリーズの第1冊目となり、その最も基本となる離散構造（整数論など）に関する「基本的な概念と記法、関数、構成技法、同値/順序/帰納的証明、解析技法」などに関して、精密な解説と豊富な例題で学べるようになっています。Binary Hacsk / Write Great Code / The Art of Computer Programming など名著と呼ばれるコンピュータ書の読者層に特にお薦めなシリーズです。

第1章　基本概念と表記法

1.1　証明入門
　　　1.1.1　文と真理値表
　　　1.1.2　数についてひと言
　　　1.1.3　証明技法
1.2　集合
　　　1.2.1　集合の定義
　　　1.2.2　集合上の演算
　　　1.2.3　有限集合を数える
　　　1.2.4　多重集合
　　　1.2.5　集合は複雑過ぎてはいけない
1.3　順序構造
　　　1.3.1　組
　　　1.3.2　リスト
　　　1.3.3　文字列と言語
　　　1.3.4　関係
　　　1.3.5　組を数える
1.4　グラフと木
　　　1.4.1　グラフの定義
　　　1.4.2　グラフ中の経路
　　　1.4.3　グラフの走査
　　　1.4.4　木
　　　1.4.5　全域木
1.5　章のまとめ

第2章　関数について

2.1　定義と例
　　　2.1.1　関数の定義
　　　2.1.2　床関数と天井関数
　　　2.1.3　最大公約数
　　　2.1.4　剰余関数
　　　2.1.5　対数関数
2.2　関数を構成する
　　　2.2.1　関数の合成
　　　2.2.2　map関数
2.3　関数の性質
　　　2.3.1　単射と全射
　　　2.3.2　全単射と逆関数
　　　2.3.3　鳩の巣原理
　　　2.3.4　単純な暗号
　　　2.3.5　ハッシュ関数
2.4　可算可能性
　　　2.4.1　集合の大きさを比較する
　　　2.4.2　可算な集合
　　　2.4.3　対角線論法
　　　2.4.4　計算可能性の限界
2.5　章のまとめ

第3章　構成技法

3.1　帰納的に定義される集合
　　　3.1.1　数
　　　3.1.2　文字列
　　　3.1.3　リスト
　　　3.1.4　二分木
　　　3.1.5　集合のデカルト積
3.2　再帰関数と手続き
　　　3.2.1　数
　　　3.2.2　文字列
　　　3.2.3　リスト
　　　3.2.4　二分木
　　　3.2.5　更に2つの問題
　　　3.2.6　無限列
3.3　文法
　　　3.3.1　英文法の復習
　　　3.3.2　文法の構造
　　　3.3.3　導出
　　　3.3.4　文法を構成する
　　　3.3.5　意味と曖昧さ
3.4　章のまとめ

第4章　同値、順序、帰納的証明

4.1　二項関係の性質
　　　4.1.1　関係の合成
　　　4.1.2　閉包
　　　4.1.3　経路問題
4.2　同値関係
　　　4.2.1　定義と例題
　　　4.2.2　同値類
　　　4.2.3　直和分割
　　　4.2.4　同値関係を生成する
4.3　順序関係
　　　4.3.1　半順序
　　　4.3.2　トポロジカル整列
　　　4.3.3　整礎順序
　　　4.3.4　順序数
4.4　帰納的証明
　　　4.4.1　数学的帰納法による証明
　　　4.4.2　整礎帰納法による証明
　　　4.4.3　様々な例
4.5　章のまとめ

第5章　解析技法

5.1　アルゴリズムを解析する
　　　5.1.1　最悪実行時間
　　　5.1.2　決定木
5.2　和と閉形式
　　　5.2.1　基本和と閉形式
　　　5.2.2　和を近似する
　　　5.2.3　定積分を用いた近似
　　　5.2.4　調和数
　　　5.2.5　多項式と部分関数
5.3　順列と組合せ
　　　5.3.1　順列（順序が重要）
　　　5.3.2　組合せ（順序は重要でない）
5.4　離散型確率
　　　5.4.1　確率の用語
　　　5.4.2　条件付き確率
　　　5.4.3　独立事象
　　　5.4.4　期待値と平均的な振舞い
　　　5.4.5　有限マルコフ連鎖
　　　5.4.6　近似（モンテカルロ法）
5.5　漸化式を解く
　　　5.5.1　単純な漸化式を解く
　　　5.5.2　分割統治漸化式
　　　5.5.3　生成関数
5.6　成長率を比較する
　　　5.6.1　ビッグ・オー
　　　5.6.2　ビッグ・オメガ
　　　5.6.3　ビッグ・シータ
　　　5.6.4　リトル・オー
　　　5.6.5　記号を使用する
5.7　章のまとめ
　　　注釈

付録
　ギリシャ文字
　記号
　参考文献


索引

付属データはこちら

お問い合わせ

内容についてのお問い合わせは、正誤表、追加情報をご確認後に、お送りいただくようお願いいたします。

正誤表、追加情報に掲載されていない書籍内容へのお問い合わせや
その他書籍に関するお問い合わせは、書籍のお問い合わせフォームからお送りください。

利用許諾に関するお問い合わせ

本書の書影（表紙画像）をご利用になりたい場合は書影許諾申請フォームから申請をお願いいたします。
書影（表紙画像）以外のご利用については、こちらからお問い合わせください。

  • 読みやすさを考慮して原著にない表現の追記

    下から9行目と4行目

    要素x∈Pが下界で、
    ↓
    要素x∈がSの下界で、
この商品の「よくある質問」はありません。

ご購入いただいた書籍の種類を選択してください。

書籍の刷数を選択してください。

刷数は奥付（書籍の最終ページ）に記載されています。

現在表示されている正誤表の対象書籍

書籍の種類:

書籍の刷数:

本書に誤りまたは不十分な記述がありました。下記のとおり訂正し、お詫び申し上げます。

対象の書籍は正誤表がありません。

最終更新日:2016年01月18日
発生刷 ページ数 書籍改訂刷 電子書籍訂正 内容 登録日
1刷 017
下から4行目		 2刷 未
誤 B⊆
正 B⊆A
2014.02.03
1刷 019
積集合の性質(1.6) 		2刷 未
誤 b. ∪には交換律が成り立つ c. ∪には結合律が成り立つ e. A ∪ B = B
正 b. ∩には交換則が成り立つ c. ∩には結合則が成り立つ e. A ∩ B = A
2014.02.03
1刷 024
4行目		 2刷 未
誤 道具の集合
正 道具の集合の部分集合
2014.02.03
1刷 039
7行目		 2刷 未
誤 <a, a, c, a, b, b
正 <:a, a, c, a, b, b>
2014.02.03
1刷 069
「部分関数」7～13行目（4箇所）		 2刷 未
誤 全関数
正 全域関数
2014.02.03
1刷 071
下から6行目		 2刷 未
誤 しかしp⌊x⁄p⌋⌊x⌋は整数である。
正 しかしp⌊x⁄p⌋は整数である。
2014.02.03
1刷 072
下から6行目		 2刷 未
誤 演習問題2.7
正 例題2－⑦
2014.02.03
1刷 073
下から4行目挿入		 2刷 未
誤
正 b > 0 の間 ;
2014.02.03
1刷 087
4行目		 2刷 未
誤 ≤log_2(n)<3
正 2≤log_2(n)<3
2014.02.03
1刷 092
下から1行目		 2刷 未
誤 ℕ→ℕ
正 ℕ→ℕ×ℕ
備
考		 N→N
と
N→N×N
です
2014.02.03
1刷 095
4行目冒頭		 2刷 未
誤 ＝0となる。数x,c　
正 ＝0となる数x,c　
備
考		 。は削除
2016.01.18
1刷 111
7行目		 2刷 未
誤 Rには、可算な数の…ことになる。
正 R中の可算な数だけが計算可能なのである。
2014.02.03
1刷 123
例題3-⑨中ほど（8行目の式）		 2刷 未
誤 L ∈ Sであれば、cons(a, cons(b, tail(L)) ∈ S
正 L ∈ Sであれば、cons(a, cons(b, tail(L))) ∈ S
備
考		 式末尾付近に閉じ括弧1つ不足
2016.01.18
1刷 128
下から4行目（6．の選択肢d.）		 2刷 未
誤 { ambn | m, n ∈ N}
正 { ambn | m, n ∈ ℕ}
2016.01.18
1刷 150
下から1行目		 2刷 未
誤 自然数
正 整数
2014.02.03
1刷 189
4段落1行目		 2刷 未
誤 (x x)
正 (x, x)
2014.02.03
1刷 210
図4.14		 2刷 未
誤 右端の図　Power({a,b})の上
正 空集合記号が欠落していました
備
考		 修正図
2015.10.20
1刷 223
2行目		 2刷 未
誤 glbとlub
正 下限と上限
2014.02.03
1刷 250
下から8行目		 2刷 未
誤 下限
正 下界
2014.02.03
1刷 250
下から6行目		 2刷 未
誤 非零
正 零でない
2014.02.04
1刷 252
4行目（g.の右辺）		 2刷 未
誤 　
n+1
Σ
k＝m+１		 ak
正
n+i
Σ
k＝m+１		 ak
2014.02.03
1刷 256
5行目（d.の右辺）		 2刷 未
誤
 a - (n+1)an+1 + naa+2 
 (a-1)2 
正
 a - (n+1)an+1 + nan+2 
 (a-1)2 
2014.02.03
1刷 264
2番目の式の右端		 2刷 未
誤 = n(n + 1)Hn − 2n
正 =n(n+1)(Hn-1)
2014.02.03
1刷 264
下から10行目（小見出し）		 2刷 未
誤 5.2.5 多項式と部分関数
正 5.2.5 多項式と部分分数
2014.02.03
1刷 266
4行目右端		 2刷 未
誤
+    Dx + C  
 (x2 + 1)2 
正
+    Dx + E  
 (x2 + 1)2 
2014.02.03
1刷 269
15.の式2行目		 2刷 未
誤 while i¡ ¡n+1 do
正 while i ≤ ¡n+1 do
備
考		 原著誤りの見落としでした
2015.10.20
1刷 303
7行目		 2刷 未
誤 =2n-1r1+2n-2 (2)+2n-2 (2)
正 =2n-1r1+2n-2 (2)+2n-3 (3)
2014.02.03
1刷 304
下から12～11行目		 2刷 未
誤 係数のリストである。 poly(C, x) = if C = < > then 0 else head(C)+...
正 空でないリストである。 poly(C, x) = if length(C) = 1 then head(C) else head(C)+...
2014.02.03
1刷 304
下から2行目		 2刷 未
誤 長さnである。n = 0であれば、C = < > なので、次のとおり。
正 長さn+1である。n = 0であれば、length(C) = 1なので、次を得る。
2014.02.03
1刷 305
1～2行目		 2刷 未
誤 = poly(< >, x) = 0 …である。n>0であれば…
正 =head(C) …であり、算術演算は実行されない。n>0であれば、length(C)>1なので、次を得る。
2014.02.03
1刷 305
4行目右端		 2刷 未
誤 n - 1
正 n
2014.02.03
1刷 305
下から10行目		 2刷 未
誤 494個
正 495個
2014.02.03
1刷 315
12行目と15行目		 2刷 未
誤 …bkbn－k +…
正 …bkbn－k-1 +…
2014.02.03
1刷 319
下から4行目（a.）		 2刷 未
誤 O(f(n))
正 f(n) = O(f(n))
2014.02.03
1刷 326
ページ末尾の式		 2刷 未
誤
正 改行位置が誤っていました
備
考		 正しい改行位置
2015.10.20
1刷 330
1.の2行目		 2刷 未
誤 o(nε)nである。
正 o(nε)である。
2015.10.20