Документ взят из кэша поисковой машины. Адрес оригинального документа : http://www.iki.rssi.ru/aspirantura/vstp051311.doc Дата изменения: Mon Mar 17 17:14:51 2014 Дата индексирования: Sun Apr 10 01:39:43 2016 Кодировка: koi8-r Поисковые слова: guide 8.0

УТВЕРЖДАЮ
директор ИКИ РАН
академик РАН Л.М.Зеленый

__________________________


«
»______________2013г.


ПРОГРАММА
вступительного экзамена по специальности
05.13.11 «Математическое и программное обеспечение вычислительных машин,
комплексов

и компьютерных сетей»
по физико-математическим и техническим наукам
1. Математические основы программирования
Понятие алгоритма и его уточнения: машины Тьюринга, нормальные
алгоритмы Маркова, рекурсивные функции.
Примеры эффективных (полиномиальных) алгоритмов: быстрые алгоритмы
поиска и сортировки; полиномиальные алгоритмы для задач на графах и сетях
(поиск в глубину и ширину, о минимальном остове, о кратчайшем пути, о
назначениях).
Алгебра логики. Булевы функции, канонические формы задания булевых
функций. Понятие полной системы. Критерий полноты Поста. Минимизация
булевых функций в классах нормальных форм.
Исчисление предикатов первого порядка. Понятие интерпретации.
Выполнимость и общезначимость формулы первого порядка. Понятие модели.
Теорема о полноте исчисления предикатов первого порядка.
Отношения и функции. Отношение эквивалентности и разбиения. Фактор
множества. Отношения частичного порядка. Теоретико-множественное и
алгебраическое определения решетки, их эквивалентность. Свойства решеток.
Булевы решетки. Полные решетки.
Формальные языки и способы их описания. Классификация формальных
грамматик. Их использование в лексическом и синтаксическом анализе.
Основы криптографии. Задачи обеспечения конфиденциальности и
целостности информации. Теоретико-информационный и теоретико-сложностный
подходы к определению криптографической стойкости. Американский стандарт
шифрования DES и российский стандарт шифрования данных ГОСТ 28147-89.
Системы шифрования с открытым ключом (RSA). Цифровая подпись. Методы
генерации и распределения ключей.
2. Вычислительные машины, системы и сети
Архитектура современных компьютеров. Организации памяти и архитектура
процессора современных вычислительных машин. Страничная и сегментная
организация виртуальной памяти. Кэш-память. Командный и арифметический
конвейеры, параллельное выполнение независимых команд, векторные команды.
Специализированные процессоры. Машины, обеспечивающие выполнение
вычислений, управляемых потоком данных. Организация ввода-вывода, каналы и
процессоры ввода-вывода, устройства сопряжения с объектами.
Назначение, архитектура и принципы построения информационно -
вычислительных сетей (ИВС). Локальные и глобальные ИВС, технические и
программные средства объединения различных сетей.
Классификация вычислительных систем (ВС) по способу организации
параллельной обработки. Многопроцессорные и многомашинные комплексы.
Вычислительные кластеры. Проблемно-ориентированные параллельные структуры:
матричные ВС, систолические структуры, нейросети.
Понятие параллельных вычислительных систем. Типы параллельных
вычислительных систем.
Концепция ГРИД. Программное обеспечение Globus Toolkit, Legion.
Кластерные файловые системы. Кластерная файловая система «Lustre».
Методы и средства передачи данных в ИВС, протоколы передачи данных.
Особенности архитектуры локальных сетей (Ethernet, Token Ring, FDDI).
Сеть Internet, доменная организация, семейство протоколов TCP/IP.
Информационно-вычислительные сети и распределенная обработка информации.


3. Языки и системы программирования.

Технология разработки программного обеспечения
Языки программирования. Процедурные языки программирования (Фортран,
Си), Функциональные языки программирования (Лисп), логическое
программирование (Пролог), объектно-ориентированные языки программирования
(Ява).
Процедурные языки программирования. Основные управляющие конструкции,
структура программы. Работа с данными: переменные и константы, типы данных
(булевский, целочисленные, плавающие, символьные, типы диапазона и
перечисления, указатели), структуры данных (массивы и записи). Процедуры
(функции): вызов процедур, передача параметров (по ссылке, по значению, по
результату), локализация переменных, побочные эффекты. Обработка
исключительных ситуаций. Библиотеки процедур и их использование.
Объектно-ориентированное программирование. Классы и объекты,
наследование, интерфейсы. Понятие об объектном окружении. Рефлексия.
Библиотеки классов. Средства обработки объектов (контейнеры и итераторы).
Машинно-ориентированные языки, язык ассемблера. Представление
машинных команд и констант. Команды транслятору. Их типы, принципы
реализации. Макросредства, макровызовы, языки макроопределений, условная
макрогенерация, принципы реализации.
Системы программирования (СП), типовые компоненты СП: языки,
трансляторы, редакторы связей, отладчики, текстовые редакторы. Модульное
программирование. Типы модулей. Связывание модулей по управлению и данным.
Пакеты прикладных программ (ППП). Системная часть и наполнение. Языки
общения с ППП. Машинная графика. Средства поддержки машинной графики.
Графические пакеты.
Технология разработки и сопровождения программ. Жизненный цикл
программы. Этапы разработки, степень и пути их автоматизации. Обратная
инженерия. Декомпозиционные и сборочные технологии, механизмы наследования,
инкапсуляции, задания типов. Модули, взаимодействие между модулями,
иерархические структуры программ.

4. Операционные системы
Режимы функционирования вычислительных систем, структура и функции
операционных систем. Основные блоки и модули. Основные средства аппаратной
поддержки функций операционных систем (ОС): система прерываний, защита
памяти, механизмы преобразования адресов в системах виртуальной памяти,
управление каналами и периферийными устройствами.
Виды процессов и управления ими в современных ОС. Представление
процессов, их контексты, иерархии порождения, состояния и взаимодействие.
Многозадачный (многопрограммный) режим работы. Команды управления
процессами. Средства взаимодействия процессов. Модель клиент-сервер и ее
реализация в современных ОС.
Управление доступом к данным. Файловая система, организация,
распределение дисковой памяти. Управление обменом данными между дисковой и
оперативной памятью. Рабочее множество страниц (сегментов) программы,
алгоритмы его определения.
Управление внешними устройствами.
Оптимизация многозадачной работы компьютеров. Операционные системы
Windows, Unix, Linux. Особенности организации, предоставляемые услуги
пользовательского взаимодействия.
Операционные средства управления сетями. Эталонная модель
взаимодействия открытых систем ISO/OSI. Маршрутизация и управление потоками
данных в сети. Локальные и глобальные сети. Сетевые ОС, модель клиент -
сервер, средства управления сетями в ОС UNIX, Windows NT. Семейство
протоколов TCP/IP, структура и типы IP-адресов, доменная адресация в
Internet. Транспортные протоколы TCP, UDP .
Удаленный доступ к ресурсам сети. Организация электронной почты,
телеконференций. Протоколы передачи файлов FTP и HTTP, язык разметки
гипертекста HTML, разработка WEB-страниц, WWW-серверы.

5. Методы хранения данных и доступа к ним.

Организация баз данных и знаний
Концепция типа данных. Абстрактные типы данных. Объекты (основные
свойства и отличительные признаки).
Основные структуры данных, алгоритмы обработки и поиска.
Сравнительная характеристика методов хранения и поиска данных.
Основные понятия реляционной и объектной моделей данных.
Теоретические основы реляционной модели данных (РДМ). Реляционная
алгебра, реляционное исчисление. Функциональные зависимости и нормализация
отношений.
CASE-средства и их использование при проектировании базы данных (БД).
Организация и проектирование физического уровня БД. Методы
индексирования.
Обобщенная архитектура, состав и функции системы управления базой
данных (СУБД). Характеристика современных технологий БД. Примеры
соответствующих СУБД.
Основные принципы управления транзакциями, журнализацией и
восстановлением.
Язык баз данных SQL. Средства определения и изменения схемы БД,
определения ограничений целостности. Контроль доступа. Средства
манипулирования данными.
Стандарты языков SQL. Интерактивный, встроенный, динамический SQL.
Основные понятия технологии клиент-сервер. Характеристика SQL-сервера
и клиента. Сетевое взаимодействие клиента и сервера.
Информационно-поисковые системы. Классификация. Методы реализации и
ускорения поиска.
Методы представления знаний: процедурные представления, логические
представления, семантические сети, фреймы, системы продукций.
Интегрированные методы представления знаний. Языки представления знаний.
Базы знаний.

6. Сети передачи данных
Основные сетевые концепции. Глобальные, территориальные и локальные
сети. Проблемы стандартизации. Сетевая модель OSI. Модели взаимодействия
компьютеров в сети.
Среда передачи данных. Преобразование сообщений в электрические
сигналы, их виды и параметры. Проводные и беспроводные каналы передачи
данных.
Локальные сети. Протоколы, базовые схемы пакетов сообщений и
топологии локальных сетей. Сетевое оборудование ЛВС.
Глобальные сети. Основные понятия и определения. Сети с коммутацией
пакетов и ячеек, схемотехника и протоколы. Принципы межсетевого
взаимодействия и организации пользовательского доступа. Методы и средства
защиты информации в сетях. Базовые технологии безопасности.

7. WWW технологии

Принципы функционирования Internet, типовые информационные объекты и
ресурсы. Ключевые аспекты WWW-технологии.
Адресация в сети Internet. Методы и средства поиска информации в
Internet, информационно-поисковые системы.
Языки и средства программирования Internet приложений. Язык
гипертекстовой разметки HTML, основные конструкции, средства подготовки
гипертекста (редакторы и конверторы). Стандарт DOM. Язык написания
сценариев Java Script. Технология Ajax.

8. Форматы представления растровых и векторных данных
Принципы построения форматов хранения растровых данных. Основные
форматы для представления растровых изображений: BMP, GIF, JPEG, PNG, TIFF,
HDF. Сравнительный анализ следующих характеристик вышеприведенных форматов:
степень сжатия, потеря качества, область применения. Целесообразность
использования тех или иных форматов для предоставления доступа к растровым
данным в распределенных информационных системах.

Форматы для представления географически привязанных изображений.
Использование пирамиды разрешений для организации эффективного доступа.
Использование «мозаик» (разбиения изображения на фрагменты) для организации
доступа к географически привязанным данным. Использование форматов класса
GeoTIFF для организации доступа к географически привязанным изображениям.
Сравнение вышеперечисленных подходов.

Форматы представления векторных данных и графики: EPS, WMF, PDF, шейп-
файлы, SVG и др.

9. Стандарты Open Geospatial Consortium (OGC) для организации доступа к
пространственным данным.
Основные задачи OGC. OpenGIS стандарты: Web Map Service (WMS), Web
Coverage Service Interface Standard (WCS), Geography Markup Language
Encoding Standard (GML). Краткое описание назначения вышеперечисленных
стандартов.

Современные возможности построения распределенных геоинформационных
систем для сбора, представления и анализа информации. Архитектуры
построения распределенных систем представления пространственных данных на
примере MapServer. Стандарты OpenGIS.

Поддержка OpenGIS стандартов в различных СУБД, в частности в MySQL и
PostgreSQL.



10. Построение информационных систем спутникового
дистанционного зондирования
Основные задачи современных систем дистанционного зондирования.
Особенности построения современных систем дистанционного мониторинга, их
основные типы и особенности.
Основные задачи современных КА дистанционного мониторинга.
Системы низкого пространственного разрешения. Системы среднего
пространственного разрешения. Системы высокого пространственного
разрешения. Системы сверхвысокого пространственного разрешения.
Метеорологические системы. Природоресурсные системы (среднего и высокого
пространственно разрешения). Картографические системы сверх высокого
пространственного разрешения.
Комплексные экспериментальные системы ДЗЗ

Жизненный цикл данных ДЗЗ. (основные этапы обработки и использования
данных). Основные требования к системам обработки данных ДЗЗ. Основные
требования к информации, поступающей с КА ДЗЗ. Основные требования по
управлению КА ДЗЗ и целевой аппаратурой.

Основная литература
1. Введение в криптографию / Под ред. В.В. Ященко. СПб.: МЦНМО, 2001.
2. Дейт К.Дж. Введение в системы баз данных. М.: Вильямс, 1999.
3. Дейтел Г. Введение в операционные системы. М.: Мир, 1987.
4. Кнут Д. Искусство программирования. Т. 1 - 3. М., СПб., Киев: ИД
«Вильямс», 2000.
5. Когаловский М.Р. Энциклопедия технологий баз данных. М.: Финансы и
статистика, 2002.
6. Компьютерные сети. Учебный курс Microsoft Corporation, 1997.
7. Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы, построение и анализ.
М.: МЦНМО, 2000.
8. Котов В.Е., Сабельфельд В.К. Теория схем программ. М.: Наука, 1991.
9. Мельников В.В. Защита информации в компьютерных системах. М.: Финансы
и статистика, 1997.
10. Керниган Б., Пайк П. UNIX - универсальная среда программирования. М.:
Финансы и статистика, 1992.

Дополнительная литература
1. Корнеев В.В. Параллельные вычислительные системы. М.: Нолидж, 1999.
2. Павел Анни, Этот Grid - неспроста. // Открытые системы, 2003, ? 1.
3. Сайт ПО Globus Toolkit - http://www.globus.org
4. Сайт консорциума OGC - http://www.opengeospatial.org/
5. Сайт ПО Mapserver http://mapserver.org
6. Ефремов В.Ю., Лупян E.A., Мазуров A.A., Прошин А.А., Флитман Е.В.
Технология построения автоматизированных систем хранения спутниковых
данных // Современные проблемы дистанционного зондирования Земли из
космоса М.: Полиграф-сервис, 2004. Т.1, Вып. 1. с 437-443.
7. Ефремов В.Ю., Крашенинникова Ю.С., Лупян Е.А., Мазуров А.А., Прошин
А.А., Флитман Е.В. Оптимизированная система хранения и представления
географически привязанных спутниковых данных, // Современные проблемы
дистанционного зондирования Земли из космоса М.:ООО Азбука-2000,
2007. Т.4, ? 1.с. 125-134 с.
8. Современные проблемы дистанционного зондирования Земли из космоса.
(выпуски 1-5)
9. Чандра А. М., Гош С. К. Дистанционное зондирование и географические
информационные системы. М. Техносфера, 2008.
10. Шовенгердт Р.А. Дистанционное зондирование. Модели и методы обработки
космических снимков. М.: Техносфера, 2010.
11. Барский А.Б. Параллельные информационные технологии. М.: Изд-во
"Интернет-университет информационных технологий - ИНТУИТ.ру", "БИНОМ.
Лаборатория знаний", 2007.
12. Миано Дж . Форматы и алгоритмы сжатия изображений в действии М.: Изд-
во Триумф, 2003.
13. Шаши Шекхар, Санжей Чуала. Основы пространственных баз данных./Пер. с
англ. М.: КУДИЦ-ОБРАЗ 2004.
14. Лупян Е.А., Мазуров А.А., Назиров Р.Р. и др. Технология построения
автоматизированных информационных систем сбора, обработки, хранения и
распространения спутниковых данных для решения научных и прикладных
задач //Современные проблемы дистанционного зондирования Земли из
космоса: Физические основы, методы и технологии мониторинга окружающей
среды, потенциально опасных явлений и объектов. М.: Полиграф сервис,
2004. Т.1, Вып.1. с.81-88.


Составители:


д.т.н. Е.А.Лупян


к.т.н. А.А.Прошин