2010-02-28
2010-02-27
今天99台大數學考題
A=
[1 2 3 4 5]
[6 7 8 9 10]
[11 12 13 14 15]
[16 17 18 19 20]
[21 22 23 24 25]
求det(A-I)
感覺不難....可是沒想到 囧
[1 2 3 4 5]
[6 7 8 9 10]
[11 12 13 14 15]
[16 17 18 19 20]
[21 22 23 24 25]
求det(A-I)
感覺不難....可是沒想到 囧
2010-02-26
2010-02-25
[離散]Recurrence Relations
The problem examines a given convex polygon of n sides -that is, a polygon of n sides that satisfies the property: For all point P1 P2 within the interior of the polygon, the line segment joining P1 and P1 also lies within the interior of the polygon.
Given a convex polygon of n sides, Euler wanted to count the number of ways the interior of the polygon could be triangulated(Subdivided) by drawing diagonals that do not intersect.
for a convex polygon of n >= 3 sides, let t(n) count the number of ways the interior of the polygon can be triangulated by drawing non intersecting diagonals.
a)Define t(2) = 1 and verify that t(n+1) = t(2)t(n)+t(3)t(n-1) + ....+t(n)t(2)
請問助教這一題的題意到底在問什麼??
我進不到題目裡面
謝謝助教
Given a convex polygon of n sides, Euler wanted to count the number of ways the interior of the polygon could be triangulated(Subdivided) by drawing diagonals that do not intersect.
for a convex polygon of n >= 3 sides, let t(n) count the number of ways the interior of the polygon can be triangulated by drawing non intersecting diagonals.
a)Define t(2) = 1 and verify that t(n+1) = t(2)t(n)+t(3)t(n-1) + ....+t(n)t(2)
請問助教這一題的題意到底在問什麼??
我進不到題目裡面
謝謝助教
線代 證明
Let A and B be n*n matrices with property Ax=Bx for all x屬於Rn Show that A=B
這題不太會有大大會證明嗎
pai 提到...
感覺上是這樣因為所有x屬於Rn都可讓Ax=Bx取x=e_i, for i=1 to n也就是 Ae_i=Be_i =>A_i=B_i=>A和B的每一行都一樣所以A=B
若拙 提到...
我發覺 好像也不是這樣
耶假設A=[(0,-1),(0,1)]B=[(0,1),(0,-1)]x=[1,1]
則Ax=Bx但是A 不等於 B 呢
因為x是行向量相加不代表A等於B
我的看法是 false
有大大其他看法嗎?
這題不太會有大大會證明嗎
pai 提到...
感覺上是這樣因為所有x屬於Rn都可讓Ax=Bx取x=e_i, for i=1 to n也就是 Ae_i=Be_i =>A_i=B_i=>A和B的每一行都一樣所以A=B
若拙 提到...
我發覺 好像也不是這樣
耶假設A=[(0,-1),(0,1)]B=[(0,1),(0,-1)]x=[1,1]
則Ax=Bx但是A 不等於 B 呢
因為x是行向量相加不代表A等於B
我的看法是 false
有大大其他看法嗎?
[線代]Row Operations
Row operations on a matrix A can change the linear dependence relations among rows of A
ex
[1 1 1 1] [1 1 1 1]
[2 2 2 2] ~[0 0 0 0]
[1 2 3 4] [0 1 2 3]
原本2 3 列LI 之後變成 LD 所以是 true嗎 ?
另外請問
Let A be m*n matrix with m>n and b be an m*1 vector then Ax=b may have multiple solution
這應該是true吧 ?
ex
[1 1 1 1] [1 1 1 1]
[2 2 2 2] ~[0 0 0 0]
[1 2 3 4] [0 1 2 3]
原本2 3 列LI 之後變成 LD 所以是 true嗎 ?
另外請問
Let A be m*n matrix with m>n and b be an m*1 vector then Ax=b may have multiple solution
這應該是true吧 ?
2010-02-24
[線代]矩陣的rank問題
A:m*n
A具左反<->rank(A)=n
即A要行獨立
又A行獨立時 Ax=b 未必有解 若有解則必唯一
--
請問 Ax=b未必有解 可以用A之行空間之維度若未到達m 則有些b不在CS(A)中 這樣解釋
可是如果用A具左反來看 令A之左反為B
則 Ax=b -> x=Bb 這樣是錯在哪裡呢 看起來都可以得到x阿...
雖然自己舉例也可以看到矛盾
例如A=[1,0;0,1;0,0]
Ax=[0,0,1]^t本應無解
可是取A之左反等於A^t
則A^tAx = x = A^tb = [0,0]
列完式子 看起來變成Ax=b的近似解了 = =
請問左反對求解的意義是什麼呢 ?
單純就 Ax=b 若A具左反B 則 BAx=x=Bb 所以 x=Bb這樣來看 就字面來看很像是有解
可是實際上並不是這樣...
還是說在A之rank未到達m時
且b不屬於CS(A)時
A之左反就是用來求近似解呢
A具左反<->rank(A)=n
即A要行獨立
又A行獨立時 Ax=b 未必有解 若有解則必唯一
--
請問 Ax=b未必有解 可以用A之行空間之維度若未到達m 則有些b不在CS(A)中 這樣解釋
可是如果用A具左反來看 令A之左反為B
則 Ax=b -> x=Bb 這樣是錯在哪裡呢 看起來都可以得到x阿...
雖然自己舉例也可以看到矛盾
例如A=[1,0;0,1;0,0]
Ax=[0,0,1]^t本應無解
可是取A之左反等於A^t
則A^tAx = x = A^tb = [0,0]
列完式子 看起來變成Ax=b的近似解了 = =
請問左反對求解的意義是什麼呢 ?
單純就 Ax=b 若A具左反B 則 BAx=x=Bb 所以 x=Bb這樣來看 就字面來看很像是有解
可是實際上並不是這樣...
還是說在A之rank未到達m時
且b不屬於CS(A)時
A之左反就是用來求近似解呢
[離散] - 布林代數2
2.Suppose that(R,+,.)and(S,⊕,⊙) are two rings
with zero element Zr and Zs respectively.
Given a ring homorphism f:R→S,let K={aεR|f(a)=Zs}
Prove that
(a)(K,.,+) is a ring
(b)K is an ideal of R
謝謝
with zero element Zr and Zs respectively.
Given a ring homorphism f:R→S,let K={aεR|f(a)=Zs}
Prove that
(a)(K,.,+) is a ring
(b)K is an ideal of R
謝謝
[線代] - eigenvalue
Find det(A) given that A has p(入) as its characteristic polynomail
a. p(入) = 入^3 - 2入^2 +入 + 5
老師解法:
假設A為nxn,因為p(入)=det(入I-A)
→p(0) = det(-A) = (-1)^n det(A) = -5
我想問我一般p(入)會令成det(A-入I),這樣答案不是差的負號??
a. p(入) = 入^3 - 2入^2 +入 + 5
老師解法:
假設A為nxn,因為p(入)=det(入I-A)
→p(0) = det(-A) = (-1)^n det(A) = -5
我想問我一般p(入)會令成det(A-入I),這樣答案不是差的負號??
2010-02-23
[離散] - 布林代數
1. Suppose that (K. * , + )is a Boolean algebra and a is an atom of K.
Prove that a*b=0 or a*b=a for every b belongs K.
ps. 這邊的atom不知道是什麼
2. The following is a proof for a*0=0 in Boolean algebra (K,*,+),where a belongs K
a*0 = (a*0)+0 = (a*0)+(a*a')=a*(0+a')=a*a'=0
Prove a+1=1
a+1 = a+ (a+a') = a+a' =1
ps.我這樣寫第二步就出來了.....如果考試要我直接證明a*0=0
我也寫不出這麼多步驟耶~~這超直觀
Prove that a*b=0 or a*b=a for every b belongs K.
ps. 這邊的atom不知道是什麼
2. The following is a proof for a*0=0 in Boolean algebra (K,*,+),where a belongs K
a*0 = (a*0)+0 = (a*0)+(a*a')=a*(0+a')=a*a'=0
Prove a+1=1
a+1 = a+ (a+a') = a+a' =1
ps.我這樣寫第二步就出來了.....如果考試要我直接證明a*0=0
我也寫不出這麼多步驟耶~~這超直觀
線代 ,Show that no 2*2 matrices A and B exist that satisfy the matrix equation AB-BA=I
請問這裡這麼解阿?
Show that no 2*2 matrices A and B exist that satisfy the matrix equation AB-BA=I
用determine嗎? det(AB)=det(BA)
det(AB)-det(BA) =0
det(I)=1
矛盾
旦 det(AB-BA) 會等 det(AB)-det(BA) ?
Show that no 2*2 matrices A and B exist that satisfy the matrix equation AB-BA=I
用determine嗎? det(AB)=det(BA)
det(AB)-det(BA) =0
det(I)=1
矛盾
旦 det(AB-BA) 會等 det(AB)-det(BA) ?
離散~
一、(97台大資工) Suppose that (R, +, ×) is a ring. Prove that if S包含R is finite, then (S, +, ×) is a ring if
二、In how many ways can 60060 be factored into three factors, each greater than 1, if the order of the factors is not relevant?
謝謝
2010-02-22
[線代]Quadratic form
(a)(8%)Find the standard form of the quadratic curve
3(x^2)+2xy+3(y^2)+6√2 x-10√2 y+10=0.
(b)(4%)Give the coordinates of the center and the vectors representing the
two principal axes of the curve.(the x'-axis must be 0<=θ<π/2 and
the y'-axis must be π/2<=θ<π)
我算到後來有個疑問
V(2):span={[-1 1]}
V(4):span={[1 1]}
但我在第二題我看座標轉軸的時候
不是要看P^t 為順還是逆嗎?
但我如果把上面的eigenvector照順序把成行的話
會發生奇妙的結果耶
[cos -sin]
[sin cos]
左上角應該要跟又下角一樣的值
我照我的說的順序擺不就兩個cos 竟然不同值
這樣不就不是旋轉矩陣了嗎?
還是一定要注意要把成旋轉矩陣
PS:這一題是台大今年的期末考題
有點難算 希望跟有算的一起對答案
因為我算的數字醜到爆...
3(x^2)+2xy+3(y^2)+6√2 x-10√2 y+10=0.
(b)(4%)Give the coordinates of the center and the vectors representing the
two principal axes of the curve.(the x'-axis must be 0<=θ<π/2 and
the y'-axis must be π/2<=θ<π)
我算到後來有個疑問
V(2):span={[-1 1]}
V(4):span={[1 1]}
但我在第二題我看座標轉軸的時候
不是要看P^t 為順還是逆嗎?
但我如果把上面的eigenvector照順序把成行的話
會發生奇妙的結果耶
[cos -sin]
[sin cos]
左上角應該要跟又下角一樣的值
我照我的說的順序擺不就兩個cos 竟然不同值
這樣不就不是旋轉矩陣了嗎?
還是一定要注意要把成旋轉矩陣
PS:這一題是台大今年的期末考題
有點難算 希望跟有算的一起對答案
因為我算的數字醜到爆...
FSM的問題
(i)What is the set generated by the following phrase-structure grammar? G=(V,T,S,P), V={0,1,S}, T={0,1}, P={S->01,S->0S1}
這題答案是:
{0^n1^n n>=1}
(ii)Construct a phrase-structure grammar to generate the set {1^n0 n>=0}
這題答案是:
是這樣嗎?
如果有錯 請助教能多多教我一下
[離散]Graph
Let Kv(G)and Ke(G) represent the vertex connectivity and edge connectivity,
respectively, of a graph G.
show Kv(G)<= Ke(G)
沒看過證連通性的問題
請問助教要如何證明
謝謝
respectively, of a graph G.
show Kv(G)<= Ke(G)
沒看過證連通性的問題
請問助教要如何證明
謝謝
2010-02-21
[離散] - 圖論 3
[離散] - 圖論 2
1. Suppose G=(V,E) where V = {(1,3),(1,4),(1,6),(2,3),(2,5),(2,7),(3,7),(4,6),(4,7),(5,6)}
(d)Is G = ({1,2,4,5},{(1,4),(2,5),(5,6)}) a subgraph of G?
(e)Is the subgraph of G induced by {2,4,5,6,7} biconnected?
可以解釋一下嗎?
2.Suppose G=(V1,E1),H=(V2,E2) G,H is isomorphic,which of the statements are correct?
(a)|V1|=|V2| and |E1|=|E2|
(b)If G has Hamiltonian path, H has HP.
(c)If G is not planar,H isn't.
(d)If G has a matching of size k, H has,too
(e)G and H has same chromatic number.
4.Explain why every n-vertex srongly connected digraph contains at least n arcs
何謂arcs??
(d)Is G = ({1,2,4,5},{(1,4),(2,5),(5,6)}) a subgraph of G?
(e)Is the subgraph of G induced by {2,4,5,6,7} biconnected?
可以解釋一下嗎?
2.Suppose G=(V1,E1),H=(V2,E2) G,H is isomorphic,which of the statements are correct?
(a)|V1|=|V2| and |E1|=|E2|
(b)If G has Hamiltonian path, H has HP.
(c)If G is not planar,H isn't.
(d)If G has a matching of size k, H has,too
(e)G and H has same chromatic number.
4.Explain why every n-vertex srongly connected digraph contains at least n arcs
何謂arcs??
2010-02-20
[線代] - 一些觀念
95中央 T or F
(f) Perspective projection is combined from the perspective and projection
transformations; the perspective projection is not linear transformation, but
perspective transformation is invertible.
→請問perspective transformation是什麼阿? Perspective projection?
(j) The columns of the change-of-coordinates matrix P are C-coordinate vectors of
C<-B
the vector in B.
→這題看不懂,後面那句到底是C轉B還B轉C~考試很怕英文不好會錯意
謝謝
(f) Perspective projection is combined from the perspective and projection
transformations; the perspective projection is not linear transformation, but
perspective transformation is invertible.
→請問perspective transformation是什麼阿? Perspective projection?
(j) The columns of the change-of-coordinates matrix P are C-coordinate vectors of
C<-B
the vector in B.
→這題看不懂,後面那句到底是C轉B還B轉C~考試很怕英文不好會錯意
謝謝
[離散] - 圖論
上課筆記有一題: n個點{1,2,3,.........,n}
1.simple graph 個數?
2.三角形123 有幾個?
3.所有三角形有幾個?
4.平均一個graph的三角形有幾個?
另外,98中山電機
1.How many ways can the undirected complete graph be oriented into a directed graph?
2.Given two selected vertices S and T, how many paths of length n-1 with distinct vertices
from vertex S to vertex T are contained in the graph?
我圖論算個數都不太會.....不知道怎麼想
麻煩助教了,謝謝
1.simple graph 個數?
2.三角形123 有幾個?
3.所有三角形有幾個?
4.平均一個graph的三角形有幾個?
另外,98中山電機
1.How many ways can the undirected complete graph be oriented into a directed graph?
2.Given two selected vertices S and T, how many paths of length n-1 with distinct vertices
from vertex S to vertex T are contained in the graph?
我圖論算個數都不太會.....不知道怎麼想
麻煩助教了,謝謝
2010-02-19
2010-02-18
[離散] - 排列組合
1.Determine the number of four-element subsets of S = {1,2 ,3,......,15}
contaun no consecutive integers.
2. (1+x^2+x^4)^5 , how many terms are there? (是不是只能展開看有幾項~?)
3. The nuver of partitions of {1,2,3,4,5} into three blocks is [5 3]^t = 25
The total number of functions f: {1,2,3,4,5} -> {1,2,3,4} with |f({1,2,3,4,5})| = 3
is ?
ans: 4 x 25 x6 (看不懂)
contaun no consecutive integers.
2. (1+x^2+x^4)^5 , how many terms are there? (是不是只能展開看有幾項~?)
3. The nuver of partitions of {1,2,3,4,5} into three blocks is [5 3]^t = 25
The total number of functions f: {1,2,3,4,5} -> {1,2,3,4} with |f({1,2,3,4,5})| = 3
is ?
ans: 4 x 25 x6 (看不懂)
[線代] 一題題目請益
A linear system Ax=b of m equations and n variables . State under what conditions will the linear system have solutions , a unique solution ,
and infinity many solutions ?
------------------------------------------------------------
請問這題是直接寫出3版課本的定理1-19嗎?!
還是說有其他需要補充的地方呢?!!
麻煩各位了~謝謝 !!!
and infinity many solutions ?
------------------------------------------------------------
請問這題是直接寫出3版課本的定理1-19嗎?!
還是說有其他需要補充的地方呢?!!
麻煩各位了~謝謝 !!!
2010-02-17
[離散]邏輯 if p then q else r
請問 if p then q else r
等價於(p->q)and(~p->r) 等價於 (p and q)or(~p and r)
最後那一個是怎樣推的呢 ?
等價於(p->q)and(~p->r) 等價於 (p and q)or(~p and r)
最後那一個是怎樣推的呢 ?
2010-02-15
[離散] 一些題庫
大家好, 新年快樂
問題一:
(97中興資管) How many strings of five decimal digitals which have exactly three digitals 9s?
答案是C5取3乘9平方, 解答意思似乎是選三個位置放9, 其餘位置的範圍為0~8有九個
請問它不用扣掉首項為零的strings嗎?
如..{00999,01999,...,08999, 09099,09199,...,09899, 09909,09919,...,09989, 09990,09991,...,09998}這些
問題二:請問後面的n-2代表什麼意思呢
問題三: (c)小題為什麼會有個係數3?
問題四: 下面的推導好像有錯..不知道在哪裡
謝謝
問題一:
(97中興資管) How many strings of five decimal digitals which have exactly three digitals 9s?
答案是C5取3乘9平方, 解答意思似乎是選三個位置放9, 其餘位置的範圍為0~8有九個
請問它不用扣掉首項為零的strings嗎?
如..{00999,01999,...,08999, 09099,09199,...,09899, 09909,09919,...,09989, 09990,09991,...,09998}這些
問題二:請問後面的n-2代表什麼意思呢
問題三: (c)小題為什麼會有個係數3?
問題四: 下面的推導好像有錯..不知道在哪裡
(p→q)∧[﹁q∧(rˇ﹁q)]
≡(p→q)∧[﹁q∧(q→r)]
≡[(p→q)∧(q→r)]∧﹁q
≡(p→r)∧﹁q
≡(﹁pˇr)∧﹁q
謝謝
2010-02-14
[線代]負定判斷
Q=[ 0 1 1 ]
[ 1 0 1 ]
[ 1 1 0 ]
Q on the subspace M={x: x1 + x2+ x3 =0}
is 正定 負定 不定?
請問這種是直接判斷Q是不是負定就好
還是要縮小定義域 檢查M的element在Q 會不會恆小於0
如果M的element在Q會恆小於0 可以說Q在M上負定嗎 ?
例如 取M的一組basis={[1,-1,0]^t,[1,0,-1]^t}
M中的任一vector可表成x=c1v1+c2v2
則x^tQx = -2c1^2-2c1c2 -2c2^2 = -2((c1-c2/2)^2+3c2^2/4) 恆小於0
所以可以說 Q 在 M負定嗎 ?
2010-02-13
[離散]Eular Formula證明
先令N表所有區域為成的邊數總和(涵無線區域及重複邊)
因為每個區域至少含三邊 所以 N>=3r
因為每個邊至多落在2個區域邊界上 所以N<=2e
請問為什麼不是剛好落在兩個region的邊界上 所以N=2e 呢 ... ?
我看老師的筆記 算圍成region邊數的方法
似乎是要繞一圈耶
x----y----z
像這樣只有一個無限區域圍成外面region的邊數似乎要算成4個@@
這樣圍成外面region 和圍成裡面region的邊數都是6
因為每個區域至少含三邊 所以 N>=3r
因為每個邊至多落在2個區域邊界上 所以N<=2e
請問為什麼不是剛好落在兩個region的邊界上 所以N=2e 呢 ... ?
我看老師的筆記 算圍成region邊數的方法
似乎是要繞一圈耶
x----y----z
像這樣只有一個無限區域圍成外面region的邊數似乎要算成4個@@
x
\
y---z
|\ |
| t |
| |
w---v
這樣圍成外面region 和圍成裡面region的邊數都是6
2010-02-12
2010-02-11
2010-02-09
[離散]rooted ordered tree
How many rooted ordered tree on n vertices?
請問這題要怎樣算呢 ?
如果是求 binary tree 個數的話就是 C_n
這題答案是 C_n-1
rooted ordered tree 似乎就不限binary tree 了
請問這題要怎樣算呢 ?
如果是求 binary tree 個數的話就是 C_n
這題答案是 C_n-1
rooted ordered tree 似乎就不限binary tree 了
線代模擬考
2010-02-08
解遞迴-特徵方程式的問題
http://img504.imageshack.us/img504/3284/dsc03168ub.jpg
我對非齊次解裡的特徵解還是有一些不了解
如上圖裡
1.%(d0+d1 n+d2 n+.....)?
上面式子裡?那個位置是該看原本方程式裡的哪邊決定呢
%那位置老師上課說要看出現的次數~是要看根出現幾次就寫n次方嗎
括號內要怎麼看出要令幾項d呢
2.
像圖中
(1)為什麼會少一項呢 (2)中有假設d0和d1 可是(1)中只有假設一個?
(3)中有令到n的2次方 請問如何看要令到幾次方及哪些可以省略 這題裡好像省略d0和d1
(4)裡也有省略 要如何看呢
麻煩助教了
上課這裡有點聽得不太清楚
似懂非懂的
我對非齊次解裡的特徵解還是有一些不了解
如上圖裡
1.%(d0+d1 n+d2 n+.....)?
上面式子裡?那個位置是該看原本方程式裡的哪邊決定呢
%那位置老師上課說要看出現的次數~是要看根出現幾次就寫n次方嗎
括號內要怎麼看出要令幾項d呢
2.
像圖中
(1)為什麼會少一項呢 (2)中有假設d0和d1 可是(1)中只有假設一個?
(3)中有令到n的2次方 請問如何看要令到幾次方及哪些可以省略 這題裡好像省略d0和d1
(4)裡也有省略 要如何看呢
麻煩助教了
上課這裡有點聽得不太清楚
似懂非懂的
2010-02-07
2010-02-06
NPcomplete
it takes exponential number of steps to solve any NP complete problem in worst case?
順便請問助教 NP complete這部份怎麼讀比較好.....@@
另外,給一個graph,求connectivity和edge-connectivity是什麼意思?
感謝回答
順便請問助教 NP complete這部份怎麼讀比較好.....@@
另外,給一個graph,求connectivity和edge-connectivity是什麼意思?
感謝回答
2010-02-05
2010-02-04
組合問題[ASAP]
In how many ways can two dozen identical robots be assigned to
four assembly lines with
(a) at least three robots assigned to each line?
(b) at least three, but no more than nine, robots assigned to each line?
four assembly lines with
(a) at least three robots assigned to each line?
(b) at least three, but no more than nine, robots assigned to each line?
幾個小問題
看到一題:
1.how many paths length 4 are there in K7?
這題的path應該是指5個點的path吧?
假設考試時,忘了是哪種定義,可以自己假設lenght長度為4
是4個點的path嗎?
也就是在不確定的題目裡面,可以自己假設嗎......
2.還有,題目問求 largest value entries in matrix A是指在A的第一行裡面最大的元素
還是指A矩陣所有元素裡面最大的?
3.what formulas will make the nonlinear transformation into matrix transformation?
4.in what situation will you use compute a least square solution through a QR factorization?
5.請問min cut的定義是? 在做 flow network時,有時候不大確定要怎麼切....
麻煩解答了 感謝
1.how many paths length 4 are there in K7?
這題的path應該是指5個點的path吧?
假設考試時,忘了是哪種定義,可以自己假設lenght長度為4
是4個點的path嗎?
也就是在不確定的題目裡面,可以自己假設嗎......
2.還有,題目問求 largest value entries in matrix A是指在A的第一行裡面最大的元素
還是指A矩陣所有元素裡面最大的?
3.what formulas will make the nonlinear transformation into matrix transformation?
4.in what situation will you use compute a least square solution through a QR factorization?
5.請問min cut的定義是? 在做 flow network時,有時候不大確定要怎麼切....
麻煩解答了 感謝
2010-02-03
2010-02-01
[離散]Catalan number 之變形
令A(x)為a_n之生成函數
請問一下a_n = a_2*a_n-1 + a_3*a_n-2 + ... + a_n-1*a_2
a_2 = 1
這個要怎樣推導出 A(x)的多項式形式呢...
請問一下a_n = a_2*a_n-1 + a_3*a_n-2 + ... + a_n-1*a_2
a_2 = 1
這個要怎樣推導出 A(x)的多項式形式呢...
訂閱:
文章 (Atom)