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

[[image:seminar1.jpg|thumb|right|Участники семинара (декабрь 2013 г.)]]

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

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

==Руководители==
[[Селезнева_Светлана_Николаевна|Селезнева Светлана Николаевна]]

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

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

Слушатели семинара: Мельник Марина (318 гр.), Ким Игорь (518 гр.), Плаксина Анна (518 гр.), Хрулев Егор (518 гр.), Гордеев Михаил (418 гр.). В осеннем семестре 2014-2015 учебного года заседания семинара проходят совместно с семинаром [[Дискретный анализ]].

{| class="wide" width="100%"
! Дата
! Доклад
! Докладчик
|-
| 10 октября 2014 г.
| О сложности функций алгебры логики в классе поляризованных полиномиальных форм. 
Доклад по статье Н.А. Перязева, "Алгебра и логика", 1995, т. 34, N 3.
| Ким Игорь, 518 гр.
|-
|}

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

В весеннем семестре 2013-2014 учебного года заседания семинара проходят совместно с семинаром [[Дискретный анализ]].

{| class="wide" width="100%"
! Дата
! Доклад
! Докладчик
|-
| 28 марта 2014 г.
| 
| Хрулев Егор (418 гр.)
|-
| 21 марта 2014 г.
| О длине булевых функций в классе полиномиальных форм с аффинными множителями в слагаемых. Доклад по статье Селезневой С.Н.
| Гордеев Михаил (318 гр.)
|-
| 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 г.
| Организационное заседание семинара
|
|}

=== Осенний семестр 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:prog.pdf|Текст программы]], [[Media:primes_krasikov.pdf|Результат №1]], [[Media:big_primes_krasikov.pdf|Результат №2]]
|-
| Плаксина Анна, 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|Результаты]]
|}



[[Категория:Спецсеминары кафедры математической кибернетики]]