Информационни технологии & Интернет

АЛГОРИТМИ – ОСНОВНИ ПОНЯТИЯ

Думата ’алгоритъм’ идва от името на арабския математик al-Khwarezmi, който през VIII в. описва откриването на десетичната бройна система и представя редица важни концепции в книгата си Al-jabr wa’l muqabala. Алгоритъм – крайна последователност от действия (стъпки) за решаване на конкретен проблеми или даден вид проблеми. Точното математическо определение свежда  понятието ’алгоритъм’ до добре дефинирано въображаемо изчислително устройство, например машината на Тюринг. Съвременно  понятие за алгоритъм – „ясно и точно предписание за изпълнение на последователност от елементарни операции, с цел  решаването на клас еднотипни задачи“ (акад.Макаров). Алгоритъм в програмирането – пълно, точно и еднозначно предписание за изпълнение на даден клас задачи при входни данни, които могат да се променят в определени граници.

РАЗВИТИЕ НА АЛГОРИТМИТЕ

„Историческо“ развитие – условно се разделя на 3 етапа:

• Намиране на начин за символно представяне на информацията под формата на данни (например видовете числа);
• Формулиране на алгоритми, използващи данните за решаване на изчислителни задачи;
• Създаване на механични изчислителни машини, които могат да изпълняват машините ефективно.

Алгоритмите през вековете:
• ок.300 г. пр.н.е. – алгоритъм на Евклид;
• ок.250 г. пр.н.е. – решето на Ератостен;
• oк.800 г. – ал-Хорезми и книгата му „Алгебрата и уравненията“
• 1424 г. – Масуд ал-Каши изчислява π с точност до 16-я знак след
запетаята.

АНАЛИЗ НА АЛГОРИТМИТЕ

• 1845 г. – Габриел Лейм показва, че алгоритъмът на Евклид извършва
брой деления, не повече от 5 пъти броя на десетичните цифри на по-малкото число;
• 1900 г. – Дейвид Хилберт поставя въпроса за намирането на процедура
за решаване на диофантови уравнения;
• 1910 г. – Поклингтън дефинира сложност на алгоритъм като полином,
зависещ от броя на цифрите в двоичното кодиране на данните;
• 1920-1930 г. – Пост предлага прост унарен модел за изчисления,
известен като машина на Пост;
• 1930 г. – Алонсо Чърч представя ламбда–смятането;
• 1936 г. – Алън Тюринг публикува статия, където представя машината на
Тюринг (формален, но физически осъществим модел за изчислимост).

СВОЙСТВА НА АЛГОРИТМИТЕ

• Еднозначност;
• Детерминираност (определеност);
• Крайност;
• Резултатност;
• Масовост;
• Дискретност.

КОМПЮТЪРНИ АЛГОРИТМИ

Три основни свойства:

1. Простота и елегантност;
2. Коректност;
3. Бързодействие;

Докато първото от тях може да се оцени интуитивно, за другите две е
нужен много по-задълбочен анализ.
Пример:
1) n = 100;
2) sum = 0;
3) for (int i=0; i
4)
for (int j=0; j
5)
sum++;

АНАЛИЗ НА ПРИМЕРА

Редове 1) и 2): n = 100; sum = 0; – статична инициализация (константно време a)
Редове 3) и 4): (i = 0; i < n; i + +) и (j = 0; j < n; j + +) – константни времена b, c и d (съответно e, f и g) Ред 5): константно време h За прозволно n имаме: a + b + n.c + n.d + n.(e + n.f + n.g + n.h) = a + b + n.c + n.d + n.e + n.n.f + n.n.g + n.n.h = n2 .(f + g + h) + n.(c + d + e) + a + b = i.n2 + j.n + k Нека имаме 2 функции F (n) и G(n) (време за изпълнение на два алгоритъма A1 и A2 ): F (n) = 2.n2 – квадратична; G(n) = 200.n – линейна За достатъчно големи n (в случая n > 100) имаме F (n) > G(n).

АСИМПТОТИЧНИ НОТАЦИИ

O–нотация:
O(g(n)) = {f (n) : съществуват цели константи c и n0 такива, че
0 ≤ f (n) ≤ c.g(n), ∀ n ≥ n0 };
Ω–нотация:
Ω(g(n)) = {f (n) : съществуват цели константи c и n0 такива, че
0 ≤ c.g(n) ≤ f (n), ∀ n ≥ n0 };
Θ–нотация:
Θ(g(n)) = {f (n) : съществуват цели константи c1 , c2 , и n0 такива, че
0 ≤ c1 .g(n) ≤ f (n) ≤ c2 .g(n), ∀ n ≥ n0 }.
O(F ) е най-често използвана при оценка на сложност на алгоритми и
програми.

ОСНОВНИ АСИМПТОТИЧНИ ФУНКЦИИ

- Сложност O(1) – константна
- Сложност O(log2 n) – логаритмична
- Сложност O(n) – линейна
- Сложност O(n2 ) – квадратична
- Сложност O(cn ) – експоненциална
Когато функцията F е полином, сложността O(F ) наричаме полиномна
Изпълнено е:
O(1) ⊂ O(log2 n) ⊂ O(n) ⊂ O(n2 ) ⊂ . . . ⊂ O(nk ) ⊂ O(cn ) ⊂ O(n!) ⊂ O(nn )
От примера: i.n2 + j.n + k = O(n2 ) + O(n) + O(1) = O(n2 )

ВКЛЮЧВАНЕ В КЛАС НА СЛОЖНОСТ

Положителни примери
Отрицателни примери
10n ∈ O(n)
10n ∈ O(1)
/
10n ∈ O(n2 )
10n2 ∈ O(n)
/
10n2 + 3n ∈ O(n)
10n + 3 ∈ O(n)
/
4n2 − 5n + 2 ∈ O(n2 )
4n3 − 5n + 2 ∈ O(n2 )
/
√
√
n ∈ O(n)
5n + 1 ∈ O( n)
/
√
√
log2 n ∈ O( n)
n ∈ O(log2 n)
/
( 3 )n ∈ O(n1000 )
n100 + 1000n99 ∈ O(2n )
/
2
2n ∈ O(3n )
n! ∈ O(4n )
/
n! + 100n ∈ O(n!)
nn ∈ O(n!)
/

ОПРЕДЕЛЯНЕ СЛОЖНОСТ НА АЛГОРИТЪМ

- Елементарен оператор – сложност O(1);
- Последователност от оператори – определя се от сложността на най-
бавния от тях;
- Вложени оператори – сложността се пресмята като произведение на
отделните сложности;
- Оператор if – if (P ) S1 ; else S2 ; сложността е max{O(P ), O(S1 ), O(S2 )};
- Цикъл – сложност O(n);
- Вложени цикли – сложността зависи от включените в циклите
оператори;
- Рекурсия – to be continue…..

ПРИМЕРИ С ВЛОЖЕНИ ЦИКЛИ

Пример 1:
unsigned sum = 0;
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
sum++;
Сложност O(n.n) = O(n2 )
Пример 2:
unsigned sum = 0;
for (int i = 0; i < n-1; i++)
for (int j = i; j < n; j++)
sum++;
Сложност O( (n.n−1) ) = O(n2 )
2

ПРИМЕРИ С ВЛОЖЕНИ ЦИКЛИ

Пример 3:
unsigned sum = 0;
for (int i = 0; i < n*n; i++)
sum++;
Сложност O(n2 )
Пример 4:
unsigned sum = 0;
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
if (i == j)
for (k = 0; k < n; k++)
sum++;
Сложност O(???)

Сходни статии:

1. По-важни алгоритми Програма за преобразуване на еднобайтово число в допълнителен код Инструкцията NEG преобразува в допълнителен код, като инвертира всички 8 бита на числото и добавя единица. За знак използва флага N...
2. СА Алгоритми Задание: Около кръгла маса са наредени n на брой човека, номерирани последователно с числата от 1 до n. След това започвайки от номер 1, всеки трети напуска масата, докато накрая...
3. Рекурентни редици и рекурсия Recurrence Relations and Recursion: A method for teaching the topic of “Recursion” in the programming course is developed in this article. It also uses the recurrent-sequences knowledge, gained from discrete-mathematics...
4. Криптографски алгоритми Известните базови криптографски алгоритми се класифицират по различни класификационни признаци. Като класификационен признак на първото ниво на класификацията е използвано свойството симетричност на алгоритмите. По този признак базовите криптографски алгоритми...
5. Програмиране в C и C++ Кодирането или съставянето на програмата е реализация на алгоритмите чрез език за програмиране. Езиците за програмиране от високо ниво, какъвто е и програмният език C, се характеризират със задължителни синтактични...