Аспирантский семинар: формирование производственных ячеек, специализация в многоклеточных системах, передача информации в общем канале связи
Место: Факультет компьютерных наук, Кочновский проезд, д. 3, ауд. 205
Время: 29 сентября, 18:10 – 19:30
Доклады состоятся в рамках научно-исследовательского семинара аспирантской школы по компьютерным наукам.
Первый доклад
Тема: Эффективная точная модель для решения задачи о формировании производственных ячеек
Докладчик: Илья Бычков, аспирант третьего года обучения, кафедра прикладной математики и информатики факультета информатики, математики и компьютерных наук (Нижний Новгород)
В докладе рассматривается задача о формировании производственных ячеек (cell formation problem) с неизвестным числом кластеров. Она заключается в объединении станков и обрабатываемых ими деталей в производственные кластеры в целях увеличения эффективности производства. На текущий момент исследователями предложено множество эвристических алгоритмов, которые эффективно решают даже случаи больших размеров. Однако точных алгоритмов для решения задачи о формировании производственных ячеек известно гораздо меньше, и, как правило, они характеризуются большим временем работы и рядом ограничений, таких как использование упрощенных целевых функций или жестко заданное число производственных ячеек.
В своей работе я предлагаю новую точную модель для решения вышеупомянутой задачи при условии, что число кластеров-ячеек изначально неизвестно. Вычислительные эксперименты были проведены на двух наборах данных: ставшего классическим набора из 35 примеров, предложенного в работе (Goncalves and Resende, 2004), и нового набора из 32 задач, реже встречающихся в литературе. Точные решения (в том числе несколько неизвестных ранее решений) были найдены для 63 из 67 рассмотренных примеров. Время вычислений было заметно сокращено по сравнению с лучшими известными методами.
Второй доклад
Тема: Модели специализации в многоклеточных системах
Докладчик: Денис Тверской, аспирант третьего года обучения, департамент математики факультета экономических наук
Возникновение функциональной специализации и природа многоклеточных — ключевые вопросы в современной эволюционной биологии. Мы рассматриваем колонию клеток и предполагаем, что они могут выполнять одну из двух задач — репродуктивную и соматическую. При этом каждая клетка не может увеличивать выполнение одной задачи, не уменьшив выполнения другой, — данное свойство формализуется посредством внутренней функции компромиссов клетки. Как указано в современной литературе, форма функции компромиссов должна быть вогнутой для колоний малых размеров и выпуклой — для больших колоний. Мы предлагаем абстрактную математическую модель, которая изучает то, как возникновение специализации в колонии зависит от формы внутренних функций компромиссов клеток, ресурсного ограничения и "важности" выполняемых задач в терминах жизнеспособности колонии. Более того, мы рассматриваем случай различных типов клеток в колонии. Мы описываем множество всевозможных решений поставленной задачи математического программирования и рассматриваем подробно некоторые интересные примеры оптимального поведения колонии, возникающие в предложенной модели. Мы показываем, что переход к полностью специализированным организмам потенциально мог происходить различными путями.
Третий доклад
Тема: Асинхронный метод передачи информации в общем канале связи
Докладчик: Александр Штохов, аспирант четвертого года обучения, базовая кафедра Яндекс департамента больших данных и информационного поиска факультета компьютерных наук
Большинство современных систем мониторинга (экологический мониторинг, мониторинг сложных инженерных сооружений и др.) по экономическим соображениям используют модель, в которой наблюдения поступают от множества датчиков через один общий канал связи. В такой модели возникает проблема фрагментации полученного сигнала из общего канала с целью сопоставления этой информации датчикам, от которых этот сигнал был получен. В докладе будет рассмотрена математическая модель системы передачи сообщений большим количеством датчиков в общем канале связи. Будет описан алгоритм решения задачи выделения сигнала от активных датчиков при асинхронном методе передачи информации в рамках рассматриваемой модели. Также будут описаны результаты численного моделирования работы данного алгоритма.
Бычков Илья Сергеевич
Лаборатория алгоритмов и технологий анализа сетевых структур (Нижний Новгород): Стажер-исследователь
Тверской Денис Никитович
Международная научно-учебная лаборатория анализа и выбора решений: Стажер-исследователь
Штохов Александр Николаевич