25 сентября 2012 г. (вторник), 16:00, ауд. 615
А.А. Владимиров (ИППИ):
Максимальные паросочетания без пересечений
Аннотация:
Решается задача определения максимального паросочетания без пересечений в случайном слове, записанном в алфавите {1,2,3,4}, с разрешенными парами 12 и 34. В упрощенном варианте для алфавита {1,...,M} разрешены пары 11, 22,...,MM. С прикладной точки зрения эта задача описывает модели вторичных структур молекул РНК (см. O.V. Valba, M.V. Tamm, S.K. Nechaev, "New alphabet-dependent morphological transition in a random RNA alignment"). Будет доказано, что в обеих постановках при M>2 ненулевая доля символов остается без пары. Если допустимые пары выбираются случайно с вероятностью 0<p<1, то имеет место фазовый переход: при значении параметра p порядка 0.38 доля не спаренных символов становится (асимптотически) равной нулю.
| 19.09.2012 | Петров Леонид Александрович |