Дополнительная программа кандидатского экзамена по специальности 05.13.11

Программа кандидатского экзамена
по специальности 05.13.11
Математическое и программное обеспечение
вычислительных машин и систем
  1. Математические основы информатики и программирования
    1. Понятие алгоритма и его уточнения: машины Тьюринга, нормальные алгоритмы Маркова, рекурсивные функции. Понятие об алгоритмической неразрешимости. Примеры алгоритмически неразрешимых проблем.
    2. Понятие сложности алгоритмов. Классы P, NP. Теорема Кука об NP-полноте задачи выполнимости булевой формулы. Примеры NP-полных задач.
    3. Алгебра логики. Булевы функции, канонические формы задания булевых функций. Понятие полноты системы.
    4. Исчисление высказываний. Теорема о полноте исчисления высказываний.
    5. Исчисление предикатов 1-го порядка. Понятие интерпретации. Выполнимость и общезначимость формулы 1-го порядка. Понятие модели. Теорема о полноте исчисления предикатов 1-го порядка.
    6. Основные положения теории графов. Типы графов, способы задания графов. Изоморфизм, отображения. Критерий планарности. Виды и свойства бинарных деревьев. Перечисление бинарных деревьев. Алгоритмы обхода вершин графа. Алгоритмы разбиения графа на подграфы заданного типа.
    7. Основные понятия логического программирования. Теорема Эрбрана. Метод резолюций.
    8. Основные понятия общей алгебры: алгебра, подалгебра, гомоморфизм, конгруэнтность, факторалгебра. Алгебра термов.
    9. Понятие булевой алгебры. Примеры булевых алгебр (алгебра подмножеств, алгебры Линденбаума для теорий первого порядка).
    10. Основные понятия исчисления взаимодействующих систем Р.Милнера. Понятие процесса в CCS. Наблюдаемая конгруэнция на множестве CCS-процессов. Теорема о неподвижной точке. Взаимодействующие процессы Хоара, средства описания процессов, понятие спецификации процесса.
    11. Представление о сетях Петри для анализа свойств поведения параллельных программ (разметка, функционирование, развертка, граф достижимости).
  2. Элементы смежных областей
    1. Численные методы линейной алгебры. Основные алгоритмы и их сложность.
    2. Численные методы решения обыкновенных дифференциальных уравнений. Основные алгоритмы и их сложность.
    3. Численные методы интегрирования. Основные алгоритмы и их сложность.
    4. Понятие устойчивости разностных схем.
    5. Быстрое преобразование Фурье (БПФ) и его применение.
    6. Погрешность результата, неустранимая, относительная. Погрешность, вызываемая методами выполнения арифметических операций в ЭВМ. Ошибки округления. Накопление ошибок.
    7. Основные понятия линейного программирования. Алгоритм симплекс-метода решения задачи линейного программирования.
  3. Архитектура современных микропроцессоров и вычислительных систем
    1. Понятие архитектуры ЭВМ. Принципы организации машины фон Неймана. Основные компоненты традиционных ЭВМ. Узкие места компьютера.
    2. Организация памяти. Иерархия памяти. Банки памяти, interleaving. Виртуальная память. Страничная и сегментная организация памяти. Понятие виртуальной памяти. Cache память, ее назначение. Основной принцип организации Cache памяти, ее характеристики, алгоритмы доступа. Когерентность кэш-памяти.
    3. Процессор, состав и функционирование. Организация регистров. Командный конвейер. Причины приостановки конвейера (ветвление инструкций, зависимость по данным между инструкциями, конфликты по памяти и т.д.) и техника их преодоления (предсказание ветвлений, блок предварительной выборки, переименование регистров и т.д.). Арифметический конвейер. Представление данных. Основные арифметические операции. Устройство управления, его назначение.
    4. Устройства ввода/вывода. Понятие и характеристики шин. Шинный интерфейс
    5. Системы команд. Характеристики и функции. Способы адресации и форматы команд.
    6. RISC архитектура. Характеристики RISC архитектуры. Понятие регистрового окна.
    7. Введение в параллельную обработку. Понятие последовательного и параллельного исполнения. Уровни параллелизма. Классификация Флинна: SIMD и MIMD архитектуры. Уточненная классификация.
    8. Архитектуры микропроцессоров с параллелизмом на уровне команд (ILP-архитектуры). Примеры ILP-процессоров (Alpha 21264, R12000, Pentium 4, E2K, Itanuim). Суперскалярные процессоры. Архитектура команд с длинным машинным словом (VLIW). Архитектуры c явным параллелизмом (EPIC).
    9. Архитектуры микропроцессоров с параллелизмом на уровне данных. Классификация. Векторные процессоры. Векторизация вычислений. Примеры архитектур (Cray C90, Covex C4/XA, Fuijtsu VPP5000/31). Оценки производительности.
    10. Архитектуры микропроцессоров с параллелизмом на уровне процессов и тредов (thread). Классификация. Проблемы синхронизации и задержки памяти. Организация памяти. Гибридные мультитредовые архитектуры. Программное обеспечение. Примеры архитектур (Alpha 21464). Оценки производительности.
    11. SIMD-архитектуры. Пространственный и временной параллелизм. Векторно-конвейерные суперЭВМ. Матричные процессоры. Ассоциативные вычислители.
    12. Классификация MIMD архитектуры: мультипроцессорные системы с разделяемой (SMP), кластеры, архитектуры с массовым параллелизмом (MPP), архитектуры на базе векторно-конвейерных ЭВМ. Организация каждого класса (структура узла, сеть связи, поддержка когерентности кэш-памяти, масштабируемость, системы программирования). Характеристики производительности мультипроцессорных систем.
    13. Мультикомпьютеры и мультипроцессоры. Способы увеличения масштабируемости. Архитектуры UMA, NUMA, cc-NUMA, COMA. Примеры современных MIMD-компьютеров (Earth- Simulator, SP2, ASCI White, Cray T3E, AlphaServer, МВС 1000/М, ORIGIN). Тенденции развития параллельных компьютеров.
    14. Кластерные системы. Организация памяти. Структура узла. Сеть связи. Поддержка кэш-когерентности. Коммуникационные среды (SCI, Myrinet, Raceway, MC, Fast Ethernet). Сравнительный анализ коммуникационных сред. Программное обеспечение. Примеры современных кластеров (RM 600, кластер МВС-1000М). Оценки производительности.
    15. Принципы организации и функционирования потоковых вычислителей. Клеточные, нейронные и клеточно-нейронные вычисления.
    16. Методы организации сетей ЭВМ. Основные принципы их функционирования. Классификация сетей по масштабу и топологии.
    17. Понятие сетевого протокола. Семиуровневая модель OSI/ISO. Понятие стандарта.
    18. Сетевая архитектура TCP/IP: основные принципы организации и функционирования.
    19. Способы маршрутизации сообщений в сетях ЭВМ.
    20. Основные функции сервера в сети ЭВМ. Состав и структура его программного обеспечения.
    21. Основные принципы и средства управления сетью.
  4. Операционные системы
    1. Принципы организации функционирования ЭВМ на основе операционных систем. Схемы взаимосвязи пользователей и ЭВМ. Пакетный режим, режимы разделения времени и реального времени. Критерии производительности ОС.
    2. Основные функции ОС (организация исполнения программ, операции ввода/вывода, файловая система, обнаружение ошибок, распределение ресурсов, защита программ, системные вызовы)
    3. Общая структура операционной системы, ее основные компоненты. Управляющие, системные и пользовательские процессы. Синхронизация процессов в ЭВМ.
    4. Основные средства аппаратной поддержки функций ОС: система прерываний, защита памяти, механизм преобразования адресов в системах виртуальной памяти, управление каналами и периферийными устройствами.
    5. Управление памятью. Управление процессорами. Управление устройствами. Управление информацией. Команда обращения к супервизору. Обработка прерываний. Cистемные управляющие программы. Системные библиотеки.
    6. Управление потоками заданий в ЭВМ. Языковые средства пользователей ЭВМ. Обработка потоков заданий в ЭВМ. Входные и выходные очереди заданий. Понятие входных и выходных классов. Приоритеты заданий. Планирование заданий. Формирование входных очередей. Выборка заданий из очередей. Формирование выходных очередей. Алгоритмы планирования (первый вошел - первый обслужен, кратчайшее задание первым, приоритеты, многоуровневые очереди и другие).
    7. Супервизор, основные функции супервизора. Управляющие блоки и таблицы супервизора.
    8. Организация мультипрограммных процессов ЭВМ. Принципы мультипрограммной обработки данных. Создание процессов. Взаимодействие процессов. Критические участки. Средства синхронизации процессов. Семафорные операции.
    9. Организация последовательного использования ресурсов. Дедлоки, необходимые условия наличия дедлоков, способы борьбы с дедлоками. Алгоритм банкира. Спулинг (spooling).
    10. Управление оперативной памятью. Распределение оперативной памятью. Фрагментация памяти. Виртуальная память, типы виртуальной памяти. Структурное распределение. Сегментное распределение. Сегментно-страничное распределение памяти. Защита реальной и виртуальной памяти. Стратегия распределения памяти. Режимы виртуальной памяти.
    11. Обработка прерываний и управление ресурсами. Управляющие блоки и таблицы для управления процессами. Основные операции над процессами и ресурсами. Организация планировщиков процессов, синхронизация процессов. Методы планирования процессов. Программные средства комплексирования ЭВМ и мультипроцессорных систем.
    12. Управление информацией в ЭВМ. Файловые системы. Уровни управления наборами данных. Логический и физические уровни. Базисный уровень наборов данных. Методы доступа. Процедуры доступа к наборам данных. Файловые справочники. Управление доступом. Обеспечение независимости программ обработки от данных. Блоки управления данными. Процедуры открытия и закрытия наборов данных. Управление внешней пямятью.
    13. Синхронизация процессов ввода-вывода и обработки данных. Буферизация данных, spooling. Объединение буферов в пулы при вводе-выводе. Способы управления буферами. Режимы пересылки данных. Простая и обменная буферизация. Объединение записей в блоки. Физический уровень управления данными. Процедура запуска операций ввода-вывода. Функции супервизора ввода-вывода. Обработка прерываний ввода-вывода.
    14. Организация сетевого взаимодействия в современных ОС. Средства взаимодействия процессов. Модель клиент-сервер и ее реализация в современных ОС. Структура современных распределенных ОС.
  5. Модели, языки, системы и методы программирования
    1. Языки естественные и формальные. Грамматики языков, классификация по Хомскому. Регулярные выражения и их языки. Конечные автоматы, автоматы с магазинной памятью (МП). Детерминированные и недетерминированные конечные автоматы, их эквивалентность. Автоматные грамматики. Языки конечных автоматов и их свойства. Контекстно-свободные грамматики. Контекстно-свободные языки. Характеристика КС-языков в терминах МП-автоматов. Детерминированные КС-языки.
    2. Языки программирования. Синтаксис, семантика. Подходы к классификации языков (по уровню абстракции/непроцедурности, по классам применения, по классам пользователей). Общий обзор моделей и конструкций языков программирования Фортран, С, Модула 2, Пролог.
    3. Системы программирования, типовые компоненты СП: языки, трансляторы, редакторы связей, отладчики, текстовые редакторы. Понятие иерархии абстрактных машин.
    4. Модели вычислений и языки программирования. Процедурные и декларативные языки. Функциональные и логические языки.
    5. Основные концепции процедурно-ориентированных языков программирования. Методы процедурного программирования. Примеры.
    6. Основные концепции логического программирования. Методы составления программ и их исполнения в парадигме логического программирования.
    7. Основные концепции функционального программирования. Методы функционального программирования и их реализация. Примеры.
    8. Основные концепции объектно-ориентированного программирования. Организация выполнения объектно-ориентированных программ. Примеры объектно-ориентированных систем программирования.
    9. Общая структура языка программирования. Элементы языка программирования. Данные в языках программирования. Операторы в языках программирования. Выражения, функции, параметры. Управление последовательностью действий. Управление данными. Управление памятью.
    10. Язык ассемблера. Проектирование ассемблера. Одно- и многопроходные схемы трансляции. Макрогенераторы.
    11. Этапы трансляции: лексический, синтаксический, семантический анализ, оптимизация, генерация выходного текста, сборка.
    12. Распознаватели, восходящие и нисходящие алгоритмы, сравнительная характеристика. Проблемы нисходящего разбора и методы решения. Проблемы нисходящего разбора без возвратов. Простое и операторноe предшествование.
    13. Распределение памяти в создаваемой транслятором программе. Статическая и динамическая память. Организация памяти для простых переменных, массивов с переменными границами, для строчных переменных, для структур. Задача экономии памяти в компиляторах.
    14. Организация передачи параметров между программными модулями. Параметры, явные и неявные. Вызов по значению, по именования. Проблемы комплексирования разноязыковых модулей. Подключение среды, информационный интерфейс, организация управления. Организация компиляции, редактирования, загрузки, выполнения.
    15. Структуры данных и алгоритмы над структурами данных. Массивы, управление массивами, динамические массивы. Списки, обработки списков. Отношения и таблицы, обработка таблиц. Типы данных в языках программирования, абстрактные типы данных. Управление памятью в программах.
    16. Параллельное программирование. Понятие параллельной программы. Задача параллельного программирования. Параллельные языки программирования. Средства описания параллелизма в современных языках программирования. Процессы, прямое и потоковое управление, распределение ресурсов. Средства задания потокового и прямого управления. Динамические свойства параллельной программы (настраиваемость на доступные ресурсы, устойчивость к сбоям, динамическая балансировка загрузки). Асинхронные программы. Параллельное программирование с использованием системы коммуникационных процедур MPI.
  6. Методы хранения, организация и доступа к данным
    1. Концепция типа данных. Абстрактные типы данных. Объекты (основные свойства и отличительные черты).
    2. Основные структуры данных, алгоритмы обработки и поиска.
    3. Модели данных. Иерархическая, сетевая, реляционная, алгебра отношений. Примеры соответствующих СУБД.
    4. Информационно-поисковые системы. Классификация. Методы реализации и методы ускорения поиска.
    5. Базы данных. Основные понятия языков управления и манипулирования данными, Распределенные базы данных, активные базы данных, интегрированные базы данных.
    6. Понятие о базе знаний, их использование в экспертных системах и системах логического вывода. Способы представления знаний.
    7. Организация физического уровня баз данных. Методы индексирования и сжатия данных.
    8. Язык баз данных SQL. Средства управления и изменения схемы базы данных, определения ограничений целостности. Контроль доступа.
  7. Общие вопросы информатики и вычислительной техники
    1. Понятие о вычислительном эксперименте и его инструментальной поддержке.
    2. Проблемы защиты информации от несанкционированного доступа.
    3. Машинная графика. Средства поддержки машинной графики. Графические пакеты.
    4. Технология программирования. Жизненный цикл программы. Основные этапы. Инструментальные средства поддержки.
    5. Требования к программному продукту (надежность, переносимость, познаваемость, рациональная ресурсоемкость) и их влияние на системы программирования и технологии разработки программных систем.
    6. Методы спецификации программ. Методы проверки спецификации.
    7. Защита авторских прав разработчиков программ.

Список литературы

  1. Ахо А., Ульман Дж. Теория синтаксического анализа, перевода и компиляции. Т. 1,2. М. Мир. 1978.
  2. Барский А.Б. Параллельные процессы в вычислительных системах. Планирование и организация. - М.: Радио и связь, 1983.
  3. Бахвалов Н.С. Численные методы. М. Наука. 1975.
  4. Высокоскоростные вычисления. Под ред. Ковалика Я. - М.: Радио и связь, 1988.
  5. Головкин Б.А. Параллельные вычислительные системы. М.: Наука, 1980.
  6. Гэри, Джонсон. Вычислительные машины и труднорешаемые задачи. М. Мир. 1984.
  7. Девис У. Операционные системы: Функциональный подход. М. Мир. 1980.
  8. Корнеев В.В. Параллельные вычислительные системы. М.: Москва, 1999.
  9. Королев Л.Н. Структуры ЭВМ и их математическое обеспечение. М. Наука. 1980.
  10. Котов В.Е., Сабельфельд В.К. Теория схем программ. 1992.
  11. Мартин Дж. Организация баз данных в вычислительных системах. М. Мир. 1987.
  12. Мендельсон Э. Введение в математическую логику. М. Мир. 1985.
  13. Попов Ю.П., Самарский А.А. Вычислительный эксперимент. М. Знание. 1983.
  14. Пратт Т. Языки программирования. Разработка и реализация. М. Мир. 1979.
  15. Скорняков Л.А. Элементы общей алгебры. 1984.
  16. Современные высокопроизводительные компьютеры В. Шнитман, информационно-аналитические материалы Центра Информационных Технологий, 1996 год http://www.citforum.ru/win/hardware/svk/contents.shtml
  17. Современные микропроцессоры http://ssd.sscc.ru
  18. Уоркли Дж. Архитектура и программирование микро-ЭВМ. В двух томах. М. Мир. 1984.
  19. Фоли Дж., Вэн Дем А. Системы интерактивной графики. М. Мир. 1985.
  20. Хокни Р., Джесхоуп. Параллельные ЭВМ: Архитектура, программирование и алгоритмы. - М.: Радио и связь, 1986.
  21. Хоггер К, Введение в логическое программирование. М. Мир. 1988.
  22. Яблонский С.В. Введение в дискретную математику. М. Наука. 1979.
  23. Barker, V (Ed) 2000. Cluster Computing Whitepaper at http://www.dcs.port.ac.uk/mab/tfcc/WhitePaper/.
  24. Message-Passing Architectures. http://www2.lmn.pub.ro/pvmdoc/node60.html
  25. MP-MPICH (http://lfbs.rwth-aachen.de/-joachim/MP-MPICH/).
  26. SPEC CPU 2000: определение производительности в новом тысячелетии