[線代]台科96

請問這題要怎樣解呢 謝謝...

[線代]minimal polynomial

Let A:nxn with entries over R such that A^2=-I,where I:nxn is the identity matrix.

If B:nxn is another matrix with entries over R such that B^2=-I,then A~B.

請問是true還是 false呢
--
可以先由 A^2+I=0 知道 A 之 minimal polynomial = (x+i)(x-i)知其有eigenvalue{i,-i}

B也一樣

而且他們的minimal polynomial重根數都只有1

可以看出來如果 over C 就都可以對角化

但是因為是 over R 所以不可對角化... (以上觀念有錯嗎 ?)

然後因為是over R所以不可對角化 然後要怎樣回答呢 ?

[線代] 一題應用題型請益

http://img163.imageshack.us/img163/8526/956dh.jpg

上面這題麻煩助教幫忙解惑一下~感謝 !!

一、請問unweighted longest simple path可以用DP在polynomial time完成嗎? why?

二、(不是題組.. 假設是無向圖)
請問下面這個演算法可以找到最長路徑嗎? 該怎麼 prove or disprove it呢
Step1:任意選取G=(V,E)上點u，然後找距離u最遠之點v
Step2:再由v找距離它最遠之點w，則(v,w)包含最長路徑

謝謝~

成大數學

想請問一下助教，(b)(c)這兩小題應該怎麼解呢？

不是很懂他的意思，麻煩了~

區分狀態的最短路徑

P2和P3之間還有(1,0) 可以區分，那答案是否多一組0010?

[線代]求f(A)

請問一下(c)小題要怎麼算比較好
Px(A)=(x-3)^3 檢查過無法對角化...

least

請問一下

漢斯圖若無least的話

是要回答空集合 還是無解啊 謝謝

least

請問一下

今年台大電機有考一題 漢斯圖的問題

若是沒有least的話

答案是有寫空集合 還是 寫無解啊??

謝謝

一、(94交大演算法)
下圖為甲市之街道圖，其中點A, B, ..., Y 等路口，線段 AB, AC, ..., TY等為街道，其旁邊之數字為相鄰路口之距離(m)，所有街道都是雙向道
每天晚上9點鐘起，警車乙由路口B出發，沿著cycle B-D-H-N-X-M-L-K-J-E-B 以30km/hr前進，每到一路口便停留10分鐘對所有經過該路口之車輛進行酒測臨檢，直到次日早上6點鐘。每天晚上10點鐘起，警車丙由路口S出發，沿著cycle S-M-X-V-W-O-G-C-D-I-L-R-S 以36km/hr前進，每到一路口便停留15分鐘對所有經過該路口之車輛進行酒測臨檢，直到次日早上7點鐘。
今有丁君於某日晚上10點鐘要由路口A開車以時速48公里到路口Y，當時酒精濃度為1.0單位，若酒精濃度在人體內以每分鐘0.01單位速率降低，甲市規定凡被酒測臨檢發現酒精濃度大於等於0.25單位皆會被立即扣留24小時
(a)(10%) 請算出丁君最快何時到達路口Y
(b)(15%) 請提出適當的演算法來解決問題
//內心的OS: 叫計程車應該最快，可是出題教授硬要別人酒駕。

















二、(91成大) 有限狀態機苦手..








三、Kruskal’s proof of correctness (紅色處不能理解..)

Let T’ be a minimum spanning tree

Let T be a tree formed by Kruskal’s algorithm that utilizes edges in T’

whenever a tie needs to be broken

Assumption: T has weight greater than T’

(otherwise Kruskal’s algorithm has produced an optimal solution)

Let e be the smallest weight edge in T that is not in T’

Add e to T’ and consider the cycle CY that is formed

There must be some edge e’ on cycle CY that has weight greater than e (Why?)

Replace e’ by e in T’

We have a new spanning tree T’’ and this new spanning tree has smaller weight

This contradicts the fact that T’ was a minimum spanning tree

四、

五、

六、

polya小問題

假設有籃和紅兩種顏色顏色的珠子若干個，選2顆做鍊子，可做多少不同鍊子？

可算出 (12 12)=(1)(2)=X1^2
(12 21)=(12)=X2

可得出總方法數1/2(2^2+2)=3

那題目改成選3顆珠子做鍊子的情況，

我的做法是不轉 (123 123)=(1)(2)(3)=X1^3
120度 (123 312)=(123)=X3
240度(123 231)=(123)=x3
總數是1/3(8+2+2)=4

答案不正確，書上寫＂鍊子的兩端對調無法辨識＂，

想請問什麼是對調無法辨識的情況?有點搞不清楚^_^"

T(n)=T(n-1) + 1/n

像這種的 T(n)(p) 要怎麼令?

幾個問題

1. let A and B be propositional formulas. then B is logically consequence of A iff (A and ~B) is
satisfiable
2.which one of the following propositional formulas logically implies all others?
(a) ~p and q (b) p->q (c) p or q (d) q

3.how many strongly connected components in a path with n vertices?
4.矩陣AX<=B的解有幾組?
A= b=
[1 -1 0 0 0] [0]
[1 0 0 0 -1] [-1]
[0 1 0 0 -1] [1]
[-1 0 1 0 0] [5]
[-1 0 0 1 0] [4]
[0 0 -1 1 0] [-1]
[0 0 -1 0 1] [-3]
[0 0 0 -1 1] [-3]
第一題是F?
第二題是要問什麼呢?

麻煩解答了 感謝

[線代]linear system

請問在解限性系統時發現做完是這個形式
[0 1 0][b1]
[1 0 0][b2]
[0 0 1][b3]


請問 x1 x2 x3中
x1 x2的解會反過來嗎?

線性代數

請問一下9-3和9-4~

9-3的direction of x' axis，應該要做逆時針還是順時針的旋轉？

9-4感覺是算出9-3後取其值乘以二，就是length 2。

麻煩解答了~

另外想請問在A可逆情況下，eigenvalue(A+2I)=eigenvalue(A)+2的觀念是什麼？

[線代]99 台大資工

[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]

求 determinant

請問老師這有特殊砍法嗎?

我當場只會暴力法

[線代]99 台大資工

[3 2 0 0 0]
[2 3 2 0 0]
[0 2 3 2 0]
[0 0 2 3 2]
[0 0 0 2 3]

求最大eigenvalue?

當場做的時候 怎麼砍都砍不成0

請教助教或黃大師

線代

Prove that if A is an invertible matrix and B is row equivalent to A, then B is also invertible


這題可以這樣證嗎?

存在P為可逆矩証 使得 PB=A
A可逆 使得 Ax=0 , x=0
=>PBx=Ax
=>P^-1PBX=P^-1*0
=>Bx=0

99數學

請問課本定義的Boolean代數是否為ring?

因為前天離散有題選擇是這樣
"Boolean algebra (A, *, +) ...blabla... a*(b+c)=a*b+a*c=...., and a+b*c=...."
謝謝~

[線代] 三題題目請益 !

http://twpic.org/uploads2/8d7084b632.jpg

麻煩助教解惑了 !!感謝!!!