09.04.02 Информационные системы и технологии (Интеллектуальные технологии обработки цифрового контента)

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

ПоповПроцедура проведения вступительных испытаний вмагистратуруВступительный экзамен в магистратуру проводится с целью определениясоответствия знаний, умений и навыков поступающего в магистратуру по направлению09.04.02 – «Информационные системы и технологии». Вступительные испытанияпроходят в виде тестирования.

Каждый испытуемый проходит тест на компьютере, гдеиспытуемому предъявляются тестовые задания по разным разделам дисциплиннаправления «Информационные системы и технологии», указанных ниже. Сложностьзаданий в выборке у всех испытуемых одинаковая. Таким образом, испытуемые находятсяв равных условиях. Время, отводимое на тест – 90 минут. Итоговый результат выдается вконце сеанса тестирования в виде балла от 0 до 100.Для объективной оценки усвоения материала тестовые задания отражают содержаниеосновных разделов дисциплин направления бакалавриата – «Информационные системы итехнологии».

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

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

Нормальные формы. Полные системы булевыхфункций. Минимизация булевых функций. Логические схемы. Синтез логических схем.Оценки сложности логических схем. Конечные автоматы и их задание. Методыминимизации. Грамматики.Раздел 5. Методы комбинаторики.Основные принципы комбинаторики. Перестановки и сочетания. Комбинаторныеформулы. Бином Ньютона. Задачи о размещении.

Комбинаторика и вероятность.Раздел 8. Сложность алгоритмовОпределения сложности алгоритма. Алгоритмически неразрешимые проблемы.Машина Тьюринга. Нижние и верхние оценки сложности. Задача о симметрии.Оптимальные алгоритмы. Алгоритмы сортировки. Алгоритм решения задач линейногопрограммированияЛитератураосновная1. Рыбин С.В. Поздняков С.Н. Дискретная математика, учебник для студентов высш.учеб.

заведений, обучающихся по направлениям подготовки "Информатика ивычислительная техника", "Информационные системы", "Информационнаябезопасность"; М.,Издательский центр "Академия", 2008; 448с.2. Новиков Ф.А. Дискретная математика для программистов, учебное пособие длявузов; СПб., Питер, 2008; 383с.3.

Андерсон Д.А. Дискретная математика и комбинаторика, Пер. с англ.; М.,Издательский дом "Вильямс", 2004; 957 с.дополнительная4. Горбатов В.А. Фундаментальные основы дискретной математики. – М. Наука.Физматгиз, 20005. Яблонский С.В. Введение в дискретную математику М., Наука, 19866. Юдин Д.Б., Горяшко А.П., Немировский А.С. Математические методыоптимизации устройств и алгоритмов АСУ., М.

Радио и связь, 19827. Ф. Харари Теория графов, М., Мир, 19738. М.Холл Комбинаторика, М., Мир, 1970МАТЕМАТИЧЕСКАЯ ЛОГИКА И ТЕОРИЯ АЛГОРИТМОВРаздел 1. Алгебра высказываний1.1. Пропозициональные связки, истинностные таблицы. Тавтологии и противоречия.Логическая эквивалентность и логическое следствие.1.2. Дизъюнктивные и конъюнктивные нормальные формы.1.3. Полные системы.

Базис.Раздел 2. Формальные аксиоматические теории2.1. Аксиомы, правила вывода. Формализация понятий «теорема» и «доказательство».2.2. Исчисление высказываний.Раздел 3. Логика предикатов3.1. Понятие терма, предиката. Кванторы.3.2. Логическая общезначимость. Эквивалентность формул логики предикатов.3.3. Нормальные пренексные формы. Связь предикатов с теорией множеств.Раздел 4. Теория алгоритмов4.1. Нормальные алгоритмы Маркова. Принцип нормализации.4.2.

Машина Тьюринга, машина Поста. Тезис Чёрча.Литератураосновная1. Лавров И.А. Математическая логика, учебное пособие; М., Академия, 2006; 240с.2. Данилов А.Н., Дьячков А.М., Норин В.П. и др. Математическая логика и теорияалгоритмов. Задания и методические указания для самостоятельной работы студентов.Руководство по проведению практических занятий. М.: 2004-99 с.дополнительная3. Самохина А.В.

Спец. главы математики. Основы дискретной математики,математической логики, теории алгоритмов: Курс лекций. М.: Изд-во МГУП, 2001.4. Лавров И.А., Максимова Л.Л. Задачи по теории множеств, математической логике итеории алгоритмов. М.: Физматлит, 2001.5. Успенский В.А. Машина Поста. М.: Наука, 1979.6. Новиков П.С. Элементы математической логики. М.: Наука, 1973.7. Мендельсон Э. Введение в математическую логику. М.: Наука, 1971.БАЗЫ И БАНКИ ДАННЫХРаздел 1: Мир баз данных.Эволюция систем баз данных.

Первые СУБДСистемы реляционных баз данныхСистемы клиент/сервер и многоуровневые архитектурыРаздел 2: Модель данных сущность связь.Элементы ER-модели. Множества сущностей.Атрибуты. Связи. Диаграммы сущностей и связей.Экземпляры ER-диаграммы. Множественность бинарных связей. Многосторонние связиСвязи и роли. Связи и атрибутыПреобразование многосторонних связей в бинарныеПодклассы в ERмоделиПринципы проектирования( Достоверность, Отсутствие избыточности, Простота)Принципы проектирования( Выбор подходящих связей, Использование элементовадекватных типов)Моделирование ограниченийКлассификация ограничений.Ключи и ER-моделирование Представление ключей в ER-модели.Ограниченияуникальности.Ограниченияссылочнойцелостности. Ссылочнаяцелостность и ER-диаграммы.

Ограничения других видовСлабые множества сущностей. Примеры использования слабых множеств сущностейТребования к слабым множествам сущностей. Система обозначений слабых множествсущностейРаздел 3: Реляционная модель.Основы реляционной модели. Атрибуты. Схемы.Кортежи. Домены.Формы представления отношений. Экземпляры отношенияПреобразование множеств сущностей к отношениям. Преобразование ER-связей котношениям.Объединение отношений. Преобразование слабых множеств сущностейПреобразование структур подклассов в отношения. Преобразование в стиле сущностьсвязь. Объектно-ориентированный подходЗначения null и объединение отношений. Сравнение стратегийОпределение функциональной зависимости ( Ключи отношений, Суперключи, Выборключей для отношения)Правила использования функциональных зависимостей.

Правиларазделения/объединения.Правила использования функциональных зависимостей. Тривиальные функциональныезависимостиПравила использования функциональных зависимостей. Замыкание множества атрибутов.Обоснование алгоритма вычисления замыканияРаздел 4: Проектирование реляционных схем.Аномалии. Декомпозиция отношений.Нормальная форма Бойса- КоддaДекомпозиция в BCNF.Реконструкция данных из отношений декомпозиции. Третья нормальная формаМногозначные зависимости Независимость атрибутов как причина избыточностиПроектирование реляционных схем. Определение многозначной зависимости.

Правилаиспользования многозначных зависимостей Четвертая нормальная формаРеляционная алгебра .Раздел 5: Обработка запросов СУБД. Программирование для баз данныхЯзык SQLPL/SQL. Ограничения и триггеры. Хранимые процедуры и функцииЛитератураосновная1.2.3.4.5.6.7.Уидом Д., Ульман Д.Д., Гарсиа-Молина Г.Системы баз данных,Полный курс;М.,Издательский дом "Вильямс",2004;1083 с.А.А. Марков, М.Е. Смирнова Разработка WEB-приложений для iPhone/iPod Touch.Часть 1. Работа с данными. Учебное пособие. М.: МГУП, 2009 -105с.Базы и банки данных.

Лабораторные работы и методические указания по ихвыполнению. М.:МГУП, 2007-78с.А.А. Марков Практическое введение в базы данных. Ч.1 Проектирование учебной базыданных. М.: МГУП, 2004 -26с.А.А. Марков Практическое введение в базы данных.

Ч.2 MySQL: Создание учебнойбазы данных и управление пользователями. М.: МГУП, 2004 -32с.Конноли, Бегг. Базы данных. Проектирование, реализация и сопровождение. Теория ипрактика. 3-е изд. Пер. с англ.- М.: Издательский дом Вильямс. 2003-1439 с.Дюбуа П. MySQL, Полное и исчерпывающее руководство по применению иадминистрированию баз данных MySQL 4, а также программированиюприложений;М.,Издательский дом "Вильямс",2004;1051 с.,;дополнительная1. Томсон Лаура, Веллинг Люк, Разработка WEB приложений на MySQL и PHP. 2-изд.Испр.

СПб. : ООО «Диасофт», 2003, 672 с.2. MySQL. Reference Manual. MySQL AB. 2003.-869pp Дейт К. Введение в системыбаз данных. –К.: Диалектика, 1998.ТЕХНОЛОГИЯ ПРОГРАММИРОВАНИЯРаздел 1. Технология разработки программного обеспечения.Основные этапы решения задач на ЭВМ. Требования к созданию приложений.Абстракции и спецификации. Способы записи алгоритмов. Критерии качества программы.Оформление документации. Правила оформления программной документации. ГОСТ ЕСПД.Стандарт RUP. Жизненный цикл программы.