Cтраница 2
Для анализа работы алгоритма нужна какая-нибудь модель вычислительной машины. Наша книга начинается с определения нескольких таких моделей, достаточно простых для анализа, но в то же время точно отражающих основные черты реальных машин. Эти модели включают машину с произвольным доступом к памяти, машину с произвольным доступом к памяти и хранимой программой, а также некоторые их разновидности. Машина Тьюринга вводится для доказательства экспоненциальных нижних оценок эффективности алгоритмов в гл. Поскольку общая тенденция в разработке программ состоит в отходе от использования машинно-ориентированных языков, вводится язык высокого уровня, называемый Упрощенным Алголом ( Pidgin ALGOL), как основное средство для описания алгоритмов. Сложность программы на Упрощенном Алголе связывается с соответствующей моделью машины. [16]