Валерий Костенко / Степан Кунцьо (5-й курс) opt-sem

На этом форуме публикуются и уточняются постановки задач студентам, а также отслеживается ход их выполнения

Модератор: staff

Закрыто
Бычков Иван
Аспирант
Сообщения: 179
Зарегистрирован: 23 сен 2008 01:19 pm

Валерий Костенко / Степан Кунцьо (5-й курс) opt-sem

Сообщение Бычков Иван »

Алгоритмы планирования обменов для вычислительных систем реального времени, построенные на основе алгоритмов решения японских кроссвордов.

Данная работа является продолжением работы выполненной студентом на 3-м и 4-м курсах.
Рассматриваются вычислительные системы реального времени со средой обмена, построенной на основе коммутаторов Fibre Channel. Требуется построить статическое расписание обменов, такое чтобы все сообщения передавались в рамках заданных директивных интервалов и в любой момент времени каждый порт участвовал в передаче лишь одного сообщения. Студент доказал, что рассматриваемая задача является NP-трудной, свел эту задачу к задаче решения японских кроссвордов и разработал алгоритмы ее решения, основанные на идеях алгоритмов решения японских кроссвордов.
В японском кроссворде в отличие от обычного кроссворда, зашифрованы не слова, а изображение. Поле кроссворда представляет собой расчерченный на клетки лист фиксированного размера. При решении японского кроссворда необходимо восстановить картинку по числам, которые проставлены слева от строк и над колонками. Числа в сетке японского кроссворда показывают, в какой последовательности должны быть расположены группы черных клеток в соответствующей строке или столбце и сколько слитных черных клеток содержит каждая группа. При этом между двумя последовательными группами должна быть как минимум одна пустая клетка. Основная идея решения японских кроссвордов заключается в том, чтобы по заданным длинам групп вычислить те области, которые либо точно будут закрашены, либо точно останутся пустыми. Итеративно повторяя данный процесс, возможно «раскрасить» все поле японского кроссворда.
Алгоритмы решения японских кроссвордов предполагают, что полное решение существует (все группы черных клеток могут быть размещены) и является единственным, являются точными и имеют экспоненциальную сложность. В рассматриваемой задаче полного решения может не существовать (все сообщения из исходного набора корректно размещены в расписание). Также из-за большого размера задачи построения расписания не полиномиальные и псевдополиномиальные алгоритмы не приемлемы по вычислительной сложности. Предложенные алгоритмы состоят из двух шагов: 1)построение областей точного размещения и точного неразмещения сообщений алгоритмом японских кроссвордов, 2)если после первого шага остались области со статусом “неопределенно”, то заполнение этих областей эвристическим алгоритмом. Разработанный алгоритм имеет псевдополиномиальную сложность и является эвристическим. Вычислительные эксперименты показали, что реальная сложность алгоритма для ряда частных задач (накладываются дополнительные ограничения на возможные значения входных данных) значительно меньше ее верхней оценки и для ряда частных задач алгоритм является точным.
В дипломную работу будут включены все результаты, полученные на 3 и 4-м курсах. На 5-м курсе студент должен будет разработать ряд эвристических алгоритмов для заполнения областей со статусом “неопределенно” и для каждого алгоритма выделить частные подзадачи, для которых алгоритм имеет полиномиальную сложность и прогнозируемую точность решение (или является точным). Предполагается, что эти свойства алгоритмов будут доказаны или методом статистической проверки гипотез или аналитически.
Закрыто