מבחן משנת 2011 סמסטר ב מועד ב

קיים אלגוריתם דחיסה שלוקח כל מחרוזת בינארית באורך n פרט למחרוזת האפסים ודוחס אותה למחרוזת בינארית קצרה יותר באופן שניתן לשחזור

רשום בתשובה שהפיתרון טריויאלי.

אפשר לדעת מה הוא?

I'm pretty sure that that is an error in the answers and should be (a). For example, if I give you the binary string '1', there is no way to shorten it into a shorter string…

If i am wrong, hopefully the lecturers or assistants will correct me :)

Dear professors,

Can we please get a clarification on that one?

We saw that supposedly wrong answer more that once and just want to make sure that it is wrong!

thanks,

Sivan

The number of binary strings of length n which are not the all-zeros string is

2**n - 1

How many strings of length strictly shorter than n are there?

It's the sum of a geometric sequence:

sigma{i=0 , i <= n-1 } (2** i) = 1 + 2 + 4 + ... + 2**(n-1) = 2**n - 1

So the two sets have the same size, and we can define a mapping from one set to the other.

For instance if we work with n=2, the strings (we would like to compress) are : "01", "10", "11"

So we can define the following mapping:

"01" -> "" (empty string)

"10" -> "0"

"11" -> "1"

Obviously, there are many other possible mappings, this was just an example.

You may be able to map everything to a shorter length, but you wont be able to decode it. For example in your code, you receive the string '1' and would like to decode it. So you know '1'->'11'. But what about empty strings? There are an infinite amount of empty strings in '1'! So you dont have enough data to know what to write.

And if you say - ok, lets transfer only the representation of one number at a time and not a word, then how do you send an empty binary pattern? These arnt strings or some kind of data object (otherwise they would have significant overhead, without relation to the data). Its just bits. You cant send an empty bit through a network card… also, mathematically, an empty bit is not in the Field of natural numbers, so its just an abstract notion….

if i am wrong, i hope the lecturers will correct me.

The idea was to understand that there can be such a mapping between the two sets since the sets are of the same size (as explained above).

However, if I am not mistaken, in the exam itself - because of the issue of sending an empty string - both answers (Tzfnia is correct, and Tzfabia is a liar) were accepted .