[理工]中山103離散 良序證明

[h9638512 (馬吉叫我辦的)]

第一題的c要怎麼用良序法則證明數學歸納法?
http://i.imgur.com/6ZqmDwy.jpg
順便對一下第二題答案
http://i.imgur.com/E7CVqCk.jpg
http://i.imgur.com/Xy9ELFY.jpg
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 182.235.130.102
※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1483931220.A.D9C.html
※ 編輯: h9638512 (182.235.130.102), 01/09/2017 11:46:06
推 qq70200: http://i.imgur.com/cf4c4EW.jpg
推 qq70200: 然後第二的c應該是全部-[f(x1)=y1]的情況 所以是n!-(n-1)
→ qq70200: !
→ h9638512: 沒看到f(X1)不等於y1..感謝你的解答~
→ qq70200: 然後2的a我寫n^(m-2)因為f(x1)和f(xm)只能對應到yn
→ h9638512: 不好意思 可以再問一下4 5 6 8嗎?
→ h9638512: http://i.imgur.com/e2fZqa9.jpg
→ h9638512: 我以為2的a是多對ㄧ的意思  搞錯了 謝謝!!
推 qq70200: 2的e次方項應該是mn-2
→ h9638512: 扣掉2個關係的意思?
→ h9638512: 2的mn-2是這個意思嗎?
→ h9638512: http://i.imgur.com/RbmIjwu.jpg
推 yupog2003: 4.5題：http://imgur.com/tNPkmJF 沒答案，有錯請指正
→ qq70200: 應該是因為畫出的mxn矩陣中 x1y1和x2y2的位置都是1
→ yupog2003: 6,(1+x+x^2)(1+x^2+x^4)(1+x^3+x^6)...(1+x^2+x^(2n))
→ yupog2003: x^n係數即為所求
→ yupog2003: 8-a，for all u1,u2,v1,v2 屬於Zp*
→ yupog2003: (u1,v1)*(u2,v2)=(u1*u2 mod p,v1*v2 mod p)
→ yupog2003: =(u2*u1 mod p,v2*v1 mod p)=(u2,v2)*(u1,v1)，得證
→ yupog2003: 阿for all那行打錯了，應該是這樣：
→ yupog2003: for all u1,u2屬於Zp*, v1,v2屬於Zq*，眼殘把p跟q看錯
→ h9638512: 對耶 用矩陣去想要比較清楚 感謝!
→ h9638512: 跟大家對一下第七題的答案是(43,256,9)嗎?
→ h9638512: 第六題我跟y大寫一樣  但我不知道怎麼找Xn係數
→ h9638512: 還是只要說找Xn係數就好?
推 yupog2003: 對，只要說找係數就好，不然他直接問請問是多少就好了
→ yupog2003: 第七題我算(43,256,8)，負號應該不能直接轉
→ h9638512: OK!!
→ h9638512: 阿 減反了..
→ h9638512: 順便對一下第三題答案><
→ h9638512: http://i.imgur.com/i5nfFEy.jpg
→ h9638512: http://i.imgur.com/W26kNQz.jpg
→ h9638512: http://i.imgur.com/cVrEiTZ.jpg
→ h9638512: c最上面中間是+5  一開始寫錯沒改到
→ h9638512: http://i.imgur.com/5QvANQU.jpg
→ yupog2003: 第三題(a)(b)(c)都跟我一樣，提供一個自己常犯的小錯
→ yupog2003: 就是最後常常忘記加上,n>=0，這樣應該會被扣分
→ h9638512: 喔喔  例題後面都會加  但我還以為那個沒寫沒關係  感
→ h9638512: 謝提醒><
推 shortid: 良序性是在全序集中任何非空子集有最小元素
→ h9638512: 可以再解釋一下4的圖嗎?
→ h9638512: 看不太懂
→ h9638512: 有人會8b嗎?
→ yupog2003: 4的圖：由於只要出現010 or 011即可，我定義S為尚未出
→ yupog2003: 現第一個0的state，A為已出現第一個0的state
→ yupog2003: B為已出現01的state，則B只要再遇到不論是0或1皆可輸出
→ yupog2003: 1代表接受
→ h9638512: 逗點前面那個是輸入值，逗點後面如果為0是拒絕，1是接
→ h9638512: 受，是這樣嗎?
→ h9638512: 接受的意思是010或011出現才會是1?
→ yupog2003: 嗯嗯，正是如此，就典型的Mealy model
→ h9638512: 但mealy machine不是前面是輸入值後面是輸出值嗎?
→ h9638512: 還是輸出值在這題變成有沒有出現目標字串?
→ yupog2003: 嗯嗯因為題目說machine that recognizes這個字串
→ yupog2003: 所以我覺得他的意思應該就是這樣
→ h9638512: OK 完全懂了 感謝你~
→ h9638512: y大會8b嗎?
→ yupog2003: 被發現我不會8b了...