anot

Анотация

Курсът подготовя студентите по Информатика за решаване на задачи, за които се изисква съставяне на по-сложни алгоритми. Изучава се целия път от поставяне на задачата до анализ на решенията - анализ на данните, преглед на съществуващи алгоритми за решаванети й, избиране на подходящ алгоритъм, модифициране на съществуващ или построяване на нов алгоритъм, избор на структури от данни, програмиране, тестване на програмата, анализ на ефективността на алгоритъма и програмата. Всички алгоритми се изучават заедно с най-ефективните им реализации като програми на С и С++.
Студентите трябва да знаят да програмират на С и/или С++.

Тематичен план

1. Стратегии при програмирането на алгоритмично трудни задачи. Оценка и сложност на алгоритми
2. Цели числа. представяне в десетична и двоична бройни системи. Прости числа. Мерсенови и съвършенни числа.
3. Рекурсия и итерация: факториел; редица на Фибоначи; най-голям общ делител; най-малко общо кратно.
4. Основни комбинаторни алгоритми: пермутации; вариации; комбинации.
5. Сортиране - общи положения; сортиране чрез сравнение; сортиране чрез трансформация
6. Последователно търсене, двоично и фибоначиево търсене
7. Динамично оптимиране - задача за раницата, "лесна" задачи, братска подялба, числа на Фибоначи и биномни коефициенти, най-дълга обща подредица
8. Разделяй и владей - намиране на k-тия по големина елемент, бързо умножение на дълги числа, циклично преместване на елементите на масив
9. Задачи с графи
10. Геометрични задачи
11. C++ Standard Template Library (STL) и използването й при решавене на задачи от състезания