Раздел 5.
Введение в теорию алгоритмов
Понятие алгоритма является одним из основных понятий информатики. Эта часть курса посвящена пониманию природы алгоритмов как процесса обработки информации механического характера. Здесь рассматриваются как классические проблемы теории алгоритмов (машина Тьюринга, тезис Черча-Тьюринга, алгоритмически неразрешимые проблемы и вопросы сложности алгоритмов), так и более недавно разработанные разделы, связанные с практическими проблемами проверки правильности алгоритмов - их верификация. Кроме того, рассматриваются вопросы, в классической теории алгоритмов не упоминаемые - это параллельные алгоритмы и их верификация.
Содержание раздела 5
Понятие алгоритма. Формы представления алгоритмов. Машина Тьюринга. Тезис Черча-Тьюринга. Алгоритмически неразрешимые проблемы. Сложность алгоритмов. Подход Флойда-Хоара к верификации программ обработки данных. Программы как преобразователи предикатов. Использование предикативной семантики языков программирования для генерации тестов последовательных программ.
Раздел 6.
Введение в теорию формальных грамматик
Эта часть курса посвящена изучению основных вопросов, составляющих формальный базис теории трансляции формальных языков. Здесь рассматриваются проблемы, связанные с практическими задачами компиляции языков программирования: языки, грамматики, синтаксис, семантика, порождающие грамматики Хомского, иерархия грамматик и языков, синтаксический анализ, семантические вычисления, связь семантики с синтаксисом в формальных языках.
Содержание раздела 6
Идеи Н. Хомского о механизмах понимания естественных языков и методах задания формальных языков. Двусмысленность в естественных языках. Примеры формальных языков. Порождающие грамматики Хомского. Иерархия порождающих грамматик Хомского. Синтаксический анализ. Автоматные грамматики и их связь с автоматными языками. Контекстно-свободные грамматики. Дерево вывода. Семантические вычисления. Неоднозначные грамматики и двусмысленные конструкции формальных языков. Синтаксис и семантика. Методы семантических вычислений. Лексический анализ. Стековая объектная машина. Алгоритмы синтаксического анализа. Алгоритм рекурсивного спуска. Классы S-грамматик, LL(k)-грамматик, грамматик простого предшествования. LR(k), SLR(k), LALR(k) - грамматики. Алгоритм Эрли. Атрибутные грамматики. Атрибутные трансляции слева направо. Компиляторы компиляторов. Оптимизация в компиляторах. Построение компилятора языка Милан.
Курсовая работа: Разработка компилятора алгоритмического языка
Темы самостоятельных работ:
1. Формы представления, эквивалентные преобразования, минимизация и реализация логических функций
2. Базисы логических функций
3. Методы логического вывода в логике высказываний
4. Метод резолюций в логике предикатов
5. Реализация конечного автомата
6. Минимизация конечного автомата-преобразователя
7. Минимизация конечного автомата-распознавателя
8. Недетерминированные конечные автоматы
9. Регулярные выражения и автоматные языки
10. Генерация тестов для программ
Распределение времени студентов по видам занятий
и формы контроля
Таблица 1
|
Разделы программы |
Лекции |
Практические занятия |
Самостоятельная работа |
|
4-й семестр 1. 2. 3. 4. 5. |
6 6 8 6 8 |
6 6 8 6 8 |
4 4 4 4 3 |
|
Итого
В том числе с элементами НИРС 15 часов |
34 |
34 |
19 |
|
5-й семестр 6.
|
- |
17 |
20 |
|
Итого
В том числе с элементами НИРС 25 часов |
- |
17 |
20 |
Таблица 2
|
Виды занятий и формы контроля |
Семестры |
|
|
|
4 |
5 |
|
Лекции, ч/нед Практические занятия, ч/нед Контрольные работы, кол./сем. Самостоятельные задания, кол./сем. Курсовые работы, кол./сем. Зачеты, кол./сем. Экзамены, кол./сем. |
2 2 - 8 1 - 1 |
- 1 1 - 1 1 - |
ЛИТЕРАТУРА