ИНФОРМАЦИЯ
О БОЛЬШОМ СЕМИНАРЕ
КАФЕДРЫ
ТЕОРИИ ВЕРОЯТНОСТЕЙ
(руководитель
- член-корр. РАН, профессор А.Н. Ширяев)
Программа на декабрь 2003 г.
3 декабря – П.А. Виленкин,
А.Г. Дьячков.
Вероятностные и
статистические методы исследования
средней длины наибольшего общего подслова двух слов
в конечном алфавите.
Резюме.
Пусть x и y – две конечные последовательности, элементы которых берутся из q-ичного алфавита. Пусть z –последовательность, которая является подпоследовательностью и x, и y, т.е. может быть получена из x или y удалением некоторых элементов. Тогда z называется общей подпоследовательностью x и y. Общая подпоследовательность максимальной длины называется наибольшей общей подпоследовательностью и обозначается LCS(x,y) (Longest Common Subsequence). Ее длина |LCS(x,y)| является часто употребляемой мерой сходства двух строк, которая, в отличие от сходства Хемминга, учитывает возможность вставок и выпадений символов. Данная мера была введена В.И.Левенштейном в 1965 году. Эта мера используется во многих задачах, связанных с сопоставлением, классификацией, распознаванием и т.д. В теории кодирования данное понятие используется при передаче сообщений по каналам связи, в которых могут происходить ошибки типа вставок и выпадений символов.
Пусть задана
длина n и последовательности x и y выбираются случайным образом – каждый
из n элементов выбирается независимо от остальных в соответствии с равномерным
распределением на q-ичном алфавите. Тогда |LCS(x,y)| является случайной величиной.
Исследование этой величины представляет собой определенный теоретический
интерес.
В докладе будет рассказано о существующих вероятностных и статистических методах исследования математического ожидания M |LCS(x,y)|.
Координатором
Большого кафедрального семинара на осенний семестр 2003 года назначен
профессор Сенатов Владимир Васильевич.
Ученым секретарем Большого
кафедрального семинара на осенний семестр 2003 года назначен Селиванов Андрей Валерьевич
(e-mail: a_seliv@mech.math.msu.su).
Семинар проходит по средам в
аудитории 16-24. Начало в 16-20.