Сложность решения дискретных задач

Спецсеминар для студентов и аспирантов кафедры математической кибернетики. Проходит по пятницам с 16:20 до 17:55. ауд. 503

Тематика семинара

Алгоритмическая сложность задач распознавания свойств дискретных функций, схемная и мультипликативная сложность вычисления булевых функций, сложность полиномиальных представлений дискретных функций, построение и анализ эффективности алгоритмов для решения дискретных задач.

Руководители

Селезнева Светлана Николаевна

Расписание докладов

Осенний семестр 2013-2014 учебного года

В осеннем семестре 2013-2014 учебного года слушатели семинара выполняют практическое задание. Оно состоит в написании программы построения больших простых чисел по известным алгоритмам и получении экспериментальных результатов. Цель исследований:

1. Изучить быстрые алгоритмы построения больших простых чисел.

2. Написать программу с использованием библиотеки для работы с большими числами.

3. Исследовать, насколько эффективно (с точки зрения времени работы) алгоритм, имеющий хорошую теоретическую оценку временной сложности, работает на практике.

4. Получить экспериментальные результаты - простые числа с десятками тысяч десятичных знаков.

Выход на суперкомпьютеры не предполагается, студенты пользуются персональными компьютерами.

Дата	Вид чисел	Студент
	N = 2 * k * 7^m - 1	Красиков Антон, 518 группа
	N = 2 * 3^m - 1	Плаксина Анна, 418 группа
	N = 2 * k * 3^m - 1	Хрулев Егор, 418 группа
	N = 2 * 2^m - 1	Гордеев Михаил, 318 группа