计算机代考|理论计算机EECS 2001

这是一份加拿大 York University 的计算机专业EECS 2001: Introduction to the Theory of Computation科目的代考成功案例，学生在我们的帮助下取得了满意的成绩~

All topics from Lectures 0 􀀀 12 are relevant for the midterm, including regular expressions
(but not including the pumping lemma). You should, in particular be comfortable with all
questions that have appeared in the rst two assignments, or have been solved during the
tutorials. Below, I am listing some additional practice questions.

(a) $A$ is the set of all integers that are multiples of 3 and are less than or equal to 20. Thus $A={3,6,9,12,15,18}$. Since $A$ contains only six elements and each of them is also an element of $B$, we have $A \subseteq B$. On the other hand, $B$ contains only elements that are multiples of 3 and less than or equal to 18, whereas $A$ contains an additional element 20 that is not in $B$. Hence $B \subsetneq A$. The intersection of $A$ and $B$ is $A \cap B = {3,6,9,12,15,18}$.

(b) $A$ is the set of all ordered pairs $(1,1)$, $(1,2)$, $(3,1)$, and $(3,2)$, whereas $B$ is the set of ordered pairs $(1,1)$, $(2,1)$, and $(3,1)$. Thus $B$ is a proper subset of $A$, and we have $B \subsetneq A$. The intersection of $A$ and $B$ is $A \cap B = {(1,1),(3,1)}$.

To show that being connected by a path is an equivalence relation on the vertices of an undirected graph $G=(V,E)$, we need to show that it satisfies the following three properties:

1. Reflexivity: Every vertex is connected to itself by a path of length 0.
2. Symmetry: If vertex $u$ is connected to vertex $v$ by a path, then vertex $v$ is connected to vertex $u$ by a path.
3. Transitivity: If vertex $u$ is connected to vertex $v$ by a path and vertex $v$ is connected to vertex $w$ by a path, then vertex $u$ is connected to vertex $w$ by a path.

Proof:

1. Reflexivity: Every vertex is connected to itself by a path of length 0. Therefore, being connected by a path is reflexive.
2. Symmetry: Let $u$ and $v$ be two vertices in $G$ such that $u$ is connected to $v$ by a path. Let $P$ be a path in $G$ from $u$ to $v$. We can simply reverse the order of the vertices in $P$ to obtain a path from $v$ to $u$. Therefore, being connected by a path is symmetric.
3. Transitivity: Let $u$, $v$, and $w$ be three vertices in $G$ such that $u$ is connected to $v$ by a path and $v$ is connected to $w$ by a path. Let $P_1$ be a path in $G$ from $u$ to $v$ and let $P_2$ be a path in $G$ from $v$ to $w$. We can concatenate $P_1$ and $P_2$ to obtain a path from $u$ to $w$. Therefore, being connected by a path is transitive.

Since being connected by a path satisfies all three properties of an equivalence relation, it is indeed an equivalence relation on the vertices of an undirected graph.

For a directed graph, being connected by a path is not necessarily an equivalence relation. Specifically, it may not be symmetric. For example, consider the directed graph with vertices $u$, $v$, and $w$ and edges $(u,v)$ and $(v,w)$. Vertex $u$ is connected to vertex $v$ by a path, and vertex $v$ is connected to vertex $w$ by a path, but vertex $w$ is not connected to vertex $u$ by a path. Therefore, being connected by a (directed) path is not an equivalence relation in a directed graph.

To determine whether there exists a one-to-one function $f:A\rightarrow B$, we need to check whether each element of $A$ is assigned to a distinct element of $B$. If there exists such a function, we say that $A$ can be injected into $B$.

To determine whether there exists an onto function $g:A\rightarrow B$, we need to check whether every element of $B$ is the image of at least one element of $A$. If there exists such a function, we say that $A$ can be surjected onto $B$.

(a) $A = {1, 2, 3, 4}$ and $B = {1, 2, 3}$.

There exists a one-to-one function $f:A\rightarrow B$ if and only if $|A|\leq |B|$. In this case, we have $|A|=4$ and $|B|=3$, so there cannot exist a one-to-one function from $A$ to $B$.

There exists an onto function $g:A\rightarrow B$ if and only if $|A|\geq |B|$. In this case, we have $|A|=4$ and $|B|=3$, so there cannot exist an onto function from $A$ to $B$.

(b) $A = {a, b, c}$ and $B = {1, 2, 3, 4}$.

There exists a one-to-one function $f:A\rightarrow B$ if and only if $|A|\leq |B|$. In this case, we have $|A|=3$ and $|B|=4$, so there exists a one-to-one function from $A$ to $B$. For example, we can define $f(a)=1$, $f(b)=2$, and $f(c)=3$.

There exists an onto function $g:A\rightarrow B$ if and only if $|A|\geq |B|$. In this case, we have $|A|=3$ and $|B|=4$, so there cannot exist an onto function from $A$ to $B$.

Let $G=(V,E)$ be a tree. We can prove the given result by induction on the number of vertices in $G$.

Base Case: If $G$ has only one vertex, then there are no edges, and $|V|=1$ and $|E|=0$. Hence, $|V|=|E|+1$ holds.

Inductive Step: Assume that for any tree $T$ with $k$ vertices, we have $|V|=|E|+1$. Now, let $G$ be a tree with $k+1$ vertices. Choose any leaf vertex $v$ of $G$. By definition of a leaf, $v$ has degree 1, and is connected to only one other vertex $u$. Let $G’$ be the tree obtained from $G$ by removing $v$ and the edge $(u,v)$. Then, $G’$ has $k$ vertices and $k-1$ edges. By the induction hypothesis, we have $|V(G’)|=|E(G’)|+1$.

Now, adding the vertex $v$ and the edge $(u,v)$ back to $G’$ forms the tree $G$ with $k+1$ vertices and $k$ edges. Thus, \begin{align*} |V(G)| &= |V(G’)| + 1 \ &= |E(G’)| + 2 && \text{(by induction hypothesis)}\ &= k-1 + 2 \ &= k+1 \ &= |E(G)| + 1. \end{align*} Therefore, the equation $|V|=|E|+1$ holds for any tree $G=(V,E)$, by induction on the number of vertices.

线性代数后续课程数值分析代写成功案例

QR分解，Schmidt正交化,least sqaure method代写成功案例

凸优化代写成功案例