ІНСТИТУТ КОМП’ЮТЕРНИХ НАУК ТА ІНФОРМАЦІЙНИХ ТЕХНОЛОГІЙ Напрям: Компютерні науки Спеціальність: Інтелектуальні системи прийняття рішень (0305)I. Системи штучного інтелекту1. Інтерпретація формулІнтерпретація формул логіки висловлювань. Інтерпретація формул логіки першого ступеня. Алгоритм Девіса-Патнема. Алгоритм Куайна. 2. Основи логічного виведенняЛогічне виведення у логіці висловлювань. Принцип прямої дедукції. 3. Логічне виведення у логіці висловлюваньПравила виведення у логіці висловлювань. Правило резолюцій. Правило modus ponens. Правило уведення диз’юнкції. Гіпотетичний силогізм. 4. Застосування правила резолюцій у численні висловлюваньАлгоритм резолюцій. Хорнівські диз’юнкти. 5. Логічне виведення у логіці першого ступеняПідстановка та уніфікація. Алгоритм резолюцій. Сколемівська нормальна форма. Метод резолюцій у численні першого ступеня. Принцип логічного програмування. ^ II. Організація баз даних та знань1. Основи комп'ютерного опрацювання данихІнформаційні системи та інформаційні технології. Інформація і дані.2. Моделі баз данихАрхітектура баз даних. Фізичні моделі даних. Концептуальна модель бази даних. Метод "сутність – зв'язок". Даталогічна концептуальна модель бази даних. Логічні одиниці даних. Логічні моделі баз даних. Види логічних моделей даних.3. Основи реляційних баз данихРеляційна модель бази даних. Проектування реляційних баз даних. Функціональні залежності в реляційних базах даних. Ключі у відношеннях реляційних баз даних. Нормалізація відношень. Подальша нормалізація відношень. Нормальні форми вищих порядків.4. Реляційна алгебра. Операції над відношеннямиПоняття реляційної алгебри. Теоретико-множинні операції. Спеціальні реляційні операції. Операції над станами відношень. Операції над схемами відношень. 5. Реляційні численняРеляційне числення зі змінними-кортежами. Відповідність формул реляційного числення зі змінними-кортежами та операцій реляційної алгебри. Реляційне числення зі змінними на доменах. ^ III. Дискретна математика1. Математична логікаЛогіка висловлювань. Закони логіки висловлювань. Нормальні форми логіки висловлювань. Логіка першого ступеня.2. Основи теорії множинПоняття множини. Поняття кортежа. Декартів добуток множин. Операції над множинами. Доведення рівностей з множинами. Комп’ютерне зображення множин. 3. Теорія графівОсновні означення та властивості. Деякі спеціальні класи простих графів. Способи задання графів. Шляхи та цикли, зв’язність. Ізоморфізм графів. Ейлерів цикл у графі. Гамільтонів цикл у графі. Зважені графи та алгоритми пошуку найкоротшого шляху. Обхід графів. Планарні графи.4. Дерева та їхнє застосуванняОсновні означення та властивості. Обхід дерев. Префіксна та постфіксна форми запису. Бінарне дерево пошуку. Дерева прийняття рішень. Алгоритм бектрекінг.5. ВідношенняВідношення та їхні властивості. Відношення еквівалентності. Відношення часткового порядку. Операції над відношеннями.6. Основи теорії автоматівОсновні вимоги до алгоритмів. Машини Тьюрінга. Обчислення числових функцій на машині Тьюрінга.^ IV. Детерміновані моделі дослідження операцій та оптимізації інформаційних систем1. Вступ до проблематики дослідження операцій та практичних застосуваньПредмет та задачі дослідження операцій: Історія виникнення дослідження операцій (ДО). Основні поняття ДО та етапи операційного дослідження. Пряма та обернена задачі ДО. Детерміновані задачі ДО. Проблема вибору розв’язків в умовах невизначеності. Основні класи задач дослідження операцій. Багатокритерійні задачі ДО та основні підходи до їх розв’язування: Основні поняття та постановка задачі. Методи згортання критеріїв. Метод “ідеальної точки”. Переведення критеріїв в обмеження. Контрольні показники. Метод послідовних поступок. Поняття про діалогові методи. 2. Задача лінійного програмуванняПостановка задачі лінійного програмування. Місце лінійного програмування в математичному програмуванні. Формальна постановка задачі лінійного програмування. Побудова моделей задач лінійного програмування. Геометричне представлення задач лінійного програмування. Задачі аналізу лінійних моделей на чутливість. Основні теоретичні відомості про задачу лінійного програмування. Загальна схема алгоритму симплекс-методу (СМ) та його таблична форма. Теоретичне обгрунтування СМ. Методи знаходження початкового базового розв’язку: метод великих штрафів та двоетапний метод. Особливі випадки СМ та відображення їх в симплекс-таблицях. Інтерпретація симплекс-таблиць. Задачі дробово-лінійного програмування. Двоїстість в лінійному програмуванні. Модифікований симплекс-метод. Блочні задачі лінійного програмування. Метод Данціґа-Вулфа. Пряма та двоїста задачі лінійного проґрамування. Зв’язок між розв’язками прямої та двоїстої задач. Отримання оптимального розв’язку двоїстої задачі за допомогою СМ. Економічна інтерпретація задач лінійного проґрамування. Двоїстий СМ. Математична та змістовна постановка транспортної задачі (ТЗ). Методи знаходженння опорного плану ТЗ. Метод потенціалів. Розв’язування ТЗ з ускладненнями в постановці. Інтерпретація методу потенціалів як симплекс-методу. Метод диференційних рент. Задача про призначення. Задачі оптимізації на мережах. Поняття потоку. Теорема Форда-Фалкерсона. Загальна постановка та часткові випадки потокових задач. Задачі пошуку найкоротшого маршруту в мережі. Алгоритм Дійкстри. Задача мінімізації мережі. Задача про багатополюсний найкоротший ланцюг. Алгоритм Флойда. Задача пошуку максимального потоку. Алгоритм розташування позначок. Узагальнення задачі про максимальний потік.3. Задачі з цілочисельними зміннимиПостановка задачі цілочисельного лінійного програмування, її інтерпретація та основні підходи до розв’язування. Розв’язування лінійних задач змішаного програмування методом Ґоморі і методом розгалужень та границь. Структура та основні складові методу розгалужень та границь. Практичні реалізації методу розгалужень та границь: Розв’язання багатовимірної задачі про наплечник за допомогою методу розгалужень та границь. Загальна постановка задачі булевого програмування. Алгоритм Балаша. Методи приведення цілочисельних задач до булевих. Задача про комівояжера. 5. Ігрові задачі дослідження операційОсновні поняття теорії ігор. Класифікація ігор. Матричні ігри двох осіб з нульовою сумою. Матриця гри. Верхня та нижня ціна гри. Теорема про мінімакс. Мішані стратегії в іграх двох осіб з нульовою сумою. Представлення гри у вигляді задач лінійного програмування. Ігри порядку 22, 2n та m2. Графічне розв’язування ігор. Поняття про позиційні ігри. Кооперативні ігри та методи їх дослідження. Прийняття рішень в умовах невизначеності. 8. Динамічне програмуванняПоняття динамічного проґрамування (ДП) та загальна постановка задачі ДП. Принцип оптимальності. Метод функціональних рівнянь. Динамічні моделі управління запасами.^ V. Системний аналіз1. Вступ до проблематики системного аналізу об'єктів та процесів комп'ютеризаціїРозвиток системних уявлень та необхідність виникнення системного підходу. Історія розвитку системних уявлень. Основні напрямки системних досліджень. Передумови та необхідність виникнення системного підходу. Предмет системного аналізу. Основні поняття системного аналізу. Принципи системного підходу. Поняття системи, навколишнього середовища, мети. Декомпозиція. Поняття елементу, функції, структури. Види потоків в системах. Класифікація та властивості систем. Класифікація систем за призначенням, взаємодією з зовнішнім середовищем, походженням, видом елементів, способом орґанізації. Складні та великі системи. Способи керування системами та реалізація ними своїх функцій.2. Системний аналіз та моделюванняСистема та модель. Наукове пізнання та моделювання. Модель. Зв’язок між системою та моделлю. Ізо- та гомоморфізм. Функції моделей систем. Класифікація моделей систем. Системно-методолоґічні аспекти моделювання. Дослідження систем за допомогою аксіоматичного підходу. Метод „чорної скрині”. Проблеми оптимізації в системному аналізі та моделюванні. Імітаційні моделі. Аналітичний та синтетичний підходи до дослідження складних систем. Повнота моделі. Декомпозиція та аґреґування. Види аґреґатів, що використовуються в системному аналізі. Системні особливості моделей інформаційних систем та систем прийняття рішень.3. Методолоґії системного аналізуОсобливості методолоґій системного аналізу. Послідовність методолоґія—метод—нотація—засіб. Етапи системного розв’язання проблем. Послідовність етапів і робіт системного аналізу. Методолоґія системного дослідження, орієнтована на дослідження існуючих систем та виявлення проблем. 4. Методи системного аналізуМетод дерева цілей. Метод Дельфі. Функціонально-вартісний аналіз та споріднені методи. Огляд технолоґій розроблення нових й аналізу розроблених виробів і процесів. Функціонально-вартісної аналіз. Технолоґія аналізу можливості виникнення і впливу дефектів на споживача (FMEA). Функціонально - фізичний аналіз. Метод розгортання функцій якості QFD. Використання CASE-засобів в функціонально-вартісному аналізі. Методи комбінаторно-морфолоґічного аналізу і синтезу. Особливості реалізацій морфолоґічного підходу. Отримання та систематизація інформації для аналізу і синтезу систем. Побудова морфолоґічних таблиць. Основи синтезу раціональних систем. Морфолоґічні методи синтезу раціональних варіантів систем. Аналіз процесів функціонування систем. Аналіз систем за допомогою коґнітивних карт. Таблиці рішень. Мережі Петрі. Виконання мереж Петрі. Моделювання одночасності та конфліктів засобами мереж Петрі. Узагальнення мереж Петрі. 5. Отримання експертної інформації для системного аналізуПроблеми та методи отримання інформації від експертів: Труднощі та психолоґічні особливості отримання інформації від експертів. Особливості лінґвістичного та ґносеолоґічного аспекту спілкування з експертом. Класифікація методів видобування знань. Особливості пасивних та активних методів видобування знань. Групові методи видобування знань. Ігри з експертом та текстолоґічні методи видобування знань6. Застосування методолоґій системного аналізу при створенні інформаційних систем Класичні підходи до проектування інформаційних систем: Поняття системного проектування. Класичні схеми проектування інформаційних систем. Вдосконалення класичних схем проектування. Методолоґія швидкого розроблення застосувань (RAD). Інструментарій класичних схем проектування. Системні методолоґії та проектування інформаційних систем: Передумови змін в методах проектування. Виникнення і зміст реінженерії бізнес-процесів. Якісні зміни в інформаційних технологіях. Перспективи розвитку системних методів проектування^ VI. Комп’ютерні мережі1. Головні архітектурні принципи побудови комп’ютерних мережІсторія розвитку комп’ютерних мереж. Класифікація мережевих вирішень. Стандартизація у комп’ютерних мережах. Організації що займаються стандартизацією. Еталонна модель взаємозв’язку відкритих систем. Методи комутації.2. Середовища передавання, коди та сигнали комп’ютерних мережПараметри середовищ передавання та їх порівняння. Коаксіальні кабелі. Волоконно-оптичні кабелі. Скручена пара як середовище передавання даних у комп’ютерних мережах. Стандарт EIA- 568- AB, ISO/IEC 11801. Параметри скрученої пари. Канал передавання даних. Модуляція. Кодування. 3 Базові протоколи комп’ютерних мережФункції протоколів фізичного та канального рівнів. Протоколи керування доступом. Протокол HDLC. Протоколи мережевого та транспортного рівнів. Методи маршрутизації. 4. Протокольний стек TCP/IPСтруктура мережі TCP/IP та базові принципі її роботи. Адресація у мережі. Головні протоколи мережі Ipv 4. Протокол IPv6. Служба DNS. Маршрутизація у мережах IP. Трансляція мережевих адрес (NAT). 5. Об’єднання мереж та мережеві вирішенняЗасоби об’єднання мереж. Багаторівнева комутація. Кабельні системи комп’ютерних мереж. Структури мережевих вирішень. 6. Мережеві технологіїШини вводу-виводу PCI, PCI-e. Інтерфейсні технології. Технологія передавання SCSI. Локальні мережі. Архітектура, різновиди та порядок роботи мереж Ethernet. Безпровідні мережі. Глобальні мережі. ^ VII. Об’єктно-орієнтоване програмування1. Технології об’єктно-орієнтованого проектування програмних системСучасні технології та платформи проектування програмних систем. Технологія об’єктно-орієнтовного проектування: класи, інкапсуляція даних, успадкування, поліморфізм. Case-засоби об'єктно-орієнтованого проектування програмних систем. UML-діаграми класів.2. Особливості мови С++Новий стиль включення файлів у програму; простір імен; коментарі; особливість оголошень типів даних; нові типи даних; тип посилання; розширений набір зарезервованих слів та операцій. Оголошення функцій; нові стилі оголошення функцій; аргументи функцій за замовчуванням; вбудовані функції; перевантаження функцій; декорування імен функцій; специфікації зовнішніх зв’язків; операції виділення та звільнення динамічної пам’яті.3. Класи та об’єкти С++Оголошення та структура класу. Дані та методи класу. Декларації private, protected, public. Звичайні, константні та статичні дані та методи, особливості їхнього оголошення та використання. Вказівники на елементи класу – синтаксис оголошення та семантика застосування. Конструктори та деструктори, їх призначення, оголошення, розміщення у програмі та виклики. Конструктори перетворення типу та конструктори копіювання, особливості їхнього оголошення та варіанти викликів. Дружні функції та дружні класи (friend). Види класів. Глобальні та локальні класи. Контейнерні та вкладені класи. Оголошення об’єктів класу. Об’єкти у динамічній пам’яті. Види та властивості об’єктів. Вказівники на об'єкти класу. Вказівник this. Перетворення до типу об'єктів класу.4. Класи потокового введення-виведенняСтандартні об’єкти-потоки. Виведення на екран та введення з клавіатури. Робота з файлами. Переадресування введення-виведення. Форматування потоків. Опрацювання станів потоків. Маніпулятори потоків. Форматування в пам’яті (резидентних потоків).5. Перевантаження операцій та операторні функціїПеревантаження унарних та бінарних операцій. Особливості перевантаження первинних операцій, інкременту та декременту, new та delete, присвоєння, приведення типу. Перевантаження потокових операцій введення-виведення.6. Успадкування класівОдинарне успадкування класів. Базові та похідні класи. Оголошення успадкування. Ієрархія класів, правила успадкування. Особливості викликів конструкторів та деструкторів при успадкуванні класів. Множинне успадкування класів. Синтаксис та семантика множинного успадкування. Успадкування класів з загальною базою. Особливості викликів конструкторів та деструкторів при множинному успадкуванні класів. 7. Поліморфізм віртуальних функційПеревантаження функцій, поліморфізм, віртуальні функції та пізнє зв'язування. Динамічні віртуальні функції. Чисті віртуальні функції та абстрактні класи. Інтерфейси компонентної моделі об’єктів.8. Шаблони функцій та класівШаблонні (параметризовані) функції. Синтаксис оголошення. Використання шаблонів функцій. Спеціалізація шаблонів. Перевантаження шаблонів функцій. Шаблонні класи. Синтаксис оголошення. Визначення та спеціалізація шаблону класу. Об'єкти шаблонних класів. Друзі шаблонних класів. Бібліотека стандартних шаблонів STL. 9. Інформація про типи та операції приведення типівОтримання інформації про тип під час виконання програми. Програмування з використанням RTTI. Перетворення та приведення типів. Операції static_cast, dynamic_cast, const_cast, reinterpret_cast. Перетворення типів поліморфних об’єктів. Низхідне та перехресне приведення типів.10. Керування виключеннямиКонтроль за виконанням секції коду. Оператор try. Викидання виключень. Оператор throw. Опрацювання виключень. Оператор catch. Специфікації виключень. Робота з конструкторами та виключеннями. Робота з ієрархіями виключень. Кадроване керування виключеннями та фільтруючий вираз. Опрацювання виключних станів роботи процесора.