Лейзерсон Ч., Ривест Р. Алгоритмы: построение и анализ. М.: Мцнмо, 1999. Косовский Н. К. Основы теории элементарных алгоритмов

Программа вступительного экзамена

05.13.17

Утверждена на заседании Ученого совета математико-механического факультета СПбГУ, протокол № 5 от 10.05.2012 г.

Санкт-Петербург

2012


Специализация «Информатика»
I. ТЕОРИЯ ЛОГИЧЕСКИХ ИСЧИСЛЕНИЙ

----------------------------

1. Исчисление высказываний и его свойства.

2. Исчисление предикатов первого порядка и его свойства.

3. Исчисление предикатов с равенством.

4. Формальная арифметика.

5. Теорема Геделя о неполноте арифметики.
Литература:

- Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: построение и анализ. — М.: МЦНМО, 1999.

- Косовский Н.К. Основы теории элементарных алгоритмов. — Л.: Изд. Ленингр. ун-та, 1987.
II. ТЕОРИЯ АЛГОРИФМОВ

-----------------

1. Машины Тьюринга.

2. Нормальные алгорифмы.

3. Элементарные по Кальмару алгорифмы.
Литература:

- Успенский В.А., Семенов А.Л. Теория алгоритмов: основные открытия и приложения. — М.: Наука, 1987.

- Грэхем Р., Кнут Д., Паташник О. Конкретная математика. Основание информатики. — М.: Мир, 1998.
III. АНАЛИЗ АЛГОРИТМОВ

-----------------

1. Перечисление графов.

2. Теорема Пойа.

3. Анализ сложности алгоритма сортировки Шелла.

4. Алгоритмы глобального анализа графов.

5. Эквивалентность некоторых комбинаторных задач. Классы Р и NP. NP-трудные и NP-полные задачи.
Литература:

- Харари Ф.,Палмер Д. Перечисление графов. — М.: Мир, 1982.

- Кнут Дональд. Искусство программирования, том 1. Основные алгоритмы (3-е изд.). — М.: Издательский дом "Вильямс", 2000.
IV. ЯЗЫКИ ПРОГРАММИРОВАНИЯ

----------------------

1. Языки программирования. Основные понятия и определения. История и эволюция. Классификация языков. Проблемы и перспективы развития.

2. Языки, поддерживающие классические технологические процессы.

3. Языковые абстракции: абстракция данных, абстракция управления, абстракция модульности.

4. Языки моделирования. Моделирование на основе структурной методологии.

Моделирование на основе объектно-ориентированной методологии.

5. Языки программирования высокого уровня: обзор языков, ориентированных на предметную область.

6. Языки программирования для задач искусственного интеллекта: Язык Турбо Пролог.

7. Языки программирования для задач искусственного интеллекта: Язык Рефал 5.

8. Естественные языки. Особенности естественных языков и культурных сред.

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

- Пратт Т., Зелковиц М. Языки программирования: разработка и реализация. 4-е издание. — СПб.: Питер, 2002.

- Себеста Р. У. Основные концепции языков программирования, 5-е изд. — М.: Издательский дом "Вильямс", 2001.

- Бабаев И.О., Герасимов М.А., Косовский Н.К. Интеллектуальное программирование. Турбо Пролог и Рефал-5 на персональных компьютерах. – СПб.: Издательство СПбУ, 1992.

-------------------------------------

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), при помощи магазинных процессоров.
Литература:

- Ахо А., Ульман Дж. Теория синтаксического анализа, перевода и компиляции. В 2-х т. — М.: Мир, 1978.

- Мартыненко Б. К. Синтаксически управляемая обработка данных — СПб.: Изд-во СПбГУ, 1997.

- Фитиалов С. Я. Формальные грамматики. — Л.: Изд-во ЛГУ. — 1984.

VI. БАЗЫ ДАННЫХ

-----------

1. Языки описания данных, концептуальная, внешняя схемы и схема хранения.

2. Модели данных концептуального уровня, модель данных "сущность-связь".

3. Реляционная модель данных, реляционная алгебра и исчисление.

4. Целостность в модели данных сущность-связь и в реляционной модели данных.

5. Язык SQL и его соотношение с реляционными языками запросов.

6. Основные алгоритмы выполнения реляционных операций.

7. Оптимизация и выполнение запросов.

8. Структуры хранения баз данных, индексы.

9. Объектные расширения реляционной модели: структуры данных и языки запросов.

10. Согласованность данных и транзакции. Аномалии конкурентного выполнения

транзакций.

11. Истории, расписания, сериализуемость по конфликтам, критерий cериализуемости.

12. Двухфазный протокол блокирования, его корректность и варианты.

13. Обнаружение и разрешение тупиков в транзакционных системах.

14. Обработка отказов приложений: восстановимость расписаний.

15. Ведение журналов и восстановление после отказов системы и носителей данных.

16. Восстановление в распределенных системах: двухфазный протокол фиксации.
Литература:

- Дейт К. Введение в системы баз данных, 6-е изд. — К.; М.; СПб.: Издательский дом "Вильямс", 2000.