ТЕСТ

Посочете вярно или невярно е всяко от следващита твърдения за точната оценка на сложността на дадения алгоритъм за сортиране на $n$ елемента.
- бързо сортиране на Хоор -- $O(n)$
+ пряка селекция -- $O(n^2)$


Дадена задача има размер на входа $n$. Разполагаме с два различни алгоритъма A и B за решаването \`и, изискващи време $an$ и $bn^2$ съответно, където $a$ и $b$ са неизвестни положителни константи. Направено е измерване на времето на работа на всеки от алгоритмите при стойности на $n$ 1024 и 2048, при което са получени следните резултати: за алгоритъм A -- 128 и 256; за алгоритъм B --  16 и 64. Посочете верните твърдения:
+ Алгоритъм А ще бъде по-бавен от B за стойности на $n$, по-малки от 5.
- Алгоритъм B ще бъде по-бавен от D за стойности на $n$, по-малки от 8192.


Отбележете верните твърдения за примери на комбинаторни конфигурации.
+ 12 21 е пермутация без повторения $n=2$
- 12 13 14 23 24 34 е пермутация без повторения за $n=4, k=2$


Посочете верни и неверни твърдения за бързодействието на алгоритми при достатъчно големи входни данни и зададени сложности.
+ Алгоритъм със сложност $O(n^2)$ е по-бавен от друг със сложност $O(1)$
- Алгоритъм със сложност $O(1)$ е по-бавен от друг със сложност $O(n^2)$


Дадена е следната рекурсивна функция
   unsigned no_gcd(unsigned a, unsigned b)
   { return (0 == b) ? a : no_gcd(b, a/b); }
Отбележете верните и неверни съответствия "параметри на функция -> върната стойност".
+ "100, 50 -> 25"
- "8, 24 -> 8"


Посочете верните твърдения за метода ``разделяй и владей''.
+ Разбиване на изходната задача на няколко подзадачи, решаване на подзадачите и конструиране на решение на изходната задача.
- Методът се реализира само с нерекурсивни функции.


Посочете верните твърдения за динамичното оптимиране.
+ Биномни коефициенти се пресматат с приложение на този метод.
- Методът изисква реализация с рекурсивна функция.


$k$-тият по големина елемент в несортиран масив може да се намери (в най-лошия случай) за време:
+ $O(n^2)$
- $O(1)$


Алгоритъм за умножение на две $n$-цифрени числа може да има сложност:
+ $O(n^2)$
- $O(1)$


Отбележете задачите, за решаването на които по метода на динамичното оптимиране може да се използва рекурентната формула от класическата задача за раницата.


Дадена е задача за раницата с 4 вида предмети с тегла 2, 4, 1 и 5 и цени съответно 8, 15, 3 и 21. Предполагаме, че има неограничени количества от всички предмети. Решения ли са следните комбинации на зададено максимално тегло -- получена максимална цена?
+ 12,  50
- 1, 4


Посочете верните твърдения за графи.
+ Граф G наричаме наредената двойка (V, A), където V е крайно множеството от върховете на графа, а А -- крайно множество от дъги.
- Ориентиран свързан граф без цикли се нарича дърво.


Верни ли са следните твърдения за класификация на задачите?
+ Всяка задача с полиномиален алгоритъм за решаването \'и е полиномиално проверима.
- NP = P