CSCB324 Състезателно програмиране - I част

Info

Записки от лекциите по “CSCB324 Състезателно програмиране - I част”, водени от доц. Николай Киров, д-р.

Лекция №1 §

Вход и изход за много примери §

// Четене на зададен брой примери (числа)  
int n;  
cin >> n;  
for (int i = 0; i < n; i++) { cin >> ... }  
 
// Четене до края на файла за числа или думи (низове)
while (cin >> x) { ...}  
while (cin >> x && x > 0) { ... }   
  
// Четене до края на файла на редове (низове)  
string st;  
while(getline(cin, st)) { ... }

Tip

Може да ползваме string за обработка вход като “Дадени са две цели числа в интервала “.

Структури от данни - STL §

Въведение в STL §

Контейнери:

• съдържат информацията, която обработваме
• биват два типа:
  • контейнери-редици (sequence): елементите са съхранени последователно (пр. vector, deque, list, forward_list)
  • асоциативни: елементите са съхранени под формата на двойки: ключ стойност (пр. map/unordered_map, multimap/unorederd_multipmap, set/unordered_set, multiset/unordered_multiset)

Итератори:

• дават достъп до информацията, която контейнера съдържа

Алгоритми:

• използвайки итераторите, работят с информацията съдържана в контейнерите: sort, reverse и др.

Контейнер-редици §

Вектор std::vector §

Подходящ:

• добавяне на елементи, но не и премахване
• бързо търсене по индекс
• конветртиране до C-style масив

Неподходящ:

• добавяне/изтриване на елементи в средата на списъка
• търсене на елемент по индекс, който не е число

Сложност:

• : вмъкване в началото, вмъкване на позиция, премахване на начален елемент, премахване на елемент на позиция, търсене на елемент по стойност
• : добавяне на елемент в края, премахване на елемент в края, достъпване на елемент на позиция

Дек std::deque §

Същите характеристики като std::vector, но с ефективни начини за добавяне/премахване на елементи в началото.

Сложност:

• : вмъкване на елемент на позиция, премахване на елемент на позиция, търсене на елемент по стойност
• : вмъкване на елемент в началото, вмъкване на елемент в края, премахване на елемент в началото, премахване на елемент в края, достъпване на елемент на позиция

Списък std::list/std::forward_list §

Предимства:

• добавяне на елементи в средата/началото на списъка
• ефикасно сортиране (смяна на pointer вместо копиране)

Недостатъци:

• директен достъп до елементи

Ако имаме нужда от двупосочно итериране, да се ползва std::list, ако нямаме - std::forward_list.

Сложност:

• : вмъкване на елемент на позиция, премахване на елемент на позиция, достъпване на елемент на позиция, търсене на елемент по стойност
• : вмъкване на елемент в началото, вмъкване на елемент в края, премахване на елемент в началото, премахване на елемент в края

Contiguous memory is when the memory is in one big block without any gaps.

Асоциативни контейнери §

std::map / std::unordered_map §

Подходящ:

• съхранение на двойки ключ/стойност
• търсене по ключ (константно време)
• проверка дали съществува двойка ключ/стойност
• премахване на повторения
• std::map - подреден map / std::unordered_map - хеш таблица

Неподходящ:

• сортиране

std::unordered_map е по-бързо от std::map. Използват се за binary search trees.

Сложност:

Действие	std::map	std::unordered_map
Вмъкване		O(1)
Достъп по ключ		O(1)
Премахване по ключ		O(1)
Търсене по стойност		-
Премахване по стойност		-

std::set §

Подходящ:

• премахване на повторения
• подреден динамичен списък

Неподходящ:

• директен достъп по индекс

Използват се за binary search trees.

Сложност:

• : добавяне / премахване / търсене

std::stack §

Подходящ:

• “First-in Last-Out” действия
• обръщане на реда на елементи

Сложност:

• : вмъкване в края, премахване от края, достъпване на последния елемент

std::queue §

Подходящ:

• “First-in First-out” действия

Сложност:

• : вмъкване в края, премахване от началото, достъпване на първия елемент

std::priority_queue §

Подходящ:

• “First-in First-out” действия, на които може да се променя приоритета

Сложност:

• : достъпване на елемента с най-висок приоритет
• : вмъкване на елемент, премахване на елемент

Лекция №2 §

Оценка и сложност на алгоритми §

Три главни свойства на компютърен алгоритъм:

• простота и елегантност;
• коректност;
• бързодействие.

Warning

NP (nondeterministic polynomial time) Complete задачи не могат да бъдат решени в полиномиално време, но могат да бъдат полиномиално проверена.

Размер на входните данни §

Пример 2. Да се намери най-големият общ делител на  и
В този пример размерът на входните данни се определя от броя на двоичните цифри (битовете) на по-голямото от числата  и .

Пример 3.
Да се намери покриващо дърво на граф.
В този случай характеризираме размера на входа с две числа: брой на върховете и брой на ребрата.

Асимптотична нотация §

Когато се интересуваме от сложността на алгоритъм най-често се интересуваме как ще работи при достатъчно голям размер n на входните данни.  При формалното оценяване на сложността на алгоритмите изследваме поведението им при “достатъчно голямо” ().

свойства и примери:

Нотацията (най-лош случай) е най-често използваната при оценка на сложност на алгоритми и програми.

По-важни свойства на О(f) (с означаваме принадлежност):

• рефлексивност:
• транзитивност: ако , , то ;
• транспонирана симетрия: ако , то и обратно
• константите могат да бъдат игнорирани: за всяко ,
• n, повдигнато в по-висока степен, нараства по-бързо: , за
• нарастването на сума от функции се определя от най-бързо нарастващата от тях:
• ако е полином от степен , то
• ако нараства по-бързо от , а нараства по-бързо от , то следва, че нараства по-бързо от

Пример:

• елементарна операция - не зависи от размера на обработваните данни - 
• последователност от оператори - определя се от асимтотично най-бавния - 
• композиция на оператори - произведение от сложностите - 
• условни оператори - определя се от асимтотично най-бавния между условието и различните случаи;
• цикли, два вложени цикъла,  вложени цикли - , ,

Популярни алгоритми §

• Binary Search:
• Linear Search:
• Quick Sort:
• Selection Sort:
• Travelling salesperson :
• бързо сортиране на Хоор -

“Разделяй и владей”:

• Принципи на “разделяй и владей”: разбиване на изходната задача на няколко подзадачи (разделяй), решаване на подзадачите и конструиране на решение на изходната задача (владей).
• пример: двоично търсене
• Бързо сортиране с разделяне на дялове (Хоор, “разделяй и владей”) - O(n2) в най-лошия случай, O(n) в най-добрия случай, O(n log n) средно. Сложността зависи от избора на елемент за разделяне на дялове;
• Сортиране чрез сливане

Мажорант: Ще казваме, че даден елемент на множеството е негов мажорант, ако се среща строго повече от  пъти.

*Решение с двоен цикъл: *броене колко пъти се среща всеки елемент - .

*Решение със сортиране при линейна наредба на елементите му: *сортираме и проверяваме средния елемент за мажорант - време или по-добро, ако сортираме с по-бърз алгоритъм.

Решение с броене: , ако в масива има различни стойности.

Умножение на числа: Класическият алгоритъм за умножение на цели числа има сложност .

Алгоритъм за умножение на две -цифрени числа и , като е степен на 2. Сложността на алгоритъма е O(n^r), . Тъй като < 2, то този алгоритъм е по-добър от класическия.

Циклично преместване на елементите на масив:

Пример за циклично преместване на позиции елементите на масив m от n елемента. 0 1 2 3 4 5 -> 2 3 4 5 0 1

Алгоритъм 1:

• копираме първите k елемента на m в друг масив x;
• преместваме n-k елемента на m на k позиции вляво;
• копираме елементите на x обратно в m на последните k позиции.

Сложност , допълнителна памет k елемента.

Лекция №3 §

• Fibonacci Sequence
• Euclidean Algorithm
• Factorial

Лекция №4 §

• Prime numbers
• Sieve of Eratosthenes
• Perfect Numbers

Комбинаторни алгоритми §

Пермутации:

• с повторения: Общ брой  където  е броят на i-тия различен елемент, участващ в мултимножеството (пример: множество { 1 1 2 3 }, )
• без повторения: , брой на елементи в множеството

Вариации:

• с повторения: , общ брой:
• без повторения: , общ брой:

Комбинации:

• с повторения:

• без повторения:

Лекция №8 §

Динамично оптимиране §

Тест §

Верни твърдения:

• пряка селекция - 
• 12 21 е пермутация без повторения за
• Алгоритъм със сложност е по-бавен от друг със сложност
• Метод “разделяй и владей”: Разбиване на изходната задача на няколко подзадачи, решаване на подзадачите и конструиране на решение на изходната задача.
• Метод “разделяй и владей” не се реализира само с нерекурсивни функции.
• Биномни коефициенти се пресмятат с приложение на динамично оптимиране.
• Динамично оптимиране не изисква реализация с рекурсивна функция.
• -тият по големина елемент в несортиран масив може да се намери (в най-лошия случай) за време:
• Алгоритъм за умножение на две n-цифрени числа може да има сложност:
• Контейнерът map съхранява двойки елементи (ключ, стойност) и поддържа операция индекс.
• Всяка задача с полиномиален алгоритъм за решаването й е полиномиално проверима.
• е
• не е

---

Въпроси:

Дадена е следната рекурсивна функция:

unsigned no_gcd(unsigned a, unsigned b)
{ return (0 == b) ? a : no_gcd(b, a/b); }

Параметри на функция: 100, 50 Върната стойност: 25

---

Дадена задача има размер на входа n. Разполагаме с два различни алгоритъма и за решаването й, изискващи време и съответно, където и са неизвестни положителни константи. Направено е измерване на времето на работа на всеки от алгоритмите при стойности на и , при което са получени следните резултати: за алгоритъм и ; за алгоритъм и . *Отговор: *Алгоритъм ще бъде по-бавен от за стойности на , по-малки от 5.

---

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

---

Нека , , и са функции с положителни цели аргументи и положителни стойности. Вярно твърдение: Ако е , то е за всяка константа .