• 5 июля 2017, среда
  • Москва, ул. Большая Дорогомиловская, д.5к2

Математические семинары. P=NP?

Регистрация на событие закрыта

Извините, регистрация закрыта. Возможно, на событие уже зарегистрировалось слишком много человек, либо истек срок регистрации. Подробности Вы можете узнать у организаторов события.

Другие события организатора

2458 дней назад
5 июля 2017 c 20:00 до 22:00
Москва
ул. Большая Дорогомиловская, д.5к2

В Кочерге продолжается цикл семинаров по теории алгоритмов — науке, которая является свзующим звеном между программированием и абстрактной математикой. Это область с огромным числом нерешенных вопросов, в числе которых одна из проблем тысячелетия — проблема «P=NP?».

В Кочерге продолжается цикл семинаров по теории алгоритмов — науке, которая является свзующим звеном между программированием и абстрактной математикой. Это область с огромным числом нерешенных вопросов, среди которых одна из проблем тысячелетия — проблема «P=NP?».

На первых двух встречах мы обсудили машины Тьюринга и проблему остановки. На третьей и четвертой встречах мы дали определение сложности алгоритма и проанализировали сложность решения классических задач: умножение и деление длинных чисел, нахождение НОД (алгоритм Евклида), проверка на простоту, решение линейных сравнений первой степени, быстрое возведение в степень по модулю, а также нахождение эйлеровых и гамильтоновых циклов в графах, проверка ДНФ и КНФ на выполнимость.

Подробный список пройденного, а также некоторые задачи для самостоятельного обдумывания расположены на страничке: http://mesyarik.ru/17/kocherga_algo...

На ближайшей встрече мы наконец дадим определение класса NP (того самого, о котором идет речь в упомянутой проблеме тысячелетия) и разберемся, почему вопрос о равенстве классов P и NP является столь животрепещущим. Кроме того, рассмотрим новые примеры известных задач из P и из NP, оценим алгоритмическую сложность их решения.

От слушателей ожидается владение математикой и программированием на уровне выпускника 11-го класса профильной школы.


Ведущий — Илья Мещерин, студент 5 курса кафедры дискретной математики МФТИ, студент Школы анализа данных Яндекса.

Встречи проходят по вторникам в 20:00 в антикафе Кочерга.
Мероприятие вконтакте

Регистрация

Рекомендуемые события

Организуете события? Обратите внимание на TimePad!

Профессиональная билетная система, статистика продаж 24/7, выгрузка списков участников, встроенные инструменты продвижения, личный кабинет для самостоятельного управления и еще много чего интересного.

Узнать больше