ПРОГРАМА кандидатського іспиту за спеціальністю 01.05.01 – теоретичні основи інформатики та кібернетики ПРОГРАМА кандидатського іспиту за спеціальністю 01.05.01 – теоретичні основи інформатики та кібернетики

Затверджена вченою радою Інституту кібернетики ім. В.М. Глушкова НАН України

(протокол № 2 від 27 лютого 2007  р.) 

1. МАТЕМАТИЧНІ ОСНОВИ

1.1. Алгебраїчні та топологічні структури.

Одноосновні та багатоосновні універсальні алгебри та алгебраїчні системи. Породжуючі сукупності: системи твірних та визначаючих співвідношень. Вільні алгебри. Гомоморфізми та конгруенції. Групи, напівгрупи, кільця, поля. Векторні простори та алгебри над полями. Частково впорядковані множини, ґратки та булеві алгебри. Алгебра множин та відношень. Топологічні та метричні простори. Категорії, топоси. Теореми Фрейда.

 1.2. Комбінаторний аналіз та теорія графів

Перестановки, розміщення, комбінації. Метод рекурентних співвідношень. Метод продуктивних функцій. Неорієнтовані та орієнтовані графи. Операції над графами. Властивості графів. Матриці та графи. Планарність та укладання графів. Розфарбовуваня графів. Нескінченні графи. Дерева. Алгоритми обходу дерева (графа). Мережі Петрі. Задачі на графах та їх складність.

 1.3. Математична логіка

Числення висловлювань. Теорема дедукції. Несуперечність та повнота числення висловлювань. Числення висловлювань та булеві функці, Числення предикатів першого порядку. Несуперечність та повнота числення предикатів. Нормальні форми. Сколемівські форми. Теорема Ербрана. Метод резолюцій. Прикладні теорії. Формальна арифметика. Теорема1 Геделя про неповноту арифметики. Формальна теорія множин. Логіки вищих порядків. Інтуїціонізм та інтуїціоністські числення. Модальні логіки. Темпоральні логіки.

 1.4. Теорія алгоритмів

Поняття про алгоритм та алгоритмічну систему. Частково-рекурсивні та рекурсивні функції. Перечислені множини. Алгоритмічні системи Поста, Тьюринга, Маркова та Колмогорова - Успенського. Ламбда-числення. Теорема Черча–Россера про b-редукцію. Теорема Кліні. Тези Тьюринга та Черча. Універсальний алгоритм. Частково-визначені функції та теорема про нерухому точку. Алгоритмічно нерозв'язувані проблеми. Складність алгоритмів та обчислень. Класи Р, NP, РSРАСЕ. Теорема Кука про NР-повноту задачі виконаності булевої формули. Інші приклади NР-складних та NР-повних задач. Евристичний пошук, розфарбування вершин графа, задача про комівояжера.

 1.5. Теорія автоматів та дискретних перетворювачів

Поняття  автомата. Засоби  представлення  автоматів. Гомоморфізм та ізоморфізм автоматів. Автоматні відображення.

Еквівалентність автоматів. Алгебра Кліні регулярних мов. Основна теорема теорії скінчених автоматів. Алгоритм аналізу автоматів. Алгоритм синтезу автоматів. Алгоритм приведення (мінімізації) автоматів. Нескінченні автомати. Періодично-визначені перетворення на регістрах. Магазинні автомати. Дискретні динамічні системи та дискретні перетворювачі. Самоорганізація та самоудосконалення автоматів. Системи алгоритмічних алгебр. Методи розв'язання рівнянь у системах алгоритмічних алгебр. Транзиційні системи. Еквівалентність транзиційних систем.

 1.6. Формальні системи та мови

Формальні граматики. Класифікація мов за Хомським. Синтаксис та семантика формальних мов. Регулярні та контекстно-вільні граматики та мови. Контекстно-вільні мови та їх зв'язок з магазинними автоматами. Аналіз та синтез магазинних автоматів. Нормальні форми граматик. Контекстно-вільна мова як розв'язок системи рівнянь. Методи синтаксичного аналізу. Елементарні формальні системи.

 1.7. Теорія оптимізації

Методологія прийняття рішень та послідовний аналіз варіантів. Лінійне та динамічне програмування. Симплекс-метод. Алгебра і геометрія симплекс методу. Економічна інтерпретація симплекс-методу. Елементи опуклого аналізу. Опукле програмування. Двоїстість. Теорема Куна-Таккера. Субградієнтні методи мінімізації опуклих функцій. Негладкі штрафні функції. Метод еліпсоїдів. Алгоритм Хачіяна для розв'язання задач лінійного програмування. Методи спряжених напрямів. Метод лінеаризації. Основні класи задач цілочислової, частково-цілочислової оптимізації, їх властивості та методи їх розв'язання.

 1.8. Теорія ймовірності та стохастичні процеси.

Стохастичний експеримент. Алгебри і ð-алгебри випадкових подій. Аксіоми теорій ймовірностей. Ймовірністні простори. Випадкові величини, їх розподіл, щільності. Приклади. Математичне очікування випадкової величини. Моменти. Дисперсія. Незалежність випадкових подій і величин. Лема Бореля – Кантеллі. Умовні ймовірності і розподіли. Нерівності Чебишова, Маркова, Колмагорова. Збіжність за ймовірністю. Слабкий закон великих чисел. Збіжність за ймовірністю 1. Підсилений закон великих чисел. Збіжність рядів незалежних випадкових величин. Приклади. Центральна гранична теорема для сум незалежних випадкових величин. Випадкові вектори. Кореляційні матриці. Багатомірний нормальний розподіл. Поняття випадкового процесу. Гаусовські випадкові процеси. Стаціонарні процеси. Марковські процеси. Мартингали. Стохастичний інтеграл Іто. Стохастичні диференціальні рівняння.

Локальні методи. Задачі багатокритеріальної оптимізації, методи їх розв'язання. Задачі оптимального керування. Принцип максимуму Понтрягіна. Елементи теорії ігор. Комбінаторні задачі оптимізації.

 2. КОМП'ЮТЕРНІ АСПЕКТИ.

2.1. Архітектура та стуктура обчислювальних систем

Нейманівська архітектура обчислювальних машин. Ненейманівські архітектури: рекурсивні ЕОМ, машини з масовим паралелізмом, однорідні та різнорідні системи. SIМD та МІМD системи. Розподілені ЕОМ. Комп'ютерні мережі. Архітектура зовнішнього програмного забезпеченння. Архітектура внутрішнього математичного забезпечення. Комп'ютерні платформи. Види спеціалізованих архітектур обчислювальних систем. Архітектура мультимедіа.

 2.2. Системи програмування та проектування компонент обчислювальних систем.

Основні парадигми програмування: імперативне, функціональне, алгебраїчне та логічне програмування. Об'єктно-орієнтоване та паралельне програмування. Мови та системи програмування: С, С++, Фортран, Паскаль, ЛІСП, МL., Пролог, Модула, Смолток, АДА, Джава. Структура трансляторів та інтерпретаторів. Етапи трансляції: лексичний, синтаксичний, семантичний аналізи, оптимізація, генерація об'єктного коду, збирання. Організація передачі параметрів між програмними модулями. Виклик за значенням, за найменуванням, за результатом. Метасистеми програмування. Діалогові системи програмування. Методи візуалізації структур даних та процесу виконання програм. Мови моделювання обчислювальних систем. UML.

 2.3. Організація обчислень та взаємодії у комп’ютерних системах

Операційні системи та їх структура: MS DOS, UNIX, WINDOWS. Якість програмного забезпечення та методи її виявлення. Методи налагодження програм. Тестування програм. Організація кооперативної роботи. Метод "Клієнт-Сервер". Інтелектуальні програмні агенти. Характеристика Іnternet. Методи організації паралельної роботи програм. Координаційні мови. Підтримка проведення розподілених конференцій. Методи організації розподілених обчислень.

 2.4. Інтелектуалізація компонент обчислювальних систем.

Загальна характеристика баз даних. Концептуальні схеми БД. Моделі даних БД. Цілісність даних та види функціональних залежностей. Мови БД. Реляційна, мережева та ієрархічна модель БД. Тезаурус та словники в системах обробки даних. Розподілені БД. Машини БД. Бази знань. Методи інженерії знань: формалізація, поповнення знань, узагальнення та класифікація знань, виведення нових знань. Обробка неповної та нечіткої інформації. Експертні системи.

 2.5. Комп'ютерне забезпечення розв'язання прикладних задач

Пакети прикладних програм. Системи підтримки прийняття рішень та особливості їх реалізації. Системи імітаційного моделювання та особливості їх реалізації. Вирішувачі задач. Системи обчислень з динамічною зміною стратегій. Системи автоматизації доведення теорем. Системи автоматизації проектування. Інтерактивні системи. Системи штучного інтелекту.

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

1. Ахо А., Хопкрофт Дж., Ульман Дж. Анализ и построение внчислительных алгоритмов.–М.: Мир, 1975. – 457 с.

2. Барендрегт X. Ламбда-исчисление. Его синтаксис и семантика. –М:  Мир, 1985. – 606 с.

3. Берж К. Теория графов и ее приложение. – М.: ИЛ, 1962. – 320 с.

4. Братко И. Программирование на языке ПРОЛОГ для искусственного интеллекта. – М.: Мир, 1990. – 560 с.

5. Вагин В.Н. Дедукция и обобщение в системах принятия решений. – М.: Наука, 1968. – 384 с.

6. Глушков В.М. Введение в кибернетику. – Киев: Изд-во АН УССР, 1964. – 324 с.

7. Глушков В.М. Основы безбумажной информатики. – М.: Наука, 1982. –324 с.

8. Глушков В.М., Цейтлин Т.Е., Ющенко Е.Л. Алгебра. Языки. Программирование. 3-е изд. – Киев: Наук. думка, 1989. – 234 с.

9. Голдблат Р. Топосы. Категорньй анализ логики. – М.: Мир, 1983. – 476 с.

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

11. Гольштейн Е.Г. Теория двойственности в математическом программировании и ее при-ложения. – М.:  Наука, 1971. – 352 с.

12. Гринченко Т.А., Стогний А.А. Машинний интеллект и новые информационные технологии. – Киев: Изд-во "Манускрипт" при АН України, 1993. – 164 с.

13. Грэй П. Логика, алгебра и базы данных. – М.: Машиностроение, 1989. – 359 с.

14. Демьянов В.Ф., Васильєв Л.В. Недифференцируемая оптимизация. – М.: Наука, 1981. –391 с.

15. Евстигнеев В.А., Касьянов В.Н. Теория графов. Алгоритмы обработки деревьев. – Новосибирск: Наука, 1994. – 360 с.

16. Еремин И.И., Мазуров В.Д., Астафьев Н.Н. Несобственные задачи линейного и выпук-лого программирования. – М.: Наука, 1983. – 336 с.

17. Ермольев Ю.М. Методы стохастического программирования. – М.: Наука, 1976. – 240 с.

18. Замулин А.В. Системы программирования баз данньх и знаний .– М. Наука, 1990. –234 с.

19. Зелковец М., Шоу А., Геннон Дж. Принципы разработки программного обеспечения. –М.: Мир, 1982. – 368 с.

20. Калиниченко Л.А., Рывкин В.М. Машины баз данных и знаний. – М.:  Наука, 1990. –269 с.

21. Капитонова Ю.В., Летичевский А.А. Математическая теория проектирования вычислительных систем. – М.:Наука, 1978. – 295 с.

22. Касьянов В.Н. Оптимизирующие преобразования программ. – М.: Наука, 1988. – 335 с.

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

24. Ковалев М.М. Дискретная оптимизация (целочисленное программирование). – Минск: Изд-во Белорус. ун-та, 1977. – 192 с.

25. Кокорева Л.В., Перевозчикова О.Л., Ющенко Е.Л. Диалоговые системи и представ-ление знаний. – Киев: Наук. думка, 1993.– 448 с.

26. Королев Л.Н. Структура ЭВМ и их математическое обеспечение. – М.: Наука, 1978. – 352 с.

27. Котов В.Е. Сети Петри. – М.: Наука, 1984. – 160 с.

28. Котов В.Е. Введение в теорию схем программ. – Новосибирск. – М.: Наука, 1991. – 247 с.

29. Котов В.Е., Сабельфельд В.К Теория схем программ. – М.: Наука, 1991. – 247 с.

30. Кук Д., Бейз Г. Компьютерная математика. – М.: Мир, 1990. – 383 с.

31. Лавров И.А., Максимова Л.Л. Задачи по теории множеств, математической логике и теория алгоритмов. – М.: Наука, 1975. – 234 с.

32. Логический подход к искусственному интеллекту: от классической логики к логи-ческому программированию /А. Тей., П. Грибомон , Ж. Луи и др. – М.: Наука, 1990. – 632 с.

33. Лоэв М. Теория вероятностей. – М.: ИЛ. 1962 – 720 с.

34. Лорьер Ж. Л. Системы искусственного интеллекта. – М.: Мир, 1990. – 568 с.

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

36. Мальцев А.И. Алгоритмы и рекурсивнне функции. – М.: Наука, 1975. – 237 с.

37. Марков А.А. Теория алгоритмов. – Труды математического института им. В.А. Стеклова АН СССР, 1954. – Т. 42. – 376 с.

38. Медник С., Донован Дж. Операционные системы. – М.: Мир, 1979. – 234 с.

39. Мендельсон И. Введение в математическую логику. – М.: Мир, 1985. – 307 с.

40. Мелехов А.Н., Бернштейн Л.С, Коровин СЯ. Ситуационные советующие системы с нечеткой логикой. – М.: Наука, 1990. – 272 с.

41. Мину М. Математическое программирование. М.: Наука, 1989. – 485.

42. Михалевич В.С., Шор Н.З. Вычислительные методы выбора оптимальных проектных решений. – Киев: Наук. думка, 1977. – 178 с.

43. Немировский А.С, Юдин Д.Б. Сложность задач и эффективность методов оптимизации. – М.: Наука, 1979. – 383 с.

44. Озкарахан 3. Машины баз данных и управления базами данных. – М.: Мир, 1989. – 659 с.

45. Оре О. Теория графов.  – М.: Наука, 1960. – 336 с

46. Организация экспертных систем / М. Стефик, Я. Зйкинс, Р. Валлер и др. – Кибернетический сборник. – М.: Мир, 1985. – Вып. 22. – С. 170–220.

47. Осуга С. Обработка знаний. – М.: Мир, 1969. – 293 с.

48. Пападимитриу X., Стайглиц К. Комбинаторная оптимизаиия.: – Мир, 1985.  – 510 с.

49. Парасюк И.Н., Сергиенко И.В. Пакеты программ анализа даннных: технология разработки. – М.: Финансы и статистика, 1988. – 159 с.

50. Представление и использование знаний / Х.Уэнс, Т.Кояма, Т.Окамото и др. – М.: Мир, 1989. – 220 с.

51. Подиновский В.В., Ногин В. Д. Парето-оптимальные решения многокритериальных задач. – М.:Наука,1982. – 256 с.

52. Поляк Б.Т. Введение в оптимизацию. – М.: Наука, 1983.–382 с.

53. Приобретение знаний / Под ред. С. Осуги, Ю. Саэки. – М.: Мир,1990. – 304 с.

54. Пшеничний Б.Н. Метод линеаризации. – М.: Наука, 1983. – 136 с.

55. Пшеничний Б.Н. Выпуклый анализ и экстремальные задачи. – М.:Наука, 1986. – 234 с.

56. Райзер. Г. Комбинаторная математика. – М.: Мир, 1966. –127 с.

57. Рокафеллар Р.  Выпуклый анализ. – М.: Мир,1973. – 468 с.

58. Сергиенко И.В. Математические модели и методы решения задач дискретной оптимизации. – Киев: Наук.думка, 1985. – 384 с.

59. Системы управлення базами данных и знаний / А.Н. Наумов, .А.М. Вандров, В.К. Иванов и др.// Изд-во Финансы и статистика, 1991. – 352 с.

60. Смальян Р. Теория формальных систем. – М.: Наука, 1981. – 206 с.

61. Тыугу З.Х. Концептуальное программирование. – М.: Наука,1 967.– 256 с.

62. Уилсон А. Введение в теорию графов. – М.: Мир, 1977. – 207 с.

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

64. Фелер В. Введение в теорию вероятностей. – М.: Мир, 1964. – 376 с.

65. Хантер П. Проектирование и конструирование компиляторов. – М.: Финансы и статистика, 1984. – 232 с.

66. Харари Ф. Теория графов. – М.: Мир, 1973. – 195 с.

67. Холл М. Комбинаторика. – М.: Мир, 1970. – 234 с.

68. Ху Т. Целочисленное программирование и потоки в сетях. – М.: Мир, 1974. – 519 с.

69. Хювенен 3., Сеппенек И.  Мир Лиспа: В 2-х т. – М.: Мир, 1990. – Т. 1 – 447 с.; Т. 2 – 319 с.

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

71. Шор Н.З.  Методы минимизации недифференцируемых функций и их приложения. –Киев: Наук. думка, 1979. – 199 с.

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

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

 

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

доктор фізико-математичих наук, професор,

академік НАН України ЛЕТИЧЕВСЬКИЙ О.А.,

доктор фізико-математичних наук, професор КНОПОВ П.С.

 

На початок сторінки> 

© ІПC НАН України, 2008 — 2015 
Всі права захищені
Адміністрація ресурсу не несе відповідальності за протиправні дії третіх осіб
Тел.: +38 (044) 526 21 48