Перечисление разбиений с тестированием надежности вычислений
прямоугольник разбиение домино тест
Программа предназначена для подсчета количества разбиений прямоугольника с фиксированной шириной w и переменной высотой h на «костяшки домино». Задача актуальна, она встречается в прикладных вопросах физики и в перечислительной комбинаторике. 
При фиксированном w: R=2^(w/2), a[h] - количество разбиений, (x[1], …, x[R]) – целочисленное решение системы линейных алгебраических уравнений с коэффициентами из множества {a[1], …, a[2R]}.
Для вычисления a[1], …, a[2R] (и, дополнительно, «контрольного» значения a[2R+1]) по классической формуле Kasteleyn P.W. используется класс BigFloat из библиотеки Extreme.Numerics.dll. Ввиду известных вычислительных проблем этой формулы для обеспечения точности необходимо устанавливать параметр Accuracy (число знаков после запятой), от которого зависит вычислительная точность методов класса BigFloat, в большое значение (при w=16, например, в значение 6000).
После нахождения x[1], …, x[R] вычисление a[2R+1], a[2R+2], … по формуле
a[2R+k]=x[1]*a[2R+k-1]+…+ x[R]*a[R+k], k=1, 2, …				(1) которая использует только арифметические операции над целыми числами, не требует значительных затрат времени. Цель программы состоит в распознавании корректности выбора параметра Accuracy. Предусмотрено двойное тестирование. Первый тест –«вектор, полученный удалением из вектора x всех элементов, начиная с самого правого вхождения элемента -1, и заменой оставшихся элементов их абсолютными значениями, является палиндромом». Если тест не пройден, вычисления прерываются и возобновляются лишь после увеличения значения Accuracy. Если тест пройден успешно, то проверяется второй тест: «значение a[2R+1], вычисленное по формуле (1), равно ранее вычисленному «контрольному» значению a[2R+1]»; в случае неуспеха снова корректируется значение Accuracy. Если программа успешно прошла оба теста, надежность вычислений при выбранном значении Accuracy обеспечена.
Рекомендуется применять программу при исследовании вопросов термодинамики, для перечисления совершенных паросочетаний решетчатых графов, а также (в демонстрационных целях) на лекциях по дискретной математике и информатике.
Абдулкарим
Магомедов
Магомедович
Заведующий кафедрой
Доктор физико-математических наук
Профессор
AHE-13894-2022
7005785836
5008
0000-0002-2482-1239
РОССИЯ
Муртазали
Рабаданов
Хулатаевич
Ректор
РОССИЯ
20.01.45
Преподавание информатики
27.03.19
Математическая логика
01.02.ER
COMPUTER SCIENCE, CYBERNETICS
Абдулкарим
Магомедов
Магомедович
Разработка программы
РОССИЯ
ДГУ
Федеральное государственное бюджетное образовательное учреждение высшего  образования "Дагестанский государственный университет"
1020502631621
Организация
Министерство науки и высшего образования Российской Федерации
Федеральные государственные бюджетные учреждения
ДГУ
Федеральное государственное бюджетное образовательное учреждение высшего  образования "Дагестанский государственный университет"
1020502631621
Организация
Министерство науки и высшего образования Российской Федерации
Федеральные государственные бюджетные учреждения