47. Машина Поста.

Машина Поста представляет собой идеальное, воображаемое устройство, состоящее из неограниченной в обе стороны ленты и каретки, способной перемещаться вдоль ленты. Лента разбита на клетки. Любая клетка может быть отмеченной или нет. За один шаг каретка может переместиться на одну клетку вправо или на одну клетку влево. Каретка может определить отмечена текущая клетка или нет, а также поставить в текущую клетку отметку или же стереть её.

Машина Поста задается:

1.начальным распределением отмеченных клеток;

2.начальным положение каретки;

3.программой, определяющей последовательность действий каретки.

Командой машины Поста называется указание исполнителю (каретке) выполнить единственное действие из набора возможных действий.

Структура команды машины Поста:

<порядковый номер команды>. <операция> <номер следующей команды>

Невыполнимые команды:

• стереть отметку, если текущая клетка не отмечена;

• поставить отметку, если текущая клетка уже отмечена.

Выполнение программы может:

• не завершится никогда (безостановочная работа);

• завершится безрезультатно на невыполнимой команде;

• завершится результативно на команде Стоп.

Требование к программе машины Поста

1. Порядковые номера команд программы должны образовывать возрастающую арифметическую последовательность, начинающуюся с номера 1 и с шагом 1.

2. Используемые в командах номера должны обозначать присутствующие в программе команды.

48. Интуитивное понятие алгоритма. Роль алгоритмов в обществе и в информатике.

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

Алгоритм представляет собой совокупность правил, инструкций для исполнителя, выполняя которые он за конечное число шагов добьется искомого результата.

Исполнителем алгоритма называется субъект или объект, осуществляющий исполнение алгоритма.

Исполнение алгоритма представляет собой последовательную и точную реализацию исполнителем предписанных в алгоритме действий в конкретных условиях решаемой задачи.

Алгоритм есть описание способа решения задачи. Таким образом, исполнение алгоритма есть фактическое решение задачи по заданному в алгоритме способу.

Алгоритмы являются:

1. формой изложения научных результатов;

2. руководством к действию при решении ранее изученных проблем;

3. необходимым этапом при автоматизации обработки информации и решения различных задач.

49. Основные свойства алгоритмов.

1. Дискретность. Действия алгоритма должны быть представлены последовательностью явно различимых, отделенных друг от друга шагов, этапов. Выполнение любых двух этапов разделено конечным ненулевым отрезком времени.

2. Конечность. Подразумеваются три аспекта свойства.

a. Конечность общего количества этапов. Пример: правило вычисления значения 1+1/4+1/9+…? задает бесконечное количество этапов, а правило 1+1/4+1/9+1/16+1/25+1/36+1/49+1/64+1/81+1/100 ? задает конечное количество этапов.

b. Конечность общего количества выполнений этапов.

c. Явное задание всех этапов. Пример неявного задания этапов: 1+1/4+1/9+…+1/100 ? подразумеваются действия по аналогии.

3. Определенность. Алгоритм должен быть построен так, чтобы любой его исполнитель, выполняя действия алгоритма в одних и тех же исходных условиях получал один и тот же конечный результат. Не допускается любая неопределенность, неоднозначность, случайность в выполнении действии или определении порядка их выполнения.

4. Понятность. Требование означает, что алгоритм должен содержать только такие действия, способ выполнения которых известен исполнителю. Иначе говоря, все предусмотренные в алгоритме действия должны входить в систему команд исполнителя.

5. Потенциальная выполнимость. Требование означает, что алгоритм должен содержать только такие действия, которые исполнитель в состоянии выполнить.

6. Массовость. Требование означает, что алгоритм должен формулироваться так, чтобы его можно было применять к как можно более широкому кругу наборов исходных данных, начальных ситуаций, состояний.