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

Версия 19:21, 10 февраля 2017

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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