Оптимізація в неперервних та дискретних структурах

Мета вивчення дисципліни: формування у студентів знань основних понять, фактів, методів цілочислової оптимізації; ознайомлення із характерними прикладами їх застосування; оволодіння уміннями розв’язувати деякі класи оптимізаційних задач, вивчення основних математичних методів безумовної та умовної оптимізації; вивчення типових оптимізаційних задач та методів їх формального опису; оволодіння теоретичними основами методів оптимізації; отримання знань, які стосуються застосування чисельної теорії оптимізації; отримання теоретичних знань та практичних навичок щодо освоєння технологій оптимізації і моделювання технологічних процесів.

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

Результати навчання

ПРН01. Мати передові концептуальні та методологічні знання з інженерії програмного забезпечення та дотичних до неї міждисциплінарних напрямів, а також дослідницькі навички, достатні для проведення наукових і прикладних досліджень на рівні останніх світових досягнень з відповідного напряму, отримання нових знань та/або здійснення інновацій.
ПРН02. Планувати і виконувати експериментальні та/або теоретичні дослідження з інженерії програмного забезпечення та дотичних міждисциплінарних напрямів з використанням сучасних інструментів та дотриманням норм академічної і професійної етики, критично аналізувати результати власних досліджень і результати інших дослідників у контексті усього комплексу сучасних знань щодо досліджуваної проблеми.
ПРН05. Застосовувати сучасні інструменти і технології пошуку, оброблення та аналізу інформації, зокрема, статистичні методи аналізу даних великого обсягу та/або складної структури, спеціалізовані бази даних та інформаційні системи для покращення ефективності програмних систем.
ПРН07. Розробляти та досліджувати концептуальні, математичні і комп’ютерні моделі процесів і систем для отримання нових знань та/або створення інноваційних продуктів у галузі інженерії програмного забезпечення та дотичних міждисциплінарних напрямах.
ПРН09. Формулювати та розв’язувати задачі оптимізації, адаптації, прогнозування, керування та прийняття рішень щодо процесів, засобів та ресурсів розробки, впровадження, супроводу та експлуатації програмного забезпечення.
ПРН10. Аналізувати та оцінювати стан і перспективи розвитку інженерії програмного забезпечення та інформаційних технологій у цілому.

Тематика та види навчальних занять

Лекційні заняття
Лекція 1. «Предмет та задачі курсу «Оптимізація в неперервних та дискретних структурах». Базові поняття теорії дискретних структур і алгоритмів їх обробки».
Лекція 2. «Поняття дискретної структури даних. Прості структури даних. Структури даних «зв’язаний список». Нелінійні структури даних».
Лекція 3. «Алгоритми пошуку над дискретними структурами. Алгоритми сортування дискретних даних. Хешування даних».
Лекція 4. «Аналіз неперервної оптимізації. Неперервна змінна оптимізація. Методи вирішення завдань неперервної оптимізації».
Лекція 5. «Логіка висловлень. Умовиводи. Способи перевірки правильності умовиводів».
Лекція 6. «Основні поняття теорії автоматів. Автоматні відображення. Класифікація автоматів. Обчислювальні автомати».
Лекція 7. «Задачі динамічного програмування. Метод рекурентних співвідношень. Математичні моделі та їх види. Класична задача оптимізації».
Лекція 8. «Чисельні методи одномірної оптимізації нульового порядку, безумовної оптимізації першого та другого порядку. Методи лінійного та нелінійного програмування».

Практичні заняття
Практичне заняття №1. «Елементи теорії множин і відношень. Побудова остового дерева мінімальної вартості».
Мета заняття: вивчити теоретичні методи аналізу і синтезу дискретних об’єктів, що застосовуються при проектуванні сучасних засобів обчислюваної техніки, набути практичних навичок щодо їх використання.
Практичне заняття №2. «З’ясування зв’язності графів. Елементи математичної логіки. Моделювання лінійних неперервних систем засобами пакета Simulink».
Мета заняття: уяснити принципи переходу від математичного опису до побудови структурних схем. засвоїти методику створення, редагування та експлуатації структурних математичних моделей в середовищі MATLAB-Simulink.
Практичне заняття №3. «Моделювання лінійних неперервних систем засобами пакета Simulink».
Мета заняття: розглянути питання математичного опису та побудови структурних моделей лінійних та нелінійних стаціонарних динамічних систем.
Практичне заняття №4. «Теорія автоматів. Клітинні автомати. Автоматні схеми. Мови програмування і формальні граматичні структури».
Мета заняття: придбання студентами знань із прикладної теорії цифрових і керуючих автоматів, вивчення математичних основ теорії автоматів та їх структурних моделей.
Практичне заняття №5. «Методи формальних описів та аналізу протоколів. Методи градієнтного типу в задачах умовної та безумовної оптимізації».
Мета заняття: висвітлити методи одномірної оптимізації функцій, включаючи градієнтні та методи нульового порядку, класичні підходи до вирішення задач умовної оптимізації, методи багатомірної оптимізації та лінійного програмування.
Практичне заняття №6. «Задачі опуклого програмування. Двоїсті задачі. Методи локального випадкового пошуку. Методи, які використовують функції Лагранжа».
Мета заняття: оволодіння базовими навичками розв’язання типових задач теорії оптимізації систем великої розмірності.
Практичне заняття №7. «Оптимальні системи управління. Проектування оптимального лінійно-квадратичного регулятора з використанням Matlab та Simulink».
Мета заняття: формування навичок використання методів оптимізації при проектуванні систем, плануванні і аналізі функціонування існуючих систем, керуванні динамічними системами.

Консультації здійснюються впродовж семестру згідно встановленого розкладу.

Форми контрольних заходів та оцінювання результатів навчання

Поточний контроль полягає у виконанні:
1) семи практичних робіт. Бездоганне виконання індивідуальних поточних завдань №1 та №2 оцінюється у 5 балів кожне; індивідуальних поточних завдань №3–№7 – у 10,0 балів кожне. Всього бездоганне виконання практичних занять оцінюється у 60 балів.
2) двох модульних контрольних робіт. Модульні контрольні роботи складаються з теоретичної і практичної частин та проводяться у формі комп'ютерного тестування. Бездоганне виконання кожної модульної контрольної роботи становить 20 балів. Всього 40 балів.

Підсумковий контроль – екзамен (усний), білет до якого складається з трьох запитань (одне теоретичне і два практичних). Максимальна оцінка за правильні відповіді на всі питання екзаменаційного білету становить 100 балів, мінімальна оцінка становить 60 балів.