1. Зачем понадобилось уточнять понятие «алгоритм»?
Понятие «алгоритм» уточнялось для создания строгой математической основы, необходимой для изучения вычислимости и автоматизации. Это позволило формализовать его свойства и создать общепринятые методы анализа алгоритмов.
2. Какие задачи рассматриваются в теории алгоритмов?
Теория алгоритмов рассматривает задачи, связанные с изучением вычислимости, разрешимости, сложности алгоритмов, их оптимальности, а также с созданием моделей вычислений, таких как машины Тьюринга или автоматы.
3. Почему можно ограничиться алгоритмами обработки символьных строк? Можно ли рассматривать только алгоритмы для преобразования двоичных кодов?
Ограничение на обработку символьных строк объясняется их универсальностью, так как любую информацию можно представить в виде последовательности символов. Аналогично, двоичные коды являются достаточной основой, поскольку любая информация может быть преобразована в бинарный формат.
4. Как связаны понятия «алгоритм» и «исполнитель»?
Алгоритм связан с исполнителем, поскольку исполнитель (человек, машина или программа) должен последовательно выполнять команды алгоритма. Алгоритм задаёт, что делать, а исполнитель реализует эти действия.
5. В каком случае говорят, что два алгоритма эквивалентны?
Два алгоритма считаются эквивалентными, если для одинаковых входных данных они дают одинаковые выходные результаты, независимо от способа реализации.
6. Сравните интуитивное и строгое понятия алгоритма.
7. Что такое состояние машины Тьюринга?
8. Сопоставьте устройство машины Тьюринга с устройством компьютера. Какие устройства машины Тьюринга выполняют те же функции, что и аналогичные устройства компьютера?
Устройство машины Тьюринга можно сопоставить с устройством компьютера следующим образом: лента машины Тьюринга соответствует оперативной памяти компьютера, головка чтения-записи – процессору или устройству ввода-вывода, таблица переходов – программному обеспечению или алгоритму, который выполняется на компьютере. Состояние машины Тьюринга соответствует текущему состоянию процессора.
9. В чём особенность состояний q0 и q1 машины Тьюринга?
Состояние q0 обозначает начальное состояние машины Тьюринга, в котором она начинает работу. Состояние q1 часто выбирают как конечное (завершающее), в котором машина останавливается после выполнения программы.
10. Как можно построить программу для машины Тьюринга, которая последовательно выполняет операции А и Б, если уже есть две программы, которые выполняют две эти операции по отдельности?
Для объединения двух программ для машины Тьюринга, выполняющих операции А и Б, можно использовать состояние завершения первой программы как начальное состояние второй. Таким образом, программа сначала выполнит операцию А, затем автоматически перейдёт к выполнению операции Б.
11. Сравните машины Тьюринга и Поста.
Машины Тьюринга и Поста различаются в подходе к моделированию вычислений. Машина Тьюринга работает с бесконечной лентой и набором состояний, а машина Поста (нормальная система Поста) оперирует с цепочками символов и правилами переписывания. Однако обе машины обладают эквивалентной вычислительной мощностью.
12. Зачем нумеруются строки в программе для машины Поста?
Нумерация строк в программе для машины Поста позволяет однозначно определить порядок выполнения инструкций и задавать переходы между командами в зависимости от результата текущей операции.
13. Что такое нормальный алгорифм Маркова?
Нормальный алгоритм Маркова (НАМ) – это система правил замены символов, которая позволяет последовательно преобразовывать строку символов. Это формальная модель вычислений, эквивалентная по мощности машинам Тьюринга.
14. Зачем используют специальные символы в НАМ?
Специальные символы в НАМ используются для задания начального или конечного состояния строки, разделения данных и управления процессом вычисления. Они упрощают обработку строк и делают правила замены более понятными.
15. Что означает эквивалентность различных универсальных исполнителей?
Эквивалентность различных универсальных исполнителей означает, что они обладают одинаковой вычислительной мощностью и могут решить одни и те же задачи. Например, машины Тьюринга, машины Поста и нормальные алгоритмы Маркова могут быть преобразованы друг в друга без потери вычислительных возможностей.