Сложность решения дискретных задач
Спецсеминар для студентов и аспирантов кафедры математической кибернетики. Проходит по пятницам с 16:20 до 17:55. ауд. 503
Содержание
Тематика семинара
Алгоритмическая сложность задач распознавания свойств дискретных функций, сложность вычисления дискретных функций, сложность полиномиальных представлений дискретных функций, построение и анализ эффективности алгоритмов для решения дискретных задач.
Участники семинара (декабрь 2013 г.)
Руководители
Расписание докладов
Осенний семестр 2014-2015 учебного года
Слушатели семинара: Барбачакова Светлана (518 гр.), Ким Игорь (518 гр.), Плаксина Анна (518 гр.), Хрулев Егор (518 гр.), Гордеев Михаил (418 гр.). В осеннем семестре 2014-2015 учебного года заседания семинара проходят совместно с семинаром Дискретный анализ.
| Дата | Доклад | Докладчик | ||||||||||||||||||||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 17 октября 2014 г. | О сложности функций алгебры логики в классе поляризованных полиномиальных форм. Доклад по статье Н.А. Перязева, "Алгебра и логика", 1995, т. 34, N 3. | Ким Игорь, 518 гр.}
Весенний семестр 2013-2014 учебного годаВ весеннем семестре 2013-2014 учебного года заседания семинара проходят совместно с семинаром Дискретный анализ.
Осенний семестр 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. Получить экспериментальные результаты - простые числа с десятками тысяч десятичных знаков. Выход на суперкомпьютеры не предполагается, студенты пользуются персональными компьютерами.
|
