Loading [MathJax]/jax/output/SVG/config.js
Семинары
RUS  ENG    ЖУРНАЛЫ   ПЕРСОНАЛИИ   ОРГАНИЗАЦИИ   КОНФЕРЕНЦИИ   СЕМИНАРЫ   ВИДЕОТЕКА   ПАКЕТ AMSBIB  
Календарь
Поиск
Регистрация семинара

RSS
Ближайшие семинары




Семинар Добрушинской лаборатории Высшей школы современной математики МФТИ
25 сентября 2012 г. 16:00, комн. 307 ИППИ РАН (Большой Каретный пер., 19), Москва
 


Максимальные паросочетания без пересечений

А. А. Владимиров

Институт проблем передачи информации им. А. А. Харкевича РАН, г. Москва

Количество просмотров:
Эта страница:201

Аннотация: Решается задача определения максимального паросочетания без пересечений в случайном слове, записанном в алфавите {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 доля не спаренных символов становится (асимптотически) равной нулю.
 
  Обратная связь:
 Пользовательское соглашение  Регистрация посетителей портала  Логотипы © Математический институт им. В. А. Стеклова РАН, 2025