Сложность вычислений ФПМИ
رفتن به کانال در Telegram
764
مشترکین
اطلاعاتی وجود ندارد24 ساعت
اطلاعاتی وجود ندارد7 روز
اطلاعاتی وجود ندارد30 روز
آرشیو پست ها
Готово второе домашнее задание. В нём нет разницы по максимальному числу зачтённых задач со сделанным проектом и без него. Рекомендую посмотреть на задачи и решить, не хотите ли вы всё-таки написать проект. Запись ещё открыта. Срок сдачи задания пока не ставлю, принимаются предложения по нему.
Также я всё-таки сделал список проектов, приглашаю желающих выбрать себе тему на втором листе таблички: https://docs.google.com/spreadsheets/d/12ApZWYJQSgR4HAWgosn4kFy8u7V0wZqHZbNNYZ52b9M/edit?usp=sharing
Список составлен так: взяты осенние темы, которые никто на курсе не взял, также добавлен ряд новых, как по темам весеннего курса, так и других. Алгоритмических тем в списке в этот раз нет, но если придумаете что-нибудь отличное от осеннего списка, то можно сделать.
Проект ничего не блокирует, но позволяет заменить часть задач из домашки.
Выкладываю текущую версию книги. Что нового:
- почти написана первая обзорная глава, там много интересного материала
- почти написано доказательство экспоненциальной PCP-теоремы
- отдельные исправления ошибок и дополнения в других главах.
Сегодня, 4 мая, лекции тоже не будет - я в отъезде, провести онлайн нет возможности. 11 мая сделаем последнюю лекцию - думаю, доразберёмся с MIP=NEXP. Про рациональные доказательства можно сделать дополнительную лекцию 18-го, если будет запрос. В к/р этой темы не будет, но в домашку одну задачу включу.
Как и обещал, выкладываю первую домашку. В файле индивидуальные варианты. Если вас нет в списке, берите один из запасных в конце файла и сообщите мне. Там сказано про проекты, постараюсь их список тоже выложить сегодня-завтра. Проект можно сделать вместо решения части задач (примерно четырёх), итоговую оценку он не ограничивает. Срок сдачи в файле не написан, предлагаю 12 мая (это для задач, для проектов позже).
Сегодня постараюсь выложить первую домашку. Пока что сделал табличку для оценок, оттуда же буду брать данные для индивидуальных вариантов. Там сейчас только бакалавриат кафедры ДМ. Если вы из магистратуры или с другой кафедры и сдаёте курс, напишите мне имя и номер группы, чтобы я добавил.
Ссылка: https://docs.google.com/spreadsheets/d/12ApZWYJQSgR4HAWgosn4kFy8u7V0wZqHZbNNYZ52b9M/edit?usp=sharing
Приглашаю поучаствовать в математическом квесте "Интеграл по городу", который пройдёт в Майкопе (Адыгея) и онлайн 11-12 марта. Суть квеста - поиск различных объектов в городе или в интернет-источниках (панорамах, фотосайтах и т.д.) и решение математических задач, данные для которых нужно найти на этих объектах. Задачи не используют высшую математику, так что доступны старшим школьникам - зовите друзей-нематематиков или младших братьев и сестёр (а половина заданий не требуют математики вообще).
11 марта будут короткие категории "Тьюринг" онлайн и "Евклид" в городе, начало в 15:30, окончание в 18:00. 12 марта - длинные категории "Колмогоров" онлайн и "Лобачевский" в городе, начало в 10:00, окончание в 18:30. Можно участвовать командами от 1 до 6 человек.
Подробности и регистрация по ссылке https://www.runcity.org/ru/events/maykop2023/
Участие стоит 961 рубль с команды или бесплатно по промокоду mipt. Если кто-то захочет добраться до Майкопа и понадобится помощь, пишите в личку.
Закреплённый пост со служебной информацией, весна 2023
Расписание:
Лекции - четверг, 10:45-13:00, 113 ГК.
Ресурсы для студентов:
https://t.me/diht_complexity - этот канал
https://t.me/+_zvpm0_mwVwwZThi - чат к каналу
https://www.dropbox.com/sh/r46j99n2ujdfjhm/AADMtzp7AVXyX9oZWnZOGoNja?dl=0 - папка с материалами
Статья про нулевое разглашение для детей, про которую я говорил сегодня на лекции.
Сегодня будет вводная лекция, по крайней мере первую пару из полутора. На ней я неформально расскажу про основные темы курса, в том числе опишу решения таких задач:
1) Как убедить недоверчивого дальтоника, что в остальном одинаковые предметы имеют разный цвет.
2) Как гениальному археологу доказать назойливой прессе открытие древнего заклинания, не разгласив его.
3) Как записать математическое доказательство, чтобы для его проверки было достаточно прочесть лишь несколько битов, и при чём здесь задачи аппроксимации.
4) Как заставить жадного владельца облачного сервера проводить именно те вычисления, которые нужны клиенту.
Приходите, лекция уже скоро!
Кто не сдавал экзамен, но хочет сдать, напишите мне в личку, выберем дату. Особенно если хотите сдавать в первой половине февраля.
В новом семестре этот канал будет использоваться для курса дополнительных глав сложности вычислений. Он будет проходить по четвергам с 10:45 до 13:05 (полторы пары) в 113 ГК. Этот курс обязательный для кафедры ДМ и факультативный для всех остальных. В том числе он входит в пул курсов по выбору на 5-м курсе магистратуры бывшего фупма, так что название канала актуализирую. Программа нового курса и прочие подробности будут чуть позже.
Комментарий по датам экзамена:
- предварительные даты есть в таблице с результатами.
- можно без ограничений меняться датами друг с другом.
- если ваша группа в табличке отличается от "официальной", то можно перенести на тот день, когда сдаёт "официальная"
- на 23-е получается много сдающих и мало экзаменаторов. Так что с 23-го можно переносить в любом направлении, первые 15 заявок будут удовлетворены, дальше не факт.
- если уже знаете, что вообще не сможете прийти по любой причине, напишите, пожалуйста
- если хотите перенести или есть особые обстоятельства, не покрытые пунктами выше, пишите мне в личку
Хотелось бы финализировать список сдающих 21-го завтра (20-го) днём, тогда я расставлю по времени согласно текущему рейтингу (чем он выше, тем раньше заход). Потом тоже можно будет ещё поменяться временем или перенести по уважительной причине.
А вот теперь готова и вторая дорешка. В файле задачи сразу по обеим контрольным - переписывание второй и домашняя третья.
Комментарии:
- в части групп так и не проверена вторая к/р, я попросил семинаристов проверить как можно быстрее. Пока даны все задачи, можете решать те, которые не решали на к/р.
- задача оценивается из 5 баллов, если вы были на к/р, но не решили, из 8 баллов, если пропустили к/р по уважительной причине, и из 10 баллов, если задача ранее не давалась (это задачи из 3-й к/р и 2 из 3 задач 12-14).
- последняя задача из 3-й к/р затрагивает тему, которой не было в курсе. Можно её изучить самостоятельно по моей книге или другим источникам.
- формула перевода баллов за задачи в итоговую оценку слегка пересмотрена и стала нелинейной. Порог на 1 балл снизился и теперь равен 36, на 2 балла не изменился и равен 80, на 3 балла повысился и теперь равен 132, в промежутках линейная интерполяция. Можно и больше 3 баллов набрать, там наклон ещё круче.
Готова предварительная версия программы экзамена, а также теоропроса для зачёта. В тексте возможны опечатки и несуразности, пишите, если заметите - поправим.
Информация по зачёту для студентов магистратуры блокчейн. Я получил одобрение на его выставление вплоть до конца экзаменов. Так что можно будет сдавать теоропрос либо на неделе 9-13 января, либо с основными экзаменами 21-24 января. Если оба варианта не подходят, пишите - попробуем согласовать другой вприант. Программу постараюсь сделать в начале следующей недели.
Рассадка в Б. Хим. на сегодня. Начинаем в 14:00, не опаздывайте.
Левая часть: места 2-4 на рядах 1-12 и 1-4 на рядах 13-17
Средняя часть: места 5-6 на 1-м ряду и 5-8 на остальных
Правая часть: места 9-11 на рядах 1-12 и 9-12 на рядах 13-17.
Контрольная пройдёт по той же схеме, что и первая. Примерно в 13 часов вывешу рассадку, не позже 14:00 постараюсь раздать работы. Будет выдан 1 лист с условием и 1 подписанный пустой лист, решения можно записывать на обоих, а также на своих пустых листах. Немного дополнительных листов тоже принесу. Пользоваться материалами и/или гаджетами нельзя. Если пропускаете по уважительной причине, пишите об этом до начала контрольной.
