сайты - меню - вход - но­во­сти


Задания
Версия для печати и копирования в MS Word

Фо­кус­ник и его Ас­си­стент го­то­вят­ся по­ка­зать сле­ду­ю­щий фокус. Фо­кус­ни­ку за­вя­жут глаза, после чего один из зри­те­лей на­пи­шет на доске 60-бит­ное слово (по­сле­до­ва­тель­ность из 60 нулей и еди­ниц). Ас­си­стент уве­рен, что смо­жет не­за­мет­но пе­ре­дать фо­кус­ни­ку за­пис­ку, со­дер­жа­щую 44 бита (не обя­за­тель­но биты за­га­дан­но­го слова, может на­пи­сать какие хочет). После чего Фо­кус­ник дол­жен будет на­звать слово. Для ка­ко­го наи­боль­ше­го числа C Фо­кус­ник и Ас­си­стент могут при­ду­мать стра­те­гию, поз­во­ля­ю­щую все­гда на­звать слово, сов­пав­шее хотя бы в C битах с на­пи­сан­ным зри­те­лем.

Спрятать решение

Ре­ше­ние.

До­ка­жем оцен­ку C мень­ше или равно 56. Пусть су­ще­ству­ет стра­те­гия, поз­во­ля­ю­щая оши­бать­ся не более чем в k битах (т. е. C=60 минус k пра­вая круг­лая скоб­ка . Тогда за­ме­тим, что На­блю­да­тель, зна­ю­щий стра­те­гию Фо­кус­ни­ка, со­об­щен­ное Ас­си­стен­том слово, и набор бит, в ко­то­рых ошиб­ся Фо­кус­ник, может вос­ста­но­вить на­пи­сан­ное Зри­те­лем слово. В самом деле, На­блю­да­тель берет слово, ко­то­рое дол­жен был на­пи­сать Фо­кус­ник, и ме­ня­ет его в тех ме­стах, где Фо­кус­ник ошиб­ся. Зна­чит, ко­ли­че­ство раз­лич­ных пар вида «слово со­об­щен­ное Ас­си­стен­том и набор мест, в ко­то­рых фо­кус­ник ошиб­ся» не мень­ше, чем раз­лич­ных слов, ко­то­рые мог на­пи­сать зри­тель. То есть

 2 в сте­пе­ни левая круг­лая скоб­ка 44 пра­вая круг­лая скоб­ка левая круг­лая скоб­ка левая круг­лая скоб­ка \beginarrayc 60 0 \endarray пра­вая круг­лая скоб­ка плюс левая круг­лая скоб­ка \beginarrayc 60 1 \endarray пра­вая круг­лая скоб­ка плюс умно­жить на s плюс левая круг­лая скоб­ка \beginarrayc 60 k \endarray пра­вая круг­лая скоб­ка пра­вая круг­лая скоб­ка боль­ше или равно 2 в сте­пе­ни левая круг­лая скоб­ка 60 пра­вая круг­лая скоб­ка .

Пе­ре­пи­шем в виде

 левая круг­лая скоб­ка левая круг­лая скоб­ка \beginarrayc60 0\endarray пра­вая круг­лая скоб­ка плюс левая круг­лая скоб­ка \beginarrayc60 1\endarray пра­вая круг­лая скоб­ка плюс умно­жить на s плюс левая круг­лая скоб­ка \beginarrayc60 k\endarray пра­вая круг­лая скоб­ка пра­вая круг­лая скоб­ка боль­ше или равно 2 в сте­пе­ни левая круг­лая скоб­ка 16 пра­вая круг­лая скоб­ка ,

и за­ме­тим, что при k мень­ше или равно 3 не­ра­вен­ство не­вер­но: 2 в сте­пе­ни левая круг­лая скоб­ка 16 пра­вая круг­лая скоб­ка боль­ше 64 000, но

 левая круг­лая скоб­ка \beginarrayc60 0\endarray пра­вая круг­лая скоб­ка плюс левая круг­лая скоб­ка \beginarrayc60 1\endarray пра­вая круг­лая скоб­ка плюс левая круг­лая скоб­ка \beginarrayc60 2\endarray пра­вая круг­лая скоб­ка плюс левая круг­лая скоб­ка \beginarrayc60 3\endarray пра­вая круг­лая скоб­ка мень­ше 1 плюс
 плюс 60 плюс дробь: чис­ли­тель: 60 в квад­ра­те , зна­ме­на­тель: 2 конец дроби плюс дробь: чис­ли­тель: 60 в кубе , зна­ме­на­тель: 6 конец дроби =1 плюс 60 плюс 1800 плюс 36 000.

Те­перь по­про­бу­ем по­ка­зать, из каких со­об­ра­же­ний стро­ит­ся при­мер. Для на­ча­ла на­пом­ним кон­струк­цию, из­вест­ную как ма­те­ма­ти­кам так и про­грам­ми­стам: дво­ич­ный код длины 15, поз­во­ля­ю­щий пе­ре­дать 11 бит по­лез­ной ин­фор­ма­ции и ис­пра­вить ошиб­ку не более чем в одном бите (также из­ве­стен как 15-бит­ный код Хэм­мин­га). По­стро­им его.

Для на­ча­ла за­ме­тим, что есть ровно 11 слов длины 4 из нулей и еди­ниц, со­дер­жа­щих хотя бы две еди­ни­цы (всего слов 2 в сте­пе­ни левая круг­лая скоб­ка 4 пра­вая круг­лая скоб­ка =16, минус одно из одних нулей, минус че­ты­ре с одной еди­ни­цей). При­пи­шем такие слова но­ме­рам от 1 до 11 как угод­но, на­при­мер как в таб­ли­це:

 

№1№2№3№4№5№6№7№8№9№10№11
0011010110010110101011000111 1011110111101111

 

Те­перь по­стро­им код таким об­ра­зом: в пер­вые 11 бит за­пи­шем те биты, ко­то­рые хотим пе­ре­дать (пер­вые 11 по­зи­ций будем на­зы­вать ин­фор­ма­ци­он­ны­ми). В по­след­ние 4 бита за­пи­шем сле­ду­ю­щие кон­троль­ные суммы. В 12-й за­пи­шем сумму по мо­ду­лю два тех из пер­вых 11 бит, при­пи­сан­ное 4-знач­ное число ко­то­рых имеет 1 в пер­вом раз­ря­де, то есть биты №№ 3, 5, 6, 8, 9, 10, 11. В 13-й  — сумму тех из пер­вых 11 бит, при­пи­сан­ное 4-знач­ное число ко­то­рых имеет 1 во вто­ром раз­ря­де, в 14-й сумму бит, име­ю­щих 1 в тре­тьем раз­ря­де при­пи­сан­но­го слова, в 15-й  — в чет­вер­том. По­ка­жем, по­че­му этот код поз­во­ля­ет ис­пра­вить одну ошиб­ку при пе­ре­да­че.

Пусть По­лу­ча­тель по­лу­чил ко­до­вое слово, воз­мож­но ис­ка­жен­ное в одном бите. По­лу­ча­тель точно так же по пер­вым 11 битам по­счи­та­ет 4 кон­троль­ные суммы, и срав­нит их с че­тырь­мя по­лу­чен­ны­ми. Если сов­па­ли все че­ты­ре  — то слово дошло без ис­ка­же­ний. В самом деле, если бы ис­ка­зил­ся кон­троль­ный бит  — в нем было бы рас­хож­де­ние, а если ин­фор­ма­ци­он­ный  — то рас­хож­де­ния были бы во всех кон­троль­ных, в ко­то­рые он вхо­дит. Ана­ло­гич­но, если рас­хож­де­ние есть ровно в одном кон­троль­ном бите, то ис­ка­зил­ся имен­но он. В самом деле, если ис­ка­зил­ся дру­гой кон­троль­ный  — то все ин­фор­ма­ци­он­ные дошли пра­виль­но, тогда в этом кон­троль­ном рас­хож­де­ния бы не было; а если ис­ка­зил­ся ин­фор­ма­ци­он­ный, то все кон­троль­ные дошли пра­виль­но, и тогда рас­хож­де­ния были бы во всех кон­троль­ных, в ко­то­рые вхо­дит ис­ка­жен­ный ин­фор­ма­ци­он­ный, а таких кон­троль­ных хотя бы два (имен­но за этим мы при­пи­сы­ва­ли ком­би­на­ции нулей и еди­ниц, со­дер­жа­щие хотя бы две еди­ни­цы). По ана­ло­гич­ным со­об­ра­же­ни­ям если по­лу­ча­тель видит не менее двух рас­хож­де­ний с кон­троль­ны­ми би­та­ми, то ис­ка­жен точно ин­фор­ма­ци­он­ный. Тогда до­ста­точ­но из 11 ин­фор­ма­ци­он­ных по­зи­ций вы­брать ту, в при­пи­сан­ном 4-бит­ном слове ко­то­рой еди­ни­цы стоят ровно на тех ме­стах, на ко­то­рых есть рас­хож­де­ния с кон­троль­ны­ми сум­ма­ми  — это и есть ис­ка­жен­ная по­зи­ция.

Те­перь по­ду­ма­ем в дру­гих тер­ми­нах, что же мы по­стро­и­ли. У нас есть код из 211 ко­до­вых слов. Каж­дое из этих слов можно ис­ка­зить 16 спо­со­ба­ми (ни­че­го не ме­нять, или из­ме­нить один из 15 бит). Все 16 \times 2 в сте­пе­ни левая круг­лая скоб­ка 11 пра­вая круг­лая скоб­ка по­лу­чен­ных в ре­зуль­та­те слов будут раз­ны­ми. В самом деле, если бы какое-то слово w по­лу­ча­лось двумя раз­ны­ми спо­со­ба­ми: ис­ка­же­ни­ем ко­до­во­го слова u1 и ис­ка­же­ни­ем ко­до­во­го слова u2 (в обоих слу­ча­ях  — не более чем в одном бите), то код бы не ис­прав­лял одну ошиб­ку  — По­лу­ча­тель может по­лу­чить слово w, но в этом слу­чае не может по­нять, по­сы­ла­ли ему u1 или u2. Итак, все 16 \times 2 в сте­пе­ни левая круг­лая скоб­ка 11 пра­вая круг­лая скоб­ка слов раз­ные, но это озна­ча­ет что во­об­ще любое из слов длины 15 по­лу­ча­ет­ся ис­ка­же­ни­ем ка­ко­го-то из ко­до­вых слов не более чем в одном бите.

На этом и по­стро­им стра­те­гию Фо­кус­ни­ка и Ас­си­стен­та. Ас­си­стент видит на­пи­сан­ное зри­те­лем 60-бит­ное слово, режет его на че­ты­ре 15-бит­ных слова w1, w2, w3, w4. Как до­ка­за­но выше, для них най­дут­ся ко­до­вые слова u1, u2, u3, u4, такие что wi от­ли­ча­ет­ся от ui не более чем в одном сим­во­ле. Тогда Ас­си­стент вы­бра­сы­ва­ет из каж­до­го ко­до­во­го слова кон­троль­ные сим­во­лы, по­лу­ча­ет че­ты­ре слова длины 11, то есть одно слово длины 44. Его он и пе­ре­да­ет Фо­кус­ни­ку. Фо­кус­ник вос­ста­нав­ли­ва­ет кон­троль­ные суммы, по­лу­ча­ет слово u1u2u3u4 от­ли­ча­ю­ще­е­ся от ис­ход­но­го мак­си­мум в че­ты­рех битах  — по­бе­да.

 

Ответ: C=56.

Спрятать критерии
Критерии проверки:

A: эти кри­те­рии оце­ни­ва­ют про­гресс в до­ка­за­тель­стве оцен­ки C мень­ше или равно 56.

А0 Голый ответ −. и 0 бал­лов. До­ка­за­тель­ство, что C мень­ше 60: также 0 бал­лов.

A7 По­лу­че­но клю­че­вое утвер­жде­ние, что если можно оши­бить­ся не более k раз (т. е. C= 60 минус k пра­вая круг­лая скоб­ка то

 левая круг­лая скоб­ка \beginarrayc60 0\endarray пра­вая круг­лая скоб­ка плюс левая круг­лая скоб­ка \beginarrayc60 1\endarray пра­вая круг­лая скоб­ка плюс умно­жить на s плюс левая круг­лая скоб­ка \beginarrayc60 k\endarray пра­вая круг­лая скоб­ка боль­ше или равно 2 в сте­пе­ни левая круг­лая скоб­ка 16 пра­вая круг­лая скоб­ка ,

но не ука­за­но пра­виль­ное зна­че­ние k, для ко­то­ро­го не­ра­вен­ство ста­но­вит­ся вер­ным: ± и 18 бал­лов.

А9 Кор­рект­но до­ка­зан­ная оцен­ка 干 и 20 бал­лов.

Баллы за раз­ные ли­те­ры скла­ды­ва­ют­ся

В0 По­стро­е­ни любых ал­го­рит­мов, до­ка­зы­ва­ю­щих C боль­ше или равно 52: 0 бал­лов.

В3 Мечты в духе «нас бы устро­ил Хэмин­гов­ский код с та­ки­ми-то свой­ства­ми», если тре­бу­ет­ся ис­прав­лять боль­ше одной ошиб­ки, и нет со­об­ра­же­ний, как его стро­ить — 10 бал­лов.

B8 При­мер чи­стый по мо­ду­лю су­ще­ство­ва­ния со­вер­шен­но­го кода Хэмин­га, ис­прав­ля­ю­ще­го одну ошиб­ку, ко­то­рое по­сту­ли­ро­ва­но но не до­ка­за­но — то же, что В9.

В9 При­мер 56 минус плюс / 2 и 30 бал­лов (таким об­ра­зом A9 + B9 дает пол­ную цену за­да­чи).