Программное обеспечение ЭВМ и информационные технологии (09.04.04 Программная инженерия)

Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования «Московскяй государственный технический университет именя Н.Э. Баумана» (МГТУ им. Н.Э. Баумана) УТВЕЖДАЮ Первый проректор— кпн бг. ПРОГРАММА ВСТУПИТЕЛЬНЫХ ИСПЫТАНИЙ В МАГИСТРАТУРУ по направлению подготовки 09.04.04 П ог аммная Пижоне ия коа и ианыспооанвс ма!срааяспс!п поисотоонм Факультет Информатика и системы управления (ИУ) Полное наименование Еактньтсга (сопри~ионное иаиыеновапне) Кафедра(ьг) Программное обеспечение ЭВМ н информационные технологии ~ИУ7) Пенное намыеповапне каоепры (сокрасоениос напыеиованпе) Москва, 2016 г. 1.

ОБЩИЕ ПОЛОЖЕНИЯ К вступительным испытаниям в магистратуру допускаются лица, имеющие документ государственного образца о высшем образовании любого уровня !диплом бакалавра или специалиста). Липа, предъявивщие диплом магистра, могут быль зачислены только иа договорной основе. Прием осуществляется на конкурсной основе по результатам вступнтельвь!х исп*ттаний. Программа вступительных испытаний в магистратуру по направлению подготовки: 09.04.04 П ог аммнаи внжене ня и! а н наййепоааам на$атав$а$!нн ноз$ отава!! составлена на основании Федерального государственного образовательного стандарта высшего образования подготовки бакалавра по направлению: 09.03е04 Про! раммнаи инженерия коа а наименование направлении по!мотовка и охватывает базовые дисциплины подготовки оакалавров по названному направлению.

Программа содержит описание формы вступительных испытаний, перечень вопросов для вступительных испытаний и спис~~ литературы рекомендт смой для подготовки, 2. ЦЕЛЬ ВСТУПИТЕЛЬНЫХ ИСПЫТАНИЙ Вступительные испытания призваны определить степень готовности поступаюп!его к освоению основной образовательной программы магистратуры по направлению: 09.04.044Програяеатиая инженерии йоа и йаййеиойаййе пай!!ай,квай ноанноаки 3. ФОРМА ПРОВЕДЕНИЯ ВСТУПИТЕЛЬНЫХ ИСПЫТАНИЙ Вступительные испытания проводятся в письменной форме в соответствии с установленным приемной комиссией МГТУ расписанием. Поступающему предлагается ответить письменно на !О вопросов и задач билета, расположенных в порядке возрастания трудности и охватывающих содержание разделов и тем программы соответствующих вступительных испытаний.

На ответы по вопросам н задачам билета отводится 210 минут. Результаты испытаний оцениваются по стобалльной !пкале. Результата! испытаний оглап!лютея не позднее чем через три рабочих дня. 4. ПРОГРАММА ВСТУПИТЕЛЬНЫХ ИСПЫТАНИЙ Письменное испытание проводится по программе, базирующейся на основной образовательной программе бакалавриата по на!!равнению 09.03,04 Программнан пнжене ни нов н наименование нан!$а$йтеннв потнотонки Перечень рвзделов н тем дисциплин, включенных в нцсьменное нспьггвипе ДИСЦИПЛИНА 1. Базы банных.

Общие представления о реляционной модели и реляционных объектах данных. Понятие целостности реляционных данных. Реляционная алгебра и реляционное исчисление (вариант кортежей). Условные выражения и предикаты языка ЗСИ.. Функциональные зависимости. Правила вывода Армстронга и Дарвена, Замыкание множества атрибутов, Нормализация отношений, Первая, вторая и третья нормальные формы. Нормальная форма Бойса-Кодда.

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

Перечень вопросов 1. Реляционная модель. Реляционные объекты данных. Целостность реляционных данных. 2. Реляционная алгебра. 3. Реляционное исчисление (вариант кортежей). 4. Условные выражения и предикаты языка ЗСП . 5. Функциональные зависимости. Правила вывода Армстронга и Дарвена.

Замыкание множества атрибутов. 8. Нормализация отношений. Первая, вторая и третья нормальные формы. Нормальная форма Бойса-Кодда. 7. Нормализация отношений. Многозначные зависимости и четвертая нормальная форма. Зависимости соединения и пятая нормальная форма. 8. Управление транзакциями. Типы транзакций. Свойства транзакций, 9. Управление транзакциями. Тупиковые ситуации и способы их обнаружения, Уровни изоляции. Поддержка блокировок в стандарте языка ЗСИ.. 10.

Безопасность данных в базах данных. Поддержка мер обеспечения безопасности в стандарте языка ЗО~; механизм представлений и подсистема полномочий, 11, Декларативная и процедурная поддержка ограничений целостности. Поддержка ограничений целостности в стандарте языка ЗСН . Основная учебная литература. Литература 1.

Дейт К. Дж. Введение в систему баз данных. - М.: «Вильямс», б-издание, 2012. ДИСЦИПЛИНА 2. Типы и структуры данных Понятие стека, дека, очереди. Алгоритмы включения, исключения элементов в этих структурах. Сравнение эффективности конкретных реализаций данных структур. Алгоритмы включения и исключения элемента из двусвязного списка. Рекурсия и рекурсивные типы данных.

Рекурсивные процедуры и функции. Разработка рекурсивных и итеративных алгоритмов. Оценка эффективности алгоритмов. Принципы выбора различных по эффективности алгоритмов для решения конкретных задач. Разреженные матрицы. Понятие абстрактных типов данных. Принципы создание алгоритмов с использованием абстрактных типов данных.

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

Перечень еолросое. 1. Понятие списка, стека, дека, очереди. Основные алгоритмы включения, исключения элементов в этих структурах. Сравнительный анализ эффективности конкретных реализаций данных структур. Алгоритмы включения и исключения элемента из двусвязного списка. 2. Понятие рекурсии. Рекурсивные типы данных. Рекурсивные процедуры и функции. Критерии выбора для разработки рекурсивных или итеративных алгоритмов. 3.

Оценка эффективности алгоритмов. Принципы выбора различных по эффективности алгоритмов для решения конкретных задач. 4. Разреженные матрицы. Методы хранения и расчета разреженных матриц, Использование разреженных матриц, 5. Понятие абстрактных типов данных. Принципы создание алгоритмов с использованием абстрактных типов данных. 6. Деревья.

Виды деревьев. Использование различных видов деревьев для поиска и сортировки. Сравнение различных методов поиска в массивах, деревьях, хэштаблицах 7. Поиск в графах. Алгоритмы поиска в ширину и глубину, построение каркасов графа. Пути в графах. Алгоритмы поиска Эйлерова и Гамильтонова пути. Алгоритмы поиска минимальных путей. Основная учебная литература. 1. Кормен Т., Лейзерсон Ч., Ривест Р., Щтайн К, Алгоритмы: Построение и анализ.

2-е изд. — М.: Издат. дом «Вильямс», 2012. -1296 с. ДИСЦИПЛИНА 3. Системное проераммирование Назначение и функции ОС, Поколения ОС, современные тенденции развития ОС. Типы ОС. Понятие процесса: процесс как единица декомпозиции системы. Параллельные процессы: уровни наблюдения - параллельные и псевдопараллельные процессы. Состояния процесса: диаграмма состояний процесса. Приостановка и возобновление; проблемы приостановки и возобновления. Процессы в ОС ОМХ.

Реализация мультипрограммированияпланирование и диспетчеризация. Дисциплины планирования. Супервизор: системные и пользовательские процессы; уровни привилегий. Структура ядра ОС. Взаимодействие процессов. Монитор: читатели и писатели. Разделяемые ресурсы и монопольный доступ. Взаимная блокировка процессов.

Семафоры: определение, виды семафоров, примеры. Взаимоисключение при помощи семафоров. Тупики. Метод редукции графа: представление состояний системы в виде направленных графов, Алгоритмы обнаружения тупиков: метод прямого обнаружения; алгоритм со счетчиком ожиданий; примеры реализации. Обход тупиков - алгоритм банкира и его аппроксимации.

Обнаружение и восстановление работоспособности системы. Виртуальная память, Страничная организация памяти: таблицы страниц. Стратегии управления виртуальной памятью. Схемы преобразования адресов. Алгоритмы "выталкивания" страниц: выталкивание случайной страницы, Е!ЕО, Ы0, ~Е0, й0й, метод связанных пар - размер страницы. Определение, стратегия рабочего множества.

Анализ страничного распределения. Сегментная организация виртуальной памяти; преобразование адресов; организация таблиц сегментов. Сегментно-страничная организация: преобразование адресов, особенности реализации. Коллективное использование информации и защита информации для страничной, сегментной и сегментно-страничной организации памяти. Перечень еопросое 1. Назначение и функции ОС: ресурсы ВС, управление ресурсами. Поколения ОС, современные тенденции развития ОС. Типы ОС: однопрограммные и мультипрограммные, ОС пакетной обработки и системы с раздепением времени, системы реального времени, сетевые и многопроцессорные ОС.

2. Понятие процесса: процесс как единица декомпозиции системы. Параппепьные процессы: уровни наблюдения - параллельные и псевдопараллельные процессы. Состояния процесса: диаграмма состояний процесса, Оценка эффективности работы ОС. Приостановка и возобновление; проблемы приостановки и возобновления, Процессы в ОС 0МХ. 3. Реализация мультипрограммирования - планирование и диспетчеризация. Дисциплины планирования. Супервизор: системные и пользовательские процессы; уровни привилегий. 4. Структура ядра ОС: монолитное ядра - определение, системные вызовы, прерывания; микроядро - определение, передача сообщений, синхронизация; диаграмма состояний процесса - три состояния блокировки при передаче сообщения, 5.

Взаимодействие процессов: проблемы взаимодействия асинхронных процессов - синхронизация, взаимоисключение, взаимоблокировка. Монитор: читатели и писатели. 6. Разделяемые ресурсы и монопольный доступ. Обеспечение монопольного доступа к разделяемым ресурсам - взаимоисключение: алгоритм Деккерера, бесконечное откладывание и проблема активного ожидания.

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