Сложность решения дискретных задач
Спецсеминар для студентов и аспирантов кафедры математической кибернетики. Проходит по пятницам с 16:20 до 17:55. ауд. 503
Тематика семинара
Алгоритмическая сложность задач распознавания свойств дискретных функций, схемная и мультипликативная сложность вычисления булевых функций, сложность полиномиальных представлений дискретных функций, построение и анализ эффективности алгоритмов для решения дискретных задач Невозможно разобрать выражение (лексическая ошибка): k<math>. ==Руководители== [[Селезнева_Светлана_Николаевна|Селезнева Светлана Николаевна]] == Расписание докладов == === Осенний семестр 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. Получить экспериментальные результаты - простые числа с десятками тысяч десятичных знаков. Выход на суперкомпьютеры не предполагается, студенты пользуются персональными компьютерами. {| class="wide" width="100%" ! Студент ! Вид чисел ! Результаты |- |Красиков Антон, 518 группа | N = 2 * k * 7^m - 1 |[[Media:primes.txt|Файл с простыми числами]] |- | Плаксина Анна, 418 группа | N = 2 * 3^m - 1 |[[Media:plaksina.pdf|Текст программы и результаты]] |- | Хрулев Егор, 418 группа | N = 2 * k * 3^m - 1 |[[Media:khrulev1.pdf|Текст программы]], [[Media:khrulev2.pdf|Результаты]] |- | Гордеев Михаил, 318 группа | N = 2 * 7^m - 1 |[[Media:gordeev1.pdf|Текст программы]], [[Media:gordeev2.pdf|Результаты]] |} [[Категория:Спецсеминары кафедры математической кибернетики]]
