09.04.04 Программная инженерия

Приложение № 6к приказу № 661-1 от 16 ноября 2015 г.МОСКОВСКИЙ АВИАЦИОННЫЙ ИНСТИТУТ(НАЦИОНАЛЬНЫЙ ИССЛЕДОВАТЕЛЬСКИЙ УНИВЕРСИТЕТ)ПРОГРАММАВСТУПИТЕЛЬНОГО МЕЖДИСЦИПЛИНАРНОГО ЭКЗАМЕНА ВМАГИСТРАТУРУ ПО НАПРАВЛЕНИЮ ПОДГОТОВКИ09.04.04 «ПРОГРАММНАЯ ИНЖЕНЕРИЯ»Программа составлена в соответствии с требованиями Федеральногогосударственного образовательного стандарта высшего профессиональногообразования по направлению подготовки 09.03.04 – «Программнаяинженерия».1.Цели и задачи вступительных испытанийВступительные испытания предназначены для определения уровняподготовленности абитуриента и проводятся с целью определениясоответствия профиля и уровня полученного им образования длядальнейшего обучения в магистратуре по направлению 09.04.04 –«Программная инженерия».2.

Содержание вступительных испытанийОценка уровня знаний проводится в виде междисциплинарноговступительного экзамена. В основу программы вступительного экзаменаположены квалификационные требования в области информатики, ЭВМ ипериферийных устройств, операционных систем, программирования, сетей ителекоммуникаций, защиты информации, баз данных, разработкипрограммного обеспечения, предъявляемые к бакалаврам направления09.03.04 – «Программная инженерия».Общая оценка подсчитывается по 100-балльной шкале как суммабаллов по всем разделам вступительных испытаний.Раздел 1.

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

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

Понятие кратчайшего пути в графе. Алгоритм Дейкстры. Задачакоммивояжера. Метод ветвей и границ. Гамильтонов путь в графе и егопоиск. Эйлеров путь в графе. Условия существования. Алгоритмы поиска.Примеры задач на Гамильтонов и Эйлеров путь. Исчисление предикатов2первого порядка. Нормальные формы, алгоритмы приведения к ним. Связьлогики предикатов с естественным языком. Примеры задач на логикупредикатов. Формализация понятия алгоритма, машина Тьюринга, тезисЧерча. Алгоритмически неразрешимые проблемы, меры сложностиалгоритмов, легко и трудноразрешимые задачи, классы задач P и NP, NP полные задачи, понятие сложности вычислений, эффективные алгоритмы.Раздел 2.

ИнформатикаКоличество и качество информации. Единицы измерения информации.Информация и энтропия. Формула Хартли. Количество информации поШеннону. Двоичный алфавит. Кодирование текстовых данных.Кодирование чисел. Позиционные системы счисления. Методы переводачисел. Двоичная арифметика. Коды: прямой, обратный, дополнительный,модифицированный.

Оптимальное основание системы счисления.Раздел 3. ЭВМ и периферийные устройстваОсновные узлы ЦП и их назначение. Команды ЭВМ: арифметические,логические, перехода, связь программы с подпрограммой. Форматы команд,адресность команд. Способы адресации. Основные стадии выполнениякоманды. Микропрограмма выполнения команд с индексной адресацией.Принцип работы блока устройства управления (БУУ). МикропрограммнаяреализацияБУУ.Горизонтальнаяивертикальнаяреализациямикропрограммного БУУ. Схемная реализация БУУ. Сравнениемикропрограммной и схемной реализации БУУ. АЛУ – назначение,классификация.

Выполнение операций сложения, вычитания над числами сфиксированной точкой с использованием обратного и дополнительногокодирования. Определение переполнения. АЛУ для выполнения операцииумножения на числами с фиксированной точкой. Четыре способавыполнения операции умножения. Микропрограмма. АЛУ для выполненияоперации деления на числами с фиксированной точкой. Деление свосстановлением и без восстановления остатка. Микропрограммавыполнения операции деления. Формат представления чисел с плавающейточкой. Мантисса, порядок, смещенный порядок.

Диапазон и точность.Выполнение арифметических операций над числами с плавающей точкой.Условие переполнения разрядной сетки. Принципы обработки прерыванийв ЭВМ. Организация системы прерываний с помощью «старых» и «новых»ячеек памяти. Стековый механизм организации прерываний. Прямой доступк памяти.

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

Организация КЭШ-памяти.Алгоритмы замещения. Буферная память прямого соответствия, секторный,3ассоциативный и группо-ассоциативный способ отображения оперативнойпамяти. Конвейерное и параллельное выполнение операций, команд,программ. Межкомандная зависимость: информационная, ресурсная,программная. Диспетчеризация конвейера. Блок устройства управления.Временные проблемы. Синхронизация. Мейнфреймы.

Кластерныеархитектуры. Ассоциативные, матричные, векторные ЭВМ. Супер-ЭВМ.Раздел 4. Операционные системыАрхитектурные особенности ОС. Монолитное ядро. Микроядернаяархитектура. Нано-ядро. Экзо-ядро. Процессы. Операции над процессами,контекст процесса, одноразовые и многоразовые операции. Переключениеконтекста.

Планирование процессов: уровни планирования, краткосрочное идолгосрочное планирование. Критерии планирования процессов итребования к алгоритмам. Параметры планирования. Вытесняющее иневытесняющее планирование на примере алгоритмов SJF и SRT.Алгоритмы планирования: FCFS, RR, приоритетное планирование.Критическая секция. Организация взаимоисключения для критическихучастков.

Условие прогресса, условие ограниченного ожидания. Запретпрерываний. Алгоритм Петерсона. Механизмы синхронизации. Семафоры.Решение проблемы «производитель-потребитель» с помощью семафоров.Мониторы. Сообщения. Тупики. Разделяемые и выделенные ресурсы.Условия возникновения тупиков. Борьба с тупиками. Алгоритм банкира.Предотвращение тупиков за счет нарушения условий возникновениятупиков. Обнаружение тупиков.

Редукция графа повторно используемыхресурсов. Модель Холта. Восстановление после тупиков. Схемы управленияпамятью: Схема с фиксированными разделами. Оверлейная структура.Динамическое распределение. Свопинг. Схема с переменными разделами.Аппаратно-независимый уровень управления виртуальной памятью.Исключительные ситуации при работе с памятью. Страничное нарушение.Стратегии управления страничной памятью. Алгоритмы замещениястраниц: алгоритм FIFO, Аномалия Билэди; оптимальный алгоритм;алгоритмы LRU, NFU. Определение драйвера устройства.

Место драйвера вОС. Символьный, Блочный, Сетевой драйвер. Взаимодействие драйвера ОСи оборудования: порты и память ввода-вывода, обработка прерываний.Раздел 5. ПрограммированиеОбоснованность типов данных в языке высокого уровня и их применения.Типы констант в языке высокого уровня. Рекурсивный доступ кподпрограмме, особенности, реализация. Работа с внешними библиотками.Объектно-ориентированная парадигма. Объект и класс. Поля данных иметоды. Открытые и закрытые компоненты класса. Методы-конструкторыи методы-акцессоры. Перегрузка методов.

Инкапсуляция, наследование,полиморфизмвобъектно-ориентированномпрограммировании.Защищённые компоненты класса. Переопределение методов. Экономиякода программ при наследовании. Виртуальные функции (методы).4Экономия кода с использованием виртуальных функций. Абстрактныеметоды и абстрактные классы. Полиморфные объекты. Основные этапыпроектирования программы. Критерии качества программы. Жизненныйцикл программных систем. Требования, предъявляемые к разработкепрограммного обеспечения (ПО), Методы разработки программногообеспечения (ПО).

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

Кабели. Сетевые устройства.Коммутация на основе каналов, пакетов. Агрегация каналов.Мультиплексирование. Первичные сети. Модели ISO OSI, TCP IP. Уровни,протоколы. Инкапсуляция и деинкапсуляция. Принцип работы Ethernet.Атрибуты кадра Ethernet. MAC Ethernet. Разрешение адресов. Адресация вкорпоративной сети. Использование схемы адресации иерархической IPсети.

Использование VLSM. Создание схемы IP- адресации. Описание IPv4и IPv6. Структура IPv4 и IPv6 адресов. Маска подсети. Одноадресная,широковещательная и многоадресная рассылка IPv4. Типы адресов IPv4 иIPv6. Реализация статической маршрутизации. Типы статическихмаршрутов.

Настройка статических маршрутов и маршрутов по умолчанию.Настройка суммарных и плавающих статических маршрутов. Динамическаямаршрутизация. Алгоритмы, протоколы. Автономные системы. Таблицамаршрутизации. Определение оптимального маршрута. Предотвращениепетель коммутации. Настройка VLAN. Транкинг и маршрутизация междуVLAN. Обслуживание VLAN в корпоративной сети. Преобразованиесетевых адресов для протокола IPv4. Принцип работы NAT. СтатическийNAT. Динамический NAT. NAT с перегрузкой. Настройка NAT.

Соединениятипа "точка-точка". Инкапсуляция HDLC. Принцип работы протокола PPP.Настройка протокола PPP. Отладка соединений WAN. Фильтрация трафикас использованием списков контроля доступа (ACL-списков). Групповаямаска. Настройка списков контроля доступа. Разрешение и запрещениеопределенных типов трафика. Стандартные ACL-списки для IPv4.Расширенные ACL-списки для IPv4.Раздел 7. Защита информацииКриптографические методы защиты информации.

Криптографическиемодели. Примеры применения в криптографии. Аутентификация доступапользователей к информационным ресурсам. Электронная подпись.Реализация. Цифровой сертификат. Методы и алгоритмы шифрования соткрытым и закрытым ключами. Реализация. Виды атак на информацию.5Системы обнаружения атак. Средства защиты от атак на информацию:межсетевые экраны, на уровне протоколов.Раздел 8. Базы данныхЭтапы проектирования базы данных.