Н. А. КРИНИЦКИЙ

АЛГОРИТМЫ ВОКРУГ НАС

Издание второе

ВВЕДЕНИЕ

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

Но не всем известно, что крупнейшим достижением науки XX в. является теория алгоритмов — новая математическая дисциплина. Теория электронных вычислительных машин, теория и практика программирования не могут обойтись без нее. Математическая логика и кибернетика предъявляют на нее свои права. Однако она является самостоятельной наукой, которая готова служить всем наукам, и имеет свое лицо, свой предмет.

Само название — теория алгоритмов — говорит о том, что ее предмет — алгоритмы. Что это такое? Понятие алгоритма является и очень простым и очень сложным. Его простота — в многочисленности алгоритмов, с которыми мы имеем дело, в их обыденности. Но эти же обстоятельства делают его туманным, расплывчатым, трудно поддающимся строгому научному определению.

Слово «алгоритм» происходит от имени узбекского математика Хорезми (по-арабски ал-Хорезми), который в IX в. н. э. разработал правила четырех арифметических действий над числами в десятичной системе счисления. Совокупность этих правил в Европе стали называть «ал-горизм». Впоследствии это слово переродилось в «алгоритм» и сделалось собирательным названием отдельных правил определенного вида (и не только правил арифметических действий). В течение длительного времени его употребляли только математики, обозначая правила решения различных задач.

В 30-х годах XX в. понятие алгоритма стало объектом математического изучения (прежде им только пользовались),  а с появлением электронных вычислительных машин получило широкую известность. Развитие электронной вычислительной техники и методов программирования способствовало уяснению того факта, что разработка алгоритмов является необходимым этапом автоматизации. То, что сегодня записано в виде алгоритма, завтра будет выполняться роботами. В настоящее время слово «алгоритм» вышло за пределы математики. Его стали применять в самых различных областях, понимая под ним точно сформулированное правило, назначение которого — быть руководством для достижения необходимого результата.

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

Описывая зарождение теории алгоритмов, мы не пойдем путем, которым шла история этой науки (хотя о ней и расскажем), а сразу познакомим читателя с современным интуитивным понятием алгоритма. Затем это понятие уточним настолько, чтобы стали возможными изложение традиционных теорий алгоритмов, дальнейшее уточнение понятия алгоритма и, наконец, широкое формальное определение.

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