作者查詢 / eggy1018

總覽項目：發文 | 留言 | 暱稱

作者 eggy1018 在 PTT [ Grad-ProbAsk ] 看板的留言(推文), 共265則

限定看板：Grad-ProbAsk

首頁

尾頁

[理工] 演算法TSP問題

[ Grad-ProbAsk ]29 留言, 推噓總分: +3

作者: TEPLUN - 發表於 2018/09/24 16:10(5年前)

1^F推eggy1018: 因為是要用tsp的問題解Hamilton cycle, 所以是由Hamilto09/24 20:55

2^F→eggy1018: n cycle reduce到 TSP，reduces 後的new graph G’一定09/24 20:55

3^F→eggy1018: 存在Hamilton cycle, 令原來Hamilton cycle 的問題為G(V09/24 20:55

4^F→eggy1018: ,E) -> G’(V,E’), 其中E是完全圖的邊。因為Hamilton09/24 20:55

5^F→eggy1018: cycle 存在G中，所以令裡面的edge weight=0(即原來屬09/24 20:55

6^F→eggy1018: 於E的邊), 其他的為1。因此解完TSP的同時，因為Hamilt09/24 20:55

7^F→eggy1018: on cycle 的邊在E中，又因為E的edge weight=0, 所以cost09/24 20:55

8^F→eggy1018: 為0，若不為0則表示沒Hamilton cycle09/24 20:55

9^F→eggy1018: 因為可以用poly time Algo 驗證，加上可以由Hamilton cy09/24 20:56

10^F→eggy1018: cle reduced to TSP,所以TSP是NP complete09/24 20:56

13^F推eggy1018: 是可以互相reduce 因為那是NP hard的性質～也謝謝你上09/24 23:30

14^F→eggy1018: 次細心回答我的問題09/24 23:30

27^F推eggy1018: 感謝點明觀念，我的意思可能沒表達清楚可以互相reduce09/25 11:33

28^F→eggy1018: 但不一定都是polynomial time, NPC則是一定可以在polyn09/25 11:33

29^F→eggy1018: omial time 互相reduces09/25 11:33

[理工] 離散 1-114題費馬小定理

[ Grad-ProbAsk ]6 留言, 推噓總分: +4

作者: yunghan15 - 發表於 2018/09/24 18:52(5年前)

4^F推eggy1018: 在推費馬小定理的時候是兩邊都乘m並累乘了特定次數(即09/24 20:46

5^F→eggy1018: 戶質的個數)，因為累乘結果和mod m的m必戶質（而且兩邊09/24 20:46

6^F→eggy1018: 都有），根據定理可以相消09/24 20:46

[理工] 線代正規方程式觀念疑問

[ Grad-ProbAsk ]16 留言, 推噓總分: +5

作者: eggy1018 - 發表於 2018/09/18 15:38(5年前)

14^F→eggy1018: 謝謝各位大大！！09/21 15:56

[理工] 線代正交補空間

[ Grad-ProbAsk ]10 留言, 推噓總分: +4

作者: AAQ8 - 發表於 2018/09/18 22:00(5年前)

1^F推eggy1018: 因為u是orthonormal vector, u^Tu=I09/18 22:39

2^F→eggy1018: 所以原本的投影矩陣公式u*(u^Tu)^-1*u^T 變成 u*u^T09/18 22:40

7^F推eggy1018: 把u帶進去投影公式看看就知道為什麼了09/19 11:05

[理工] 線代矩陣有解的判斷

[ Grad-ProbAsk ]31 留言, 推噓總分: +16

作者: piskebee - 發表於 2018/09/13 08:03(5年前)

1^F推eggy1018: 就Amxn來說，若是rank=n時稱作full column rank,此時A09/13 08:21

2^F→eggy1018: 的row在做消去法的同時若出現一個「非零值=0」則「無解09/13 08:21

3^F→eggy1018: 」，反之就是「0=0」，所以有「唯一解」09/13 08:21

4^F推eggy1018: Rank = m則稱為full row rank, 此時「不可能會有0=0」09/13 08:24

5^F→eggy1018: 產生，要考慮的是在消去法的同時會產生多少的free varia09/13 08:24

6^F→eggy1018: ble, 所以宏觀而言，如果rank = m < n就無限多組解，因09/13 08:25

7^F→eggy1018: 為必有free variable 出現09/13 08:25

8^F推eggy1018: 無解》消去法過程中非零值 = 0 / 無限多組解〉有自由09/13 08:28

9^F→eggy1018: 變數出現（rank(A)< n)09/13 08:28

10^F推eggy1018: 最後你寫唯一解跟無限多解的方式都是對的，至於在看例題09/13 08:32

11^F→eggy1018: 的時候建議從rank & 消去法下手，以上有錯還請告知09/13 08:32

24^F推eggy1018: 感謝K大分享新觀點09/13 13:12

[理工] 台大資工+電機丙 106 離散答案

[ Grad-ProbAsk ]3 留言, 推噓總分: +3

作者: yeye1313 - 發表於 2018/09/11 10:42(5年前)

1^F推eggy1018: 推好心09/11 12:52

[理工] 離散生成函數數列設不同起始點的問題

[ Grad-ProbAsk ]16 留言, 推噓總分: +5

作者: piskebee - 發表於 2018/09/10 20:28(5年前)

10^F推eggy1018: 生成函數的係數就代表著這個函數可以生成的數列，所以09/11 08:25

11^F→eggy1018: 為了符合數列的係數，其起始值x^n 最小都應該是x^0，所09/11 08:25

12^F→eggy1018: 以你的算式在化簡的時候有出現1/x的狀況，應該要變數變09/11 08:25

13^F→eggy1018: 換換掉才是，比如n用n+1代，就沒事了09/11 08:25

14^F→eggy1018: 以上為個人淺見，有錯還請告知09/11 08:26

[理工] 離散5-54

[ Grad-ProbAsk ]5 留言, 推噓總分: +3

作者: qazws3483 - 發表於 2018/09/07 12:56(5年前)

4^F推eggy1018: K-1表示你能用n這個數表示的2進位數的最高次項，也就是09/07 14:41

5^F→eggy1018: 說n = 2^k-1 + 2^k-2.....，只是k-1表示能夠進到第幾位09/07 14:41

線代對角矩陣與對稱矩陣

[ Grad-ProbAsk ]13 留言, 推噓總分: +5

作者: o5739201 - 發表於 2018/09/03 17:55(5年前)

8^F推eggy1018: 對稱矩陣都是可對角化的，而題目指的是可以和非對稱矩陣09/03 19:55

9^F→eggy1018: 相似，可對角化的集合為相似集合的子集09/03 19:55

10^F→eggy1018: 所以說可以A對角化，相當於A和某個對角矩陣相似09/03 19:55

11^F推eggy1018: https://i.imgur.com/bYrxuDv.jpg09/03 19:57

12^F→eggy1018: https://i.imgur.com/GawzpY8.jpg09/03 19:58

[理工] 線性代數黃子嘉題庫8-39題

[ Grad-ProbAsk ]10 留言, 推噓總分: +5

作者: hl654ck6 - 發表於 2018/09/03 05:04(5年前)

4^F推eggy1018: https://i.imgur.com/Ecvi7Po.jpg09/03 12:07

5^F→eggy1018: 如果有錯還請包涵，採用8-63定理8-27的概念09/03 12:08

首頁

尾頁