Topic outline
-
Тема №1. Въведение в дисциплината
Обща информация. Кратко представяне на дисциплината, съдържанието, ресурсите и начинът на изпитване. Алгоритми. История, дефиниция, свойства, начини на представяне и описание.
-
Тема №2. Числа (част I)
Бройни системи. Непозиционни и позиционни бройни системи и операции с числа с различни бройни системи. Битове и битови маски. Операции и алгоритми за работа с битове и с битови маски. Итерация и рекурсия. Описание на итеративни и рекурсивни алгоритми и няколко конкретни задачи.
-
Тема №3. Числа (част II)
НОД и НОК. Най-голям общ делител и най-малко общо кратно. Алгоритъм на Евклид за НОД. Решаване на уравнения. Решаване на линейно уравнение и на система от две линейни уравнения с две неизвестни. Геометрично представяне. Изчисляване на функции. Приближено изчисляване на функции, техни производни и интеграли. Намиране на корени с двоично търсене и метод на Нютон.
-
Тема №4. Масиви (част I)
Масиви. Структура от данни „масив“. Видове масиви. Физическа реализация. Отбелязване. Базови операции с масиви. Инициализиране. Копиране, вмъкване, изтриване. Сумиране и средна стойност. Намиране на максимум или минимум. Последователно и двоично търсене. Алгоритми за сортиране на масиви. Сортиране на байтове, сортиране чрез вмъкване, сортиране по метода на мехурчето и сортиране чрез избор.
-
Тема №5. Сложност на алгоритми
Производителност и сложност. Измерване на производителността и сложността на алгоритми. Критерии за оценяване. Скала. Видове сложност. Нотации O(…), Ω(…), Θ(…), o(…) и ω(…). Свойства на O(…) и примери. Оценяване на сложност. Оценяване на последователни инструкции, цикли, вложени цикли, условно изпълнение, функции. Оценяване на алгоритми за числа на Фибоначи, прости числа и операции с масиви.
-
Тема №6. Масиви (част II)
Бързи алгоритми за сортиране. Сортиране на Шел. Бързо сортиране. Сортиране чрез сливане. Други алгоритми за сортиране.
-
Тема №7. Матрици
За матриците. Етимология. Използване. Термини. Представяне. Адресиране. Преобразуване до масив и от масив. Операции с матрици. Транспониране. Събиране и изваждане. Умножение със скалар, с вектор и с матрица. Детерминанта на матрица. Използване на матрици. Решаване на система от линейни уравнения. Геометрични трансформации. Координатни системи. Гледна точка. Свързани обекти.
-
Тема №8. Низове
ASCII и Unicode. Числови и текстови данни. Представяне чрез ASCII и чрез Unicode. Операции. Търсене, изтриване, вмъкване на символ. Дължина, конкатенация, работа с поднизове, търсене, сравняване, сортиране. Преобразуване. Главни и малки букви, числа, кодиране и декодиране.
-
Тема №9. Асоциативни масиви
Асоциативни масиви. Разширение на масивите – на размера, на типа на данните, на индексите. Задача за броене на думи в „Ромео и Жулиета“. Хеш-таблици. Хеширане. Хеш-таблица. Хеш-функция над число и над низ. Колизия. Отворено, затворено и зоново хеширане. Рехеширане.
-
Тема №10. Стек и опашка
Стек. Динамични структури. Стек. Реализация на стек. Приложение на стек – осъществяване на рекурсия, извикване на функции и обработване на изрази. Опашка. Операции. Реализация чрез масив. Приоритетна опашка. Дек.
-
Тема №11. Списъци
Списък . Дефиниция. Данни в списъци. Видове вписъци. Езици със списъци. Операции със списъци. Създаване и проверка за празен списък. Глава и опашка. Работа с първи елемент. Обхождане. Отпечатване. Работа с последен и с вътрешен елемент. Копиране и обединяване. Алгоритми със списъци. Цикличен и двойно свързан списък. Стек чрез списък. Размяна на елементи. Функция map.
-
Тема №12. Дървета
Дървета. Нужда от дървета. Какво е дърво. Графично представяне. Данни в дърво. Операции с дървета. Обхождане в широчина и дълбочина. Двоични дървета. Видове. Представяне с масив. Създаване, търсене, добавяне, премахване. Обхождане в дълбочина. Задачи с дървета. Път в лабиринт. Аритметични изрази. Кодиране.
-
Тема №13. Графи
Графи . История. Дефиниция. Примери. Класификация. Матрица на съседство. Списък на съседство. Алтернативни представяния. Операции с графи. Обхождане в дълбочина и широчина. Намиране на най-къс път. Покриващи дървета. ДССР и графични задачи с графи.
-
Тема №14. Визуализация на данни
Графични обекти. Графични примитиви. Общи свойства. Размерности. Сложни обекти – съставни, ротационни, влачени, конструктивни, параметрични, процедурни. Създаване на диаграми. Лентова диаграма. Кръгова диаграма. Радарна диаграма. Мрежова диаграма. Проблеми и решения при генерирането им..
-
Тема №15. Моделиране и симулиране
Моделиране на движение. Линейно и кръгово движение. Балистика. Топане. Загуба на енергия. Инерция. Скачане. Вълни. Случайни числа. Видове и характеристики. Генератори на случайни числа. Метод на Монте Карло и Лас Вегас. Моделиране на форми. Фрактали – алгебрични и геометрични методи. Моделиране на нежива и жива природа (брауново движение, мълния, остров, терен, листо, дърво, микроорганизми, медуза, корал).