目次
- 1.コンピューター科学への導入この授業で学ぶこと・前提知識
- 2.コンピューター発展史とデータの単位階差機関からマイクロプロセッサまで・ビットとバイト
- 3.コンピューター内部の数の表現2進法・2の補数・浮動小数点と数値誤差
- 4.コンピューター内部の文字の表現文字コード・Unicode・絵文字
- 5.フォントとタイポグラフィ補足＋スライド書体の仕組みと文書作成
- 6.論理回路とブール代数真理値表・論理ゲート・標準形
- 7.論理回路の簡単化と回路設計カルノー図・加算器・関数的完全性
- 8.順序回路とフリップフロップ記憶する回路・レジスタ・カウンタ
- 9.情報理論の初歩符号化と圧縮の限界・誤り訂正とシャノンの定理
- 10.アルゴリズムと計算量整列アルゴリズム・O記法・計算量の下界
- 11.コンピューターでは解けない問題停止性問題と対角線論法
- 12.計算困難性とP≠NP予想PとNP・NP完全・co-NP・現代暗号との関係
- 13.NP完全性と多項式時間還元還元の連鎖でNP完全性を証明する
- 付2進法の表記と変換補足資料: 基数変換の計算法
この資料について
本資料は、新型コロナウイルス感染症の流行期(2020年〜)に大学のオンライン授業用として作成した講義資料を元に、生成AIを用いて全体の整理・内容点検を行い、Web公開用に再編集したものです。
誤りの指摘や改善の提案を歓迎します。上記の各章は、読み物としても独立して読めるように構成していますが、章の順に読み進めることを想定しています。各章末には練習問題とその解答があります。
数式の表示にはMathJaxを使用しています。表示が崩れる場合はブラウザのJavaScriptを有効にしてください。
ライセンス
本教材はクリエイティブ・コモンズ 表示 - 非営利 - 継承 4.0 国際ライセンス(CC BY-NC-SA 4.0)のもとで公開しています。
出典を明示すれば、非営利目的での利用・改変・再配布ができます。改変した資料は同じライセンスで公開してください。