黃子嘉 - 線代離散研究室: 1月 2011

2011-01-31

前人種樹, 後人.........種樹

Q1. 97中山電機

老師的解答為2^(i+j-1)
我的疑問是另個node不一定在另一邊子樹, 因為跑到root不是有可能折返跑回同一子樹嗎?
若root在level0, 那level2到level2, 應該是2^2*2^2, 一般化是2^(i+j)
若root在level1, 那level2到level2, 應該是2*2, 一般化是2^(i+j-2)

Q2. 97台中教大

leaves個數是否應為3^5?

Q3. 93交大資科

請問第4題的B小題為什麼是戊呢?

Q4. 94成大電機

這題L1應該是9, L2應該是1嗎?

Q5. 94師大資教

請問這題不是應該是 3!*3!, 是不是為無解@@?

謝謝助教~

2011-01-29

小小的觀念

請問一個linear operator with standard matrix T經過換底後, 是不是R(T')不一定跟原來的linear operator T 具相同的行空間?

謝謝!

投影

Q1:

B選項老師解答寫FALSE = = WHY?? 不是成立嗎?? A是寫TRUE的那B一定TRUE呀!!

Q2:

這題好奇怪= =!! B選項為何是對的呢!! 他的x1應該是10/6吧!答案是B = =

還有關於A選項我算出Proj s v 的NROM會是根號910/7 他說要求最短距離v~s那應該是在拿v-根號910/7對吧??

Q3:

這個敘述應該是錯的吧!! 95台大第六題!! 因為他沒說A和B是方陣捏!! 答案是說這個是正確的

[離散]時間複雜度

1.請助教幫我看一下答案

右下角是求 n^(1/2^k)=2

use Rule 1 => n^3+n^2log3n 之就不會了

還請助教幫忙指點謝謝

請問Least square approximtion 與Least square solution的關係是不是:

若x為一向量，而A為一基底。
求x對span(A)的Least square approximation，即求proj x (也就是 x 映射到 CS(A)上的向量);
而Least square solution則是指，proj x其用A為基底的表示法，即[proj x]_A。

另外，
若有兩個向量空間S與T，且S與T垂直(orthogonal, perpendicular)
除了上述條件外，還要再加上S與T 直和(direct sum)，S與T才可稱作 orthogonal complement。

請問這兩個觀念，對嗎?
謝謝 ~

2011-01-28

向量空間的問題

題7.的(c)要怎麼解呢?

手上的解答是寫:

取{v1,v2,v3}為N(A)之orthonormal basis

取{1/3 * [2, 0, -1, 2]^t}為N(A-I)之orthonormal basis

則A= 0 v1*v1^t + 0 v2*v2^t +0 v3*v3^t +v4*v4^t

請問為什麼這麼取呢? 是我漏抄了什麼還抄錯什麼嗎?

題4的(d) 答案是A*(A^t * A)A^t 嗎?

謝謝~

2011-01-27

內積&tree的小問題

Q1:

此題是FALSE 為什麼內積會有無限多種壓@@ 可否舉個小例子

Q2:

在離散中定義tree的高度是從0開始嗎= =? 高度就等於level ? 皆從0開始?

因為我看資結他level 是從1開始定的= = 那像在考清大他離散和資結是一起考的

那該如何去辨別呢!! PS因為今天寫清大考古題關鍵就錯在此問題XD

幾題有關向量空間的問題

三題皆為Ture or false的題目。
1. True
2. True
3. a: True, b:false

請問答案對嗎? 因為之前上課太趕，沒抄仔細，對答案沒有把握(尤其是第二)

謝謝~

2011-01-24

Q1:

這兩張圖是同購是要求點123456對應到隔壁那張圖的對應點
老師的答案:---我的答案:
1對到a ---1:a
2對到f ---2:f
3對到d---3:e
4對到c---4:b
5對到b---5:c
6對到e---6:e

這樣寫不知道是否OK@@

Q2:

此題的選項abcd該如何去判斷呢!!

Q3:

pusedoforest 是一顆長的怎樣的圖壓

2011-01-23

請問幾個第2次模擬考的問題

1.If the real matrix A is m*n and has the property A^T*A=I, then for any vector x in Rm, x-AA^Tx is orthogonal to the column space of A.這題是true

這題看來是正交矩陣，但我推不大出來為何正交…因為是正交矩陣…所以x-AA^Tx應該是屬於N(A^T)或N(A)嘛？

2.If A is an n*n real matrix such that x^TAx = 0, for all x in Rn, then A=0. 這題是false

這是因為x有可能是0對嗎？若加上條件x≠0，應該就成立吧？

2011-01-22

[離散]99中央資工

我想請問第一個選項中的 proper cycle是啥

麻煩可以舉個簡單的例子讓我比較好懂

謝謝 ^^

離散幾題疑問(組合圖論)

相關類題

我自己補上了座標
只考慮不經過(3,2)至(7,5)是不是太狹隘
是不是還要考慮(3,2)至(7,2) ,(3,2)至(7,3), (3,2)至(7,4)
(4,2)至(7,5)(7,4)(7,3)(7,2)等
(5,2)至(7,5)(7,4)(7,3)(7,2)等............
感覺算不完==
還是我根本想錯了

請助教指點了

~~~~~~~~~~~~~~~~~~~~~之前問的~~~~~~~~~~~~~~~~~~~~~

只是想確定(b)用最小著色數就可以吧?

2. 3.

這兩題完全不懂==|

是第3章的範圍嗎

ans:

每小時k個人總共k*n人所以 C(k*n,n) ,且有n個小時要排班(=相異箱子) ,

故n!*C(k*n,n)

不知是否正確

請助教跟各位達人指點一下了

2011-01-20

圖論

Q1:

這一題是看不懂題目要問甚麼=.= 該如何下手呢!!

Q2:

這一題我覺得很奇怪,他說保證G是連通的話,那不就是只要有V-1 = E 就是一顆tree這樣不就保證連通了嗎? 那為什麼還要寫成 CV-1 取2 +1的樣子呢

遞回

Q1:

這題看不懂他到底是要問甚麼 .. 還有為什麼遞回式子會這樣令!! AB兩小題ˊˋ

線性代數及離散數學的勘誤表已更新

更新離散數學第五版勘誤表，並於同一文章新增離散數學分類題庫第五版勘誤表

更新線性代數第三版勘誤表及線性代數分類題庫第三版勘誤表

2011-01-19

我覺得先圖底部顏色4種，然後再塗其他面３＊２＊２＊２

total=4*3*2*2*2

我想問他所謂的在空間中旋轉是什麼意思?
2.

這堤完全看不懂耶...

不知道是不是再說最短路徑

此題不知如何下手

感謝各位高手幫忙!!

2011-01-18

模擬考投影矩陣的問題

Find the matrix P that projects onto the plane x-y+z=0
解答是寫u=1/(3^1/2)*[-1 1 1]，Q = uu^T，P = I - Q，請問那個Q為何是這樣算的？
這個有點像house holder但又好像差一點點

2011-01-17

類似於鴿龍問題

A factory makes automobile parts. Each part has a code consisting of a digit,a letter,and a digit,with the digits disinct,such as 5C7,1O6,or 3Z0.Last week the factory made 8,000 parts.
Find the minimum number of parts that must have the same serial number.[96台大電機離散 14 .]

解答給D，但我覺得是C，理由如下:
   8000 = 2340 + 2340 + 2340 + 980
   Find the minimum number of parts that must have the same serial number.
   最小的重複號碼我認為只有三組
   ex: 位數為2，僅使用0~1編號，共14組
   考慮如下;
   (0 0)   (0 0)    (0 0)    (0 0)
   (0 1)   (0 1)    (0 1) (0 1)
   (1 0)   (1 0) (1 0)
   (1 1)   (1 1) (1 1)
   Find the minimum number of parts that must have the same serial number.
   >>三組

2011-01-16

離散題庫[T4]98中央資工(4-35頁)第13題

第12題,我自己解出的式子是到螢光筆處~

所以我第13小題就是用那個式子來求解

但是我最後解出的答案和解答給的不一樣

我附上我的算法~~請幫我找錯謝謝

機率問題

1.他說正獨立跟相依那我能直接用老師的公式嗎？ p(e1交集e2)=p(e1)p(e2) 說不是要說明一下，這個公式為何就是獨立相依

2.請問這提該如何解我猜答案是P 作法是另e1為 0-1 e2為收到1的機率求P(e1|e2)

5.證明不出來耶，我帶進去是錯誤的，我同學說可能試問這提條件式如何才會相等，如果是這樣該如何解

7.完全看不懂該如何下手，謝謝大家幫忙解題～

想確認一下作法跟一些問題

2.想請問第二提可以寫等價於T(N)=T(N/2)+1 這樣下去解嗎

3.這是出在數學考捲上的問題不知道可以用MASTER定理直接解嗎？還是要用數學的解法
題目有說divide and conquer 如果試用數學解法可以畫樹嗎

5.可以舉個例子然後寫出尤拉定義，然後找一條路徑給他嗎？

6.關於這提我跟同學討論過後，他的樹比我高卻比我總權重卻較少，當10+15＝25時這時要抓一個20跟他作，還是另外建一個20跟25 一起作，我用前面後者因為我想樹會比較矮

8.請問這提答案完整的定義應該怎描述我只會寫 ab* or ab*ab* 還是寫一個程式碼給他去判斷這個狀態接收

2011-01-15

圖論 Kn證明 , 求cut set ,Eulerian Path 證明

一、證明不太順手這樣寫不知可不可以

二、求cut set ,Eulerian Path 證明, 好像課本找不到相似的類題

(a)1/2(n-1)!

(b)n^n-2 說明我照[五版]7-33頁寫就好嗎?

(c)(d)小題完全沒有頭緒

(a) (b)沒頭緒=.=

請助教指點一下謝謝

請教模擬考的QR分解題

1.A=[cos sin]
[sin 0 ]

要算出QR，我在算u2的時候一堆sin^2和cos^2相乘，然後又要算單範就...是否有人可以幫解一下，三角函數有點弱，感謝

2.最後一題的(x < y < z)的反向為何是(x>=z or z>=y)呢？

3.The orthogonal projection of y onto v is the same as the orthogonal projection of y onto cv whenever c <> 0.
課本7-68提到proj b = Ax必定唯一，跟這題有關係嗎？怎麼感覺好像proj y = v應該是唯一的…

2011-01-14

請教正交補空間的問題

課本習題21. 任意實矩陣A, y屬於R^m，則y = yc + yn, yc屬於R(A)且yn屬於N(A^T)，這題是true

我有爬文看到之前助教回Allen同樣的問題，好像有說到正交投影矩陣才有R(A)垂直N(A^T)的性質，這題就只說是任意實矩陣，為何這題是true呢？若改成N(A)也是true嗎？

2011-01-13

離散圖論

想問關於此圖的 biconnected components ？我覺得找不到切點所以是沒解
不過大碩給的答案我不太懂所以想問一下這提

一題線代的問題

the non-pivot columns of a matrix are always linearly dependent.這題是false

想不出反例來，可否幫忙舉個反例的矩陣，感謝

生成函數觀念

題目解題是 1<= Xi <= 6
所以 A(X) = (x + x^2 + x^3 + x^4 + x^5 + x^6) ^5去解題
那可否將1<= Xi <= 6 變成 0<= Yi <= 5去解?
所以會變成A(X) = (1 + y^2 + y^3 + y^4 + y^5 ) ^5
不知道這樣可以嗎??
謝謝助教~~

2011-01-12

助教為什麼x*r的係數會是C (r-6取4) 應該是C( 5+r-1 取 r) 吧!!

有關函數的問題

if f:A->B and B is countable infinite, then A is always countably infinite.
這題是false，但我有疑問的是，老師上課時說f:R->Z，可是對角線論證法說明，Z->R時可以取到一個x屬於R，但Z對不到x，所以不onto，那這樣豈不是代表R->Z會有對不到的狀況，那這樣f:R->Z還算是函數嗎？