Программа кандидатского экзамена по специальности 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