「コンピューターって、そもそも何ができて、何が苦手なのか？」——これを理論的に探るのが計算機科学です。この講義では「どう解くか（アルゴリズム）」「どれだけ速いか（計算量）」「そもそも解けるか（計算可能性）」「情報をどう測るか（情報理論）」「どう守るか（暗号理論）」という5つの問いを順に追い、現代のコンピューティングの理論的土台を一緒に確かめます。
ねらい — 同じ問題でも解き方によって速さが全然違う——その「違い」を数学的に測る方法を学ぼう。
アルゴリズムとは「問題を解くための、有限ステップで記述された明確な手順」のことです。例えばコンビニで買い物をするとき「財布を出す→商品を選ぶ→レジに並ぶ→支払う」という手順がアルゴリズムです。同じ問題（例えば1000人のデータを並べ替える）でも、解き方によって必要な計算時間が数秒から数時間まで大きく変わるため、効率の評価が重要です。
計算量（けいさんりょう）はデータの数 n に対して「どれだけのステップが必要か」を大まかに表します。例えば O(n) は「n に比例した時間」、O(log n) は「n が2倍になっても少ししか増えない（めちゃ速）」、O(2ⁿ) は「n が増えると爆発的に遅くなる」ことを意味します。この「ビッグオー記法」で、異なるアルゴリズムの速さを比較できます。
ねらい — どんなに速いコンピューターを使っても、原理的に解けない問題があります——その不思議な事実を理解しよう。
チューリング機械（チューリングきかい）とは「計算とは何か」を厳密に定義するための数学モデルです。1936年にアラン・チューリングが考案した「無限のテープとヘッドを持つ仮想の機械」で、現代のコンピューターが計算できることはすべてこの機械で表せます（これをチャーチ＝チューリングのテーゼと呼びます）。
「停止性問題（ていしせいもんだい）」とは「任意のプログラムと入力を与えたとき、そのプログラムがいつか止まるかどうかを判定するプログラムを作れるか？」という問いです。答えは「No——どんなコンピューターでも原理的に作れない」です。これは計算の根本的な限界を示す驚くべき結果で、背理法という論理的手法で証明できます。
ねらい — 「すぐ解ける問題」と「解は確認しやすいのになぜか解くのが難しい問題」——この謎の壁が現代暗号の根拠になっています。
クラス P とは「多項式時間（例えば O(n²) など）で解けるアルゴリズムが存在する」判定問題の集合です。一方 NP とは「正解が提示されたとき、それが正解かどうかを多項式時間で確認できる」問題の集合です。例えばジグソーパズルは「完成形を見ればすぐ正解とわかる（NP）」が、「正解を一から探す（解く）のは大変」です。SAT・巡回セールスマン問題・グラフ彩色などが NP に属する有名問題です。
「P = NP か？」——つまり「確認が速い問題はすべて解くのも速いか？」は、21世紀最大の未解決問題の一つで、100万ドルの懸賞金がかかっています。多くの研究者は P ≠ NP（解くのは本質的に難しい）と信じていますが、いまだ証明されていません。NP 完全問題（NP 完全もんだい）とは「NP の問題をすべて多項式時間で帰着できる最も難しい問題群」で、一つでも P で解けたら P = NP が証明されます。
P=NP? は懸賞金100万ドルのミレニアム問題——半世紀以上、世界中の天才が挑戦して今も未解決。
ねらい — 「情報量」を数学で測れるとしたら？1948年にシャノンが与えた答えが、現代の通信・圧縮・AIの基礎になっています。
1948年、クロード・シャノンは「情報量（じょうほうりょう）」を H(X)=−Σ p(x) log p(x) という「エントロピー」で定義しました。エントロピーが大きいほど「不確実性が高い（予測しにくい）」ことを意味します。例えばコインの表・裏のエントロピーは最大で、「必ず表が出るコイン」のエントロピーは0です。これはデータ圧縮の理論的な下限（これ以上小さくできない限界）を与えます。
シャノンは「ノイズ（雑音）のある通信路でも、十分な誤り訂正符号（あやまりていせいふごう）を使えば、一定の速度で正確に情報を送れる」ことも証明しました（通信路容量定理）。これは「Wi-Fi や携帯電話がノイズに強い」理由の理論的根拠です。情報理論は今や通信・ストレージ・機械学習の理論的基盤になっています。
ねらい — ネットバンキングや LINE のメッセージを「盗み見できない」ようにしているのは何か？その数学を一緒に確かめましょう。
昔の暗号（例えばシーザー暗号）は「文字を一定数ずらす」だけで、規則がわかれば簡単に解読できました。現代暗号は「難しい計算問題を解くのが困難」という数学的な根拠に頼っています。例えば RSA 暗号は「大きな数（例えば600桁）を素因数分解するのが非常に難しい」という事実を使います。暗号化は簡単でも、鍵なしに解読するには天文学的な時間がかかります。
公開鍵暗号（こうかいかぎあんごう）は「鍵を2つ用意し、暗号化に使う鍵は公開、復号に使う鍵は秘密にしておく」仕組みです。ハッシュ関数（はっしゅかんすう）は「どんな長さのデータも一定長の『指紋』に変換し、元データの改ざんを検出する」道具です。デジタル署名・ゼロ知識証明（知っていることを証明するが内容は明かさない）などと組み合わせて、ネットバンキングからブロックチェーンまで支えています。量子コンピューター（りょうしコンピューター）が実用化されると従来の暗号が破られる恐れがあるため、耐量子暗号（たいりょうしあんごう：量子計算でも破られない暗号）の研究が急速に進んでいます。