Задачі, змiст дисциплiни "Алгоритми та методи обчислювань", страница 2

       Базові  положення  теорії   приближення   функцій  та  класифікація    методів апроксимації. Локальна інтерполяція:   лінійна,   квадратична   та   кубічні   інтерполяційні сплайни. Глобальна інтерполяція: інтерполяційні многочлени Лагранжа.

     Побудова   емпіричної   аналітичної   залежності    вихідної     характеристики системи. Визначення величин, які неможливо спостерігати,  за  результатами   вимірювання інших величин, що являються їх функціями.

     Можливості   програмного   середовища   МАТLAB  щодо   вирішення   задач апроксимації.

Тема3. Методи рішення систем лінійних алгебраїчних рівнянь (10 годин)

    Класифікаційна схема методів рішення систем рівнянь та класифікаційна  схема   взаємозв’язку   умов     сумісності   систем    лінійних алгебраїчних   рівнянь   (СЛАР)   та  умов,   при   яких   однорідна   СЛАР    має  нетривіальне  рішення. 

    Ітераційні методи рішення систем  лінійних алгебраїчних рівнянь: метод простих ітерацій,

метод Гауса-Зейделя.

    Можливості програмного   середовища   МАТLAB  щодо   вирішення  СЛАР.

     Тема4. Теоретико-числові алгоритми та методи обчислювань (6 годин)

     Основні поняття теорії чисел: прості та взаємно-прості числа, алгоритм Євкліда. Елементи теорії порівнянь: повний та приведений набори вичетів за даним модулем, квадратичні вичети за даним модулем.  Функція Ейлера, її властивості та способи  визначення. Теорема Ейлера-Ферма.

    Методи вирішення порівняння  ax = b(mod n). Китайська теорема про остачу.

   Можливості    програмного    середовища     МАТLAB      щодо       виконання теоретико-числових перетворень.

РозділII.Алгоритми та методи обчислювань, спрямовані на вирішення задач оптимізації(42 години)

Тема 5.  Загальна характеристика методів оптимізації (3 годин)

     Постановка задачі оптимізації.  Класифікація і загальна характеристика  методів оптимізації. Умовна та безумовна оптимізація.

     Можливості  програмного   середовища   МАТLAB   щодо   вирішення   задач оптимізації.

Тема 6. Нелінійна оптимізація (9 годин)

    Класифікація та  загальна характеристика методів нелінійної оптимізації. Постановка задачі квадратичного програмування.

    Безумовна нелінійна оптимізація: метод найскорішого спуску. Умовна нелінійна оптимізація: метод невизначених множників Лагранжа.

Тема 7. Лінійна оптимізація (17 годин)

     Базові  поняття з області  лінійного програмування: приклади  задач лінійного програмування (ЗЛП); основна ЗЛП  та  умови наявності  у  неї  допустимого  рішення;  ЗЛП  з 

обмеженнями-нерівностями  та перехід  від  неї  до канонічної форми ЗЛП.

    Геометрична інтерпретація ЗЛП.

  Симплекс-метод рішення задачі лінійного програмування: загальна   ідея   симплекс-методу    та    її    зв’язок   з   геометрично   інтерпретацією ЗЛП, стандартна форма представлення загальної ЗЛП, алгоритм рішення ЗЛП симплекс-методом.

    Рішення задачі лінійного програмування на основі табличного алгоритму симплекс-методу:

узагальнений алгоритм рішення ЗЛП за допомогою симплекс-таблиць, алгоритм пошуку припустимого рішення ЗЛП, алгоритм пошуку оптимального рішення ЗЛП.

   Двойствені  задачі  лінійного  програмування.    Основна   теорема  двойственості.

Тема 8. Дискретна оптимізація (3 годин)

    Загальна постановка задачі дискретної оптимізації.  Постановка  найбільш  розповсюджених    задач   дискретної   оптимізації   та особливості методів їх вирішення.

   Послідовність рішення  задачі  цілочисельного  лінійного  програмування  за допомогою методу відсікання Гоморі.

   Загальна ідея методу гілок та границь.

Тема 9. Динамічне програмування (3 години)

   Загальна ідея і область застосування методу динамічного програмування.    Постановка задачі  динамічного програмування.

   Вирішення задачі визначення критичних шляхів мережі за допомогою методу динамічного програмування.

Лабораторні заняття

1. Застосування програмного  середовища  МАТLAB  в  режимі  прямих  обчислювань.

2. Вирішення   задач   апроксимації   та   нестатистичної   обробки    результатів  обчислювального експерименту.

3. Методи  рішення   систем    лінійних  алгебраїчних   рівнянь

4. Рішення     задач      нелінійної    оптимізації     із     застосуванням        пакета Optimization  Toolbox програмного середовища MATLAB.

5. Рішення    задачі     лінійного    програмування     із    застосуванням     пакета Optimization  Toolbox програмного середовища MATLAB.