作者LiquidTLO (俊偉)
看板Math
標題[其他] 離散兩題
時間Thu Oct 8 16:54:59 2020
題目1:
https://imgur.com/a/bwIe3cc
不需要知道(a)(b)(c)部分
跟(d)(e)無關
(d)部分我有證出後半段
想問要如何證明前半段
Hamming distance between any two codewords
in RS[5,3] is at least 3
(e)部分沒什麼想法
題目的max Hamming distance = m-n+1是typo
應該是min Hamming distance = m-n+1
題目2:
https://imgur.com/a/pJud5MX
題目裡的Maru還沒開始比
他贏第一場就拿1分
之後贏第i場就拿i分
(a)部分沒甚麼問題
(b)部分
我的想法是把分數i∈{1,2,...,10}
看作x_1+2x_2+3x_3+...+10x_10 > 27
0 <= x_i <= 1
但是不知道怎麼解含係數!= 1的不等式
我只解過x_1+x_2+...x_n = k這種的
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 61.224.187.128 (臺灣)
※ 文章網址: https://webptt.com/m.aspx?n=bbs/Math/M.1602147303.A.1B1.html
1F：→ hwanger : 讓F是指定的finite field 給定u1,u2在F^3中 並令P1, 10/08 22:13
2F：→ hwanger : P2為其相對應的polynomials 則Hamming distance為 10/08 22:15
3F：→ hwanger : ((P1-P2)(a0),(P1-P2)(a1),...,(P1-P2)(a5))的非零 10/08 22:17
4F：→ hwanger : 個數 注意到(P1-P2)是一個degree小於等於2的多項式 10/08 22:18
5F：→ hwanger : 所以最多兩個零根 故至少三個非零 10/08 22:20
6F：→ hwanger : 至於(e) 你的Decode(*)的定義或者所採用的演算法是 10/08 22:22
7F：→ hwanger : 啥? 因為一般的error correction code的decoding 10/08 22:24
8F：→ hwanger : function就是要滿足圖中的式子 並以此來找decode的 10/08 22:25
9F：→ hwanger : 算法 (一般來說 如果我們接收到錯誤的代碼C' 我們糾 10/08 22:28
10F：→ hwanger : 正錯誤的方法 就是去找Hamming distance最近的 10/08 22:28
11F：→ hwanger : codeword 再以此decording) 10/08 22:29
12F：→ hwanger : 至於題目2 我目前也沒有有效率的算法 不過可以用下 10/08 22:35
13F：→ hwanger : 列遞迴函數的方式解 令F(n,m)為"從1到n中至少取一個 10/08 22:40
14F：→ hwanger : 且其總和小於等於m"的方法數 則我們有 10/08 22:41
15F：→ hwanger : F(1,k)=1 for all k in N 10/08 22:43
16F：→ hwanger : when m>n, F(n,m)=F(n-1,m)+F(n-1,m-n)+1 10/08 22:45
17F：→ hwanger : when m=n, F(n,m)=F(n-1,m)+1 10/08 22:47
18F：→ hwanger : when m<n, F(n,m)=F(n-1,m) 10/08 22:49
19F：→ hwanger : 則所求為 1023-F(10,27) 至少可以跑程式 冏 10/08 22:50
20F：→ hwanger : 題目2的(b)根本不用上面這麼麻煩 XD 當我們從{1,2, 10/09 15:27
21F：→ hwanger : 3,...,10}中取一些數出來總和大於27時 剩下來的數總 10/09 15:28
22F：→ hwanger : 和就會小於等於27 反之亦然 也就是說我們可以在1024 10/09 15:29
23F：→ hwanger : 個子集合中兩兩湊對 所以總共有1024/2=512種方法數 10/09 15:30
24F：→ hwanger : 這裡湊對的方式就是子集合和他的補集 10/09 15:34
25F：→ hwanger : 所以27這個數字是特別挑過的 (28是1到55的中間) 10/09 15:34
26F：→ LiquidTLO : 對，我後來看到程式結果也想到這樣XD 10/09 19:33
27F：推 hwanger : XD 我也是 10/09 20:35
28F：推 hwanger : 這是個很好的警惕 先跑程式看看答案再說 XD 10/09 20:41