|
Факультет прикладной математики и экономики ПРОГРАММА
Программа разработана кафедрой "Системное
программирование" (базовое предприятие Институт системного программирования
РАН) в соответствии с магистерской программой 0103060 - "Системное программирование".
Москва 1999 г. Вычислительные машины 1. Введение в архитектуру ЭВМ. Организация процессора. Оперативная и внешняя память. Представление команд и данных в ЭВМ. Устройства ввода и вывода информации. Параллелизм работы устройств ЭВМ. 2. Машинная арифметика. Позиционные системы счисления. Представление чисел в ЭВМ. Перевод чисел из одной системы в другую. Выполнение арифметических операций в ЭВМ. Точность и методы округления. 3. Оперативная память. Расслоение памяти. Защита памяти. Способы организации виртуальной памяти. Методы контроля памяти. 4. Внешняя память. Магнитные диски, магнитные ленты. Аппаратное сопряжение устройств внешней памяти, оперативной памяти и процессора и организация обменов. Шинная архитектура. Селекторные и мультиплексные каналы. Контроллеры. Методы контроля внешней памяти. 5. Устройства ввода-вывода. Классификация устройств ввода-вывода. Организация обменов с устройствами. Методы контроля. 6. Многопроцессорные и многомашинные вычислительные системы. СуперЭВМ. Локальные и глобальные сети ЭВМ. Сети с коммутацией пакетов. Литература: 1. Королев Л.Н. Структуры ЭВМ и их математическое обеспечение. М. Наука. 1978. 2. Смирнов А.Д. Архитектура вычислительных систем. М. Наука. 1990. 3. Дж. Уокерли. Архитектура и программирование микро-ЭВМ. т. 1. М. Мир. 1984. 4. Малые ЭВМ высокой производительности. Архитектура и программирование. М. Радио и связь. 1990. 5. Амамия М., Танака Ю. Архитектура ЭВМ и искусственный интеллект. М. Мир. 1993. 6. Манфред Брой. Информатика. Основополагающее введение. Часть 2. М. Диалог-МИФИ (Springer-Lehrbuch). 1996. Основы программирования 1. Основные понятия теории алгоритмов. Машины Тьюринга. Нормальные алгорифмы Маркова. Понятия об алгоритмической неразрешимости. 2. Абстрактные структуры данных. Множества, полная упорядоченность, индексация. Графы и деревья, обход деревьев. Стеки, очереди. 3. Конкретные структуры данных. Массивы. Списки (одинарные, двойные). Доступ к данным, включение и исключение элементов данных. 4. Представление в памяти ЭВМ различных структур данных: графов, деревьев, стеков, очередей. 5. Обработка таблиц. Поля и ключи. Последовательный поиск в упорядоченном массиве. Деревья поиска. Перемешанные таблицы. 6. Элементы внутренней сортировки. Деревья сравнений. Сортировка вставками. Сортировка слиянием. 7. Управляющие структуры и их отображение на команды управления ЭВМ. Последовательное управление, ветвление, оператор итерации. 8. Подпрограммы и функции. Соглашения о связях. Передача параметров по ссылке, значению, имени. Повторновходимые подпрограммы. Рекурсивные обращения к подпрограмме. Использование стека при взаимодействии подпрограмм. 9. Статическое и динамическое распределение памяти. Освобождение памяти и сборка мусора. Распределение памяти блоками переменной длины: методы первого подходящего, наилучшего подходящего, близнецов. Литература: 1. Д.Кнут. Искусство программирования для ЭВМ. Том 1. Основные алгоритмы. Глава 2; Том 3. Сортировка и поиск. М. Мир. 1976. 2. П.Холл. Вычислительные структуры. Введение в нечисленное программирование. М. Мир. 1978. 3. Э.З.Любимский, В.В.Мартынюк, Н.П.Трифонов. Программирование. М. Наука. 1980. 4. У.Далл, Э.Дейкстра, К.Хоор. Структурное программирование. М. Мир. 1975. 5. Ахо, Хопкрофт, Ульман. Построение и анализ вычислительных алгоритмов. М., Мир. 1979. 6. Липский. Комбинаторика для программистов. М., Мир. 1987. 7. Н.Вирт. Алгоритмы и структуры данных. М., Мир. 1989. 8. Д.Цикритзис, Ф.Лоховски. Модели данных. М. Финансы и статистика. 1985. 9. Манфред Брой. Информатика. Основополагающее введение. Часть 1. М. Диалог-МИФИ (Springer-Lehrbuch). 1996. Языки и компиляторы 1. Языки и грамматики. Синтаксис и семантика языков программирования. Формальное определение грамматики и языка. Классификации грамматик по Хомскому. 2. Ассемблеры и загрузчики. Команды и псевдокоманды, символические адреса, адресные выражения. Организация работы двухпроходного ассемблера. Классификация загрузчиков и методы загрузки. 3. Характерные особенности языков программирования: Фортран, Алгол, Паскаль, PL/I, Лисп, Си. 4. Основные этапы работы компилятора: лексический анализ, синтаксический анализ и генерация промежуточного кода, генерация объектного кода, оптимизация кода. 5. Лексический анализатор. 6. Синтаксический разбор. Нисходящий анализ, метод рекурсивного спуска. Восходящий анализ. Грамматика предшествования. 7. Промежуточное представление. Польская запись, тетрады, триады и деревья. 8. Оптимизация программ. Основные методы оптимизации. Машиннозависимая и машиннонезависимая оптимизации. 9. Организация таблиц в компиляторах. Распределение памяти под элементарные и составные типы данных. Соответствие фактических и формальных параметров. 10. Генерация объектного кода. Нейтрализация семантических и синтаксических ошибок. 11. Макрогенераторы. Определение, вызов и расширение макросов. Литература. 1. Б.Хигман. Сравнительное изучение языков программирования. М. 1974 г. 2. Д.Баррон. Ассемблеры и загрузчики. М. Мир. 1974 г. 3. Н.Кемпбелл-Келли. Введение в макросы. М. Мир. 1978 г. 4. Д.Грис. Конструирование компиляторов для цифровых вычислительных машин. М. 1974 г. 5. Т. Пратт. Языки программирования: разработка и реализация. М. Мир. 1979 г. 6. Хантер. Проектирование и конструирование компиляторов. М. Финансы и статистика. 1989. 7. Манфред Брой. Информатика. Основополагающее
введение. Часть 1 и 3. М. Диалог-МИФИ (Springer-Lehrbuch). 1996.
Программное обеспечение ЭВМ 1. Функции и основные понятия операционной системы. 2. Процессы. Реализация процессов. Взаимодействие процессов. Параллельные процессы. Взаимное исключение и взаимная синхронизация. Примитивы синхронизации: события, семафоры, мониторы Хоара, почтовые ящики. 3. Распределение времени процессора. Мультипрограммирование. Методы планирования в мультипрограммных системах. 4. Управление памятью. Распределение памяти и организация доступа к памяти в ЭВМ с различной структурой памяти. Виртуальная память. Стратегии и методы замешения страниц. 5. Ввод-вывод и файлы. Базисная и логическая системы управления файлами. Физическая организация данных. Методы доступа к файлам. Индексированные файлы. B-деревья. 6. Базы данных. Модели данных и их особенности; реляционная, сетевая и иерархическая модели. 7. Управление данными в реляционной модели. Реляционная алгебра. Реляционное исчисление. 8. Защита базы данных. Целостность. Секретность. 9. Организация мультидоступа к базе данных. Транзакция. Синхрозахваты. 10. Управление заданиями. Языки управления заданиями. Планирование заданий. 11. Программное обеспечение сетей ЭВМ.
Базовая эталонная модель взаимодействия открытых систем.
Литература: 1. Д.Цикритзис, Ф.Бернстайн. Операционные системы. М. Мир. 1977. 2. С.Кейслер. Проектирование операционных систем для малых ЭВМ. М. Мир. 1986. 3. Г.Дейтел. Введение в операционные системы. М. Мир. 1987. 4. Дж.Ульман. Основы систем баз данных. М. Финансы и статистика. 1983 г. 5. Дж.Мартин. Организация баз данных в вычислительных системах. М. Мир. 1980 г. 6. Хоар. Теория последовательных взаимодействующих процессов. М. Мир. 1989. 7. С.Клименко и В.Уразметов. Internet. Среда обитания информационного общества. РЦФТИ. Протвино. 1995. 8. Манфред Брой. Информатика. Основополагающее
введение. Часть 3. М. Диалог-МИФИ (Springer-Lehrbuch). 1996.
Основы вычислительной математики * Элементы теории погрешностей. Метод наименьших
квадратов.
Литература: 1. Бахвалов Н.С., Жидков Н.П., Кобельков Г.М. Численные методы. М. Наука. 1987. 2. Самарский А.А., Гулин А.В. Численные методы. М. Наука. 1989. 3. Бабенко К.И. Основы численного анализа. М. Наука. 1986. 4. Тыртышников Е.Е. Краткий курс численного анализа. М. ВИНИТИ. 1994. 5. Воеводин В.В. Вычислительные основы
линейной алгебры. М. Наука. 1977.
|