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}
這題答案是:
是這樣嗎?
如果有錯 請助教能多多教我一下
2010-02-21
[離散] - 圖論 3
For the following graph, how many maximal cliques of size 3 are there,
and what is the size of maximum idependent sets?
答案是 8跟4嗎?
[離散] - 圖論 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-10
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是什麼意思?
感謝回答
訂閱：
文章 (Atom)