Теория вычислений, программа, beta-1
Чему я буду учить детей весной, если дело выгорит (громко не ржать!):
Цели изучения дисциплины
Понимать и уметь использовать такие математические формализмы как: детерминированные и недетерминированные конечные автоматы, регулярные выражения, контекстно-свободные грамматики. Понимать принцип работы и уметь самостоятельно реализовать основанные на этих формализмах лексический и синтаксический анализаторы, уметь использовать готовые библиотеки и инструменты.
Понимать, что такое машины Тьюринга, понимать разделение задач на классы сложности P, NP, PSPACE.
Место дисциплины в учебном плане
Дисциплина изучается в 8 семестре в качестве курса по выбору. Предполагает у учащихся навыки программирования на С++ или Java или Python (по выбору студента).
Программа
ЛекцийСамостоятельно
Конечные автоматы
1. Детерминированные конечные автоматы.
2. Недетерминированные конечные автоматы.2
3. Преобразование НКА в ДКА
4. Алгоритм минимизации ДКА.24
Регулярные выражения
5. Определение, основные свойства.
6. Преобразование регулярного выражения в НКА2
7. Стандартные расширения языка регулярных выражений. Утилиты grep, flex, регулярные выражения в Python.2
8. Реализация лексического анализатора
9. Лемма о накачке.24
Контекстно-свободные грамматики
10. Определение, основные свойства.
11. Атрибутные грамматики2
12. Алгоритм разбора рекурсивным спуском.2
13. LL- и LR-грамматики, алгоритмы разбора.4
14. Инструменты antlr и bison4
15. Лемма о накачке для КС-грамматик 4
Машины Тьюринга
16. Определение, основные свойства, теоретическое значение.
17. Варианты машин Тьюринга, преобразования между ними2
18. Разрешимые, перечислимые, неперечислимые множества. Проблема останова.2
19. Классы сложности P, NP, PSPACE.24
Курсовой проект416
Конечные автоматы
1. Детерминированные конечные автоматы. Детерминированные конечные автоматы с точки зрения теории вычислений. Определение, несколько примеров.
2. Недетерминированные конечные автоматы. Недетерминированные конечные автоматы. Несколько подходов к пониманию их работы. НКА с ε-переходами. Примеры.
3. Преобразование НКА в ДКА. Алгоритм преобразования, оценка сложности. Оценка скорости работы реализации НКА, реализации ДКА.
4. Алгоритм минимизации ДКА.
Регулярные выражения
5. Определение, основные свойства. Введение понятия регулярного выражения, свойства, примеры.
6. Преобразование регулярного выражения в НКА. Алгоритм построения НКА, реализующего заданное регулярное выражение.
7. Стандартные расширения языка регулярных выражений. Утилиты grep, flex, регулярные выражения в Python. Стандартные удобные расширения, не увеличивающие вычислительную мощность. Синтаксис регулярных выражений, применяемый в утилитах fleх и grep. Расширения, увеличивающие мощность на примере Python.
8. Реализация лексического анализатора. Вопросы практической реализации лексического анализатора на основе регулярных выражений и конечных автоматов. Отличия практики от теории.
9. Лемма о накачке. Формулировка и доказательство леммы о накачке.
Контекстно-свободные грамматики
10. Определение, основные свойства. Введение понятия контекстно свободной грамматики. Примеры, свойсва, основные определения (порождение, левосторонний-правостонний вывод, дерево разбора, неоднозначность, существенная необнозначность).
11. Атрибутные грамматики. Добавление атрибутов к КС-грамматикам.
12. Алгоритм разбора рекурсивным спуском. Пример реализации разбора простой грамматики методом рекурсивного спуска.
13. LL- и LR-грамматики, алгоритмы разбора. Описание подклассов КС-грамматик, допускающих эффективный разбор. Алгоритмы разбора, примеры.
14. Инструменты antlr и bison. Использование antlr и bison для реализации синтаксического анализатора, примеры.
15. Лемма о накачке для КС-грамматик. Формулировка, объяснение, идея доказательства.
Машины Тьюринга
16. Определение, основные свойства, теоретическое значение. Введение понятия, пример простой программы. Тезис Чёрча-Тьюринга.
17. Варианты машин Тьюринга, преобразования между ними. Одноленточные, многоленточные, недетерменированные МТ, преобразование любой МТ к одноленточной детерменированной. Универсальная МТ. Равномощность МТ и компьютера.
18. Разрешимые, перечислимые, неперечислимые множества. Проблема останова. Классификация задач по разрешимости. Проблема останова.
19. Классы сложности P, NP, PSPACE. Эффективность решения различных задач разными МТ. Классы P, NP, PSPACE, примеры задач. Утверждение: P не равно NP.
На данный момент половину программы я представляю себе довольно ясно, а половину - довольно смутно... К счастью, впереди ещё вся осень и почти вся зима. "Самостоятельно" - это домашние задания, пока планирую по штуке на раздел. Ну и курсовик, конечно. 4 часа лекций на курсовик - устроим публичную защиту.
Более подробного плана пока в природе не существует.
Мысли-предложения?
Цели изучения дисциплины
Понимать и уметь использовать такие математические формализмы как: детерминированные и недетерминированные конечные автоматы, регулярные выражения, контекстно-свободные грамматики. Понимать принцип работы и уметь самостоятельно реализовать основанные на этих формализмах лексический и синтаксический анализаторы, уметь использовать готовые библиотеки и инструменты.
Понимать, что такое машины Тьюринга, понимать разделение задач на классы сложности P, NP, PSPACE.
Место дисциплины в учебном плане
Дисциплина изучается в 8 семестре в качестве курса по выбору. Предполагает у учащихся навыки программирования на С++ или Java или Python (по выбору студента).
Программа
ЛекцийСамостоятельно
Конечные автоматы
1. Детерминированные конечные автоматы.
2. Недетерминированные конечные автоматы.2
3. Преобразование НКА в ДКА
4. Алгоритм минимизации ДКА.24
Регулярные выражения
5. Определение, основные свойства.
6. Преобразование регулярного выражения в НКА2
7. Стандартные расширения языка регулярных выражений. Утилиты grep, flex, регулярные выражения в Python.2
8. Реализация лексического анализатора
9. Лемма о накачке.24
Контекстно-свободные грамматики
10. Определение, основные свойства.
11. Атрибутные грамматики2
12. Алгоритм разбора рекурсивным спуском.2
13. LL- и LR-грамматики, алгоритмы разбора.4
14. Инструменты antlr и bison4
15. Лемма о накачке для КС-грамматик 4
Машины Тьюринга
16. Определение, основные свойства, теоретическое значение.
17. Варианты машин Тьюринга, преобразования между ними2
18. Разрешимые, перечислимые, неперечислимые множества. Проблема останова.2
19. Классы сложности P, NP, PSPACE.24
Курсовой проект416
Конечные автоматы
1. Детерминированные конечные автоматы. Детерминированные конечные автоматы с точки зрения теории вычислений. Определение, несколько примеров.
2. Недетерминированные конечные автоматы. Недетерминированные конечные автоматы. Несколько подходов к пониманию их работы. НКА с ε-переходами. Примеры.
3. Преобразование НКА в ДКА. Алгоритм преобразования, оценка сложности. Оценка скорости работы реализации НКА, реализации ДКА.
4. Алгоритм минимизации ДКА.
Регулярные выражения
5. Определение, основные свойства. Введение понятия регулярного выражения, свойства, примеры.
6. Преобразование регулярного выражения в НКА. Алгоритм построения НКА, реализующего заданное регулярное выражение.
7. Стандартные расширения языка регулярных выражений. Утилиты grep, flex, регулярные выражения в Python. Стандартные удобные расширения, не увеличивающие вычислительную мощность. Синтаксис регулярных выражений, применяемый в утилитах fleх и grep. Расширения, увеличивающие мощность на примере Python.
8. Реализация лексического анализатора. Вопросы практической реализации лексического анализатора на основе регулярных выражений и конечных автоматов. Отличия практики от теории.
9. Лемма о накачке. Формулировка и доказательство леммы о накачке.
Контекстно-свободные грамматики
10. Определение, основные свойства. Введение понятия контекстно свободной грамматики. Примеры, свойсва, основные определения (порождение, левосторонний-правостонний вывод, дерево разбора, неоднозначность, существенная необнозначность).
11. Атрибутные грамматики. Добавление атрибутов к КС-грамматикам.
12. Алгоритм разбора рекурсивным спуском. Пример реализации разбора простой грамматики методом рекурсивного спуска.
13. LL- и LR-грамматики, алгоритмы разбора. Описание подклассов КС-грамматик, допускающих эффективный разбор. Алгоритмы разбора, примеры.
14. Инструменты antlr и bison. Использование antlr и bison для реализации синтаксического анализатора, примеры.
15. Лемма о накачке для КС-грамматик. Формулировка, объяснение, идея доказательства.
Машины Тьюринга
16. Определение, основные свойства, теоретическое значение. Введение понятия, пример простой программы. Тезис Чёрча-Тьюринга.
17. Варианты машин Тьюринга, преобразования между ними. Одноленточные, многоленточные, недетерменированные МТ, преобразование любой МТ к одноленточной детерменированной. Универсальная МТ. Равномощность МТ и компьютера.
18. Разрешимые, перечислимые, неперечислимые множества. Проблема останова. Классификация задач по разрешимости. Проблема останова.
19. Классы сложности P, NP, PSPACE. Эффективность решения различных задач разными МТ. Классы P, NP, PSPACE, примеры задач. Утверждение: P не равно NP.
На данный момент половину программы я представляю себе довольно ясно, а половину - довольно смутно... К счастью, впереди ещё вся осень и почти вся зима. "Самостоятельно" - это домашние задания, пока планирую по штуке на раздел. Ну и курсовик, конечно. 4 часа лекций на курсовик - устроим публичную защиту.
Более подробного плана пока в природе не существует.
Мысли-предложения?