Сложность решения дискретных задач — различия между версиями
(→Расписание докладов) |
(→Расписание докладов) |
||
| Строка 15: | Строка 15: | ||
=== Весенний семестр 2013-2014 учебного года === | === Весенний семестр 2013-2014 учебного года === | ||
| + | |||
| + | В весеннем семестре 2013-2014 учебного года заседания семинара проходят совместно с семинаром [[Дискретный анализ]]. | ||
{| class="wide" width="100%" | {| class="wide" width="100%" | ||
| Строка 23: | Строка 25: | ||
| 21 февраля 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 гр.) | ||
| + | } | ||
Версия 21:58, 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. Получить экспериментальные результаты - простые числа с десятками тысяч десятичных знаков. Выход на суперкомпьютеры не предполагается, студенты пользуются персональными компьютерами.
|
