Статья
Rational Dyck Paths in the Non Relatively Prime Case
Потоковые алгоритмы возникают при решении многих прикладных задач. В статье предложена модель потоковых программ- автоматов-преобразователей над полугруппами- и для нее была исследована проблема эквивалентности. В настоящей работе описан метод оптимизации потоковых программ. Этот метод является обобщением ранее известного подхода, предложенного в статье для минимизации автоматов-преобразователей. Решение задачи минимизации потоковых программ над группами представлено в статье
Автоматы-преобразователи в качестве модели последовательных реагирующих программы используются в системном программировании, в компьютерной лингвистике, в криптографии, при проектировании микроэлектронных схем и др. Преобразователь принимает на входе последовательность сигналов и выполняет некоторую последовательность действий, преобразуя тем самым конечные слова входного алфавита в полугрупповое выражение, значения которых и являются результатами вычислений.
Мы рассматриваем автоматы-преобразователи над произвольной полугруппой $S$, которая вложима в некоторую конечно порожденную группу с разрешимой проблемой тождества. Ранее было установлено, что задача проверки $k$-значности конечных автоматов-преобразователей над свободными моноидами разрешима. Затем было показано, что эту задачу можно решить за время, полиномиальное относительно размера преобразователей и был предложен более общий метод анализа поведения автоматов преобразователей над полугруппами, вложимыми в разрешимые группы,. Однако применение этого метода было обосновано только для решения задачи проверки 2-значности автоматов-преобразователей. Цель данной работы - показать, что для любого $k, k\geq 1,$ за полиномиальное время проверять свойство $k$-значности конечных автоматов-преобразователей, работающих над полугруппой, вложимой в конечно порожденные разрешимые группы.
Книга содержит необходимые сведения из универсальных и классических алгебр, системы аксиом для основных алгебраических структур (группоид, моноид, полугруппы, группы, частичные порядки, кольца, поля). Описываются основные криптографические алгоритмы. Рассматриваются ставшие классическими помехоустойчивые коды – линейные, циклические, БЧХ. Приводятся алгоритмы проектирования таких кодов. В основу книги положен многолетний опыт преподавания авторами дисциплины «Дискретная математика» на факультете бизнес-информатика, на факультете компьютерных наук Национального исследовательского университета Высшая школа экономики и на факультете автоматики и вычислительной техники Национального исследовательского университета Московский энергетический институт. Книга предназначена для студентов бакалавриата, обучающихся по направлениям 09.03.01 «Информатика и вычислительная техника», 09.03.02 «Информационные системы и технологии», 09.03.03 «Прикладная информатика», 09.03.04 «Программная инженерия», а также для ИТ-специалистов и разработчиков программных продуктов.
В сборнике представлены тезисы докладов участников XVIII Международной студенческой конференции-школы-семинара «Новые информационные технологии», состоявшейся в мае 2010 года.
Сборник состоит из двух разделов. Первый раздел сборника включает пленарные доклады ведущих специалистов. Второй раздел содержит тезисы докладов студентов и аспирантов, учащихся техникумов и колледжей, участвовавших в работе школы-семинара.
В основе настоящего учебного пособия лежит специальный курс по выбору студента, прочитанный автором на механико - математическом факультете МГУ им. М.В. Ломоносова в 2010-2012 учебных годах. Пособие знакомит читателя с методом параметрикса и его дискретным аналогом, развитым в самое последнее время автором пособия и его коллегами-соавторами. Оно объединяет воедино материал, который ранее содержался только в ряде журнальных статей. Не стремясь к максимальной общности изложения, автор ставил целью продемонстрировать возможности метода при доказательстве локальных предельных теорем о сходимости марковских цепей к диффузионному процессу и при получении двусторонних оценок типа Аронсона для некоторых вырожденных диффузий.
Настоящая книга представляет собой своеобразный расширенный учебник по математической статистике. Данный учебник не ограничен рамками учебного стандарта или вузовской программы --- он предназначен всем, кто интересуется математикой вообще и, в частности, хочет узнать, что такое современная математическая статистика, какие задачи и какими методами она решает, какие результаты в ней уже накоплены, какие проблемы в ней сегодня актуальны; наконец, каковы ее истоки, какой путь она прошла и какие ученые были ее творцами. По замыслу авторов, книга простым и доступным языком рассказывает о математической статистике и одновременно обучает ей. Вся теория объясняется и иллюстрируется на интересных и тщательно подобранных примерах. Книга может служить и задачником, так как содержит большой список упражнений для самостоятельного решения, а также справочным пособием по математической статистике, а в некоторых аспектах --- и по теории вероятностей.
Книга будет интересна преподавателям, аспирантам и студентам естественных и технических вузов, в которых изучается математическая статистика, научным работникам, использующим в своей деятельности методы математической статистики, а также самому широкому кругу любителей математики.
В сборнике представлены тезисы докладов участников XIX Международной студенческой конференции-школы-семинара «Новые информационные технологии», состоявшейся в мае 2011 года.
Сборник состоит из двух разделов. Первый раздел сборника включает пленарные доклады ведущих специалистов. Второй раздел содержит тезисы докладов студентов и аспирантов, учащихся техникумов и колледжей, участвовавших в работе школы-семинара.