Какво е алгоритъм и защо това е една от най-важните идеи в науката | Д-р Атанас Илчев

📞 Онлайн уроци по математика за цялата страна◆ гл.ас. д-р Атанас Илчев◆ Индивидуални и групови уроци • Тел: 0883 375 433◆ Подготовка за НВО, ДЗИ, кандидатстудентски изпити◆ 📞 Онлайн уроци по математика за цялата страна◆ гл.ас. д-р Атанас Илчев◆ Индивидуални и групови уроци • Тел: 0883 375 433◆ Подготовка за НВО, ДЗИ, кандидатстудентски изпити◆

Математика & съвременен свят

Какво е алгоритъм и защо
това е една от най-важните идеи в науката

От рецептата за тесто до ChatGPT, от дългото деление в началното училище до алгоритмите, които сортират новинарската ви емисия във Facebook — алгоритмите са навсякъде около нас. Те са невидимата логика, която стои зад почти всичко, което правим с компютри, а самата дума произлиза от името на един персийски учен от IX век.

Автор: гл.ас. д-р Атанас Илчев Април 2026 Алгоритми История Изчислимост AI

Днес думата „алгоритъм" се е настанила в ежедневния ни речник. Чуваме я във връзка с Facebook, TikTok и YouTube, с изкуствения интелект и ChatGPT, с Google и дори с алгоритмите, които банките използват при одобряване на заеми. За някои звучи като невидима и малко заплашителна сила, която „решава" какво ще видим, какво ще купим и дори кого ще срещнем. Но зад тази модерна употреба се крие изненадващо просто понятие — и една от най-дълбоките идеи в цялата наука.

Алгоритъмът е крайна, точно описана последователност от стъпки за решаване на задача. Една детайлна готварска рецепта е алгоритъм. Инструкциите за сглобяване на мебел от IKEA — също (ако са написани добре). Дългото деление, което учите в четвърти клас, е алгоритъм. Ситото на Ератостен за намиране на прости числа е алгоритъм.

Но колкото и банално да звучи, именно тази идея промени хода на научната мисъл през XX век. Тя ни даде теоретичната рамка да разберем какво изобщо може да бъде изчислено, какво не може, и какво можем да изчисляваме ефективно. И, което е най-невероятното: без нея не биха съществували нито интернет, нито смартфоните, нито съвременната медицина, нито изкуственият интелект.

Името на един персиец

Всяка история има своето начало. Историята на думата „алгоритъм" започва около IX век в Багдад — по онова време един от най-големите центрове на знанието в света. Тук, под покровителството на халиф ал-Мамун, работи Мухаммад ибн Муса ал-Хорезми (около 780–850 г.). Неговата фамилия подсказва произхода му: от Хорезм, област на юг от Аралско море (днес между Узбекистан и Туркменистан).

Ал-Хорезми работи в известната Къща на мъдростта (Байт ал-хикма) — гигантски научно-образователен център, в който учени от всички краища на познатия свят превеждат и надграждат гръцки, индийски и персийски трактати. Около 820 г. ал-Хорезми вече е сред главните му математици и астрономи.

Двата негови най-влиятелни труда пренасят две думи през хилядолетие. Единият — Ал-Китаб ал-мухтасар фи хисаб ал-джабр уа-л-мукабала („Кратка книга за смятане чрез попълване и уравновесяване“) — описва систематични методи за решаване на линейни и квадратни уравнения. От думата ал-джабр идва съвременното алгебра.

Вторият трактат обяснява индо-арабските цифри и позиционния запис. Когато през XII век той е преведен на латински, името на ал-Хорезми се латинизира като Algoritmi или Algorismi. Оттам в европейските езици идва думата алгоритъм.

Две думи от едно име Ал-Хорезми е може би единственият човек в историята, от чиито трудове произлизат едновременно две от най-важните думи в математиката: алгебра (от заглавието на книгата) и алгоритъм (от латинизираното име на автора). Затова понякога го наричат „дядо на компютърните науки", макар да е живял повече от хиляда години преди първия компютър.

Какво е алгоритъм, всъщност?

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

Обърнете внимание на ключовите думи. Краен — не може да продължава вечно. Ясно дефинирани — всяка стъпка трябва да е недвусмислена. Стъпка по стъпка — инструкциите се изпълняват последователно. Води до решение — гарантира правилен резултат при валиден вход.

Една готварска рецепта почти покрива определението, но не точно. Когато казваме на човек „добавете две яйца”, всеки готвач разбира, че яйцата трябва да се счупят. Когато пишем алгоритъм за компютър, обаче, такова предположение не съществува. Компютърът няма опит, няма интуиция и няма „здрав разум” — той просто изпълнява инструкциите буквално, до последния символ. Затова един алгоритъм трябва да бъде напълно недвусмислен: нито една стъпка не бива да зависи от непосочени предположения.

Алгоритъмът е просто списък от инструкции, които ти позволяват да завършиш дадена задача. Една детайлна готварска рецепта е алгоритъм, такива са и (поне би трябвало да са) инструкциите за сглобяване на мебел от кашон. А в математиката — дългото деление е алгоритъм, и ситото на Ератостен е алгоритъм. — Plus Magazine (Университет Кеймбридж), Maths in a minute: Algorithms, ноември 2023 г.

Интересното е, че алгоритмите са много по-стари от компютрите. Хората са създавали алгоритми откакто са можели да предават инструкции един на друг. Древните египтяни са имали алгоритми за умножение. Вавилонците са имали алгоритми за квадратни корени. А един от най-старите и най-влиятелни алгоритми, запазени в писмен вид, е изложен в книга, написана преди повече от 2 300 години — но преди да стигнем до нея, нека погледнем още по-дълбоко в миналото.

Петте свойства на Кнут

През 1968 г. Доналд Кнут — един от най-влиятелните компютърни учени — започва своя епичен многотомен труд The Art of Computer Programming. Първият том се открива с дискусия какво точно е алгоритъм. Кнут изброява пет свойства, които според него всяка истинска процедура трябва да притежава, за да се нарече алгоритъм:

Петте свойства на алгоритъма (Кнут, 1968) 1. Крайност (finiteness) — алгоритъмът трябва винаги да завършва след краен брой стъпки.
2. Определеност (definiteness) — всяка стъпка трябва да е точно и недвусмислено дефинирана.
3. Вход (input) — алгоритъмът има нула или повече входни стойности от определено множество.
4. Изход (output) — алгоритъмът произвежда една или повече изходни стойности, свързани с входа.
5. Ефективност (effectiveness) — всяка операция трябва да е достатъчно основна, за да може принципно да бъде изпълнена точно и за краен брой стъпки с молив и хартия.

Самият Кнут обича да сравнява алгоритъма с готварска рецепта. „Рецептата има крайност (готвенето в крайна сметка завършва), вход (яйца, брашно) и изход (например палачинки), но няма определеност. „Щипка сол“, „топъл коняк в малка тенджерка“ — тези инструкции са напълно разбираеми за опитен готвач, но са далеч от прецизността, която компютърът изисква.“

За своя принос в анализа на алгоритмите и за поредицата The Art of Computer Programming Кнут получава наградата Тюринг през 1974 г. The New York Times нарича труда му една от определящите книги за професията. Бил Гейтс веднъж казва: „Ако мислите, че сте наистина добър програмист, прочетете Кнут. Ако успеете да прочетете целия — непременно ми изпратете автобиография.“

Алгоритъм, програма, модел, евристика — каква е разликата?

Думата „алгоритъм“ често се бърка с няколко сродни, но различни понятия. Струва си да ги разграничим ясно, защото това разграничение ни спестява недоразумения:

Ключови разграничения • Алгоритъм — абстрактна процедура, описана независимо от конкретния език на програмиране или хардуер. Пример: алгоритъмът на Евклид.
• Програма — конкретната реализация на алгоритъм на определен програмен език (Python, C++, Java). Един и същ алгоритъм може да бъде реализиран в хиляди програми.
• Модел — математическа схема, която описва явление или процес (напр. модел на атмосферата). Моделите често се пресмятат с алгоритми, но самите те не са алгоритми.
• Евристика — практичен метод, който често работи добре, но не гарантира оптимален или винаги правилен отговор. Например „избирай винаги най-близкия град“ при задачата на търговския пътник е евристика, не оптимален алгоритъм.

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

Как измерваме един алгоритъм?

Когато казваме, че един алгоритъм е „добър“, имаме предвид няколко различни неща. Ето основните:

Коректност — алгоритъмът трябва да дава правилен отговор за всеки допустим вход. Изглежда очевидно, но много „бързи“ алгоритми се оказват грешни за редки случаи.
Време (брой стъпки) — колко операции трябва да извърши. Обикновено изразяваме това като функция на размера на входа \(n\): \(O(n^2)\) значи около \(n^2\) стъпки, \(O(n \log n)\) е значително по-малко.
Памет — колко пространство използва по време на работата си. Често има компромис: ако искаме по-бърз алгоритъм, обикновено жертваме повече памет (и обратно).
Мащабируемост — как се държи при нарастващ размер на входа. Алгоритъм, който е приемлив за 100 елемента, може да е безнадежден за 1 милион.

Тази „математика на алгоритмите“ — известна като теория на изчислителната сложност — е една от най-бурно развиващите се области на съвременната информатика. Юрис Хартманис и Ричард Стърнс дефинират формално понятията „време“ и „памет“ в поредица от статии от 1960-те. Оттогава изчислителната сложност е превърнала неясните интуиции в точен математически език.

Още един древен алгоритъм: вавилонските корени

Преди Евклид, преди Гърция и Александрия, в плодородните земи на Месопотамия, около 1800 г. пр.н.е., вавилонците вече са познавали изумителен итеративен алгоритъм за изчисление на квадратен корен. Физическо доказателство: глинената плочка YBC 7289 от колекцията на Йейлския университет, датираща от XIX–XVII век пр.н.е., изчислява \(\sqrt{2}\) с точност до пет десетични знака.

Методът — по-късно описан систематично от Херон Александрийски през I век сл.н.е. и затова наричан често методът на Херон — работи така. Искате да намерите \(\sqrt{S}\). Започвате с произволно начално предположение \(x_0\). След това прилагате следната формула:

\[x_{n+1} = \frac{1}{2}\left( x_n + \frac{S}{x_n} \right).\]

Тук стои една много красива идея: ако \(x_n\) е по-малко от корена, то \(S/x_n\) е по-голямо, и обратно. Средното им аритметично е по-добро приближение от което и да е от двете. Поразително е, че след като приближението вече е достатъчно добро, броят на правилните цифри обикновено нараства приблизително двойно на стъпка. Това прави алгоритъма изключително ефективен.

Например, за \(S = 2\) и \(x_0 = 1\):

Изчисляване на \(\sqrt{2}\) по вавилонския метод \(x_0 = 1\) (един правилен знак: „1")
\(x_1 = \frac{1}{2}(1 + 2/1) = 1{,}5\) (един правилен знак: „1")
\(x_2 = \frac{1}{2}(1{,}5 + 2/1{,}5) \approx 1{,}4166\ldots\) (три правилни знака)
\(x_3 \approx 1{,}41421568\ldots\) (шест правилни знака)
\(x_4 \approx 1{,}41421356237469\ldots\) (~12 правилни знака)

Точната стойност е \(\sqrt{2} \approx 1{,}41421356237309\ldots\)

След само четири итерации сме получили 12 правилни знака. След още една — 24 знака. След десет итерации — няколко хиляди знака. Тази скорост на сближаване е забележителна за алгоритъм, измислен преди 4000 години.

Ирония на историята: когато сър Исак Нютон през XVII век измисля общия си метод за намиране на корени на функции (методът на Нютон-Рафсън), той се оказва просто обобщение на вавилонския метод върху произволни функции. С други думи, съвременните числени методи имат дълбоки корени — в буквалния смисъл — в древна Месопотамия.

Най-влиятелният античен алгоритъм: Евклидовият

Около 300 г. пр.н.е. в Александрия Евклид пише своите Елементи — книга, която оформя математическото образование на Запада за следващите две хиляди години. В книга VII от Елементите той описва процедура за намиране на най-големия общ делител на две цели числа — алгоритъм, който днес носи неговото име.

Идеята е изненадващо проста и красива. Искаме да намерим най-голямото цяло число, което дели едновременно \(a\) и \(b\). Наблюдението на Евклид е следното: ако \(d\) дели \(a\) и \(d\) дели \(b\), то \(d\) дели и остатъка \(a - b\). Значи задачата за \(\gcd(a,b)\) се свежда до задачата за \(\gcd(b, a-b)\) — същата задача, но за по-малки числа!

В модерна формулировка алгоритъмът на Евклид изглежда така:

Алгоритъм на Евклид (около 300 г. пр.н.е.) За да намерим \(\gcd(a, b)\), където \(a \geq b > 0\):
1. Разделете \(a\) на \(b\): получавате \(a = qb + r\), където \(0 \leq r < b\).
2. Ако \(r = 0\), то \(\gcd(a, b) = b\). Спираме.
3. В противен случай повтаряме процедурата с двойката \((b, r)\) вместо \((a, b)\).

Например, за \(\gcd(252, 105)\):

\[252 = 2 \cdot 105 + 42, \quad 105 = 2 \cdot 42 + 21, \quad 42 = 2 \cdot 21 + 0.\]

Следователно \(\gcd(252, 105) = 21\). Красиво е, че никога не е нужно да разлагаме числата на прости множители — задача, която за големи числа е огромно предизвикателство.

Сложността на алгоритъма на Евклид е \(O(\log \min(a, b))\) — логаритмична в размера на входа. Което означава, че дори за числа с хиляди цифри той работи изключително бързо. След повече от 2 300 години той все още се използва активно в криптографията, в теорията на числата и в изчислителната математика. Малко идеи в науката са оцелели толкова дълго.

Най-лошият случай: числата на Фибоначи Кога алгоритъмът на Евклид работи най-дълго? Френският математик Габриел Ламе доказва през 1844 г., че най-лошият случай са последователните числа на Фибоначи. Например \(\gcd(F_n, F_{n-1})\) изисква точно \(n-2\) рекурсивни стъпки. Това е исторически един от първите прецизни анализи на сложността на конкретен алгоритъм — и потвърждава, че дори в най-неблагоприятния сценарий сложността остава логаритмична.

Ада Лъвлейс и първият алгоритъм за машина

Следващата голяма стъпка идва чак през XIX век — и идва от една необикновена жена. Ада Лъвлейс (1815–1852 г.) обикновено се разглежда като автор на първия публикуван алгоритъм, предназначен да бъде изпълнен от машина. Бележка G, която публикува през 1843 г., съдържа детайлен план, написан с такава прецизност, каквато не е съществувала преди това. Историците подчертават и съвместния контекст на работата на Лъвлейс с Чарлз Бабидж — но няма съмнение, че именно нейната форма на изложение поставя началото на това, което днес наричаме програмиране.

Как се стига дотук? През 1830-те и 1840-те години английският учен Чарлз Бабидж проектира — но никога не успява да построи — поредица от механични изчислителни машини. Най-амбициозната от тях, наречена Аналитичната машина (Analytical Engine), е фактически първото описание на устройство с обща изчислителна цел в историята: тя има „склад” (памет) и „мелница” (процесор), работи с перфокарти и може да се препрограмира за различни задачи.

През 1842 г. италианският математик Луиджи Менабреа публикува на френски кратка статия, обобщаваща лекция на Бабидж за Аналитичната машина. Ада, дъщеря на поета лорд Байрон (макар израснала под строго математическо възпитание от страна на майка си), решава да я преведе на английски. Но не се задоволява с прост превод. Насърчена от самия Бабидж, тя добавя седем обстойни бележки (означени с букви от A до G), които заедно са над два пъти по-дълги от оригиналната статия. Те са публикувани през август 1843 г. в Taylor’s Scientific Memoirs и подписани само с инициалите й — A.A.L.

Именно в Бележка G Ада представя детайлен план как Аналитичната машина би могла да изчисли числата на Бернули — сложна математическа редица. Поразително е колко много от съвременното програмиране вече присъства там:

цикли — повтарящи се блокове от операции;
вложени цикли — цикъл в цикъла;
индексирани променливи (V₁, V₂, …);
условен контрол на потока — различни действия според текущото състояние;
рекурсия — числата на Бернули се изчисляват едно през друго.

По този повод Бабидж по-късно пише за нея на Майкъл Фарадей като за „тази чародейка, която е обгърнала с магия най-абстрактната от науките и я е овладяла със сила, каквато малко мъжки умове биха могли да проявят“. А визията й за компютъра като устройство, което обработва не само числа, но и всякакви символи, музика и език, се оказва пророческа цял век по-рано.

Възражението на Лъвлейс В Бележка G Ада изрично заявява, че Аналитичната машина „няма претенции сама да поражда каквото и да било. Тя може да прави само това, което знаем как да я накараме да направи“. Това твърдение, което Алън Тюринг по-късно нарича „възражението на лейди Лъвлейс“, открива философския дебат за изкуствения интелект още един век преди появата му. Тюринг го обсъжда в своята статия от 1950 г. „Computing Machinery and Intelligence“ — и не съвсем се съгласява с него.

Тюринг: какво изобщо може да бъде изчислено?

Въпреки Бабидж и Лъвлейс, до 1930-те години никой не е дал прецизен математически отговор на въпроса „какво изобщо означава да се изчислява нещо?“. Интуицията е ясна — алгоритъм е списък с инструкции — но какви инструкции са позволени? Всяка задача ли има алгоритъм? Ако не, кои задачи имат и кои не?

През 1936 г. двама млади математици — американецът Алонзо Чърч и британецът Алън Тюринг — независимо един от друг, дават изключително прецизни отговори, които се оказват математически еквивалентни.

Тюринг въвежда модел, който днес наричаме машина на Тюринг. Това е абстрактна „машина” с безкрайна лента, четящо-пишеща глава и краен набор от състояния и правила. Тя не е физическо устройство, а математически модел — умишлено примитивен, за да е ясно какво може и какво не може да прави:

Машина на Тюринг: безкрайна лента от клетки със символи, четящо-пишеща глава и краен брой вътрешни състояния. Изненадващо е, че този минимален модел може да изчисли всичко, което изобщо е изчислимо.

Тюринг доказва, че такава машина може да изчисли всичко, което може да бъде изчислено с „ефективна процедура” (т.е. алгоритъм). Това твърдение, наричано теза на Чърч-Тюринг, е един от най-дълбоките философски и математически резултати на XX век. Той гласи приблизително следното: всичко, което може да се нарече алгоритъм, може да бъде изпълнено от машина на Тюринг. Не е теорема — а теза, защото дефинира формално какво значи „алгоритъм“. Но всички алтернативни дефиниции (рекурсивните функции на Гьодел, λ-смятането на Чърч, продукциите на Пост) се оказват еквивалентни. В това е дълбочината й.

Теза на Чърч-Тюринг (1936) Всяка функция, която може да бъде ефективно изчислена (т.е. с алгоритъм), може да бъде изчислена от машина на Тюринг. И обратно.

Следствието: ако машина на Тюринг не може да реши дадена задача, то никой алгоритъм не може да я реши.

Наистина, Тюринг не само дефинира какво е алгоритъм — той доказва, че има задачи, за които не съществува алгоритъм. Най-известната е задачата за спиране (halting problem): може ли да се напише програма, която, като получи на вход произволна друга програма, да казва дали тя ще спре след краен брой стъпки или ще работи вечно? Отговорът на Тюринг е: не. Такава универсална програма е математически невъзможна.

Това е поразителен резултат. Той означава, че има ясно формулируеми, напълно смислени задачи, за които никой алгоритъм не може да съществува — не защото сме недостатъчно умни, а защото самата математическа структура го забранява. Границите на това, което може да се изчисли, са по-тесни от границите на това, което може да се формулира.

Класическите алгоритми: сортиране и търсене

След Тюринг теорията на изчислимостта процъфтява. Но паралелно се развива и друга линия: практическите алгоритми за всекидневни задачи. Може би най-добре изучените сред тях са два: сортирането (подреждане на списък по даден критерий) и търсенето (намиране на конкретен елемент в списък).

На пръв поглед и двете звучат тривиално. Но всъщност са фундаментални — защото почти всяка програма, която пишем, в един или друг момент сортира или търси данни. Ако вашата база данни има милиарди записи (помислете за клиентите на банка или потребителите на Facebook), всяка наносекунда в избора на алгоритъм се превръща в минути или часове изчакване.

Сортиране

Класически алгоритми за сортиране включват bubble sort (сравнява съседни елементи и ги разменя, докато списъкът е подреден), insertion sort (вмъква всеки нов елемент на правилното му място в сортираната вече част), selection sort (намира най-малкия останал елемент и го премества на правилна позиция). Те са интуитивни и работят, но са бавни — времевата им сложност е \(O(n^2)\). За списък от 1000 елемента това са около 1 000 000 операции.

Истинският пробив идва с т.нар. алгоритми „разделяй и владей". Когато британският компютърен учен Тони Хоар е гостуващ студент в Москва през 1959 г., той работи по проект за машинен превод. Трябва да сортира руски думи, за да ги търси в речник. Първата му идея — insertion sort — му се струва твърде бавна. Той измисля нова: разделяш списъка около произволно избран елемент („опорен“ или pivot), така че по-малките стоят отляво, а по-големите отдясно, и после сортираш всяка половина рекурсивно по същия начин.

Това е известният алгоритъм Quicksort, публикуван през 1961 г. Средно той работи за време \(O(n \log n)\) — драстично по-бързо от \(O(n^2)\). За списък от 1 000 000 елемента това е разликата между ~20 милиона операции (при \(n \log n\)) и ~1 трилион (при \(n^2\)).

10⁶

Операции за сортиране на 1000 елемента с bubble sort (\(n^2\))

10⁴

Операции за същата задача с quicksort (\(n \log n\))

100×

Пъти по-бърз quicksort за 1000 елемента

50 000×

Пъти по-бърз quicksort за 1 000 000 елемента

Алтернативни елегантни идеи от същата епоха дават merge sort (разделя списъка на две, сортира всяка половина, после ги слива) и heap sort (използва специална структура данни, наречена „купа“). Всички те са с асимптотична сложност \(O(n \log n)\). В практиката съвременните езици често комбинират няколко подхода: Timsort и негови близки хибридни варианти, използвани в Python, Java и Android, са хибриди на merge sort и insertion sort, оптимизирани да работят бързо върху данни, които вече са частично подредени.

Сравнение на типичните сложности на алгоритми. Разликата между \(O(n \log n)\) и \(O(n^2)\) изглежда малка за 100 елемента, но за милиони тя е огромна. Експоненциалните алгоритми, като \(O(2^n)\), са практически неизползваеми дори при скромни входни данни.

Търсене

Веднъж сортирани, данните могат да се търсят драматично по-бързо. Помислете как сами търсите дума в речник: не започвате от първата страница — отваряте по средата и веднага виждате в коя половина да продължите. Точно това прави двоичното търсене (binary search): сравняваме с елемента в средата, продължаваме в лявата или дясната половина, и така нататък. Сложност: \(O(\log n)\).

Разликата с обикновеното линейно търсене (което проверява всеки елемент по ред) е поразителна. За 1 милиард елемента линейното търсене може да прави 1 000 000 000 сравнения в най-лошия случай, а двоичното — само около 30. Ето защо сортирането не е самоцелно: то е инвестиция, която прави всяко последващо търсене почти мигновено.

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

Когато по-бързо не е възможно Едно от най-красивите теоретични открития в теорията на алгоритмите е, че понякога можем да докажем, че по-бърз алгоритъм е математически невъзможен. За алгоритмите, които сортират чрез сравнения (т.е. само сравняват двойки елементи), е доказано, че не може да съществува алгоритъм, изискващ средно по-малко от \(\Omega(n \log n)\) сравнения. Това е долна граница, фундаментално ограничение на задачата. Quicksort, mergesort и heapsort попадат точно в тази оптимална асимптотична сложност — знаем, че не може да бъде направено по-добре.

Алгоритмите в ежедневието: Люн и кредитните карти

За да видите силата на една добре измислена алгоритмична идея, няма нужда от Нобелова награда или компютърни центрове. Трябва ви само кредитна карта в портфейла.

Всяка кредитна карта от Visa, Mastercard, Discover и др. има 15 или 16 цифри. Те не са случайни. Първата цифра е идентификатор на индустрията (4 за Visa, 6 за Discover). Следващите няколко цифри посочват издаващата банка. Следва номер на сметката. И накрая има една последна цифра, която няма нищо общо с банковата информация — нейната роля е да направи целия номер „математически валиден“ според специална проверка.

Тази проверка е известна под името алгоритъм на Люн, описан и патентован през 1960 г. от Ханс Петер Люн, изследовател в IBM. Работи по следния начин:

Алгоритъм на Люн (1960) Вземете всички цифри на номера, без последната (контролната).
1. Започвайки отдясно, удвоете всяка втора цифра.
2. Ако удвояването даде двуцифрено число, съберете неговите цифри (напр. 7 × 2 = 14 → 1 + 4 = 5).
3. Съберете всички получени стойности и добавете контролната цифра.
4. Ако сумата е кратна на 10, номерът е валиден. Иначе не е.

На пръв поглед изглежда като магия. Но зад него стои точна математика: чрез правилен избор на контролна цифра се гарантира, че всяка единична грешка в набирането на цифра (най-често срещаният тип грешка) задължително прави сумата некратна на 10. Същото важи и за разменянето на две съседни цифри (например „37“ вместо „73“), с едно-единствено изключение — размяната на „09“ и „90“.

Това не е случайност: холандският математик Якобус Верхоф доказва през 1969 г., че тези два типа грешки съставляват близо 90% от човешките грешки при набор на цифри. Люн не предотвратява измами (за това има отделни системи), но спестява милиони ненужни проверки от банките: ако вече сумата не е кратна на 10, няма смисъл да се свързвате с банката изобщо — знаете, че картата е невалидна.

Сродни идеи с контролни цифри се използват в множество други кодове — например при баркодове, ISBN номера на книги, международни банкови сметки (IBAN), номера на пратки, номера на социални осигуровки в някои страни — макар не винаги чрез точно същия алгоритъм. Обикновено забелязваме само мигновеното червено предупреждение „грешен номер“ — но зад него стои 60-годишна математическа идея.

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

Ако алгоритъмът на Люн е микроскопичен пример, то следните няколко са истинските гиганти — без тях интернет и съвременните технологии просто не биха съществували в днешния си вид.

Алгоритъмът на Дейкстра (1956): навигация и интернет

Всеки път, когато Google Maps ви казва как да стигнете до желана дестинация, на някой сървър работи вариант на алгоритъма на Дейкстра за намиране на най-къс път в мрежа. Измислен е за около 20 минути от холандеца Едсгер Дейкстра в едно амстердамско кафене през 1956 г. Същата идея е в сърцевината на протоколите, по които рутерите насочват всеки ваш интернет пакет — OSPF и IS-IS.

RSA (1977): криптография на обществения ключ

През пролетта на 1977 г. тримата учени от MIT — Рон Rивест, Ади Sамир и Ленард Aдлеман — представят алгоритъм, който ще промени лицето на цифровата комуникация. Той се основава на асиметрията между две задачи: лесно е да умножим две големи прости числа, но практически невъзможно е да разложим обратно произведението им на множители.

Пробивът става в конкретна нощ — тази на Песах, 5 април 1977 г. Тримата прекарват Седер у дома на студент и пият доста вино, преди да се приберат около полунощ. Ривест не може да заспи и заляга на дивана с учебник по математика. До изгрев слънце той е формулирал идеята — системата се основава на изчислителната асиметрия на умножаване срещу разлагане на прости множители. През следните часове той написва по-голямата част от статията.

Всеки от трите има по един публичен и един частен ключ. Публичният се разпространява свободно — с него всеки може да ви изпрати криптирано съобщение. Но само притежателят на частния ключ може да го декриптира. Това е фундаментален пробив: за първи път двама души, които никога не са се виждали, могат да установят сигурна комуникация през публичен канал.

Един забележителен факт: идеята фактически е била открита още през 1973 г. от Клифърд Кокс, математик в британската разузнавателна агенция GCHQ — но тя е била класифицирана до 1997 г. Същият математически резултат е открит независимо два пъти: веднъж в тайна от британското разузнаване, а втори път — открито — от тримата учени от MIT. Публичното описание на RSA през 1977 г., последвано от статията в Communications of the ACM през 1978 г. и популяризацията от Мартин Гарднър в раздела „Математически игри“ на Scientific American през август 1977 г., е онова, което наистина промени света — хиляди хора по целия свят пишат писма със самоадресирани пликове, за да получат оригиналната статия.

Днес RSA е в основата на почти всяка защитена комуникация в интернет: HTTPS, SSL/TLS, защитените имейли, цифровите подписи, интернет банкирането. Тримата му автори получават наградата Тюринг през 2002 г. През 2020 г. най-голямото публично разложено RSA число има 829 бита (250 десетични цифри) — разбиването му отнема около 2 700 процесор-години. Съвременните препоръки са за ключове с поне 2048 бита, което прави класическо разбиване практически невъзможно. Но потенциален квантов компютър, достатъчно мощен да реализира алгоритъма на Шор (открит 1994 г.), би променил цялата картина — и точно заради това пост-квантовата криптография е една от най-активно развиващите се области на съвременната математика.

PageRank (1998): как Google „чете“ интернет

През 1998 г. двама докторанти в Станфорд — Лари Пейдж и Сергей Брин — публикуват алгоритъм, който подрежда уеб страниците по „важност“ на база на това кой ги линква. Този алгоритъм е в основата на Google. Математически той е собствен вектор на гигантска матрица, която описва линк структурата на целия интернет. Днес „собственият вектор за 25 милиарда долара“ е един от най-икономически значимите алгоритми в историята.

Когато случайността помага

Едно от най-красивите и неочаквани открития в теорията на алгоритмите е, че случайността често прави алгоритмите по-бързи. Звучи парадоксално — как случайността може да помогне за намиране на скрити, нескучни модели?

Ето един пример. Да предположим, че искаме да проверим дали дадено голямо число \(N\) е просто или съставно. Прямолинейното решение („пробвай всички възможни делители“) е мъчително бавно за числа с няколкостотин цифри. Но през 1970-те се появяват бързи вероятностни тестове за простота. Идеята им тръгва от малката теорема на Ферма: ако \(N\) е просто, то за всяко \(x\), \(x^N - x\) е кратно на \(N\). Ферматовият тест обаче сам по себе си има съществено ограничение — съществуват т.нар. числа на Кармайкъл, които лъжливо минават теста за много основи. Затова най-използваният на практика е по-усъвършенстваният тест на Милър–Рабин: той бързо отхвърля съставните числа и след няколко случайни проверки дава изключително висока увереност, че числото е просто — вероятността за грешка пада по-бързо, отколкото вероятността метеорит да удари Земята, докато четете отговора.

Казвате просто: „Добре, оставям опитите, нека пробвам нещо произволно.” За твърде много задачи това се оказва успешен подход. — Ерик Блей, компютърен учен в Университета на Ватерло, цитиран в Quanta Magazine

Това се нарича вероятностен или рандомизиран алгоритъм. Днес те се използват навсякъде: при тестване на простота (основа на RSA!), при Monte Carlo симулации във физиката и финансите, при машинно обучение, при графови алгоритми. Забележителната работа на Ноам Нисан и Ави Вигдерсон от 1994 г. показва дълбока връзка между случайността и трудността на изчислителните задачи: ако съществуват достатъчно трудни функции, тогава случайността в много алгоритми може да бъде заменяна с псевдослучайност, а алгоритмите — „дерандомизирани“. На практика такова дерандомизиране често е трудно, затова случайността остава един от най-мощните инструменти на съвременните компютърни учени.

Градиентно спускане: математиката на изкуствения интелект

Когато чуете „невронна мрежа” или ChatGPT, зад тях стои един конкретен алгоритъм, който се изпълнява милиарди пъти по време на обучението: градиентно спускане. Интуицията е изящна.

Представете си, че сте на планина в гъста мъгла и искате да слезете. Не виждате в далечината, но усещате наклона с краката си. Тогава каквото можете да направите, е да направите крачка в най-стръмната спускаща се посока, да се ориентирате отново и пак да направите малка крачка надолу. След много стъпки ще стигнете до долина.

Градиентното спускане прави точно това, но не с крака, а с производни. „Планинската повърхност“ в случая е функция на грешката: колко далеч е моделът от това да прогнозира правилно примерите, които му показваме. Производната (градиентът) ни казва в коя посока функцията нараства най-стръмно — значи противоположната посока е най-стръмно спускане.

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

Математически: ако имаме функция \(f(\mathbf{w})\), която зависи от множество параметри \(\mathbf{w}\), на всяка стъпка обновяваме параметрите по правилото

\[\mathbf{w}_{\text{ново}} = \mathbf{w}_{\text{старо}} - \eta \cdot \nabla f(\mathbf{w}_{\text{старо}}),\]

където \(\eta\) е „стъпката на обучение“ — колко голяма да бъде всяка крачка. Правим това милиарди пъти върху огромни набори от данни, и постепенно параметрите се стабилизират в стойности, при които моделът „се научава“ да решава задачата.

В съвременните системи почти никога не се използва чистото градиентно спускане в учебникарски вид. На практика се работи със стохастично градиентно спускане (SGD) и негови адаптивни варианти — най-известен е Adam (2014 г.), — които използват малки партиди от данни (mini-batches) и автоматично настройват скоростта на обучение за всеки параметър. Тези варианти значително ускоряват обучението и са практически стандарт при всеки голям модел: от класификатори на изображения до езикови модели като ChatGPT.

Проклятието на размерността... което се оказа благословия Дълго време се смяташе, че при много параметри (милиони или милиарди, както в съвременните невронни мрежи) градиентното спускане ще се „заседи“ в локални минимуми — ями, където всеки път нагоре изглежда стръмен. Но през 2010-те Йошуа Бенджо и съавтори аргументират теоретично и подкрепят емпирично тезата, че в многоизмерната неконвексна оптимизация седловите точки (saddle points) често са по-съществен проблем от лошите локални минимуми — а от седлова точка винаги има поне една посока надолу. Това помага да обясним защо дълбокото обучение работи — по причина, която никой не е очаквал.

P срещу NP: трудните задачи

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

Не всички алгоритми са еднакви. Едни работят за „разумно“ време дори за огромни входни данни, а други се задавят още при средноголеми. Компютърните учени разделят задачите в класове на сложност, от които най-известни са два:

P — задачи, за които има „бърз“ алгоритъм (такъв, чието време нараства полиномиално с размера на входа, напр. \(n^2\), \(n^3\), \(n \log n\)).
NP — задачи, за които можем бързо да проверим дали дадено решение е правилно, но не е ясно дали можем бързо да го намерим.

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

Въпросът P срещу NP — дали P = NP, т.е. дали всяка задача, чието решение може да се провери бързо, може и да се намери бързо — е една от най-прочутите открити задачи в математиката. Математическият институт Clay предлага милион долара награда за нейното решение. Консенсусът сред учените е, че P ≠ NP, но през 55 години никой не е успял да докаже това.

Защо ни интересува? Защото ако се окаже, че P = NP, това ще промени света по невиждан начин: всяка задача от логистика, криптография, биология, оптимизация, която днес изисква дни или години, ще може да се реши за секунди. Но това ще счупи и цялата съвременна криптография — включително RSA.

Пробив през 2025 г.: памет срещу време

Теорията на алгоритмите е жива наука — в нея постоянно се случват неочаквани пробиви. През май 2025 г. компютърният учен Райън Уилямс от MIT публикува доказателство, което се определя от колегите му като „зашеметяващо“ — първият съществен прогрес по ключов въпрос от компютърните науки за последните 50 години.

Въпросът е прост: колко памет е нужна за изчислителна задача, чието решение отнема определено време? Интуицията ни казва, че тези две неща — време и памет — са свързани. Докато бързият алгоритъм не може да има време да запълни много памет, бавен алгоритъм има тази възможност. И наистина: от 1975 г. насам се знаеше, че всяка задача, решима с определено време \(t\), може да се реши с малко по-малко памет от \(t\). Разликата обаче беше минимална, и 50 години никой не можа да я подобри.

Уилямс намери начин да я подобри драматично. На популярно-интуитивно равнище (а не като буквално техническо твърдение) може да се каже, че той показва как всяка задача, изпълнима за време \(t\), може да бъде симулирана с памет от порядъка на \(\sqrt{t}\). Quanta представя резултата като голям пробив за дълбоката връзка между време и памет — а не като директна формула за практическо ползване. За задача, отнемаща милион стъпки, интуицията е, че може да се справим с памет от около хиляда клетки, а дотогава се смяташе, че трябва да е от порядъка на милиона.

Помислих си за това и реших: „Ами, просто не може да е вярно.” — Райън Уилямс, цитиран в Quanta Magazine за откритието си, май 2025 г.

Причината е едновременно проста и дълбока. Времето тече безвъзвратно — не можем да „върнем“ изхарчените секунди. Но паметта може да бъде използвана многократно: можем да пишем и после да изтриваме, да пишем друго на същото място. Уилямс намери елегантен метод, базиран на „катализиращото изчисление“ на Стивън Кук-младши и Иан Мерц от 2023 г., който превръща всеки алгоритъм в негов еквивалент с драстично по-малко памет.

Резултатът засега няма практическо приложение (новите алгоритми са по-бавни), но променя дълбоко разбирането ни какво означава „изчислителен ресурс”. Това е пример за това как теорията на алгоритмите продължава да ни изненадва — дори и след векове развитие.

Ключови моменти в историята на алгоритмите

Ето една кратка времева ос на някои от най-влиятелните открития в тази история:

Вавилонците използват итеративен алгоритъм за квадратен корен; плочката YBC 7289 показва \(\sqrt{2}\) с точност до 5 десетични знака.
Евклид описва в „Елементите“ алгоритъма за най-голям общ делител — най-влиятелният античен алгоритъм, оцелял до днес.
Ератостен Киренски описва ситото си за намиране на прости числа — елегантен пример за алгоритъм с „филтриране“.
Ал-Хорезми пише своите математически трактати в Багдад. Латинизирането на името му по-късно дава думата „алгоритъм“.
Ада Лъвлейс публикува Бележка G — първия детайлно описан алгоритъм, предназначен да бъде изпълнен от машина.
Алън Тюринг публикува „On Computable Numbers“, въвеждайки машината на Тюринг и решавайки задачата за спиране.
Едсгер Дейкстра измисля алгоритъма за най-къс път — и без да знае, поставя основите на GPS навигацията и интернет рутирането.
Тони Хоар публикува алгоритъма Quicksort — един от най-влиятелните практически алгоритми в историята.
Юрис Хартманис и Ричард Стърнс дефинират математически „време“ и „памет“ на изчисление, създавайки теорията на изчислителната сложност.
Доналд Кнут публикува първия том на „The Art of Computer Programming“ и формулира петте свойства на алгоритъма.
Стивън Кук и Ричард Карп формулират класа NP-пълни задачи и отварят проблема P срещу NP.
Ривест, Самир и Адлеман публикуват RSA — първата практична система за криптиране с публичен ключ.
Лари Пейдж и Сергей Брин публикуват PageRank, алгоритъмът, който прави Google доминираща търсачка.
Райън Уилямс доказва силен нов резултат за симулация на време с приблизително коренна по порядък памет — първи голям пробив по темата от десетилетия.

Ограниченията: какво не можем да изчислим

Един от най-завладяващите резултати на теорията на алгоритмите е, че тя ни казва не само какво можем, но и какво не можем да изчислим.

Има три основни „стени“, които ограничават възможностите:

1. Нерешими задачи. Задачата за спиране на Тюринг е класически пример. Тя няма решение, независимо колко ресурси сте готови да инвестирате. Тюринг показва, че съществуват ясно формулируеми задачи, за които не може да има общ алгоритъм. А работата на Гьодел от 1931 г. по свой начин очертава ограниченията на формалните системи: в достатъчно богати аксиоматични системи има истинни твърдения, които не могат да бъдат доказани вътре в самата система.

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

3. Задачи с квантови решения. Шор показва през 1994 г., че квантов компютър може да разлага големи числа на прости множители експоненциално по-бързо от класически компютър. Ако квантовите компютри достигнат достатъчен мащаб, RSA ще бъде разкодиран. Затова днес активно се развиват „пост-квантови“ криптографски алгоритми.

5 алгоритъма, които ползвате всеки ден, без да знаете 1. GPS маршрут — вариант на алгоритъма на Дейкстра, когато Google Maps ви показва как да стигнете до работа.
2. Проверка на банкова карта — алгоритъмът на Люн, когато пазарувате онлайн.
3. Търсене в Google — PageRank и множество модерни негови надстройки, когато търсите рецепта.
4. Препоръки в YouTube/TikTok/Netflix — препоръчителни системи, обучени с градиентно спускане върху огромни невронни мрежи.
5. Отключване с Face ID или разпознаване на обекти — дълбоки невронни мрежи, които преди десетилетие биха изглеждали като научна фантастика.

Алгоритми и компресия: как се смаляват файловете

Когато изпращате снимка през WhatsApp, гледате видео в YouTube или слушате музика в Spotify, в играта влиза друг важен клас алгоритми — тези за компресия на данни. Те изхождат от едно изненадващо наблюдение: повечето реални данни съдържат много излишност, която може да бъде премахната без загуба (или с много малка загуба) на съдържание.

Класически пример е алгоритъмът на Хъфман (1952 г.). Идеята е проста: често срещаните символи се кодират с по-малко битове, рядко срещаните — с повече. Ако в един текст буквата „е“ се появява много по-често от „щ“, няма смисъл двете да заемат еднакво място в паметта. Хъфмановото кодиране стои като ключов компонент в схеми и формати като ZIP, PNG, JPEG и много други.

Други схеми жертват малко качество, за да спечелят много пространство. JPEG (за изображения) използва дискретно косинусово преобразувание, за да представи изображенията в честотна област и да изхвърли детайлите, които човешкото око не различава. MP3 (за аудио) прилага модели на човешкото слухово възприятие, за да изхвърли честотите, които ухото не чува ясно. H.264 и H.265 (за видео) правят същото за движещото се изображение, като използват факта, че съседните кадри обикновено са много сходни. Всички тези алгоритми използват особеностите на човешкото зрение и слух, за да спестят място и да ускорят преноса на данни.

Квантови алгоритми отвъд Шор

Алгоритъмът на Питър Шор от 1994 г. за разлагане на числа често се споменава като „квантовата заплаха за RSA“. Но той не е единственият квантов алгоритъм и далеч не е представителен за целия клас. През 1996 г. Лов Гроувър публикува алгоритъм за търсене в неструктурирана база данни, който постига квадратично ускорение — за търсене сред \(N\) елемента класическият алгоритъм използва средно \(N/2\) проверки, а Гроувъровият — около \(\sqrt{N}\).

Квадратичното ускорение не е катастрофално за класическата криптография, както е експоненциалното на Шор, но е достатъчно сериозно, за да наложи по-дълги симетрични ключове. А квантовите алгоритми като този на Гроувър се изучават и като основа за квантова оптимизация, квантови невронни мрежи и симулация на квантови системи. Квантовите компютри обещават не само да „счупят“ старата криптография — те може да открият нови класове задачи, които класически компютри принципно не могат да решат ефективно. Така квантовите алгоритми не са просто заплаха за криптографията, а нова представа за това кои задачи са бързо решими изобщо.

Алгоритми и справедливост

С разширяването на алгоритмите от абстрактна математика към инструменти, които решават кой ще получи кредит, кой обект ще бъде показан в Google Maps или кого ще спре полицията, възниква нов кръг от въпроси, които не са само технически, а етически. Алгоритмите не са неутрални: те наследяват предразсъдъците на данните, върху които са обучени, и на хората, които са ги проектирали.

Класически пример са препоръчителните системи в социалните мрежи, които могат неволно да засилват разделението — показват на всеки човек това, което той вече е склонен да харесва, и по този начин го изолират от различни мнения. Алгоритми за оценка на риска в съдебната система в САЩ са били критикувани, защото произвеждат систематично различни резултати за различни расови групи. Автоматични системи за подбор на персонал понякога наследяват половите или етническите предразсъдъци на историческите данни.

Затова в съвременната информатика все повече внимание се отделя на проверимостта (дали можем да разберем защо алгоритъмът е взел дадено решение) и на справедливостта (дали различни групи от хора се третират еднакво). Това поставя въпроса не само за точността на алгоритъма, но и за неговата прозрачност, обяснимост и справедливост спрямо различни групи от хора. Така теорията на алгоритмите става нещо повече от чиста математика — тя става и тема на обществен и етически дебат. И може би най-дълбокият урок от историята на алгоритмите е именно този: самата им сила означава, че ние, които ги създаваме, носим сериозна отговорност.

Алгоритмите и училищната математика

Може би не е случайно, че класическата математика в училище е пълна с алгоритми — те са нейната най-дълбока скрита тема. Когато ученикът учи дълго деление, алгоритъма на Евклид, решаване на уравнение по стъпки или построение с пергел и линия, той всъщност учи алгоритмично мислене: разбиване на задача на по-прости подзадачи, последователност от точни стъпки, проверка на резултата.

Това умение е напълно различно от това да помниш факти и формули. То е способността да преведеш неясна реалност в точна процедура. И именно тук математическото образование си спестява една очевидна истина: алгоритмите не са само в компютърните науки. Те са навсякъде в самата математика. Всеки метод за решаване на задача, който учите в училище, е алгоритъм. Всеки пример от учебника ви учи да следвате крайна, точно описана процедура. Това е най-важният урок от часа по математика — и рядко се нарича с истинското си име.

Защо това е една от най-важните идеи в науката

Когато ал-Хорезми през IX век описва стъпка-по-стъпка процедури за решаване на квадратни уравнения, той едва ли е подозирал, че хилядолетие по-късно името му ще даде думата за фундаментална научна концепция. Когато Евклид през 300 г. пр.н.е. описва методи за намиране на най-голям общ делител, той едва ли е очаквал, че същата процедура ще криптира банковите ви транзакции. Когато Ада Лъвлейс пише Бележка G, тя не може да знае, че един век по-късно нейните идеи ще се материализират в устройство, което децата носят в джобовете си.

Алгоритмите са дълбока идея именно защото обединяват три неща:

Универсалност — един и същ формален език описва готварската рецепта, GPS навигацията, търсенето в Google и обучаването на ChatGPT.
Прецизност — всеки алгоритъм има ясна спецификация за това какво прави, колко време отнема и колко ресурси изразходва. Това го прави проверим.
Мощ — алгоритмите са формата, в която машинното действие може да бъде описано, повторено и анализирано. Без тях няма как да мислим систематично за изчисление.

Всеки от нас живее заобиколен от алгоритми, повечето от които дори не подозираме. Когато купувате кафе с карта — Люн. Когато отваряте Google Maps — Дейкстра. Когато правите покупка онлайн — RSA. Когато гледате TikTok — препоръчителен алгоритъм, обучен с градиентно спускане. Когато водата в дома ви е чиста — алгоритъм за оптимизиране на третирането на водата. Невидимите инструкции, които някой е написал преди десет или хиляда години, движат всяка стъпка от модерния живот.

Историята на алгоритмите не е свършила — тя продължава да се пише, както показват откритията на Уилямс през 2025 г. и еволюцията на квантовите алгоритми и невронните мрежи. Ако ал-Хорезми би могъл да види какво е родено от едно негово име, сигурно би се усмихнал от изненада. А ние — ако разберем дълбочината на тази концепция — не само ще използваме алгоритмите. Ще можем и да ги разбираме.

Източници

Plus Magazine (University of Cambridge). Maths in a minute: Algorithms. 21 November 2023. plus.maths.org
Plus Magazine. Maths in a minute: Gradient descent algorithms. 10 August 2021. plus.maths.org
Brubaker, B. How Randomness Improves Algorithms. Quanta Magazine, 3 April 2023. quantamagazine.org
Brubaker, B. For Algorithms, a Little Memory Outweighs a Lot of Time. Quanta Magazine, 21 May 2025. quantamagazine.org
Murtagh, J. The Math Trick Hidden in Your Credit Card Number. Scientific American, 12 August 2025. scientificamerican.com
Williams, R. Simulating Time with Square-Root Space. arXiv:2502.17779, February 2025. arxiv.org
Cook, J. & Mertz, I. Tree Evaluation is in Space O(log n · log log n). STOC 2023. dl.acm.org
Rivest, R. L., Shamir, A. & Adleman, L. A method for obtaining digital signatures and public-key cryptosystems. Communications of the ACM, 21(2), February 1978, 120–126.
Hoare, C. A. R. Quicksort. The Computer Journal, 5(1), 1962, 10–16.
Turing, A. M. On Computable Numbers, with an Application to the Entscheidungsproblem. Proceedings of the London Mathematical Society, 42(1), 1937, 230–265.
Lovelace, A. A. (1843). Notes upon the memoir „Sketch of the Analytical Engine Invented by Charles Babbage“ by L. F. Menabrea. Taylor's Scientific Memoirs, vol. III.
Misa, T. J. Charles Babbage, Ada Lovelace, and the Bernoulli Numbers. arXiv:2301.02919, 2023. arxiv.org
Knuth, D. E. The Art of Computer Programming, Volume 1: Fundamental Algorithms. 3rd edition, Addison-Wesley, 1997. (Петте свойства на алгоритъма и основни въвеждащи дефиниции.)
MacTutor History of Mathematics. Al-Khwarizmi (790–850). mathshistory.st-andrews.ac.uk
Encyclopaedia Britannica. al-Khwarizmi — Muslim mathematician. britannica.com
Hollings, C., Martin, U. & Rice, A. The Lovelace-De Morgan mathematical correspondence: A critical re-appraisal. Historia Mathematica, 44(3), 2017, 202–231.
Shallit, J. A Very Brief History of the Euclidean Algorithm. Centre for Applied Cryptographic Research, University of Waterloo, 1994.
Gardner, M. A new kind of cipher that would take millions of years to break. Scientific American, August 1977, 120–124.
Hoare, C. A. R. Algorithm 64: Quicksort. Communications of the ACM, 4(7), 1961, 321.
Stanford Encyclopedia of Philosophy. The Church-Turing Thesis. plato.stanford.edu
Copeland, B. J. & Shagrir, O. The Church-Turing Thesis: Logical Limit or Breachable Barrier? Communications of the ACM, 62(1), 2019. cacm.acm.org
Frana, P. L. & Misa, T. J. An Interview with Edsger W. Dijkstra. Communications of the ACM, 53(8) (2010), 41–47.
Luhn, H. P. Computer for Verifying Numbers. US Patent 2 950 048, 23 August 1960.
Verhoeff, J. Error detecting decimal codes. Mathematical Centre Tracts 29, Amsterdam, 1969.
Fowler, D. & Robson, E. Square Root Approximations in Old Babylonian Mathematics: YBC 7289 in Context. Historia Mathematica, 25(4), 1998, 366–378.
Yale Babylonian Collection. YBC 7289 (Old Babylonian clay tablet, c. 1800–1600 BCE). Yale University.
Lamé, G. Note sur la limite du nombre des divisions dans la recherche du plus grand commun diviseur entre deux nombres entiers. Comptes Rendus Acad. Sci. Paris, 19 (1844), 867–870.
Huffman, D. A. A Method for the Construction of Minimum-Redundancy Codes. Proceedings of the IRE, 40(9), 1952, 1098–1101.
Grover, L. K. A fast quantum mechanical algorithm for database search. Proceedings of the 28th Annual ACM Symposium on Theory of Computing, 1996, 212–219.
Kingma, D. P. & Ba, J. Adam: A Method for Stochastic Optimization. ICLR 2015, arXiv:1412.6980.
Dauphin, Y. et al. Identifying and attacking the saddle point problem in high-dimensional non-convex optimization. NeurIPS 2014.
O'Neil, C. Weapons of Math Destruction: How Big Data Increases Inequality and Threatens Democracy. Crown, 2016. (За алгоритмичен bias и общественото значение.)

Още от поредицата „Любопитно от математиката“

▶

Любопитно от математиката

Биографии на велики математици, исторически факти, забавни задачи и вдъхновяващи истории от света на математиката.

Вижте всички статии →

Запишете урок

Индивидуални и групови онлайн уроци по математика за цялата страна

🎓 Подготовка за изпити

›НВО по математика след 7 клас
›НВО по математика след 10 клас
›Кандидатстудентски изпити по математика
›Прием в университети в чужбина (ISEE, SAT, A-Level)

📚 Текущо обучение и студенти

›Усвояване на текущия учебен материал (всички класове)
›Студенти: Мат. анализ, Линейна алгебра, Аналитична геометрия, Диф. уравнения, Теория на вероятностите, Статистика и др.

✆ 0883 375 433 ☎ Viber

Харесва ли ви съдържанието?

Ако тази статия ви е харесала, можете да подкрепите създаването на нови безплатни материали.