• A
  • A
  • A
  • АБВ
  • АБВ
  • АБВ
  • А
  • А
  • А
  • А
  • А
Обычная версия сайта

Новости

Семинар лаборатории теоретической информатики возобновил свою работу

В январе лабораторией теоретической информатики было запланировано проведение двух семинаров. На первом семинаре выступил Иван Аржанцев. На втором семинаре о своих результатах рассказал наш коллега из Нижнего Новгорода Дмитрий Сироткин.

На семинаре 16 января Иван Аржанцев обсудил с участниками семинара конструкцию "идеальных чисел", редуцирующую неоднозначные разложения к однозначным, которая позволила Куммеру в 1850 году доказать великую теорему Ферма для всех регулярных простых чисел. Идея Куммера приводит к элементарному и по сути комбинаторному определению теории дивизоров для полугруппы. 
Участники обсудили это определение и проиллюстрировали его на примерах из разных областей математики, определили группу классов дивизоров полугруппы, рассмотрели полугруппу последовательностей с нулевой суммой константу Дэвенпорта и прослушали обзор известных в этой области результатов и открытых проблем. 

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