РОССИЙСКАЯ ФЕДЕРАЦИЯ
ФЕДЕРАЛЬНАЯ СЛУЖБА ПО ИНТЕЛЛЕКТУАЛЬНОЙ СОБСТВЕННОСТИ
ГОСУДАРСТВЕННАЯ РЕГИСТРАЦИЯ ПРОГРАММЫ ДЛЯ ЭВМ

Номер регистрации (свидетельства): 2016662287

Дата регистрации: 07.11.2016

Номер и дата поступления заявки: 2016616849 28.06.2016

Дата публикации: 20.12.2016

Контактные реквизиты:
evatutin@rambler.ru
	
Авторы:
Ватутин Эдуард Игоревич,
Титов Виталий Семенович,
Заикин Олег Сергеевич,
Журавлев Алексей Дмитриевич,
Манзюк Максим Олегович,
Кочемазов Степан Евгеньевич,
Федоров Сергей Сергеевич

Правообладатель:
федеральное государственное бюджетное образовательное учреждение высшего образования «Юго-Западный государственный университет»

Название программы для ЭВМ:
Программа для рекуррентного перечисления диагональных латинских квадратов заданного порядка методом полного перебора и его модификациями

Реферат:
Программа реализует метод полного перебора и группу его модификаций, позволяющих производить формирование диагональных латинских квадратов (ДЛК) заданного порядка N. При этом ведется подсчет числа сформированных решений (квадратов) и их вывод на экран (при необходимости). Исходная версия реализации метода полного перебора характеризуется темпом генерации менее 1 ДЛК/с. С целью увеличения темпа генерации был реализован ряд модификаций метода полного перебора, отличающихся использованием диагонального порядка заполнения элементов ДЛК; использованием статических структур данных вместо размещения их в динамической памяти; учетом числа возможных значений |Sij | для еще не заполненных ячеек квадрата в совокупности с ранним внеочередным заполнением ячеек с |Sij |=1 и ранним отсечением неперспективных ветвей дерева комбинаторного перебора с |Sij |=0; применением вспомогательных структур данных (одномерных массивов) для быстрого заполнения множеств допустимых элементов Sij ; выбором порядка заполнения ячеек квадрата по критерию |Sij | > min, что уменьшает арность узлов дерева комбинаторного перебора. В совокупности указанные модификации позволяют повысить темп генерации квадратов до 220 000 ДЛК/с. Программа может быть использована для решения ряда задач комбинаторной оптимизации на подсчет объектов, базирующихся на ДЛК.

Тип реализующей ЭВМ: IBM PC - совмест. ПК

Язык программирования: Delphi

Вид и версия операционной системы: Windows ХР/Vista/7/8

Объем программы для ЭВМ: 43 Кб