История одной идеи

  • А.Н. Терехов
Keywords: учет последующего контекста, методы сначала-в-ширину и сначала-в-глубину, рекурсивно-переборные задачи, BDD, оптимизация объектного кода

Abstract

В статье рассматривается эволюция идеи учета последующего контекста, возникшая в середине 50-х годов в задаче автоматического перевода с русского языка на английский, её пробная реализация в середине 70-х годов на примере синтеза эффективной объектной программы в компиляторах и, наконец, её современная реализация и применение в задачах поиска решений методом сначала-в-ширину (breadth-first). Для реализации этой идеи применялись различные техники, наиболее эффективной из которых оказалась техника использования BDD (двоичных диаграмм решений). Конечным, хотя и несколько неожиданным результатом, явилось утверждение, что для широкого класса рекурсивно-переборных задач метод решения сначала-в-ширину выигрывает у традиционного механизма возвратов (метод сначала-в-глубину).
Published
2014-01-21
How to Cite
Терехов, А. (2014). История одной идеи. Computer Tools in Education, (2). Retrieved from http://cte.eltech.ru/ojs/index.php/kio/article/view/1172
Section
Articles