Сложность решения дискретных задач — различия между версиями
(→Осенний семестр 2014-2015 учебного года) |
|||
| Строка 1: | Строка 1: | ||
[[image:seminar1.jpg|thumb|right|Участники семинара (декабрь 2013 г.)]] | [[image:seminar1.jpg|thumb|right|Участники семинара (декабрь 2013 г.)]] | ||
| − | Спецсеминар для студентов и аспирантов кафедры математической кибернетики. | + | Спецсеминар для студентов и аспирантов кафедры математической кибернетики. В осеннем семестре 2015-2016 учебного года семинар проходит по пятницам с 16:20 до 17:55 в ауд. 503 |
| − | ауд. | + | |
| − | + | ||
| − | + | ||
| − | + | ||
==Руководители== | ==Руководители== | ||
[[Селезнева_Светлана_Николаевна|Селезнева Светлана Николаевна]] | [[Селезнева_Светлана_Николаевна|Селезнева Светлана Николаевна]] | ||
| + | [[Бухман_Антон_Владимирович|Бухман Антон Владимирович]] | ||
| + | |||
| + | == Тематика семинара == | ||
| + | |||
| + | На семинаре изучается алгоритмическая сложность распознавания свойств дискретных функций. | ||
| + | Быстрые алгоритмы обеспечивают эффективность вычислений, а алгоритмическая сложность задачи показывает возможности ее эффективного решения. | ||
| + | |||
| + | На семинаре также изучаются вид, свойства и сложность некоторых представлений дискретных функций. Различные представления дискретных функций и их свойства применяются, например, при построении быстрых алгоритмов, при представлении данных в компьютерах, при проектировании интегральных схем. | ||
| + | |||
| + | При решении перечисленных задач часто возникают графы, комбинаторные множества, поэтому на семинаре уделяется внимание изучению этих дискретных структур. | ||
== Расписание докладов == | == Расписание докладов == | ||
| + | |||
| + | === Осенний семестр 2015-2016 учебного года === | ||
| + | |||
| + | Слушатели семинара: Гордеев Михаил (518/1 гр.), Мельник Марина (418 гр.), Жорина Александра (318 гр.). В осеннем семестре 2015-2016 учебного года заседания семинара проходят совместно с семинаром [[Дискретный анализ]]. | ||
=== Осенний семестр 2014-2015 учебного года === | === Осенний семестр 2014-2015 учебного года === | ||
Версия 22:07, 10 октября 2015
Спецсеминар для студентов и аспирантов кафедры математической кибернетики. В осеннем семестре 2015-2016 учебного года семинар проходит по пятницам с 16:20 до 17:55 в ауд. 503
Содержание
Руководители
Селезнева Светлана Николаевна Бухман Антон Владимирович
Тематика семинара
На семинаре изучается алгоритмическая сложность распознавания свойств дискретных функций. Быстрые алгоритмы обеспечивают эффективность вычислений, а алгоритмическая сложность задачи показывает возможности ее эффективного решения.
На семинаре также изучаются вид, свойства и сложность некоторых представлений дискретных функций. Различные представления дискретных функций и их свойства применяются, например, при построении быстрых алгоритмов, при представлении данных в компьютерах, при проектировании интегральных схем.
При решении перечисленных задач часто возникают графы, комбинаторные множества, поэтому на семинаре уделяется внимание изучению этих дискретных структур.
Расписание докладов
Осенний семестр 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 | Текст программы, Результаты |
