«Утверждаю» | |
Председатель Ученого совета математико-механического факультета СПбГУ, декан математико-механического факультета СПбГУпрофессор ________________ «10» мая 2012 г. |
Программа вступительного экзамена
по специальности научных работников
05.13.11
«Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей»
«Системное программирование»
Утверждена на заседании Ученого совета математико-механического факультета СПбГУ, протокол от 01.01.2001 г.
Санкт-Петербург
2012
Специализация «Системное программирование»
1. Математические основы программирования
1. Понятие алгоритма и его уточнения: машины Тьюринга, нормальные алгоритмы Маркова, рекурсивные функции.
2. Понятие сложности алгоритмов. Классы P и NP. Полиномиальная сводимость задач.
3. Примеры эффективных (полиномиальных) алгоритмов: быстрые алгоритмы поиска и сортировки; полиномиальные алгоритмы для задач на графах и сетях (поиск в глубину и ширину, о минимальном остове, о кратчайшем пути, о назначениях).
4. Автоматы. Эксперименты с автоматами. Алгебры регулярных выражений.
5. Алгебра логики. Булевы функции, канонические формы задания булевых функций. Понятие полной системы. Критерий полноты Поста.
6. Исчисление предикатов первого порядка. Понятие интерпретации. Выполнимость и общезначимость формулы первого порядка. Понятие модели.
7. Отношения и функции. Отношение эквивалентности и разбиения. Фактор множества. Отношения частичного порядка.
8. Формальные языки и способы их описания. Классификация формальных грамматик. Их использование в лексическом и синтаксическом анализе.
9. l-исчисление, правила редукции, единственность нормальной формы и правила ее достижения, представление рекурсивных функций.
10. Основы комбинаторного анализа. Метод производящих функций, метод включений и исключений. Примеры применения.
11. Коды с исправлением ошибок. Алфавитное кодирование. Методы сжатия информации.
12. Основы криптографии. Задачи обеспечения конфиденциальности и целостности информации. Теоретико-информационный и теоретико-сложностный подходы к определению криптографической стойкости. Системы шифрования с открытым ключом (RSA). Цифровая подпись.
2. Вычислительные машины, системы и сети
1. Архитектура современных компьютеров. Организации памяти и архитектура процессора современных вычислительных машин. Страничная и сегментная организация виртуальной памяти. Кэш-память. Командный и арифметический конвейеры, параллельное выполнение независимых команд, векторные команды.
2. Классификация вычислительных систем (ВС) по способу организации параллельной обработки. Многопроцессорные и многомашинные комплексы. Вычислительные кластеры. Проблемно-ориентированные параллельные структуры: матричные ВС, систолические структуры.
3. Назначение, архитектура и принципы построения информационно – вычислительных сетей (ИВС). Локальные и глобальные ИВС, технические и программные средства объединения различных сетей.
4. Методы и средства передачи данных в ИВС, протоколы передачи данных.
5. Особенности архитектуры локальных сетей (Ethernet, FDDI).
6. Сеть Internet, доменная организация, семейство протоколов TCP/IP. Информационно-вычислительные сети и распределенная обработка информации.
3. Языки и системы программирования.
Технология разработки программного обеспечения
1. Языки программирования. Процедурные языки программирования (Фортран, Си), Функциональные языки программирования (Лисп), логическое программирование (Пролог), объектно-ориентированные языки программирования (Ява).
2. Процедурные языки программирования. Основные управляющие конструкции, структура программы. Работа с данными: переменные и константы, основные типы данных, структуры данных (массивы и записи). Процедуры (функции): вызов процедур, передача параметров (по ссылке, по значению, по результату).
3. Объектно-ориентированное программирование. Классы и объекты, наследование, интерфейсы. Понятие об объектном окружении. Рефлексия. Библиотеки классов. Средства обработки объектов (контейнеры и итераторы).
4. Распределенное программирование. Процессы и их синхронизация. Семафоры, мониторы Хоара. Объектно-ориентированное распределенное программирование. CORBA. Параллельное программирование над общей памятью. Нити. Стандартный интерфейс Open MP.
5. Основы построения трансляторов. Структура оптимизирующего транслятора. Промежуточные представления программы: последовательность символов, последовательность лексем, синтаксическое дерево, абстрактное синтаксическое дерево.
6. Анализ исходной программы в компиляторе. Автоматные (регулярные) грамматики и сканирование, контекстно свободные грамматики и синтаксический анализ, организация таблицы символов программы, имеющей блочную структуру, хеш-функции.
7. Оптимизация программ при их компиляции. Оптимизация базовых блоков, чистка циклов. Анализ графов потока управления и потока данных.
8. Генерация объектного кода в компиляторах. Перенастраиваемые (retargetable) компиляторы, gcc (набор компиляторов Gnu). Переработка термов (term rewriting).
9. Машинно-ориентированные языки, язык ассемблера. Представление машинных команд и констант. Команды транслятору. Их типы, принципы реализации.
10. Системы программирования (СП), типовые компоненты СП: языки, трансляторы, редакторы связей, отладчики, текстовые редакторы.
11. Пакеты прикладных программ (ППП). Системная часть и наполнение. Языки общения с ППП. Машинная графика. Средства поддержки машинной графики. Графические пакеты.
12. Технология разработки и сопровождения программ. Жизненный цикл программы. Этапы разработки, степень и пути их автоматизации. Обратная инженерия.
13. Отладка, тестирование, верификация и оценивание сложности программ. Генерация тестов. Системы генерации тестов.
14. Методы спецификации программ. Методы проверки спецификации. Схемное, структурное, визуальное программирование. Разработка пользовательского интерфейса, стандарт CUA.
4. Операционные системы
1. Режимы функционирования вычислительных систем, структура и функции операционных систем. Основные блоки и модули.
2. Виды процессов и управления ими в современных ОС. Представление процессов, их контексты, иерархии порождения, состояния и взаимодействие. Многозадачный (многопрограммный) режим работы. Модель клиент-сервер и ее реализация в современных ОС.
3. Параллельные процессы, схемы порождения и управления. Организация взаимодействия между параллельными и асинхронными процессами: обмен сообщениями, организация почтовых ящиков.
4. Управление доступом к данным. Файловая система, организация, распределение дисковой памяти. Управление обменом данными между дисковой и оперативной памятью.
5. Управление внешними устройствами.
6. Оптимизация многозадачной работы компьютеров. Операционные системы Windows, Unix, Linux. Особенности организации, предоставляемые услуги пользовательского взаимодействия.
7. Операционные средства управления сетями. Эталонная модель взаимодействия открытых систем ISO/OSI. Маршрутизация и управление потоками данных в сети. Локальные и глобальные сети. Сетевые ОС, модель клиент — сервер, средства управления сетями в ОС UNIX, Windows NT. Семейство протоколов TCP/IP, структура и типы IP-адресов, доменная адресация в Internet.
8. Удаленный доступ к ресурсам сети. Организация электронной почты, телеконференций. Протоколы передачи файлов FTP и HTTP, язык разметки гипертекста HTML, разработка WEB-страниц, WWW-серверы.
5. Методы хранения данных и доступа к ним.
Организация баз данных и знаний
1. Концепция типа данных. Абстрактные типы данных. Объекты (основные свойства и отличительные признаки).
2. Основные структуры данных, алгоритмы обработки и поиска. Сравнительная характеристика методов хранения и поиска данных.
3. Основные понятия реляционной и объектной моделей данных.
4. Теоретические основы реляционной модели данных (РДМ). Реляционная алгебра, реляционное исчисление. Функциональные зависимости и нормализация отношений.
5. CASE-средства и их использование при проектировании базы данных (БД).
6. Организация и проектирование физического уровня БД. Методы индексирования.
7. Обобщенная архитектура, состав и функции системы управления базой данных (СУБД). Характеристика современных технологий БД. Примеры соответствующих СУБД.
8. Основные принципы управления транзакциями, журнализацией и восстановлением.
9. Язык баз данных SQL. Средства определения и изменения схемы БД, определения ограничений целостности. Контроль доступа. Средства манипулирования данными.
10. Основные понятия технологии клиент—сервер. Характеристика SQL-сервера и клиента. Сетевое взаимодействие клиента и сервера.
11. Информационно-поисковые системы. Классификация. Методы реализации и ускорения поиска.
Основная литература
1. Ахо, Ульман Дж. Компиляторы: принципы, техника реализации и инструменты. М., 2001.
2. Введение в криптографию / Под ред. . СПб.: МЦНМО, 2001.
3. Дж. Введение в системы баз данных. М.: Вильямс, 1999.
4. Введение в операционные системы. М.: Мир, 1987.
5. Искусство программирования. Т. 1 – 3. М., СПб., Киев: ИД «Вильямс», 2000.
6. Когаловский технологий баз данных. М.: Финансы и статистика, 2002.
7. Компьютерные сети. Учебный курс Microsoft Corporation, 1997.
8. Алгоритмы, построение и анализ. М.: МЦНМО, 2000.
9. , Сабельфельд схем программ. М.: Наука, 1991.
10. Механизмы защиты в сетях ЭВМ. М.: Мир, 1993.
11. Мельников информации в компьютерных системах. М.: Финансы и статистика, 1997.
12. Яблонский в дискретную математику. М.: Наука, 2001.
Дополнительная литература
1. Сети передачи данных. М., «Мир», 1989.
2. Сети ЭВМ: протоколы, стандарты, интерфейсы. М., «Мир», 1990
3. Новые стандарты высокоскоростных сетей. // Открытые системы, 3(7), 1994.
4. UNIX – универсальная среда программирования. М.: Финансы и статистика, 1992.
5. Корнеев вычислительные системы. М.: Нолидж, 1999.
6. Королёв ЭВМ и их математическое обеспечение. М.: Наука, 1980.
7. Внутреннее устройство Microsoft Windows 2000. СПб.: Питер, 2001.
8. Ульман Дж. Основы систем баз данных. М., «Финансы и статистика», 1983.
9. Фокс Дж. "Проектирование и создание программных комплексов". М., "Мир", 1984.
Специализация «Информатика»
I. ТЕОРИЯ ЛОГИЧЕСКИХ ИСЧИСЛЕНИЙ
------
1. Исчисление высказываний и его свойства.
2. Исчисление предикатов первого порядка и его свойства.
3. Исчисление предикатов с равенством.
4. Формальная арифметика.
5. Теорема Геделя о неполноте арифметики.
II. ТЕОРИЯ АЛГОРИФМОВ
------
1. Машины Тьюринга.
2. Нормальные алгорифмы.
3. Элементарные по Кальмару алгорифмы.
III. АНАЛИЗ АЛГОРИТМОВ
------
1. Перечисление графов.
2. Теорема Пойа.
3. Анализ сложности алгоритма сортировки Шелла.
4. Алгоритмы глобального анализа графов.
5. Эквивалентность некоторых комбинаторных задач. Классы Р и NP. NP-трудные и NP-полные задачи.
IV. ЯЗЫКИ ПРОГРАММИРОВАНИЯ
1. Языки программирования. Основные понятия и определения. История и эволюция. Классификация языков. Проблемы и перспективы развития.
2. Языки, поддерживающие классические технологические процессы.
3. Языковые абстракции: абстракция данных, абстракция управления, абстракция модульности.
4. Языки моделирования. Моделирование на основе структурной методологии.
Моделирование на основе объектно-ориентированной методологии.
5. Языки программирования высокого уровня: обзор языков, ориентированных на предметную область.
6. Языки программирования для задач искусственного интеллекта: Язык Турбо Пролог.
7. Языки программирования для задач искусственного интеллекта: Язык Рефал 5.
8. Естественные языки. Особенности естественных языков и культурных сред.
Семантический анализ естественных языков. Интернационализация и локализация программных продуктов.
V. ТЕОРИЯ ФОРМАЛЬНЫХ ЯЗЫКОВ И ТРАНСЛЯЦИЙ
----
1. Формальные грамматики, их основные классы. КС-грамматики и деревья выводов в них. Приведенные и неукорачивающие КС-грамматики. Нормальные формы неукорачивающих КС-грамматик.
2. Однозначность и существенная неоднозначность КС-языков. Примеры не КС-языков.
3. Автоматные грамматики и конечные автоматы. Регулярные выражения. Детерминированные конечные автоматы.
4. МП-автоматы различных типов, их эквивалентность КС-грамматикам. Детерминированные автоматы и языки, их основные свойства.
5. LR(k)-грамматики и языки, их основные свойства.
6. Определение трансляции как формального объекта. Некоторые способы задания трансляций: явное перечисление элементов, гомоморфизм, схема синтаксически-управляемой трансляции, конечный и магазинный преобразователь, магазинный процессор.
7. Простые синтаксически-управляемые трансляции. Эквивалентность простых схем синтаксически-управляемых трансляций и недетерминированных магазинных преобразователей.
8. Эквивалентность магазинных преобразователей, реализующих трансляции при конечном состоянии и при пустом магазине.
9. Простые семантически однозначные схемы синтаксически-управляемых трансляций и детерминированные магазинные преобразователи. Генерация выхода простой семантически однозначной трансляции по левостороннему анализу входа посредством детерминированного магазинного преобразователя.
10. Определение класса LL(k)-грамматик. Необходимые и достаточные признаки LL(k)-грамматик.
11. Алгоритм тестирования КС-грамматики на ее принадлежность классу LL(k)-грамматик для заданного значения k. Вспомогательные алгоритмы: построение множества FIRST(), где - цепочка, составленная из терминалов и нетерминалов грамматики, и построение множества (A), где A - нетерминал.
12. Специальные необходимые и достаточные условия LL(1)-грамматик. Сильные LL(k)-грамматики.
13. k-предсказывающие алгоритмы анализа и трансляции, задаваемые при помощи k-предсказывающих алгоритмов анализа (использование этих алгоритмов в качестве анализаторов LL(k)-языков).
14. Построение 1-предсказывающего алгоритма анализа по данной LL(1)-грамматике. Доказательство правильности получаемого алгоритма анализа.
15. Построение k-предсказывающего алгоритма анализа по сильной LL(k)-грамматике.
16. LL(k)-таблицы. Построение множества необходимых и достаточных таблиц для анализа LL(k)-языков.
17. Построение k-предсказывающего алгоритма анализа по множеству необходимых и достаточных LL(k)-таблиц. Доказательство правильности этого алгоритма.
18. Доказательство леммы о том, что никакая леворекурсивная грамматика не может быть LL(k)-грамматикой ни при каком k.
19. Оценка числа шагов k-предсказывающего алгоритма анализа.
20. Реализация простых семантически однозначных трансляций с входными языками класса LL(k) при помощи k-предсказывающих алгоритмов трансляции.
21. Реализация трансляций, определяемых семантически однозначными непростыми схемами синтаксически-управляемых трансляций с входными грамматиками класса LL(k), при помощи магазинных процессоров.
VI. СИСТЕМЫ ПРОГРАММИРОВАНИЯ
--
1. Системы программирования. Основные понятия и определения. История и эволюция. Классификация. Проблемы и перспективы развития.
2. Процесс-ориентированный инструментарий, применяемый в рамках процессов: возникновение и исследование идеи, управление, анализ требований и проектирование.
3. Процесс-ориентированный инструментарий, применяемый в рамках процессов: программирование (реализация). Трансляторы. Компиляторы. Системы генерации трансляторов. Системы анализа корректности программного кода. Интерпретаторы. Декомпиляторы. Системы управления компиляцией и построением программ.
4. Процесс-ориентированный инструментарий, применяемый в рамках процессов: тестирование и отладка. Тестовые мониторы. Средства отслеживания тестового покрытия. Средства динамического построения профиля программы. Системы построения срезов программы. Отладчики. Системы отслеживания проблем (ошибок).
5. Универсальный инструментарий: инструменты работы с текстом. Средства, базирующиеся на регулярных выражениях. Средства поиска различий. Средства поиска на основе шаблонов. Обозреватели и базы данных программ. Текстовые редакторы. Синтаксически-ориентированные редакторы. Гипертекстовые средства
6. Универсальный инструментарий: электронные библиотеки и инструментарий Интернета. Профессиональный поиск информации. Коллекции информационных ресурсов в Интернете.
7. Инструментальные системы: инструментальные среды программирования, средства автоматизации разработки программ (CASE-средства), интегрированные среды. Репозитории проекта.
8. Средства поддержки коллективной разработки. Системы разделения файлов: управления версиями файлов, управления пространствами, синхронизации удаленных пространств. Системы поддержки работы виртуальных групп
VII. БАЗЫ ДАННЫХ
1. Языки описания данных, концептуальная, внешняя схемы и схема хранения.
2. Модели данных концептуального уровня, модель данных "сущность-связь".
3. Реляционная модель данных, реляционная алгебра и исчисление.
4. Целостность в модели данных сущность-связь и в реляционной модели данных.
5. Язык SQL и его соотношение с реляционными языками запросов.
6. Основные алгоритмы выполнения реляционных операций.
7. Оптимизация и выполнение запросов.
8. Структуры хранения баз данных, индексы.
9. Объектные расширения реляционной модели: структуры данных и языки запросов.
10. Согласованность данных и транзакции. Аномалии конкурентного выполнения
транзакций.
11. Истории, расписания, сериализуемость по конфликтам, критерий сериализуемости.
12. Двухфазный протокол блокирования, его корректность и варианты.
13. Обнаружение и разрешение тупиков в транзакционных системах.
14. Обработка отказов приложений: восстановимость расписаний.
15. Ведение журналов и восстановление после отказов системы и носителей данных.
16. Восстановление в распределенных системах: двухфазный протокол фиксации.
VIII. АРХИТЕКТУРНАЯ ПЛАТФОРМА
-
1. Основы архитектуры ЭВМ. Основные понятия и определения. История и эволюция компьютерных архитектур. Классификация вычислительных систем. Проблемы и перспективы развития.
2. Цифровая логика и цифровые системы. Представление данных в памяти компьютера. Оценка производительности вычислительных систем.
3. Микропрограммная реализация ЭВМ.
4. Основные архитектуры набора команд. Классические архитектуры: Фон Неймановская, аккумулятор, стековая, регистр-регистр. Архитектуры CISC и RISC.
5. Архитектура ЭВМ с точки зрения транслятора.
6. Организация вычислительной системы: процессор, память, шина, устройства ввода и вывода данных. Функциональное описание.
7. Параллельные и распределенные архитектуры. Основные классы параллельных архитектур. Коммутаторы вычислительных систем.
8. Архитектура компьютерных сетей. Классификация сетей и сетевые топологии.
Стандарты в области сетей. Аппаратная поддержка локальных сетей. Глобальная сеть Интернет.
IX. ОПЕРАЦИОННАЯ ПЛАТФОРМА
1. Операционные системы. Основные понятия и определения. История и эволюция операционных систем. Поколения операционных систем. Краткий обзор истории создания операционных систем. Классификация операционных систем. Проблемы и перспективы развития.
2. Процессы и потоки (нити) управления. Коммуникация и синхронизация процессов в централизованных архитектурах. Аппаратная поддержка взаимоисключений. Семафоры. Мониторы. Тупики. Модели для анализа свойств процессов.
3. Коммуникация процессов в сетях. Уровневые протоколы. Адресация и маршрутизация в сетях. Средства коммуникации высокого уровня. Синхронизация процессов в распределенных системах.
4. Планирование и диспетчеризация процессов.
5. Память. Основная память. Привязка адресов. Управление виртуальной памятью.
Распределенная общая память.
6. Внешняя память. Управление внешней памятью. Файлы и файловые системы. Распределенные файловые системы. Драйверы.
7. Операционные системы реального времени. Отказоустойчивые операционные системы.
8. Оболочки операционных систем. Администрирование операционных систем.
9. Сетевая безопасность. Основы криптографии.
10. Сравнительный анализ операционных систем семейств Windows и Unix.
11. Распределенные вычисления. Web как пример архитектуры "клиент-сервер". Web-технологии, Web-сервера и Web-протоколы.
X. ТЕХНОЛОГИИ ПРОГРАММИРОВАНИЯ
-----
1. Технологии программирования. Основные понятия и определения. История и эволюция. Классификации. Проблемы и перспективы развития.
2. Классические технологические процессы: возникновение и исследование идеи,
управление.
3. Классические технологические процессы: анализ требований и проектирование,
программирование (реализация).
4. Классические технологические процессы: тестирование и отладка, ввод программы в действие, эксплуатация и сопровождение, завершение эксплуатации.
5. Основные технологические подходы: ранние технологические подходы, группа подходов быстрой разработки, адаптивные технологические подходы, подходы исследовательского программирования.
6. Основные технологические подходы: каскадные технологические подходы, каркасные технологические подходы, генетические технологические подходы, подходы на основе формальных преобразований.
7. Технологии коллективной разработки.
8. Качество программного обеспечения.
Литература:
- Мифический человеко-месяц или как создаются программные системы. — СПб.: Символ-Плюс, 1999.
- Керниган Пайк Роб. Практика программирования. — СПб.: Невский диалект, 2001.
- Инженерия программного обеспечения. – М.: Издательский дом "Вильямс", 2002.
- Иртегов Д. В. Введение в операционные системы. — СПб.: БХВ-Петербург, 2002.
- Современные операционные системы. – СПб.: Питер, 2002.
- Компьютерные сети. – СПб.: Питер, 2002.
- В., Воеводин Вл. В. Параллельные вычисления. — СПб.: БХВ-Петербург, 2002.
- Код. — М.: Издательско-торговый дом "Русская Редакция", 2001.
- Архитектура компьютера. — СПб.: Питер, 2002.
- Дейт К. Введение в системы баз данных, 6-е изд. — К.; М.; СПб.: Издательский дом "Вильямс", 2000.
- Гарсиа-Молина, Ульман, Видом. Системы баз данных. Полный курс."Вильямс", 2003.
- Языки программирования: разработка и реализация. 4-е издание. — СПб.: Питер, 2002.
- Себеста Р. У. Основные концепции языков программирования, 5-е изд. — М.: Издательский дом "Вильямс", 2001.
- , , Косовский программирование. Турбо Пролог и Рефал-5 на персональных компьютерах. – СПб.: Издательство СПбУ, 1992.
Литература:
- Перечисление графов. — М.: Мир, 1982.
- Кнут Дональд. Искусство программирования, том 1. Основные алгоритмы (3-е изд.). — М.: Издательский дом "Вильямс", 2000.
Литература:
- , Семенов алгоритмов: основные открытия и приложения. — М.: Наука, 1987.
- Конкретная математика. Основание информатики. — М.: Мир, 1998.
Литература:
- Алгоритмы: построение и анализ. — М.: МЦНМО, 1999.
- Косовский теории элементарных алгоритмов. — Л.: Изд. Ленингр. ун-та, 1987.
Специализация «Исследование операций»
1.Теория вероятностей и математическая статистика
Случайные величины и распределения вероятностей. Цепи Маркова.
Математичская статистика.
Статистическое моделирование.
Теория массового обслуживания.
2.Вычислительная комбинаторика
методы перебора перестановок, сочетаний, размещений.
3.Теория графов
Основные определения, Связность.
Матрица инйиденций и ее свойства.
теория паросочетаний.
4. Экстремальные задачи
Теория двойственности.
Численные методы линейного и нелинейного программирования.
Методы генерирования столбцов.
Транспортная задача и экстремальные задачи на графах.
Дискретное программирование. Динамическое программирование.
5.Теория игр
матричные игры. Позиционные игры. Игры n лиц.
6. Математико-экономические модели.
Модель Леонтьева. Модель фон Неймана. Модель Вальда.
7. Представление данных
сновные структуры данных и операции над ними
8. Объектно - ориентированное программирование
Основные принципы ООП.
Языки, поддерживающие ООП.
9. Реляционные базы данных
Основные понятия. Операции над данными, Язык запросов
SOL.
Нормальные формы.
СПИСОК ЛИТЕРАТУРЫ
1. Боровков вероятностей. М., 2003.
2. Гнеденко теории вероятностей. М., 1965.
3. Введение в теорию вероятностей и приложения. Тома 1 и 2, М,
1984.
4. Перечисление графов. — М.: Мир, 1982.
5. Кнут Дональд. Искусство программирования, том 1. Основные алгоритмы (3-е изд.). — М.: Издательский дом "Вильямс", 2000.
6. Языки программирования: разработка и реализация. 4-е издание. — СПб.: Питер, 2002.
7. Себеста Р. У. Основные концепции языков программирования, 5-е изд. — М.: Издательский дом "Вильямс", 2001.
8. , , Косовский программирование. Турбо Пролог и Рефал-5 на персональных компьютерах. – СПб.: Издательство СПбУ, 1992.
