ИНФОРМАЦИОННЫЕ ТЕХНОЛОГИИ INFORMATION TECHNOLOGIES УДК 519.7+519.683 Клеточно-автоматные алгоритмы сортировки строк и умножения целых чисел по схеме Атрубина И.В. <...> Заплетина2 1Институт проблем проектирования в микроэлектронике РАН 2Национальный исследовательский университет «МИЭТ» 3АО «НИИМЭ и Микрон» (г. Москва) Cellular Automata Algorithms for String Sorting and Integer Multiplication by Atrubin’s Scheme I.V. <...> Zapletina2 1Institute for Design Problems in Microelectronics of Russian Academy of Sciences, Moscow 2National Research University of Electronic Technology, Moscow 3JSC «NIIME and Mikron», Moscow Приведены отсутствующие в литературе последних десятилетий клеточно-автоматные формулировки алгоритмов сортировки массивов символов и строк. <...> Впервые предложен клеточный автомат, умножающий два целых числа, записанных в системе счисления с произвольным основанием. <...> Алгоритм основан на схеме параллельного умножения Атрубина для систолического массива процессоров и требует четыре компонента (регистра) вместо пяти. <...> Ключевые слова: клеточные автоматы; сортировка; КА-произведение двух целых чисел; умножитель Атрубина. <...> The cellular automata formulations of the algorithm for sorting arrays of characters and strings, not available in literature of recent decades, have been presented. <...> The algorithm is based on the Atrubin’s scheme for parallel multiplication by means of a symbolic array of processors and requires four components (registers) instead of five. <...> С появлением многоядерных процессоров и других нетрадиционных архитектур приобрела актуальность задача адаптации вычислительных алгоритмов к структуре вычислителя [1], подразумевающая значительную степень параллелизма обработки информации. <...> Один из путей решения этой задачи состоит в использовании формализма клеточных автоматов (КА) при задании параллельного алгоритма [2]. <...> В настоящей работе рассматриваются три типовые задачи, встречающиеся в практике программирования: сортировка символов, сортировка строк (или двумерная сортировка) и умножение чисел в системе с основанием N. <...> Существуют и другие задачи, потенциально разрешимые с помощью КА: генерация простых чисел [3], выполнение четырех арифметических действий над числами [4, 5 <...>