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

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

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

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

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

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

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

За компютрите, от друга страна, това е фундаментален проблем с десетилетна давност. И той наистина се нуждае от отговор, тъй като приложенията му в съвременния свят обхващат всичко - от анализ на мрежовия трафик - представете си 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

Обратно в сайта X

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

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

Силна буря удари Кюстендил

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

Има пожари в землищата на селата Ябълково, Коняво и Горно Уйно

Кратер погълна магистрала в Норвегия, изчезна човек

Кратер погълна магистрала в Норвегия, изчезна човек

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

Причината за бедствието все още не е ясна

Израел уби премиера на хутите в Йемен

Израел уби премиера на хутите в Йемен

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

Други членове на правителството също бяха убити

Съдът остави в ареста служителя на ЦГМ, задържан за побой

Съдът остави в ареста служителя на ЦГМ, задържан за побой

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

Според съда има опасност от извършване на ново престъпление.

Голям пожар гори до село Бодрово

Голям пожар гори до село Бодрово

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

На място има няколко пожарни автомобила

Украински дрон запали пожар до двореца на Путин

Украински дрон запали пожар до двореца на Путин

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

Официално руският президент отрича да има нещо общо с имота

Мерц: Германия вече е в конфликт с Русия

Мерц: Германия вече е в конфликт с Русия

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

Мерц: Путин вече не спазва никакви международни споразумения

Червеният кръст: Евакуацията на Газа би била опасна

Червеният кръст: Евакуацията на Газа би била опасна

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

Израел продължава да следва плана си да поеме пълен контрол над цялата ивица Газа

Повод за гордост! България със сребро на Европейското по баскетбол за момичета

Повод за гордост! България със сребро на Европейското по баскетбол за момичета

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

С успеха българите взеха реванш за драматичната загуба от Япония с 2:3 гейма в предварителната група

Радев: Доверието в институциите е критично ниско, хората търсят алтернатива

Радев: Доверието в институциите е критично ниско, хората търсят алтернатива

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

Държавният глава коментира темите по време на откриването на младежка олимпиада по информатика в Шумен

Ким Чен-ун се срещна със семейства на загинали в Украйна войници

Ким Чен-ун се срещна със семейства на загинали в Украйна войници

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

Предстои Ким да посети Китай, където ще присъства на парад заедно с руския президент Путин

Автомобил се вряза в тълпа във Франция, има жертва

Автомобил се вряза в тълпа във Франция, има жертва

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

Инцидентът е станал в град Еврьо в северния френски регион Нормандия

<p>Даниил: Ако загуби човек духовната свобода, не може да опази и политическата свобода</p>

Патриарх Даниил: Ако загуби човек духовната свобода, не може да опази и политическата свобода

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

Днес Българската православна църква чества празника за пренасяне на мощите на св. Александър Невски

<p>Убит е бившият председател на украинския парламент Андрий Парубий</p>

Зеленски: Убит е бившият председател на украинския парламент Андрий Парубий

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

За момента не се съобщават повече подробности

Иран арестува 8 шпиони на Мосад, готвели удари по обекти

Иран арестува 8 шпиони на Мосад, готвели удари по обекти

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

Задържаните са обвинени, че са предоставили информацията на Мосад по време на въздушната война на Израел срещу Иран през юни

<p>Киселова: Правим първи бюджет в евро</p>

Наталия Киселова: Правим първи бюджет в евро

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

Приоритетите на правителството сега са плавно преминаване към еврото, каза тя