Skip to content

Berkeley CS70

Basic Information

来源:UC Berkeley

课程名称:CS70, Discrete Mathematics and Probability Theory (Spring 2024)

主题:离散数学与概率论

主要内容:26 个 Lecture, 26 个 Discussion, 13 个 Homework

课程网站:https://www.eecs70.org

个人实现:24Sp-CS70-Berkeley

起止时间:2024.07 - 2024.08

Content

Lectures

课程的主要内容是离散数学与概率论初步,主要内容有

  • 命题逻辑, 逻辑量词, 推理

  • Stable Matching, Gale-Shapley 算法

  • 图论初步:平面图, 树, 欧拉回路

  • 数论初步:同余, 扩展 Euclid 算法, 中国剩余定理, RSA 加密算法

  • 多项式初步:Lagrange 插值, 多项式的整除, 有限域, Reed-Solomon 纠错码

  • 计数问题, 组合恒等式, 容斥原理

  • 势, 可数与不可数

  • 自指, Quine, 停机问题, 对角论证法, Gödel 不完备定理, 可计算性和复杂性

  • 概率论(使用 UCB CS126 替代)

Content

Homework 6

Determine the countability of the following collections:

a. The functions from \(\mathbb{N}\to \mathbb{N}\).

Proof

Uncountably infinite. We use Cantor's Diagonalization Proof:

Let \(\mathscr{F}=\{f\mid f:\mathbb{N}\to \mathbb{N}\}\). If we can construct a bijection from \(\mathbb{N}\) to \(\mathscr{F}\), then consider

\[ \begin{array}{c} 0\longleftrightarrow (f_0(0), f_0(1), f_0(2), f_0(3), \cdots)\\ 1\longleftrightarrow (f_1(0), f_1(1), f_1(2), f_1(3), \cdots)\\ 2\longleftrightarrow (f_2(0), f_2(1), f_2(2), f_2(3), \cdots)\\ 3\longleftrightarrow (f_3(0), f_3(1), f_3(2), f_3(3), \cdots)\\ \vdots \end{array} \]

Consider the function \(g:\mathbb{N}\to \mathbb{N}\) where \(g(i)=f_i(i) +1\) for all \(i\in \mathbb{N}\). We claim that \(g\) is not in our list of functions, because \(f_n(\cdot)\) and \(g(\cdot)\) differ in the \(n\)-th argument, so the original set is uncountably infinite.

b. The set of finite-length strings drawn from a countably infinite alphabet, \(\mathscr{A}\).

Proof

The idea is to restrict both the length of the string and the characters we are allowed to use:

a. List all strings containing only characters in \(\{a_1\}\) with length at most \(1\).

b. List all strings containing only characters in \(\{a_1,a_2\}\) with length at most \(2\) and have not been listed before.

c. Proceed onwards.

We can prove that our enumeration is complete, and each string appears exactly once in the listing.

c. The set of infinite-length strings over the English alphabet.

Proof

Consider a subset, which is the set of infinite-length strings containing only as and bs. We construct a bijection from this subset to \(\mathbb{R}[0,1]\) by replacing as with 0s and bs with 1s, which produces a unique binary number, e.g.

\[ ababbaaa \leftrightarrow (0.01011000)_2 \]

So the set is uncountably infinite.