Альтернативный экзамен МЛиТА-2009

     Альтернативный экзамен по МЛиТА 2009 года будет проходить в два этапа: 28 декабря и 21 января с 11 часов.
На экзамене должны присутствовать все его участники, так как цель экзамена - получить как можно больше профессиональных знаний посредством обмена результатами проделанной работы.
Каждый участник готовит презентацию, которая позволяет за выделенные 10 минут наиболее понятно и полно представить полученные результаты. Презентации должны быть представлены на сайтах участников. Там же нужно разместить использованные в ходе подготовке материалы, ссылки, сделанные программы. Участники экзамена, по уважительным причинам пропустившие часть докладов, должны разобраться с материалами этих докладов самостоятельно. Ссылки на страницы с участников экзамена будут расположены ниже.

ТЕМЫ АЛЬТЕРНАТИВНОГО ЭКЗАМЕНА ПО МЛИТА-2009

 

№

Тема работы

Тип

ФИО

Гр.

Результат/

номера выступлений, на которых не присутствовали

 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
37Cравнить два класса алгоритмов:
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
      

 

Другие темы:

1. «Алгоритм вместо доказательства»: алгоритм быстрого нахождения набора, на котором два данных многочлена Жегалкина не совпадают (теоретическая исследовательская задача).

2. Реализация логики в квантовом компьютере (теория).

3. Программа обработки «юридических» текстов на предмет противоречивости, избыточности и возможной оптимизации формулировок (теория + программа).

4. Визуализация преобразований логических выражений на графе, демонстрация кратчайших путей для преобразований одного выражения в другое на основе данного набора преобразований (теория + программа).

5. Проверка условий логических задач в процессе их составления на n-мерном кубе (программа).

6. Схема классов замкнутости как лабиринт: хождение по графу классов замкнутости в поисках минимального класса замкнутости, в который попадает данная функция (программа).

7. Сколько существует тупиковых форм для данной СДНФ от  n  переменных (можно использовать геометрические соображения – граф n-мерного куба). Можно рассмотреть похожие задачи: по данному реберному покрытию найти все минимальные реберные покрытия эквивалентные данному (теория + программа).

8. Тренажёр на классы замкнутости: для предложенного полного набора функций студент находит (наиболее экономное) выражение заданной функции через функции набора (теория + программа).

9. Сравнить трудоемкость доказательства теорем исчисления высказываний через составление таблиц истинности и методом резолюций (теоретическая исследовательская задача).

10. «Мир геометрических фигур» для работы с кванторами (рук. Пухов) (программа).

Пример (http://mathcyb.cs.msu.su/courses/logprog.html): «Каков бы ни был черный куб, лежащий под всеми черными шарами, слева от него не находится ни одного белого шара».
B(x) – «предмет x имеет черный цвет»;
W(x) – «предмет x имеет белый цвет»;
C(x) – «предмет x –  куб»;
S(x) – «предмет x –  шар»;
D(x,y) – «предмет x расположен под предметом y»;
U(x,y) – «предмет x расположен над предметом y»;
L(x,y) – «предмет x расположен слева от предмета y»;
R(x,y) – «предмет x расположен справа от предмета y».


Голубая заливка означает, что тема затронута во взятых работах, но не полностью.

Жёлтая заливка означает, что тема уже "занята".

ВОПРОСЫ и ОТВЕТЫ:

НМ> Сергей Николаевич, а не могли бы Вы объяснить, что подразумевает собой исследовательская задача (на примере темы "Минимизация логических выражений, содержащих только операции отрицания, конъюнкции и скобки" ?
Это подразумевает, что Вы:
1) проведёте исследование с функциями одной и двух переменных для того, чтобы получить представление о возможных упрощениях;
2) найдёте эмпирические алгоритмы упрощения (часть из них очень простые, например, !!x=x); на их основе, возможно, построите алгоритмы, которые будут делать различные частичные упрощения и выбирать из них самое лучшее;
3) поищите в литературе, не решалась ли уже эта задача или похожая;
4) попробуете получить полное теоретическое решение задачи.



Подстраницы (1): Подготовка к МЛиТА-2009
Comments