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

Материал из Кафедра математической кибернетики
Перейти к: навигация, поиск
(Тематика семинара)
(Тематика семинара)
Строка 17: Строка 17:
 
При решении перечисленных задач часто возникают графы, комбинаторные множества, поэтому на семинаре также уделяется внимание изучению этих дискретных структур.
 
При решении перечисленных задач часто возникают графы, комбинаторные множества, поэтому на семинаре также уделяется внимание изучению этих дискретных структур.
  
[[Media:seminar-selezn-2015.pdf|Информация для студентов 2-го курса]]
+
[[Media:2-2015-selezn.pdf|Информация для студентов 2-го курса]]
  
 
== Расписание докладов ==
 
== Расписание докладов ==

Версия 22:35, 10 октября 2015

Участники семинара (декабрь 2013 г.)

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

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

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

Бухман Антон Владимирович

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

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

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

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

Информация для студентов 2-го курса

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

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

Слушатели семинара: Гордеев Михаил (518/1 гр.), Мельник Марина (418 гр.), Жорина Александра (318 гр.). В осеннем семестре 2015-2016 учебного года заседания семинара проходят совместно с семинаром Дискретный анализ.

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

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

Дата Доклад Докладчик
28 ноября 2014 г. Хрулев Егор, 518 гр.
31 октября 2014 г. О сложности функций k-значной логики в классе поляризованных полиномиальных форм.

Доклад по статье С.Н. Селезневой, "Дискретная математика", 2002.

Гордеев Михаил, 418 гр.
10 октября 2014 г. О сложности функций алгебры логики в классе поляризованных полиномиальных форм.

Доклад по статье Н.А. Перязева, "Алгебра и логика", 1995, т. 34, N 3.

Ким Игорь, 518 гр.

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

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

Дата Доклад Докладчик
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. Получить экспериментальные результаты - простые числа с десятками тысяч десятичных знаков.

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

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