Министерство образования и науки Российской Федерации

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

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

Тверской государственный университет

УТВЕРЖДАЮ

Декан факультета

А.В.Язенин

20 г.

ПРОГРАММА

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

ПО НАПРАВЛЕНИЮ

010400.68 Прикладная математика и информатика ООП Системное программирование Квалификация (степень): магистр Форма обучения: очная Обсуждено на заседании Рассмотрено и рекомендовано на кафедры информатики заседании Ученого совета факультета ПМиК протокол № от 20 г.

протокол № от 20 г. Зав.каф.

Тверь 1 Пояснительная записка Итоговый междисциплинарный экзамен вводится по решению ученого совета ГОУ ВПО Тверской государственный университет протокол №6 от 24.02.2011. Цель экзамена проверка овладения выпускником магистратуры основных компетенций, требуемых в профессиональной деятельности: знать и уметь применять методы алгебры, математической логики и теории алгоритмов, уметь применять технологии разработки программного обеспечения, знать историю и современный уровень развития математики и информатики.

Экзамен проводится в устной форме. Каждый билет содержит по одному вопросу по каждой из дисциплин, вынесенных на экзамен, охватывая, таким образом, компетенции, все компетенции, для проверки которых проводится экзамен. Экзаменуемому предоставляется 2 часа для подготовки, после чего он отвечает комиссии. По результату ответа комиссия выставляет оценку.

Экзаменуемый должен продемонстрировать достаточный уровень овладения наиболее существенными компетенциями.

2 Компетенции Итоговый междисциплинарный экзамен нацелен на проверку в первую очередь следующих компетенций:

ОК-2 Иметь представление о современном состоянии и проблемах прикладной математики и информатики, истории и методологии их развития ОК-3 Способность использовать углубленные теоретические и практические знания в области прикладной математики и информатики ВК-1 Способность осуществлять научные исследования в области теоретической информатики, умение пользоваться методами математической логики и теории алгоритмов ВК-4 Умение применять формальные модели языков и вычислительных устройств для анализа алгоритмов и программ 3 Вопросы к госэкзамену и литература для подготовки 3.1 Интеллектуальный анализ данных 1) Ассоциативные правила и их оценка.

2) Построение частых наборов с помощью алгоритма Apriori. Порождение правил по частым наборам и оценка их интересности.

3) Алгоритм FP-tree.

4) Классификация с помощью алгоритма C4.5 для построения деревьев решений.

5) Алгоритм классификации CART – Classication and Regression Tree.

6) Алгоритм классификации k-ближайших соседей (kNN).

7) Усиление простых классификаторов. Алгоритм AdaBoost.

8) Алгоритмы разбиения:семейство алгоритмов k-средних (k-Means).

9) Агломеративные алгоритмы иерархической кластеризации.

10) Информационный поиск: архитектура систем ИП, модели, алгоритмы.

11) Задача совместной фильтрации и рекомендующие системы. Предсказания на основе N ближайших соседей.

12) Алгоритм анализа связей PageRank.

Литература [1] Барсегян А.А., Купрянов М.С., Степаненко В.В., Холод И.И. Методы и модели анализа данных: OLAP и Data Mining, СПб: "БХВ-Петербург 2004.

[2] Чубукова И.А..Data Mining.. БИНОМ. Лаборатория знаний, Интернетуниверситет информационных технологий – ИНТУИТ.ру, 2008.

[3] А.М. Дехтярь, М.И. Дехтярь. Алгоритмы извлечения знаний из данных (конспект лекций). Тверь: ТвГУ, 2012 (электр.) 3.2 Дискретные и математические модели (биоинформатика) 1) Алгоритмы точного поиска подстрок: линейный алгоритм с Z-значениями.

2) Алгоритмы точного поиска подстрок: Алгоритм Бойера-Мура и его линейное уточнение.

3) Алгоритм Ахо-Корасика для множественного поиска.

4) Суффиксные деревья и алгоритмы их построения.

5) Применения суффиксных деревьев: наибольшая общая подстрока двух строк; распознание загрязнения ДНК.

6) Повторяющиеся структуры в молекупярных строках.

7) Выравнививание последовательностей ДНК: попарное выравнивание.Методы динамического программирования (алгоритм СмитаУотермана).

8) Выравнививание последовательностей ДНК. Локальное и глобальное выравнивание.

9) Методы кластеризации данных и их применение к проблемам биоинформатики.

10) Филогенетические деревья и иерархическая кластеризация.

11) Множественное выравнивание строк: NP-полнота и аппроксимации.

Литература [1] Гасфилд Д. Строки, деревья и последовательности в алгоритмах: Информатика и вычилительная биология. СПб.: Невский Диалект; БХВПетербург, 2003.

[2] Леск А. Введение в биоинформатику. М.: БИНОМ. Лаборатория знаний, 3.3 История и методология прикладной математики и информатики 1) Основные этапы развития математического знания: зарождние, античность, средние века, новое время, современная эпоха.

2) Зарождение и развитие математических дисциплин: геометрии, алгебры, анализа, теории вероятностей, математической логики.

3) Развитие математики в России: допетровская эпоха, 18, 19, 20–21 века.

4) Проблема обоснования математики: формализм, интуиционизм, конструктивизм.

5) Современное состояние математики, наиболее известные из нерешенных математических задач.

6) Развитие методов вычилений и вычислительной техники: древние счетные приспособления (абак, китайская счетная доска), механические устройства (машины Паскаля, Лейбница, Джевонса), развитие вычислительной техники в 20 веке.

Литература [1] Гнеденко Б.В. Очерки по истории математики в России. М.: КомКнига, [2] Бурбаки Н. Очерки по истории математики. М.: КомКнига, 2007.

[3] История математики. (под ред. А.П.Юшкевича). Т.1-3. М.: Наука, 1972.

[4] Математика 19 в. (под ред. А.Н.Колмогорова и А.П.Юшкевича). М.: Наука, 1987.

3.4 Прикладная алгебра и теория чисел 1) Линейное кодирование. Теоремы об исправлении ошибок и об обнаружении ошибок.

2) Матричное кодирование. Лидеры классов. Декодирование.

3) Проверочные матрицы.

4) Условие на проверочную матрицу, гарантирующее обнаружение (d 1) ошибки.

5) Коды Хемминга.

6) Полиномиальные коды.

7) Задание полиномиального кода матрицей.

8) Теорема о связи делимости многочлена, задающего кодирование, с чётностью каждого кода.

9) Теоремы о минимальном расстоянии между кодами.

10) Коды Боуза-Чоудхури- Хоккенгейма.

Литература [1] Г.Биркгоф, Т.Барти. Современная прикладная алгебра. Мир, Москва, [2] У.Питерсон, Э.Уэлдон. Коды, исправляющие ошибки. Мир, Москва, 3.5 Управление проектами 1) Определение этапов при последовательном развитии проекта 2) Жесткие и гибкие стратегии в методологиях программирования 3) Последовательное развитие проекта и итеративное наращивание как метод снижения неопределённости достижения целей 4) Производственные функции в моделировании жизненного цикла 5) Классическая итерационная модель жизненного цикла 6) Каскадная модель жизненного цикла 7) Спираль охвата предметной области 8) Инструментальная спиралевидная модель 9) Модель RUP 10) Модель процессов MSF 11) Модель жизненного цикла экстремального программирования 12) Система трассировки требований 13) Фазовое измерение модели фазы функции 14) Жизненный цикл в методологиях быстрого развития проектов 15) Треугольник менеджмента проектов Литература [1] Скопин И.Н. Основы менеджмента программных проектов. М.: ИНТУИТ.РУ: БИНОМ, [2] Арчибальд Р. Управление высокотехнологичными программными проектами. Пер. с англ. М.: Компания АйТи,