Программа вступительного экзамена в аспирантуру ФИЦ ИВТ 05.13.11 Математическое и программное обеспечение вычислительных машин и систем
1. Алгебра, математическая логика и вычислимость
Алгебраические системы. Решётки, булевы алгебры. Исчисление высказываний, нормальные формы. Исчисление предикатов (синтаксис, семантика, теорема дедукции). Теорема о полноте.
Машина Тьюринга, нормальные алгорифмы. Рекурсивные и частично рекурсивные функции, рекурсивные и рекурсивно перечислимые множества. Тезис Чёрча. Универсальная функция, s-m-n теорема. Теорема о рекурсии. Неразрешимые проблемы.
Литература
- Мальцев А.И. Алгебраические системы. М., Наука, 1970.
- Мальцев А.И. Алгоритмы и рекурсивные функции. М., Наука, 1965.
- Ершов Ю.Л., Палютин Е.А. Математическая логика. М., Наука, 1979.
- Катленд Н. Вычислимость. Введение в теорию рекурсивных функций. М., Мир, 1983.
2. Математические основы программирования
Конечные автоматы. Магазинные (МП) автоматы. Алгоритмические проблемы пустоты и эквивалентности для автоматов. Сложность и меры сложности вычислений.
Способы задания формальных языков, классификация грамматик.
Методы описания семантики программирования (операционный, денотационный). Стандартные, рекурсивные и обогащённые (магазинные, счётчиковые) схемы программ. Схемы Янова. Структурированные схемы. Алгоритмические проблемы для схем программ Трансляция классов схем программ. Сети Петри. Корректность и верификация программ. Аксиоматический метод Хоара.
Литература
- Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов. М., Мир, 1979.
- Ахо А., Ульман Дж. Теория синтаксического анализа, перевода и компиляции. М., Мир, 1978.
- Бауэр Ф., Гооз Г. Информатика. М., Мир, 1976.
- Ершов А.П. Введение в теоретическое программирование. М., Наука, 1977.
- Котов В.Е. Введение в теорию схем программ. Новосибирск, Наука, 1978.
- Семантика языков программирования, сб. статей. М., Мир, 1980.
- Андерсон Р. Доказательство правильности программ. М., Мир, 1982.
- Вирт Н. Систематическое программирование. Введение. М., Мир, 1977.
- Котов B.E. Сети Петри. М., Наука, 1984.
3. Архитектура вычислительных средств
Общие сведения об архитектуре ЭВМ.
Процессор, память, система команд, типы адресации, система прерываний. Каналы, устройства ввода-вывода. Семейства ЭВМ. Особенности архитектуры микропроцессоров. Микро и мини ЭВМ. Средства связи между ЭВМ, магистрали, модемы. Многомашинные комплексы, системы передачи данных, сети ЭВМ.
Литература
- Королев Л.Н. Структура ЭВМ и их математическое обеспечение. М., Наука, 1978 и 1980.
- Клингман Э. Проектирование микропроцессорных систем. М., Мир, 1980.
- Якубайтис Э.А. Архитектура вычислительных сетей. М., Статистика, 1980.
- Глушков В.М. Основы безбумажной информатики. М., Наука, 1982.
4. Программное обеспечение вычислительных машин и систем
Принципы организации функционирования ЭВМ на основе операционных систем. Структура операционной системы: управление памятью, управление процессами, управление устройствами, управление информацией. Мультипрограммирование и мультиобработка. Организация режима разделения времени. Организация файловых систем.
Языки программирования: основные структуры данных и управления, абстракция данных и управления, средства поддержки модульного и структурного программирования.
Системы программирования: трансляция и интерпретация, этапы трансляции (лексический, синтаксический, семантический анализ, оптимизация, генерация выходного текста, сборка), управление памятью в создаваемой программе, организация передачи параметров между программными модулями. Ассемблеры, загрузчики и редакторы связей. Диалоговые системы
Литература
- Донован Дж. Системное программирование. М., Мир, 1977.
- Цикритзис Д., Бернстайн Ф. Операционные системы. М., Мир, 1977.
- Пратт Т. Языки программирования разработка и реализация. М., Мир, 1979.
- Лингер Р. , Миллс X., Уит Б. Теория и практика структурного программирования. М., Мир, 1982.
- Грис Д. Конструирование компилятора для цифровых вычислительных машин. М., Мир, 1975.
- Довягло А.М. Диалог пользователя и ЭВМ. Основы проектирования и реализации. Киев, Наукова думка, 1978.
- Данные в языках программирования. М., Мир, 1982.
5. Основы организации баз данных и баз знаний
Понятия баз данных, систем управления базами данных и банками данных. Основные требования к банкам данных. Уровни представления данных. Иерархическая, сетевая и реляционная модели данных.
Основные классы интеллектуальных систем. Дедуктивные и индуктивные схемы вывода. Семантические сети. Системы продукций. Фреймовые средства представления знаний. Вычислительные модели.
Литература
- Мартин Дж. Организация баз данных в вычислительных системах. М., Мир, 1980.
- Дейт К. Введение в системы баз данных. М., Наука, 1980.
- Ульман Дж. Основы систем баз данных. М., Финансы и статистика, 1983.
- Поспелов Д.А. Логико-лингвистические модели в системах управления. М., Энергоиздат, 1981.
- Тыугу Э.X. Концептуальное программирование. М., Наука, 1984, с 250.
- Рыбина Г.В., Строганова Н.А., Фардзинова М.М., Храмов А.А. Системы представления понятийных знаний с использованием фреймов. В кн.: Вопросы кибернетики. Интеллектуальные банки данных. Вып. 55, М., 1979, с.25-48.
6. Методы вычислений
Интерполирование функций, многочлены Лагранжа и Ньютона. Среднеквадратичные приближения. Простейшие интерполяционные и сглаживающие сплайны. Численное интегрирование. Вычислительные методы линейной алгебры. Решение систем нелинейных уравнений. Основные методы минимизации функционалов. Численное решение обыкновенных дифференциальных уравнений. Основные понятия теории разностных методов.
Литература
- Бахвалов Н.С. Численные методы, т.1. М., Наука, 1975.
- Карманов В.Г. Математическое программирование. М., Наука, 1980.
- Годунов С.К., Рябенький B.C. Разностные схемы, введение в теорию. М., Наука, 1977.
- Березин И.С., Жидков Н.П. Методы вычислений, ч. 1, 2. М., Физматгиз, 1959.
Составители: Поттосин И. В., Ильин В.П., Замулин А.В., Непомнящий В.А., Нариньяни А,С.