ผลต่างระหว่างรุ่นของ "01204211/activity8 polynomials and graph theory 1"

จาก Theory Wiki
ไปยังการนำทาง ไปยังการค้นหา
แถว 15: แถว 15:
  
  
'''A.1-2''' Let's experiment on erasure code using the degree 3 polynomial <math>f</math> from the last question.  You should work with another student.
+
'''A.1-2''' '''Erasure codes.''' Let's experiment on erasure codes using the degree 3 polynomial <math>f</math> from the last question.  You should work with another student.
  
 
''Encoding:'' Let's treat the first 4 digits of your ID <math>a_0,a_1,a_2,a_3</math> as a message.  We will encode it into 6 pairs of numbers (modulo 11) like this: <math>(0,f(0))</math>, <math>(1,f(1))</math>, <math>(2,f(2))</math>, <math>(3,f(3))</math>, <math>(4,f(4))</math>, <math>(5,f(5))</math>.
 
''Encoding:'' Let's treat the first 4 digits of your ID <math>a_0,a_1,a_2,a_3</math> as a message.  We will encode it into 6 pairs of numbers (modulo 11) like this: <math>(0,f(0))</math>, <math>(1,f(1))</math>, <math>(2,f(2))</math>, <math>(3,f(3))</math>, <math>(4,f(4))</math>, <math>(5,f(5))</math>.
แถว 24: แถว 24:
  
 
''Decoding:'' Now suppose that you have already got the encoded message (with 2 missing pairs) from your friend.  How can you decode the message?  Try to decode the message and check with your friend if you do that correctly.
 
''Decoding:'' Now suppose that you have already got the encoded message (with 2 missing pairs) from your friend.  How can you decode the message?  Try to decode the message and check with your friend if you do that correctly.
 +
 +
 +
'''A.1-3''' '''Secret sharing.'''
  
 
=== Graph theory 1 ===
 
=== Graph theory 1 ===
  
 
== Homework ==
 
== Homework ==

รุ่นแก้ไขเมื่อ 01:47, 26 พฤศจิกายน 2558

This is part of 01204211-58.

In-class activities

Polynomials

To work on these questions, you can refer to this lecture note from Berkeley.

For this set of activities, we shall work modulo 11.

We will use your student ID as a data. For , let denote the -th digit (counting from the lest, starting at 0) of your student ID. For example if your student ID is 5755543210, , , ,


A.1-1 We shall use your last 4 digits: . Find a polynomial of degree 3 such that for . You should start by writing down .


A.1-2 Erasure codes. Let's experiment on erasure codes using the degree 3 polynomial from the last question. You should work with another student.

Encoding: Let's treat the first 4 digits of your ID as a message. We will encode it into 6 pairs of numbers (modulo 11) like this: , , , , , .

Note that the first 4 pairs represent your message exactly. The last 2 pairs provide extra information.

Now discard 2 of the first 4 pairs, and give the rest (including the last 2 pairs) to your friend. (I.e., you should give your friend 4 pairs of integer modulo 11.) Notes: do not give out the polynomial.

Decoding: Now suppose that you have already got the encoded message (with 2 missing pairs) from your friend. How can you decode the message? Try to decode the message and check with your friend if you do that correctly.


A.1-3 Secret sharing.

Graph theory 1

Homework