Додаток:Комп'ютерні науки та інформаційні технології

1. математичні основи створення інформаційних систем та технологій
1.1. теорія графів
1. обхід графів. пошук вглиб та вшир.
2. алгоритми знаходження найкоротшого шляху в графі.
3. проблема ізоморфізму графів.
4. ейлерові та гамільтонові графи та їх властивості.
5. пласкі та планарні графи. теорема ейлера. умови планарності та непланарності.
6. мережі, потоки, теорема форда фалкерсона.
7. бінарне дерево пошуку. його застосування.
8. збалансоване дерево. кістякове дерево. теорема Кірхгофа.
9. незалежні множини вершин графа, кліки, паросполучення.
10.вершинне пофарбування графів. теорема хейвуда.
1.2. теорія автоматів
1. скінченні автомати з виходом.
2. скінченні автомати без виходу. детерміновані та недетерміновані автомати.
3. структурний синтез скінчених автоматів.
4. скінчений автомат, як розпізнавач мов.
5. автомат з магазинною пам'яттю як розпізнавач та перетворювач.
6. лінійно обмежені автомати та їх властивості.
7. машина Тьюрінга та її властивості.
1.3. теорія алгоритмів
1. інтуітивне визначення алгоритмів та необхідність його уточнення.
2. основні етапи повної побудови алгоритму.
3. теорія NP-повних проблем (теорія NP-повноти).
4. уточнення алгоритма по Тьюрінгу.
5. уточнення алгоритма по Маркову.
6. рекурсивні функції.
7. рекурсивні та рекусивно-перераховувані множини, їх властивості та відношення.
8. теорія зведеності. співвідношення класів P і NP.
9. теорема Черча.
1.4. теорія граматик та формальних мов
1. Визначення та класифікація (за Хомським) формальних мов та граматик.
2. властивості контексно вільних граматик та їх використання.
3. контексно вільні мови та автомати з математичною пам'яттю.
4. контексно залежні граматики та їх властивості.
5. граматики для машинного аналізу природньої мови.
6. мови програмування як формальні мови.
1.5. математична логіка
1. алгебра висловлювань та її властивості.
2. числення висловлювань та його дедуктивні властивості.
3. модельні властивості числення висловлювань (повнота, розв'язуваність, несуперечність).
4. числення предикатів першого порядку та його дедуктивні властивості.
5. нормальні форми в логіці.
6. підхід Ербрана до доведення теорем.
7. метод резолюцій Робінсона.
8. ЛОК - резолюція.
9. семантична резолюція.
10.зворотний метод доведення теорем.
11.лінійна резолюція.
1.6. алгебраїчні системи
1. Алгебраїчні системи з однією операцією
2. алгебраїчні системи з двома операцією.
3. ґратки. дистрибутивні ґратки. булеві ґратки.
4. матроїд. вільний матроїд. матроїд розбиття. жадібний алгоритм.
5. булева алгебра та її властивості.
6. проблема повноти системи функцій алгебри логіки.
7. гомоморфізм, ізоморфізм, автоморфізм.
1.7. теорія ймовірностей, математична статистика та потоки подій
1. неперервні випадкові величини. імовірнісні характеристики неперервних випадкових величин.
2. центральна гранична теорема.
3. теорема Бернуллі та закон "великих чисел".
4. статистична перевірка гіпотез. критерій "хі квадрат".
5. однофакторний дисперсійний аналіз.
6. метод найбільшої правдоподібності.
7. інтервальне оцінювання параметрів.
8. пуасонові потоки подій.
9. гранична теорема для марківських процесів.
1.8. теорія прийняття рішень
1. задача прийняття рішень.
2. бінарні відношення на функціях вибору.
3. методи розв'язування задач багатокритеріальної оптимізації.
4. методи розв'язування задач багатокритеріального вибору.
5. механізм колективного прийняття рішень.
6. голосування та колективний вибір.
1.9. дослідження операцій
1. лінійне програмування (ЛП). симплекс-метод. двоїстість у ЛП.
транспортні задачі ЛП.
2. дискретна оптимізація. класифікація задач дискретної оптимізації. умови, що приводять до задач дискретної оптимізації. метод гілок та границь.
метод Гоморі. метод динамічного програмування
3. нелінійне програмування. метод множників лагранжа та теорія двоїстості.
теорема Куна-Такера. Методи розв'язання задач без обмежень. Методи розв'язання задач з обмеженнями.
2. Моделі та алгоритми штучного інтелекту
2.1. штучний інтелект як подання і пошук
1. формалізація постановки задачі в просторі станів. Стратегії сліпого пошуку. Ітераційне поглиблення. Особливості, переваги і недоліки цих стратегій.
2. функції, які спрямовують пошук. Класифікація методів пошуку за стратегіями обходу графа простору станів. Стратегії пошуку hill-climbing, best-first search, А*.
3. характеристики оцінювальної функції: монотонність, допустимість, інформативність.
4. А*-алгоритм еврістичного пошуку. Допустимість А*-алгоритму.
5. концепція і основні поняття пошуку методом редукції. Розбиття задач на підзадачі. AND/OR-графи.
6. ігрові дерева пошуку. пошук по дереву гри з основним варіантом. виявлення ідентичних позицій в різних частинах дерева гри. Таблиця перестановок.
7. мінімаксний алгоритм пошуку на ігрових деревах. MiniMax, NegaMax.
8. метод альфа-бета-відсічення.
2.2. системи, які базуються на знаннях
1. дані та знання. основні моделі представлення даних і знань.
2. експертні системи. основні визначення і характеристики.
3. базова архітектура експертної системи. Розробники і користувачі ЕС.
4. представлення знань за допомогою продукційної моделі. Основні визначення. Переваги і недоліки продукційної моделі.
5. базова архітектура продукційної системи.
6. інтерпретатор продукцій (механізм виведення).
7. керування пошуком в продукційній системі через розв'язування конфліктів.
8. стратегії розв'язання кофліктів в системі CLIPS.
9. керування пошуком в продукційній системі через вибір стратегії виведення.
10.методологія „класної дошки” як різновид продукційної системи.
11.стратегії розв'язування конфліктів в продукційній системі. Приклади.
12.прямий ланцюжок виведення в продукційній системі. Приклад за стратегією пошуку в глибину.
13.зворотній ланцюжок виведення в продукційній системі. Приклад за стратегією пошуку в глибину.
14.формалізація логічної моделі представлення знань на мові Prolog.
15.концепція. Основні поняття, терміни, переваги і недоліки семантичних мереж. Приклади семантичних мереж.
16.класифікація відношень семантичних мереж. Приклади семантичних мереж.
17.лінгвістичні відношення, які використовуються в семантичних мережах.
18.фундаментальні відношення, які використовуються в семантичних мережах. Правила успадкування властивостей.
19.концепція. Основні поняття, терміни, переваги і недоліки фреймової моделі. Приклад фреймової моделі.
20.структура фрейма.
21.приєднані процедури, які використовуються у фреймовій моделі.
22.способи отримання значення слотом.
23.використання коефіцієнтів впевненості для представлення ненадійних знань.
24.виведення на основі ненадійних знань в продукційній системі. Приклад прямого ланцюжка виведення.
25.виведення на основі ненадійних знань в AND/OR-графі. Приклад.
2.3. Експертні ІТ та ІТ з елементами штучного мислення.
1. види експертних ІТ. Етапи створення експертної системи. Компоненти експертних систем.
2. системи, засновані на знаннях. системи породжувальних правил.
розв'язок конфліктів. прямий та зворотний ланцюг міркувань.
3. логічне програмування. факти, правила та питання. теорія логічного програмування.
4. формування знань на основі машинного навчання. Індуктивне навчання. Дерева рішень.
2.4. Web-технології для побудови корпоративних інформаційних систем
1. технології платформної незалежності. Технології Java/J2EE та .NET.
2. багатоланкові архітектури Web-систем.
3. методологія створення web-систем MVC (Model-View-Control).
4. технології розробки Web-систем (CGI, мова PHP, сервлети, серверні сторінки JSP/ASP, Java Bean, AJAX).
5. мова та технології XML (XML, XSL, DTD, XML Schema, XML Query, XML Encryption та ін.)
3. формальні та алгоритмічні основи автоматичного опрацювання природних мов
3.1. основні структури.
1. алфавіт, рядок (слово), мова: поняття, визначення, представлення та властивості. Побудова тестових наборів рядків.
2. N-грами, грань, масив граней, синтаксичне дерево (дерево пошуку), суфіксне дерево, узагальнене суфіксне дерево, суфіксний масив, орієнтований ациклічний граф слів.
3. скінченні автомати та скінченні трансдьюсери. Поняття, визначення, застосування та алгоритми побудови.
4. відстань між рядками. Метрики Хемінга, Левенштейна, редакційна. Зважена відстань.
3.2. алгоритми та ефективність пошуку.
1. типові завдання пошуку: входження підрядка, всіх входжень підрядка, найбільшого спільного підрядка, максимальних повторюваних структур.
2. алгоритми пошуку: наївний, Бойєра-Мура, Кнута-Морріса-Пратта, ShiftAnd, Карпа-Рабина.
3. синтаксичні дерева, суфіксні дерева, суфіксні масиви, орієнтовані ациклічні графи слів, автомати та трансдьюсери в задачах пошуку.
3.3. апроксимація рядків.
1. глобальне вирівнювання рядків.
2. локальне вирівнювання рядків.
3. найбільша спільна підпослідовність. комбінаторний алгоритм пошуку найбільшої спільної підпослідовності.
3.4. методи автоматичного опрацювання природних мов.
1. завдання та методи опрацювання на фонетичному, доморфологічному, морфологічному, синтаксичному, семантичному та прагматичному рівнях.
2. методи розпізнавання та синтезу усного мовлення.