1. Содержание государственного экзамена.

Согласно утвержденному в вузе учебному плану данного направления подготовки магистра базовыми дисциплинами для государственного экзамена являются дисциплины:

·        Вычислительные системы;

·        Интеллектуальный анализ данных и управление знаниями;

·        Сетевые протоколы (магистерская программа «Неоднородные информационные системы»);

·        Испытание и квалиметрия информационных систем (магистерская программа «Компьютерная системная аналитика»).

 2 Регламент государственного экзамена

Государственный экзамен проводится в форме собеседования с членами комиссии и включает в себя следующие части:

1. По общему разделу программы магистрант непосредственно во время экзамена получает теоретический вопрос из общего раздела программы экзамена, по которому проводится устная беседа с членами комиссии.

2. Вопросы по базовым дисциплинам  выдаются за 2 дня до экзамена. Магистрант готовит на каждый вопрос развернутый ответ (в виде конспекта, черновика и т.п.), а также презентацию, по которым проводится устная беседа с членами комиссии.

3. Итоговая оценка выставляется по 100–балльной шкале по сумме баллов по 3 дисциплинам и общему разделу (максимум по 25 баллов за каждый).

3 Вопросы, выносимые на государственный экзамен по базовым дисциплинам

3.1. Общий раздел

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

1.        Основные элемента аппаратно-программной архитектуры: адресное пространство, сегментация, основные сегменты программы: код, статические данные, стек, куча. Структура команды, способы адресации операндов, этапы исполнения команды, микропрограммирование.

2.        Прерывание программ как элемент архитектуры и прием программирования. Этапы обработки прерываний, структуры систем прерываний. Определение допустимого момента прерывания. Организация вхождения в прерывающую программу, возврат к прерванной программе. Вложенные (приоритетные) прерывания. Эмуляция прерываний на уровне процесса (APC, сигналы).

3.        Архитектура, организация ввода–вывода в ЭВМ на системном и прикладном уровнях. Ввод–вывод с программным опросом, по прерыванию и с прямым доступом к памяти. Основные функции контроллера ПДП.

4.        Локальные сети (ЛВС), принципы построения. Топология локальных вычислительных сетей. Методы управления доступом к передающей среде. Детерминированные методы. Случайные методы доступа к передающей среде. Особенности структуры протоколов в ЛВС.

5.        Языки программирования высокого уровня. Структура и сравнительная характеристика: типы данных, классы памяти (локальная, глобальная, динамическая), модульная организация данных и алгоритма, пространства имен, области видимости.

6.        Технология структурного программирования: нисходящее, пошаговое, модульное программирование алгоритма и данных. Технология объектно-ориентированного программирования. Класс, объект, метод, конструктор, деструктор, наследование, полиморфизм, шаблоны, исключения Элементы абстрагирования: полиморфизм, абстрактные классы, интерфейсы.

7.        Модульная разработка программы: проект, файл, объектный модуль, программный (загрузочный) модуль, библиотека объектных модулей.  Внешние ссылки и точки входа. Редактирование связей (компоновка загрузочного модуля). Статическое и динамическое связывание, DLL.

8.        Модульное программирование на Си++ в технологии ООП. Представление программы: заголовочный файл, cpp-файл, объектный модуль. Особенности представления имен внешних ссылок.

9.        Модульное программирование на Java. Файлы class и jar, их структура. Особенности представления Java-программы, динамической загрузки и динамического связывания кода.

10.    Внутренний параллелизм в приложениях. Потоки – определение, составные части и способы описания на уровне API (системных вызовов) и в языках программирования. Управление потоками и синхронизация (Примеры)

11.    Ввод-вывод. Последовательные файлы и файлы прямого доступа. Двоичные и текстовые файлы. Сериализация объектов. (Примеры).

12.    Язык ассемблера. Структура, принципы трансляции. Макрообработка.

13.    Мультипрограммирование, системы пакетной обработки,  разделения времени,  реального времени. Задание, задача, процесс, поток. Системные и прикладные задачи (процессы).  Процесс как основной компонент ОС. Структура адресного пространства процесса. Ядро.  Концепция  ОС  как системы независимых квазипараллельных процессов. Защита процессов, Режим пользователя и режим ядра. Системные вызовы.

14.    Ресурсы ВС и управление ими в ОС.  Базовые ресурсы ОС: ЦП, ОП, ВЗУ, данные. Концепция ОС как системы  распределения  ресурсов  между процессами (задачами).  Тактика и стратегия управления ресурсами – диспетчеры и планировщики. Основные принципы планирования ресурсов в ОС, критерии эффективности ОС.

15.    Управление ЦП в ОС.  Понятие состояния процесса и потока, контекста процесса в ядре ОС. Переключение процессов и потоков. Диспетчер. Стратегии и алгоритмы разделения ЦП: пакетная обработка, разделение времени, реальное время.

16.    Управление памятью в ОС.  Виртуальное и физическое адресное пространство. Понятие виртуального адреса и его преобразования в логический адрес.  Аппаратные средства управления  памятью.  Стратегии управления ОП,  свопинг  (замещение задач). Образ процесса, сегменты виртуального адресного пространства. Файл подкачки.

17.    Виртуальная память и её организация, таблицы страниц. Особенности страничного прерывания, алгоритм его обработки. Структура таблиц на примере микропроцессора Intel.

18.    Методы управления виртуальной памятью, сегментно-страничное распределение с динамической загрузкой страниц.  Сущность конкуренции страниц за физическую память. Глобальное и локальное вытеснение. Алгоритмы вытеснения страниц: оптимальный, LRU, FIFO.

19.    Понятие локальности обращений к памяти. Рабочий набор страниц, способы его определения (отслеживания). Работа ос в условиях дефицита памяти: свопинг рабочих наборов, пробуксовка.

20.    Управление вводом/выводом в ОС. ВУ последовательного и произвольного доступа. Физический параллелизм работы ЦП и ВУ. Очереди ввода/вывода, буферизация. Драйверы. Диспетчер ввода-вывода. Отложенная запись, кэширование. Пример организации ввода-вывода в многозадачной системе с виртуальной памятью и драйвером, работающим по прерыванию.

21.    Управление данными в ОС.  Файлы,  файловая система.  Уровни файловой системы: физический, базовый, логический, их функции. Примеры реализации: контроль свободного пространства, размещение файла, индексный файл, доступ и защита, система каталогов, работа в файле с записями произвольной длины. Надежность и восстановление файловой структуры, методы и средства.

22.    Сравнительная характеристика структуры и функциональности файловых систем (FAT, NTFS, EXT)

23.    Синхронизация процессов  в  ОС.   Механизмы   синхронизации процессов в ядре ОС и на уровне прикладного программирования: ожидание событий на объектах, семафоры, почтовые ящики, порты. Пример синхронизации (задача «поставщик-потребитель»).

24.    Трансляторы. Компиляция  и интерпретация.  «Чистые» компиляторы и интерпретаторы, смешанные системы (на примере Си++, Java, C#). Фазы трансляции: лексический, синтаксический,  семантический анализ, генерация кода, оптимизация. Их сущность. Примеры лексических, синтаксических  и семантических ошибок и ошибок времени исполнения.

25.    Формализация описания процесса трансляции: формальные грамматики и конечные автоматы. Основные компоненты транслятора: синтаксическое дерево, семантические таблицы, семантические процедуры, связь лексической, синтаксической и семантической компонент.

26.    Лексический анализ. Конечные автоматы и построение лексических анализаторов. Синтаксический анализ.  Формальные грамматики и языки. Восходящий и нисходящий разбор. Магазинные автоматы и их использование в синтаксических анализаторах.

27.    Среда исполнения Си-программы. Стек. Организация контекста исполнения функции – формальные/фактические параметры и локальные переменные. Механизмы вызова виртуальных функций и динамического приведения типов.

28.    Среда исполнения Java-программы. Мета-уровень представления объектов и классов (классы Object и Class). Виртуальная машина (JVM), система команд. Контекст вызова метода.

29.    Банки данных. База данных, банк данных СУБД. Модели данных: иерархическая, сетевая,  реляционная. Функции и языковые средства СУБД. Этапы проектирования БД.

30.    Системы искусственного интеллекта. Отличия знаний и данных.  Процедурные и декларативные знания. Методы представления знаний: продукции, логика предикатов, семантические сети, фреймы. Языки логического программирования 

3.2. Вычислительные системы

 

1.    История и уровни параллелизма. Скалярная и векторная обработка информации. Конвейер. Классификации архитектур вычислительных систем. Систематика Флинна.

2.    Векторно-конвейерные системы. Общие принципы магистральной обработки. Архитектурные принципы. Функциональные устройства. Системы STAR-100, CRAY

3.    Матричная обработка информации. Общие принципы построения и функционирования матричных архитектур. Массивы процессорных элементов. Сети обмена. Система ILLIAC-IV.

4.    Общие принципы ассоциативной обработки информации. Категории ассоциативных систем. Система PEPE.

5.    Подсистема управления. Модули ассоциативных матриц. Система STARAN. Функциональная схема, Флип-сеть системы.

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

7.    Общие принципы построения транспьютерных систем. Поддержка параллелизма. Язык Оккам.

8.    Транспьютерное семейство фирмы Inmos. Внутренняя архитектура транспьютера, процессор транспьютера. Организация связного списка процессов.

9.    Модель коллектива вычислителей. Принципы построения. Функциональный, коммуникационно-настроечный автомат. Функциональная структура элементарной машины. Системные операции.

10.    Организация межмашинных взаимодействий. Типовые схемы обменов. Архитектура и системное устройство ОВС «Минимакс». Особенности распределенных вычислительных систем.

11.    Однородные вычислительные среды. Классификация. Принципы построения вычислительных сред. Соединительные и функциональные элементы среды. Программирование и настройка среды. Физическая реализация элементов среды.

12.    Основные подходы при организации параллельных вычислений. Локальное и глобальное распараллеливание. Распараллеливание на уровне алгоритмических языков. Ярусно-параллельные формы. Крупноблочное распараллеливание. Особенности реализации параллельных алгоритмов на распределенных вычислительных системах.

13.    Основные режимы функционирования ВС. Режим решения сложной   задачи. Решение набора задач на ВС. Эвристические алгоритмы, основанные на минимизации функции штрафа. Функционирование ВС при поступлении потока задач. Организация функционирования распределенных вычислительных систем.

14.    Отказоустойчивые вычислительные системы. Концепция устойчивости вычислительных систем к отказам. Алгоритмы обнаружения неисправностей. Эффект «Домино» и методы его устранения. Вычислительная система космического корабля «Шаттл».

15.    Производительность вычислительных систем. Пиковая и реальная производительность. Закон Гроша. Способы измерения реальной производительности. Методы оценки производительности. Основные тенденции развития архитектурных принципов в области вычислительных систем.

3.3. Интеллектуальный анализ данных и управление знаниями

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

2.    Закономерность. Основные виды закономерностей. Основы представления, структурирования, трансформации и воспроизведение знаний.

3.    Общее и  особенное в процессах извлечения и приобретения знаний. Характеристики основных методов, средств и технологий извлечения знаний из данных.

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

5.    Основы организации, обработки и анализа данных в системах управления знаниями.

6.    Базовые методы и модели когнитивного анализа данных для  поддержки принятия решений.

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

8.    Выделение сегментов и обнаружения скрытых закономерностей  в многомерных данных методами прикладной статистики.

9.    Выявления и восстановление  функциональных зависимостей средствами регрессионного анализа.

10.    Анализ и прогнозирование временных рядов. Основные способы формирования, оценки адекватности и точности моделей прогнозирования временных рядов.

11.    Деревья решений, принципы их построения, основы их применения для решения основных задач интеллектуального анализа данных.

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

13.    Основы организации и применения OLAP-технологии в системах интеллектуального анализа данных и управления знаниями.

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

15.    Основные направления эволюционного моделирования и особенности применения эволюционного программирования в системах интеллектуального анализа данных и управления знаниями.

16.    Генетические алгоритмы, их основные особенности и применение в системах интеллектуального анализа данных и управления знаниями.

3.4. Сетевые протоколы (магистерская программа «Неоднородные информационные системы»)

1.    Информационная сеть. Понятие протокола. Протоколы и интерфейсы. Иерархия протоколов. Терминология и типовые решения: подтверждения, тайм-ауты, keep-alive, прозрачность, избыточность, синхронизация потоков данных, управление потоками данных, автоматные модели протоколов.

2.    Модель OSI для взаимодействия открытых систем. Назначение, функции и алгоритмы функционирования протоколов 7 уровней модели. Интернет. Стек протоколов TCP/IP, его особенности, соответствие модели OSI.

3.    Программирование на прикладном уровне в Интернет. Логический канал, дейтаграмма. Программный интерфейс Socket. Установление соединения на сокетах: структуры данных (TCB), связь с протоколом TCP. Работа с логическими соединениями на  Java (Socket, ServerSocket, потоки данных).

4.    Протокол HTTP (форматы, алгоритмы, представление данных). Использование классов URL и URLConnection для работы с протоколом HTTP на Java. Использование сервлетов для реализации серверных компонент протокола HTTP (пример). Протокол удаленного доступа  к файлам FTP.

5.    Распределенные системы и системы с удаленным (дистанционным) доступом. Клиент и сервер: программные компоненты и роли. Определение точки соединения «клиент-сервер». Тонкий и толстый клиент. Протоколы на основе текстовых, двоичных и сериализуемыех потоков данных. Асинхронное и синхронное взаимодействие. Сервер с постоянными короткими  соединениями (транзакциями). Многопоточность в клиентских и серверных приложениях (примеры).

6.    Сети p2p и сети с распределенным хранением и поиском данных. Протокол DirectConnect (DC).

7.    Протоколы канального уровня в соединениях типа точка-точка (в битовых и байтовых потоках). Протоколы локальных сетей: подуровни MAC и LLC. Протоколы ARP и RARP для связи канального уровня с уровнем IP.

8.    Семейство протоколов IP. Формат кадра IP. Функциональность протокола. Маршрутизация. Иерархия маршрутизаторов: протоколы GGP,EGP,IGP(RIP)

9.    Транспортный протокол TCP. Формат пакета. Сегментирование потока данных, подтверждение, тайм-ауты, управление потоком. Установление соединения: алгоритм, диаграмма состояния.

10.              Доменная система имен и DNS. Домены и зоны, серверы DNS, алгоритм определения IP-адреса по имени.

3.5. Испытание и квалиметрия информационных систем (магистерская программа «Компьютерная системная аналитика»)

1. Определение квалиметрии. Объект, предмет исследования, методология. Показатели качества продукции, методы измерения показателей качества. Измерительные шкалы. Комплексирование показателей качества. Многоуровневая структура показателей качества.

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

3. Метрики Холстеда. Оценки длины и объема программы. Потенциальный  объем программы. Уровень языка программирования. Интеллектуальное содержание программы. Метрика числа ошибок в программах. Причины  несоответствия  оценок теоретическим значениям.

4. Измерительные мониторы, их классификация. Виды измеряемых характеристик программ. Детерминированные  и статистические характеристики. Трассировочные записи, временные и частотные профили.

5. Корректность программ. Верификация ПО на различных этапах жизненного цикла. Методы верификации программ.

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

7. Надежность программного обеспечения. Математические модели надёжности программ. Классификация и общие характеристики. Динамические модели надёжности, примеры расчётов

8. Надежность программного обеспечения. Математические модели надёжности программ. Классификация и общие характеристики. Статические и эмпирические модели надёжности, примеры расчётов.

9. Тестирование программных продуктов. Классификация видов тестирования. Методы тестирования по принципу «белого ящика», их описание и иллюстрация применения.

10. Тестирование программных продуктов. Классификация видов тестирования. Методы тестирования по принципу «чёрного ящика», их описание и иллюстрация применения.

11. Метрические свойства параллельных алгоритмов. Измерение характеристик и методология оптимизации производительности параллельных приложений.