Разработка программных средств для исследования эвристических алгоритмов решения таблиц покрытия

Организация заказчика

ЗАО Морские Компьютерные Системы (МКС)

Контакты представителя заказчика

Павел Васькин +7 911 989-40-97 (моб. Тел., WhatsApp), скайп pvaskin​

Название

Разработка программных средств для исследования эвристических алгоритмов решения таблиц покрытия

Цель

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

Описание проекта (Проблема)

 Проверить целесообразность реализации комбинаторных оптимизационных задач средствами современных СУБД (MS SQL, Postgress) . Критерии оценки:

• Простота реализации;
• Размерность решаемых задач;
• Быстродействие.

Сравнить приближенные алгоритмы решения таблиц покрытия на потоке задач (выбрать и реализовать известные эвристики и предложить собственные).

Размер команды

3 человека (можно две команды: С# + СУБД MS SQL или Qt+Python + Postgress)

Роли и компетенции

• Программист: С# или Qt+Python
• Разработчик баз данных (СУБД MS SQL или Postgress)
• Аналитик и менеджер продукта: гибкие методологии разработки

Результат /
Продукт

Приложение, позволяющее:

• задавать параметры таблиц покрытия для псевдослучайного генератора таблиц покрытия;
• управлять процессом сравнения приближенных алгоритмов на потоке задач;
• управлять архивом.

База данных и набор хранимых процедур, которые позволяют:

• по заданным параметрам таблиц покрытия псевдослучайным образом формировать в базе данных конкретные экземпляры;
• находить решение таблиц покрытия приближенными алгоритмами;
• запоминать и хранить информацию по сравнению приближенных алгоритмов.

Предлагаемые подходы к решению проблемы

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