COMP6991 Exercise 1

使用SSH远程连接学校服务器以避免环境问题、作业提交失败等情况。



# 官方文档

[Logging In With SSH - CSE taggi](https://taggi.cse.unsw.edu.au/FAQ/Logging_In_With_SSH/)

[Connecting with SSH — CSE Home Computing](https://www.cse.unsw.edu.au/~learn/homecomputing/ssh/)

同时，也可以使用VLAB进行操作：

[Vlab - CSE taggi](https://taggi.cse.unsw.edu.au/Vlab/)

# 操作步骤

1. 启动相应SSH客户端。不推荐使用Windows的cmd。
2. 连接域名：
    ```
    login.cse.unsw.edu.au
    ```
3. 使用你的zID和zPass登录。

# 终端与免密登录

注意：该部分内容基于macOS/Unix类系统，Windows的文件位置可能会有些许差别。

使用本地终端输入以下指令：

```
vim ~/.ssh/config
```

在文件中输入以下内容并保存：

```
Host CSE
	HostName login.cse.unsw.edu.au
	User z123456
	Port 22
```

其中，“CSE”可以更改为任意你喜欢的别名，User需要修改为自己的zID。

保存完毕后，输入以下指令生成ssh密钥：

```
ssh-keygen -t rsa -b 4096 -C "your_email@example.com"
```

邮箱可以选择任何你喜欢的邮箱，并连按三下回车以选择默认配置结束生成。

之后，终端输入以下命令将密钥发送至CSE服务器：

```
ssh-copy-id z123456@login.cse.unsw.edu.au
```

记得替换自己的zID，输入zPass后复制完成。

至此，可以使用终端输入以下指令免密快速登录CSE：

```
ssh CSE
```

注意：该名称为第一步中在config文件内写下的Host后面的字符串自定义名称。

Enjoy UNSW Life.

UNSW CSE服务器登陆指南

COMP9020 Quiz 1，Test started Feb 14, 2024 6:00 PM to Feb 21, 2024 6:00 PM.



# Part 1

## 1.1
Question:
> How many integers between -101 and 1001 (inclusive) are divisible by 3?

Answer:

> 367

本题用 [此部分 - 简单理论3](https://rin977.com/post/COMP9020-1-2#%E5%AE%9E%E6%95%B0%E4%B8%8E%E6%95%B4%E6%95%B0%E4%B9%8B%E9%97%B4%E7%9A%84%E8%BD%AC%E6%8D%A2) 中提到的公式进行计算即可。

$$
⌊\frac{1001}{3}⌋ - ⌊\frac{-101-1}{3}⌋=333-(-34)=367
$$

## 1.2

### Question

> Which of the following will give:
> 
> - x+1 if x is an integer, and
> - The smallest integer greater than x if x is not an integer.
> 
> Select all that apply:
> 
> $2-⌊1-x⌋$
> 
> $⌈x+1⌉$
> 
> $⌊x⌋+1$
> 
> $2-⌈1-x⌉$
> 
> $⌊x+1⌋$
>  
> $⌈x⌉+1$

### Answer
> $⌊x⌋+1$
> 
> $2-⌈1-x⌉$
> 
> $⌊x+1⌋$

本题用 [此部分 - 简单理论1&2](https://rin977.com/post/COMP9020-1-2#%E5%AE%9E%E6%95%B0%E4%B8%8E%E6%95%B4%E6%95%B0%E4%B9%8B%E9%97%B4%E7%9A%84%E8%BD%AC%E6%8D%A2) 中提到的公式进行计算即可。

选项1：

$$
2-⌊1-x⌋ = 2+⌈x-1⌉=⌈x+1⌉
$$

- 不符合条件2，排除。

选项2：

- 同选项1，排除。

选项3：

- 正确。

选项4：

$$
2-⌈1-x⌉=2+⌊x-1⌋=⌊x+1⌋
$$

- 正确。

选项5：

- 同选项4，正确。

选项6：

- 不符合条件2，排除。


## 1.3

### Question

> Which of the following is true for all real numbers x?
> 
> Select all that apply:
> 
> $⌈x⌉=⌈⌈x⌉⌉$
> 
> $⌊x⌋<⌈x⌉$
> 
> $⌈⌊x⌋⌉\le⌊⌈x⌉⌋$
> 
> $⌊⌈x⌉⌋\le⌈⌊x⌋⌉$

### Answer

> $⌈x⌉=⌈⌈x⌉⌉$
> 
> $⌈⌊x⌋⌉\le⌊⌈x⌉⌋$

本题用常理推断即可。

选项1：

由于 $⌈x⌉$ 为整数，因此第二层向上取整无效。$⌈⌈x⌉⌉=⌈x⌉$。

- 正确。

选项2：

$$
\because ⌊x⌋ \le x, \ x \le ⌈x⌉ \\
\therefore ⌊x⌋ \le  x \le ⌈x⌉ \\
\therefore ⌊x⌋ \le ⌈x⌉ \\
$$

- 当 $x$ 为整数时，应当存在等号，因此该选项错误。

选项3：

由于 $⌈x⌉$ ， $⌊x⌋$ 均为整数，因此第二层向上取整和向下取整均无效。

$$
⌈⌊x⌋⌉=⌊x⌋ \\
⌊⌈x⌉⌋=⌈x⌉
$$

因此，原不等式变为：

$$
⌊x⌋ \le ⌈x⌉
$$

- 参考选项2，正确。

选项4：

参考选项3，其可变形为：

$$
⌈x⌉ \le ⌊x⌋
$$

- 参考选项2，错误。

## 1.4

### Question

Which of the following propositions are true?

Select all that apply:


- For every integer x, there exists an integer y such that x|y.
- For every integer x, there exists an integer y such that y|x.
- There exists an integer y, such that for every integer x, x|y.
- There exists an integer y, such that for every integer x, y|x.
- None of the above

### Answer

- For every integer x, there exists an integer y such that y|x.
- There exists an integer y, such that for every integer x, x|y.

本题主要考察 [可约分性的定义](https://rin977.com/post/COMP9020-1-2#%E5%8F%AF%E7%BA%A6%E5%88%86%E6%80%A7) 。

选项1：

- 当 $x=0$ 时，$x|y$ 无意义，错误。

选项2：

- 无论 $x$ 的值为多少，都可以使 $y = 1$ ，则： $y|x$ 成立。正确。
- $ 1 $可以整除任何数，包括0。
- 当 $x = 0$ 时，仍然成立。即： $1|0$ 仍是正确的。

选项3：

- 没有一个整数 $y$ 能做到可以被所有的数字整除。即：$x|y$ 不可能对任意 $x$ 成立。错误。

选项4：

- 使 $y = 1$ ，则对于任意的 $x$ 均有 $y|x$ 成立。正确。
- $ 1 $可以整除任何数，包括0。


:::warning{title="注意"}
本题需要非常严谨地思考量词与逻辑顺序，这在第一节课是着重强调过的。

- 选项1、选项2，意为：对于任意的值 $x$，总存在一个与其对应的 $y$，并使得后面的式子成立。
- 选项3、选项4，意为：存在一个值 $y$，对于所有的 $x$ 的取值，均能让后面的式子成立。

前两个选项中，对于不同的 $x$ 值， $y$ 的值是可以变化的。而在后两个选项中， $y$ 的值是恒定不变的。
:::


## 1.5

### Question

What is gcd(286,396)?

### Answer

22

使用欧里几德算法即可快速算出。略过不表。


## 2.1

### Question

True or False:

For all positive integers $m,n$ and all integers $a,b$ , 

if $a=_{(m)}b$ and $a=_{(n)}b$ ,
then $a=_{(mn)}b$

### Answer

False

因为 $m,n$不一定是互质的。以下是一个简单的反例：

$$
a=14, b=2 \\
m=6, n=4 \\
$$

根据计算可得：

$$
14=_{(4)}2 \\
14=_{(6)}2 \\
14\ne_{(24)}2
$$

## 2.2

### Question

Which of the following will give:

- $1$ if $x>0$
- $0$ if $x<0$

Select all that apply:

- $x / (2|x|) + 1/2$
- $|x+1| / (2x)$
- $x - |x|$
- $(x + |x|) / (2x)$
- $x / ⌈x⌉$

### Answer

- $x / (2|x|) + 1/2$
- $(x + |x|) / (2x)$

大部分选项错在他们根本没法稳定地仅得到 $1$ 或 $0$ 这两种结果。

选项1：

当 $x>0$ 时，

$$
\frac{x}{2|x|}+\frac{1}{2}=\frac{1}{2}+\frac{1}{2}=1
$$

当 $x<0$ 时，

$$
\frac{x}{2|x|}+\frac{1}{2}=-\frac{1}{2}+\frac{1}{2}=0
$$

- 正确。

选项2：

反例：当 $x = 2$时，

$$
\frac{|x+1|}{2x}=\frac{3}{4}\ne1
$$

- 错误。

选项3：

当 $x<0$ 时，

$$
x - |x| = x - (-x) = 2x\ne0
$$

- 错误。

选项4：

当 $x>0$ 时，

$$
\frac{x+|x|}{2x}=\frac{x+x}{2x}=1
$$

当 $x<0$ 时，

$$
\frac{x+|x|}{2x}=\frac{x-x}{2x}=0
$$

- 正确。

选项5：

反例：当 $x=1.5$ 时，

$$
\frac{x}{⌈x⌉} = \frac{1.5}{⌈1.5⌉} = \frac{1.5}{2} = 0.75\ne1
$$

- 错误。



## 2.3

### Question

Suppose $x,y$ and $z$ are arbitrary integers such that $x|y$ and $y|z$.

Which of the following are always true (i.e. true for any such $x, y, z$)?

Select all that apply:

- $xy|yz$
- $xy|z$
- $x+y|z$
- $x|yz$
- $x+y|y+z$
- $x|y+z$

### Answer

- $xy|yz$
- $x|yz$
- $x|y+z$

依然是关于整除的问题。

已知：

$$
x|y，y = a * x\\
y|z，z = b * x
$$

因此：

$$
x|z，z = (a+b) * x
$$

选项1：

因为 $x|z$，即$ z = k * x$，因此可得：

$$
yz = k * xy
$$

即：$xy|yz$。

- 正确。

选项2：

- 由选项1可知 $xy|yz$。当且仅当 $y=1$ 时，$xy|z$ 。
- 错误。

选项3：

- 显然错误。

选项4：

已知：

$$
x|y，y = a * x\\
y|z，z = b * x
$$

故：

$$
yz = abx * x \\
x | yz
$$

- 正确。

选项5：

已知：

$$
x|y，y = a * x\\
y|z，z = b * x
$$

故：

$$
x + y = (a + 1) * x \\
y + z = (a + b) * x \\
\frac{y+z}{x+y}=\frac{a+b}{a+1}
$$

- 由于 $\frac{a+b}{a+1}$ 不一定为整数，因此不一定有 $x+y|y+z$ 。错误。

选项6：

已知：

$$
x|y，y = a * x\\
y|z，z = b * x
$$

故：

$$
y + z = (a + b) * x \\
\frac{y+z}{x}=a+b
$$

- 正确。

## 2.4

### Question

Let $m, n$ and $k$ be arbitrary integers, with $k≥1$ and $n<m$.

Which of the following counts the number of multiples of k between n (exclusive) and m (exclusive)?

Select all that apply:

- $⌊(m-1)/k⌋ - ⌊n/k⌋$
- $⌊(m-n-1)/k⌋$
- $⌊m/k⌋ - ⌈n/k⌉$
- $⌈m/k⌉ - ⌊n/k⌋$
- $⌊(m-n)/k⌋$

### Answer

- $⌊(m-1)/k⌋ - ⌊n/k⌋$

其实上课听了倍数数量的证明就知道为什么了，自己画个数轴非常快就明白了。

![Recording 19:20 Week 1, Fri 16, Feb](/static/img/ce05d16c53713fde444e702f5d4b833e.image.webp)


## 2.5

### Question

Which of the following hold for all real numbers x and y?

Select all that apply:

- $⌊xy⌋ ≥ ⌊x⌋·⌊y⌋$
- $|xy| ≥ |x|·|y|$
- $⌊x+y⌋ ≥ ⌊x⌋ + ⌊y⌋$
- $|x+y| ≥ |x| + |y|$
- $⌈xy⌉ ≥ ⌈x⌉·⌈y⌉$
- $⌈x+y⌉ ≥ ⌈x⌉ + ⌈y⌉$

### Answer

- $|xy| ≥ |x|·|y|$
- $⌊x+y⌋ ≥ ⌊x⌋ + ⌊y⌋$

选项1：

- 在负数上不成立，错误。


选项2：

其实应该是等号。

- 正确。

选项3：

假设：

$$
x = ⌊x⌋ + a, \ a\in[0,1) \\
y = ⌊y⌋ + b, \ b\in[0,1) 
$$

则有：

$$
x + y = ⌊x⌋ + ⌊y⌋ + (a + b)
$$

已知 $⌊x⌋ + ⌊y⌋$ 为整数，那么：

$$
a + b \ge 1, \ \ ⌊x+y⌋ > ⌊x⌋ + ⌊y⌋ \\
a + b \lt 1, \ \ ⌊x+y⌋ = ⌊x⌋ + ⌊y⌋
$$

综上所述，$⌊x+y⌋ ≥ ⌊x⌋ + ⌊y⌋$。

- 正确。


选项4：

当 $xy < 0$ 时，会出现 $|x+y| < |x| + |y|$。

- 错误。


选项5：

反例：

$$
x=1.1,y=1.1 \\
⌈x⌉=2,⌈y⌉=2 \\
⌈x⌉⌈y⌉=2 * 2 = 4>⌈xy⌉=⌈1.1 * 1.1⌉=⌈1.21⌉=2
$$

- 错误。

选项6：

反例：

$$
x=1.1,y=1.1 \\
⌈x⌉=2,⌈y⌉=2 \\
⌈x⌉+⌈y⌉=2 + 2 = 4>⌈x+y⌉=⌈1.1 + 1.1⌉=⌈2.2⌉=3
$$

- 错误。

COMP9020 Quiz 1

Numbers and Numerical Operations【数字与数值运算】

Divisibility【可约分性】

Greatest Common Divisor & Least Common Multiple【最大公约数与最小公倍数】

Modular Arithmetic【模运算】

Euclidean Algorithm【欧里几德算法】



# 数字与数值计算

## Notation for Numbers

- 自然数（Natural Numbers）：
    - $N = \{0,1,2,...\}$
- 整数（Integers）：
    - $Z=\{...,-1,0,1,2,...\}$
- 正整数（Positive Integers）：
    - $N_{>0}=Z_{>0}=\{1,2,...\}$
- 有理数/分数（Rational Numbers / Fractions）：
    - $Q=\{\frac{m}{n}:m,n \in Z,n \ne 0\}$
- 实数（Real Numbers）：
    - $R=a_1 a_2...a_k b_1 b_2 ...$

在$N$和$Z$中，不同的数字代表不同的数值：

$$
1 \ne 2 \ne 3
$$

在$Q$和$R$中，不同的数字可以代表相同的数值：

$$
\frac{1}{2} = \frac{2}{4} = \frac{3}{6}
$$


## 实数与整数之间的转换

使用最大整数(ceiling)与最小整数（floor）概念。

- 最大整数 $⌈x⌉$：$the\ greatest\ integer \le x$
- 最小整数 $⌊x⌋$：$the\ least\ integer \ge x$

$$
⌊\pi⌋ = 3 = ⌈e⌉
$$

以下是一些关于最大整数与最小整数的简单理论：

:::info{title="1"}

因为有 $⌊-x⌋ = -⌈x⌉$，所以有$⌊x⌋ = -⌈-x⌉$。
:::


:::info{title="2"}

对于所有的 $t \in Z$，均有：
- $⌊x + t⌋ = ⌊x⌋ + t$
- $⌈x + t⌉ = ⌈x⌉ + t$

:::

:::info{title="3"}
令 $k,m,n \in Z$，并且 $k>1, m \ge n$，则 $k$ 在区间 $[n,\ m]$ 的整数倍数的数量为：
$$
⌊\frac{m}{k}⌋ - ⌊\frac{n-1}{k}⌋
$$
:::


# 可约分性

## 定义

对于 $m,n \in Z$，如果$n = k * m, k \in Z$，我们可以称$m$可约$n$（$m$ divides $n$），记作：

$$
m|n
$$

同时也可以说：
- $n$对$m$是可约的。（$n$ is divisible by $m$）
- $m$是$n$的约数。（$m$ is a divisor of $n$）
- $n$是$m$的倍数。（$n$ is a multiple of $m$）



# 最大公约数和最小公倍数

最大公约数：Greatest common divisor，GCD


:::info{title="Definition of GCD"}
$$
gcd(m,\ n) = largest\ d \in Z_{>0}\ such \ that \\

d|m \ and\ d|n.
$$
:::

最小公倍数：Least common multiple，LCM

:::info{title="Definition of LCM"}
$$
lcm(m,\ n) = smallest\ k \in Z_{>0}\ such \ that \\

m|k \ and\ n|k.
$$
:::

最大公约数和最小公倍数是非负的，不管 $m$ $n$的正负性。

并且有事实：

$$
gcd(m,n)\ * \ lcm(m,n) = |m|\ * \ |n|
$$

由此可得，当 $m, n > 0$ 时，如果有：

$$
lcm(m,n)=m\ * \ n
$$

则有：

$$
gcd(m,n)=1
$$

即：$m,n$ 是互质数。


:::info{title="互质数（Relatively Prime）"}
如果$gcd(m,n)=1$，我们就认为 $m$ 和 $n$ 是互质数，也说他们两个是互质的。
:::

# 模运算

已知：对于任意的整数 $m$，均有：

$$
m = n * q + r，r \in [0, m)
$$

可以用模运算符 $\% $ 或 $mod$ 对 $r$ 进行表示：

$$
r = m \% n \\
r = m\ \ mod\ \   n
$$

此外，模运算还存在同余概念：

$$
m = _{(n)}p \ \ if\ \  n|(m-p)
$$

这表示，$m$ 与 $p$ 在模 $n$ 的意义下同余（即在相同的除数的情况下具有相同的余数）。

需要注意的是，$m = _{(n)}p $ 并不是一个标准的数学符号，更常见的表示方法是：

$$
m = p\ \ (mod \ n)
$$

以下是一些基本事实：


![COMP9020 - Lecture 2: Number Theory pp.55](/static/img/e8dc1ec76cc1f9c96840bc21e62803b7.image.webp)

# 欧里几德算法

最基本的欧里几德算法没有涉及到模运算，它使用了递归的思路，经过大量重复之后回归到模运算的结果。

$gcd(m,n)=$

$$
m,\ \ \ (m=n) \\
gcd(m-n,n),\ \ \ (m > n) \\
gcd(m,n-m),\ \ \ (m < n) 
$$

以下是当 $m>n$ 时，公式的证明方法：

![COMP9020 - Lecture 2: Number Theory pp.44](https://rin977.com/static/img/40ff4c68a4aa12d5de5440dfaf20f6cd.image.webp)

然而，在掌握了模运算后，该公式可以简化为：

$gcd(m,n)=$

$$
m,\ \ \ (m=n\ or\ n=0) \\
n,\ \ \ (m=0) \\
gcd(m\%n,n)\ \ \ (m>n>0) \\
gcd(m,n\%m)\ \ \ (0<m<n)
$$

COMP9020 1.2 离散数学概念

> Annoyingly, sometimes the English in the question is the hardest part, not the maths.



---
# 直接证明（Direct Proof）

分析条件，从条件出发，根据要求推导结论。

| Proposition Form | You Need to Do | Comment |
| --- | --- | --- |
| $ A⇒B $| assume A and prove B | 给出条件A，证明命题B |
| $ A ⇔ B $ | prove "if A then B" and "if B then A" | “当且仅当”，要有双向证明 |
| $ ∀x.A $ | show A holds for every possible value of x | 对任意x，命题A均成立 |
| $ ∃x.A $ | find a value of x that makes A true | 存在x，使得命题A成立 |

# 反证法（Contradiction）

To prove A is true, assume A is false and derive a contradiction.
That is, start from the negation of the proposition and derive false.

通过假设某个命题的否定为真，然后通过逻辑推理导出矛盾（contradiction），从而证明该命题实际上为真的证明方法。


:::tip{title="TIPS"}
Proof by contradiction only apples when your statement is for "IF A THEN B".

你只能在“$ A ⇒ B $”这种命题方式中使用反证法。以下表格中只是对逻辑条件中的取反的一种说明。
:::

以下为命题的否定的表示方法：


| Proposition Form | Negation | Comment |
| --- | --- | --- |
| $ A\ and\ B $ | $ not\ A\ or\ not\ B $ | 任一个条件取反 |
| $ A\ or\ B $ | $ not\ A\ and\ not\ B $ | 所有条件均取反 |
| $ A ⇒ B $ | $ A\ and\ not\ B $ | 条件A推导出非B即取反 |
| $ A ⇔ B $ | $ A\ and\ not\ B,\ or\ B\ and\ not\ A $ | 一个方向不成立即可取反 |
| $ ∀x.A $ | $ ∃x.\ not\ A $ | 假设一个反例 |
| $ ∃x.A $ | $ ∀x.\ not\ A $ | 假设没有能够成立的例子 |