1

Н ауката е чудесен инструмент за иновации и подобряване на живота ни, но нека си признаем, че има някои неща, които сме усвоили до голяма степен. Не бихте очаквали, например, че можем да подобрим нещо като... като броенето.

(Във видеото може да научите повече за: Митко Христов - учител по математика от ново поколение)

Затова може да е изненада, че група учени са направили точно това: намерили са нов начин за решаване на проблем с десетилетна давност, който задава въпрос, който на пръв поглед изглежда много прост - колко различни неща има пред мен?

Това е по-труден проблем - и по-умно решение - отколкото си мислите.

Проблемът за отчетливите елементи

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

Понякога най-много проблеми създават нещата, които изглеждат почти смешно прости за човека. Вземете например броенето - по-конкретно броенето на отделни обекти. За нас това е лесно: гледаме колекцията от обекти и мозъкът ни просто автоматично ги подрежда в групи вместо нас. Почти не ни се налага да работим върху това.

За компютрите, от друга страна, това е фундаментален проблем с десетилетна давност. И той наистина се нуждае от отговор, тъй като приложенията му в съвременния свят обхващат всичко - от анализ на мрежовия трафик - представете си Facebook или Twitter, които следят колко хора са влезли в даден момент - до откриване на измами, биоинформатика, анализ на текст и много други.

Очевидно е, че от известно време насам можем да правим тези неща и това е така, защото този въпрос за преброяването - правилно известен като Проблемът за отчетливите елементи - наистина има отговори. Те просто не са много добри. 

"Всички по-рано известни алгоритми бяха "базирани на хеширане" и качеството на този алгоритъм зависеше от качеството на хеширащите функции, които този алгоритъм избира", обясни Винодчандран Вариям, професор в Училището по информатика към Университета Небраска-Линкълн, в изявление от миналата година. 

Заедно с колегите си Сурав Чакраборти от Индийския статистически институт и Кулдип Мил от Университета в Торонто той открива начин за значително опростяване на проблема: "Новият алгоритъм използва само стратегия за вземане на проби, а анализът на качеството може да се извърши с помощта на елементарни техники."

Как работи?

Новият метод, наречен CVM алгоритъм в чест на създателите си, драстично намалява нуждите от памет - важно предимство в съвременната ера на големите данни - и го прави с помощта на хитър трик от теорията на вероятностите. За да илюстрирате концепцията, разгледайте примера, изследван от Вариам и колегите му, както и неотдавнашната статия в Quanta Magazine: представете си, че броите броя на уникалните думи в "Хамлет" на Шекспир, но разполагате с достатъчно памет, за да съхраните само 100 думи едновременно. 

Първо, правите очевидното: записвате първите 100 уникални думи, на които сте попаднали. Сега мястото ви е изчерпано - затова вземате монета и я хвърляте за всяка дума. Орел - тя остава; опашка - забравяте я.

В края на този процес в списъка ви ще има около 50 уникални думи. Започвате отново процеса отпреди - но този път, ако попаднете на дума, която вече е в списъка, отново хвърляте монетата, за да видите дали да я изтриете. След като достигнете 100 думи, отново преминавате през списъка, като хвърляте монета за всяка дума и я изтривате или запазвате според указанията.

Във втория рунд нещата са малко по-сложни: вместо една глава, за да запазите дума в списъка, са необходими две поредни - всичко останало се изтрива. По същия начин в третия кръг ще трябва да получите три поредни глави, за да остане; в четвъртия кръг ще са необходими четири поредни глави и така нататък, докато стигнете до края на "Хамлет".

В тази лудост има метод - и то интелигентен. Като сте преминали през текста по този начин, сте се уверили, че всяка дума в списъка ви има еднаква вероятност да присъства: 1/2k, където k е броят на пътищата, които трябваше да преминете през списъка. Така че, да кажем, че са ви били необходими шест кръга, за да стигнете до края на "Хамлет", и сте останали със списък от 61 отделни думи: след това можете да умножите 61 по 26, за да получите приблизителна оценка на броя на думите.
 
Ще ви спестим отварянето на приложението ви за калкулатор: отговорът е 3 904 - а според Вариам и ко действителният отговор е 3 967 (да, те пресметнаха.) Ако имате памет, която може да съхранява повече от 100 думи, точността се повишава още повече: при възможност за съхраняване на 1 000 думи алгоритъмът оценява отговора като 3 964 - вече едва ли има грешка при закръгляването - и "разбира се", казва Вариам, "ако паметта е толкова голяма, че да побере всички думи, тогава можем да получим 100-процентова точност".

Прост подход

Той е ефективен, но това, което прави алгоритъма още по-интригуващ, е неговата простота.

"Новият алгоритъм е изумително прост и лесен за изпълнение", казва пред Quanta Андрю Макгрегър, професор в Колежа по информационни и компютърни науки в Масачузетския университет в Амхърст.

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

Това означава, че макар статията, в която подробно е описан алгоритъмът, да не е била рецензирана в официалния смисъл на думата, тя определено е била рецензирана от колеги. Всъщност Доналд Кнут, автор на "Изкуството на компютърното програмиране" и така нареченият "баща на анализа на алгоритми", пише статия, в която възхвалява алгоритъма през май 2023 г.

Междувременно различни екипи - включително Чакраборти, Вариям и Мил - прекараха последната година в проучване и усъвършенстване на алгоритъма. Някои от тях, казва Вариам, вече го преподават в своите курсове по информатика.

"Смятаме, че това ще бъде основен алгоритъм, който ще се преподава в първия курс по информатика за алгоритми като цяло и вероятностен алгоритъм в частност", каза той.

Кнут е съгласен: "Той е чудесно пригоден за преподаване на ученици, които изучават основите на информатиката. Почти съм сигурен, че нещо подобно в крайна сметка ще се превърне в стандартна тема за учебник".

И така, как един толкова революционен алгоритъм е останал незабелязан толкова дълго време? Според Вариам това не е толкова невероятно, колкото звучи.

"Учудващо е, че този прост алгоритъм не е бил открит по-рано. В науката не е необичайно простотата да бъде пропусната в продължение на няколко години", казва той.

Не пропускайте най-важните новини - последвайте ни в Google News Showcase

Коментари 1
Кирилица:
Фонетична
Имате 2000 позволени символа

* Моля, коментирайте конкретната статия и използвайте кирилица! Не се толерират мнения с обидно или нецензурно съдържание, на верска или етническа основа, както и написани само с главни букви!

1 коментар
 
Баба ми казваше: Най-страшната безработица е кога не ти работи главата.  
Прочети целия
Обратно в сайта X

ДОСТЪП ЗА ЛОГНАТИ ПОТРЕБИТЕЛИ За да пишете, оценявате или докладвате коментари, моля логнете се в профила си.

  1. Запомни ме
забравена парола Полетата маркирани с * са задължителни
Полето Потребителско име не трябва да е празно.
Полето E-mail не трябва да е празно.
Полето Парола не трябва да е празно.
Полето Повторете паролата не трябва да е празно.
  1. Декларирам, че съм се запознал с Общите условия за ползване на услугите на Нетинфо.
Полетата маркирани с * са задължителни

Последни

<p>&quot;Война на световете&quot;: Запис на НАСА предизвика паника</p>

"Война на световете": По погрешка пуснат запис на НАСА предизвика паника

Свят Преди 8 минути

„На борда на Международната космическа станция няма извънредна ситуация“, се казва в акаунта на МКС

с

Max Chef 3-в-1 еър фраер с грил и тенджера – Вашето решение за по-здравословно, лесно и приятно готвене!

Любопитно Преди 9 минути

Представяме Ви най-компактния и универсален уред в кухнята Ви

<p>Известен певец се оплака, че са му сложили усмирителна риза в болница</p>

Музикант се оплака, че са го помислили за луд, след като не повярвали, че е известен певец

Любопитно Преди 55 минути

Александър Морис е настоящият вокалист на легендарната група Four Tops

Старт на втория етап на съвместните учения между Русия и Беларус за ядрени удари

Старт на втория етап на съвместните учения между Русия и Беларус за ядрени удари

Свят Преди 1 час

Ученията са насочени към подготовка на войски и техника „за безусловно гарантиране на суверенитета и териториалната цялост на Съюзната държава“

ЦИК обявява окончателните резултати от вота за НС

ЦИК обявява окончателните резултати от вота за НС

Избори 2 в 1 Преди 1 час

На 16 юни ще станат ясни и имената на новоизбраните 240 депутати в българския парламент

След гръмотевичната буря: Спасиха сърничка в Шумен

След гръмотевичната буря: Спасиха сърничка в Шумен

България Преди 1 час

Животното е предадено на горските служители

Достъпът до педиатри се превръща в битка: Решим ли е проблемът

Достъпът до педиатри се превръща в битка: Решим ли е проблемът

България Преди 1 час

Детските болести да са по-широко застъпени в специализацията по обща медицина, призова д-р Киров

НАТО ще подкрепи мисията за обучение за Украйна

НАТО ще подкрепи мисията за обучение за Украйна

Свят Преди 2 часа

Между съюзници се водят разговори и за сключване на споразумение за дългосрочна финансова помощ за Украйна

Нов вариант на COVID-19: Какво трябва да знаем за KP.3

Нов вариант на COVID-19: Какво трябва да знаем за KP.3

Свят Преди 2 часа

KP.2 все още следва второ място, представлявайки 22,5 % от случаите

<p>Огнен ад в Гърция: Пожар в близост до резервоари с пропан (СНИМКИ)&nbsp;</p>

Огнен ад в Гърция: Пожар в близост до резервоари с пропан

Свят Преди 2 часа

Изпратени са 40 огнеборци с 16 противопожарни коли

Локомотив София остана без основния спонсор

Локомотив София остана без основния спонсор

България Преди 2 часа

Собственикът на Локомотив София - Иван Василев, потвърди новината

Земетресение разтърси Мармарис

Земетресение разтърси Мармарис

Свят Преди 2 часа

Епицентърът му е бил в морето, на дълбочина 44,4 километра

<p>Еврокомисар очаква да паднат сухопътните шенгенски граници на страната ни, ето кога&nbsp;</p>

Еврокомисар очаква през 2024 г. да паднат сухопътните шенгенски граници на страната ни

Свят Преди 2 часа

Еврокомисар Илва Йохансон очаква тази година да паднат сухопътните шенгенски граници на България и Румъния

<p>&quot;Путин е наистина бесен&quot;</p>

Киев: Путин е „бесен“ заради удара по най-модерния руски самолет

Свят Преди 2 часа

Андрий Юсов, говорител на Главното разузнавателно управление на Украйна, направи тази оценка по националната телевизия

<p>Microsoft със сериозно предупреждение</p>

Microsoft със сериозно предупреждение: Руските кибератаки стават все по-агресивни

Свят Преди 2 часа

Президентът на технологичния гигант обрисува тежка картина на сегашното киберпространство