Синтез и анализ на алгоритми 2020
Курсове
.jpg?lmsauth=d6cd16dafdd71b85749bb3b461ad951514a7080a){kind=small}
Недялко Пешев
Синтез и анализ на алгоритми е задължителен курс от учебния план на специалност „Приложна електронна и компютърна техника”. Знанията и уменията, придобити при обучението по този курс създават предпоставка за реализация в областта на създаването на софтуерни продукти.
Целта на учебната дисциплина е да запознае студентите с различни методи за решаване на програмни задачи и тяхната оценка. В края на обучението си студентът трябва:
• да създава алгоритми за решаване на задачи и да оценява тяхната ефективност;
• да може да прилага основните методи за сортиране (пряка селекция, пряка размяна, пряко вмъкване, сортиране с намаляваща стъпка, пирамидално сортиране, бързо сортиране);
• да може да създава и използва рекурсивни функции;
• да може да създава и използва рекурсивни структури от данни.
В курса се изучават видовете алгоритми и основните принципи на тяхното изграждане. Застъпени са: рекурсивни алгоритми, основни алгоритми за сортиране на едномерни масиви, динамични структури от данни и по-подробно: линейни списъци, стекове и опашки; представени са базови знания от теорията на графите.
Необходими са предварителни познания по синтаксиса на езика С/С++.
Заверка
Заверка
1.Регистрация в класа „Синтез и анализ на алгоритми 2015“
2.Всички текущи тестове в системата за електронно обучение да бъдат направени с оценка от 3 до 6.
3.Тестът с 6-те алгоритъма за сортиране да бъде направен с 12 „ОК“.
4.Всички задължителни задачи от упражненията да бъдат решени и качени в системата.
Оценяване
1.Текуща оценка.
2.Два теста на хартия, които трябва да бъдат направени с оценка от 3 до 6.
Всяко неявяване на хартиен тест се оценява със служебна оценка 2.
За всеки тест има по една поправка.
a)Тест 1 е с тежест 50
b)Тест 2 е с тежест 50
c)Всеки от текущите тестове е с тежест 1.
3.Поправката е по време на поправителната сесия и включва целия материал.
Ето конспекта на класа:
1. Електронно ОбучениеЛинк към видео урок |
2. Алгоритми
11 Ноем
Алгоритъм - понятие, свойства, представяне |
3. Упражнение 1: Анализ на циклични алгоритми.По зададен цикличен алгоритъм се определят броят на итерациите и стойностите на променливите. |
4. Упражнение 2: Задачи от едномерни масиви.Задачи за обработка на едномерни масиви. |
5. Упражнение 3: САА: Тест 1Примерен вариант на Тест 1. Включва: теория на алгоритмите, блокови схем, анализ на алгоритмите. Този тест е разширена версия на Тест 1, който ще се изпълни на хартия. Съдържа всички типове въпроси, които са включени в хартиената версия. Предвиден е за самостоятелна работа. |
6. Сортиране на едномерни масиви
11 Ноем
Описват се 6 основни метода за сортиране на едномерни масиви. |
7. Сортиране по метода на прякото вмъкване
11 Ноем
Прост метод за сортиране на едномерен масив. |
8. Сортиране по метода на пряката размяна
11 Ноем
Прост метод за сортиране на едномерен масив. Носи още наименованието метод на мехурчето. |
9. Сортиране по метода на пряката селекция
11 Ноем
Разглежда се намиране на максимален елемент, основния принцип на сортиране по метода на пряката селекция, блокова схема и код на програмата на езика С++. |
10. Сортиране чрез вмъкване с намаляваща стъпка (Сортиране по Shell)
25 Ноем
Представлява подобрение на метода за сортиране чрез пряко вмъкване. Предложено е от D.L.Shell през 1959г. |
11. Пирамидално сортиране
25 Ноем
Подобрява метода на пряката селекция. Носи наименованието Пирамидално сортиране или Дървовидно сортиране. |
12. Сортиране по дялове – бързо сортиране
9 Декември
Подобрява метода на сортиране с пряка размяна (метод на мехурчето). Утвърден е като най-бързия метод за сортиране на масиви. |
13. Упражнение 4Задачи от едномерни масиви. Сортиране. Търсене. |
14. Упражнение 4Задачи от едномерни масиви. Генериране на нов масив. Упражнения върху сортиране на масиви. Подготовка за контролно. |
15. Упражнение 5: Контролно - сортиране на масивиЗадължително за подпис |
16. Упражнение 6Прости числа. Ситото на Ератостен. Гаусово разпределение. |
17. Упражнение 7. Задачи от сортиране на масивиПриложение на алгоритмите за сортиране при масиви, изградени от сложни елементи. |
18. Рекурсивни алгоритми
9 Декември
Дефиниране на рекурсивни обекти. Примери. Рекурсивни алгоритми. Видове рекурсия. Дълбочина на рекурсията. Приложение. Примери. |
19. Алгоритми с отстъпване (с връщане назад)
9 Декември
Рекурсивни алгоритми. Метод на пробите и грешките. |
20. Упражнение 8. Задачи от рекурсияПриложение на рекурсивните алгоритми |
21. Динамични структури от данни
9 Декември
|
22. Реализация на линейни списъци
9 Декември
В настоящата разработка се спирам на реализация на едносвързан линеен списък. За реализацията на линейни списъци в С++ могат да се използват масиви, рекурсивни структури или рекурсивни класове. В настоящата разработка се спирам на реализация посредством рекурсивни класове. |
23. Класове наследници, дефиниращи възлите на списъка*
9 Декември
Данните, които ще се съхраняват в отделните възли на списъка се декларират в класове, наследници на класа Node. В тези класове освен данните, задължително трябва да се дефинират и виртуалните функции на класа Node. Като примери в настоящата работа съм представила 3 класа: MyFloatList, MyCharList и MyStringList, с помощта на които реализирам списък с елементи, които са числа с плаваща запетая; списък с елементи, които са символи; списък с елементи, които са символни низове. |
24. Класове наследници, дефиниращи вида на списъка*
9 Декември
Докато базовите класове изграждат скелена на линейната структура, класовете наследници се използват за създаване на действителната линейна стуктура. |
25. Стек*
9 Декември
1. Понятие за стек 2. Програмна реализация на стек 2.1. Реализация чрез масив 2.2. Реализация чрез линеен списък |
26. Опашка*
9 Декември
|
27. Упражнение 9. Задачи от линейни списъциПриложение на алгоритмите за обхождане и обработване а линейни списъци, стекове и опашки. |
28. Теория на графите
9 Декември
Дефиниция. Свойства. Представяне и алгоритми за обхождане. Път в граф. |
29. Упражнение 10. Задачи от теория на графите.Тестове, свързани с основните понятия от теорията на графите и представянето им чрез програмни обекти. |
30. Упражнение 11. Тест 3 - Динамични структури от данни. Теория на графите.Тест върху рекурсивни структури и теория на графите. |
31. Задачи от двумерни масивиОбработкана елементите на двумерен масив. Задачите са за самостоятелна работа. |
32. Самостоятелни задачиОформят се като доклад и се представят пред групата. Задължителна демонстрация. Формира 30% от оценката по САА. |
33. Текущи резултати по дисциплината |
34. Примерни тестове
22 Януари
Примерни тестове за контролни и изпит |