Сложность вычислений ФПМИ
Kanalga Telegram’da o‘tish
Новости курса "Сложность вычислений" для 3 курса ФИВТ МФТИ
Ko'proq ko'rsatish764
Obunachilar
Ma'lumot yo'q24 soatlar
Ma'lumot yo'q7 kun
Ma'lumot yo'q30 kun
Postlar arxiv
Обновлённая программа. Оказалось, что 23 и 25 вопросы были продублированы, так что последний разделён на два.
Дорешка по второй контрольной (результаты проверки в табличке). Принимается до экзамена.
Итоговый список вопросов для экзамена. По сравнению с прошлым годом удалены вопросы про вероятностные алгоритмы на логарифмической памяти, вместо этого включены несложные вопросы 15 и 23. Также в 19 билет добавлено третье определение. Вместо задачи о случайном блуждании включена задача о распознавании древесности на логарифмической памяти. Ещё немного порядок поменялся.
Вторая контрольная пройдёт в среду, 19 декабря, в Большой Химической аудитории. Начало в 12:20. Не опаздывайте, потом там будет к/р по ОКТЧ и зачёт по логике у 1-го курса.
Если кому нужно дополнительное время для проектов, договаривайтесь индивидуально с семинаристами.
Наконец-то готова дорешка по первой к/р. Дедлайн поставил на конец праздников - 9 января, но вообще лучше раньше присылайте.
В табличке появились оценки за все контрольные, кроме двух неподписанных работ. Признавайтесь, кто забыл подписаться.
https://docs.google.com/spreadsheets/d/1AM6BGdfP-xA0RBPGyoT2eNuYROaJ8oiweXeKaiKx1Tc/edit?usp=sharing - сделали табличку по оценкам. Там ещё не все оценки, но уже многие. Там же видно, какая будет формула оценки. А именно, сумма всех баллов за контрольные делится на K (пока в табличке K=26, но это может поменяться в зависимости от получившейся сложности контрольных), добавляется оценка за проект, делённая на 5 и оценка за экзамен, делённая на 2. Всё это сначала округляется до одной десятой, а потом берётся целая часть. (Например, в итоге 5.96 округлится до 6, а 5.94 - до 5). Для любой положительной оценки необходимо получить хотя бы 3 за экзамен, а для отличной оценки - хотя бы 5 за проект.
К сожалению, сегодня семинар в 699 группе не состоится. Можно прийти на проходящий в то же время семинар Михаила Григорьева (15:30, 527 ГК).
Контрольная сегодня пройдёт в обычной лекционной аудитории 117 ГК. Рассадка: не больше 3 человек за 1 партой. Если вдруг придёт больше 81 человека из 84 списочного состава, то можно по 4. Общаться и обмениваться материалами нельзя. Начало в 12:20.
Профессор нашей кафедры Алексей Савватеев борется за приз зрительских симпатий премии "Просветитель". Его можно поддержать вот по этой ссылке: https://m.vk.com/wall-74404187_672899
Обновлённый тренировочный вариант в связи с переносом контрольной - будет задача про PSPACE, а про диагонализацию какая-то одна
Централизованная контрольная будет 14 ноября вместо лекции. Если какие-то группы это по какой-то причине не устраивает, то можно договориться отдельно. Поскольку контрольная сдвинулась, в ней также будет задача про PSPACE-полноту (пройдём сегодня). А про диагонализацию и оракулы будет только одна задача.
Также напоминаю, что сегодня нужно зафиксировать тему проекта, если вы собираетесь его делать. Дальше в любой момент редактирование файла со списком проектов может быть отключено, и после этого взять проект (а значит, и получить "отлично" за курс) будет нельзя.
Предварительная дата первой контрольной: через 2 семинара, т.е. 26/30 октября.
http://www.nada.kth.se/~viggo/problemlist/ - ещё один список NP-полных задач, где можно искать темы для проектов, если из предложенного списка ничего не приглянулось.
