microbeの活動日記

プログラミングコンテストとか勉強とかいろいろ

計算理論の基礎 1.オートマトンと言語 序論

目的

一度読んではいるけど曖昧な理解なまま終わってしまったのでもう一回読んで知識のアウトプット

参考書はこの3つです.

計算理論の基礎 [原著第2版] 1.オートマトンと言語

計算理論の基礎 [原著第2版] 1.オートマトンと言語

 
計算理論の基礎 [原著第2版] 2.計算可能性の理論

計算理論の基礎 [原著第2版] 2.計算可能性の理論

 
計算理論の基礎 [原著第2版] 3.複雑さの理論

計算理論の基礎 [原著第2版] 3.複雑さの理論

 

 

内容 

序論ということで内容はこの本で学んでいくうえで必要なグラフや集合など数学的概念,背理法などの証明のタイプの説明.この本で必要なグラフや集合などの知識は一般的なことなので省略

定理の主張しているものの構成法を見せる論法を構成的証明,定理が偽であると仮定し,その仮定から矛盾を道ぶく手法を背理法,無限集合のすべての要素がある特定の性質をもつことを示す際に用いられる論法が帰納法帰納法は,証明したい性質がx(1)としたときx(1),x(2),...が真であることを証明する基底,各i\geqに対してx(i)が真であると仮定してx(i + 1)が真であることを示す帰納法のステップの二つからなる.

 

感想

基本的なことなのでまあはい.