№
|
Тема работы
|
Тип
|
ФИО
|
Гр.
|
Результат/ номера выступлений, на которых не присутствовали
|
1
|
Реляционное исчисление
|
теор
|
Шолмова Наталья
|
8391
|
/1-/9
|
2
|
Реляционная алгебра
|
теор
|
Курдакова Елена
|
8391
|
Была на всех докладах 28.12.09
|
3
|
Логические схемы и формулы
|
теор
|
Хусаинова Элина
|
8392
|
Была на всех докладах 28.12.09
|
4/8
|
Компьютер на ДНК
|
теор
|
Шарафутдинова Юлия
|
8391
|
Самост. подобран материал Была на всех докладах 28.12.09
|
5/1
|
Тренажер «Классы замкнутости»
|
прог + теор
|
Левоневский Дмитрий
|
8392
|
Выполн. на отлично 01.11.09 Был на всех докладах 28.12.09
|
6
|
Конструктор автоматов «Умный муравей» для КИО (рук. Посов)
|
прог
|
Борисенко Константин
|
8372
|
Есть промеж. рез-ты /8-/9
|
7
|
Компьютер, не потребляющий энергию
|
теор
|
Смирнова Екатерина
|
8372
|
Была на всех докладах 28.12.09
|
8
|
Логические казуальные игры
|
прог
|
Спиридонов Роман
|
8391
|
Создан сайт, составлен каталог игр /1-/9
|
9
|
Теория конструирования регулярных выражений на основе примеров и
контрпримеров (рук. Посов) (иссл.)
|
прог
|
Камышанов Андрей
|
8371
|
/3-/5
|
10
|
Тренажёр на конструирование регулярных выражений на основе
примеров и контрпримеров (рук. Посов)
|
теор
|
Евсигнеева Ангелина
|
8371
|
/3
|
11
|
Построение генераторов задач по логическому описанию
предметной области
|
прог
|
Кудряшов Кирилл
|
8392
|
Был на всех докладах 28.12.09
|
12
|
Упрощённый язык записи химических формул SMILE
|
теор
|
Сафиуллин Рустам
|
8392
|
Был на всех докладах 28.12.09
|
13
|
Темпоральная логика
|
теор
|
Подольская Александра
|
8372
|
Была на всех докладах 28.12.09
|
14
|
Перевод тренажёра по булевым функциям на JavaScript
|
прог
|
Петров Сергей
|
8371
|
/3-/6
|
15
|
Минимизация логических выражений, содержащих только операции отрицания, конъюнкции и скобки. Например, выражение !(x*!y)*!(x*y) можно упростить до !x, выражение !(!x*!y)*(x*y) можно упростить до x*y, а выражение !(x*!y)*!(!x*y) видимо упростить нельзя (иссл.)
|
теор
|
Мосяков Никита
|
8305
|
/1-/9
|
16
|
Разработать алгоритм, определяющий класс замыкания любого
набора булевых функций (иссл.)
|
теор
|
Лисицкая Ксения
|
8302
|
/1-/9
|
17
|
Тренажёр «Многочлены Жегалкина»
|
прог
|
Рублёв Евгений
|
8302
|
Был на всех докладах 28.12.09
|
18/6
|
Токенизация текста (рук. Посов)
|
прог
|
Береснев Игорь
|
8302
|
Был на всех докладах 28.12.09
|
19
|
Тренажер по регулярным выражениям (рук. Посов)
|
прог
|
Антонов Роман
|
8392
|
Был на всех докладах 28.12.09
|
20/4
|
Сайт для подготовке к экзамену по МЛиТА
|
прог
|
Галеев Равиль
|
8392
|
Был на всех докладах 28.12.09
|
21
|
Визуализация решений логических задач на многомерном кубе | теор + прог
|
Мартынов Антон
|
8305
|
Был на всех докладах 28.12.09 (отказ от участия)
|
22
|
Символьная верификация моделей и темпоральная логика
|
теор
|
Дубровская Марина
|
8305
|
/1-/9 (отказ от участия)
|
23
|
Многозначная логика и генераторы задач многозначной логики
|
теор + прог
|
Ермаков Владимир
|
8305
|
/1-/9 (отказ от участия)
|
24/2
|
Реализация логики в биокомпьютере
|
теор
|
Каримов Артур
|
8301
|
Был на всех докладах 28.12.09
|
25
|
Реализация логики в квантовом компьютере
|
теор
|
Михайлов Михаил
|
8301
|
Был на всех докладах 28.12.09
|
26
|
Казуальная игра "Булевы функции"
|
прог
|
Жеронкин Кирилл
|
8391
|
/1-/9 (отказ от участия)
|
27
|
Минимизация логических выражений, содержащих только знаки отрицания и конъюнкции (иссл. задача)
|
теор
|
Проценко Владислав
|
8301
|
/1-/9 (отказ от участия)
|
28
|
Представьте конечный автомат для выражения a*b*, Пусть он содержит две петли по a и по b. Если добавить условие, что количество движений по ребру первой петли равно количеству движений по второй петле, то язык получается a^n b^n. Это уже нерегулярный язык. Вопрос, можно ли с помощью подобных условий на количество движений по ребрам получить любой КС язык и если да то как (иссл. задача)?
|
теор
|
Горшков Илья
|
8301
|
/1-/9 (отказ от участия)
|
29 | "Упростить регулярное выражение". Подробнее: 1) из теоремы Клини следует, что любой автоматный язык можно описать регулярным выражением; 2) однако в теореме ничего не говорится о единственности, и действительно, один и тот же язык можно описать множеством разных регулярных выражений, например, a*+a и a* задают один язык, aa* и aaa*+a задают один язык и т.д. (кстати, уже возникает исследовательская подзадача, интересная сама по себе, - определить, задают ли два выражения один язык или нет); 3) для автоматов (а для каждого регулярного выражения можно построить распознающий автомат) есть теория минимизации, позволяющая минимизировать число состояний автомата; возможно, что этот алгоритм позволит упростить и регулярное выражение; 4) но даже если такой путь позволит упростить выражение, то останется открытым вопрос, можно ли упрощать полученное регулярное выражение дальше (иссл. задача).
| теор | Быстрова Наталья
| 8392 | /1-/9 (отказ от участия)
|
30/3 | Сравнить трудоемкость доказательства теорем исчисления высказываний через составление таблиц истинности и методом резолюций (иссл. задача). | теор | Каримов Тимур
| 8301
| Был на всех докладах 28.12.09 |
31 | "Вычисление значений логических выражений с кванторами". В качестве предметной модели возьмём небольшое множество целых чисел, например, от 0 до 9 (предметные константы). В качестве предметных перемнных - малые латинские буквы (достаточно x, y, z, u, v, w). В качестве предметных функций - арифметические операции. В качестве элементарных предикатов - отношения равенства и неравенства (больше, меньше, равно, не равно, больше или равно, меньше или равно). Тогда вычисляемые выражения будут иметь вид: !AxEy((x<y)=>x=1) - здесь A и E - кванторы всеобщности и существования, а ! - отрицание. Конечная программа должна иметь вид тренажёра: генерировать высказывание с кванторами и проверять ответ.
| прог | Васильев Сергей
| 8305 | Был на всех докладах 28.12.09 |
32/7 | "Теорема о приведении недетерминированного автомата к автомату без пустых символов". Разработать или найти доказательство. Вторая задача - попробовать разработать алгоритм, приводящий недетерминированный автомат к эквивалентному детерминированному без промежуточного этапа с удалением пустых символов. Трудная задача - попробовать объединить эти алгоритмы с алгоритмом минимизации автоматов так, чтобы из недетерминированного получался сразу детерминированный и минимальный (иссл. задача).
| теор | Волков Вячеслав | 8372
| Был на всех докладах 28.12.09 |
33 | Описать класс булевых функций, полученный замыканием функции "импликация". Предложить простой метод определения принадлежности функции классу, а для функций из класса придумать алгоритм для выражения функции через импликацию (иссл. задача).
| теор | Ионин Александр | 8373 | Был на всех докладах 28.12.09 |
34
| Предложить способ построения булевых схем (and, or, not) для функции голования с n=2k+1 переменной (иссл. задача).
| теор | Назаров Д.
| 8373 | Был на всех докладах 28.12.09 |
35 | Сконструировать машину Тьюринга, преобразующую многоленточную или многоголовочную машину Тьюринга в обычную (иссл. задача). | теор | Анна Рыжкова
| 8373 | /1-/2, /9
|
36 | Алгоритм вместо доказательства: алгоритм быстрого
нахождения набора, на котором два данных многочлена Жегалкина не совпадают (иссл. задача). | теор | Вячеслав Гульванский
| 8392 | /1-/9 |
37 | Cравнить два класса алгоритмов: 1) те, которые можно описать конечными автоматами; 2) те, которые описываются примитивно-рекурсивными функциями; и выяснить их отношение. Скорее всего окажется, что автоматные языки входят в класс примитивно-рекурсивных функций, не совпадая с ним. Тогда надо будет придумать примитивно-рекурсивную функцию, которая не может быть задана конечным автоматом, а затем попытаться доказать, что любой автомат можно описать примитивно-рекурсивной функцией (иссл. задача). | теор | Ольга Забайкина
| 8373 | /1-/9 (отказ от участия)
|
38 | Декларативные языки программирования. Программирование логики в ПРОЛОГе. | теор | Александр Трефилов
| 8302 | /1-/9 |
39 | Двоичные разрешающие диаграммы | теор | Захаренко Светлана | 8372 | /1-/9
|
40 | Доказать, что функцию голосования с 2n+1 входами можно выразить через одну функцию - функцию голосования с 3 входами. Какие функции голосования можно выразить через функции голосования с 5 входами? Для экспериментов можно поработать с задачей "Автомат для голосования" конкурса КИО (иссл. задача).
| теор
| Спицова Ольга
| 8372 | /1-/9 |
41/5
|
Обобщенная булева алгебра, включающая время
|
теор
|
Стрелкова Марина
|
8372
|
/8
|
42/9 | Обработка текстов на естественном языке
| прог
| Карасенко Дмитрий
| 8372 | Был на всех докладах 28.12.09
|
| | | | | |