Уроки 58 - 60
Уточнение понятие алгоритма. Универсальные исполнители
§34. Уточнение понятия алгоритма

Содержание урока

Зачем нужно определение алгоритма?

Что такое алгоритм?

Универсальные исполнители

Машина Тьюринга

Машина Поста

Нормальные алгорифмы Маркова

Вопросы и задания

Задачи

Вопросы и задания

1. Зачем понадобилось уточнять понятие «алгоритм»?
2. Какие задачи рассматриваются в теории алгоритмов?
3. Почему можно ограничиться алгоритмами обработки символьных строк? Можно ли рассматривать только алгоритмы для преобразования двоичных кодов?
4. Как вы понимаете утверждение «Алгоритм задаёт некоторую функцию»?
5. Как связаны понятия «алгоритм» и «исполнитель»?
6. Что такое программа?
7. В каком случае говорят, что два алгоритма эквивалентны?
8. Что такое универсальный исполнитель?
9. Сравните интуитивное и строгое понятия алгоритма.
10. Опишите устройство и систему программирования машины Тьюринга.
11. Что такое состояние машины Тьюринга?
12. Сопоставьте устройство машины Тьюринга с устройством компьютера. Какие устройства машины Тьюринга выполняют те же функции, что и аналогичные устройства компьютера?
13. В чем особенность состояний q₀ и q₁, машины Тьюринга?
14. По какому принципу можно построить программу для машины Тьюринга, которая последовательно выполняет операции А и Б?
15. Сформулируйте тезис Чёрча-Тьюринга.
16. Сравните машины Тьюринга и Поста.
17. Зачем нумеруются строки в программе для машины Поста?
18. Что такое нормальный алгорифм Маркова?
19. Зачем используют специальные символы в НАМ?
20. Что означает эквивалентность различных универсальных исполнителей?

Подготовьте сообщение

а) «Какие бывают машины Тьюринга?»
б) «Эзотерические языки программирования»
в) «Рекурсивные функции»

Следующая страница Задачи

Cкачать материалы урока