Сложность решения дискретных задач — различия между версиями
(→Расписание докладов) |
(→Расписание докладов) |
||
| Строка 34: | Строка 34: | ||
| О длине булевых функций в классе полиномиальных форм с аффинными множителями в слагаемых. Доклад по статье Селезневой С.Н. | | О длине булевых функций в классе полиномиальных форм с аффинными множителями в слагаемых. Доклад по статье Селезневой С.Н. | ||
| Гордеев Михаил (318 гр.) | | Гордеев Михаил (318 гр.) | ||
| − | } | + | |} |
Версия 22:00, 10 марта 2014
Спецсеминар для студентов и аспирантов кафедры математической кибернетики. Проходит по пятницам с 16:20 до 17:55. ауд. 503
Содержание
Тематика семинара
Алгоритмическая сложность задач распознавания свойств дискретных функций, схемная и мультипликативная сложность вычисления булевых функций, сложность полиномиальных представлений дискретных функций, построение и анализ эффективности алгоритмов для решения дискретных задач.
Участники семинара (декабрь 2013 г.)
Руководители
Расписание докладов
Весенний семестр 2013-2014 учебного года
В весеннем семестре 2013-2014 учебного года заседания семинара проходят совместно с семинаром Дискретный анализ.
| Дата | Доклад | Докладчик |
|---|---|---|
| 21 февраля 2014 г. | Организационное заседание семинара | |
| 14 марта 2014 г. | О мультипликативной сложности квадратичных булевых функций. Доклад по статье Mirwald R., Schnorr C.P. The multiplicative complexity of quadratic boolean forms // Theoretical Computer Science. 102. 1992. P. 307-328. | Плаксина Анна (418 гр.) |
| 21 марта 2014 г. | О длине булевых функций в классе полиномиальных форм с аффинными множителями в слагаемых. Доклад по статье Селезневой С.Н. | Гордеев Михаил (318 гр.) |
Осенний семестр 2013-2014 учебного года
В осеннем семестре 2013-2014 учебного года слушатели семинара выполняют практическое задание. Оно состоит в написании программы построения больших простых чисел по алгоритмам из работы Садовник Е.В. Проверка на простоту некоторых чисел вида 2kp^m-1 // Дискретная математика, 2006, т. 18, вып. 1, с. 146-155 (http://www.mathnet.ru/php/archive.phtml?wshow=paper&jrnid=dm&paperid=38&option_lang=rus) и получении экспериментальных результатов. Цели исследований:
1. Изучить быстрые алгоритмы построения больших простых чисел.
2. Написать программу с использованием библиотеки для работы с большими числами.
3. Исследовать, насколько эффективно (с точки зрения времени работы) алгоритм, имеющий хорошую теоретическую оценку временной сложности, работает на практике.
4. Получить экспериментальные результаты - простые числа с десятками тысяч десятичных знаков.
Выход на суперкомпьютеры не предполагается, студенты пользуются персональными компьютерами.
| Студент | Вид чисел | Результаты |
|---|---|---|
| Красиков Антон, 518 группа | N = 2 * k * 7^m - 1 | Текст программы, Результат №1, Результат №2 |
| Плаксина Анна, 418 группа | N = 2 * 3^m - 1 | Текст программы и результаты |
| Хрулев Егор, 418 группа | N = 2 * k * 3^m - 1 | Текст программы, Результаты |
| Гордеев Михаил, 318 группа | N = 2 * 7^m - 1 | Текст программы, Результаты |
