Нижегородский филиал
Федерального государственного автономного образовательного учреждения высшего образования
"Национальный исследовательский университет
"Высшая школа экономики"
Факультет информатики, математики и компьютерных наук
Утверждена
Ученым советом НИУ ВШЭ – Нижний Новгород
Протокол № __ от ___________ 201__г.
Программа
государственного итогового междисциплинарного экзамена
по направлению 01.03.02 «Прикладная математика и информатика»
подготовки бакалавра
Нижний Новгород, 2016
Требования к выпускнику НИУ ВШЭ по направлению подготовки 01.03.02 «Прикладная математика и информатика», уровень подготовки бакалавр
Требования к выпускнику НИУ ВШЭ предъявляются в соответствии с
ОБРАЗОВАТЕЛЬНЫМ СТАНДАРТОМ ФЕДЕРАЛЬНОГО ГОСУДАРСТВЕННОГО АВТОНОМНОГО ОБРАЗОВАТЕЛЬНОГО УЧРЕЖДЕНИЯ ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ «НАЦИОНАЛЬНОГО ИССЛЕДОВАТЕЛЬСКОГО УНИВЕРСИТЕТА «ВЫСШАЯ ШКОЛА ЭКОНОМИКИ» по направлению подготовки
01.03.02 «Прикладная математика и информатика» подготовки бакалавра.
Настоящая программа предназначена для бакалавров четвертого курса направления подготовки 01.03.02 «Прикладная математика и информатика». Программа раскрывает содержание тем экзамена и содержит список рекомендуемой литературы.
В результате освоения материала по предложенным темам у студента должны быть сформированы следующие профессиональные компетенции:
способность демонстрации общенаучных базовых знаний естественных наук, математики и информатики, понимание основных фактов, концепций, принципов теорий, связанных с прикладной математикой и информатикой;
способность понимать и применять в исследовательской и прикладной деятельности современный математический аппарат;
способность собирать, обрабатывать и интерпретировать данные современных научных исследований, необходимые для формирования выводов по соответствующим научным, профессиональным, социальным и этическим проблемам;
способность решать задачи производственной и технологической деятельности на профессиональном уровне, включая разработку математических моделей, алгоритмических и программных решений;
Форма проведения государственного итогового междисциплинарного экзамена
Экзамен проводится в письменной форме. Студентам дается два задания. Одно – по блоку математических дисциплин, второе – по блоку информационных технологий.
-
Содержание тем, включенных в государственный итоговый междисциплинарный экзамен. Рекомендуемая литература по темам
1. Линейная алгебра
Векторы, матрицы и действия с ними. Линейная зависимость системы векторов. Базис линейного пространства. Скалярное произведение.
Определитель квадратной матрицы. Вычисление определителей. Разложение определителя по строке и по столбцу.
Транспонированная матрица. Обратная матрица. Ранг матрицы. Специальные виды матрицы.
Системы линейных уравнений. Метод Крамера. Метод Гаусса. Фундаментальная система решений.
Собственные числа и собственные векторы матрицы.
Квадратичные формы. Матрица квадратичной формы. Условие положительной (отрицательной) определенности квадратичной формы.
Литература
Ильин В.А., Позняк Э.Г. Линейная алгебра. – М.: ФИЗМАТЛИТ, 2007, 280 с.
Александров П.С. Курс аналитической геометрии и линейной алгебры. – СПб.: Изд-во ″Лань″, 2009, 512 с.
Мальцев А.И. Основы линейной алгебры. – СПб.: Изд-во ″Лань″, 2009, 480 с.
Ильин В.А., Позняк Э.Г. Аналитическая геометрия. – М.: Физматлит, 2009, 234 с.
2. Математический анализ
Функции одной переменной. Производные. Исследование и построение графика функции.
Функции многих переменных. Частные производные. Полный дифференциал. Градиент функции. Производная по направлению. Матрица Гессе. Безусловный экстремум функции многих переменных. Необходимые и достаточные условия экстремума функции многих переменных.
Выпуклые функции и множества. Примеры экономических приложений. Оптимизация при наличии ограничений. Функция Лагранжа и ее стационарные точки. Максимизация полезности и бюджетное ограничение. Окаймленный Гессиан. Условия второго порядка.
Литература:
Берман Г.Н. Сборник задач по курсу математического анализа: решение типичных и трудных задач. Санкт-Петербург: Лань, 2007. – 608 с.
Ильин В.А., Садовничий В.А., Сендов Бл.Х. Математический анализ. Ч.1. Москва: Проспект. Изд-во МГУ, 2006. - 672 c.
Ильин В.А., Садовничий В.А., Сендов Бл.Х. Математический анализ. Ч.2. Москва: Проспект. Изд-во МГУ, 2006. - 368 c.
3. Дифференциальные уравнения
Уравнения в полных дифференциалах. Метод замены переменных. Интегрирующий множитель. Уравнение Бернулли.
Линейные дифференциальные уравнения 1-го порядка. Метод вариации постоянной.
Однородные линейные дифференциальные уравнения с постоянными коэффициентами. Характеристическое уравнение. Устойчивость решения.
Неоднородные линейные дифференциальные уравнения с постоянными коэффициентами и с правой частью в виде квазимногочлена.
Литература:
Тихонов А.Н., Васильева А.Б. Дифференциальные уравнения. М.: ФИЗМАТЛИТ, 2005. 256 с.
Петровский И.Г. Лекции по теории обыкновенных дифференциальных уравнений. М.: ФИЗМАТЛИТ, 2009. 208 с.
4. Теория вероятностей
Основные понятия теории вероятностей. Случайные события и случайные величины. Функция плотности распределения. Совместное распределение нескольких случайных величин. Условные распределения.
Характеристики распределений случайных величин (математическое ожидание, дисперсия, ковариация). Свойства математического ожидания и дисперсии. Условное математическое ожидание.
Нормальное распределение и связанные с ним хи-квадрат распределение, распределения Стьюдента и Фишера, и их основные свойства. Таблицы квантилей распределений и их использование.
5. Математическая статистика
Генеральная совокупность и выборка. Выборочное распределение и выборочное характеристики (среднее, дисперсия, ковариация, коэффициент корреляции). Корреляционная связь.
Статистическое оценивание. Точечные оценки. Линейность, несмещенность, эффективность и состоятельность оценок. Интервальные оценки, доверительный интервал.
Статистические выводы и проверка статистических гипотез. Ошибки 1-го и 2-го рода. Уровень доверия и проверка значимости.
Линейная регрессионная модель для случая одной объясняющей переменной. Теоретическая и выборочная регрессии. Природа случайной составляющей. Линейность по переменным и параметрам. Степень соответствия линии регрессии имеющимся данным. Коэффициент детерминации и его свойства.
Оценивание параметров. Метод наименьших квадратов (МНК). Свойства оценок параметров, полученных по МНК.
Литература:
Гмурман В.Е. Теория вероятностей и математическая статистика. - М.: Высшее образование, 2012. – 479 с.
Гмурман В.Е. Руководство к решению задач по теории вероятностей и математической статистики. - М.: Высшее образование, 2011.– 404 с.
Черемных Ю.Н. и др, Количественные методы в экономических исследованиях, Москва, ЮНИТИ, 2004.
Сигел Э.Ф. Практическая бизнес статистика, Москва, ЮНИТИ, 2005.
6. Исследование операций
Канонические формы задачи линейного программирования. Базисные и небазисные переменные. Допустимые базисные точки. Симплекс-алгоритм. Экспоненциальная сложность алгоритма. Двойственность.
Транспортная задача. Алгоритмы северо-западного угла и Фогеля.
Метод потенциалов. Задача о назначениях.
Целочисленная оптимизация. Метод ветвей и границ. Задача коммивояжера.
Алгоритм нахождения минимального остова. Алгоритм нахождения кратчайшего пути. Алгоритм нахождения максимального потока.
Постановка задачи динамического программирования. Принцип оптимальности Беллмана. Выбор оптимальной стратегии замены оборудования как задача динамического программирования. Задача оптимального распределения инвестиций.
Литература:
Таха Х.А. Введение в исследование операций, Изд.дом <�Вильямс>, 7-е издание 2005.
Андерсон Дж. Дискретная математика и комбинаторика. М. Издательский дом "Вильямс". 2004. ISBN 5-8459-0498-6.
Хаггарти Р. Дискретная математика для программистов. М. Техносфера. 2003.ISBN 5-94836-016-4.
Логвинова К.В. Учебное пособие по дисциплине <�Теоретическая информатика>. НФ ГУ-ВШЭ. 2007.
7. Дискретная математика
Понятие множества, основные операции над множествами. Свойства операций над множествами. Диаграммы Венна. Доказательство соотношений.
Бинарные отношения. Рефлексивность, антирефлексивность, симметричность, антисимметричность, транзитивность.
Булева алгебра. Основные логические операции. Функции. Полином Жегалкина. СДНФ, СКНФ. Минимизация булевых функций (метод Квайна-Маккласки). Полнота и замкнутость системы булевых функций.
Комбинаторика. Перестановки, сочетания, с повторением и без. Принцип включения-исключения.
Графы, матрица расстояний и матрица инцидентности. Степени вершин. Эйлеров и гамильтонов циклы. Деревья и их свойства. Задача о раскраске графа. Хроматическое число.
Двоичные деревья поиска и алгоритмы, красно-черные деревья, AVL-деревья.
Литература:
Таха Х.А. Введение в исследование операций, Изд.дом <�Вильямс>, 7-е издание 2005.
Андерсон Дж. Дискретная математика и комбинаторика. М. Издательский дом "Вильямс". 2004. ISBN 5-8459-0498-6.
Хаггарти Р. Дискретная математика для программистов. М. Техносфера. 2003.ISBN 5-94836-016-4.
Логвинова К.В. Учебное пособие по дисциплине <�Теоретическая информатика>. НФ ГУ-ВШЭ. 2007.
8. Основы информатики и программирования
Место и роль вычислительной техники в информатике.
Классификация средств вычислительной техники.
Вычислительные машины, системы и сети.
Обобщенная структурная схема ЭВМ: центральная и периферийная часть.
Особенности ЭВМ архитектуры фон-Неймана.
Понятие формата команд и адресации команд и операндов.
Классификация периферийных устройств.
Основные характеристики центральных и периферийных устройств.
Вычислительные сети.
Принципы построения локальных вычислительных сетей.
Топология ЛВС.
Глобальные вычислительные сети.
Программное обеспечение ЭВМ.
Классификация программного обеспечения.
Системное программное обеспечение.
Прикладное программное обеспечение.
Назначение, состав и функции операционной системы.
Понятие компьютерных ресурсов.
Способы распределения ресурсов.
Однопрограммный и мультипрограммный, однопользовательский и многопользовательский режимы работы.
Концепция системы виртуальных машин.
Интерфейсы операционных систем.
Операционные оболочки и среды.
Жизненный цикл программы.
Постановка задачи и спецификация программы.
Проектирование и реализация.
Тестирование.
Инсталляция и сопровождение.
Понятие системы программирования.
Системы программирования транслирующего и интерпретирующего типов. Интегрированные среды программирования.
Концепция типов данных.
Стандартные простые типы данных: структуры хранения и операции.
Понятие алгоритма. Свойства алгоритмов.
Оценка сложности алгоритмов. Классификация алгоритмов по сложности.
Способы записи алгоритмов.
Классы сложности задач: P, NP.
Организация данных в виде массива, записи, связанного списка.
Алгоритмы на массивах: обмен, группировка, поиск максимального, минимального элементов.
Методы сортировки: простыми вставками, выбором, пузырьком.
Алгоритм быстрой сортировки.
Понятие АТД (абстрактный тип данных).
Понятие динамических структур данных.
Деревья: основная терминология, классификация.
Последовательный файл.
Структуры управления: следование, ветвление, цикл.
Разновидности циклов.
Переключатель.
Вложенность управляющих структур.
Рекурсия и её применение.
Энтропия и основы алгоритмов сжатия информации.
Методология процедурно-ориентированного программирования.
Понятие процедуры и модуля.
Процедурная декомпозиция.
Способы обмена данными между процедурами.
Структурное программирование.
Межмодульная связь и внутримодульное сцепление.
Достоинства и недостатки процедурно-ориентированной методологии программирования, области применения.
Методология объектно-ориентированного программирования.
Понятие класса и объекта.
Состояние и поведение объекта.
Инкапсуляция.
Наследование.
Полиморфизм.
Перегрузка операций.
Управление по событиям.
Достоинства и недостатки объектно-ориентированной методологии программирования, области применения.
Литература
Балдин, К.В. Математическое программирование [Электронный ресурс]: учебник / К. В. Балдин, Н. А. Брызгалов, А. В. Рукосуев; под общ. ред. д.э.н., проф. К. В. Балдина; ЭБС Знаниум. - 2-е изд. - М.: Издательско-торговая корпорация «Дашков и К°», 2013. - 220 с. - ISBN 978-5-394-01457-4. - Режим доступа: http://znanium.com/bookread.php?book=415097. - Загл. с экрана. Гриф МО РФ 2003. – 848 с.
Голицына О.Л. Языки программирования [Электронный ресурс]: учебное пособие / О.Л.Голицына, Т.Л.Партыка, И.И.Попов; ЭБС Знаниум. - 2-e изд., перераб. и доп. - М.: Форум, 2010. - 400 с.: ил. - (Профессиональное образование). - ISBN 978-5-91134-442-9. - Режим доступа: http://znanium.com/bookread.php?book=226043. - Загл. с экрана.
Шилдт Г. Полный справочник по Си.– СПб.: Вильямс, 2007.
Страуструп, Б. Язык программирования С++. Специальное издание / Б. Страуструп. – М.: Бином-Пресс, 2006. – 1104 с.
изд. – М.: Издательский дом «Вильямс», 2006. – 304 с.
Керниган, Б. Язык программирования С / Б. Керниган, Д. Ритчи. – 2-е Давыдов, В.Г. Программирование и основы алгоритмизации: учебное пособие / В.Г. Давыдов. – М.: Высшая школа, 2012. – 447 с.
Александреску, А. Современное проектирование на С++ / Андрей Александреску. – М.: Издательский дом «Вильямс», 2015. – 336 с.
Сатер, Г. Новые сложные задачи на С++ / Герб Сатер. – М.: Издательский дом «Вильямс», 2005. – 272 с.
4.Образцы заданий. Блок информационных технологий
Вопрос 1
Организация данных в виде массива, записи, связанного списка.
Принципы построения локальных вычислительных сетей.
Вопрос 2
Понятие класса и объекта.
Рекурсия и её применение.
Образцы заданий. Блок математических дисциплин
Ответы должны быть обоснованы логическими рассуждениями.
1. Рассматриваемые множества являются подмножествами универсального множества M={a, b, c, d, e, f, g, h, k, l}. Для заданных множеств А={c, d, e, f, g} и В={e, f, g, k, l} описать все множества Х, такие что верно равенство A (B U X)=X
2. Задано отношение R на множестве U. Показать, что R является отношением порядка. Найти все минимальные и максимальные элементы и построить диаграмму Хассе отношения R.
U = {2, 3, 4, 5, 6, 8, 9, 10, 12, 18, 20},
aRb b=a·k, где k некоторое целое число (b делится на a без остатка)
3. Неориентированный граф задан матрицей смежности.
- найти степени вершин графа и найти диаметр графа.
- выяснить, существует ли для данного графа путь, проходящий ровно один раз через все вершины графа (Гамильтонов путь). Найти этот путь (если он существует).
- вычислить хроматическое число графа
- найти все максимальные клики графа
0 0 1 1 1 1
0 0 1 0 0 1
1 1 0 1 1 1
1 0 1 0 0 1
1 0 1 0 0 0
1 1 1 0 0
4. Выразить с помощью основных логических операций (отрицание, конъюнкция, дизъюнкция) булеву функцию, заданною таблицей истинности. Постарайтесь найти наиболее короткое выражение булевой функции.
-
X1
|
X2
|
X3
|
F(X1 ,X2, X3)
|
0
|
0
|
0
|
1
|
0
|
0
|
1
|
0
|
0
|
1
|
1
|
0
|
0
|
1
|
0
|
1
|
1
|
0
|
0
|
0
|
1
|
0
|
1
|
0
|
1
|
1
|
1
|
0
|
1
|
1
|
0
|
1
|
5. Сколько существует восьмизначных натуральных чисел, в десятичной записи которых ровно 4 раза встречается цифра 4?
6. Дана задача линейного программирования 3x1+2x2+3x3 -> max
x1+x2+x3 ≤ 2, 2x1+x2+3x3 ≤3, x1≥0, x2≥0
Сформулировать двойственную задачу. Решить двойственную задачу графически. Найти решение исходной задачи с помощью принципа дополняющей нежесткости.
7. Сформулируйте задачу о минимальном остовном дереве.
- Опишите в общем виде алгоритм Прима (Prim) для решения этой задачи.
- Примените алгоритм (опишите все шаги алгоритма) к поиску остовного дерева следующей сети (указаны ребра и веса)
(o,a) 3; (o,b) 4; (o,c) 2; (a,b) 1; (b,c) 3; (a,d) 5, (b,d) 2; (b,e) 5; (c,e) 1; (e,d) 4
5. Критерии оценивания (по десятибалльной системе оценивания) результатов итогового междисциплинарного экзамена
При проведении государственного итогового междисциплинарного экзамена по направлению 010400.62 «Прикладная математика и информатика» (подготовка бакалавра) выпускник должен продемонстрировать умение:
логически излагать материал;
аргументировано отстаивать свое мнение;
письменно оформлять результаты своих умозаключений.
Выпускник должен:
иметь системное представление о структурах и тенденциях развития прикладной математики и информатики;
понимать многообразие и взаимосвязь различны процессов в современном мире;
обладать всеми навыками, знаниями и умениями, необходимыми в профессиональной деятельности.
Выпускник должен понимать сущность и социальную значимость своей
профессии, необходимость регулярно повышать свою квалификацию как с помощью дальнейшего обучения, так и самостоятельно овладения новыми знаниями.
Наряду с общим представлением о предметной области, экзаменуемый должен иметь представление о проблемах, возникающих в различных областях профессиональной деятельности и о возможных путях их преодоления.
При проведении государственного итогового междисциплинарного экзамена по направлению 010400.62 «Прикладная математика и информатика» (подготовка бакалавра) в письменной форме устанавливаются следующие критерии оценки знаний выпускников:
Оценка «отлично» (8,9,10)- глубокие исчерпывающие знания всего программного материала, понимание сущности и взаимосвязи рассматриваемых процессов и явлений, твердое знание положений смежных дисциплин: логически последовательные, содержательные, полные, правильные и конкретные ответы на все вопросы экзаменационного билета и дополнительные вопросы членов экзаменационной комиссии при грамотном чтении и чётком изображении схем и графиков; использование в необходимой мере в ответах на вопросы материалов всей рекомендованной литературы.
Оценка «хорошо» (6,7) - твердые и достаточно полные знания всего программного материала, правильное понимание сущности и взаимосвязи рассматриваемых процессов и явлений; последовательные, правильные, конкретные ответы на поставленные вопросы при свободном устранении замечаний по отдельным вопросам; грамотное чтение и четкое изображение схем и графиков.
Оценка «удовлетворительно» (4,5)- твердое знание и понимание основных вопросов программы; правильные и конкретные, без грубых ошибок ответы на поставленные вопросы при устранении неточностей и несущественных ошибок в освещении отдельных положений при наводящих вопросах экзаменатора; наличие ошибок в чтении и изображении схем и графиков; при ответах на вопросы основная рекомендованная литература использована недостаточно.
Оценка «неудовлетворительно» (0,1,2,3) - неправильный ответ хотя бы на один из основных вопросов, грубые ошибки в ответе, непонимание сущности излагаемых вопросов; неуверенные и неточные ответы на дополнительные вопросы.
При проведении государственного междисциплинарного экзамена в письменной форме критерии оценки знаний выпускников отражаются в методике получения результирующей балльной оценки.
Результирующая оценка по государственному итоговому междисциплинарному экзамену рассчитывается следующим образом:
Орезультат = 0,5* Оматемат.блок +0,5*Оинформац.блок
Оматемат.блок - оценка по 10-бальной школе за блок математических дисциплин
Оинформац.блок - оценка по 10-бальной школе за блок информационных технологий
Способ округления итоговой оценки - арифметический.
Полученные после округления этих величин до целого значения и выставляются как результирующие оценки по 10-балльной шкале.
|
