ПРОГРАМА кандидатських іспитів за спеціальністю 01.05.03

Затверджена вченою радою Інституту кібернетики ім. В.М. Глушкова НАН України
(протокол № 2 від 27 лютого 2007 р. )

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

1. Теоретичні основи

1.1. Алгебра множин і відношень. Алгебраїчні системи, моделі, алгебри. Породжуючі сукупності: системи твірних та системи визначаючих співвідношень. Конгруенції.

1.2. Одноосновні та багатоосновні універсальні алгебри. Структури. Гратки. Булеві алгебри. Категорії. Топоси.

1.3. Формальні мови та теорії. Числення висловлювань. Виконувані та загальнозначимі формули. Теорема Геделя про неповноту.

1.4. Числення предикатів. Нормальна форма. Теорема Ербрана. Метод резолюцій. Лямбда-числення. Поняття редекса. Теорема Черча-Россера.

1.5. Основні обчислювальні оператори. Примітивно-рекурсивні, загально-рекурсивні та частково-рекурсивні функції. Тези Черча-Тьюринга, Поста-Кліні. Теорема про універсальну машину та s-m-n-теорема. Теорема Кліні про нерухому точку.

1.6. Алгоритмічно нерозв’язні проблеми. Проблема зупинки. Теорема Черча про нерозв’язні проблеми розпізнавання виведення в численні предикатів першого порядку. Теорема Райса про розпізнавання властивостей.

1.7. Поняття скінченного автомата. Гомоморфізм та ізоморфізм автоматів. Мінімізація автоматів. Скінченні автомати та їх зв’язок з регулярними мовами. Аналіз та синтез скінченних автоматів. Дискретні перетворювачі. Системи алгоритмічних алгебр В.Глушкова.

1.8. Формальні граматики. Класифікація мов за Хомським. Синтаксис і семантика формальних мов. Визначення регулярності граматики. Контекстно-вільні мови та їх зв’язок з магазинними автоматами. Нормальна форма Хомського. Нормальна форма Грейбах. Контекстно-вільна мова як розв’язок рівняння. Аналіз і синтез магазинних автоматів.

1.9. Синтаксичний аналіз “згори-униз”. LL(k)-граматики. Рекурсивний спуск. Синтаксичний розбір “знизу-вгору”. Граматики передування.

1.10. Дискретні системи та задачі їх реалізації. Приклади дискретних систем. Графи. Мережі Петрі.

1.11. Складність алгоритмів та обчислень. Класи P, NP, PSPACE. Теорема Кука про NP-повноту задачi виконаностi булевої формули. Iншi приклади NP-складних і NP-повних задач. Градієнтні методи, евристичний пошук, лінійне та динамічне програмування, розфарбування вершин графа, задача про комівояжера.

2. Архітектура систем оброблення інформації

2.0. Комп’ютерні платформи (персональні комп’ютери, mainframe, суперкомп’ютери, кишенькові персональні комп’ютери, термінали).

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

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

2.4. Клієнт-серверна архітектура. Багаторівнева (багатоланкова) архітектура. Поняття клієнта і сервера. Тонкий клієнт. Сервер застосувань, файл-сервер.

2.5. Паралельні системи та обчислення. SIMD- і MIMD-архітектура. Кластери.

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

2.7. Поняття розподіленої системи. Технології розподілених систем. Поняття Веб-сервісів, Remoting., Simple Object Access Protocol (SOAP), Web service definition language (WSDL). Роль мови XML у обміні документами.

2.8. Взаємодія між процесами (Inter-process communication). Рівні та засоби передачі інформації мережею: Sockets та Named Pipes.

2.9. Найвідоміші протоколи Інтернету: електронна пошта (SMTP, POP3, IMAP), електронний каталог (LDAP, Active Directory), віддалена консоль (Telnet, SSH), обмін файлами (FTP), гіпертекстові сторінки (HTTP, HTTPS). Поняття захищеного каналу SSL, інтеграція SSL у Web-серверах (IIS, OpenSSL).

2.10. Серверні застосування в Інтернеті. Веб-сервери. Сервери баз даних.

2.11. Стек протоколів TCP/IP: основнi принципи організацiї та функцiонування. Microsoft Internet Explorer, Mozilla FireFox, мова HTML, мова Java Script.

3. Операційні системи

3.1. Операційні системи: призначення, основні концепції, складові. Інтерфейс користувача. Розподіл ресурсів. Управління процесами. Фізична і віртуальна пам’ять. Кеш. Однокористувацькі та багатокористувацькі операційні системи. Поняття операційного середовища (environment), API, служби (домена), драйвера, віддаленого керування.

3.2. Служби організації безпеки в операційних системах. Поняття аутентифікації (локальна, мережна), прав та атрибутів доступу, політики безпеки. Роль центрів сертифікації ключів. Основні положення Закону України „Про електронний цифровий підпис”.

3.3. Організація взаємодії програм через переривання. Динамічне завантаження.

3.4. Багатозадачність в операційних системах. Процеси, розподіл пам’яті, пріоритет. Принципи організації обчислень у кластерних комплексах.

3.5. Приклади ОС та операційних оболонок: UNIX, Windows. Порівняння поколінь Windows (95, 98, Ме, NT,2000,XP,2003, Vista).

3.6. Середовище Windows. Базові класи вікон. Керівні елементи, кнопки, фокус вводу. Об’єкти. Організація сценаріїв.

3.7. Паралельне виконання. Процеси, нитки, потоки. Синхронна, асинхронна взаємодія.

3.8. API-функції міжмодульного інтерфейсу. Модель компонентного об’єкта. COM, СОМ+, DCOM і CORBA. OLE 2.

3.9. Уніфіковані форми та засоби організації інтерфейсу корис¬тувача (текстові та графічні редактори, електронні таблиці, гіпертекстові системи, ігри та мультимедіа).

3.10. Поняття відкритої системи. POSIX-сумісне середовище відкритих система.

3.11. Інтернаціоналізація і локалізація інформаційних технологій. Набори культурних елементів. Специфіка національно-української локалізації.

4. Мови та системи програмування

4.1. Процедурні, об’єктні та скриптові мови, мови специфікацій; особливості організації і напрямки розвитку. Поширені мови програмування (Фортран, С, C++, C#, Паскаль, Delphi, Visual Basic, Smalltalk, Java, Пролог, Лісп).

4.2. Основи Web-програмування. Порівняння засобів розробки Web-застосування CGI, PHP, ASP, ASP.NET. Мови Perl, Python, JavaScript, VBScript, C#. Сервлети і аплети Java. Поняття Web-сервісів. Мова XML, взаємодія Web-клієнту з сервером застосувань.

4.3. Асемблери, компілятори, інтерпретатори. Етапи компіляції: лексичний, синтаксич¬ний, семантичний аналізи, оптимізація і генерація об’єктного коду. Лінкування та інсталяція.

4.4. Керування пам’яттю скомпільованої програми: статична, автоматична, базована та динамічна пам’ять. Методи кешування.

4.5. Організація передачі параметрів між програмними модулями. Виклик за значенням, за найменуванням, за результатом. Проблеми комплексування різномовних модулів.

4.6. Мови, орієнтовані на паралельну та розподілену обробку. Особливості реалізації.

4.7. Генератори систем програмування. Макрогенератори та розширювані системи програмування, препроцесори.

4.8. Метасистеми програмування: багатомовні системи, параметричні системи та метатранслятори.

5. Інструменти програмної інженерії

5.1. Основні стадії й етапи проектування програм та документування. Технічне завдання. Ескізний, технічний, робочий проекти. Впровадження та супровід. Життєвий цикл програмного забезпечення (ПЗ). Каскадна та спіральна моделі життєвого циклу ПЗ.

5.2. Специфікація програм. Понятійні засоби специфікації. Денотаційна, операційна та аксіоматична семантики. Класифікація мов специфікацій.

5.3. Якість програмного забезпечення. Методи налагодження та тестування програм, верифікація програм.

5.4. Організація роботи колективів програмістів. Планування виробництва ПЗ. Моделі роз¬робки програмного продукту та об’єктно-орієнтований підхід. CASE-технології.

5.5. Поняття рекурсії. Рекурсивні означення та рекурсивні програми. Властивості рекурсивних алгоритмів. Функціональні і рекурсивні структури даних.

5.6. Структурне програмування. Теорема про структурування програм. Багатоосновні алгебри структур даних. Теоретико-множинні структури даних.

5.7. Повторне використання ПЗ. Методи та засоби повторного використання.

5.8. Об’єктний підхід у проектуванні ПЗ. Мова UML. Компонентне програмування.

5.9. Функціональне програмування. Концепції та приклади. Мова Лісп.

5.10. Логічне програмування. Системи програмування “за правилами”. Мова Пролог.

6. Бази даних і концептуальне моделювання

6.1. Загальне уявлення про систему баз даних: схеми і екземпляри даних, фізична база даних, модель даних, схема даних, підсхема. Проектування концептуальної схеми. Мова визначення даних (DDL). Адміністратор бази даних. Мова маніпулювання даними. Незалежність даних; цілісність даних та види функціональних залежностей.

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

6.3. Реляційна, мережна, ієрархічна моделі даних. Багатовимірні, об’єктно-орієнтовані, об’єктно-реляційні бази даних.

6.4. Вітрини та сховища даних (Data Warehouse). Поняття метаданих.

6.5. Мови маніпулювання даними для реляційної моделі: реляційна алгебра та реляційне числення; алгебраїчні мови та мови числення.

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

6.7. Проектування баз даних. ER-діаграми.

6.9. Розподілені бази даних: централізовані і децентралізовані СУБД; проблеми розподілення баз даних; виконання запитів; одночасна обробка та оновлення.

6.10. Розподілені та клієнт-серверні системи. Обробка транзакцій та OLTP.

6.11. Методи і засоби розробки застосувань баз даних. Універсальний доступ до баз даних (ODBC, RDO, ADO, JDBC).

6.12. Приклади серверів баз даних: Oracle, MS SQL Server, Informix, IBM DB2. Штатні процедури резервного копіювання та актуалізації бази даних після збоїв.

6.13. Багатовимірні СУБД і OLAP. Методи Data Mining’a.

6.14. Гіпертекстові системи і системи ведення документних баз.

6.15. Машина баз даних як апаратно-програмний мультипроцесорний комплекс, призначений для виконання функцій СКБД, паралельні машини баз даних. Рівні розпаралелювання. Кластерні сервери баз даних.

7. Моделі і методи штучного інтелекту

7.1. Відмінність понять “знання” та “дані”. Моделі подання знань: продукційні, логічні, фреймові та за допомогою семантичних мереж.

7.2. Мови та системи подання знань: концепції і приклади.

7.3. Поняття експертної системи та її архiтектура: база знань; розв’язувач (машина виведення); компонент надбання знань; пояснювальний та діалоговий компоненти.

7.4 Інтелектуальні агенти. Поняття агента, середовища. Структура агентів. Визначення раціональності.

7.5. Онтології. Поняття категорії, об’єкта, дії, ситуації, події, процесу.

7.6. Задачі планування. Моделі планування: простір станів, графи, пропозиційна логіка. Умовне планування. Мультиагентне планування. Конкуренція та кооперація.

7.7. Методи добування знань із дослідних даних та самонавчальні алгоритми. Нейронні мережі. Генетичні алгоритми.

7.8. Імовірнісні моделі дій за умови невизначеності. Подання знань байєсівськими мережами. Врахування часу. Фільтри Калмана і динамічні байєсівські мережі.

7.9. Системи підтримки прийняття рішень та особливості їх реалізації. Методи і засоби експертного аналізу і прогнозу за груповими експертними оцінками. Методи і засоби статистического аналізу і прогнозування. Дерева розв’язків. Типові оптимізаційні задачі і методи недиференційовної оптимізації.

7.10. Поняття навчання. Застосування знань в навчанні. Статистичні моделі навчання.

Список літератури

1. Андон Ф.И., Коваль Г.И., Коротун Т.М., Суслов В. Ю.. Основы инженерии качества программных систем. – Киев: Академпериодика, 2002. – 504 с.

2. Ахо А., Сети Р., Ульман Дж. Компиляторы: принципы, технологии и инструменты. – М.: Издательский дом “Вильямс”, 2001. – 768 с.

3. Ахо А., Хопкрофт Д., Ульман Д. Структуры данных и алгоритмы. – М.: Издательский дом “Вильямс”, 2000. – 384 с.

4. Браун П. Макропроцессоры и мобильность программного обеспечения. – М.: Мир, 1977. – 254 с.

5. Буч Г., Рамбо Д., Джекобсон А. Язык UML. Руководство пользователя. / Пер. с англ. – М.: ДМК Пресс, 2001. – 432 с.

6. Эспозито Д. Знакомство с Microsoft ASP.NET 2.0 /Пер. с англ. – М.: Издательско-торговый дом «Русская редакция», 2005. – 512 с.

7. Ван Тассен Д. Стиль, разработка, эффективность, отладка и испытание программ. – М.: Мир, 1989.

8. Себеста В. Основные концепции языков программирования: 5-е изд. – М.: Издательский дом “Вильямс”, 2001. – 672 с.

9. Воеводин В.В., Воеводин Вл.В. Параллельные вычисления. – СПб.: БХВ-Петербург, 2004. – 608 с.

10. Гаек П., Гавранек Т. Автоматическое образование гипотез. – М.: Наука, 1984. – 260 c.

11. Гектор Г.М., Ульман Дж., Уидом Д. Системы баз данных: Полный курс. – М.: Издательский дом “Вильямс”, 2003. – 1088 с.

12. Грис Д. Наука программирования. – М.: Мир,1984. – 274 с.

13. Гук М. Аппаратные средства IBM PC. Энциклопедия: 3-е изд. – СПб.: Питер, 2006. – 1072 с.

14. Перевозчикова О.Л. Основи системного аналізу об’єктів і процесів комп’ютеризації. – К.: Вид. дім „КМ Академія”, 2003.– 432 с.

15. Камер Д. Компьютерные сети и Internet. – М.: Издательский дом “Вильямс”, 2002. – 640 с.

16. Касьянов В.Н. Графы в программировании: обработка, визуализация и применение. – СПб: БХВ-Петербург, 2003. – 1104 с.

17. Кватрани Т. Визуальное моделирование с помощью Rational Rose 2002 и UML. – М.: Издательский дом “Вильямс”, 2001. – 672 с.

18. Клини С.К. Математическая логика. – М.: Мир, 1973. – 658 с.

19. Кнут Д. Искусство программирования: 3-е изд.: В 3-х т. – М.: Издательский дом “Вильямс”, 2000.

20. Ларичев О.И., Мечитов А.И., Мошкович Е.М., Фуремс Е.М. Выявление экспертных знаний. – М.: Наука, 1989. – 187 с.

21. Леонг-Хонг Б. Системы словарей-справочников данных. – М.:Финансы и статистика, 1986. – 311 c.

22. Мальцев А.И. Алгебраические системы. – М.: Наука,1970. – 393 c.

23. Сичкаренко. В.А. SQL-99. Руководство разработчика баз данных. – СПб: ООО «ДиаСофтЮП», 2002. – 816 с.

24. Рамбо Д., Якобсон А., Буч Г. UML: специальный справочник. – СПб.: Питер, 2002. – 656 с.

25. Рассел С., Норвиг П. Искусственный интеллект: современный подход (AIMA). – М.: Издательский дом “Вильямс”, 2005. – 1424 с.

26. Ритхер Д. Программирование на платформе Microsoft .NET Framework. – СПб.: Питер, 2005. – 486 с.

27. Соммервилл И. Инженерия программного обеспечения. – М.: Издательский дом “Вильямс”, 2002. – 624 с.

28. Успенский В.А., Семенов А.Л. Теория алгоритмов: основные открытия и приложения. – М.: Наука, 1987. – 288 с.

29. Филд А., Харрисон П. Функциональное программирование. – М.: Мир, 1993. – 637 с.

30. Хайкин С. Нейронные сети: полный курс. – М.: Издательский дом “Вильямс”, 2005. – 1104 с.

31. Перевозчикова О.Л. Інформаційні системи та структури даних. – К.: Вид. дім „КМ Академія”, 2007.– 284 с.

32. Хоггер К. Введение в логическое программирование. – М.: Мир, 1988. – 384 с.

33. Хювенен Э., Сеппенек Й. Мир Лиспа. – М.: Мир, 1990. – Т. 1. – 447 c.; Т. 2. – 319 с.

34. Чень Ч., Ли Р. Математическая логика и автоматическое доказательство теорем. – М.: Наука,1983. – 358 с.

35. Экспертные системы: принципы работы и примеры / Под ред. Р.Форсайта. – М.: Радио и связь, 1987. – 223 с.

36. Элти Дж., Кумбе М. Экспертные системы: концепции и примеры. – М.: Финансы и статистика, 1987. – 191 c.

37. Эммерих В. Конструирование распределенных объектов. – М.: Мир, 2002. – 510 с.

38. Англо-український тлумачний словник з обчислювальної техніки, Інтернету і програмування. – Вид. 2. – К.: Вид. дім „СофтПрес”, 2006. – 824 с.

Програму склали:

член-кореспондент НАН України,
доктор фізико-математичних наук, професор ПЕРЕВОЗЧИКОВА О.Л.,
член-кореспондент НАН України, доктор технічних наук ПАРАСЮК І.М.,
доктор фізико-математичних наук КРИВИЙ С.Л.