CSCB214 Увод в алгоритмите и програмирането
Анотация:
Курсът излага основните принципи и подходи за създаването на алгоритми и формализирането на типични за програмистката практика задачи. Въвеждат се и начални представи за числените методи, основаващи се на прости примери за алгоритми, тематично и терминологично обвързани с материал от курсовете по дискретна математика и анализ. Занятията са съчетание от лекционен материал, семинарни занятия с решаване на задачи и тестване на решения в компютърен клас. След всяко занятие, студентите получават задание за домашна работа, в което имат поставени задачи, пряко обвързани с разглежданото в часовете и нерядко - за задача да реализират програмно преподадените алгоритми, да направят разширени и усложнени варианти на съществуващите програми. Заданията за домашни работи се публикуват в Мудъл и студентите имат срок за предаването им пред системата. Комплектът от предадени домашни се подлага на защита от всеки студент и представлява част от текущата семестриално оценка. Самостоятелните разработки по домашните задания се представят при явяване на изпит и са необходимо условие за провеждане на изпита.
Цели на курса:
Да създаде програмистично и алгоритмично мислене
Да даде основните принципи и подходи за създаването на алгоритми и формализирането на типични за програмистката практика задачи
Да се разгледат и анализират прости примери за алгоритми
Да създаде начални представи за сложност на алгоритмите, за числени методи
Преподавател(и):
проф. Велина Славова д-р
гл. ас. Филип Андонов д-р
Описание на курса:
Компетенции:
Успешно завършилите курса студенти:
1) знаят:
що е алгоритъм и каква е връзката му с програмирането
принципите на съставянето на несложни алгоритми и програми за тяхното изпълнение
имат представа за понятието “сложност на алгоритъм”
2) могат:
да програмират основни несложни алгоритми
да разчитат алгоритмичния смисъл на програми, реализиращи несложни алгоритми
да обвързват смислово материал от областите на математическия анализ, дискретната математика и алгоритмите
Предварителни изисквания:
Студентите да имат знания и/или умения:
• Самостоятелно логическо мислене
• Основни представи за изучаваното в средношнолската математика
• Владеене, на начално ниво, на произволен процедурен език за прорамиране
Форми на провеждане:
Редовен
Учебни форми:
Лекция
Език, на който се води курса:
Български
Теми, които се разглеждат в курса:
- Увод. RAM - машина. Елементи на управление на абстрактен автомат. Примери. Алгоритъм на Евклид - преговор.
- Базови конструкти на управление. Клонове, повторения. Машинен модел на множеството на целите числа. Алгоритъм за събиране в позиционна бройна система. Използване на операцията целочислено делене.
- Машинни модели на числата. Цели числа, препълвяне. Натрупване на суми и произведения. Формула на Гаус за първите ен естествени числа. Рационални и реални числа. Натрупване на безкрайни алтелнативни редове. Пи. Синус и косинус.
- Тренировъчен семинар – решаване на задачи. Итерация. Точност на решението, загуба на точност. Конструктът „Дотогава, докато“ и конкгпуктът „Толкова пъти“. Табулиране на функция. Подготовка за решаване на уравнение по метода на сканиране на интервала. Влагане на цикли с обновяване на изчислението на база на вече изчисленото.
- Задачата за претърсване. Обхождане. Дихотомия. Големина на входа. Начална представа за сложност на алгоритъм.
- Преговор - алторитъм за намиране на минимален/максимален елемент в масив. Сортиране - общи понятия. Какво е релация на наредба (в множеството на данните) - преговор от дискретната математика. Принцип на сортиране с извличане на минимален/максимален емемент - Сортиране в друг масив.
- Метод на Пряката селекция. Трасиране на алгоритама. Брой сравнения на стойности. Схема на броене. Инверсия.
- Тренировъчен семинар. Трасиране на алгоритъм. Съставяне на програма по даден изучен алгоритъм. Решаване на задачи.
- Сортиране по метода на пряката размяна (мехурчето). Зависимост на алгоритъм от състоянието на входните данни. Най-добър и най-лош случай - оценка на брой сравнения. Задачи.
- Сортиране по метода на прякото вмъкмане. Зависимост на алгоритъм от състоянието на входните данни. Най-добър и най-лош случай - оценка на брой сравнения. Задачи.
- Понятие за сложност по време. Начална представа за асимптотична нотация. Сравнителен анализ на сложнастта и поведението на изучените олгаритми за претърсване и сортиране. Съчетаване на алгоритмични подходи.
- Работа с индекси. Задачи. Алгоригъм и програма за Умножение на матрици.
- Работа с индекси. Задачи. Алгоригъм и програма за Метода на Гаус за решаване на СЛУ (опростен вариант)
- Контолна работа – писмена – решаване на задачи
- Защита на самостоятелните работи
Литература по темите:
1. Увод в алгоритмите и програмирането, Велина Славова, Станислав Иванов, НБУ, Планета 3, София 2003.
2. Киндлер Е. Языки моделирования М. 1985
3. Манев К. Увод в дискретната математика, учебник, издателство на НБУ, 1997
4. Всяка книга по програмиране на Паскал, С, Делфи.
Средства за оценяване:
1. Текущо оценяване по време на семестъра.
Базира се на предадените домашни (спазен срок) – 33%, на защитата на тези разработки – 33% и на контолната работа – 33%
От изпит се освбождават студентите, които получат семестриална оценка над 4.50 вкл.
2. Изпит. Състои се от две части – решаване на задачи и събеседване