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