О, Да, "ДАА"!

Увод, безплатна мостра.

Здрасти

Често има разминаване между представата на студентите за това какво се учи по ДАА и това, което всъщност се учи по ДАА.

Тук няма да се учим как да програмираме, а как да програмираме алгоритми.
Приемаме, че вече знаеш как се компилира сорс файл, какво е функция и как се конструира сравнително четим код.

Всичко друго тук е незадължително.
Ползването на ООП¹ е по собствено желание.

Езици за програмиране

Безпрецедентно най-добрият език за писане на алгоритми е C.
Той е забележимо труден, обаче, затова през повечето време ще се задоволяваме и с по-прости неща.
C++ е на второ място. По-бавен е по време на работа, но пак е много бърз, а някои неща се пишат по-кратко.
Java също става, макар и да не е език правен точно за тази цел.
C# е приемливо.
ActionScript, Python, Ruby, et al… - не. Само ако много много бързаш и наистина няма друг начин. Бавни са, не са за това правени.

Та, алгоритми

Пример:
Ако трябва да направиш програма за сървъра на Еврофутбол, тук няма да се научиш как става.
Как програмата ти приема заявки за залози, откъде получава данни за текущите коефиценти и т.н. ще трябва да си измислиш ти.
Какъв Уеб/Десктоп/друг интерфейс да има, как да изглежда той и дали ще приема UTF-8 или само ASCII - за това не ти трябват алгоритми.

Трябват ти, обаче, когато е нужно да обработиш 10 000 000 залога и да кажеш кои от тях имат най-голям шанс да спечелят поне 10 евро.
Трябват ти когато искаш да рисуваш някаква 3D графика, на нивото има 20 000 000 тригъгълника, а можеш да рисуваш примерно само по 20 000 на кадър.
Трябват ти когато времето просто не стига.
Когато искаш нещо да е бързо.

Какво значи Алгоритъм?

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

Алгоритъм е нещо, което прави друго нещо.

В този курс ще се учим на неща, които ще използваме за да правим други неща от трети неща.
Стига толкова сухи дефиниции, хайде да напишем една примерна програмка.

Пример, Фибоначи…

Да, изтъркано е, вярно.

Числата на Фибоначи са рекурентно дефинирани:
$F(0) = 1$
$F(1) = 1$
$F(n) = F(n-1) + F(n-2), \forall n \ge 2$

Задача:
Дадено е N. Искаме да сметнем F(n).
Ще го сметнем за колкото се може по-голямо N.

---

Първите 20-тина числа на Фибоначи са смятани толкова пъти, че производителите на процесори вече слагат специални инструкции за тяхното пресмятане. Наистина²!

…както баба ти го е писала:

N = 50

/**
    Най-обикновена рекурсия, която директно пренася дефиницията на редицата в код.
    Работи за O(2^n) време.
*/
int fib_1(int n)
{
    if(n == 0 || n == 1)
        return 1;
    return fib_1(n-1) + fib_1(n-2);
}

Това е Баааааааавно. Много много бавно. Експоненциално бавно³.
Лесно се доказва(и по-късно ще го доказваме), че за дадено N програмата минава през $2^n - 1$ стъпки, за да получи верен отговор.
Тоест, за N = 10, има над 1000 стъпки.
За N = 20 има над 1 000 000 стъпки.
За N = 50 има да чакаш.

Ето една картинка, която илюстрира ситуацията.

Това е много зле. Ти не искаш картинката да изглежда така.

…както ще го пишеш ти, за да нямаш двойка на изпита:

N = 500000

Първо една уговорка.
5000-то число на Фибоначи има повече от 1000 цифри.
Вградените числови типове на C/C++ събират има-няма 20 цифри.
Ако искаме да го смятаме точно, ще трябва да си напишем наши типове, които поддържат произволен брой цифри.

Тези се наричат BigNum, BigInteger и разни други подобни имена. На български е "Големи числа".
Те са трудни за писане и бавни. Сега няма да се занимаваме с тях.

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

Лесно се вижда, че fib_1(50) ползва fib_1(49) и fib_1(48).
Но fib_1(49) също ползва fib_1(48)!
Нещо повече, всички ползват fib_1(1), fib_1(2) и т.н.
Ползват ги по няколко милиарда пъти, докато те всъщност винаги връщат един и същи резултат.
Можем просто да си ги пазим някъде и да не ги смятаме всеки път, нали?
Да.

const int MOD = 1000000;
/**
    По-интелигентна версия, която запомня смятани преди резултати и не ги смята по много пъти.
    Във всеки един момент помни само F(n), F(n-1) и F(n-2). От тях извежда F(n+1).
    Работи за O(n) време.
*/
int fib_2(int n)
{
    if(n == 0 || n == 1)
        return 1;
 
    int a,b=1,c=1;
    n-=2;
 
    do
    {
        a = (b + c) % MOD;
        c = b;
        b = a;        
    }while(n--);
 
    return a;
}

Ето колко бързо работи:

Една милисекунда за десетхилядното число.

А ето защо C е най-добрият език за алгоритми:

0.7 секунди за 50-милионното число.
Пробвай това на каквото и да е друго⁴.

…както го пише Чък Норис:

N = 100000000000000000000000000000000000 …
Последният алгоритъм за днес може да работи за мноооооооооооооооого големи числа.
Много по-големи, отколкото е удобно да се запише в C++.
Може да работи за числа с по 50000 цифри. Може и с по 100000.
Да, буквално работи за един Гугол!

Ама няма да ти обяснявам как става.
Вече идва моментът да си използваш главата, надявам се да можеш да го разбереш.
Ако не успееш, надявам се след като минеш курса по ДАА да ти бъде ясно и да ти бъде лесно.
Това е само началото.

typedef unsigned long long ull;
const int MOD = 1000000;
/**
    Помощна структура, представлява матрица 2x2.
*/
struct ma3x
{
    ull pts[4];
};
 
/**
    Умножава две матрици.
    Резултатът се записва в първия аргумент.
*/
void multiply(struct ma3x *m1, struct ma3x *m2, int mod);
 
/**
    Много бърза имплементация, която се базира на факта, че матрицата:
    {
        { 1 1 }
        { 1 0 }
    }
    Повдигната на (N-2)-ра степен съдържа N-тото число на Фибоначи в първия елемент на първия си ред.
    Използва бързо повдигане на степен.
 
    Работи за O(log(n)) време.
*/
ull fib_3(ull n)
{
    n-=2;
    if(n < 0)
        return 1;
    struct ma3x res = {1,1,1,0};
    struct ma3x m1 = {1,1,1,0};
    while(n)
    {
        if(n % 2)
            multiply(&res, &m1, MOD);
        n/=2;
        multiply(&m1, &m1, MOD);
    }
    return res.pts[0];
}
 
void multiply(struct ma3x *m1, struct ma3x *m2, int mod)
{
    struct ma3x tmp = {0,0,0,0};
    #define a(n) m1->pts[n]
    #define b(n) m2->pts[n]
 
    tmp.pts[0] = (a(0)*b(0) + a(1)*b(2)) % mod;
    tmp.pts[1] = (a(0)*b(1) + a(1)*b(3)) % mod;
    tmp.pts[2] = (a(2)*b(0) + a(3)*b(2)) % mod;
    tmp.pts[3] = (a(2)*b(1) + a(3)*b(3)) % mod;
 
    int x;
    for(x=0;x<4;++x)
        m1->pts[x] = tmp.pts[x];
 
    #undef a
    #undef b
    return;
}

Отново до 50 милиона, но докато fib_2(50000000) работеше за 0.7 секунди, fib_3(50000000) работи за 0.000032 секунди.
Не е прекалено зле.

Освен това, fib_3(100000000000000000) работи за 0.00005 секунди.

В заключение

Ето затова трябва да учиш алгоритми.

Тук има едно архивче, с което можеш да тестваш програмите, които са написани горе.
Изисква се да имаш Линукс, както и Gnuplot.http://fmi.wikidot.com/daa1

Footnotes

1. Обектно-ориентирано програмиране, аджеба. Забележи, че това е едно от малкото места, където ООП реално прави нещата по-трудни!

2. Не, не наистина.

3. Макар все още да не знаем официално какво значи това

4. Освен асемблер, де :)