CSCB214 Увод в алгоритмите и програмирането
Анотация:
Курсът излага основните принципи и подходи за създаването на алгоритми и формализирането на типични за програмистката практика задачи. Въвеждат се и начални представи за числените методи, основаващи се на прости примери за алгоритми, тематично и терминологично обвързани с материал от курсовете по дискретна математика и анализ. Занятията са съчетание от лекционен материал, семинарни занятия с решаване на задачи и тестване на решения в компютърен клас. След всяко занятие, студентите получават задание за домашна работа, в което имат поставени задачи, пряко обвързани с разглежданото в часовете и нерядко - за задача да реализират програмно преподадените алгоритми, да направят разширени и усложнени варианти на съществуващите програми. Заданията за домашни работи се публикуват в Мудъл и студентите имат срок за предаването им през системата. Комплектът от предадени домашни се подлага на защита от всеки студент и представлява част от текущата семестриално оценка. Самостоятелните разработки по домашните задания се представят при явяване на изпит и са необходимо условие за провеждане на изпита.
Цели на курса:
? Да създаде програмистично и алгоритмично мислене
? Да даде основните принципи и подходи за създаването на алгоритми и формализирането на типични за програмистката практика задачи
? Да се разгледат и анализират прости примери за алгоритми
? Да създаде начални представи за сложност на алгоритмите, за числени методи
Преподавател(и):
проф. Велина Славова д-р
гл. ас. Филип Андонов д-р
Описание на курса:
Компетенции:
Успешно завършилите курса студенти:
1) знаят:
? що е алгоритъм и каква е връзката му с програмирането
? принципите на съставянето на несложни алгоритми и програми за тяхното изпълнение
? имат представа за понятието “сложност на алгоритъм”
2) могат:
? да програмират основни несложни алгоритми
? да разчитат алгоритмичния смисъл на програми, реализиращи несложни алгоритми
? да обвързват смислово материал от областите на математическия анализ, дискретната математика и алгоритмите
Предварителни изисквания:
Студентите да имат знания и/или умения:
• Самостоятелно логическо мислене
• Основни представи за изучаваното в средношнолската математика
• Владеене, на начално ниво, на произволен процедурен език за прорамиране
Форми на провеждане:
Редовен
Учебни форми:
Лекция
Език, на който се води курса:
Български
Теми, които се разглеждат в курса:
- RAM - машина. Елементи на управление на абстрактен автомат. Значение на условния и безусловния преход при управление на автомата. Примери. Алгоритъм на Евклид - преговор. Реализация на повтарението посредством условен и безусловен преход.
- Основи на структурното програмеране. Базови конструкти на управление. Клонове и повторения Схеми на управление като конструкти за управление на автомата. Реализиране на конструктите с готови езикови фрази нв използвани програмни езици.
- Машинен модел на множеството на целите числа. Препълване. Цикли по брояч. Алгоритъм за събиране в позиционна бройна система. Реализация с програма. Използване на операцията целочислено делене.
- Цикли по брояч. Натрупване на крайни суми и произведения. Формула на Гаус за сумата на първите ен естествени числа. Пресмятане на крайни суми и произведения - примерни програми.
- Рационални и реални числа - машинно представяне. Итерация и итеративни процеси, точност на решението. Изчислителни процедури за натрупване суми на алтелнативни редове. Примери – Пи, Синус, програмна реализация на итеративните изчислителни процедури.
- Тренировъчен семинар – решаване на задачи. Итерация. Точност на решението, загуба на точност. Конструктът „Дотогава, докато“ и конкгпуктът „Толкова пъти“. Влагане на цикли с обновяване на изчислението на база на вече изчисленото.
- Втора част. Задачата за претърсване. Обхождане. Котва. Дихотомия. Големина на входа. Начална представа за сложност на алгоритъм.
- Преговор - алторитъм за намиране на минимален/максимален елемент в масив. Сортиране - общи понятия. Какво е релация на наредба (в множеството на данните) - преговор от дискретната математика. Принцип на сортиране с извличане на минимален/максимален емемент - Сортиране в друг масив.
- Метод на Пряката селекция. Трасиране на алгоритама. Брой сравнения на стойности. Схема на броене. Тренировъчен семинар. Трасиране на алгоритъм. Съставяне на програма по даден изучен алгоритъм. Решаване на задачи.
- Инверсия. Схема на броене, прилагане на формулата на Гаус. Сортиране по метода на пряката размяна (мехурчето). Зависимост на алгоритъм от състоянието на входните данни. Значение на обхващащие цикъл по условие за наличие на инверсии. Най-добър и най-лош случай - оценка на брой сравнения. Задачи.
- Сортиране по метода на прякото вмъкмане. Зависимост на алгоритъм от състоянието на входните данни. Най-добър и най-лош случай - оценка на брой сравнения. Значение на вътрешния цикъл по условие, реализация с котва. Сравнителен анализ на сложността и поведението на изучените олгаритми за претърсване и сортиране.
- Работа с индекси. Задачи. Алгоригъм и програма за Умножение на матрици.
- Работа с индекси. Задачи. Алгоригъм и програма за за реализиране на Метода на Гаус за решаване на СЛУ (опростен вариант)
- Семинарно занятие - обсъждане и защита на самостоятелните разработки
- Контролна работа – тест през Мудъл – решаване на задачи и логически въпроси над мателиала.
Литература по темите:
1. Увод в алгоритмите и програмирането, Велина Славова, Станислав Иванов, НБУ, Планета 3, София 2003.
2. Niklaus Wirth, Algorithms and Data Structures. Oberon version 2004
3. Манев К. Увод в дискретната математика, учебник, издателство на НБУ, 1997
4. Cormen, Thomas H. (2013) Algorithms Unlocked, The MIT Press
Средства за оценяване:
1. Текущо оценяване по време на семестъра.
Базира се на предадените домашни (спазен срок) – 33%, на защитата на тези разработки – 33% и на контолната работа – 33%
От изпит се освбождават студентите, които получат семестриална оценка над 4.50 вкл. и нямат двойка по нита една от компонентите за текущо оценяване.
2. Изпит. Състои се от две части – решаване на задачи - тест пред Мудъл и събеседване, лазирано на самостоятелните разработки.