Н ауката е чудесен инструмент за иновации и подобряване на живота ни, но нека си признаем, че има някои неща, които сме усвоили до голяма степен. Не бихте очаквали, например, че можем да подобрим нещо като... като броенето.
(Във видеото може да научите повече за: Митко Христов - учител по математика от ново поколение)
Затова може да е изненада, че група учени са направили точно това: намерили са нов начин за решаване на проблем с десетилетна давност, който задава въпрос, който на пръв поглед изглежда много прост - колко различни неща има пред мен?
Това е по-труден проблем - и по-умно решение - отколкото си мислите.
Проблемът за отчетливите елементи
Компютрите могат да бъдат много интелигентни, но могат да бъдат и много, много... неинтелигентни. Доказателство за това е неотдавнашният бум на чатботовете с изкуствен интелект: те са страхотни в това да звучат интелигентно, но ако ги подложите на изпитание, може да се окажете в блато от глупости.
Понякога най-много проблеми създават нещата, които изглеждат почти смешно прости за човека. Вземете например броенето - по-конкретно броенето на отделни обекти. За нас това е лесно: гледаме колекцията от обекти и мозъкът ни просто автоматично ги подрежда в групи вместо нас. Почти не ни се налага да работим върху това.
За компютрите, от друга страна, това е фундаментален проблем с десетилетна давност. И той наистина се нуждае от отговор, тъй като приложенията му в съвременния свят обхващат всичко - от анализ на мрежовия трафик - представете си Facebook или Twitter, които следят колко хора са влезли в даден момент - до откриване на измами, биоинформатика, анализ на текст и много други.
Очевидно е, че от известно време насам можем да правим тези неща и това е така, защото този въпрос за преброяването - правилно известен като Проблемът за отчетливите елементи - наистина има отговори. Те просто не са много добри.
Computer Scientists Invent an Efficient New Way to Count: "By making use of randomness, a team has created a simple algorithm for estimating large numbers of distinct objects in a stream of data." via @QuantaMagazine https://t.co/WUCmyIXt6x pic.twitter.com/yYRtGFqWNw
— RealClearScience (@RCScience) May 17, 2024
"Всички по-рано известни алгоритми бяха "базирани на хеширане" и качеството на този алгоритъм зависеше от качеството на хеширащите функции, които този алгоритъм избира", обясни Винодчандран Вариям, професор в Училището по информатика към Университета Небраска-Линкълн, в изявление от миналата година.
Заедно с колегите си Сурав Чакраборти от Индийския статистически институт и Кулдип Мил от Университета в Торонто той открива начин за значително опростяване на проблема: "Новият алгоритъм използва само стратегия за вземане на проби, а анализът на качеството може да се извърши с помощта на елементарни техники."
Как работи?
Новият метод, наречен CVM алгоритъм в чест на създателите си, драстично намалява нуждите от памет - важно предимство в съвременната ера на големите данни - и го прави с помощта на хитър трик от теорията на вероятностите. За да илюстрирате концепцията, разгледайте примера, изследван от Вариам и колегите му, както и неотдавнашната статия в Quanta Magazine: представете си, че броите броя на уникалните думи в "Хамлет" на Шекспир, но разполагате с достатъчно памет, за да съхраните само 100 думи едновременно.
Първо, правите очевидното: записвате първите 100 уникални думи, на които сте попаднали. Сега мястото ви е изчерпано - затова вземате монета и я хвърляте за всяка дума. Орел - тя остава; опашка - забравяте я.
В края на този процес в списъка ви ще има около 50 уникални думи. Започвате отново процеса отпреди - но този път, ако попаднете на дума, която вече е в списъка, отново хвърляте монетата, за да видите дали да я изтриете. След като достигнете 100 думи, отново преминавате през списъка, като хвърляте монета за всяка дума и я изтривате или запазвате според указанията.
Във втория рунд нещата са малко по-сложни: вместо една глава, за да запазите дума в списъка, са необходими две поредни - всичко останало се изтрива. По същия начин в третия кръг ще трябва да получите три поредни глави, за да остане; в четвъртия кръг ще са необходими четири поредни глави и така нататък, докато стигнете до края на "Хамлет".
Прост подход
Той е ефективен, но това, което прави алгоритъма още по-интригуващ, е неговата простота.
"Новият алгоритъм е изумително прост и лесен за изпълнение", казва пред Quanta Андрю Макгрегър, професор в Колежа по информационни и компютърни науки в Масачузетския университет в Амхърст.
Действително, след публикуването му през януари 2023 г. - и като изключим няколко дребни забележки и грешки междувременно - алгоритъмът привлече вниманието и възхищението на много други компютърни учени.
Това означава, че макар статията, в която подробно е описан алгоритъмът, да не е била рецензирана в официалния смисъл на думата, тя определено е била рецензирана от колеги. Всъщност Доналд Кнут, автор на "Изкуството на компютърното програмиране" и така нареченият "баща на анализа на алгоритми", пише статия, в която възхвалява алгоритъма през май 2023 г.
Междувременно различни екипи - включително Чакраборти, Вариям и Мил - прекараха последната година в проучване и усъвършенстване на алгоритъма. Някои от тях, казва Вариам, вече го преподават в своите курсове по информатика.
"Смятаме, че това ще бъде основен алгоритъм, който ще се преподава в първия курс по информатика за алгоритми като цяло и вероятностен алгоритъм в частност", каза той.
Кнут е съгласен: "Той е чудесно пригоден за преподаване на ученици, които изучават основите на информатиката. Почти съм сигурен, че нещо подобно в крайна сметка ще се превърне в стандартна тема за учебник".
И така, как един толкова революционен алгоритъм е останал незабелязан толкова дълго време? Според Вариам това не е толкова невероятно, колкото звучи.
"Учудващо е, че този прост алгоритъм не е бил открит по-рано. В науката не е необичайно простотата да бъде пропусната в продължение на няколко години", казва той.
Не пропускайте най-важните новини - последвайте ни в Google News Showcase
