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

Материал из Кафедра математической кибернетики
Перейти к: навигация, поиск
(Осенний семестр 2013-2014 учебного года)
(Осенний семестр 2013-2014 учебного года)
Строка 36: Строка 36:
 
| Плаксина Анна, 418 группа
 
| Плаксина Анна, 418 группа
 
| N = 2 * 3^m - 1
 
| N = 2 * 3^m - 1
|
+
|[[Media:plaksina.pdf|Текст программы и результаты]]
 
|-
 
|-
 
| Хрулев Егор, 418 группа
 
| Хрулев Егор, 418 группа
 
| N = 2 * k * 3^m - 1
 
| N = 2 * k * 3^m - 1
|
+
|[[Media:khrulev1.pdf|Текст программы]], [[Media:khrulev2.pdf|Результаты]]
 
|-
 
|-
 
| Гордеев Михаил, 318 группа
 
| Гордеев Михаил, 318 группа
 
| N = 2 * 7^m - 1
 
| N = 2 * 7^m - 1
|
+
|[[Media:gordeev1.pdf|Текст программы]], [[Media:gordeev2.pdf|Результаты]]
 
|}
 
|}
  

Версия 15:54, 20 декабря 2013

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

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

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

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

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

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

Осенний семестр 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 Файл с простыми числами
Плаксина Анна, 418 группа N = 2 * 3^m - 1 Текст программы и результаты
Хрулев Егор, 418 группа N = 2 * k * 3^m - 1 Текст программы, Результаты
Гордеев Михаил, 318 группа N = 2 * 7^m - 1 Текст программы, Результаты