Website Summary Files Commits Branches @commit @diff @stats
diff options
context:
space:
mode:
Commitc9e3d1dd8c76da82db677570bbbd555405686a78 (patch)
Author
 Stoycho Kyosev <skyosev@192.168.100.17>
2024-10-11 02:24:47 -0400
Committer
 Stoycho Kyosev <skyosev@192.168.100.17>
2024-10-11 02:24:47 -0400
Filesc266de9020071ef2400f13063a02cb7514407b0a
Data-structures-and-algorithms-c9e3d1dd8c76da82db677570bbbd555405686a78.tar
Data-structures-and-algorithms-c9e3d1dd8c76da82db677570bbbd555405686a78.tar.gz
Data-structures-and-algorithms-c9e3d1dd8c76da82db677570bbbd555405686a78.zip
Parentddf71c2b4804b7a86aa9bd48e385603b7623f244 (diff)
Add seminar01
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
diff --git a/README.md b/README.md
index aaf19b5..937d47a 100644
--- a/README.md
+++ b/README.md
@@ -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