microbeの活動日記

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

計算理論

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

目的 一度読んではいるけど曖昧な理解なまま終わってしまったのでもう一回読んで知識のアウトプット 参考書はこの3つです. 計算理論の基礎 [原著第2版] 1.オートマトンと言語 作者: Michael Sipser,太田和夫,田中圭介,阿部正幸,植田広樹,藤岡淳,渡辺治 出版…

胎児から始める計算複雑性理論 P≠NP予想編

はじめに 絢辻詞に踏まれたい わかりやすくするために厳密なところは欠いています.突っ込まないで P≠NP予想とは P≠NP予想の説明をWikipediaから抜粋すると P≠NP予想(P≠NPよそう、英: P is not NP)は、計算複雑性理論(計算量理論)におけるクラスPとクラ…