Шаблон:Current Seminars — различия между версиями

Материал из Кафедра математической кибернетики
Перейти к: навигация, поиск
(Доклады на спецсеминарах)
(Доклады на спецсеминарах)
Строка 37: Строка 37:
 
|-
 
|-
 
|colspan="3"|'''[[Теоретические проблемы программирования]]'''
 
|colspan="3"|'''[[Теоретические проблемы программирования]]'''
{{announce Seminar|23 сентября 2016 года
 
| Памяти Риммы Ивановны Подловченко.
 
| Захаров В.А.}}
 
{{announce Seminar|7 октября 2016 года
 
| Обзор материалов 25-го Международного семинара "Concurrency, Specification and Programming (CS&P 2016)".
 
| Захаров В.А.}}
 
{{announce Seminar|14 октября 2016 года
 
| Доклад по статье P.A. Abdulla, B. Jonssen "Verifying Programs with Unreliable Channels": Information and Computation, v. 127, 1996, p. 91-101.
 
 
Рассматриваются задачи верификация одного класса систем взаимодействующих процессов с конечным числом состояний, которые обмениваются данными с помощью неограниченных ненадежных FIFO каналов с возможностью потери сообщений. Показано, что для этого класса распределенных систем разрешимы некоторые задачи верификации, а именно проблемы достижимости, проблема безопасности относительно регулярных множеств трасс и проблемы живости относительно множеств состояний управления. При этом следует заметить (и это очень удивительно!), что 1) все перечисленные задачи алгоритмически неразрешимы в том случае, если для каналы абсолютно надежны и 2) сложность указанных задач неэлементарна.
 
| Темербекова Г.Г.}}
 
{{announce Seminar|21 октября 2016 года
 
| Продолжение доклада по статье P.A. Abdulla, B. Jonssen "Verifying Programs with Unreliable Channels": Information and Computation, v. 127, 1996, p. 91-101.
 
| Темербекова Г.Г.}}
 
 
{{announce Seminar|11 ноября 2016 года  
 
{{announce Seminar|11 ноября 2016 года  
 
| Доказательство свойств функциональных программ методом насыщения
 
| Доказательство свойств функциональных программ методом насыщения

Версия 22:35, 1 ноября 2016

Доклады на спецсеминарах

Дискретная математика и математическая кибернетика
Дискретные функции и сложность алгоритмов
30 сентября 2016 года Доклад по статье: Мартынюк В. В. Исследование некоторых классов функций в многозначных логиках // Проблемы кибернетики. – М.: Наука, 1960. – Вып. 3. – С. 49–61. Нургалиев М.
Дискретный анализ
30 сентября 2016 г. Доклад по статье: Мартынюк В. В. Исследование некоторых классов функций в многозначных логиках // Проблемы кибернетики. – М.: Наука, 1960. – Вып. 3. – С. 49–61. Нургалиев М.
Теория управляющих систем и математические модели СБИС
21 октября 2016 г. Доклад "О глубине мультиплексорной функции" Аннотация доклада Титов В.А.
Некоторые вопросы теории управляющих систем
21 октября 2016 г. Доклад "Об одной булевской матрице" Аннотация доклада Данилов Б.Р.
Сложность решения дискретных задач
30 сентября 2016 г. Доклад по статье: Мартынюк В. В. Исследование некоторых классов функций в многозначных логиках // Проблемы кибернетики. – М.: Наука, 1960. – Вып. 3. – С. 49–61. Нургалиев М.
Теоретические проблемы программирования
11 ноября 2016 года Доказательство свойств функциональных программ методом насыщения

равенствами.

В докладе рассматривается метод преобразования программ на нестрогом функциональном языке первого порядка, основанный на комбинации методов насыщения равенствами и суперкомпиляции. Общая идея метода совпадает с идеей насыщения равенствами (предложенного в работе "Equality Saturation: A New Approach to Optimization" Тейта и др. для преобразования императивных программ) и заключается в преобразовании структуры данных, описывающей целое множество программ, а не одну программу. Используемые преобразования, однако, в основном взяты из суперкомпиляции. В рамках метода также предложено преобразование, названное слиянием по бисимуляции, соответствующее доказательству эквивалентности функций по индукции или коиндукции. Показано, что метод применим для индуктивного доказательства эквивалентности программ.

Гречаник Сергей Александрович (ИПМ им.М.В.Келдыша РАН)