Упрощенный алгол
Cтраница 1
Упрощенный Алгол отличается от всех принятых языков программирования тем, что он разрешает использовать любой тип математических предписаний, если только их значения понятны, а перевод в команды РАМ или РАСП очевиден. Этот язык не имеет также фиксированного набора типов данных. Переменные могут представлять целые числа, слова и массивы. [1]
Описание Упрощенного Алгола см. в разд. [2]
В Упрощенном Алголе применяются традиционные конструкции математики и языков программирования, такие, как выражения, условия, операторы и процедуры. Ниже приведены неформальные описания некоторых из этих конструкций. Никаких попыток дать точное определение не делается, ибо это выходит далеко за рамки тематики данной книги. Заметим, что легко написать программы, смысл которых зависит от деталей, не рассмотренных здесь, но лучше избегать этого, что мы и проделали ( мы надеемся) в нашей книге. [3]
Напишите алгоритм на Упрощенном Алголе, который располагал бы эту последовательность в порядке ая1, ая2, , йжп работая на том же месте, где она записана вначале. [4]
В качестве упражнения предлагаем написать программу на Упрощенном Алголе для операции УДАЛИТЬ. [5]
 |
Машина с произвольным доступом к памяти. [6] |
Однако, чтобы понимать вычислительную сложность алгоритма, написанного на Упрощенном Алголе, мы должны соотнести Упрощенный Алгол с более формальными моделями. Это будет сделано в последнем разделе настоящей главы. [7]
 |
Машина с произвольным доступом к памяти. [8] |
Однако, чтобы понимать вычислительную сложность алгоритма, написанного на Упрощенном Алголе, мы должны соотнести Упрощенный Алгол с более формальными моделями. Это будет сделано в последнем разделе настоящей главы. [9]
Хотя нашей простейшей моделью является РАМ, мы не хотим, как правило, описывать алгоритмы в терминах подобного устройства. Поэтому мы ввели Упрощенный Алгол ( разд. Но даже этот язык оказывается слишком примитивным, если не ввести в. В этой главе мы познакомим читателя с такими элементарными структурами данных, как списки и стеки; они часто используются в эффективных алгоритмах. [10]
Для наших целей нужно рассматривать лишь время и память, необходимые для выполнения команд, соответствующих операторам на Упрощенном Алголе. [11]
Монография известных американских специалистов, содержащая основы разработки и анализа алгоритмов вычислительной геометрии. Изложение основано на детальном рассмотрении конкретных задач и алгоритмов их решения. Особое внимание уделено способам описания алгоритмов на упрощенном Алголе. [12]
В настоящей главе рассматриваются несколько моделей вычислительной машины - машина с произвольным доступом к памяти, машина с произвольным доступом к памяти и хранимой программой и машина Тьюринга. Эти модели сравниваются по их способности отражать сложность алгоритма, и на их основе строятся более специализированные модели вычислений, а именно: неветвящиеся арифметические программы, битовые вычисления, вычисления с двоичными векторами и деревья решений. В последнем разделе этой главы вводится язык для описания алгоритмов, называемый Упрощенным Алголом. [13]
Реализация таких операторов в терминах общепринятых языков программирования или команд РАМ не вызывает затруднений, но она очень утомительна. Приписывание весов операторам такого типа зависит от контекста, в котором оказывается данный оператор. Дальнейшие примеры операторов такого рода не раз встретятся нам в этой книге в программах на Упрощенном Алголе. [14]
Для анализа работы алгоритма нужна какая-нибудь модель вычислительной машины. Наша книга начинается с определения нескольких таких моделей, достаточно простых для анализа, но в то же время точно отражающих основные черты реальных машин. Эти модели включают машину с произвольным доступом к памяти, машину с произвольным доступом к памяти и хранимой программой, а также некоторые их разновидности. Машина Тьюринга вводится для доказательства экспоненциальных нижних оценок эффективности алгоритмов в гл. Поскольку общая тенденция в разработке программ состоит в отходе от использования машинно-ориентированных языков, вводится язык высокого уровня, называемый Упрощенным Алголом ( Pidgin ALGOL), как основное средство для описания алгоритмов. Сложность программы на Упрощенном Алголе связывается с соответствующей моделью машины. [15]
Страницы: 1 2