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

проф. Марин Маринов  д-р
 Невяна Георгиева  

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

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

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

1) знаят:

- основни понятия и теореми от линейното програмиране,

- основни понятия и теореми за решаване на класически и трииндексни транспортни задачи,

- алгоритми за решаване на основните задачи за раницата,

- основни понятия от теория на графите и алгоритми за описание на всички критични пътища в мрежа,

- основните алгоритми за решаване на задачата за назначенията,

- основни алгоритми за намиране на максимален поток в мрежа,

- основни методи за решаване на задачата за търговския пътник;

2) могат:

- да използват възможностите на системата Mathematica за решаване на изучаваните задачи,

- да илюстрират с графики и анимации основни теореми и понятия от линейното програмиране,

- да реализират програми за решаване на разглежданите транспортни задачи,

- да реализират метода Branch & Bound за решаване на многомерната задача за раницата и задачата за търговския пътник,

- да реализират метода на динамичното програмиране за решаване на неограничената задача за раницата и 0-1 задачата за раницата,

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

Предварителни изисквания:
Достатъчни са знанията от гимназията и самостоятелна работа по време на занятия и върху самостоятелните работи.

Усвояването на материала би се улеснил, ако обучаемите имат начални знания по математика и информатика в обема на: CSCB038. Линейна алгебра; CSCB315. Аналитична геометрия; CSCB039 Алгоритми и програмиране.

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

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

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

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

1. Възможности на системата Mathematica за изчисления и програмиране. Реализиране на програма за намиране на върховете на многостенно множество.
2. Обща задача на линейното програмиране. Илюстрация на основните понятия и теореми.. Реализиране на програма за намиране на крайните лъчи на многостенно множество.
3. Решаване на задачата за линейното програмиране при n=3. Графична илюстрация.
4. Класическа транспортна задача. Варианти.
5. Трииндексни транспортни задачи.
6. Понятие за динамично програмиране. Неограничена задача за раницата. 0-1 задача за раницата.
7. Многомерна задача за раницата и метода Branch & Bound.
8. Контролна работа №1.
9. Критичен път в мрежа. Алгоритъм на Белман – Форд. Топологично сортиране на мрежа.
10. Алгоритъм на Дейкстра. Намиране на всички критични пътища.
11. Унгарски алгоритъм за решаване на задачата за назначенията.
12. Експериментално сравняване на методите: пълно изчерпване, линейно програмиране и унгарски алгоритъм за задачата за назначенията.
13. Алгоритъм на Форд и Фалкерсон за намиране на максимален поток.
14. Контролна работа №2.
15. Задача за търговския пътник. Метод на пълно изчерпване, евристични методи и метода Branch & Bound.

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

[1] Иванов, Г. и др. (1989), Ръководство за решаване на задачи по математическо оптимиране, С., УИ ” Климент Охридски“

[2] Кендеров, П., Г. Христов, Ас. Дончев. (1989) Математическо оптимиране, С., УИ ” Климент Охридски“

[3] Маринов, М. (2008) Матрично смятане с Mathematica. София, ”Planeta 3“

[4] Cormen, Thomas H. (2009) Introduction to Algorithms (Third Edition). Cambridge, Massachusetts; London, England : Massachusetts Institute of Technology

[5] Nicos Christofides (1975) Graph Theory. An Algorithmic Approach (Computer Science and Applied Mathematics), Academic Press, New York, London, San Francisco

[6] Ланджев Ив., Ася Русева, (2023), Аспекти на комбинаториката

[7] Манев, Кр. (2013) Алгоритми в графи: Основни алгоритми. София : КЛМН

[8] Site http://www.wolfram.com

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

Две контролни работи

Защита на контролните работи

Финално оценяване: писмен изпит и защита на самостоятелна работа