ІНСТИТУТ КОМП’ЮТЕРНИХ НАУК ТА ІНФОРМАЦІЙНИХ ТЕХНОЛОГІЙ Напрям: Компютерні науки Спеціальність: Інформаційні управляючі системита технології (0302)I. Математичні методи дослідження операцій1. Вступ. Основні поняття та методологія ДОІсторія розвитку та використання методів дослідження операцій (ДО). Наукова суть ДО. Області практичних застосувань методів ДО та мета його вивчення. Основні поняття ДО: операція, оперуюча сторона, стратегія, стан, діючі фактори операції, критерії ефективності. Методологія проведення операційного дослідження: визначення мети; складання плану розробки; формулювання проблеми; побудова математичної моделі; синтез та (або) обґрунтування математичного методу; опрацювання інформації; перевірка адекватності моделі; реалізація результатів. Пряма та обернена задачі ДО. Класифікація моделей ДО. Поняття про детерміновані та стохастичні моделі ДО і основні підходи до їх розв’язування. Проблема багатокритеріальності та її розв’язування; згортка критеріїв, переведення критеріїв в обмеження, методи послідовних поступок, діалогові методи. 2. Класичні задачі лінійного програмування (ЛП)Поняття про задачу математичного програмування (МП). Загальна постановка та класифікація задач МП, поняття складності алгоритмів розв’язування задач МП. Побудова математичних моделей задач ДО. Лінійні моделі та зв’язані з ними спрощення дійсності: пропорційність і адитивність. Загальна канонічна форма задачі ЛП. Графічне розв’язування задач ЛП. Поняття про основні задачі аналізу лінійних моделей на чутливість: статус та допустимі межі зміни ресурсів, цінність ресурсів, чутливість функції мети. Базисні розв’язки задачі ЛП. Основні теореми ЛП. Алгоритм симплекс-методу та його таблична форма. Умови оптимальності та допустимості. Особливі випадки симплекс-методу. Методи знаходження початкового базису: двоетапний та метод великих штрафів. Двоїстість у задачах ЛП. Поняття прямої та двоїстої задач ЛП. Основні теореми двоїстості. Економічна інтерпретація двоїстості. Поняття про методи розв’язування задач ЛП великої розмірності та особливої структури. Методи декомпозиції, розріджені матриці, особливості реалізації алгоритмів. Модель транспортної задачі ЛП. Приклади транспортних задач (ТЗ). Методи побудови опорного плану ТЗ: північно-західного кута, мінімального елементу, евристичний метод Фойгеля. Методи знаходження оптимального плану ТЗ (метод потенціалів і розподільчий). Теореми про потенціали. Транспортні задачі з особливостями в формулюванні, їх виродженість. 3. Задачі на мережахЗагальні поняття мережі, потоку. Властивості потоку. Теорема Форда-Фалкерсона про максимальний потік і мінімальний розріз. Постановка задачі про максимальний потік мінімальної вартості. Основні типи потокових задач як частинні випадки загальної. Задача про найкоротший ланцюг. Алгоритм Дейкстри. Задача про багатополюсний найкоротший ланцюг. Алгоритм Флойда. Задача про знаходження максимального потоку та її застосування. Алгоритм розташування позначок. Поняття про методи управління проектами. Послідовність розв’язування задач управління проектами. Параметри мережі: ранні та пізні терміни здійснення подій і робіт, критичний шлях. Резерви часу подій і робіт. Метод критичного шляху (CRМ). Схематичні моделі управління проектами. Метод PERT. 4. Задачі цілочисельного програмуванняОсобливості цілочисельних задач. Цілочисельні моделі практичних задач. Загальна характеристика основних груп методів розв’язування цілочисельних задач: відсічень, комбінаторних, евристичних. Принципи побудови евристичних алгоритмів. Основні ідеї методів відсічень. Метод Гоморі, його недоліки. Метод вектора спаду. Схема методу гілок і границь та її основні структурні елементи: стратегії розгалуження, границі та їх властивості, стратегія відтинання вузлів. Проблеми представлення цілочисельних задач і процесу їх розв’язування в ЕОМ. 5. Теорія ігорОсновні поняття теорії ігор: учасники гри, стратегії, виграші. Класифікація ігор за ознаками: кількість гравців, потужність множини стратегій; характер взаємодії гравців, розмір виграшів, вид функції виграшів, кількість і характер ходів, інформованість. Загальна характеристика методів розв’язування ігор. Матричні ігри двох осіб з нульовою сумою. Означення, приклади. Розв’язки в чистих стратегіях. Нижня й верхня ціна гри. Сідлова точка та чиста ціна гри. Оптимальні чисті стратегії. Теореми про ціну гри і максимін. Оптимальні змішані стратегії та їхні властивості. Ціна гри в змішаних стратегіях. Основна теорема матричних ігор. Геометричне розв’язування ігор розміром 2x2, 2xn, mx2. Поняття про кооперативні ігри. Біматричні ігри та положення рівноваги в біматричних іграх. Позиційні ігри. Нормальна форма позиційної гри. Графічна форма позиційної гри. Позиційні ігри з повною й неповною інформацією та обмеженою пам’яттю. Поняття про антагоністичні ігри, ігри з функцією виграшу, сепарабельні ігри. 6. Нелінійне програмуванняЗадачі нелінійного програмування та основні труднощі їх розв’язування. Класичний метод оптимізації та метод множників Лагранжа. Метод множників Лагранжа та теорія двоїстості. Необхідні й достатні умови існування сідлової точки. Теорема Куна – Такера. Квадратичне програмування. Метод Вольфа. Геометричне програмування. Задачі опуклого програмування. Прямі методи 1-мірного числового пошуку: дихотомії, золотого перетину, Фібоначчі. Непрямі числові методи пошуку безумовного екстремуму функцій: градієнтні, спряжених напрямків, змінної метрики. Числові методи штрафних функцій і бар’єрних поверхонь у задачах умовної оптимізації функцій. 7. Задачі варіаційного численняНайпростіша задача варіаційного числення. Формалізація, множина допустимих розв’язків, коректність задач оптимізації. Рівняння Ейлера-Пуасона. Багатокритерійні оптимізаційні задачі. Задачі оптимального управління. 8. Динамічне програмуванняОсновні поняття динамічного програмування. Загальна постановка задачі динамічного програмування та її геометрична інтерпретація. Принципи оптимальності Белмана та “прокляття розмірності”. Найпростіші економічні задачі, які розв’язуються за допомогою методу динамічного програмування. Рекурентні співвідношення в задачах динамічного програмування. Задачі з адитивною та мультиплікативною функцією мети. Метод функціональних рівнянь. Багатовимірні задачі динамічної оптимізації. Поняття про стохастичні задачі динамічного програмування. 9. Моделі управління запасамиЗагальна постановка задачі управління запасами. Класифікація моделей управління запасами. Загальна характеристика методів розв’язування задач управління запасами. Детерміновані моделі управління запасами: однопродуктова статична модель; однопродуктова модель з розривами цін; багатопродуктова статична модель з обмеженням на ємність складів. Однопродуктова модель динамічного управління за скінченну кількість періодів; постійні та спадні граничні витрати; календарне планування виробництва на скінченну кількість етапів. 10. Задачі побудови розкладівКласифікація задач побудови розкладів. Критерій оцінки якості розкладів. Складання розкладів для одного верстату. Перестановочні розклади. Евристичні методи побудови розкладів. Правила впорядкування. Впорядкування при наявності обмежень на можливі варіанти розкладів. Складання розкладів для паралельних верстатів. Розклади для систем конвеєрного типу. Алгоритм Джонсона для конвеєрної системи двох верстатів. Методи розв’язування задач побудови розкладів для складання конвеєрних систем. ^ II. Об’єктно-орієнтоване програмування1. Основні поняття та методологія ООПОсновні поняття ООП. Природа класу та об’єкта, взаємозв’язок між ними. 2. Класи та обєктиВизначення та ідентифікація класів та об’єктів. Конструктор деструктор. Типи методів. Поля методи властивості. 3. Основні принципи ООПАбстракція. Інкапсуляція. Наслідування. Поліморфізм. 4. Характеристика правил повторного використання кодуТипи ієрархій. Правила наслідування. Перевантаження. Заміщення. Уточнення. 5. Стандартні класиІєрархія класів. Бібліотека візуальних компонент. ^ III. Програмування1. Загальна характеристика програмного забезпечення комп’ютерівКласифікація програмного забезпечення. Системні та прикладні програми. Характеристика мов програмування за рівнями. Системи програмування. Етапи виконання програми. Внутрішні форми збереження числових і символьних даних. Основні риси мови програмування С. Структура С-програми. 2. Базові елементи мови СЛексеми. Типи даних. Директиви препроцесору. Бібліотечні функції. 3. Вирази та операціїАрифметичні та порозрядні операції. Операції порівняння та логічні операції. Операції присвоєння, комбіновані присвоєння. Умовна операція та операція розміру sizeof. Порядок виконання операцій. Узгодження типів операндів у виразах. 4. Оператори мови СОператори-вирази: присвоєння, виклик функції, пустий оператор. Умовні оператори: if, switch. Оператори циклу: for, while, do-while. Оператори переходу: goto, break, continue, return. 5. Вказівники та масивиОголошення вказівників, звертання до даних через вказівники. Адресна арифметика. Оголошення та ініціалізація масивів. Звертання до елементів масиву через індекси і через вказівники. Багатовимірні масиви6. Символьні рядкиОголошення та ініціалізація символьних рядків. Звертання до елементів символьних рядків. Введення-виведення символів і символьних рядків. Бібліотечні функції для роботи із символами та символьними рядками: функції функції класифікації і перетворення символів, функції операцій над символьними рядками, функції перетворення рядків символів у числа та зворотніх перетворень. Масиви символьних рядків і масиви вказівників на символи. 7. Структури та об’єднанняСтруктури: оголошення, ініціалізація, присвоєння. Звертання до полів структури. Об’єднання. Декларація перейменування типів typedef. 8. Введення-виведення, обмін даними з файламиФайли і потоки, буферизація даних. Відкриття і закриття потоків, аналіз помилок. Функції потокового введення-виведення: посимвольний обмін, обмін рядками символів, обмін блоками даних. Форматне введення-виведення даних, специфікації формату. Керування поточною позицією файла. Витирання та перейменування файлів. 9. ФункціїСтруктура функцій. Виклик функцій. Прототипи функцій. Взаємодія фактичних і формальних параметрів. Масиви і символьні рядки як параметри функцій. Опрацювання структур у функціях. Вказівники на функції. Рекурсивні функції. Функції з неоголошеними параметрами. Робота з параметрами командного рядка. 10. Робота з даними в динамічній пам’ятіСтандартні функції динамічного виділення та звільнення пам’яті. Створення масивів вказівників на динамічні дані. Різновиди динамічних списків, операції над списками. ^ IV. Комп'ютери і мікропроцесорні системи1. Архітектурні принципи побудови обчислювальних засобівТипи обчислювальних засобів і комп’ютерів. Базові архітектури комп’ютерів і мікропроцесорних систем. Експлуатаційні характеристики комп’ютерних засобів. Шляхи підвищення продуктивності обчислювальних засобів. 2. Системи численняВластивості систем числення. Непозиційні системи числення. Арифметичні операції в системі остач. 3. Архітектура пам’яті комп’ютерівТипи запам’ятовувальних пристроїв. Постійні запам’ятовувальні пристрої. Запам’ятовувальні пристрої з довільним звертанням. Запам’ятовувальні пристрої для оперативної роботи з основною пам’яттю та архівного збереження даних. 4. Паралельна обробка данихПринципи розпаралелювання. Конвеєризація обчислень. Паралельні архітектури комп’ютерів. 5. Принципи побудови мікропроцесорних системАрхітектура однокристальних мікропроцесорів. Основи синтезу мікропроцесорних систем. Програмне забезпечення мікропроцесорних систем. Мікроконтролери та контролери. Апаратні засоби мікропроцесорних систем. 6. Основи програмування мікропроцесорних системСистеми команд однокристальних мікропроцесорів. Способи адресації. Програмування спеціалізованих ВІС. Мова Асемблера. 7. Архітектура нейрокомп’ютерівЗагальні засади, що лежать в основі нейрокомп’ютерів. Базові нейропарадигми. Основи застосування нейрокомп’ютерів. ^ V. Основи системного аналізу проектування комп'ютерних інформаційних технологій1. Принципи системного аналізуКласифікація і аналіз. Принципи об’єднання в класи. Ознаки та властивості систем. Параметри системи та елементів. Мета створення системи. Поняття структури системи. Функції елементів системи. 2. Системи та об’єктиПроцес функціонування. Режим функціонування. Поняття стану системи. Алгоритм функціонування. Алгоритм управління. Критерії управління системою. Структурна схема системи. 3. Системна філософіяМета функціонування. Ефективність функціонування систем. Типи систем. Інформаційні потоки. Події в системах. Класифікація подій. Взаємодія між подіями. Системи без зворотного зв’язку. 4. Елементи системПерехід від безперервних параметрів до дискретних. Система як об’єднання та композиція підсистем. Класифікація підсистем. Взаємодія підсистем. Критичні елементи системи. 5. Класифікація системЦентралізовані системи. Децентралізовані системи. Розподілені системи. Змішані системи. 6. Складність системиСтруктурні одиниці. Функціональні елементи. Функціональні схеми. Методи дослідження систем. Стійкість систем в прямуванні до мети. Критерії повноти системи. 7. Властивості системАлгебраїчні системи. Мови опису систем. Принципи та стратегії управління. Критичні і нормальні стани. Поняття еквівалентності систем. Подібність систем. 8. Функції елементів і системиВиділення функціональних і структурних підсистем. Метод декомпозиції систем. Метод композиції систем. Утворення складної системи з елементарних. Побудова функціональних схем. 9. Взаємодія елементів і управлінняРозвиток систем шляхом вводу нових зв’язків. Розвиток систем за рахунок зміни їх структури. Успадкування властивостей системи з прототипу. Розподілене і централізоване управління. 10. Суперечки в системахМетоди виявлення помилок в системах. Виявлення вузьких місць. Мінімально несумісна підмножина. Максимально сумісна підмножина. Перехід від мінімально несумісних підмножин до максимально сумісних. Використання модальної логіки для опису систем. 11. Взаємодія системТенденції розвитку. Закономірності в системах. Поняття причинності в складних системах. Зв’язок моделей функціонування з теорією ігор. Методи розв’язку ігрових ситуацій. 12. Паралельне управлінняПоняття “порочного кола”. Поняття “чорного ящика”. Циклічні процеси в системах. Запізнення регулюючих сигналів. Автоколивання в системах. 13. Ситуаційне управлінняПоняття ситуації. Аналіз ситуацій. Поняття люфту параметрів. Чутливість системи за критичним параметром. Абсолютно нестійкі системи. 14. Моделі системАлгоритмічні моделі. Представлення функціональних схем у вигляді мереж Петрі. Операції еквівалентного перетворення функціональної схеми. Загальні моделі систем. Адекватність моделі. Оцінка подібності моделі. Міра довіри до моделі. Заміна та корекція моделей. Групи як елементарні моделі систем. Формальні мови та граматики. 15. Недетермінізм в системних процесахОбмін ресурсами в системах. Моделі потоків даних. Стохастичні моделі. Поняття ефективності в системах. Поняття надійності систем. Самоорганізація в системах. Старіння систем.