Научно-исследовательский семинар кафедры алгебры и математической логики

2017

 

15 декабря​​

Гумеров Р.Н. (КФУ, Казань) “Групповые структуры и их приложения в категориях анализа и топологической алгебры"

Аннотация: В докладе рассматривается задача о поднятии групповой структуры на накрывающее пространство компактной группы, при котором заданное накрывающее отображение становится морфизмом топологических групп. Обсуждаются приложения этой задачи, в частности, к многочленам над банаховой алгеброй непрерывных функций, заданных на компактной абелевой группе. Рассматриваются свойства морфизмов некоторых топологических групп и тесно связанных с ними полугрупповых С*-алгебр.

 

 

 

3 ноября​​

Когабаев Н.Т. (СО РАН, Новосибирск) “Вычислимые представления проективных плоскостей"

Аннотация: Доклад посвящен изложению результатов автора по исследованию классических вопросов теории вычислимых моделей в следующих основных классах проективных плоскостей:
(а) свободные проективные плоскости;
(б) свободно порождённые проективные плоскости;
(в) папповы проективные плоскости;
(г) дезарговы проективные плоскости.

 

 

27 октября

Александрова С.А. (ДМИ ММФ НГУ, Новосибирск) “О Сигма-определимости в наследственно конечных надстройках"

Аннотация: Доклад посвящен свойствам Сигма-определимости в наследственно конечных надстройках над расширениями поля действительных чисел. Существуют различные подходы к определению вычислимости на несчетных объектах, которые наиболее естественным образом обобщают понятия классической теории вычислимости. Одним из таких подходов является Сигма-определимость в наследственно конечных надстройках над различными структурами, в частности, над расширениями поля действительных чисел. В докладе будут рассмотрены некоторые результаты о выразительных свойствах такой модели вычислимости, ее дескриптивныx свойствах, а также о сравнении Сигма-определимости с другими подходами к заданию вычислимости.

 

​

20 октября

Баженов Н.А. (СО РАН, Новосибирск) “О вычислимо перечислимых отношениях эквивалентности и булевых алгебрах"

Аннотация: Доклад посвящён недавно полученным результатам о различных сводимостях для вычислимо перечислимых (в.п.) отношений эквивалентности. Отношение эквивалентности называют тёмным, если оно несравнимо относительно вычислимой сводимости с тождественным отношением. Доказано, что над любым тёмным в.п. отношением эквивалентности существует бесконечная цепь (относительно вычислимой сводимости) слабо предполных тёмных в.п. отношений эквивалентности. Говорят, что в.п. отношение эквивалентности E BA-сводится к в.п. отношению эквивалентности F, если любая в.п. булева алгебра B, реализуемая E, также реализуется и F. В докладе обсуждаются основные свойства BA-сводимости.

 

 

13 октября

Тапкин Д.Т. (КФУ, Казань) “Кольца формальных матриц и их изоморфизмы"

Аннотация: Хотя проблема изоморфизма, как проблема классификации, интересна сама по себе, наибольший интерес она представляет в свете теоремы Сколема-Нётер. Частным случаем последней теоремы является тот факт, что все автоморфизмы матричной алгебры над полем являются внутренними. Однако, уже для алгебры матриц над коммутативным кольцом это не верно. Если рассматривать родственную проблему изоморфизма, то нетрудно видеть, что для коммутативных колец влечет . В общем случае, по кольцу восстановить кольцо не представляется возможным.

Подобные проблемы были поставлены и для более широких классов колец. Так для теории алгебр инцидентности представляет интерес, можно ли по алгебре восстановить исходный порядок. Для колец верхнетреугольных (и родственным им) формальных матриц спрашивается, можно ли восстановить диагональные кольца. Для колец формальных матриц со значением в кольце интересен вопрос восстановления мультипликативных коэффициентов, определяющих произведение в кольце матриц.

В диссертационной работе исследована проблема изоморфизма для широкого класса колец формальных матриц. Для колец формальных матриц специального вида получен явный вид изоморфизма. При исследовании проблемы изоморфизма для колец формальных матриц со значением в кольце, было введено естественное обобщение этого класса колец – кольца инцидентности формальных матриц. На эти кольца обобщена теорема Крылова, получен критерий изоморфизма, явный вид изоморфизма. В частном случае, получена классификация алгебр формальных матриц над полем.

 

 

22 июня

Всемирнов М.А. (Санкт-Петербургское отделение Математического института им. В.А.Стеклова РАН, Санкт-Петербург) “Гипотезы Чапмена о "зловещем определителе"

Аннотация:  В 2003 году, исследуя свойства решеток в евклидовых пространствах, Робин Чапмен  экспериментально обнаружил некоторые закономерности в поведении определителей матриц, составленных из значений символов  Лежандра по простому модулю.  Если в случае p=3 (mod 4) предположить ответ легко, то в случае p=1 (mod 4) даже требуется некоторое везение,  чтобы по численным данным угадать правильную формулу.  Оказывается, что во втором  случае ответ удается выразить в терминах арифметических инвариантов квадратичных полей (а именно, фундаментальной единицы и числа классов).

Несмотря на многочисленные попытки,  самому Чапмену не удалось доказать эти гипотезы, и в 2009 году он даже назвал эту задачу задачей о "зловещем  определителе" [R. Chapman. My "evil determinant" problem].

В докладе я расскажу о доказательстве гипотез Чапмена, основанном на интересном матричном разложении, а также сформулирую еще несколько гипотез об аналогичных определителях.

 

 

2 июня

Гайнуллина А.Р. (КФУ, Казань) “Коммутативные операды, конструируемые с помощью полугрупп и групп, и их приложения”

Аннотация: В докладе излагаются основные результаты кандидатской диссертации А. Р. Гайнуллиной. Описывается строение алгебр над некоторыми операдами, в числе которых операда полых кубов. Показывается, как, используя алгебры специального вида над этой операдой, можно ввести новую метрику в первом квадранте евклидовой плоскости. Дальнейшие приложения относятся к криптографии с открытым ключом. Показывается, как можно использовать коммутативные операды для построения криптографических протоколов, формально аналогичных тем, в которых используется сложность задачи о дискретном логарифме.

 

 

19 мая 

Абызов А.Н.  (КФУ, Казань)

1-ая часть доклада: “Модули, близкие к проективным и инъективным”

Аннотация: Будут изложены результаты, полученные в последнее время, связанные с модулями, близкими к проективным и инъективным.

2-ая часть доклада: “Алгебраические уравнения разрешимые в радикалах и их связь с некоторыми видами тождеств”

Аннотация: Будут рассмотрены известные классы алгебраических уравнений, разрешимых в радикалах, и будет рассказано, как они связаны с некоторыми видами тождеств.

 

 

5 мая 

Батыршин И.И.  (Москва) "Асимптотическая плотность, вычислимость и теория моделей"

Аннотация: В докладе обсуждаются ключевые направления ведущихся в настоящее время исследований, связанных с асимптотической плотностью и ослабленными определениями вычислимости. Доказывается, что множество является би-иммунным тогда и только тогда, когда никакая вычислимая перестановка не переводит его в генерически вычислимое или эффективно плотно вычислимое множество. Строится пример грубо вычислимого би- иммунного множества. Доказывается, что для любого множества существует перестановка из той же Тьюринговой степени, которая переводит его в эффективно плотно вычислимое множество. Изучаются верхние плотности некоторых множеств. Предлагается программа расширения исследований, связанных с асимптотической плотностью и ослабленными определениями вычислимости, на теорию моделей.

 

28 апреля

Орлова И.В. (Вятский государственный университет, Киров) "Циклические полукольца с некоммутативным сложением"

Аннотация: Рассматриваются полукольца с некоммутативным сложением, мультипликативная полугруппа которых является циклической, возможно, с нулем. Их изучение сведено к исследованию конечных циклических полуколец типа (k, n) с некоммутативным сложением. Отдельно изучаются такие полукольца с идемпотентным сложением и с неидемпотентным сложением. Конечные циклические полукольца с идемпотентным некоммутативным сложением и нетривиальным циклом сводятся к циклическим полукольцам с коммутативным сложением и циклическим полуполям. Выведены некоторые необходимые и достаточные условия для операции сложения в циклических полукольцах с неидемпотентным некоммутативным сложением, имеющих короткий хвост (для k меньше или равного n). При их изучении применяются компьютерные программы. Формулируются задачи для дальнейшего исследования циклических полуколец.

 

 

21 апреля

Андреев М. (МГУ, Москва) "Использование игровой техники в алгоритмической теории информации"

Аннотация: Одним из классических способов доказательства утверждений в алгоритмической теории информации является игровая техника, восходящая к А.Ан. Мучнику. Она заключается в следующем: для доказательства утверждения про сложность строится комбинаторная игра, не использующая сложность явно. После этого в этой игре предъявляется выигрышная стратегия для одного из игроков, и доказывается, что утверждение про сложность является следствием существования такой стратегии. В докладе будут рассмотрены три конкретные проблемы, решения которых получены использованием игровой техники. Первая проблема касается областей определения оптимальных обычных и беспрефиксных способов описания. Вторая проблема посвящена попыткам определить случайность относительно перечислимых снизу полумер. Третий результат является обобщением работы Гача про быстро растущие функции.

 

 

14 апреля

Файзрахманов М.Х. (КФУ, Казань) "Обобщенно вычислимые нумерации и степени перечислений счетных семейств"

Аннотация: 

В докладе излагаются результаты исследований обобщенно вычислимых нумераций с позиции равномерных перечислений счетных семейств относительно произвольных оракулов.  Рассматриваются вопросы существования универсальных обобщенно вычислимых нумераций, предполноты универсальных нумераций, эффективной бесконечности множества минимальных обобщенно вычислимых нумераций заданного бесконечного семейства, а также вопросы о мощности и решеточности их полурешеток Роджерса. Кроме того, рассматриваются спектры перечислений счетных семейств и классов семейств.

 

 

7 апреля

Шилов Н.В. (Университет Иннополис, г. Иннополис) "Метод схем программ для доказательства разрешимости пропозициональных программных логик"

Аннотация: В докладе представлен обзор так называемого схемного метода доказательства разрешимости пропозициональных программных логик. Этот метод "похож" на так называемый теоретико-автоматный метод (А. Эмерсон, М. Варди и др.), но был разработан и развивался независимо от него на протяжении 30 лет (начиная с 1983 г). Он основан на сведении к вариантам проблемы относительной тотальности для недетерминированных схем Янова.

 

 

24 марта

Бикмуллина И.И. (КГТУ им. А.Н. Туполева, Казань) "Автоматический синтез диаграм классов языка UML  на основе ассоциативных отношений предметной области"

Аннотация: В докладе будет рассмотрен вопрос о повышении уровня входного языка описания предметной области на основе ассоциативных отношений с последующим синтезом структурных отношений программной системы  с использованием семантических моделей.

 

 

1 марта

Шарифуллина Ф.Ф. (КПФУ, Казань) "Исследование распределений натуральных чисел с небольшими делителями".

 

 

2016

23 декабря

Мовахеди Фатимсадат (Голестанский университет, г. Горган, Иран) "Some parameters of domination in the middle neighborhood of grap"

Annotation: For a simple graph G=(V;E), the middle neighborhood graph M_nd(G) of G is the graph with the vertex set VUS where S is the set of all open neighborhood sets of G in which two vertices u and v are adjacent if u and v in S and u  intersection with v is nonempty or u belongs V  and v is an open neighborhood set of G containing u. In this research, some properties of the middle neighborhood graph of certain graphs were determined. Also, we obtained the domination number, the independent domination number and the k-connected component domination number in the middle neighborhood graph.

 

 

2 декабря

Баженов Н.А. (СО РАН, Новосибирск) "Спектры категоричности разрешимые структуры"

Аннотация: Спектром категоричности для вычислимой структуры S называется множество всех тьюринговых степеней, могущих вычислять изоморфизм между произвольными вычислимыми копиями S. В докладе даётся обзор современных результатов по спектрам категоричности. Особое внимание уделено спектрам категоричности для структур из естественных алгебраических классов: линейных порядков, булевых алгебр, полей и т.д. Также в докладе рассматриваются различные проблемы, связанные со сложностью изоморфизмов для разрешимых структур. Вычислимая структура S называется разрешимой, если существует алгоритм, позволяющий по произвольному набору элементов из S и произвольной формуле определять, истинна ли данная формула на данном наборе в S. В докладе излагаются совместные с С.С. Гончаровым и М.И. Марчук результаты, относящиеся к проблеме вычислимой характеризации для различных классов разрешимых структур.

 

 

2 сентября

Ахбари Мохаммадхади (Исламский университет Азад, г. Эстахбанат, Иран) "On the doubly connected domination polynomials of a graph"

Annotation: Let G=(V;E) be a simple graph. A subset D of V(G) is a doubly connected dominating set of G if it is a dominating set and both induced subgraphs D and V(G)\D are connected. In this study, we introduced the doubly connected domination polynomial of a graph and investigated some properties of these polynomials for some specific graphs. We also computed the doubly connected domination polynomials for some of families of graphs such as the friendship graphs and the cactus chains graphs.

 

 

10 июня

Селиванов В.Л. (СО РАН, Новосибирск) "Элементарные теории некоторых решеток открытых множеств"

Аннотация:  Доклад содержит результаты полученные совместно с Кудиновым О.В. Будет показано, что теория порядка решеток открытых множеств в некоторых естественных топологических пространствах m-эквивалентна арифметике второго порядка. Также будет показано, что для многих естественных вычислимых метрических пространств и вычислимых областей определения теория первого порядка решеток эффективно открытых множеств является неразрешимой. Более того, для некоторых важных пространств (например, R^n, n>0, и области определения P_omega)" эта теория m-эквивалентна арифметике первого порядка.