Федеральное государственное бюджетное образовательное учреждение

высшего профессионального образования

НАЦИОНАЛЬНЫЙ ИССЛЕДОВАТЕЛЬСКИЙ УНИВЕРСИТЕТ «МЭИ»

«УТВЕРЖДАЮ»

Директор АВТИ

Лунин В.П.

подпись «» _ 2014 г.

ПРОГРАММА ВСТУПИТЕЛЬНОГО ИСПЫТАНИЯ

ПО СПЕЦИАЛЬНОЙ ДИСЦИПЛИНЕ ПРИ ПОСТУПЛЕНИИ В

АСПИРАНТУРУ

Направление – 09.06.01 Информатика и вычислительная техника код, название Направленность – Теоретические основы информатики название Москва, I. Теория информации Информатика как наука, изучающая информацию и ее свойства в естественных, искусственных и гибридных системах. Место информатики в системе наук. Понятия энтропии и информации.

Кодирование сообщений. Средняя длина кодового слова и избыточность.

Теорема Шеннона о передаче сообщений по дискретному каналу без памяти.

II. Теория множеств и теория графов Понятие множества. Счетные и несчетные множества, мощность множества. Операции и отношения на множествах. Упорядоченные множества.

Теоретико-множественное и алгебраическое определения решетки, их эквивалентность. Свойства решеток. Булевы решетки.

Понятие графа, основные характеристики. Эквивалентность и изоморфизм графов. Эйлеровы и гамильтоновы графы. Плоские графы и их основные свойства. Взвешенные графы, задачи о кратчайших маршрутах.

III. Математическая логика и моделирование рассуждений Предмет математической логики. Формальные системы (ФС).

Разрешимость и неразрешимость (ФС). Исчисление высказываний как класс ФС. Свойства системы аксиом исчисления высказываний (полнота, непротиворечивость и независимость). Исчисление предикатов первого порядка. Теорема o дедукции для исчисления предикатов. Свойства системы аксиом: полнота и непротиворечивость. Теорема Геделя o полноте.

Автоматическое доказательство теорем. Нормальные формы:

дизъюнктивная, конъюнктивная, пренексная. Логические следствия.

Сколемовская нормальная форма. Универсум Эрбрана и эрбрановская база.

Семантические деревья. Принцип резолюции для логики предикатов первого порядка. Модификации принципа резолюции: семантическая резолюция, линейная резолюция. Метод аналитических таблиц в логике предикатов первого порядка. Множество Хинтики для логики предикатов первого порядка.

Методы дедуктивного вывода в системах искусственного интеллекта.

Использование принципа резолюции в дедуктивных вопросно-ответных системах, при построении плана действий робота. Логика и модифицируемые рассуждения. Формализация модифицируемых рассуждении. Модальные логики знания и веры. Немонотонные логики Мак-Дермотта.

Автоэпистемические логики.

IV. Основы теории алгоритмов, вычислимые функции и теоретические аспекты программирования Модели вычислимости: машины Тьюринга, рекурсивные функции, нормальные алгоритмы Марковa. Алгоритмически неразрешимые проблемы.

Формальные языки, их классификация, средства задания и синтаксического анализа. -исчисление. Функциональные языки, основанные на -исчислении на примере ЛИСП. Семантика языков программирования, способы задания. Трактовка программ как наименьших фиксированных точек соответствующих им преобразований данных.

Модели взаимодействующих и параллельных процессов: сети Петри, модель Хоара. Примеры эффективных (полиномиальных) алгоритмов:

быстрые алгоритмы поиска и сортировки; полиномиальные алгоритмы для задач на графах и сетях.

Отношения и функции. Отношение эквивалентности и разбиения.

Отношения частичного порядка.

V. Языки программирования Классификация языков программирования в соответствии c их проблемной ориентацией и базовыми конструкциями. Функциональные языки программирования: ЛИСП, FPTL и др. Объектно-ориентированные языки программирования.

Среды программирования: назначение, основные компоненты, сравнительный анализ. Визуальные формы, схемы и диаграммы в программирований. Язык UML. Модели и системы человеко-машинных интерфейсов. Машинная графика.

Пакеты прикладных программ (ППП). Системная часть и наполнение.

Языки общения с ППП. Технология разработки и сопровождения программ.

Жизненный цикл программы. Этапы разработки, степень и пути их автоматизации.

Языки и средства программирования Internet приложений. Язык гипертекстовой разметки HTML, основные конструкции, средства подготовки гипертекста. Язык написания сценариев Java Script.

VI. Модели представления данных и знаний. Системы управления Модели баз данных. Реляционные базы данных (БД), языки запросов.

Линейное представление документов, запросов, тезауруса, индексирования, поиска. Понятие лексической совместимости и тезаурусной согласованности.

CASE-средства и их использование при проектировании БД. Стандарты языков SQL. Современные системы управления БД (СУБД), их сравнительные характеристики.

Модели представления знаний. Организация баз знаний (БЗ). Методы приобретения знаний, индуктивные методы обучения по примерам, методы на основе деревьев решений. Системы управления БЗ (СУБЗ).

Информационно-поисковые системы. Классификация. Методы реализации и ускорения поиска. Защита информации в компьютерах, вычислительных системах и сетях. Основные концепции Semantic Web.

VII. Вычислительные машины, системы и сети Многопроцессорные и многомашинные комплексы. Вычислительные кластеры. Проблемно-ориентированные параллельные структуры: матричные вычислительные системы (ВС), систолические структуры, нейросети.

Методы и средства передачи данных в информационных ВС, протоколы передачи данных. Глобальные, территориальные и локальные сети. Основные сетевые концепции. Модели взаимодействия компьютеров в сети. Особенности архитектуры локальных сетей (Ethernet, Token Ring, FDDI). Сеть Internet, доменная организация, семейство протоколов TCP/IP.

Архитектура современных компьютеров. Организации памяти и архитектура процессора. ВС, обеспечивающие выполнение вычислений, управляемых потоком данных. Организация ввода-вывода, каналы и процессоры ввода-вывода, устройства сопряжения с объектами. Назначение, архитектура и принципы построения информационно-вычислительных сетей (ИВС). Локальные и глобальные ИВС, технические и программные средства объединения различных сетей. ИВС и распределенная обработка информации.

Классификация ВС по способу организации параллельной обработки.

Типы параллельных ВС. Концепция GRID. Операционные средства для управления параллельной и распределенной обработкой (.NЕТ, МРI, СОRВА и др.). Управление параллельными процессами в ВС.

Операционные средства управления сетями. Эталонная модель взаимодействия открытых систем ISO/OSI. Маршрутизация и управление потоками данных в сети. Сетевые ОС, модель клиент – сервер, средства управления сетями в ОС UNIX, MS Windows. Принципы функционирования Internet. Семейство протоколов TCP/IP, доменная адресация в Internet, типовые информационные объекты и ресурсы. Удаленный доступ к ресурсам сети. Организация электронной почты, телеконференций. Протоколы передачи файлов, язык разметки гипертекста HTML, WWW-серверы.

VIII. Методы оптимизации и принятия решений Постановка задачи и классификация методов оптимизации. Методы нулевого порядка: покоординатного спуска, случайного поиска. Методы первого порядка (градиентные): с дроблением шага, наискорейшего спуска, сопряженных направлений. Методы второго порядка: Ньютона, НьютонаРафсона. Постановка задачи линейного программирования (ЗЛП).

Графический метод решения. Симплексный метод. Транспортная задача.

Определение опорного плана транспортной задачи.

Задачи условной оптимизации. Выпуклые функции. Задачи оптимизации с ограничениями в форме равенств и неравенств. Методы штрафных и барьерных функций, комбинированный метод штрафов. Методы проекции градиента. Методы возможных направлений. Задачи векторной оптимизации. Основные понятия и определения. Определение Паретооптимальных решений многокритериальной задачи. Методы решения задач многокритериальной оптимизации: свертки, последовательных уступок.

Метод гарантированного результата или метод минимакса.

Общая схема процесса принятия решений. Задача принятия решений.

Специфика принятия решений в условиях определенности, риска, неопределенности. Классификация методов теории принятия решений.

Строгие и эвристические методы. Поиск решения в пространстве состояний.

Задачи эвристического поиска. Метод уменьшения различий. Поиск решения на дереве игры: максимнный метод и метод -отсечения.

Основы теории статистических решений («игры с природой»). Методы поиска решения при известных и неизвестных вероятностях состояний природы. Основы теории ожидаемой полезности. Рациональное и иррациональное поведение лица, принимающего решения. Функция ожидаемой полезности. Теория субъективной ожидаемой полезности.

IX. Искусственный интеллект и интеллектуальные системы Понятие искусственного интеллекта (ИИ), задачи ИИ. Основные направления и этапы развития ИИ. Интеллектуальные системы (ИС) как системы, основанные на знаниях. Понятие экспертной системы (ЭС) и системы поддержки принятия решений (СППР). Языки и системы представления знаний: LISP, PROLOG, CLIPS и др.

Поиск решения в условиях неопределенности: теоретиковероятностные методы (метод Байеса, метод на основе субъективных вероятностей (коэффициентов уверенности), байесовские сети доверия).

Поиск решения в условиях неопределенности: теория свидетельств Демпстера-Шейфера. Использование нечеткой логики при поиске решения.

Приобретение знаний в ИС (ЭС). Формирование знаний в ИС, машинное обучение и формирование понятий. Интеллектуальный анализ данных. Эволюционное моделирование (ЭМ). Понятие генетического алгоритма (ГА), основные этапы. Введение в искусственные нейронные сети (ИНС). Математическая модель нейрона, персептрон. Однослойные и многослойные сети. Алгоритмы обучения нейронной сети.

Инструментальные средства конструирования ИС: CLIPS, G2, системыоболочки.

1. Базы знаний интеллектуальных систем / Т.А. Гаврилова, В.Ф.

Хорошевский. – СПб.: Питер, 2001.

2. Башлыков А.А., Еремеев А.П. Экспертные системы поддержки принятия решений в энергетике / Под ред. А.Ф. Дьякова. – М.: Издательство МЭИ, 1994.

информационные технологии: Учеб. Пособие. – М.: Изд-во МГТУ им. Н.Э.

Баумана, 2005.

4. Вагин В.Н., Головина Е.Ю., Загорянская А.А., Фомина М.В.

Достоверный и правдоподобный вывод в интеллектуальных системах. 2-е издание // Под редакцией В.Н. Вагина, Д.А. Поспелова. – М.: ФИЗМАТЛИТ, 2008.

5. Воеводин В.В., Воеводин В.Вл. Параллельные системы и параллельные вычисления. Изд. БХВ, Санкт-Петербург, 2011.

6. Дейт К. Введение в системы баз данных. – М.: Вильямс, 2005.

7. Джарратано Д., Райли Г. Экспертные системы: принципы разработки и программирование: Пер. с англ. – М.: ООО «И.Д. Вильямс», 2007.

8. Еремеев А.П., Куриленко И.Е. Применение темпоральных моделей в интеллектуальных системах / Интеллектуальные системы. Колл.

монография. Выпуск третий. / Под. Ред. В.М. Курейчика. – М.: Физматлит.

2009. – С. 124-139.

9. Зыков А.А. Основы теории графов. – М.: Вузовская книга, 2004.

10. Искусственный интеллект: В 3 кн. Справочник / Под. ред. Э.В.

Попова, Д.А. Поспелова, В.Н. Захарова, В.Ф. Хорошевского. – М.: Радио и связь. – 1990.

11. Кандрашина Е.Ю., Литвинцева Л.В., Поспелов Д.А. Представление знаний о времени и пространстве в интеллектуальных системах. / Под ред.

Д.А. Поспелова. – М.: Наука. Гл. ред. физ.-мат. лит., 1989.

12. Карпов Ю.Г. MODEL CHECKING. Верификация параллельных и распределенных программных систем. – СПб.: БХВ-Петербург, 2010.

13. Кнут Д. Искусство программирования. Т. 1-3. М., – СПб., Киев: ИД "Вильямс", 2000.

14. Кудрявцев В.Б., Андреев А.Е., Гасанов Э.Э. Теория тестового распознавания. М.: Физматлит, 2007.

15. Кузнецов О.П. Дискретная математика для инженеров. – СПб.: Издво «Лань», 2004.

16. Кук Д., Бейз Г. Компьютерная математика. – М.: Наука, 2000.

17. Ларичев О.И. Теория и методы принятия решений. – М.: Логос, 2002.

18. Логический подход к искусственному интеллекту: От модальной логики к логике баз данных: Пер. с франц. / Тейз А., Грибомон П., Юлен Г. и др. – М.: Мир, 1998.

19. Лопатин В.Н. Правовые основы информационной безопасности:

Курс лекций. – М.: Изд-во МИФИ, 2000.

20. Люгер Дж.Ф. Искусственный интеллект. Стратегии и методы решения сложных проблем: Пер. с англ. – М.: Издательский дом "Вильямс", 2003.

21. Макленнен Д. Microsoft SQL Server 2008: Data Mining – интеллектуальный анализ данных. – BHV-СПб, 2009.

22. Мартин Дж. Организация баз данных в вычислительных системах. – М.: Мир, 2000.

23. Мерков А.Б. Распознавание образов. Введение в методы статистического обучения. М.: ЭДИТОРИАЛ УРСС, 2011.

24. Назаров С.В., Широков А.И., Современные операционные системы.

– М.: Изд-во Бином, 2011.

25. Новак В., Перфильева И, Мочкорж И. Математические принципы нечеткой логики. – М.: Физматлит, 2006.

26. Новейшие методы обработки изображений. / Под ред. А.А.

Потапова. – М.: ФИЗМАТЛИТ, 2008.

27. Осипов Г.С. Методы искусственного интеллекта. – М.:

ФИЗМАТЛИТ, 2011.

28. Петровский А. Б. Теория принятия решений. – М.: Академия. 2009.

29. Поспелов Д.А. Моделирование рассуждений. Опыт анализа мыслительных актов. - М.: Радио и связь, 1989.

30. Рассел С., Норвиг П. Искусственный интеллект: современный подход, 2-е изд.: Пер. с англ. – М.: Издательский дом «Вильямс», 2006.

31. Редько В.Г. Эволюция, нейронные сети, интеллект: Модели и концепции эволюционной кибернетики. М.: УРСС, 2011.

32. Рыбина Г.В. Основы построения интеллектуальных систем: учебное пособие. – М.: Финансы и статистика; ИНФРА-М, 2010.

33. Статические и динамические экспертные системы: Учеб. пособие / Э.В. Попов, И.Б. Фоминых, Е.Б. Кисель, М.Д. Шапот. – М.: Финансы и статистика, 1996.

34. Тидвелл Дж. Разработка пользовательских интерфейсов. – Питер, 2008.

35. Финн В.К. Искусственный интеллект: Методология, применения, философия. – М.: КРАСАНД, 2011.

36. Фролов А.Б. Классификация и распознавание топологических форм. М.: Изд-во МЭИ, 2010.

37. Хоар Ч. Взаимодействующие последовательные процессы. – М.:

Изд. «Мир», 1989.

38. Хопкрофт Дж., Мотвани Р., Ульман Дж. Введение в теорию автоматов, языков и вычислений. – М.: Вильямс, 2002.

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

40. Эндрюс В.Г.. Основы многопоточного и параллельного программирования. – М.: Изд. дом «Вильямс», 2003.