ПИбд31: вопросы к экзамену по ТАиФЯ

К экзамену допущены сдавшие все практических работы и защитившие курсовую работу хоть на что-нибудь. Автоматом ставится оценка на балл ниже, чем за курсовую работу.

Вопросы к экзамену следующие:

  1. Контекстно-свободная грамматика. Определение, сокращённая запись продукций
  2. Порождения с использованием грамматики, левые и правые порождения, деревья разбора
  3. Приложения КС-грамматик: синтаксические анализаторы, генератор синтаксических анализаторов YACC
  4. Рекурсивный вывод, порождения и деревья разбора
  5. Язык описания документов и КС-грамматики
  6. Неоднозначные грамматики, неоднозначность выражений, исключение неоднозначности, существенная неоднозначность
  7. Автоматы с магазинной памятью, конечное управление, формальное определение
  8. Конфигурации МП-автомата, переходы МП-автомата, принципы МП-автоматов
  9. Языки МП-автоматов, допустимость по заключительному состоянию и по пустому магазину, переход между допустимостями
  10. Эквивалентность МП-автоматов и КС-грамматик, переход между ними
  11. Детерминированные автоматы с магазинной памятью, определение. Регулярные языки и ДМП
  12. ДМП и КС-языки, ДМП и неоднозначные грамматики
  13. Нормальные форы КС-грамматик. Нормальная форма Хомского, этапы построения
  14. Нормальные формы КС-грамматик. Удаление бесполезных символов. Вычисление порождающих и допустимых символов, удаление цепных продукций
  15. Свойства замкнутости КС-языков. Подстановки, обращение, пересечение с регулярным языком
  16. Свойства замкнутости КС-языков. Пересечение с регулярным языком, замкнутость по пересечению
  17. Свойства разрешимости КС-языков, преобразование КС-грамматики и МП-автоматов
  18. Проверка пустоты КС-языков, проверка принадлежности КС-языку
  19. Неразрешимые проблемы КС-языков
  20. Машина Тьюринга, элементы МТ, формальное описание МТ, конфигурации МТ, диаграмма переходов МТ
  21. Язык МТ, допустимость по останову, программирование МТ, память в состоянии
  22. Многодорожечные ленты МТ, подпрограммы
  23. Многоленточные МТ, переходы многоленточных МТ, эквивалентность многоленточных и одноленточных МТ, время работы
  24. Недетерминированные МТ, языки НМТ
  25. Ограничения МТ: односторонняя лента
  26. Мультистековые МТ и счётчиковые машины, мощность счётчиковых машин
  27. Имитация МТ на компьютере
  28. Имитация компьютера на МТ, универсальная МТ
  29. Неразрешимость и МТ, неперечислимый язык
  30. Двоичное представление МТ, язык диагонализации
  31. Рекурсивных языки, дополнение рекурсивных и РП-языков
  32. Сведение проблем, теорема о сведении, МТ и пустой язык
  33. Проблема соответствий Поста. Определение, модифицированная ПСП
  34. Неразрешимость неоднозначности КС-грамматики, неразрешимость КС-грамматики и регулярного выражения
  35. Определение класса проблем P, алгоритм Краскала и МТ
  36. Определение класса проблем NP, задача коммивояжёра и МТ
  37. Полиномиальные сведения
  38. NP-полные проблемы и теорема Кука
Запись опубликована в рубрике Читаемые предметы. Добавьте в закладки постоянную ссылку.

Добавить комментарий

Заполните поля или щелкните по значку, чтобы оставить свой комментарий:

Логотип WordPress.com

Для комментария используется ваша учётная запись WordPress.com. Выход /  Изменить )

Фотография Twitter

Для комментария используется ваша учётная запись Twitter. Выход /  Изменить )

Фотография Facebook

Для комментария используется ваша учётная запись Facebook. Выход /  Изменить )

Connecting to %s