Представяме ви откъс от новата книга на Джеймс Стоун (James V. Stones) "Теория на информацията: Ръководство. Въведение" (Information Theory: A Tutorial Introduction).
Всички сме запознати с мерните единици: минутата е единица за време, метърът е единица за дължина, а битът е единица за информация. Но какво имаме предвид под "единица за информация"?
Определяне на маршрута, бит след бит
Битът е количеството информация, от която се нуждаем за да изберем между две еднакво вероятни алтернативи. Представете си, че стоите на кръстопът в точка А на фигурата по-долу и искате да стигнете до точката, отбелязана с D. Тази илюстрация е изглед от птичи поглед, но на място не разполагате с него - когато трябва да вземете решение, имате пред себе си само разклонение. Ако нямате предварителна информация кой път да изберете след разклона при А, пред вас са две еднакво вероятни алтернативи. Ако ви кажа, да отидете наляво, вие сте получили един бит информация. Ако представим инструкцията с двоични числа (0 = ляво и 1 = дясно), тогава двоичното число ви предостави един бит информация, която ще ви каже кой път да изберете.
Всъщност, двоичните числа, нулите и единиците, може да се използват за представяне на целия път от точка А до D. Представете си, че се разхождате по-нататък по пътя и стигате друго разклонение, в точка B на фигурата. Отново, защото нямате представа кой път да избере, двоичното число (1 = дясно) ще ви осигури един бит информация и ще ви даде възможност да изберете правилния път, който води към точката маркирана с C.
 Един бит информация съответства на избор между две еднакво вероятни алтернативи. |
Имайте предвид, че C е една от четирите възможни междинни цели, които бихте могли да достигнете след като сте взели две решения. Двете двоични числа, които ви позволяват да вземете правилни решения, са два бита информация, която ви позволява да изберете от четири (еднакво вероятни) възможни алтернативи:
4 възможности са равни на 2 х 2 = 2 2
Третото двоично число (1 = дясно) ви предоставя още един бит информация, която ви позволява да отново да избере правилния път, водещ до точката, отбелязана с D.
Сега имате осем маршрута, между които сте могли да избирате, започвайки в A, така че три двоични числа (които ви осигуряват три бита информация) ви позволяват да изберете от осем еднакво вероятни алтернативи;
8 възможности са равни на 2 х 2 х 2 = 2 3
Имайте предвид, че решението, взето ва A изключва половината от осемте възможни дестинации, показани на фигурата, по пътя към D. По същия начин, решението, взето на всяко следващо разклонение на пътя, елиминира половината от броя на оставащите възможни дестинации.
Едно пътуване от осем алтернативи
Можем да представим това в по-обща формула, ако използваме п да представя броя на разклоненията, а m - броя на крайните дестинации. Ако сте преминали през п разклонения, тогава ще трябва сте избирали от
m = 2 n крайни дестинации.
Тъй като решението на всяко разклонение изисква по един бит информация, п разклонения изискват п бита информация, които ви позволяват да избирате от 2 n еднакво вероятни алтернативи.
Бихме могли да обозначим всяка от осемте възможни дестинации с десетични числа между 0 и 7, или с еквивалентно двоично число, както е на фигурата по-долу. Тези десетични числа и техните еквивалентни двоични представяния са показани в таблицата. Броенето с двоични числа е аналогично на броене с десетични.
Двоичното представяне на числата има много предимства. Например, двоичното число, обозначаващо всяка дестинация (в случая: 011) представя набор от инструкции ляво/дясно, необходими за достигане на това място. Това представяне може да се прилага за всеки проблем, който е свързан с вземане на редица двуалтернативни (т.е. двоични) решения.
Пътешествието на log2(8) решения
Сложността на всяко пътуване, може да бъде представена или като броят на възможните крайни дестинации или като броят на разклоненията по пътя, които трябва да бъдат преминати, за да се достигне до дадена дестинация. Знаем, че ако броят на разклонения се увеличава, броят на възможните дестинации също се увеличава. Както вече видяхме, ако имаме три разклонения тогава ще получим 8 = 23 възможни дестинации.
 Логаритъмът измерва броя на решенията. |
Погледнато от друга гледна точка, ако имаме m = 8 възможни дестинации, тогава колко разклонения п трябва да имаме? С други думи, като има 8 дестинации, на каква степен трябва да се повдигне 2, за да се получим 8 ? В този случай, знаем, че отговорът е п = 3, което се нарича логаритъм от 8 с основа 2. По този начин, 3 = log2(8) е броят на разклоненията, по които се стига до 8 дестинации.
По-общо казано, логаритъм при основа 2 от m е степента, на която трябва да се повдигне 2, за да се получи m; тоест, m = 2 п. Еквивалентно, получаваме п от числото m, като го изразим с логаритъм,
п = log2m
Сега, когато знаем за логаритмите, можем да обобщим пътуването си от една друга гледна точка, от гледната точка на бита:
Ако трябва да избираме между m еднакво вероятни алтернативи, тогава ни трябват п = log2m бита информация.
Един милион отговора на двадесет въпроса
Придвижването през поредицата разклонения на пътя, в някои отношения, е подобно на играта на 20 въпроса. В тази игра опонентът ви си избира една дума (обикновено съществително), а на вас ви е позволено да му зададете 20 въпроса, за да откриете тази дума. От голямо значение е всеки въпрос да има само да / не (т.е. двоичен) отговор и така отговорът ще ви даде най-много един бит информация.
Защо най-много? По аналогия с примера за навигацията, където всяко решение при разклона елиминира половината от броя на останалите дестинации, всеки въпрос трябва да намали наполовина броят на оставащите възможни думи. Въпрос, на който вече знаете отговора е лош избор на въпрос. Например, ако вашият въпрос е, "има ли я думата в речника?", То отговорът е почти сигурно, "Да!", Отговор, който е предвидим, не ви предоставя никаква информация.
От друга страна, добре подбраният въпрос е този, за който нямате никаква представа дали отговорът ще бъде положителен или не и има 50:50 шанс да е едно от двете. В този случай, отговорът осигурява точно един бит информация. Съкратената версия на играта на 20 въпроса на фигурата по-долу показва това по-ясно.
В тази игра, опонентът ви има речник от точно осем думи и знаете кои са тези думи. Вашият първи въпрос (Q1) би могло да бъде, "Неодушевен предмет ли е?", А отговорът трябва да намали наполовина броят на възможните думи до четири, което да доведе до втория ви въпрос (Q2). Ако втория ви въпрос (Q2) е: "Дали е бозайник?", То отговорът трябва отново намали наполовина броя на възможните думи, което води до третия въпрос (Q3). Когато се стигне до Q3, има само две останали възможни думи, а след като сте стигнали до тук може да попитате : ""Котка" ли е?". Отговорите на опонента да /не ви водят към правилния отговор. Като обобщение, вие имате нужда от три въпроса, за да изключва всички, без една от осемте възможни думи.
Нека приемем, че опонентът ви има същия речник, както и вие (повечето от нас имат един и същ реников запас от думи, така че това предположение не е напълно неоснователно). По-конкретно, нека приемем този речник съдържа точно 1,048,576 думи. Въоръжени с това знание, всеки въпрос може по принцип да бъде избран за да намали наполовина броя на оставащите възможни думи. Така че, в един идеален свят, първият ви въпрос трябва да намали наполовина броят на възможните думи до 524,288. Следващата ви въпрос трябва да ги намали наполовина до 262 144 думи и т. н.. Когато стигнете до 19-ти въпрос ще само две думи, а след 20-тия въпрос, трябва да остане само една дума.
Причината това да работи толкова спретнато е, защото 20-те въпроса ви позволяват да избирате точно от 1 048 576 = 2 20 еднакво вероятни думи (т.е. около един милион). По този начин, 20 бита информация, която сте придобили с вашите въпроси ви предоставя възможността да се стесни обхватът на възможните думи от около 1 милион до само една. С други думи, 20 въпроса ви позволяват да намерите правилната дума от около един милион възможни думи. Изчислено е, че средният човек има речник от по-малко от 20 000 думи, така двадесет добре подбрани въпроси трябва да са достатъчни, за да спечелите играта.
С добавянето на още един въпрос не само ще създадете нова игра, 21 въпроса , но това също така ще удвои броя на възможните думи (до около 2 милиона), които можете да ограничите до една. Чрез разширяване, всеки допълнителен въпрос позволява да получите още един бит информация, и следователно може да се удвои първоначалния брой думи. По принцип, една игра на 40 въпроса ви позволява да получите 40 бита информация, която ви позволява да намерите една от около 
думи.
По отношение на примера за навигация, 40 бита ще ви позволят да преминете през 40 разклонения на пътя,и следователно ще ви позволят да избере едно от около един трилион възможни маршрути. Така че следващия път, когато стигнете до вашата дестинация, след пътуване с 40 възможни избора, не забравяйте, че сте избегнали един трилион минус една неправилни дестинации.
Информация, бит и двоични числа
 Claude ShannonКлод Шанън, бащата на теорията на информацията. |
Независимо от факта, че думата "бит" произлиза от "двоична цифра"(binary digit), между тях има тънка, но жизненоважна, разлика. Бинарното число е стойността на двоичната променлива, където тази стойност може да бъде 0 или 1, но двоичното число не е информация само по себе си. За разлика от битът, който е определено количество информация. Битът и двоичното число са различни по същността си и да обърква едното с другото е известно като грешка на категориите.
За да илюстрирам това, обърнете внимание на следните два екстремни примери. В едната крайност, ако вече знаете, че трябва да тръгнете по пътя вляво от точка А и аз ви покажа двоичната цифра 0 (= ляво), вие сте видяли двоичното число, но не сте придобили никаква информация. В другата крайност, ако нямате представа кой път да избере и аз ви покажа 0, след като сте видяли двоичното число, вие сте придобили един бит информация. Между тези крайности, ако някой ви каже, има 71% вероятност, че пътят от лявата страна представлява правилното решение и впоследствие потвърдя това като ви покажа 0, това 0 ви предоставя по-малко от един бит информация (защото вече имахте някаква информация кой път да изберете).
За съжаление, в съвременното използване, термините бит и двоично число са се превърнали в синоними. Според Дейвид Маккей единицата за информация би следвало да се нарече Шанън, на името на Клод Шанън, бащата на теорията на информацията. Можете да разберете повече за него и работата му тук.
За автора:
Джеймс Стоун (James V. Stones) преподава Компютърни науки в университета в Шефилд, Англия. Тази статия е адаптирана от наскоро публикуваната му книга "Теория на информацията: Ръководство. Въведение".
Коментари
Моля, регистрирайте се от TУК!
Ако вече имате регистрация, натиснете ТУК!
Няма коментари към тази новина !
Последни коментари