Дополнительная программа кандидатского экзамена по специальности 05.13.11
по специальности 05.13.11
Математическое и программное обеспечение
вычислительных машин и систем
- Математические основы информатики и программирования
- Понятие алгоритма и его уточнения: машины Тьюринга, нормальные алгоритмы Маркова, рекурсивные функции. Понятие об алгоритмической неразрешимости. Примеры алгоритмически неразрешимых проблем.
- Понятие сложности алгоритмов. Классы P, NP. Теорема Кука об NP-полноте задачи выполнимости булевой формулы. Примеры NP-полных задач.
- Алгебра логики. Булевы функции, канонические формы задания булевых функций. Понятие полноты системы.
- Исчисление высказываний. Теорема о полноте исчисления высказываний.
- Исчисление предикатов 1-го порядка. Понятие интерпретации. Выполнимость и общезначимость формулы 1-го порядка. Понятие модели. Теорема о полноте исчисления предикатов 1-го порядка.
- Основные положения теории графов. Типы графов, способы задания графов. Изоморфизм, отображения. Критерий планарности. Виды и свойства бинарных деревьев. Перечисление бинарных деревьев. Алгоритмы обхода вершин графа. Алгоритмы разбиения графа на подграфы заданного типа.
- Основные понятия логического программирования. Теорема Эрбрана. Метод резолюций.
- Основные понятия общей алгебры: алгебра, подалгебра, гомоморфизм, конгруэнтность, факторалгебра. Алгебра термов.
- Понятие булевой алгебры. Примеры булевых алгебр (алгебра подмножеств, алгебры Линденбаума для теорий первого порядка).
- Основные понятия исчисления взаимодействующих систем Р.Милнера. Понятие процесса в CCS. Наблюдаемая конгруэнция на множестве CCS-процессов. Теорема о неподвижной точке. Взаимодействующие процессы Хоара, средства описания процессов, понятие спецификации процесса.
- Представление о сетях Петри для анализа свойств поведения параллельных программ (разметка, функционирование, развертка, граф достижимости).
- Элементы смежных областей
- Численные методы линейной алгебры. Основные алгоритмы и их сложность.
- Численные методы решения обыкновенных дифференциальных уравнений. Основные алгоритмы и их сложность.
- Численные методы интегрирования. Основные алгоритмы и их сложность.
- Понятие устойчивости разностных схем.
- Быстрое преобразование Фурье (БПФ) и его применение.
- Погрешность результата, неустранимая, относительная. Погрешность, вызываемая методами выполнения арифметических операций в ЭВМ. Ошибки округления. Накопление ошибок.
- Основные понятия линейного программирования. Алгоритм симплекс-метода решения задачи линейного программирования.
- Архитектура современных микропроцессоров и вычислительных систем
- Понятие архитектуры ЭВМ. Принципы организации машины фон Неймана. Основные компоненты традиционных ЭВМ. Узкие места компьютера.
- Организация памяти. Иерархия памяти. Банки памяти, interleaving. Виртуальная память. Страничная и сегментная организация памяти. Понятие виртуальной памяти. Cache память, ее назначение. Основной принцип организации Cache памяти, ее характеристики, алгоритмы доступа. Когерентность кэш-памяти.
- Процессор, состав и функционирование. Организация регистров. Командный конвейер. Причины приостановки конвейера (ветвление инструкций, зависимость по данным между инструкциями, конфликты по памяти и т.д.) и техника их преодоления (предсказание ветвлений, блок предварительной выборки, переименование регистров и т.д.). Арифметический конвейер. Представление данных. Основные арифметические операции. Устройство управления, его назначение.
- Устройства ввода/вывода. Понятие и характеристики шин. Шинный интерфейс
- Системы команд. Характеристики и функции. Способы адресации и форматы команд.
- RISC архитектура. Характеристики RISC архитектуры. Понятие регистрового окна.
- Введение в параллельную обработку. Понятие последовательного и параллельного исполнения. Уровни параллелизма. Классификация Флинна: SIMD и MIMD архитектуры. Уточненная классификация.
- Архитектуры микропроцессоров с параллелизмом на уровне команд (ILP-архитектуры). Примеры ILP-процессоров (Alpha 21264, R12000, Pentium 4, E2K, Itanuim). Суперскалярные процессоры. Архитектура команд с длинным машинным словом (VLIW). Архитектуры c явным параллелизмом (EPIC).
- Архитектуры микропроцессоров с параллелизмом на уровне данных. Классификация. Векторные процессоры. Векторизация вычислений. Примеры архитектур (Cray C90, Covex C4/XA, Fuijtsu VPP5000/31). Оценки производительности.
- Архитектуры микропроцессоров с параллелизмом на уровне процессов и тредов (thread). Классификация. Проблемы синхронизации и задержки памяти. Организация памяти. Гибридные мультитредовые архитектуры. Программное обеспечение. Примеры архитектур (Alpha 21464). Оценки производительности.
- SIMD-архитектуры. Пространственный и временной параллелизм. Векторно-конвейерные суперЭВМ. Матричные процессоры. Ассоциативные вычислители.
- Классификация MIMD архитектуры: мультипроцессорные системы с разделяемой (SMP), кластеры, архитектуры с массовым параллелизмом (MPP), архитектуры на базе векторно-конвейерных ЭВМ. Организация каждого класса (структура узла, сеть связи, поддержка когерентности кэш-памяти, масштабируемость, системы программирования). Характеристики производительности мультипроцессорных систем.
- Мультикомпьютеры и мультипроцессоры. Способы увеличения масштабируемости. Архитектуры UMA, NUMA, cc-NUMA, COMA. Примеры современных MIMD-компьютеров (Earth- Simulator, SP2, ASCI White, Cray T3E, AlphaServer, МВС 1000/М, ORIGIN). Тенденции развития параллельных компьютеров.
- Кластерные системы. Организация памяти. Структура узла. Сеть связи. Поддержка кэш-когерентности. Коммуникационные среды (SCI, Myrinet, Raceway, MC, Fast Ethernet). Сравнительный анализ коммуникационных сред. Программное обеспечение. Примеры современных кластеров (RM 600, кластер МВС-1000М). Оценки производительности.
- Принципы организации и функционирования потоковых вычислителей. Клеточные, нейронные и клеточно-нейронные вычисления.
- Методы организации сетей ЭВМ. Основные принципы их функционирования. Классификация сетей по масштабу и топологии.
- Понятие сетевого протокола. Семиуровневая модель OSI/ISO. Понятие стандарта.
- Сетевая архитектура TCP/IP: основные принципы организации и функционирования.
- Способы маршрутизации сообщений в сетях ЭВМ.
- Основные функции сервера в сети ЭВМ. Состав и структура его программного обеспечения.
- Основные принципы и средства управления сетью.
- Операционные системы
- Принципы организации функционирования ЭВМ на основе операционных систем. Схемы взаимосвязи пользователей и ЭВМ. Пакетный режим, режимы разделения времени и реального времени. Критерии производительности ОС.
- Основные функции ОС (организация исполнения программ, операции ввода/вывода, файловая система, обнаружение ошибок, распределение ресурсов, защита программ, системные вызовы)
- Общая структура операционной системы, ее основные компоненты. Управляющие, системные и пользовательские процессы. Синхронизация процессов в ЭВМ.
- Основные средства аппаратной поддержки функций ОС: система прерываний, защита памяти, механизм преобразования адресов в системах виртуальной памяти, управление каналами и периферийными устройствами.
- Управление памятью. Управление процессорами. Управление устройствами. Управление информацией. Команда обращения к супервизору. Обработка прерываний. Cистемные управляющие программы. Системные библиотеки.
- Управление потоками заданий в ЭВМ. Языковые средства пользователей ЭВМ. Обработка потоков заданий в ЭВМ. Входные и выходные очереди заданий. Понятие входных и выходных классов. Приоритеты заданий. Планирование заданий. Формирование входных очередей. Выборка заданий из очередей. Формирование выходных очередей. Алгоритмы планирования (первый вошел - первый обслужен, кратчайшее задание первым, приоритеты, многоуровневые очереди и другие).
- Супервизор, основные функции супервизора. Управляющие блоки и таблицы супервизора.
- Организация мультипрограммных процессов ЭВМ. Принципы мультипрограммной обработки данных. Создание процессов. Взаимодействие процессов. Критические участки. Средства синхронизации процессов. Семафорные операции.
- Организация последовательного использования ресурсов. Дедлоки, необходимые условия наличия дедлоков, способы борьбы с дедлоками. Алгоритм банкира. Спулинг (spooling).
- Управление оперативной памятью. Распределение оперативной памятью. Фрагментация памяти. Виртуальная память, типы виртуальной памяти. Структурное распределение. Сегментное распределение. Сегментно-страничное распределение памяти. Защита реальной и виртуальной памяти. Стратегия распределения памяти. Режимы виртуальной памяти.
- Обработка прерываний и управление ресурсами. Управляющие блоки и таблицы для управления процессами. Основные операции над процессами и ресурсами. Организация планировщиков процессов, синхронизация процессов. Методы планирования процессов. Программные средства комплексирования ЭВМ и мультипроцессорных систем.
- Управление информацией в ЭВМ. Файловые системы. Уровни управления наборами данных. Логический и физические уровни. Базисный уровень наборов данных. Методы доступа. Процедуры доступа к наборам данных. Файловые справочники. Управление доступом. Обеспечение независимости программ обработки от данных. Блоки управления данными. Процедуры открытия и закрытия наборов данных. Управление внешней пямятью.
- Синхронизация процессов ввода-вывода и обработки данных. Буферизация данных, spooling. Объединение буферов в пулы при вводе-выводе. Способы управления буферами. Режимы пересылки данных. Простая и обменная буферизация. Объединение записей в блоки. Физический уровень управления данными. Процедура запуска операций ввода-вывода. Функции супервизора ввода-вывода. Обработка прерываний ввода-вывода.
- Организация сетевого взаимодействия в современных ОС. Средства взаимодействия процессов. Модель клиент-сервер и ее реализация в современных ОС. Структура современных распределенных ОС.
- Модели, языки, системы и методы программирования
- Языки естественные и формальные. Грамматики языков, классификация по Хомскому. Регулярные выражения и их языки. Конечные автоматы, автоматы с магазинной памятью (МП). Детерминированные и недетерминированные конечные автоматы, их эквивалентность. Автоматные грамматики. Языки конечных автоматов и их свойства. Контекстно-свободные грамматики. Контекстно-свободные языки. Характеристика КС-языков в терминах МП-автоматов. Детерминированные КС-языки.
- Языки программирования. Синтаксис, семантика. Подходы к классификации языков (по уровню абстракции/непроцедурности, по классам применения, по классам пользователей). Общий обзор моделей и конструкций языков программирования Фортран, С, Модула 2, Пролог.
- Системы программирования, типовые компоненты СП: языки, трансляторы, редакторы связей, отладчики, текстовые редакторы. Понятие иерархии абстрактных машин.
- Модели вычислений и языки программирования. Процедурные и декларативные языки. Функциональные и логические языки.
- Основные концепции процедурно-ориентированных языков программирования. Методы процедурного программирования. Примеры.
- Основные концепции логического программирования. Методы составления программ и их исполнения в парадигме логического программирования.
- Основные концепции функционального программирования. Методы функционального программирования и их реализация. Примеры.
- Основные концепции объектно-ориентированного программирования. Организация выполнения объектно-ориентированных программ. Примеры объектно-ориентированных систем программирования.
- Общая структура языка программирования. Элементы языка программирования. Данные в языках программирования. Операторы в языках программирования. Выражения, функции, параметры. Управление последовательностью действий. Управление данными. Управление памятью.
- Язык ассемблера. Проектирование ассемблера. Одно- и многопроходные схемы трансляции. Макрогенераторы.
- Этапы трансляции: лексический, синтаксический, семантический анализ, оптимизация, генерация выходного текста, сборка.
- Распознаватели, восходящие и нисходящие алгоритмы, сравнительная характеристика. Проблемы нисходящего разбора и методы решения. Проблемы нисходящего разбора без возвратов. Простое и операторноe предшествование.
- Распределение памяти в создаваемой транслятором программе. Статическая и динамическая память. Организация памяти для простых переменных, массивов с переменными границами, для строчных переменных, для структур. Задача экономии памяти в компиляторах.
- Организация передачи параметров между программными модулями. Параметры, явные и неявные. Вызов по значению, по именования. Проблемы комплексирования разноязыковых модулей. Подключение среды, информационный интерфейс, организация управления. Организация компиляции, редактирования, загрузки, выполнения.
- Структуры данных и алгоритмы над структурами данных. Массивы, управление массивами, динамические массивы. Списки, обработки списков. Отношения и таблицы, обработка таблиц. Типы данных в языках программирования, абстрактные типы данных. Управление памятью в программах.
- Параллельное программирование. Понятие параллельной программы. Задача параллельного программирования. Параллельные языки программирования. Средства описания параллелизма в современных языках программирования. Процессы, прямое и потоковое управление, распределение ресурсов. Средства задания потокового и прямого управления. Динамические свойства параллельной программы (настраиваемость на доступные ресурсы, устойчивость к сбоям, динамическая балансировка загрузки). Асинхронные программы. Параллельное программирование с использованием системы коммуникационных процедур MPI.
- Методы хранения, организация и доступа к данным
- Концепция типа данных. Абстрактные типы данных. Объекты (основные свойства и отличительные черты).
- Основные структуры данных, алгоритмы обработки и поиска.
- Модели данных. Иерархическая, сетевая, реляционная, алгебра отношений. Примеры соответствующих СУБД.
- Информационно-поисковые системы. Классификация. Методы реализации и методы ускорения поиска.
- Базы данных. Основные понятия языков управления и манипулирования данными, Распределенные базы данных, активные базы данных, интегрированные базы данных.
- Понятие о базе знаний, их использование в экспертных системах и системах логического вывода. Способы представления знаний.
- Организация физического уровня баз данных. Методы индексирования и сжатия данных.
- Язык баз данных SQL. Средства управления и изменения схемы базы данных, определения ограничений целостности. Контроль доступа.
- Общие вопросы информатики и вычислительной техники
- Понятие о вычислительном эксперименте и его инструментальной поддержке.
- Проблемы защиты информации от несанкционированного доступа.
- Машинная графика. Средства поддержки машинной графики. Графические пакеты.
- Технология программирования. Жизненный цикл программы. Основные этапы. Инструментальные средства поддержки.
- Требования к программному продукту (надежность, переносимость, познаваемость, рациональная ресурсоемкость) и их влияние на системы программирования и технологии разработки программных систем.
- Методы спецификации программ. Методы проверки спецификации.
- Защита авторских прав разработчиков программ.
Список литературы
- Ахо А., Ульман Дж. Теория синтаксического анализа, перевода и компиляции. Т. 1,2. М. Мир. 1978.
- Барский А.Б. Параллельные процессы в вычислительных системах. Планирование и организация. - М.: Радио и связь, 1983.
- Бахвалов Н.С. Численные методы. М. Наука. 1975.
- Высокоскоростные вычисления. Под ред. Ковалика Я. - М.: Радио и связь, 1988.
- Головкин Б.А. Параллельные вычислительные системы. М.: Наука, 1980.
- Гэри, Джонсон. Вычислительные машины и труднорешаемые задачи. М. Мир. 1984.
- Девис У. Операционные системы: Функциональный подход. М. Мир. 1980.
- Корнеев В.В. Параллельные вычислительные системы. М.: Москва, 1999.
- Королев Л.Н. Структуры ЭВМ и их математическое обеспечение. М. Наука. 1980.
- Котов В.Е., Сабельфельд В.К. Теория схем программ. 1992.
- Мартин Дж. Организация баз данных в вычислительных системах. М. Мир. 1987.
- Мендельсон Э. Введение в математическую логику. М. Мир. 1985.
- Попов Ю.П., Самарский А.А. Вычислительный эксперимент. М. Знание. 1983.
- Пратт Т. Языки программирования. Разработка и реализация. М. Мир. 1979.
- Скорняков Л.А. Элементы общей алгебры. 1984.
- Современные высокопроизводительные компьютеры В. Шнитман, информационно-аналитические материалы Центра Информационных Технологий, 1996 год http://www.citforum.ru/win/hardware/svk/contents.shtml
- Современные микропроцессоры http://ssd.sscc.ru
- Уоркли Дж. Архитектура и программирование микро-ЭВМ. В двух томах. М. Мир. 1984.
- Фоли Дж., Вэн Дем А. Системы интерактивной графики. М. Мир. 1985.
- Хокни Р., Джесхоуп. Параллельные ЭВМ: Архитектура, программирование и алгоритмы. - М.: Радио и связь, 1986.
- Хоггер К, Введение в логическое программирование. М. Мир. 1988.
- Яблонский С.В. Введение в дискретную математику. М. Наука. 1979.
- Barker, V (Ed) 2000. Cluster Computing Whitepaper at http://www.dcs.port.ac.uk/mab/tfcc/WhitePaper/.
- Message-Passing Architectures. http://www2.lmn.pub.ro/pvmdoc/node60.html
- MP-MPICH (http://lfbs.rwth-aachen.de/-joachim/MP-MPICH/).
- SPEC CPU 2000: определение производительности в новом тысячелетии