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

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

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

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

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

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

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

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

Сравнениемикропрограммной и схемной реализации БУУ. АЛУ – назначение,классификация. Выполнение операций сложения, вычитания над числами сфиксированной точкой с использованием обратного и дополнительногокодирования. Определение переполнения. АЛУ для выполнения операцииумножения на числами с фиксированной точкой.

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

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

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

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

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

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

Открытые и закрытые компоненты класса. Методы-конструкторы иметоды-акцессоры. Перегрузка методов. Инкапсуляция, наследование,полиморфизм в объектно-ориентированном программировании. Защищённыекомпоненты класса. Переопределение методов. Экономия кода программ принаследовании.

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