Федеральное агентство связи

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

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

«МОСКОВСКИЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ СВЯЗИ И ИНФОРМАТИКИ»

Утверждена

советом факультета ИТ

протокол № 10 от 17.06.2014г.

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

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

Магистерская программа «Программные информационные системы»

Москва 2014

1 ЦЕЛЬ И ЗАДАЧИ ВСТУПИТЕЛЬНЫХ ИСПЫТАНИЙ

Вступительные испытания предназначены для определения практической и теоретической подготовленности бакалавра и проводятся с целью определения соответствия знаний, умений и навыков студентов требованиям обучения в магистратуре по направлению 230100 «Информатика и вычислительная техника» (магистерская программа «Программные информационные системы»).

2 СОДЕРЖАНИЕ ВСТУПИТЕЛЬНЫХ ИСПЫТАНИЙ

Вступительные испытания в магистратуру по направлению подготовки «Информатика и вычислительная техника» (магистерская программа «Программные информационные системы») проводятся по следующим разделам:

1) оценка соответствия профиля и уровня полученного образования;

2) участие в студенческой научно-исследовательской работе;

3) характеристика ВКР бакалавра (специалиста);

4) вступительный экзамен (письменный).

В основу программы вступительного экзамена положены квалификационные требования в области основ разработки автоматизированных систем и информационного, программного, технического, математического обеспечений этих систем, предъявляемые к бакалаврам по направлению подготовки 230100 «Информатика и вычислительная техника».

Целью вступительного экзамена в магистратуру по направлению ИНФОРМАТИКА И ВЫЧИСЛИТЕЛЬНАЯ ТЕХНИКА является проведение конкурсного отбора среди лиц, желающих освоить программу специализированной подготовки магистра по программе «Программные информационные системы».

Вступительный экзамен носит междисциплинарный характер и включает материал, предусмотренный ГОС ВПО по направлению подготовки 230100.62 Информатика и вычислительная техника.

На вступительном экзамене претенденту предлагается задание, состоящее из двух вопросов, отражающих основные квалификационные требования, предъявляемые к бакалавру (специалисту) для решения профессиональных задач.

Вступительный экзамен носит междисциплинарный характер и включает материал, предусмотренный ГОС ВПО по направлению подготовки 230100 Информатика и вычислительная техника.

На вступительном экзамене претенденту предлагается задание, состоящее из двух вопросов, отражающих основные квалификационные требования, предъявляемые к бакалавру для решения профессиональных задач.

СОДЕРЖАНИЕ ПРОГРАММЫ ВСТУПИТЕЛЬНОГО ЭКЗАМЕНА

Математическое моделирование.

Постановка задачи в предметной области; формализация; параметризация задачи;

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

потоки событий; системы массового обслуживания.

Применение имитационного моделирования при анализе инфокоммуникационных систем.

Дискретная математика.

Основные понятия теории графов; маршруты; циклы; связность; сети.

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

Матричные игры; модели непрерывных игр; модели алгебры нечетких множеств;

математические модели теории надежности; разрешимые и неразрешимые проблемы;

схемы алгоритмов; схемы потоков данных.

Элементы теории информации; понятие информации, ее основные свойства и особенности; понятие информации и энтропии; оптимальное кодирование информации.

Технологии программирования.

Основы теории формальных языков и грамматик; распознаватели и преобразователи: конечные автоматы и преобразователи, автоматы и преобразователи с магазинной памятью; связь между грамматиками и автоматами; многослойные распознающие машины.

Методы обеспечения надежности программных средств; критерии эффективности программных средств; спецификации программных средств с помощью логических и алгебраических моделей; принципы объектно-ориентированного программирования.

Современные языки программирования; нотации Бэкуса-Наура; спецификации языка программирования.

Абстрактные типы данных; спецификация, представление, реализация; линейные структуры данных: стек, очередь, дек; нелинейные структуры данных: иерархические списки, деревья и леса, бинарные деревья; обходы деревьев; задачи поиска и кодирования (сжатия) данных, кодовые деревья.

Операционные системы Базовые функции операционной системы (ОС) современных ЭВМ;

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

Базы данных.

Назначение и основные компоненты системы баз данных; обзор современных систем управления базами данных (СУБД); классы СУБД и возможности использования профессиональных СУБД; уровни представления баз данных; понятия схемы и подсхемы;

модели данных; иерархическая, сетевая и реляционная модели данных; архитектура базы данных, физическая и логическая независимость (трехуровневая модель ANSI); схема отношения; язык манипулирования данными для реляционной модели; реляционная алгебра и язык SQL.

Интеллектуальные системы.

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

Экзаменационные вопросы:

Мультипрограммирование. Критерии эффективности вычислительных систем.

Если программа А выполняется в монопольном режиме за 5 минут, а программа В – за 20 минут, то при последовательном выполнении они требуют 25 минут. Т – время выполнения обеих этих задач в режиме мультипрограммирования. Какое из неравенств, приведенных ниже справедливо? Объясните свой ответ.

2. Планирование и диспетчеризация потоков. Алгоритмы планирования, основанные на квантовании. Приоритетное планирование.

Могут ли быть применены сразу все перечисленные характеристики к одному алгоритму планирования потоков?

а) вытесняющий, с абсолютными динамическими приоритетами;

б) невытесняющий, с абсолютными фиксированными приоритетами;

в) невытесняющий, с относительными динамическими приоритетами;

г) вытесняющий, с абсолютными фиксированными приоритетами, основанный на квантовании с динамически изменяющейся длиной кванта;

д) невытесняющий, основанный на квантовании с фиксированной длиной кванта.

Для тех вариантов, которые вы считаете возможными, опишите более подробно алгоритм планирования.

3. Сегментная организация памяти. Структура виртуального адресного пространства.

Преобразование виртуальных адресов в физические.

В вычислительной системе с сегментной организацией памяти из 32-х бит адреса старшие 14 его бит отводятся для номера сегмента. Для некоторого процесса таблица сегментов в этой системе имеет вид:

Каким физическим адресам соответствуют адреса 0х456А8h, 0x170201h?

4. Страничная организация памяти. Структура виртуального адресного пространства.

Преобразование виртуальных адресов в физические.

Пусть в некоторой программе, работающей со страничной организацией памяти, произошло обращение по виртуальному адресу 0523568. Преобразуйте этот адрес в физический, учитывая, что размер страницы равен 16 Кбайт, и что таблица страниц данного процесса содержит следующий фрагмент:

Номер виртуальной страницы Номер физической страницы 5. Гонки (взаимные состязания). Суть проблемы. Способы реализации взаимных исключений. Изложите алгоритм «читатели-писатели» при использовании семафоров Дейкстры.

6. Системные средства синхронизации процессов и потоков: критические секции, системные семафоры, мьютексы, события, сигналы. Области применения. Приведите пример, демонстрирующий различие этих объектов синхронизации.

7. Организация контроля доступа к ресурсам. Опишите избирательный и мандатный тип управления доступом. В каком из них пользователю предоставляется большая свобода действий? Пример реализации контроля доступа.

8. Системные средства обмена данными между процессами: каналы, файловые отображения, почтовые ящики, сокеты.

9. Реляционная модель данных. Основные определения (N-арное отношение, кортеж, атрибут, домен, степень/ранг, схема отношения, -сравнимые атрибуты.

эквивалентные схемы. Основное и подчиненное отношения. PRIMARY KEY, FOREIGN KEY) 10. Проектирование реляционных БД на основе принципов нормализации: этапы жизненного цикла БД. Этапы проектирования БД.

11. Архитектура базы данных. Физическая и логическая независимость (трехуровневая модель ANSI). Описать процесс прохождения пользовательского запроса 12. Инфологическое моделирование. ER - модель (базовые понятия сущность, связь, типы связей: 1:1, 1:N, N:N, обязательная/необязательная).

13. Классическая и микроядерная архитектура ОС. Достоинства и недостатки. Примеры реализаций этих подходов к построению ОС.

14. Гонки (взаимные состязания). Суть проблемы. Способы реализации взаимных исключений. Изложите алгоритм «читатели-писатели» при использовании семафоров Дейкстры.

15. Реляционная алгебра. Теоретико-множественные операции реляционной алгебры.

Основные операции (объединение, пересечение, разность, конкатенация кортежей, произведение) 16. Реляционная алгебра. Теоретико-множественные операции реляционной алгебры.

Специальные операции (выборка, проекция, соединение, деление).

Oсновная литература:

1. В.Г.Олифер, Н.А.Олифер. Сетевые операционные системы. – СПб.: Питер, 2. Э.Таненбаум. Современные операционные системы. 3-изд. – СПб.: Питер, 3. М. Руссинович, Д. Соломон. Внутреннее устройство Microsoft Windows. - СПб.:

Питер, 2013.

4. Карпова Т.С. Базы данных: модели, обработка, реализация. – СПб.: Питер, 2001. – 5. Фаронов В.В. Программирование баз данных в Delphi 7: Учебный курс. – СПб.:

6. Кренке Д. Теория и практика построения баз данных: [пер.с англ] / Д. Кренке. - 9 е изд. - СПб.: Питер, 2005. - 858 с.

7. Хомоненко А.Д., Цыганков В.М., Мальцев М.Г. Базы данных: Учебник для высших учебных заведений / Под ред. проф. А.Д. Хомоненко. - СПб.: КОРОНА принт, Дополнительная литература:

1. Э.Таненбаум, А.Вудхалл. Операционные системы. Разработка и реализация. Питер, 2. С.В.Назаров, А.И.Широков. Современные операционные системы. - М.: ИнтернетУниверситет Информационных технологий; БИНОМ. Лаборатория знаний, 3. Джеффри Рихтер, Кристоф Назар. Windows via C/C++. – СПб.: Питер, «Русская редакция», 4. Джеффри Рихтер. Windows для профессионалов. Создание эффективных Win32пpилoжeний с учетом специфики 64-разрядной версии Windows. - СПб.: Питер, «Русская редакция», 5. Х.М.Дейтел, П.Дж.Дейтел, Д.Р. Чофес. Операционные системы.- М.: Изд. Бином, 6. Д.В.Иртегов. Введение в операционные системы. СПб.: БВХ-Петербург, 7. С.В.Назаров. Операционные среды, системы и оболочки. Основы структурной и функциональной организации: Учебное пособие. – М.: КУДИЦ-ПРЕСС, 8. Ульман Дж., Уидом Дж. Введение в системы баз данных. - М.: Лори, 2000. - 374с.

Руководитель магистерской программой