Информатика и вычислительная техника

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ БЮДЖЕТНОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ОБРАЗОВАНИЯ«МОСКОВСКИЙ ПОЛИТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ»(МОСКОВСКИЙ ПОЛИТЕХ)УТВЕРЖДАЮПроректор по учебной и научной работе_______________________ Ю.М. Боровин«___» ______________20___г.ПРОГРАММАвступительного испытания для поступающих на обучениепо программам подготовки научно-педагогических кадров в аспирантуреНаправление подготовки: 09.06.01 Информатика и вычислительная техникаМосква 2017Разработчики программы:Заведующий кафедрой «Информатика и информационные технологии»д.т.н., проф.

Д.И.ПоповДекан Факультета Информатики и систем управленияк.т.н., доцент А.Ю.ФилипповичНачальник Научно-образовательного центра инфокогнитивных технологийк.т.н., доцент Ю.Н.ФилипповичСОДЕРЖАНИЕ1. Введение..............................................................................................................

32. Экзамен по специальности ................................................................................ 32.1. Теория информации..................................................................................... 32.2. Теория алгоритмов и формальных языков ................................................ 42.3. Теория множеств, теория графов и математическая логика ................... 42.4. Элементы искусственного интеллекта ......................................................

42.5. Основы теории баз данных ......................................................................... 52.6. Языки и технологии программирования ................................................... 52.7. Сети ЭВМ и телекоммуникации ................................................................ 62.8. Методы представления и оценки знаний, основы тестологии................ 62.9. Когнитивные и семиотические модели ..................................................... 62.10.

Системный анализ, управление и обработка информации ..................... 72.11. Автоматизация и управление технологическими процессами ипроизводствами...................................................................................................... 72.12. Управление в социальных и экономических системах ...........................

82.13. Рекомендуемая литература ......................................................................... 93. Конкурс портфолио.......................................................................................... 1321. ВВЕДЕНИЕВступительные испытания для поступающих в аспирантуру состоят из двухэтапов:- экзамен по специальности;- конкурс портфолио.2. ЭКЗАМЕН ПО СПЕЦИАЛЬНОСТИВ основу программы вступительного испытания по специальности для поступающих в аспирантуру по направлению 09.06.01 Информатика и вычислительная техника положены вопросы из следующих учебных дисциплин и модулей, изучаемых на уровне магистратуры по направлению 09.04.01 Информатика ивычислительная техника:- Теория информации;- Теория алгоритмов и формальных языков;- Теория множеств, теория графов и математическая логика;- Элементы искусственного интеллекта;- Основы теории баз данных;- Языки и технологии программирования;- Сети ЭВМ и телекоммуникации;- Методы оценки знаний и тестология;- Когнитивные и семиотические модели;- Системный анализ, управление и обработка информации;- Автоматизация и управление технологическими процессами и производствами;- Управление в социальных и экономических системах.Основные вопросы, которые должен знать поступающий в аспирантуру понаправлению 09.06.01.Информатика и вычислительная техника, изложены ниже.Билет на экзамен по специальности содержит 3 вопроса из разных разделовуказанного ниже перечня.2.1.

Теория информацииИнформация. Основные понятия. Определение количества информации.Свойства количества информации. Понятие энтропии. Свойства энтропии.Условная информация и условная энтропия. Свойства условной энтропии.Структура и закономерности протекания информационных процессов.Измерение как первичный информационный процесс, его характеристики.Модели процессов передачи, обработки и накопления информации. Кодированиеинформации. Экономное кодирование. Коды Хаффмана и Шеннона-Фано. Принципы помехоустойчивого кодирования. Код с проверкой на четность.

Матричныйкод. Код Хэмминга.32.2. Теория алгоритмов и формальных языковФормальные грамматики, их основные классы. Классификация грамматик иязыков по Хомскому. КС-грамматики и деревья выводов в них. Разбор цепочек.Однозначность и существенная неоднозначность КС-языков. Примеры не КСязыков. Автоматные грамматики и конечные автоматы.

Регулярные выражения.Детерминированные и недетерминированные конечные автоматы. Обратная польская запись и ее использование. МП-автоматы различных типов, их эквивалентность КС-грамматикам.Детерминированные автоматы и языки, их основные свойства. Элементытеории трансляции. Методы построения трансляторов. Лексический, синтаксический и семантический анализ. Понятие вычислимой функции. Интуитивное понятие алгоритма. Этапы уточнения понятия алгоритма. Частичные и всюду определённые алгоритмы.Машина Тьюринга.

Конфигурации. Словарные функции. Вычислимость по Тьюрингу. Тезис Тьюринга. Операции над машинами Тьюринга.Диаграммы Тьюринга.Понятие сложности алгоритма. Временная и емкостная сложность. Рекурсивные функции. Понятие простейшей функции. Операции суперпозиции,примитивной рекурсии, минимизации. Тезис Чёрча.

Эквивалентность различных моделей алгоритмов. Эквивалентность некоторых комбинаторных задач.Классы Р и NР. NР-трудные и NР-полные задачи. Существование алгоритмическинеразрешимых проблем. Понятия индивидуальной и массовой задачи. Примерыалгоритмически неразрешимых проблем.Теория множеств, теория графов и математическая логикаПонятие множества. Способы задания множеств: явный, описательный, рекурсивный. Примеры задания множеств.Отношения между множествами: включение, равенство. Пустое множество и универсальное множество. Число подмножеств конечного множества.Операции над множествами: объединение, пересечение, дополнение, симметрическая разность.

Свойства операций.Декартово произведение. Соответствия, отношения и их свойства. Булевы алгебры. Основные операции математической логики. Формулы и законы алгебрывысказываний. Исчисление высказываний и его свойства. Исчисление предикатовпервого порядка и его свойства.Основные понятия теории графов. Способы представления. Нахождение минимальных путей между вершинами в графе. Гамильтоновы цепи и циклы. Задачипланирования.

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

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

Алгоритм унификации и его обоснование. Экспертные системы.2.5. Основы теории баз данныхЧетыре этапа эволюции систем, управляющих базами данных. Ассоциацииэлементов данных. Схемы. Иерархическая, сетевая, реляционная организацияданных. Реляционные базы данных, нормализация отношений.Реляционная алгебра. Основные операции. Примеры запросов в реляционнойалгебре. Реляционное исчисление. Примеры запросов реляционном исчислении.Язык SQL. Примеры описаний структур данных и запросов.

Общие принципы архитектуры "клиент-сервер". Транзакции и механизмы поддержки целостностиданных.Администрирование баз данных. Распределенные базы данных. Физическаяорганизация данных.2.6. Языки и технологии программированияСостав, классификация и описание языков программирования. Способы описания синтаксиса языка. Классификация алгоритмических языков программирования.