|
|
| (не показаны 133 промежуточных версий 6 участников) |
| Строка 2: |
Строка 2: |
| | {| | | {| |
| | |colspan="3"|'''[[Дискретная математика и математическая кибернетика]]''' | | |colspan="3"|'''[[Дискретная математика и математическая кибернетика]]''' |
| − | {{announce Seminar| | + | <!-- |
| − | | | + | {{announce Seminar | 6 ноября 2020 |
| − | | }} | + | | '''О возможностях построения легкотестируемых контактных схем и схем из функциональных элементов'''. |
| | + | Аннотация. Исследованы задачи реализации булевых функций контактными схемами и схемами из функциональных элементов, допускающими короткие проверяющие либо диагностические тесты относительно неисправностей заранее оговоренного вида, которые могут происходить в схемах. Указанные задачи были впервые предложены (применительно к контактным схемам) С.В. Яблонским |
| | + | и И.А. Чегис в середине 1950-х годов и изучались многими авторами. Рассмотрены следующие виды неисправностей: обрывы и/или замыкания контактов, константные (однотипные или произвольные) либо инверсные неисправности на входах и/или выходах функциональных элементов. Число допустимых неисправностей в схемах может быть ограничено сверху единицей или заданным натуральным числом либо никак не ограничено. Получен ряд верхних и/или нижних оценок длин минимальных тестов для схем, реализующих заданные, все или почти все булевы функции, при различных исходных условиях. Во многих случаях найдены точные значения этих длин и/или улучшены известные ранее результаты. |
| | + | | '''Попков К.А.''' (Институт прикладной математики им. М.В. Келдыша РАН)}} |
| | + | --> |
| | | | |
| | |- | | |- |
| | |colspan="3"|'''[[Дискретные функции и сложность алгоритмов]]''' | | |colspan="3"|'''[[Дискретные функции и сложность алгоритмов]]''' |
| − | {{announce Seminar|30 сентября 2016 года | + | {{announce Seminar| |
| − | | Доклад по статье: Мартынюк В. В. Исследование некоторых классов функций в многозначных логиках // Проблемы кибернетики. – М.: Наука, 1960. – Вып. 3. – С. 49–61. | + | | |
| − | | Нургалиев М.}} | + | | }} |
| | | | |
| | |- | | |- |
| − | |colspan="3"|'''[[Дискретный анализ]]''' | + | |colspan="3"|'''[[Теория управляющих систем и математические модели СБИС]]''' |
| − | {{announce Seminar| 30 сентября 2016 г. | + | {{announce Seminar| |
| − | | Доклад по статье: Мартынюк В. В. Исследование некоторых классов функций в многозначных логиках // Проблемы кибернетики. – М.: Наука, 1960. – Вып. 3. – С. 49–61. | + | | |
| − | | Нургалиев М.}} | + | | }} |
| | | | |
| − | |-
| |
| − | |colspan="3"|'''[[Теория управляющих систем и математические модели СБИС]]'''
| |
| − | {{announce Seminar|21 октября 2016 г.
| |
| − | | Доклад "О глубине мультиплексорной функции" <sup>[[Media:zabluk.docx|Аннотация доклада]]</sup>
| |
| − | | Титов В.А.}}
| |
| − |
| |
| − | |-
| |
| − | |colspan="3"|'''[[Некоторые вопросы теории управляющих систем]]'''
| |
| − | {{announce Seminar|21 октября 2016 г.
| |
| − | | Доклад "Об одной булевской матрице" <sup>[[Media:rom.docx|Аннотация доклада]]</sup>
| |
| − | | Данилов Б.Р.}}
| |
| | |- | | |- |
| | |colspan="3"|'''[[Сложность решения дискретных задач]]''' | | |colspan="3"|'''[[Сложность решения дискретных задач]]''' |
| − | {{announce Seminar| 30 сентября 2016 г. | + | {{announce Seminar| |
| − | | Доклад по статье: Мартынюк В. В. Исследование некоторых классов функций в многозначных логиках // Проблемы кибернетики. – М.: Наука, 1960. – Вып. 3. – С. 49–61. | + | | |
| − | | Нургалиев М.}} | + | | }} |
| − | | + | |
| | |- | | |- |
| | |colspan="3"|'''[[Теоретические проблемы программирования]]''' | | |colspan="3"|'''[[Теоретические проблемы программирования]]''' |
| − | {{announce Seminar|23 сентября 2016 года | + | {{announce Seminar| |
| − | | Памяти Риммы Ивановны Подловченко. | + | | |
| − | | Захаров В.А.}} | + | | }} |
| − | {{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 года
| + | |
| − | | Доказательство свойств функциональных программ методом насыщения
| + | |
| − | равенствами.
| + | |
| − | | + | |
| − | В докладе рассматривается метод преобразования программ на нестрогом функциональном языке первого порядка, основанный на комбинации методов насыщения равенствами и суперкомпиляции. Общая идея метода совпадает с идеей насыщения равенствами (предложенного в работе "Equality Saturation: A New Approach to Optimization" Тейта и др. для преобразования императивных программ) и заключается в преобразовании структуры данных, описывающей целое множество программ, а не одну программу. Используемые преобразования, однако, в основном взяты из суперкомпиляции. В рамках метода также предложено преобразование, названное слиянием по бисимуляции, соответствующее доказательству эквивалентности функций по индукции или коиндукции. Показано, что метод применим для индуктивного доказательства эквивалентности программ.
| + | |
| − | | Гречаник Сергей Александрович (ИПМ им.М.В.Келдыша РАН)}}
| + | |
| − | | + | |
| − |
| + | |
| − | <!--
| + | |
| − | |-
| + | |
| − | |colspan="3"|'''[[Просеминар для 2-го курса]]'''
| + | |
| − | {{announce Seminar||| }}
| + | |
| − | -->
| + | |
| | |} | | |} |
