Задача 3 от брой 12/2003 - МАЛКИЯТ ПРИНЦ - Анализ

Задача трета от нашия Конкурс е пълна противоположност на втора задача. При нея математическият модел е съвършено ясен, а възможностите за алгоритмично решаване са практически сведени до едно. Но да започнем с малък математически увод.

За математическото моделиране на задачи от живота най-често си служим с алгебрата на реалните числа с операциите събиране и умножение, както и съответните им обратни – изваждане и деление. В математиката подобна алгебра се нарича поле. Няма да се спираме на формалната дефиниция (аксиоматика) на поле, защото полето на реалните числа е достатъчно добре познато на читателите, а всяко друго поле има същите свойства. Разбира се полето на реалните числа не е единствената алгебра от подобен род. Някои читатели навярно познават и полето на комплексните числа. За решаването на задачата ще използваме поле, дефиниционното множество на което се състои само от 2 елемента – 0 и 1. Полетата с крайно много елементи са въведени и изследвани от твърде рано загиналия велик френски математик Еварист Галуа. В негова чест, крайното поле с q елемента (Галуа е показал, че то съществува за всяко q, което е степен на просто число и по същество е единствено) наричаме поле на Галуа с q елемента и означаваме с GF(q).

И така да разгледаме полето GF(2). В таблиците дадени по-долу са дефинирани двете операции на полето – събирането, наричано събиране по модул 2 и означавано със знака Å и умножението, което практически не се различава от умножението в полето на реалните числа и затова няма да използваме специален знак за него:

Това, което е характерно за полето с два елемента е, че по същество няма операция изваждане, или по-точно изваждането съвпада със събирането. Действително, разликата на две стойности a и b от това поле трябва да е стойността x такава, че a=xÅb. С елементарна проверка по таблицата може да се види че x=a Åb. Тъй като делението на нула във всяко поле е невъзможно, то в полето GF(2) остава само една възможност – деление на 1, което е елементарно, защото резултатът е равен на делимото. И така аритметиката на полето GF(2) е твърде проста.

Да представим условието на задачата в полето с два елемента. Да означим с a_ij Î{0,1} ролята на ключа с номер j за управлението на звездата с номер i, i=1,2,…,N,  j=1,2,…,K. Когато ключът с номер j може да променя състоянието на звездата с номер i, тогава  a_ij =1, в противен случай - a_ij =0. За да упростим малко нещата, нека си мислим, че в началото всички звезди са загасени, а със стойностите b_iÎ{0,1}, i=1,2,…,N, сме означили исканото състояние на звездите. Когато звездата с номер i трябва да свети, тогава  b_i =1, в противен случай – b_i =0.

Съществено за решаването на задачата е твърдението, че ако исканото състояние може да се постигне изобщо, то може да се постигне с не повече от 1 щракване на всеки един от ключовете. Очевидно е, че всяко второ щракване на ключ неутрализира въздействието на предишното щракване върху състоянието на звездите, на които ключът може да влияе. Затова всъщност е важно за всеки ключ да определим дали трябва да бъде щракнат, за да се получи исканата ситуация. Да означим с x_i Î{0,1}, j=1,2,…,K, дали ключът с номер j e щракнат. Когато е щракнат, тогава  x_i =1, в противен случай – x_i =0.

Сега условието на задачата може да представим със следния математически модел. Да се намерят стойностите на променливите x_i, ако съществуват такива, че да е удовлетворена следната система линейни уравнения в полето GF(2):

a₁₁ x₁ Å a₁₂ x₂ Å… Å a_1K x_K = b₁

a₂₁ x₁ Å a₂₂ x₂ Å… Å a_2K x_K = b₂

.....

a_N1 x₁ Å a_N2 x₂ Å… Å a_NK x_K = b_K

Теорията на системите линейни уравнения е добре известна и няма да се спираме подробно на нея в този коментар. Да отбележим само, че всяка известна техника за решаване на системи линейни уравнения работи еднакво добре във всяко поле, включително и в полето GF(2), така че всеки от известните алгоритми може да бъде приложен. В резултат на решаването може да се окаже, че системата няма решение и програмата трябва да изведе съответен резултат  (–1 в нашия случай). Може да се намери единствено решение или пък да се окаже, че системата е недоопределена и има много решения и тогава трябва да бъде избрано кое да е решение.

Това, с което полето GF(2) се отличава съществено от останалите полета при компютърни пресмятания е, че компютрите разполагат с мощно средство за работа в това поле – побитовата операция събиране по модул 2 (популярна като XOR или изключващо или). Така при побитово представяне на матрицата на системата, елиминирането на променливи (алгоритъм на Гаус или модификацията наричана алгоритъм на Гаус-Жордан) вместо да прави C.(K+1) обчайни операции за елиминиране на една от променливите в едно от уравненията, ще изисква é(K+1) / R ù  събирания по модул 2, където R е броят на битовете в използвания за побитовото представяне тип, което ще доведе до значително ускоряване на алгоритъма.

Остава да видим как да се справим с факта, че в условието е зададено начално състояние на звездите  z₁, z₂ ,…, z_N, различно от разгледаното (т.е в началото не всички звезди са угасени, а някои звезди вече светят, а други не). Ако читателят е вникнал в особеностите на полето GF(2) лесно ще съобрази, че в този случай вместо стойностите b₁, b₂ ,…, b_N в десните части на уравненията на системата трябва да се вземат сойностите  z₁Å b₁, z₂Å b₂, …, z_NÅb_N.

Както трябваше да се очаква голям брой от участниците успяха да се справят със задачата и да заслужат пълния брой точки. Най-бързо беше решението на Камен Добрев, затова той е победител в този кръг на Конкурса. Камен не за пръв път се откроява с бързина на кода и това се дължи не само на качествения алгоритъм, но и на вниманието, което отделя на останалите подробности. Например отказ от готови имплементации на класически абстрактни типове, като в собствените имплементации успява да използва особености на задачата или пък много внимателно подхожда към четенето на огромните понякога обеми от входни данни.

За въпроси можете да ни пишете на адрес: konkurs@musala.com.

Supported by Musala Soft Ltd.

Copyright 2000-2010 by Musala Soft Ltd. All rights reserved.