diff options
Add seminar01
7 files changed, 382 insertions, 1 deletions
| -rw-r--r-- | .vscode/tasks.json | 28 | ||||
| -rw-r--r-- | README.md | 5 | ||||
| -rw-r--r-- | Seminar01/README.md | 222 | ||||
| -rw-r--r-- | Seminar01/src/searching-algorithms/binary-search.cpp | 33 | ||||
| -rw-r--r-- | Seminar01/src/sorting-algorithms/bubble-sort.cpp | 34 | ||||
| -rw-r--r-- | Seminar01/src/sorting-algorithms/insertion-sort.cpp | 28 | ||||
| -rw-r--r-- | Seminar01/src/sorting-algorithms/selection-sort.cpp | 33 |
diff --git a/.vscode/tasks.json b/.vscode/tasks.json new file mode 100644 index 0000000..05054c5 --- /dev/null +++ b/.vscode/tasks.json @@ -0,0 +1,28 @@ +{ + "tasks": [ + { + "type": "cppbuild", + "label": "C/C++: g++ build active file", + "command": "/usr/bin/g++", + "args": [ + "-fdiagnostics-color=always", + "-g", + "${file}", + "-o", + "${fileDirname}/${fileBasenameNoExtension}" + ], + "options": { + "cwd": "${fileDirname}" + }, + "problemMatcher": [ + "$gcc" + ], + "group": { + "kind": "build", + "isDefault": true + }, + "detail": "Task generated by Debugger." + } + ], + "version": "2.0.0" +}
\ No newline at end of file @@ -1 +1,4 @@ -# Код от семинаритe по структури от данни 2024/2025 - Информационни системи
\ No newline at end of file +# Код от семинаритe по структури от данни 2024/2025 - Информационни системи + +## Тема 1 +Сложност на алгоритми. Сложност по време и сложност по памет. Анализ на итеративни алгоритми и примери. Алгоритми за сортиране (bubble sort, insertion sort, selection sort) и алгоритми за търсене (linear search, binary search).
\ No newline at end of file diff --git a/Seminar01/README.md b/Seminar01/README.md new file mode 100644 index 0000000..e0fd932 --- /dev/null +++ b/Seminar01/README.md @@ -0,0 +1,222 @@ +# Първи семинар по структури от данни - 10.10.2024 + +## Алгоритъм +Формално понятието алгоритъм е първично. За него няма общоприета дефиниция. Все пак обаче алгоритми сме виждали и имаме някаква представа какво представляват. + +За алгоритъм най - често се мисли като за крайна последователност от елементарни инструкции, използвани за да решат някакъв проблем или да извършат някакво изчисление. С течение на курса, изучавайки различните структури от данни, ще изучаваме и различните алгоритми, в които те се използват. Използването на правилните структури от данни често ни води до по - добри алгоритми. Но какво точно наричаме "по-добър алгоритъм"? + +## Сложност по време +За да си отговорим на въпросът "алгоритъм А по - добър ли е от алгоритъм B", трябва да въведем някаква оценка. Първият ни опит би бил да напишем и двата алгоритъма и да ги пуснем върху достатъчно голям вход. Можем да измерим за колко време се изпълнява всеки един от тях (примерно в секунди) и да сравним двете времена. + +Такъв тип оценки се правят, но те не винаги са точни. Причината за това е, че подобни оценки могат да зависят от много неща: +* Дали двата алгоритъма са пуснати на една и съща машина? +* Каква точно е машината? Какъв хардуер използва? +* Каква е операционната система на тази машина? Какви неща вървят заедно с нашите алгоритми? + +И много още. Приемаме друг подход - интересуваме се как се изменя броя стъпки (елементарни инструкции), извършени от алгоритъма, с нарастване на входа. Например, ако разгледаме произволен алгоритъм, който приема като вход цяло число и прави нещо с него, дали с нарастване на входа (числото) нарастват стъпките, които алгоритъмът изпълнява? И, ако нарастват, как точно нарастват? + +## Дефиниция: Сложността е функция по големината на входа. + +Нека разгледаме следния алгоритъм: +```cpp +unsigned algA(unsigned n) +{ + unsigned result = 0; + for(unsigned i = 1; i <= n; i++) + { + result += i; + } + return result; +} +``` +Този алгоритъм приема цяло число `n` и намира сумата на числата от 1 до `n`. Нараства ли броят на стъпките, които алгоритъмът изпълнява, с нарастване на входа? Отговорът е да - при вход 10 цикълът `for` ще се завърти 10 пъти. При вход 100 той ще се завърти 100 пъти. + +Сега нека разгледаме друг алгоритъм, решаващ същата задача: +```cpp +unsigned algB(unsigned n) +{ + return n * (n + 1) / 2; +} +``` +Формулата е добре позната (формула за аритметична прогресия). Нараства ли броят на стъпките, които алгоритъмът изпълнява, с нарастване на входа? Отговорът е не - при вход 10 и при вход 100 винаги ще имаме едно събиране, едно умножение и едно делене. + +## Асимптотични нотации +Както казахме, интересува ни **как расте броя на стъпките при нарастване на входа**. В някакъв смисъл **не ни интересува колко точно са на брой а единствено как расте.** Ще въведем две нотации, които ще ни помагат да оценяваме алгоритми. + +* Нотацията Θ ни дава точна граница. +* Нотацията О ни дава горна граница. + +Нека използваме тези нотации за да дадем оценки на алгоритмите: + +* algA = O(n) + +* algA = O(n^2) - Това е вярно, понеже О е горна граница, но е безсмислено да се разглежда. + +* algA = Θ(n) + +* algA != Θ(n^2) - Θ е точна а не горна граница. + +* algB = O(1) + +* algB = O(n) - Това е вярно, понеже О е горна граница, но е безсмислено да се разглежда. + +* algB = Θ(1) + +* algB != Θ(n) + +## Видове сложност по време +Когато разглеждаме сложността по време, имаме три случая: +* Най-добър случай +* Среден случай +* Най-лош случай + +Нека се опитаме да разберем смисъла на тези понятия чрез пример: + +```cpp +int linear_search(int* haysack, unsigned size, int needle) +{ + for(unsigned i = 0; i < size; i++) + { + if (haysack[i] == needle) + { + return i; + } + } + return -1; +} +``` +Това е алгоритъмът линейно търсене, той приема масив и число и връща индекса на числото, ако то се среща, и -1 ако не се среща в масива. В случая `n` е големината на масива (т.е. `size`). Няма смисъл да разглеждаме нарастването на търсения елемент. + +* Най-добър случай: Тук приемаме оптимистичен подход. Нека елементът, който търсим, е винаги на първа позиция. Тогава, без значение колко расте масивът, винаги ще имаме едно сравнение и веднага ще връщаме от функцията. Можем да направим извод, че сложността в най - добрия случай е Θ(1). + +* Най-лош случай: Най-лошият случай е когато елементът не присъства в масива. Тогава алгоритъмът прави възможно най-много стъпки. Тогава сложността е Θ(n). + +* Среден случай: Анализът на средния случай е най-полезен, но и най-сложен. Можем да си мислим за него като осреднената оценка на стъпките върху всички възможни входове. Интуитивно сложността в средния случай отново е Θ(n). + +Сложността в средния случай винаги се намира между сложността в най-добрия и сложността в най-лошия. Ако оценим най-лошия случай на Θ(n) а средния на Θ(n^2), то допускаме грешка. + +## Сложност по памет +Сложността по памет на даден алгоритъм е броят на елементите памет, които алгоритъмът използва, без да броим паметта в която се разполага входа и паметта в която се разполага изхода. Отново използваме асимптотичните нотации за да даваме оценка. + +## Пресмятане на сложности. +Нека разгледаме следния алгоритъм: +```cpp +int dummy(int n) +{ + int result = 0; + while(n) + { + result++; + n--; + } + return result; +} +``` +Сложността на този алгоритъм е Θ(n). Защо? Отговорът "защото прави n стъпки" не е коректен. +* Една стъпка за създаване на променливата `result` със стойност 0. + +* `n` пъти увеличаваме `result` и `n` пъти намаляме `n`. + +* "Една" стъпка за връщане на резултата. + +Тоест тук стъпките са поне 2n + 2. И все пак алгоритъмът е със сложност Θ(n). Както казахме, **не се интересуваме от точна оценка а от това как нарастват стъпките.** Приемаме следните правила: +* Игнонираме мултипликативните константи: + * 3n = Θ(n) + * 7n = Θ(n) + * 0.5n = Θ(n) +* Игнорираме събираемите + * n + 7 = Θ(n) + * 2n + 10 = Θ(n) +* Интересуваме се от функцията с най - висока асимптотика + * n^2 + 7n + 3 = Θ(n^2) + * 2^n + n^2 + 1 = Θ(2^n) + +## Анализ на итеративни алгоритми +Един от начините да анализираме сложността на итеративни алгоритми е чрез метода на сумирането. +```cpp +for(int i = 0; i < n; i++) +{ + Θ(1) +} +``` +$$ +\sum_{i=0}^n \theta(1) = \theta(n) +$$ + +```cpp +for(int i = 0; i < n; i++) +{ + for(int j = 0; j < n; j++) + { + Θ(1) + } +} +``` +$$ +\sum_{i=0}^n \sum_{j=0}^n \theta(1) = \sum_{i=0}^n \theta(n) = \theta(n^2) +$$ + +Забележка: Два вложени `for` цикъла не винаги означават Θ(n^2) сложност. +``` cpp +for(int i = 1; i < n; i *= 2) +{ + for (int j = 0; j < i; j++) + { + Θ(1) + } +} +``` + +## Примери за алгоритми с различни сложности. + +```cpp +bool is_odd(unsigned n) +{ + return (n % 2) == 1; +} +``` + +Сложност: Θ(1) + +```cpp +bool is_prime(unsigned n) +{ + if(n < 2) + return false; + + // Assuming sqrt = O(sqrt(n)). + // (which is true in most cases) + // https://en.wikipedia.org/wiki/Integer_square_root + // binary search based algorithm can be used to assure Θ(lon(n)). + unsigned square = sqrt(n); + + for(int i = 2; i <= square; i++) + { + if(n % i == 0) + { + return false; + } + } + return true; +} +``` +Сложност: Θ(sqrt(n)) + +```cpp +unsigned log_down(unsigned n, unsigned base = 2) +{ + unsigned result = 0; + + while(n) + { + ++result; + n /= base; + } + return result; +} +``` +Сложност: Θ(log(n)) + +Алгоритъм, който генерира всички подмножества на множество с големина n, би имал сложност Θ(2^n). + +## Сортиращи алгоритми - bubble sort. Анализ на сложността на bubble sort.
\ No newline at end of file diff --git a/Seminar01/src/searching-algorithms/binary-search.cpp b/Seminar01/src/searching-algorithms/binary-search.cpp new file mode 100644 index 0000000..b5befb0 --- /dev/null +++ b/Seminar01/src/searching-algorithms/binary-search.cpp @@ -0,0 +1,33 @@ +#include <iostream> + +template <class T> +int binarySearch(const T* arr, size_t size, T elem) +{ + int left = 0; + int right = size - 1; + + while (right - left >= 0) + { + int mid = left + (right - left) / 2; + + if(arr[mid] == elem) + { + return mid; + } + else if (arr[mid] > elem) + { + right = mid - 1; + } + else + { + left = mid + 1; + } + } + + return -1; +} + +int main() +{ + +}
\ No newline at end of file diff --git a/Seminar01/src/sorting-algorithms/bubble-sort.cpp b/Seminar01/src/sorting-algorithms/bubble-sort.cpp new file mode 100644 index 0000000..ac730ca --- /dev/null +++ b/Seminar01/src/sorting-algorithms/bubble-sort.cpp @@ -0,0 +1,34 @@ +#include <iostream> + +template<class T> +void bubbleSort(T* arr, unsigned length) +{ + size_t lastSwappedIndex = length - 1; + + for (size_t i = 0; i < length; i++) + { + unsigned lastSwappedIndexTemp = lastSwappedIndex; + for (size_t j = 0; j < lastSwappedIndex; j++) + { + if(arr[j] > arr[j + 1]) + { + std::swap(arr[j], arr[j + 1]); + lastSwappedIndexTemp = j; + } + } + + if(lastSwappedIndex == lastSwappedIndexTemp) { break; } + lastSwappedIndex = lastSwappedIndexTemp; + } +} + +int main() +{ + int arr[] = {5, 2, 3, 1, 4}; + bubbleSort(arr, 5); + + for(int element : arr) + { + std::cout << element << " "; + } +}
\ No newline at end of file diff --git a/Seminar01/src/sorting-algorithms/insertion-sort.cpp b/Seminar01/src/sorting-algorithms/insertion-sort.cpp new file mode 100644 index 0000000..00e823e --- /dev/null +++ b/Seminar01/src/sorting-algorithms/insertion-sort.cpp @@ -0,0 +1,28 @@ +#include <iostream> + +template<class T> +void insertionSort(T* arr, unsigned length) +{ + for (size_t i = 1; i < length; i++) + { + int elementToInsert = arr[i]; + int j = i - 1; + while (j >= 0 && arr[j] > elementToInsert) + { + arr[j + 1] = arr[j]; + --j; + } + arr[j + 1] = elementToInsert; + } +} + +int main() +{ + int arr[] = {4, 3, 1, 5, 2, 6}; + insertionSort(arr, 6); + + for(int element : arr) + { + std::cout << element << " "; + } +}
\ No newline at end of file diff --git a/Seminar01/src/sorting-algorithms/selection-sort.cpp b/Seminar01/src/sorting-algorithms/selection-sort.cpp new file mode 100644 index 0000000..5ace579 --- /dev/null +++ b/Seminar01/src/sorting-algorithms/selection-sort.cpp @@ -0,0 +1,33 @@ +#include <iostream> + +template<class T> +void selectionSort(T* arr, unsigned lenght) +{ + for (size_t i = 0; i < lenght; i++) + { + size_t minElementIndex = i; + for (size_t j = i + 1; j < lenght; j++) + { + if(arr[j] < arr[minElementIndex]) + { + minElementIndex = j; + } + } + + if(i != minElementIndex) + { + std::swap(arr[i], arr[minElementIndex]); + } + } +} + +int main() +{ + int arr[] = {1, 5, 4, 2, 3, 6}; + selectionSort(arr, 6); + + for(int element : arr) + { + std::cout << element << " "; + } +}
\ No newline at end of file |
