Программа вступительных экзаменов в аспирантуру ИДСТУ СО РАН

по специальности 05.13.11 «Математическое и программное обеспечение

вычислительных машин, комплексов и компьютерных сетей»

Введение в теорию алгоритмов

Интуитивное понятие алгоритма. Свойства алгоритмов. Понятие об исполнителе алгоритма.

Уточнение понятия алгоритма. Алгоритм как преобразование слов из заданного алфавита. Машина Тьюринга. Тезис Тьюринга и его обоснование. Нормальные алгоритмы Маркова. Принцип нормализации и его обоснование. Понятие об алгоритмической неразрешимости.

Рекурсивные алгоритмы Понятие и применение рекурсивных алгоритмов при решении задач. Связь с математической индукцией; сравнение рекурсивных и итеративных алгоритмов. Анализ сложности алгоритмов. Понятие вычислительной сложности (по времени и памяти) и его применение для анализа алгоритмов.

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

Классы сложности Обзор классов сложности (Р и NP), верхние, средние и нижние оценки.

Р и NP-классы сложности; разрешимые и неразрешимые задачи.

NP-полнота.

Сортировка и поиск 0(n2)-алгоритмы сортировки (например, выбором и вставкой); оценки сложности, лучшие и худшие случаи.

0(n*log n)-алгоритмы сортировки (например, быстрая сортировка, метод слияния);

оценки сложности; другие методы сортировки (метод Шелла и т.д.); сравнение алгоритмов сортировки.

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

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

Архитектура ЭВМ Типовая схема ЭВМ, принципы Фон-Неймана. Оперативная память: ячейка, адрес, бит, слово. Характеристики и единицы измерения памяти. Команды и данные. Центральный процессор ЭВМ: устройство управления и арифметико-логическое устройство. Регистры. Устройство ввода/вывода.

Адресность ЭВМ, схема выполнения команд. Понятие такта работы.

Понятие о структурных особенностях современных ЭВМ: прерывания, защита памяти, привилегированные команды, параллельная обработка данных.

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

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

Список литературы 1. Любимский Э.З., Мартынюк В.В., Трифонов Н.П. Программирование. – Наука, 1980.

2. Вирт Н. Алгоритмы + структура данных = программа. – Мир, 1985.

3. Ларионов A.M., Майоров С.А., Новиков Г.И. Вычислительные комплексы, системы, сети.

– Л.: Энергоатомиздат, 1987.

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

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

6. Воеводин В.В. Математические модели и методы в параллельных процессах. – М.: Наука, 1986.

7. Хоггер К. Введение в логическое программирование. – М.: Мир, 1988.

8. Алексеев В.Б., Ложкин С.А. (составители). Элементы теории графов и схем: Методическое пособие. – М.: МГУ, 1991.

9. Мендельсон Э. Введение в математическую логику. – М.: Мир, 1985.

10. Трахтенгерц Э.А. Введение в теорию анализа и распараллеливания программ ЭВМ. – М.:

Наука, 1981.

11. Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. – М.: Мир, 1982.

12. Голдблатт Р. Логика времени и вычислимость. – М.: Мир, 1993.

13. Котов В.Е., Сабельфельд В.К. Теория схем программ. – М.: Наука, 1991.

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

Технология программирования.

Данные и типы Классификация данных. Динамические и статические ЯП. Атрибуты данных и средства их описания. Характеристики, связанные с типом (класс значений, множество операций).

Именная и структурная эквивалентность типов.

Базисные типы данных в традиционных ЯП.

Операторный базис традиционных ЯП. Средства определения подпрограмм. Правила передачи параметров. Процедурные абстракции и надежность.

Понятие модуля. Примеры в конкретных языках. Инкапсуляция. Абстрактные типы данных. Имя в ЯП. Описания и области действия. Правила видимости.

Перекрытие имен и видимость. Раздельная трансляция. Недостатки независимой трансляции.

Проблемы, связанные с параметризацией типов.

Понятие исключительной ситуации (ИС). Принципы надежной обработки ИС.

Управление представлением и учет машинно-зависимых особенностей.

Объектно-ориентированные ЯП Понятие объектно-ориентированного анализа. Классы и объекты. Основные отношения между классами и объектами. Связь объектного подхода с основными понятиями языков программирования. Недостатки традиционных ЯП с точки зрения объектного подхода.

Наследование в ЯП. Понятия и примеры наследования. Наследование и полиморфизм.

Надежность и повторное использование программных компонент.

Объявление классов и объектов. Конструкторы и деструкторы. Производные классы.

Виртуальные функции-члены. Абстрактные классы и методы. Множественное наследование.

Управление доступом. Инкапсуляция. Исключения и классы.

Статическое, квазистатическое и динамическое связывание методов. Примеры объектно-ориентированных языков.

Другие парадигмы программирования: функциональное и логическое программирование.

Методы трансляции ВВЕДЕНИЕ. Место компилятора в программном обеспечении. Структура компилятора.

ЛЕКСИЧЕСКИЙ АНАЛИЗ. Регулярные множества и регулярные выражения. Конечные автоматы. Построение детерминированного конечного автомата по регулярному выражению. Построение детерминированного конечного автомата с минимальным числом состояний. Программирование лексических анализаторов.

СИНТАКСИЧЕСКИЙ АНАЛИЗ. Основные понятия и определения. Табличноуправляемый предсказывающий разбор. Алгоритм разбора сверху-вниз, LL(1)-грамматики, рекурсивный спуск, восстановление после синтаксических ошибок. Синтаксически управляемая трансляция.

ПРОМЕЖУТОЧНОЕ ПРЕДСТАВЛЕНИЕ ПРОГРАММЫ. Представление в виде ориентированного графа. Организация информации в генераторе кода. Уровень промежуточного представления.

КОНТЕКСТНЫЕ УСЛОВИЯ ЯЗЫКОВ ПРОГРАММИРОВАНИЯ. Описание областей видимости и блочной структуры. Управление данными и контроль типов.

ОРГАНИЗАЦИЯ ТАБЛИЦ КОМПИЛЯТОРА. Таблицы идентификаторов и таблицы символов. Применение таблиц расстановки. Функции расстановки. Реализация блочной структуры.

ГЕНЕРАЦИЯ КОДА. Модель машины. Динамическая организация памяти. Назначение адресов. Трансляция переменных. Трансляция арифметических выражений. Распределение регистров при вычислении арифметических выражений. Особенности трансляции логических выражений. Выделение общих подвыражений. Оптимизация кода.

Список литературы 1. Грис Д. Построение компиляторов для цифровых вычислительных машин. – М.: Мир, 2. Ахо А., Ульман Д. Теория синтаксического анализа, перевода и компиляции. – М.: Мир, 3. Кнут Д. Искусство программирования для ЭВМ. T. I: Основные алгоритмы. – М.: Мир, 4. Кауфман В.Ш. Языки программирования. Концепции и принципы. – М.: Радио и связь, 5. Буч Г. Объектно-ориентированное проектирование с примерами применения. – М.: Конкорд, 1992.

6. Джехани Н. Язык Ада. – М.: Мир, 1988.

7. Вирт Н. Программирование на языке Модула-2. – М.: Мир, 1987.

8. Керниган Б., Ричи Д. Язык Си. – М.: Финансы и статистика, 1990.

9. Страуструп Б., Эллис М. Справочное руководство по языку программирования C++ с комментариями. – М.: Мир, 1992.

10. Aho A., Sethi R., Ullman J. Compilers: principles, techniques and tools. – N.Y.: Addison Wesley, 1986.

Прикладные программные системы и области их применения Текстовые и табличные процессоры. Деловая и иллюстративная графика. Издательские системы. Интегрированные системы. Автоматизированные рабочие места.

Библиотеки программ и пакеты прикладных программ (ППП) для научных и инженерных расчетов. Системное, функциональное и информационное наполнение ППП. Примеры ППП.

Понятие базы данных. Язык определения (описания) и язык манипулирования данными. Иерархические, сетевые и реляционные базы данных. Уровни представления данных.

Понятие о системе управления базой данных (СУБД). Примеры СУБД.

Информационно-поисковые системы (ИПС). Информационный образ документа, ключевые слова, тезаурус. Поиск нужных документов, релевантность.

Проблемы искусственного интеллекта (ИИ), исторические и философские аспекты.

Классификация систем ИИ. Экспертные системы. Роботы и решатели задач. Системы общения с ЭВМ на естественном языке. Методы представления знаний в системах ИИ, базы знаний. Взаимодействие пользователя с системами ИИ.

Гипертекстовые и мультимедиа системы.

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

Система программирования, ее состав и схема работы.

Программное, языковое и информационное обеспечение системы программирования.

Редакторы текстов.

Компиляторы и интерпретаторы. Редактор внешних связей, его назначение и схема работы. Загрузчик и схема его работы.

Схема решения задач на ЭВМ. Отладчики. Понятие об инструментальных программных средствах.

Исторический обзор. Назначение и основные функции операционной системы (ОС):

управление устройствами, управление задачами и процессами, управление данными. ОС для ЭВМ различных классов.

Управляющая программа операционной системы. Язык директив. Командные файлы.

Иерархическая организация памяти ЭВМ: регистры, память типа кэш, оперативная и внешняя память. Расслоение оперативной памяти. Типы и характеристики устройств внешней памяти.

Организация работы с внешними устройствами на ЭВМ разных классов. Порты ввода вывода. Общая шина. Совмещение работы центрального процессора и периферийных устройств ЭВМ. Мультипрограммный режим работы. Понятие канала.

Файловая система. Файлы, их структура, типы и способы организации. Логические и физические записи файлов, блокирование. Текстовые, исходные, объектные, загрузочные и абсолютные модули. Каталоги. Секретность и защита данных.

Работа ЭВМ в режиме мультипрограммирования, разделения времени и реального времени. Пакетный и диалоговый режимы работы.

Необходимые требования к аппаратуре ЭВМ для организации мультипрограммной работы. Система прерываний, классы прерываний, маскирование прерываний. Защита памяти, привилегированные команды. Команды прерывания (вызов супервизора).

Статическое и динамическое распределение оперативной памяти между задачами.

Фрагментация памяти, тупики. Оверлейная структура программ. Релокация программ.

Виртуальная память, механизм подкачки. Страничная организация виртуальной памяти.

Понятие процесса. Служебные процессы ОС.

Параллельные процессы, их синхронизация. Понятие критической секции. Семафоры, примитивы управления параллельными процессами. Задача о поставщике и потребителе.

Понятие программы-фильтра. Взаимодействие параллельных процессов.

Список литературы (основной) Донован Дж. Системное программирование. – М.: Мир, 1975.

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

Бек Л. Введение в системное программирование. – М.: Мир, 1988.

Баурн С. Операционная система UNIX. – М.: Мир, 1986.

Список литературы (дополнительный) 1. Брябрин В.М. Программное обеспечение персональных ЭВМ. – М.: Наука, 1988.

2. Фигурнов В.Э. IBM PC для пользователя. – М.: Финансы и статистика. Юнити, 1995.

3. Горбунов-Посадов М.М., Корлгин Д.А., Мартынюк В.В. Системное обеспечение пакетов прикладных программ. – М.: Наука, 1990.

4. Соколов А.В. Информационно-поисковые системы. – М.: Радио и связь, 1981.

Области приложений СУБД. Интерфейсы СУБД для обеспечения интерактивного доступа к данным и создания прикладных программ. Языки запросов, запросы через формы, генераторы отчетов, языки быстрого прототипирования приложений. Типичные функции СУБД. Управление данными во внешней памяти, управление буферами оперативной памяти, управление транзакциями, журнализация изменений базы данных, восстановление после сбоев.

Проектирование баз данных. Концептуальные модели данных. Семантические модели данных. Диаграммы «сущность-связи».

СУБД и информационно-поисковые системы. Понятие гипертекста. Применение стабильной оперативной памяти, оптических дисков и других видов современной аппаратуры в информационных системах.

Реляционные базы данных. Реляционная модель данных. Реляционная алгебра и реляционное исчисление. Нормальные формы отношений.

Структуры данных реляционной базы данных. Способы хранения отношений, индексов, журнальной информации.

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

Журнализация. Связь с управлением буферами оперативной памяти. Методы восстановления баз данных после сбоев.

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

Возможности встраивания языка SQL в прикладную программу. Динамический SOL.

Экспертные системы как часть искусственного интеллекта Традиционные средства программного обеспечения ЭВМ и системы ИИ. Основные задачи исследований по ИИ. Интеллектуальная деятельность человека и ИИ. Моделирование – важнейший метод исследований в области ИИ, специфика ИИ моделей.

Решение задач и искусственный интеллект. Представление задач в пространстве состояний.

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

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

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

Программное обеспечение работ по ИИ Экспериментальный и эволюционный характер разработок систем ИИ, требования к программному обеспечению. Языки программирования для задач ИИ: основные концепции, примеры языков (ЛИСП, ПЛЭНЕР, ПРОЛОГ). Инструментальные средства для создания систем ИИ.

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

Примеры конкретных ЭС.

Обучение в системах ИИ Проблема «родителей» и «учителей». Открытость знаний системы ИИ. Приобретение (извлечение) знаний. Обучение на основе запоминания результатов собственной работы;

обучение по примерам; обучение с использованием советов человека. Интегрированные обучающиеся системы ИИ.

Общение человека с системой ИИ Модель общения человека с системой ИИ. Искусственный интеллект и естественный язык. Понимание выражений естественного языка. Представление лингвистических знаний.

Методы анализа и синтеза текста.

Список литературы Дейт К. Введение в системы баз данных. – М.: Наука, 1980.

Дейт К. Руководство по реляционной СУБД DB2. – М.: Финансы и статистика, 1988.

Ульман Дж. Основы систем баз данных. – М.: Финансы и статистика, 1983.

Цикритзис Д., Лоховски К. Модели и базы данных. – М.: Финансы и статистика, 1984.

Мейер Д. Теория реляционных баз данных. – М.: Мир, 1987.

Нильсон Н. Принципы искусственного интеллекта. – М.: Радио и связь, 1985.

Лорьер Ж.-Л. Системы искусственного интеллекта. – М.: Мир, 1991.

Тихомиров O.K. Психология мышления. – М.: МГУ, 1984.

Уэно X. и др. Представление и использование знаний. – М.: Мир, 1989.

Приобретение знаний: Пер. с япон. / Под ред. С. Осуги, Ю. Саэки. – М.: Мир, 1990.

10.