Извините, регистрация закрыта. Возможно, на событие уже зарегистрировалось слишком много человек, либо истек срок регистрации. Подробности Вы можете узнать у организаторов события.
В Кочерге продолжается цикл семинаров по теории алгоритмов — науке, которая является свзующим звеном между программированием и абстрактной математикой. Это область с огромным числом нерешенных вопросов, в числе которых одна из проблем тысячелетия — проблема «P=NP?».
В Кочерге продолжается цикл семинаров по теории алгоритмов — науке, которая является свзующим звеном между программированием и абстрактной математикой. Это область с огромным числом нерешенных вопросов, в числе которых одна из проблем тысячелетия — проблема «P=NP?».
За прошедшие три встречи мы обсудили формальное определение алгоритма как машины Тьюринга; доказали из соображений теории множеств, что не все функции вычислимы; сформулировали классическую неразрешимую задачу — проблему остановки — и доказали ее неразрешимость.
Более подробный список рассказанного, а также задачи по темам лекций и ссылки на литературу есть на странице http://mesyarik.ru/18/kocherga_algo....
В следующий раз продолжим говорить о неразрешимых проблемах. А именно, рассмотрим интересную (и на первый взгляд не связанную с проблемой остановки) проблему "равенства слов в полугруппах". Следствием из ее неразрешимости оказывается теорема Чёрча о том, что для формул с кванторами невозможно алгоритмически проверить их общезначимость (т.е. тождественную истинность). Всё это постепенно подводит нас к знаменитой теореме Гёделя о неполноте.
Ведущий — Илья Мещерин, студент 6 курса кафедры дискретной математики МФТИ, студент Школы анализа данных Яндекса.
***
Встречи проходят по понедельникам, в 20:00, в антикафе Кочерга.