CSCB642 Математически модели със система за символно смятане

Анотация:

В курса се разглеждат 7 класически задачи на комбинаторната оптимизация и методите за тяхното решаване. Това са: задача за диета; транспортна задача; задача за раницата; задача за намиране на най-къс път в мрежа; максимален поток в мрежа; задача за назначението и задача за търговския пътник. При тяхното решение студентите се запознават с класически методи като: пълно изчерпване; динамично програмиране; разклоняване и граници и други. В курса се използва системата Mathematica като средство за изчисления и представяне на решенията.

прочети още
Информатика

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

проф. Марин Маринов  д-р

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

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

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

1) знания на методите за формализация на практически задачи;

2) знания на основни методи, използвани в линейно и целочисленото програмиране;

3) умения за: намиране оптимално решение в редица практически ситуации, като използват системата Mathematica


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

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



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

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

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

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

  1. Увод. Общо описание на системата MATHEMATICA. Тема 1. Оптимална диета и многомерна задача за разпределяне на ресурси. 1.1. Обща задача на линейното програмиране. (основни понятия и теореми.) 1.2. Геометрична илюстрация на основните понятия и теореми. 1.3. Функции на системата Mathematica за решаване на линейни оптимизационни задачи. 1.4. Геометричен метод в тримерното пространство.
  2. Тема 2. Транспортна задача. (Основни транспортни задачи. Методи за решаване. Обобщения.)
  3. Тема 3. Задача за раницата 3.1. Неограничена задача за раницата и понятие за динамично програмиране. 3.2. 0-1 задача за раницата. 3.3. Многомерна задача за раницата и метода разклоняване и граници.
  4. Тема 4. Най-къс път в мрежа. 4.1. Математически модел с понятия от теория на графите. 4.2. Основни алгоритми за намиране на най-къс път в мрежа (алгоритъм на Белман – Форд; алгоритъм на Дейкстра; случай когато мрежата няма контури). 4.3. Най-дълъг път в мрежа. 4.4. Решаване на задачите чрез линейно програмиране
  5. Тема 5. Максимален поток в мрежа. 5.1. Основен пример и основни понятия и твърдения 5.2. Алгоритъм на Форд и Фалкерсон 5.3. Изтласкване на предпоток 5.4. Решение на задачата за максималния поток със системата Mathematica
  6. Тема 6. Задача за назначението. 6.1. Основен пример. Математически модел. Метод на пълното изчерпване 6.2. Метод на линейното програмиране 6.3. Двуделни графи и унгарски алгоритъм за задачата за назначенията 6.4. Най-голямо и съвършено съчетание в двуделен граф. Алгоритъм на Хопкрофт – Карп за най-голямо съчетание
  7. Тема 7. Задача за търговския пътник 7.1. Основен пример и методи за решаване на задачата (метод на пълното изчерпване; евристични методи; метода Branch & Bound) 7.2. Обобщения

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

Литература

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

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

3) Маринов, М. (2008) Матрично смятане с Mathematica. С., Издателство на НБУ.

4) Славкова, М., (2000) Математически методи за оптимизация, ЕТ „Деиком“, С.

5) Маринов, М. , Л. Ласков, Математически модели за оптимизация , (в печат)

6) Gilbert Strang, "Linear Algebra and its Applications", Published by Saunders College Publishing.

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

8) James, M. Van Verth, Lars M. Bishop. Essential Mathematics for Games and Interactive Applications: Programmer’s Guide, 2004.

9) Site http://www.wolfram.com

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

Две самостоятелни работи

Защита на самостоятелна работа

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