Бакалавърски програми - Каталог 2020/2021 | Информатика | CSCB323

CSCB323 Структури от данни

Анотация:

Курсът излага основните принципи и подходи за създаването на алгоритми и формализирането на типични за програмистката практика задачи. Занятията са съчетание от лекционен материал, семинарни занятия с решаване на задачи и тестване на решения в компютърен клас. След всяко занятие, студентите получават задание за домашна работа, в което имат поставени задачи, пряко обвързани с разглежданото в часоветел Задачите от практическите занятия в компютърен клас са за самостоятелна прогамна реализация разширени и усложнени варианти на реализираните в час програми. Заданията за домашни работи се публикуват в Мудъл и студентите имат срок за предаването им през системата. Комплектът от предадени домашни се подлага на защита от всеки студент и представлява част от текущата семестриално оценка. Самостоятелните разработки по домашните задания се представят при явяване на изпит и са необходимо условие за провеждане на изпита.

Цели на курса:

? Да създаде програмистично и алгоритмично мислене

? Да даде основните принципи и подходи за създаването на алгоритми и формализирането на типични за програмистката практика задачи

? Да се разгледат и анализират примери за основни рекурсивни подходи и алгоритми

? Да създаде по-ясна представа за сложност на алгоритмите, за числени методи

? Да запознае със съществуващите подходи за структуриране на данните при динамечно отреждане на памет.

? Да създаде умения за управление на динамични структуре данне

прочети още
Към курсовете на програмата График Виртуално обучение
Информатика

Преподавател(и):

проф. Велина Славова  д-р
гл. ас. Филип Андонов  д-р

Описание на курса:

Компетенции:

Успешно завършилите курса студенти:

1) знаят:

? принципите на съставянето на рекурсивни алгоритми и програми за тяхното изпълнение

? имат представа за понятието “сложност на алгоритъм”

? основни динамични структури от данни

2) могат:

? да програмират основни общоизвестни алгоритми

? да разчитат алгоритмичния смисъл на програми, реализиращи изучените алгоритми

? да обвързват смислово материал от областите на математическия анализ, дискретната математика и алгоритмите


Предварителни изисквания:
Студентите да имат знания и/или умения:

• От уводни курсове по алгоритми

• От уводни курсове по математика

• Владеене, на преимлево ниво, на произволен процедурен език за прорамиране



Форми на провеждане:
Редовен

Учебни форми:
Лекция

Език, на който се води курса:
Български

Теми, които се разглеждат в курса:

  1. ПЪРВА ЧАСТ Тема 1. Сложност на алгоритъм по време. Асимптотични означения. Анализ на изучените квадратични алгоритми за сортиране.
  2. Тема 2, "Едноклонова" рекурсия. Рекурсивно дефинирани обекти. Развитие на рекурсивен процес като изчисление. Пренос на резултатите при рекурсия. Примери – НОД и факториел.
  3. Тема 3. Рекурсия - продължение. Двуклонова рекурсия. Работа на рекурсивен процес, извършвана "на потъване". Пример - Бързото сортиране, трасиране и анализ на сложността по време.
  4. Тема 4. Двуклонова рекурсия, работеща на изплуване. Пример - сортиране чрез сливане, трасиране и анализ на сложността по време.
  5. Тема 5. Разделяй и владей. Пример - ханойски кули - съставяне на алгоритъма по рекурсивната дефиниция, анализ, сложност. Представа за майсторската теорема.
  6. Контролно над първа част - рекурсивни алгоритми над масиви, принципи, обмен на данни, анализ на сложнотта. Тест задачи през Мудъл
  7. ВТОРА ЧАСТ Динамични стуруктури данни. Тема 6. Увод и преговор на работа с указатели. Тема 7. Линейни динамични структури. Образуване на стек посредством указатели. Обхождане на линейна стуктура. Образуване на опашка посредством указатели.
  8. Тема 8. Поддържане на нареден линеен списък. Използване на свойствата на рекурсивен процес за „обхождоне“ в посока обратна на указателите.
  9. Тема 9. Дървета - общи понятия и термини. Идеално балансирани двоични дървета – ИБД - дефиниции и височина. Построяване на ИБД с рекурсивна функция, съставена по дефиницията.
  10. Тема 10. Обхождане на дървета в дълбочина. Инфиксна, префиксна и постфиксна схеми на обхождане.
  11. Тема 11. Двоични дървета за претърсване (ДДП). Дефиниции, свойства, височина, образуване и нарастване на ДДП.
  12. Тема 12. Динамични операции с дървета. Намаляване на дърво - премахване на възли. Височина и нареденост - теорема за височината.
  13. Тема 13. Аделсон-Велский и Ландис дървета (AVL). Дървета на Фибоначи - най-лошо AVL дърво - оценка на височина на AVL дървета. Поддържане на AVL дърво.
  14. Тема 14. Още балансирани дървета. Червено-Черни дървета - дефиниции, баланс, вмъкване, пребоядисване и други.
  15. Контролно над динамични структури - тест задачи през Мудъл
  16. ТЕМАТИЧЕН ПЛАН (за лабораторните в компютърна зала или с лично устройство) ПЪРВА ЧАСТ Тема 1. Сложност на алгоритъм по време. Асимптотични означения. Анализ на изучените квадратични алгоритми за сортиране. Програмна реализация на квадратичните алгоритме за сортиране, измерване на време на изпълнение в общия спучай, при наредени и обратно наредени данни. Съставяне на графики.
  17. Тема 2, "Едноклонова" рекурсия. Упражнение с компютър - Съставяне на програми за рекурсивен вариант на алгоритъма на Евклид и пресмятането на факториел, проследяване на обмена между копията - потъване и на изплуване. Рекурсия и итерация. Преработка на едноклонова рекурсия в итерация и обратно. Дихотомично търсене в нареден масив – рекурсивен и итеративен вариант.
  18. Тема 3. Упражнение в компютърен клас. Двуклонова рекурсия. Бързото сортиране, трасиране и измерване на времето за изпълнение в зависимост от Еталона. Схема на последователносста на изпълнение на копията. Проверка на заемане на памет при изпълнението.
  19. Тема 4. Двуклонова рекурсия, работеща на изплуване. Упражнение в компютърен клас - сортиране чрез сливане, трасиране и анализ на сложността по време. Алгоритмичен подход “Разделяй и владей”, примери за приложение при МergeSort.
  20. Тема 5. Прилагане на “Разделяй и владей” за съставяне на алгоритъма „Ханойски кули”. Упражнение в компютърен клас. Програмна реализация с преброяване на копията и измерване на врече да изпълнение.
  21. Тема 6. Подготовка за Контолна работа по част 1. Решаване на задачи
  22. Тема 7 Абстрктни структури. Програмиране на прости примери за Работа с указатели. Упражнение в компютърен клас
  23. Тема 8 Програмиране на линеен динамичен списък като стек и като опашка. Обхождане . Упражнение в компютърен клас
  24. Тема 9 Програмиране на образуване и поддържане нареден линеен списък обхождане в посока, обратно на указателите.
  25. Тема 10 Програмиране на образуване на рекурсивно дефинирано идеално балансирано дърво. Инфикско, постфисдно и префиксно обхождане Упражнение в компютърен клас
  26. Тема 11 Програма зя построяване на ДДП. Обхождане в дълбочина с тенериране на нареден линеен динамичан списък
  27. Тема 12 Динамични операции с дървета. Премахмане на възли от ДДП.
  28. Семинар обсъждане и защита на самостоятелните разработки по заданията към всяка тема.
  29. Семинар обсъждане и защита на самостоятелните разработки по заданията към всяка тема.
  30. Семинар обсъждане и защита на самостоятелните разработки по заданията към всяка тема.

Литература по темите:

Основна

1. Cormen, Thomas H. (2013) Algorithms Unlocked, The MIT Press

2. Алгоритми + структури данни = програми, Уирт Н. (още превеждан като „Вирт”), можете да ползвате кое да е издание, на какъвто искате език.

Niklaus Wirth, Algorithms and Data Structures. Oberon version 2004

4. Манев К. Увод в дискретната математика, учебник, издателство на НБУ, 1997

Средства за оценяване:

1. Текущо оценяване по време на семестъра.

Базира се на 1. участие - предадените домашни (спазен срок) – 25%, 2. на защитата на тези разработки – 25% и 3. на контролните работи – 50%

От изпит се освбождават студентите, които получат семестриална оценка над 4.50 вкл. и нямат нито една слеба оценка от изброените горе

2. Изпит. Състои се от две части – решаване на задачи и събеседване