Дискретный анализ, ФИВТ МФТИ, группа 428


Занятия проходят по пятницам c 5.09.2025, 15:30 - 16:55, ауд. 2.36 Физтех-Цифра. О занятиях и зачете/экзамене (прочитайте к 5-12.09; на ДА соотношении лекций, книг и задач к семинарам немного другое). Сценарий экзамена и общие критерии (прочитайте к 7.02.2026, можно и раньше). Необязательные консультации и досдача задач: КПМ-403, пятница между 12.20 и 15.20, желательно сообщить заранее, если планируете прийти. Успехи студентов (участники этой таблицы освобождены* от предварительной части экзамена при S\ge8).
Дорогой друг, Будем благодарны за Ваше пожелание о семинарах по ДА.
Если Вы уже сдали курс - то за отзыв: что стоит сохранить, а что желательно изменить, что оказалось полезным для Вашей дальнейшей учебы и работы, что не оказалось, а чего не хватало. Говорите / пишите и о программе-содержании семинаров, и об уровне-стиле преподавания. По возможности будьте конкретны: по одному-двум Вашим примерам мы поймем Вашу общую мысль, а верно проинтерпретировать общие слова может не получиться. Ваши критические замечания ценны, ибо помогут продумать изменения. То, что нам нравится, мы часто считаем само собой разумеющимся - но не забывайте явно отметить понравившееся, ибо сохранить его может оказаться непросто. Конструктивность (т.е. наличие предложений, а не только критики) приветствуется, но не обязательна.
Будьте осторожны, Ваши пожелания могут быть исполнены! Поэтому желайте то, чего Вам действительно хочется.
Продумывание Вашего пожелания / отзыва разумно совместить с изучением опыта преподавания и обучения, см. литературу и цитаты в поэзии.
Вы можете поговорить с нами, или написать нам лично, или (если важна анонимность) отправить анонимное письмо через старосту или написать в анонимную форму на сайте кафедры. Ваши отзывы не повлияют на Ваши оценки, если Вы их еще не получили.

Решайте задачи на том (высоком) уровне строгости, которому Вы учились на математических курсах (в т.ч. на мат. логике), ср. с текстом <<Как решать задачи этого раздела?>> на стр. 11-13.

Домашние задания (Следите за обновлениями заданий и pdf-файлов книги! Окончательны только задания с жирными датами. Номера по электронной версии книги. Бумажная версия книги доступна в библиотеке МФТИ.)

К 5.09.2025: 3ab, 4a, 2b, 5a, 6a, 7a* из п. 1.1 и 1.4.1*, 1.4.3a.
К 12.09: 3a, 4a, 5e*, 6bc, 8bd из п. 1.1 и 1.4.3b*, 1.4.4, 1.4.7сd (доказывайте использованные Вами утверждения из линейной алгебры) и 6.1.1ba (без использования формулы Стирлинга).
К 19.09: 1.4.3b*, 1.4.7df (доказывайте использованные Вами утверждения из линейной алгебры), 1.4.9, 6.1.1dce*, 6.1.3ba (без использования формулы Стирлинга), 6.1.4bac.
К 26.09: 1.4.7g, 1.4.8a* и (Пусть f_j(n) = O(1) при n\to\infty для каждого j. Обязательно ли f_1(n) + f_2(n) + ... + f_n(n) = O(n) при n\to\infty?) и 4bcd*, 5ba, 6ba, 7b, 8b, 9b из п. 6.1 (без использования не доказанных Вами утверждений про e; только в задаче 7b можно пользоваться без доказательства формулой Стирлинга; подсказка к 6.1.6a).
К 3.10: 5a, 10ab, 11ace* (без использования формулы Стирлинга) из п. 6.1 и 1.4.8a* и 2.1.1, 2.1.2a, 2.2.1abc, 2.2.2a.
К 10.10: 6.1.d*f*, 2.2.4abcdef, 2.2.3a, 2.2.5abc. Попробуйте программу Prufer или Prufer code decoder, Bracket sequence from [rooted] tree.
К 17.10: 2.2.4g*, 2.2.5bd*e*, 2.2.6ab, 2.3.4, 2.3.5 (явно стройте отображения), 2.4.4ab, 2.4.3ac, 2.4.5a (здесь и далее в п. 2.4 используйте без доказательства формулу Эйлера).
К 24.10: 2.2.5b, 2.3.5 (явно стройте отображения) и 3bd, 5abd*, 1ab*c, 6ab*, 7.5, 8.33, 9.5 из п. 2.4.
К 31.10: 1a, 3abcd, 4b*d, 5b, 6a, 7 из п. 2.5 и 2.6.1ab, 2.4.5d*.
К 7.11: 2.5.7 и 1bc, 2abcd, 4abcd, 3, 5ab*c* из п. 2.6.
К 14.11: 2.6.7ab, 2.7.1abc, 2.7.2ab, 2.7.3, 2.7.4abc.
К 21.11: 7.1.4a и 2abcd*, 3, 4abcd, 5a, 6 из из п. 2.7 и 3.1.1. 3.1.3, 3.1.10.
К 28.11: 2.7.4cd, 2.7.6 и 1, 2bс*, 3ab, 5a из п. 3.2 и 1ab, 2ab, 7, 8a* из п. 1.5 (1.5 по электронной версии; в бумажной версии это п. 1.6). Попробуйте программу Chromatic number.
К 5.12: 2.7.4c, 2.7.6, 1.5.2b, 5.1.2ab, 5.1.3ab и 3ab, 4, 5abce из п. 6.3. Готовьтесь к контрольной работе на 15-20 минут, прорешивая задачи и прочитав типичное пояснение (а дальше уж и без предупреждения).
К 12.12: 2.7.6, 5.1.3ab и 5f, 6, 3dc, 7ab, 8b, 9ab, 10a из п. 6.3.
Изучалось ранее: 1a*b*, 11a, 13a, 14a, 3(d=>c), 13b*, 14b из п. 6.3 и 2abc, 3a, 4bcd из п. 7.1. 6.3.11b*, 6.3.13b* и 4cd, 5сdbac'd'b'a' из п. 7.1. 2.4.1d* 2.5.5c*, 2.7.1d*,

К 7.02.2025: 5сdba, 6a, 2d*, 3b* из п. 7.1 и 3, 4bca, 5 из п. 7.3.
К 14.02: 7.3.4a, 7.3.2, 7.3.1* и 1(439,43'), 2abcd, 3a*, 4a, 5abc из п. 4.1.
К 21.02: 7.3.1*, 4.1.4c*, 4.1.6abc, 4.1.7a, 4.2.1ab, 4.2.2abc, 4.2.5a, 4.2.7a. 1c из [BS]
К 28.02: 4.1.6c, 4.2.3*, 4.2.5b с(x^5+y^5=z^5 mod достаточно большого простого p=5k+1), 4.2.7b*, 4.3.3bca, 4.3.1. И по [ZSS]: 3.5.3bc, 3.5.4b, 3.5.5a (не используя существования первообразного корня). И [В 2025 году на физтехе выступило несколько поэтов. От каждого из них зафанатели ровно 8 из 19 студентов 323 группы. (Один студент вполне мог зафанатеть от нескольких поэтов.) Никакие два поэта не имеют ровно трех общих фанатов (в 323 группе). Наборы фанатов разных поэтов различны. Могло ли выступить более 11000 поэтов?]
К 7.03: 4.2.5с (x^5+y^5=z^5 mod достаточно большого простого p=5k+1), 4.2.6, 4.2.4, 4.3.4abсd*, 4.3.2d*, 4.4.6a, 6.2.2a, 6.2.4a, 6.2.9a и [ZSS, 9.2.21].
К 14.03: 4.2.4, 4.3.4b, 4.4.6b* (подсказка: [Sk14, \S2.4]), 4.4.5d* и 8ab, 9bc, 10, 12abcd из п. 6.2.
К 21.03: 13ab, 14ab, 1b (используя 15 без док-ва), 15, 2b из п. 6.2 и 4.4.5d*, 4.4.6b* (подсказка: [Sk14, \S2.4]) и по [LS] (сначала пробуйте самостоятельно): 2ab, 1, 2'a и решите задачу из Вашего варианта контрольной работы 7.03.
К 28.03: 1b (используя 15 без док-ва), 15, 2b, 3b из п. 6.2 и (следующая часть задания засчитывается только тем, кто сделал хотя бы два пункта из предыдущей) по [LS] (сначала пробуйте самостоятельно): 2'b, 4ab, 3, 4'ab, 6ab, 6'ab.
К 4.04: (решите задачу из Вашего варианта контрольной работы 21.03) и 2b, 4b, 3b из п. 6.2 (подсказка: используйте - если доказали - 6.2.15 и аналог утверждения 6.2.10) и (следующая часть задания засчитывается только тем, кто сделал хотя бы два пункта из предыдущей) по [LS] (сначала пробуйте самостоятельно): 6'ab, 5, 8b, 7ab, 12a*.
К 11.04: 1ab, 3ab, 4a*, 5abc, 6acdef* из п. 5.2.
К 18.04: 5.2.6acdeb* и 1ab, 2, 3, 4, 5abc*, 6a, 8a из п. 5.3 и (решите задачу из Вашего варианта контрольной работы 4.04).
К 25.04: 5.3.4, 5.3.8a, 5.3.6b* и 1kn, 2, 3ab, 4ab из п. 5.4 и 5.5.1ab, 5.5.2abc.
Ко 2.05: 5.4.4b и 3bc, 4ad* (вопрос в d только про a), 6ab, 7, 9, 8ab из п. 5.5 и 7.2.1 (докажите использованные результаты линейной алгебры), и (решите задачу из Вашего варианта контрольной работы 18.04).
К 16.05: 7.2.1, 7.2.9 и 5, 4 из [BS] и 4, 8 из статьи А. А. Полянский, П. Б. Тарасов, Избранные задачи экзамена по дискретному анализу, стр. 206-207 и 1.2.2, 1.3.5b, 1.3.7b, 1.3.6, 1.3.5a, 2.1.1a*, 2.1.2a* из [MNS] и [Sk18, Lemma 6]. Как всегда (и как на контрольной-экзамене), попытайтесь решить самостоятельно, и только потом смотрите кусочки решений.
Задачи для необязательного самостоятельного изучения (они разбирались на семинарах прошлых лет): 10, 14 из статьи А. А. Полянский, П. Б. Тарасов, Избранные задачи экзамена по дискретному анализу, стр. 206-207. [Sk18, Lemma 7]
Успехов на экзамене! Rambler's Top100