БУРГАСКИ СВОБОДЕН УНИВЕРСИТЕТ
НОВ БЪЛГАРСКИ УНИВЕРСИТЕТ
ИНСТИТУТ ПО МАТЕМАТИКА И ИНФОРМАТИКА - БАН

УЧЕБНА ПРОГРАМА
Учебна дисциплина: Програмиране за напреднали
Специалност: Информатика
Степен на обучение: Бакалавър
Форма на обучение: Редовно
Автор: доц. Николай Киров
София, 2002 г.

СТРУКТУРА НА УЧЕБНАТА ПРОГРАМА
Вид занятие - практикум
Семестър - С
Хорариум седмично - 2 часа, общо 30 часа
Форма на оценяване - курсов проект

АНОТАЦИЯ НА КУРСА:
    Курсът подготовя студентите по Информатика за решаване на задачи, за които се изисква съставяне на по-сложни алгоритми. Изучава се целия път от поставяне на задачата до анализ на решенията - анализ на данните, преглед на съществуващи алгоритми за решаванети й, избиране на подходящ алгоритъм, модифициране на съществуващ или построяване на нов алгоритъм, избор на структури от данни, програмиране, тестване на програмата, анализ на ефективността на алгоритъма и програмата. Занятията са в компютърна зала и студентите имат възможност както сами да решават поставените задачи така и да проверяват веднага разглежданите алгоритми. Всички алгоритми се изучават заедно с най-ефективните им реализации като програми на С и С++.
    Студентите трябва да знаят да програмират на С и/или С++.

СЪДЪРЖАНИЕ НА УЧЕБНАТА ПРОГРАМА

1. Въведение и анализ на алгоритми - 4 часа, доц. Николай Киров - БСУ и ИМИ, БАН
1.1 Технология на провеждане на студентски състезания по програмиране.
1.2 Техника на програмирането на състезания по програмиране.
1.3 Задача за свързаност - различни решения и оценка на ефективността на всяко решение.
1.4 Принципи на анализа на алгоритми.

2. Структури от данни - 4 часа, доц. Николай Киров
2.1 Масиви - задачи за симулации с подхвърляне на монета и изчисляване на най-близки точки.
2.2 Свързани списъци - задача на Йосиф, обръщане на свързан списък, намиране на n-ти най-малък елемент.
2.3 Съставни структури от данни - двумерен масив. Сортиране на масив от низове.
2.4 Представяне на граф с матрица на съседство и чрез списъци на съседство.

3. Аритметика и комбинаторика - 4 часа: проф. Иван Ланджев - БСУ и ИМИ, БАН.
3.1 Делимост на числата, бройни системи.
3.2 Дълги числа, полиномиална аритметика.
3.3 Съчетания без повторения и с повторения, разбивания, преброяване.
3.4 Задачи от компресия и криптография

4. Графи - 4 часа: доц. Красимир Манев - СУ, ФМИ.
4.1 Представяне и елементарни методи - търсене в дълбочина и ширина, ойлерови и хамилтонови цикли и др.)
4.2 Свързаност
4.3 Графи с тегла - най-къс път, минимално покриващо дърво и др.
4.4 Ориентирани графи - топологическо сортиране и др.

5. Два метода за съставяне на алгоритми - 4 часа: доц. Николай Киров
5.1 Пълно изчерпване
5.2 Търсене с връщане
5.3 Задаване и работа по курсови проекти
5.4 Вътрешно блиц-състезание

6. Нестандартни задачи и подходи за решаването им - 4 часа: Кристиян Хараламбиев - ФМИ, СУ.

7. Рекурсивни алгоритми, разделяй и владей - 4 часа: доц. Николай Киров
7.1 Рекурсия - задача за изчисляване на префиксни изрази
7.2 Задачи за ханойските кули и изчертаване на линийка
7.3 Оценка на метода разделяй и владей
7.4 Работа по курсови проекти

8. Защита на курсови проекти - 2 часа: доц. Николай Киров

Литература:
[1] Преслав Наков, Основи на компютърните алгоритми, TopTeam Co., 2000.
[2] Никлаус Уирт, Алгоритми + структури от данни = програми, Техника, София, 1980. (Оригинал: Niklaus Wirth, Algorithms + Data Structures = Programs, Prentice-Hall, Inc., Englewood Cliffs, 1975.)
[3] Лендерт Амерал, Алгоритми и структури от данни в С++, ИК "Софтех", София, 2001.
[4] Емил Келеведжиев, Динамично опримиране, Мусала Софт и Анубис, София 2001.
[5] Джон Монтаг, Ноа Суджанен, Интервюта за програмисти, ИК "Софтех", София, 2002.
[6] Робърт Седжуик, Алгоритми на С. Том 1 и 2, ИК "Софтех", София, 2002.
[7] Ellis Horowitz, Sartaj Sahni, Fundamentals of computer algorithms, Computre Science Press