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


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)等............
感覺算不完==
還是我根本想錯了


請助教指點了




~~~~~~~~~~~~~~~~~~~~~之前問的~~~~~~~~~~~~~~~~~~~~~
1.
只是想確定(b)用最小著色數就可以吧?

2. 3.
這兩題完全不懂==|
是第3章的範圍嗎

4.

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種,然後再塗其他面3*2*2*2


total=4*3*2*2*2


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


這堤完全看不懂耶...

不知道是不是再說最短路徑
3.
此題不知如何下手
感謝各位高手幫忙!!




























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還算是函數嗎?

CH4

Q1:
D選項麻煩助教解釋一下他這個敘述是在敘述甚麼ˊˋ

Q2:

這題是說 有兩個線性轉換的合併之後不會線性轉換 其實還是會是線性轉換對吧!!,所以false



Q3


7.是false 助教可否請舉個反例 因為自己怎麼舉都是true呀!!

9.有點不懂這句英文的意思 做列運算為什麼會改變線性相依的關係呀!! 應該不可能說本來是線性相依然後做完就變成線性獨立吧!!

3Q助教

2011-01-11

rank


助教B和C之所以錯是因為應該是小於等於吧!!

生成函數

Q1:

助教紅色那一段 是怎麼由上面的推出來的呀!! 找來找去都找不到類似公式

Q2:

這一題答案是C 9取5對吧!!





Q3:


助教此題答案是1/(1-x)^n 嗎?


2011-01-10

複數做正規化

助教你好 線代第三版 8-78頁 範例4

-1+i
2

做完正規化是
-1+i
根號6

想請問norm怎麼算出根號6 謝謝

2011-01-09

排容

Q1:

助教這一題的(a)其中
N(a1,~a2,~a3)+N(~a1,a2,a3)+N(~a1,~a2,a3)為什麼會等於[N(a1)+N(a2)+N(a3)]-2[N(a1a2)]+N(a1a3)+N(a2a3)]+3N(a1a2a3)??
Q2:

這一題的答案是B 可是我算出來是374捏!! 應該是E吧!! 我算了2次了 =.=




CH4

Q1:

這題老師解答案上是無解=.= 可是我算出來的他的R(T)是{(4,2,6),(1,1,0),(-3,-4,9)} 而且他問哪些不是那答案應該是a b c d e吧!!

Q2:



這題老師的答案是給false,可是這個敘述老師不是有證過嗎!!是成立的 應該是True吧!!

2011-01-08

rank&nullity

助教這題的D選項 他的rank=3 nullity=0 是嗎?


*順便問一下!! 就是關於離散的組合數學那章 項式排列組合 亂序那種的 可以直接寫C取多少或是D3或D4嗎? 還是一定要求出答案呢?