Программа-минимум кандидатского экзамена по специальности 05.13.11 «Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей» по физико-математическим и техническим наукамСкачать документ
Введение
В основу настоящей программы положены следующие дисциплины: математические основы программирования; вычислительные машины, системы и сети; языки и системы программирования; технология разработки программного обеспечения; операционные системы; методы хранения и доступа к данным, организация баз данных и знаний; защита данных и программных систем.
Программа разработана экспертным советом Высшей аттестационной комиссии Министерства образования Российской Федерации по управлению, вычислительной технике и информатике при участии Московского государственного университета им. М.В. Ломоносова, Московского авиационного института (государственного технического университета), Московского государственного энергетического института (технического университета) и Института системного программирования РАН.
1. Математические основы программирования
- Понятие алгоритма и его уточнения: машины Тьюринга, нормальные алгоритмы Маркова, рекурсивные функции. Эквивалентность данных формальных моделей алгоритмов. Понятие об алгоритмической неразрешимости. Примеры алгоритмически неразрешимых проблем.
- Понятие сложности алгоритмов. Классы P и NP. Полиномиальная сводимость задач. Теорема Кука об NP-полноте задачи выполнимости булевой формулы. Примеры NP-полных задач, подходы к их решению. Точные и приближенные комбинаторные алгоритмы.
- Примеры эффективных (полиномиальных) алгоритмов: быстрые алгоритмы поиска и сортировки; полиномиальные алгоритмы для задач на графах и сетях (поиск в глубину и ширину, о минимальном остове, о кратчайшем пути, о назначениях).
- Автоматы. Эксперименты с автоматами. Алгебры регулярных выражений. Теорема Клини о регулярных языках.
- Алгебра логики. Булевы функции, канонические формы задания булевых функций. Понятие полной системы. Критерий полноты Поста. Минимизация булевых функций в классах нормальных форм.
- Исчисление предикатов первого порядка. Понятие интерпретации. Выполнимость и общезначимость формулы первого порядка. Понятие модели. Теорема о полноте исчисления предикатов первого порядка.
- Отношения и функции. Отношение эквивалентности и разбиения. Фактор множества. Отношения частичного порядка. Теоретико-множественное и алгебраическое определения решетки, их эквивалентность. Свойства решеток. Булевы решетки. Полные решетки.
- Формальные языки и способы их описания. Классификация формальных грамматик. Их использование в лексическом и синтаксическом анализе.
- ?-исчисление, правила редукции, единственность нормальной формы и правила ее достижения, представление рекурсивных функций.
- Основы комбинаторного анализа. Метод производящих функций, метод включений и исключений. Примеры применения.
- Коды с исправлением ошибок. Алфавитное кодирование. Методы сжатия информации.
- Основы криптографии. Задачи обеспечения конфиденциальности и целостности информации. Теоретико-информационный и теоретико-сложностный подходы к определению криптографической стойкости. Американский стандарт шифрования DES и российский стандарт шифрования данных ГОСТ 28147-89. Системы шифрования с открытым ключом (RSA). Цифровая подпись. Методы генерации и распределения ключей.
2. Вычислительные машины, системы и сети
- Архитектура современных компьютеров. Организации памяти и архитектура процессора современных вычислительных машин. Страничная и сегментная организация виртуальной памяти. Кэш-память. Командный и арифметический конвейеры, параллельное выполнение независимых команд, векторные команды. Специализированные процессоры. Машины, обеспечивающие выполнение вычислений, управляемых потоком данных. Организация ввода-вывода, каналы и процессоры ввода-вывода, устройства сопряжения с объектами.
- Классификация вычислительных систем (ВС) по способу организации параллельной обработки. Многопроцессорные и многомашинные комплексы. Вычислительные кластеры. Проблемно-ориентированные параллельные структуры: матричные ВС, систолические структуры, нейросети.
- Назначение, архитектура и принципы построения информационно - вычислительных сетей (ИВС). Локальные и глобальные ИВС, технические и программные средства объединения различных сетей.
- Методы и средства передачи данных в ИВС, протоколы передачи данных.
- Особенности архитектуры локальных сетей (Ethernet, Token Ring, FDDI).
- Сеть Internet, доменная организация, семейство протоколов TCP/IP. Информационно-вычислительные сети и распределенная обработка информации.
3. Языки и системы программирования. Технология разработки программного обеспечения
- Языки программирования. Процедурные языки программирования (Фортран, Си), Функциональные языки программирования (Лисп), логическое программирование (Пролог), объектно-ориентированные языки программирования (Ява).
- Процедурные языки программирования. Основные управляющие конструкции, структура программы. Работа с данными: переменные и константы, типы данных (булевский, целочисленные, плавающие, символьные, типы диапазона и перечисления, указатели), структуры данных (массивы и записи). Процедуры (функции): вызов процедур, передача параметров (по ссылке, по значению, по результату), локализация переменных, побочные эффекты. Обработка исключительных ситуаций. Библиотеки процедур и их использование.
- Объектно-ориентированное программирование. Классы и объекты, наследование, интерфейсы. Понятие об объектном окружении. Рефлексия. Библиотеки классов. Средства обработки объектов (контейнеры и итераторы).
- Распределенное программирование. Процессы и их синхронизация. Семафоры, мониторы Хоара. Объектно-ориентированное распределенное программирование. CORBA. Параллельное программирование над общей памятью. Нити. Стандартный интерфейс Open MP. Распараллеливание последовательных программ. Параллельное программирование над распределенной памятью. Парадигмы SPMD и MIMD. Стандартный интерфейс MPI.
- Основы построения трансляторов. Структура оптимизирующего транслятора. Промежуточные представления программы: последовательность символов, последовательность лексем, синтаксическое дерево, абстрактное синтаксическое дерево. Уровни промежуточного представления: высокий, средний, низкий. Формы промежуточного представления.
- Анализ исходной программы в компиляторе. Автоматные (регулярные) грамматики и сканирование, контекстно свободные грамматики и синтаксический анализ, организация таблицы символов программы, имеющей блочную структуру, хеш-функции. Нисходящие (LL(1)-грамматики) и восходящие (LR(1)-грамматики) методы синтаксического анализа. Атрибутные грамматики и семантические программы, построение абстрактного синтаксического дерева. Автоматическое построение лексических и синтаксических анализаторов по формальным описаниям грамматик. Системы lex и yacc. Система Gentle.
- Оптимизация программ при их компиляции. Оптимизация базовых блоков, чистка циклов. Анализ графов потока управления и потока данных. Отношение доминирования и его свойства, построение границы области доминирования вершины, выделение сильно связанных компонент графа. Построение графа зависимостей. Перевод программы в SSA-представление и обратно. Глобальная и межпроцедурная оптимизация.
- Генерация объектного кода в компиляторах. Перенастраиваемые (retargetable) компиляторы, gcc (набор компиляторов Gnu). Переработка термов (term rewriting). Применение оптимизационных эвристик (целочисленное программирование, динамическое программирование) для автоматической генерации генераторов объектного кода (системы BEG, Iburg и др.).
- Машинно-ориентированные языки, язык ассемблера. Представление машинных команд и констант. Команды транслятору. Их типы, принципы реализации. Макросредства, макровызовы, языки макроопределений, условная макрогенерация, принципы реализации.
- Системы программирования (СП), типовые компоненты СП: языки, трансляторы, редакторы связей, отладчики, текстовые редакторы. Модульное программирование. Типы модулей. Связывание модулей по управлению и данным.
- Пакеты прикладных программ (ППП). Системная часть и наполнение. Языки общения с ППП. Машинная графика. Средства поддержки машинной графики. Графические пакеты.
- Технология разработки и сопровождения программ. Жизненный цикл программы. Этапы разработки, степень и пути их автоматизации. Обратная инженерия. Декомпозиционные и сборочные технологии, механизмы наследования, инкапсуляции, задания типов. Модули, взаимодействие между модулями, иерархические структуры программ.
- Отладка, тестирование, верификация и оценивание сложности программ. Генерация тестов. Системы генерации тестов. Срезы программ (slice, chop) и их применение при отладке программ и для генерации тестов.
- Методы спецификации программ. Методы проверки спецификации. Схемное, структурное, визуальное программирование. Разработка пользовательского интерфейса, стандарт CUA, мультимедийные среды интерфейсного взаимодействия.
4. Операционные системы
- Режимы функционирования вычислительных систем, структура и функции операционных систем. Основные блоки и модули. Основные средства аппаратной поддержки функций операционных систем (ОС): система прерываний, защита памяти, механизмы преобразования адресов в системах виртуальной памяти, управление каналами и периферийными устройствами.
- Виды процессов и управления ими в современных ОС. Представление процессов, их контексты, иерархии порождения, состояния и взаимодействие. Многозадачный (многопрограммный) режим работы. Команды управления процессами. Средства взаимодействия процессов. Модель клиент-сервер и ее реализация в современных ОС.
- Параллельные процессы, схемы порождения и управления. Организация взаимодействия между параллельными и асинхронными процессами: обмен сообщениями, организация почтовых ящиков. Критические участки, примитивы взаимоисключения процессов, семафоры Дейкстры и их расширения. Проблема тупиков при асинхронном выполнении процессов, алгоритмы обнаружения и предотвращения тупиков.
- Операционные средства управления процессами при их реализации на параллельных и распределенных вычислительных системах и сетях: стандарты и программные средства PVM, MPI, OpenMP, POSIX .
- Одноуровневые и многоуровневые дисциплины циклического обслуживания процессов на центральном процессоре, выбор кванта.
- Управление доступом к данным. Файловая система, организация, распределение дисковой памяти. Управление обменом данными между дисковой и оперативной памятью. Рабочее множество страниц (сегментов) программы, алгоритмы его определения.
- Управление внешними устройствами.
- Оптимизация многозадачной работы компьютеров. Операционные системы 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. Защита данных и программных систем
- Аппаратные и программные методы защиты данных и программ. Защита данных и программ с помощью шифрования.
- Защита от несанкционированного доступа в OC Windows NT. Система безопасности и разграничения доступа к ресурсам в Windows NT. Файловая система NTFS и сервисы Windows NT.
- Защита от несанкционированного копирования. Методы простановки некопируемых меток, настройка устанавливаемой программы на конкретный компьютер, настройка на конфигурацию оборудования.
- Защита от разрушающих программных воздействий. Вредоносные программы и их классификация. Загрузочные и файловые вирусы, программы-закладки. Методы обнаружения и удаления вирусов, восстановления программного обеспечения.
- Защита информации в вычислительных сетях Novell Netware, Windows NT и др.
Основная литература
- Ахо, Сети Р., Ульман Дж. Компиляторы: принципы, техника реализации и инструменты. М., 2001.
- Введение в криптографию / Под ред. В.В. Ященко. СПб.: МЦНМО, 2001.
- Дейт К.Дж. Введение в системы баз данных. М.: Вильямс, 1999.
- Дейтел Г. Введение в операционные системы. М.: Мир, 1987.
- Кнут Д. Искусство программирования. Т. 1 - 3. М., СПб., Киев: ИД <Вильямс>, 2000.
- Когаловский М.Р. Энциклопедия технологий баз данных. М.: Финансы и статистика, 2002.
- Компьютерные сети. Учебный курс Microsoft Corporation, 1997.
- Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы, построение и анализ. М.: МЦНМО, 2000.
- Котов В.Е., Сабельфельд В.К. Теория схем программ. М.: Наука, 1991.
- Матфик С. Механизмы защиты в сетях ЭВМ. М.: Мир, 1993.
- Мельников В.В. Защита информации в компьютерных системах. М.: Финансы и статистика, 1997.
- Яблонский С.В. Введение в дискретную математику. М.: Наука, 2001.
Дополнительная литература
- Керниган Б., Пайк П. UNIX - универсальная среда программирования. М.: Финансы и статистика, 1992.
- Корнеев В.В. Параллельные вычислительные системы. М.: Нолидж, 1999.
- Королёв Л.Н. Структуры ЭВМ и их математическое обеспечение. М.: Наука, 1980.
- Соломон Д., Руссинович М. Внутреннее устройство Microsoft Windows 2000. СПб.: Питер, 2001.
|
