Файл Syntacore.cpp содержит код программы.

Файл data.txt содержит входные данные.

Файл output.txt содержит выходные данные.

Так как число N считается фиксированным, оно имеет тип const int и требует ручного изменения при изменении длины векторов.

Проблема подсчета весового распределения (спектра) описанного линейного подпространства, или, аналогично, весового распределения линейного кода над полем Галуа характеристики 2, является NP-трудной, и все известные алгоритмы содержат мультипликативный член 2^K в выражении для оценки трудоемкости. Идея этих алгоритмов и данной реализации заключается в переборе всевозможных линейных комбинаций заданных векторов. При этом в реализации движение от вектора к вектору согласовано с зеркальным кодом Грея, что позволяет сэкономить на числе операций на каждом шаге --- новый вектор отличается от старого ровно на один базисный вектор. Таким образом, трудоемкость в реализации есть О-большое от N * 2^K, причем константа C_0 в оценке образуется из четырех операций над типом int: присваивания, присваивания с суммированием, проверки равенства, отрицания. Стоит сказать, что в более точную оценку входит член C_1 * 2^K, где C_1 образуется из одиннадцати операций. Использование T потоков позволяет редуцировать оценку до О-большого от (N * 2^K)/T с той же константой.

Входные данные проходят обработку: по исходным данным методом Гаусса за О-большое от N^2 * K строится линейно независимый набор векторов, задающий то же самое линейное подпространство. Помимо необходимой для корректной работы алгоритма линейной независимости, этот этап гарантирует еще и то, что K <= N.

Требуемая память есть О-большое от N * K и обусловлена необходимостью хранить входные данные.

• При отсутствии распараллеливания можно немного сократить число операций, участвующих в образовании константы C_1 (второй член в оценке трудоемкости). Номер изменившегося бита при переходе от l-ого к (l+1)-ому элементу последовательности Грея в реализации определяется с помощью битовых операций над l и l + 1. Однако этот же номер может быть определен с помощью прохода по массиву из K чисел. Если K < 11, получится небольшой выигрыш в скорости.

• Существует алгоритм, основанный на матричном перемножении, который дает трудоемкость в виде О-большого от K * 2^K ("On the Computation of the Weight Distribution of Linear Codes over Finite Fields" Iliya Bouyuklieva, Stefka Bouyuklievab, Tatsuya Marutac, Paskal Piperkov). Так что, учитывая, что K <= N, можно было бы существенно улучшить скорость работы алгоритма в реализации. Однако тогда существенно возросла бы и требуемая память.