Курс посвящен теории сложности доказательств логики высказываний. Эта область тесно связана как с важными открытыми вопросами теории сложности вычислений, так и с практическими приложениями, такими как автоматическое доказательство теорем и верификация микропроцессоров.
Наряду с введением в теорию сложности доказательств, курс содержит доказательства нижних оценок для конкретных систем доказательств (резолюция, секущие плоскости, алгебраические доказательства и др.). Будут также затронуты вопросы автоматического поиска доказательств, связь с коммуникационной сложностью и криптографическими генераторами случайных чисел.
Студенты 2-6 курсов, специализирующиеся в области математики и/или информатики, приглашаются принять участие в 7-й русско-немецкой школе JASS в курсе "Propositional proof complexity". Участие в школе дает Вам возможность заниматься изучением современной теоретической информатики под руководством действующих ученых, практиковаться в общении на английском языке, знакомиться и общаться с немецкими студентами. Школа проводится при содействии Санкт-Петербургского отделения Математического института им. В.А.Стеклова РАН, Санкт-Петербургского государственного университета и Технического Университета г. Мюнхена. Участие в школе бесплатное (в том числе, участников будут бесплатно кормить обедами).
Желающим принять участие в курсе "Propositional proof complexity", необходимо отправить заявку по адресу jass09 "at" logic.pdmi.ras.ru, указав в ней следующие сведения:
К сожалению, число участников, которые могут принимать участие в курсе, ограничено, поэтому среди приславших заявки будет проведен конкурсный отбор, в котором Вы должны будете продемонстрировать свою математическую подготовку и способность делать презентации на английском языке. Тестовое задание будет выслано зарегистрировавшимся участникам по электронной почте.
Рабочий язык школы: английский
Крайний срок подачи заявки: 18-ое февраля 2009 г.
Окончательный состав участников: 1-ое марта 2009 г.
Даты школы: 29.03-07.04.2009
Контакты: Все вопросы задавайте по электронной почте jass09 "at" logic.pdmi.ras.ru