05.13.11 (Программы вступительных экзаменов в аспирантуру по направленностям)

Федеральное государственное бкяжетное образовательное учреждение высожГо образован ох (<Чоекоаекнй технологический университета УТВЕРЖДАЮ Первый проректор .'": ';е::~ .ъ>',: ' " '~::-;ис 2016 Г вступительцоГО ЭкааМЕИП"" Уровень высшего ооразоваиия ПолГотовка калров выетпей кпалпфикапип Направлеиие полГОТОВки 09.06.01 «Информатика и вычислительная техника» Направленность 1научная спениальность) 05.13.11 аМатематичеекое и протраммиое ооеепечение вычислительных машин~ комплексов и компьтотерпых сетей Москва, 2016 1. Математические основы программировании Поняти~ алгоритма и его ут~~~ения: машины Тьюринга, нормальные алгоритмы Маркова, рекурсивные функции.

Эквивалентность данных формальных моделей алгоритмов. Понятие об алгоритмическоЙ неразрешимости. Примеры алгоритмически неразрешимых проблем, Понятие сложности алгоритмов. Классы Р и МР. Полнномиальная сводимость ~ада~. Теорема Кука оо ~чР- полноте задачи выполнимости ПулевоЙ формулы. Примеры ХР-полных задач, подходы к их решению. Точные и приближенные комбинаторные алгоритмы.

Примеры эффективных 1'полиномиальных) алгоритмов: быстрые алгоритмы поиска и сортировки; полиномиальные алгоритмы для задач на графах и сетях «поиск в глубину и ширину, о минимальном кратчайшем пути, о назначениях). Автоматы. Эксперименты с автоматами. Алгебры регулярных выражений. Теорема Клини о регулярных языках. Алгебра логики. Булевы функции, канонические формы задания булевых функций. Понятие полной системы. Критерий полноты Поста. Минимизация булевых функций в классах нормальных форм. Исчисление предикатов первого порядка.

Понятие интерпретации. Выполнимость и общезначимость формулы первого порядка. Понятие модели. Теорема о полноте исчисления предикатов первого порядка. Отношения и функции. Отношение эквивалентности и разбиения. Фактор множества, Отношения частичного порядка. Теоретико-множественное и алгебраическое определения решетки, их эквивалентность.

Свойства решеток. Ьулевы решетки. Полные решетки. Формальные языки и способы их описания. Классификация формальных грамматик. Их использование в лексическом и синтаксическом анализе. Л- исчисление, правила редукции, единственность нормальной формы и правила ее достижения, представление рекурсивных функций. Основы комбинаторного анализа. Метод производящих функций, метод включений и исключений.

Примеры применения. Коды с исправлением ошибок. Алфавитное кодирование. Методы сжатия информации. Основы криптографии. Задачи обеспечения конфиденциальности и целостности информации. Теоретико- информационный и теоретикосложностный подходы к определению криптографической стойкости. Американский стандарт шифрования 0ЕБ и российский стандарт шифрования данных ГОСТ 28147-89. Системы шифрования с открытым ключом (КЯА), Цифровая подпись.

Методы генерации и распределения ключей. 2. Вычислительные машины, системы и сети Архитектура современных компьютеров. Организации памяти н архитектура процессора современных вычислительных машин. Страничная и сегментная организация виртуальной памяти. Кзш-память. Командный и арифметический конвейеры, параллельное выполнение независимых команд, векторные команд~.

Специализированные процессор~. Машины, обеспечивающие выполнение вычислений, управляемых потоком данных. Организация авода-вывода, каналы и процессоры ввода-вывода, устройства сопряжения с объектами. Классификация вычислительных систем (ВС) по способу организации параллельной обработки.

Многопроцессорные и многомашинные комплексы. Вычислительные кластеры. Проблемно-ориентированные параллельные структур~: матричные ВС, систолическне структуры, н~йр~сети. Назначение, архитектура н принципы построения информационно вычислительных сетей (ИВС), Локальные и глобальные ЛВС, технические и программные средства объединения различных сетей.

Методы и средства передачи данных в ИВС, протоколы передачи данных. Особенности архитектуры локальных сетей (Ейегпе1, Треп К(пд, ГИЗИ), Сеть ! шепнете, доменная организация, семейство протоколов ТСР/1Р. ИнФормационно-Вычислительные сети и распределенная обработка информации. 3. Языки и системы программироваиия. Технология разработки программного обеспечения Языки программирования.

Процедурные языки программирования (Фортран, Сн), Функциональные языки программирования (Лисп), логическое программирование (Пролог), обьектно-ориентированные языки программирования (Ява). Процедурные языки программирования. Основные управляющие конструкции, структура программы. Работа с данными: переменные и константы, типы данных (булевский, целочисленные, плавающие, символьные, типы диапазона и перечисления, указатели), структуры данных (массивы и записи).

Процедуры (функции): вызов' процедур, передача параметров (по ссылке, по значению, по результату), локализация переменных, побочные эффекты. Обработка исключительных ситуаций. Библиотеки процедур и их использование. Обьектно-ориентированное программирование. Классы и объекты, наследование, интерфейсы. Понятие об объектном окружении. Рефлексия. Библиотеки классов. Средства обработки объектов (контейнеры и итераторы). Распределенное программирование. Процессы и их синхронизация. Семафор~, мониторы Хоара. Ооьектно- ориентиро~а~ное распределенное программирование.

СОКВА. Параллельное программирование над общей памятью. Нити. Стандартный интерфейс Ореп МР. Распараллеливание последовательных программ. Параллельное программирование над распределенной памятью. Парадигмы ЯРМО и М1МЭ. Стандартный интерфейс МР1. Основы построения трансляторов, Структура оптимизирующего транслятора. Промежуточные представления программы.' последовательность символов, последовательность лексем, синтаксическое дерево, абстрактное синтаксическое дерево.

Уровни промежуточного представления: высокий, средний, низкий. Формы промежуточного представления. Анализ исходной программы в компиляторе. Автоматные 1регулярные) грамматики и сканирование, контекстно свободные грамматики и синтаксический ан ииз, организация таблицы символов программы, имеющей блочную структуру, хеш-функции. Нисходящие 1ЬЦ1)-грамматики) и восходящие (ЕЙ~1)-граММаТп1сп) методы синтаксического анализа. Атрибутные грамматики н семантические программы, построение абстрактного синтаксического дерева.

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

Отношение доминирования и его свойства, построений границы области доминирования вершины, выделение сильно связанных компонент графа. Построение графа зависимостей. Перевод программы в ЯЯА-представление и обратно. Глобальная и межпроцедурная оптимизация. Генерация объектного кода в компиляторах. Перенастраиваемые ~ге1агвеийе) компиляторы, асс ~набор компиляторов Спи).

Переработка термов 11епп ге~чгй1пф. Применение оптимизационных эвристик 1целочисленное программирование, динамическое программирование) для автоматической генерации генераторов объектного кода (системы ВЕб, 1Ьиг~ и др.). Машинно-ориентированные языки. язык ассемблера. Представление машинных команд и констант. Команды транслятору. Их типы, принципы реализации. Макросредства, макровызовы, языки макроопределений, условная макрогенерация, принципы реализации. Системы программирования 1СП), типовые компоненты СП: языки, трансляторы, редакторы связей, отладчики, текстовые редакторы. Модульное программирование. Типы модулей. Связывание модулей по управлению и данным.

Пакеты прикладных программ 1ППП). Системная часть и наполнение. Языки общения с ППП. Машинная графика. Средства поддержки машинной графики. Графические пакеты. Технология разработки и сопровождения программ. Жизненный цикл программы. Этапы разработки, степень и пути их автоматизации. Обратная инженерия. Декомпозиционные и сборочные технологии, механизмы наследования, инкапсуляции, задания типов. Модули, взаимодействие между модулями, иерархические структуры программ.

Отладка, тестирование, верификация и оценивание сложности программ, Генерация тестов. Системы генерации тестов. Срезы программ (в|1се, с)юр) и их применение при отладке программ и для генерации тестов. Методы спецификации программ. Методы проверки спецификации. Схемное, структурное, визуальное программирование, Разработка пользовательского интерфейса, стандарт С1.1А, мультимедийные среды интерфейсного взаимодействия. 4.

Операционные системы Режимы функционирования вычислительных систем, структура и функции операционных систем. Основные блоки и модули. Основные средства аппаратной поддержки функций операционных систем ~ОС): система прерываний, защита памяти, механизмы преобразования адресов в системах виртуальной памяти, управление каналами и периферийными устройствами. Виды процессов и управления ими в современных ОС.

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