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

Занятия проходят по вторникам cо 2.02.2021, 10:45-12:10, ауд. 113ГК. О занятиях и экзамене/зачете. Успехи студентов.
Решайте задачи на том (высоком) уровне строгости, которому Вы учились на математических курсах (в т.ч. на мат. логике), ср. с приведенным в книге первым доказательством правила Паскаля 1.1.2a (=1.1.2.1).
Отмечайте (цифрой 1) в расшаренном гуглшите (excusez mon russe) задачи, которые готовы рассказать на занятии. В 10.40 я закрываю гуглшит и до 10.45 пишу / говорю, кто что готовит рассказывать к 10.50.

Домашние задания
Следите за обновлениями заданий и pdf-файлов книги! Окончательны только задания с жирными датами. Номера по электронной версии книги. Бумажная версия книги доступна в библиотеке МФТИ.
Ко 2.02.2021: 5abcd, 5a'b'c'd', 6a из п. 7.1 и 1*, 4, 5, 6, 3, 2* из п. 7.3 и 1(439,43'), 2abcd из п. 4.1.
К 9.02: 3a, 4ab*, 5ab, 6ab, 7ab, 8 из п. 4.1 и 4.2.1abc*.
К 16.02: 4.1.7c и 1c*, 2abc, 3, 7abc*, 5abс из п. 4.2 и 3.5.3bc.
К 2.03: 3.5.3de и 5de, 6, 4* из п. 4.2 и 1, 3bca, 2bc*, 4abсd* из п. 4.3 и 4.4.1ab.
К 9.03: 4.3.2d, 4.3.4a, 4.5.1 и 2*, 3ab*, 5abd, 6a'b* из п. 4.4 и 1a, 2a, 4a, 9ab из п. 6.2.
К 16.03: 10abc, 11, 12bcdef, 13abc, 14a из п. 6.2 и 4.4.5e*, 4.4.6c*.
К 23.03: 14bc, 1b (используя 15 без док-ва), 15, 2b из п. 6.2 и 4.4.4a*b* и 1ab, 3ab, 5ab из п. 5.2.
К 30.03: 1b, 3b, 4b из п. 6.2 и 4a*b*, 5c, 6abcde из п. 5.2 и 8.5.2ac* (используя аналитическое определение компактности).
К 6.04: лемма о независимости для раскрасок и 18a, 20c*, 22a из п. 6.2 и 8.5.2c* (подсказка: дочь раскраски n стран - продолжающая ее раскраска n+1 страны) и 5.2.6cef* и 1ab, 2, 3 из п. 5.3. Готовьтесь к 15-20-минутной контрольной работе, прорешивая задачи.
К 13.04: 6.2.4c*, 22b*, 27 из п. 6.2 и приготовьте к сдаче задачи 5.3.1.ab и 4, 5abc*, 6a, 8a из п. 5.3 и 1kn, 2 из п. 5.4.
6.2.27. {\it КНФ-формула} --- конъюнкция набора дизъюнкций нескольких из переменных $x_1,\dots,x_n$ и их отрицаний. Если в каждом <<сомножителе>> КНФ-формулы ровно $k$ <<слагаемых>> и у каждого <<сомножителя>> есть общие переменные не более чем с $2^{k-2}$ другими, то булева функция, определяемая формулой, не является тождественным нулем.
К 20.04: 5.3.6b* и 3ab, 4ab из п. 5.4 и 5.5.1ab.
К 27.04: Приготовьте к сдаче задачи 5.3.1.ab, 5.3.4, 5.3.5с, 5.4.4a (если у Вас стоит 1; отречься на 0 можно по эл. почте до семинара) и 2abc, 3bc, 4ad (вопрос в d только про a), 6ab, 7 из п. 5.5.
К 4.05: 8ab*, 9 из п. 5.5 и 1 (докажите использованные результаты линейной алгебры), 2[2,4,8,16,12], 3abcd, 9* из п. 7.2.
К 11.05: 4ab*, 5[2a,ab,4k,(8k+4)*], 6, 7, 8ab, 9 из п. 7.2.

К первому занятию 1.09.2020: 2b, 3ab, 4a, 5a, 6a, 7a* из п. 1.1 и 1.4.1*, 1.4.3a.
К 8-9.09: 3b*, 4, 6b, 7bс из п. 1.4 (доказывайте использованные Вами утверждения из линейной алгебры!) и 1bd, 4ab, 5ab из п. 6.1 (без использования не доказанных Вами утверждений про e и формулы Стирлинга).
К 16.09: 5de, 6bc из п. 1.1 и 3b*, 7de*f из п. 1.4 (доказывайте использованные Вами утверждения из линейной алгебры!) и 1e*, 4cde, 6ba, 7a из п. 6.1 (без использования формулы Стирлинга и не доказанных Вами утверждений про e).
К 23.09: 1.4.7fg* и 4e, 7bcd*, 8ba, 9ba, 10b, 11b, 12a, 13a из п. 6.1 (без использования не доказанных Вами утверждений про e; только в задаче 10b можно пользоваться формулой Стирлинга).
К 30.09: 1e*, 7d*, 13b, 14ace, 15a* из п. 6.1 (без использования не доказанных Вами утверждений про e и формулы Стирлинга) и 1.1.4a, 2.1.1, 2.1.2a и 1abc, 2a, 4ab из п. 2.2.
К 7.10: 4сd, 3ab*, 5ab, 6ab из п. 2.2 и 3a, 4, 5 из п. 2.3 и 6.1.14cd, 6.1.15a*b*. Попробуйте программу Prufer или Prufer code decoder.
К 14.10: 2b, 3acd, 4ab, 5a, 1ab из п. 2.4 и 2.2.3b*, 2.2.6c*, 2.3.6b, 6.1.14f, 6.1.15c*. В этом и следующих заданиях используйте формулу Эйлера без доказательства.
К 21.10: 2.2.6d* и 3b, 5bd*, 1d*, 6ab, 7.5, 8.33, 9a из п. 2.4 и 1a, 2a, 3ab из п. 2.5.
К 28.10: 5d*, 7.7, 9b* из п. 2.4 и 3c, 4d, 5abc*, 6a, 7 из п. 2.5 и 2.6.1abc, 2.6.2.a.
К 11.11: 2bcd, 4abcd, 3, 5ab*c*, 7ab из п. 2.6 и 2.4.8.6* и 1abcd*, 2ab из п. 2.7.
К 18.11: 2cd*, 3, 4ab, 5a из п. 2.7 и 1, 3, 10 из п. 3.1 и 1, 2bс*, 3ab из п. 3.2.
К 25.11: 2.7.4cd*, 2.7.5b*, 3.2.4*, 3.2.5a и 1abcde, 2abc из п. 3.3 и 1ab, 2a из п. 1.5 (по электронной версии; в бумажной версии это п. 1.6).
Ко 2.12: 3.3.3a*b* и 2b, 7, 5*, 8a* из п. 1.5 (по электронной версии; в бумажной версии это п. 1.6) и 2ab, 3ab, 5ad из п. 5.1 и 3ab, 4 из п. 6.3.
К 9.12: 5.1.5b* и 5abcefg*, 6, 7ab, 8ab, 9ab, 3c из п. 6.3.
К 16.12: 1a*b*, 3c, 10a, 11a, 13ab*, 14ab из п. 6.3 и 2abcd, 4ac из п. 7.1.
К зачету не 23.12: приготовьте к сдаче неразобранные задачи из задания к 16.12 и 6.3.14c* и 3ab*, 4bd из п. 7.1.

Последнее обновление 8.02.2021. Пожалуйста, направляйте пожелания и замечания Аркадию Борисовичу Скопенкову, s*open*o@mccme.ru, где *=k.

Rambler's Top100