29 июл. 2015 г.

Великие идеи информатики

Философ Билл Рапапорт отметил три великие идеи информатики
Вся информация о любой вычислимой проблеме может быть представлена с использованием только 0 и 1 (или любой другой бистабильной пары, которая может быть триггером между двумя легко различимыми состояниями, такими как «включено»/«выключено», «намагничено»/«размагничено», «высокое напряжение»/«низкое напряжение» и т. д.)
  • Мнение Алана Тьюринга: достаточно 5 действий, чтобы компьютер мог выполнить «что угодно».
Каждый алгоритм может быть выражен на языке, понятном для компьютера в виде 5 основных инструкций:
  • перемещение на позицию влево
  • перемещение на позицию вправо
  • чтение символа на текущей позиции
  • вывести 0 на текущей позиции
  • вывести 1 на текущей позиции
  • Согласно Бёму и Якопини: есть только 3 способа комбинирования следующих действий (в более сложные), которые необходимы компьютеру, чтобы сделать «что-угодно».
Только 3 правила необходимы для того, чтобы совместить любой набор базовых инструкций в более сложные:
последовательность:
сперва сделать это; затем сделать то
выбор:
если такой и такой случай,
THEN (тогда сделать это)
ELSE (иначе сделать то)
повторение:
WHILE (до тех пор, пока такой и такой случаи — делать это)
Обратите внимание, что 3 правила Бема и Якопини могут быть упрощены с использованием goto

Комментариев нет:

Отправить комментарий

Комментарии просматриваются модератором.