T

TMA

Video History

Page 13 / 43
Calculus 3: Multivariable Functions, Limits, and Continuity
▶

Calculus 3: Multivariable Functions, Limits, and Continuity

Calculus 3: Multivariable Functions, Limits, and Continuity
▶

Calculus 3: Multivariable Functions, Limits, and Continuity

Calculus 3: Multivariable Functions, Limits, and Continuity
▶

Calculus 3: Multivariable Functions, Limits, and Continuity

Calculus 3: Multivariable Functions, Limits, and Continuity
▶

Calculus 3: Multivariable Functions, Limits, and Continuity

微积分 3 多元函数 极限和连续性
▶

微积分 3 多元函数 极限和连续性

### Problem 7 Suppose \( R \) is the relation on \( \mathbb{Z} \times \mathbb{Z} \) where \( aRb \) means that \( a \) has the same lowest order (right-most) digit as \( b \). **Example:** \((a, b) \in R\) when \( a = 1234 \) and \( b = 64 \) because both numbers end in 4. Determine whether \( R \) is an equivalence relation. Show your reasoning. --- ### Solution Yes, \( R \) is an equivalence relation. - **Reflexive:** \( a \) ends with the same digit as itself, so \((a, a) \in R\). - **Symmetric:** If \( a \) ends with the same digit as \( b \), then \( b \) ends with the same digit as \( a \). Thus, if \((a, b) \in R\), then \((b, a) \in R\). - **Transitive:** If \( a \) ends with the same digit as \( b \), and \( b \) ends with the same digit as \( c \), then \( a \) ends with the same digit as \( c \). Hence, \((a, c) \in R\). If asked this on the final, you must show proof of all three required properties.
▶

### Problem 7 Suppose \( R \) is the relation on \( \mathbb{Z} \times \mathbb{Z} \) where \( aRb \) means that \( a \) has the same lowest order (right-most) digit as \( b \). **Example:** \((a, b) \in R\) when \( a = 1234 \) and \( b = 64 \) because both numbers end in 4. Determine whether \( R \) is an equivalence relation. Show your reasoning. --- ### Solution Yes, \( R \) is an equivalence relation. - **Reflexive:** \( a \) ends with the same digit as itself, so \((a, a) \in R\). - **Symmetric:** If \( a \) ends with the same digit as \( b \), then \( b \) ends with the same digit as \( a \). Thus, if \((a, b) \in R\), then \((b, a) \in R\). - **Transitive:** If \( a \) ends with the same digit as \( b \), and \( b \) ends with the same digit as \( c \), then \( a \) ends with the same digit as \( c \). Hence, \((a, c) \in R\). If asked this on the final, you must show proof of all three required properties.

### 6. Consider the Turing machine \[ T = (Q, \Lambda, q_0, \delta) \] where: \[ \begin{aligned} \delta(q_0, 0) &= (1, R, q_1) \\ \delta(q_0, 1) &= (1, R, q_1) \\ \delta(q_1, 0) &= (1, L, q_0) \\ \delta(q_1, 1) &= (0, R, q_0) \\ \delta(q_0, \#) &= (1, R, q_1) \\ \delta(q_1, \#) &= (\#, R, h) \end{aligned} \] For the following tape, determine the final tape when \(T\) halts, assuming that \(T\) begins in state \(q_0\) at the position indicated by the arrow. Show all steps. ... # # 1 1 0 # # ... 起始箭头在第一个 1 上 使用中文解题
▶

### 6. Consider the Turing machine \[ T = (Q, \Lambda, q_0, \delta) \] where: \[ \begin{aligned} \delta(q_0, 0) &= (1, R, q_1) \\ \delta(q_0, 1) &= (1, R, q_1) \\ \delta(q_1, 0) &= (1, L, q_0) \\ \delta(q_1, 1) &= (0, R, q_0) \\ \delta(q_0, \#) &= (1, R, q_1) \\ \delta(q_1, \#) &= (\#, R, h) \end{aligned} \] For the following tape, determine the final tape when \(T\) halts, assuming that \(T\) begins in state \(q_0\) at the position indicated by the arrow. Show all steps. ... # # 1 1 0 # # ... 起始箭头在第一个 1 上 使用中文解题

### 5. Consider the following program segment: ```text i := 1 total := 1 while i < n do i := i + 1 total := total + i ```` Let ( p ) be the proposition: [ p:\quad ( \text{total} = \frac{i(i+1)}{2} \ \text{and}\ i \le n ) ] Use mathematical induction to prove ( p ) is a loop invariant. --- ## Solution ### Basis Step Before the loop is entered, ( p ) is true since [ \text{total} = 1 = \frac{1(1+1)}{2} ] and [ i \le n ] --- ### Inductive Step Suppose ( p ) is true and ( i = k < n ) after the ( k - 1 )-th execution of the loop. Since ( p ) is true: [ \text{total} = \frac{k(k+1)}{2} ] Suppose that the while loop is executed again. Then ( i ) is incremented to [ i = k + 1 ] Total becomes: [ \begin{aligned} \text{total} &= \text{total}_{\text{prev}} + i \ &= \frac{k(k+1)}{2} + (k+1) \quad \text{(by inductive hypothesis)} \ &= \frac{k(k+1) + 2(k+1)}{2} \ &= \frac{(k+1)(k+2)}{2} \end{aligned} ] --- After the loop, ( i \le n ) and `total` is still of the required form. Therefore, ( p ) is a loop invariant. ∎ 使用中文解答
▶

### 5. Consider the following program segment: ```text i := 1 total := 1 while i < n do i := i + 1 total := total + i ```` Let ( p ) be the proposition: [ p:\quad ( \text{total} = \frac{i(i+1)}{2} \ \text{and}\ i \le n ) ] Use mathematical induction to prove ( p ) is a loop invariant. --- ## Solution ### Basis Step Before the loop is entered, ( p ) is true since [ \text{total} = 1 = \frac{1(1+1)}{2} ] and [ i \le n ] --- ### Inductive Step Suppose ( p ) is true and ( i = k < n ) after the ( k - 1 )-th execution of the loop. Since ( p ) is true: [ \text{total} = \frac{k(k+1)}{2} ] Suppose that the while loop is executed again. Then ( i ) is incremented to [ i = k + 1 ] Total becomes: [ \begin{aligned} \text{total} &= \text{total}_{\text{prev}} + i \ &= \frac{k(k+1)}{2} + (k+1) \quad \text{(by inductive hypothesis)} \ &= \frac{k(k+1) + 2(k+1)}{2} \ &= \frac{(k+1)(k+2)}{2} \end{aligned} ] --- After the loop, ( i \le n ) and `total` is still of the required form. Therefore, ( p ) is a loop invariant. ∎ 使用中文解答

### 5. Consider the following program segment: ```text i := 1 total := 1 while i < n do i := i + 1 total := total + i ```` Let ( p ) be the proposition: [ p:\quad ( \text{total} = \frac{i(i+1)}{2} \ \text{and}\ i \le n ) ] Use mathematical induction to prove ( p ) is a loop invariant. --- ## Solution ### Basis Step Before the loop is entered, ( p ) is true since [ \text{total} = 1 = \frac{1(1+1)}{2} ] and [ i \le n ] --- ### Inductive Step Suppose ( p ) is true and ( i = k < n ) after the ( k - 1 )-th execution of the loop. Since ( p ) is true: [ \text{total} = \frac{k(k+1)}{2} ] Suppose that the while loop is executed again. Then ( i ) is incremented to [ i = k + 1 ] Total becomes: [ \begin{aligned} \text{total} &= \text{total}_{\text{prev}} + i \ &= \frac{k(k+1)}{2} + (k+1) \quad \text{(by inductive hypothesis)} \ &= \frac{k(k+1) + 2(k+1)}{2} \ &= \frac{(k+1)(k+2)}{2} \end{aligned} ] --- After the loop, ( i \le n ) and `total` is still of the required form. Therefore, ( p ) is a loop invariant. ∎
▶

### 5. Consider the following program segment: ```text i := 1 total := 1 while i < n do i := i + 1 total := total + i ```` Let ( p ) be the proposition: [ p:\quad ( \text{total} = \frac{i(i+1)}{2} \ \text{and}\ i \le n ) ] Use mathematical induction to prove ( p ) is a loop invariant. --- ## Solution ### Basis Step Before the loop is entered, ( p ) is true since [ \text{total} = 1 = \frac{1(1+1)}{2} ] and [ i \le n ] --- ### Inductive Step Suppose ( p ) is true and ( i = k < n ) after the ( k - 1 )-th execution of the loop. Since ( p ) is true: [ \text{total} = \frac{k(k+1)}{2} ] Suppose that the while loop is executed again. Then ( i ) is incremented to [ i = k + 1 ] Total becomes: [ \begin{aligned} \text{total} &= \text{total}_{\text{prev}} + i \ &= \frac{k(k+1)}{2} + (k+1) \quad \text{(by inductive hypothesis)} \ &= \frac{k(k+1) + 2(k+1)}{2} \ &= \frac{(k+1)(k+2)}{2} \end{aligned} ] --- After the loop, ( i \le n ) and `total` is still of the required form. Therefore, ( p ) is a loop invariant. ∎

### 4. Given recurrence relation \[ a_n = -a_{n-1} + n \] with initial condition \[ a_0 = 2 \] --- ### (a) Associated homogeneous recurrence relation **Solution:** \[ a_n = -a_{n-1} \] --- ### (b) General solution to the homogeneous recurrence \((a_n^{(h)})\) **Solution:** The characteristic equation has a single root \(-1\), so the general solution is \[ a_n^{(h)} = \alpha(-1)^n \] --- ### (c) Particular solution \((a_n^{(p)})\) **Solution:** Since the non-homogeneous part is \(n\), assume a particular solution of the form \[ a_n^{(p)} = cn + d \] Substitute into the recurrence relation: \[ cn + d = -\big(c(n-1) + d\big) + n \] \[ = -cn + c - d + n \] Rearranging: \[ 2cn - c + 2d - n = 0 \] \[ n(2c - 1) + (2d - c) = 0 \] Set each coefficient equal to zero: \[ 2c - 1 = 0 \Rightarrow c = \frac{1}{2} \] \[ 2d - \frac{1}{2} = 0 \Rightarrow d = \frac{1}{4} \] Therefore, the particular solution is \[ a_n^{(p)} = \frac{1}{2}n + \frac{1}{4} \]
▶

### 4. Given recurrence relation \[ a_n = -a_{n-1} + n \] with initial condition \[ a_0 = 2 \] --- ### (a) Associated homogeneous recurrence relation **Solution:** \[ a_n = -a_{n-1} \] --- ### (b) General solution to the homogeneous recurrence \((a_n^{(h)})\) **Solution:** The characteristic equation has a single root \(-1\), so the general solution is \[ a_n^{(h)} = \alpha(-1)^n \] --- ### (c) Particular solution \((a_n^{(p)})\) **Solution:** Since the non-homogeneous part is \(n\), assume a particular solution of the form \[ a_n^{(p)} = cn + d \] Substitute into the recurrence relation: \[ cn + d = -\big(c(n-1) + d\big) + n \] \[ = -cn + c - d + n \] Rearranging: \[ 2cn - c + 2d - n = 0 \] \[ n(2c - 1) + (2d - c) = 0 \] Set each coefficient equal to zero: \[ 2c - 1 = 0 \Rightarrow c = \frac{1}{2} \] \[ 2d - \frac{1}{2} = 0 \Rightarrow d = \frac{1}{4} \] Therefore, the particular solution is \[ a_n^{(p)} = \frac{1}{2}n + \frac{1}{4} \]

**3. Solve this recurrence relation** \[ a_n = -3a_{n-1} + 18a_{n-2} \] with initial conditions \[ a_0 = 2,\quad a_1 = 9. \]
▶

**3. Solve this recurrence relation** \[ a_n = -3a_{n-1} + 18a_{n-2} \] with initial conditions \[ a_0 = 2,\quad a_1 = 9. \]

## 2. Let \( G \) be the context-free grammar with non-terminal symbols \( V = \{S, A, B\} \), terminal symbols \( \Sigma = \{a, b\} \), start symbol \( S \), and productions \( P \): - \( S \to ABb \) - \( S \to Bb \) - \( A \to aB \) - \( A \to b \) - \( B \to ab \) - \( B \to \epsilon \) ### Which of these strings can be generated by \( G \)? (a) ab (b) bb (c) baaba (d) aababb (e) abb (f) bbb --- ### Solution All strings must end in **b**, that eliminates **(c)**. It isn’t possible to make three consecutive **b**’s, so **(f)** is eliminated. **(a), (b), (d), and (e)** are all generated by \( G \).
▶

## 2. Let \( G \) be the context-free grammar with non-terminal symbols \( V = \{S, A, B\} \), terminal symbols \( \Sigma = \{a, b\} \), start symbol \( S \), and productions \( P \): - \( S \to ABb \) - \( S \to Bb \) - \( A \to aB \) - \( A \to b \) - \( B \to ab \) - \( B \to \epsilon \) ### Which of these strings can be generated by \( G \)? (a) ab (b) bb (c) baaba (d) aababb (e) abb (f) bbb --- ### Solution All strings must end in **b**, that eliminates **(c)**. It isn’t possible to make three consecutive **b**’s, so **(f)** is eliminated. **(a), (b), (d), and (e)** are all generated by \( G \).

← PreviousNext →