МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ

ФЕДЕРАЦИИ

Ярославский государственный университет им. П.Г. Демидова

Факультет ИВТ

УТВЕРЖДАЮ

Декан факультета ИВТ

_

"_"2012г.

Программа вступительного экзамена в аспирантуру по специальности научных работников 05.13.11 Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей Ярославль 2012 Программа вступительного экзамена в аспирантуру по специальности 05.13.11 – математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей 1. Алгебра и геометрия: отношения и функции; отношение эквивалентности и разбиения фактор множества; отношения частичного порядка; алгебраические структуры.

Теория матриц; системы линейных алгебраических уравнений; векторные пространства, линейные отображения; линейные пространства и операторы; аналитическая геометрия;

многомерная геометрия кривых и поверхностей.

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

Уравнения математической физики: уравнения гиперболического, параболического и эллиптического типа; исследование основных задач для уравнений математической физики.

Численные методы решения задач математического анализа, алгебры и обыкновенных дифференциальных уравнений; численные методы решения задач математической физики; методы решения сеточных уравнений.

Теория вероятностей и математическая статистика: аксиоматика теории вероятностей;

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

Математические методы принятия решений; методы исследования операций. Модели линейного программирования; транспортная задача; задача распределения ресурсов;

динамическое планирование; распределение потоков товарных поставок на транспортной сети; эквивалентные сети; транспортная задача Хичкока—Купманса; выбор оптимального транспортного маршрута; использование линейного программирования для решения оптимизационных задач.

Понятие алгоритма и его уточнения: машины Тьюринга, рекурсивные функции.

Эквивалентность формальных моделей алгоритмов. Понятие об алгоритмической неразрешимости. Понятие сложности алгоритмов. Классы P и NP. Полиномиальная сводимость задач.

Автоматы. Алгебра регулярных выражений. Теорема Клини о регулярных языках.

Функциональные системы с операциями; дискретные структуры (графы, сети).

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

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

Исчисление предикатов первого порядка. Понятие интерпретации. Выполнимость и общезначимость формулы первого порядка. Понятие модели. Теорема о полноте исчисления предикатов первого порядка.

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

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

Коды с исправлением ошибок. Алфавитное кодирование. Методы сжатия информации.

Основы криптографии. Задачи обеспечения конфиденциальности и целостности информации. Системы шифрования с открытым ключом (RSA). Цифровая подпись.

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

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

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

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

Методы и средства передачи данных в ИВС, протоколы передачи данных.

Особенности архитектуры локальных сетей (Ethernet, Token Ring, FDDI).

Сеть Internet, доменная организация, семейство протоколов TCP/IP. Информационновычислительные сети и распределенная обработка информации.

3. Процедурные языки программирования (Си). Функциональные языки программирования (Лисп), логическое программирование (Пролог), объектноориентированные языки программирования (Ява).

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

Объектно-ориентированное программирование. Классы и объекты, наследование, интерфейсы. Понятие об объектном окружении. Рефлексия. Библиотеки классов. Средства обработки объектов (контейнеры и итераторы).

Распределенное программирование. Процессы и их синхронизация. Семафоры, мониторы Хоара. Объектно-ориентированное распределенное программирование. CORBA.

Параллельное программирование над общей памятью. Нити. Стандартный интерфейс Open MP. Распараллеливание последовательных программ. Параллельное программирование над распределенной памятью. Парадигмы SPMD и MIMD.

Стандартный интерфейс MPI.

Основы построения трансляторов. Структура оптимизирующего транслятора.

Промежуточные представления программы: последовательность символов, последовательность лексем, синтаксическое дерево, абстрактное синтаксическое дерево.

Уровни промежуточного представления: высокий, средний, низкий. Формы промежуточного представления.

Анализ исходной программы в компиляторе. Автоматные (регулярные) грамматики и сканирование, контекстно-свободные грамматики и синтаксический анализ, организация таблицы символов программы, имеющей блочную структуру, хеш-функции. Нисходящие (LL(1)-грамматики) и восходящие (LR(1)-грамматики) методы синтаксического анализа.

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

Системы программирования (СП), типовые компоненты СП: языки, трансляторы, редакторы связей, отладчики, текстовые редакторы. Модульное программирование. Типы модулей. Связывание модулей по управлению и данным.

Пакеты прикладных программ (ППП). Системная часть и наполнение. Языки общения с ППП. Машинная графика. Средства поддержки машинной графики. Графические пакеты.

Технология разработки и сопровождения программ. Жизненный цикл программы. Этапы разработки,, инкапсуляции, задания типов. Модули, взаимодействие между модулями, иерархические структуры программ.

Отладка, тестирование, верификация и оценивание сложности программ. Генерация тестов. Системы генерации тестов.

Методы спецификации программ. Методы проверки спецификации.

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

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

Модель клиент-сервер и ее реализация в современных ОС.

Параллельные процессы, схемы порождения и управления. Организация взаимодействия между параллельными и асинхронными процессами: обмен сообщениями, организация почтовых ящиков. Критические участки, примитивы взаимоисключения процессов, семафоры Дейкстры и их расширения. Проблема тупиков при асинхронном выполнении процессов, алгоритмы обнаружения и предотвращения тупиков.

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

Управление доступом к данным. Файловая система, организация, распределение дисковой памяти. Управление обменом данными между дисковой и оперативной памятью. Рабочее множество страниц (сегментов) программы, алгоритмы его определения.

Управление внешними устройствами.

Оптимизация многозадачной работы компьютеров. Операционные системы Windows, Unix, Linux. Особенности организации, предоставляемые услуги пользовательского взаимодействия.

Операционные средства управления сетями. Эталонная модель взаимодействия открытых систем ISO/OSI. Маршрутизация и управление потоками данных в сети. Локальные и глобальные сети. Сетевые ОС, модель клиент-сервер, средства управления сетями в ОС UNIX, Windows NT. Семейство протоколов TCP/IP, структура и типы IP-адресов, доменная адресация в Internet. Транспортные протоколы TCP, UDP.

Удаленный доступ к ресурсам сети. Организация электронной почты, телеконференций.

Протоколы передачи файлов FTP и HTTP, язык разметки гипертекста HTML, разработка WEB-страниц, WWW-серверы.

5. Концепция типа данных. Абстрактные типы данных. Объекты (основные свойства и отличительные признаки).

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

Основные понятия реляционной и объектной моделей данных.

Теоретические основы реляционной модели данных (РДМ). Реляционная алгебра, реляционное исчисление. Функциональные зависимости и нормализация отношений.

CASE-средства и их использование при проектировании базы данных (БД).

Организация и проектирование физического уровня БД. Методы индексирования.

Обобщенная архитектура, состав и функции системы управления базой данных (СУБД).

Характеристика современных технологий БД.

Основные принципы управления транзакциями, журнализацией и восстановлением.

Язык баз данных SQL. Средства определения и изменения схемы БД, определения ограничений целостности. Контроль доступа. Средства манипулирования данными.

Стандарты языков SQL. Основные понятия технологии клиент-сервер. Характеристика SQL-сервера и клиента. Сетевое взаимодействие клиента и сервера.

Информационно-поисковые системы. Классификация. Методы реализации и ускорения поиска.

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

Экспертные системы (ЭС). Области применения ЭС. Архитектура ЭС. Механизмы вывода, подсистемы объяснения, общения, приобретения знаний ЭС. Жизненный цикл экспертной системы.

6. Аппаратные и программные методы защиты данных и программ. Защита данных и программ с помощью шифрования.

Защита от несанкционированного доступа в OC Windows NT. Система безопасности и разграничения доступа к ресурсам в Windows NT. Файловая система NFTS и сервисы Windows NT.

Защита от несанкционированного копирования. Методы простановки некопируемых меток, настройка устанавливаемой программы на конкретный компьютер, настройка на конфигурацию оборудования.

Защита от разрушающих программных воздействий. Вредоносные программы и их классификация. Загрузочные и файловые вирусы, программы-закладки. Методы обнаружения и удаления вирусов, восстановления программного обеспечения.

Защита информации в вычислительных сетях Novell Netware, Windows NT и др.

по специальности 05.13.11 – математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей Смирнов В.И. Курс высшей математики. Т.1, 2, 3, 4. М.: Наука, 1974.

Яблонский С.В. Введение в дискретную математику. М.: Наука, 2001.

Феллер В. Введение в теорию вероятностей и ее приложения. В 2 т. М.: Мир, 1982.

Введение в криптографию / Под ред. В.В. Ященко. СПб.: МЦНМО, 2001.

Михайлов А.И., Черный А.И., Гиляревский Р.Э. Основы информатики. М.: Наука, 1978.

Шемякин Ю.И. Введение в информатику. М.: Финансы и статистика, 1985.

Кнут Д. Искусство программирования. Т. 1 – 3. М., СПб., Киев: ИД «Вильямс», 2000.

Королёв Л.Н. Структуры ЭВМ и их математическое обеспечение. М.: Наука, 1980.

Ахо, Сети Р., Ульман Дж. Компиляторы: принципы, техника реализации и инструменты.

М., 2001.

Мартин Дж. Организация баз данных в вычислительных системах. М.: Мир, 2000.

Попов И.И., Максимов Н.В., Храмцов П.Б. Введение в сетевые информационные ресурсы и технологии: Учеб. пособие для вузов. М.: Изд-во РГГУ, 2001.

Дейт К.Дж. Введение в системы баз данных. М.: Вильямс, 1999.

Дейтел Г. Введение в операционные системы. М.: Мир, 1987.

Мельников В.В. Защита информации в компьютерных системах. М.: Финансы и статистика, 1997.

Корнеев В.В. Параллельные вычислительные системы. М.: Нолидж, 1999.