[離散] Ordering and ...?

2. 我的想法: 對15作整數分割
所有數字可以由{1,2,4,8}組合
那就可以加速之後的服務速度
不太清楚題目要的是不是如此..

3. (a) 我的想法: 字典排序法下最少的比較次數相當於第一次比較即結束, 所以b只要為 {4XXXXX, 5XXXXXX, 6XXXXX} 即可?
(b) 我的想法: 因為b>a, 所以只要c贏過b即可, 又c與b第一個分數相同, 所以只要c的第二字比b即可?
(c) 我的想法: 不知道如何下手..




請問上面兩題如何解答、是否如此解? 謝謝

[線代] - 台大95

這題除了一個一個TRY，有更快的方法知道答案嗎?

因為配分才三分，這張考卷又30題左右~~

可以猜or拆出答案嗎?

謝謝

正(半)定矩陣判斷

A為3*3矩陣,A為正(半)定
書上定理說 A的所有主子矩陣其行列式>(=)0
但在課本P8-88 注意事項8-21提到
這個矩陣
[10 0]
[00 0]
[00-1] 去掉第二列第二行,其行列式<0,所以不是正半定>=0,這樣不是跟定理有矛盾嗎?


另外,請問這題複雜度該怎麼求呢?
2^((2logn)^1/2)


麻煩解答了 謝謝

Householder

[1 -1]
[-1 1] = A, be the 3*2 matrix.
[1 -1]
Find a matrix H such that HA = R is an upper triangular matrix.

這題由題目可以知道求Householder，也知道可以令 x = [1 -1 1]^T，最後答案求出來是
[√3 -√3]
[  0     0]
[  0     0]
但想請問的是：如果題目給的矩陣不像此題恰好只差一個負號，那請問 x 要怎麼令呢？不知道我的問題表達夠不夠清楚..Orz

另外，假設題目給說T(x)=A(x)，求對L之reflect，
L spanned by [4 3]^T，想請問法向量該怎麼令= =？

感謝！

集合論

A,B,C為3個set
(A-B)⊕(A-C)=空集合
滿足此條件A,B,C之間的關係是什麼?


麻煩解答了 感謝

圖論

請問這題該如何解呢 ?



what are the directed graph in which each vertex has at most one outgoing edge?
還有這題要回答什麼呢?

麻煩解答 謝謝

[離散] 圖論部分

Show how to label a path of N vertices with the integers 1,2,.......,N such that

the absolute values of the difference of the labels of adjacent vertices are all different.

You can construct it inductively.



請問一下題目意思，以及該如何解答?


謝謝

[離散] - 94交大

這題我用想的，覺得(1)(2)是獨立的，答案卻是1.2.3
這題可以用想的嗎~?

還是一定得要用機率算?(機率都忘光光了)

Polya

請問如何用polya解正方體(對面著色,可著六色,考慮翻轉何旋轉)?

另外,
Given the vectors α=[2,3,0]、β=[0,-3,-2]，γ=[0,1,1]. Find the orthogonal projection of α+β along γ.
請問這題的意思是 把[2,0,-2]正交投影在 [0,1,1]上嗎?

麻煩解答了 謝謝

[線代]-94台大

請問一下這題答案多少? & 怎麼想?

請問正(半)定和正規矩陣的關係

我看老師書上的定義
over C 時 quadratic form 是實係數的矩陣 必為 Hermitian 而 Hermitian就是正規矩陣
over C 時 的正定矩陣的 quadratic form必為實係數 所以為 Hermitian
所以over C 時的正定矩陣必為正規矩陣
over R 時 正定矩陣不一定要Symmetric(Hermitian)
所以只有Symmetric的正定矩陣是正規矩陣是嗎 ?(重點在於它Symmetric)

還是有什麼詳細一點的說法來判定正(半)定 和正規矩陣之間的關係呢 ?
(當然T*T=TT*是最基本的定義 請問有什麼適用在不為Hermitian的正定矩陣的判斷法嗎 ?)

Cayley-Hamilton

請問一下這一題，有點麻煩的算式..不過想問一下求解一定都要拆開嗎？
直接展開再除不是也可以。

求出Pa(x)後除以題目，得到商式： -1-3-5-5-1+8+16+16，餘式：-1+5-4(ie.-A^2+5A-4)
求出來的答案是↓
[47 0 0]
[0 48 -50]
[0 50 48]

但老師給的答案是↓
[7 0 0]
[0 8 -10]
[0 10 8]

麻煩了..感謝

幾個問題

1.不大懂題目的意思P1,P2是向量,向量連成的線段是??這題感覺像是高中的題目......

b跟c題也不會

4.題目裡只說(G,*)是群,如果沒定義*的運算,這題可以確定答案嗎?

另外還有一題,求其bigO

k=0

for (i=0 to n-1)

for (j=0 to i^2 -1)

if (j%i==0)

for(z=0 to j-1)

k++;

這題該怎麼解?

問題有點多 麻煩解答了 謝謝

內積問題

這題題目似乎有錯

取 會<0

假設題目沒錯要如何求第二小題呢?

麻煩解答了 謝謝

Cayley-Hamilton

0 0 -2
0 1 0 , find e^At
1 0 3


像這種 如果想要用 Cayley-Hamilton + 極小多項式做

特徵方程式 : (X-1)^2 * (X-2)
極小多項式 : (X-1) * (X-2)

令 f(x) = e^xt

因為 極小多項式 可整除 f(x)

所以f(x) = a(X-1) + b

X=1 e^t = b
X=2 e^2t - e^t = a

再帶回 a(A-1I) + bI
這樣對嗎?

另外 我想問的是 如果今天 極小多項式 : (X-1)^2 * (X-2)

那我則要令f(x)= a(X-1) (X-2) + b(X-1) + c
可是 X 只能帶1 和 2
要如何求出 第三個變數?

圖論

上課筆記的note寫說
Km,n 的spanning tree 有 m^(n-1)*n^(m-1)種
請問如何求的呢?


感謝解答

線性代數

一、
A=[2 -3 -6 -4]
     [1 5 -3 11]
Consider A, find a particular solution and all the homegeneous solution to Ax=[2 1]^T(直的不好打).想請問這時候的X應該怎麼取比較好求？

二、向量 A=x+y+z 和向量 B=y-z 構成之平面法向量與向量 C=x-2z之夾角為何？
(題目真的是中文..XD)  正常不是會給向量的定義嗎..這樣可以求嗎？

想請問(B)小題應該怎麼解？
另外還想請問，老師的書上有另外多問了一個問題，他是插在(a)小題前面的，題目如下：
Show that there exists a matrix, call C in R^(p*m) with rank(C)=p such that CA=I.

應該是要我們求左反矩陣嘛，可是寫到rank(A)=p，dim(RS(A))=......再來就沒下文了XDD

問題有點多，麻煩了..

[線代] 一題Markov題型請益

http://twpic.org/uploads2/f9dd735880.jpg

上面這題麻煩各位幫忙解惑一下~謝謝 !!

遞迴求解

T(n)=2T(n/2)+logn // 原式

=4T(n/4)+3logn-2
=8T(n/8)+7logn-10
= ...
=2^kT(n/2^k)+(2^k-1)logn-XXX
_________________________^^^ 求不出closed form....

麻煩解答了，感謝。

[線代] 矩陣空間

題目是 是非
R^2*2 has a basis consisting of matrices whose trace is zero.
答案是False
我想問一下
這邊題目是說一組基底可以組成一個矩陣是什麼意思
是說一組基底取

還是該怎麼想?