Просмотр кода страницы Дискретная математика 25/26

== О курсе ==
Обязательный курс "Дискретной математики" программы ПИ читается студентам-первокурсникам в модулях I - IV. Он охватывает разнообразные темы, важные для математического образования программного инженера, но выходящие за рамки
более традиционных курсов алгебры, анализа и геометрии. Среди них: основы логики и теории множеств, комбинаторика, графы, производящие функции.

== Преподаватели и учебные ассистенты ==
{| class="wikitable" style="text-align:center"
|-
! Группа !! 251 !! 252 !! 253 !! 254 !! 255 !! 256 !! 257 !! 258 !! 259 !! 2510
|-
|| '''Лектор'''
| colspan="16" | [https://t.me/edashkov Дашков Е.В.] (edashkov@gmail.com, [https://vk.com/evgeny.v.dashkov ВК)].

|- 
|| '''Семинаристы'''
|| [https://t.me/edashkov Е. В. Дашков]           <br> Пт 18:10
|| [https://t.me/t1som А. В. Никитина]            <br> Вт 13:00
|| [https://t.me/VVKikteva В. В. Киктева]         <br> Ср 13:00
|| [https://t.me/VVKikteva В. В. Киктева]         <br> Пн 11:10
|| [https://t.me/good_michael М. А. Хрыстик]      <br> Чт 14:40
|| [https://t.me/azapryagaev А. А. Запрягаев]     <br> Пт 13:00
|| [https://t.me/alexandrzaitsev_1 А. В. Зайцев]  <br> Пт 14:40 
|| [https://t.me/good_michael М. А. Хрыстик]      <br> Чт 16:20
|| [https://t.me/ignatievnick Н. Э. Игнатьев]     <br> Ср 16:20
|| [https://t.me/medvednikita Н. Ю. Медведь]      <br> Ср 9:30
|-
|  '''Ассистенты'''
|| [https://t.me/TheRatery Никита Быльнов]
|| [https://t.me/iamfarmer2 Анна Щуплова]
|| [https://t.me/JosHIliNg Владимир Плотников]
|| [https://t.me/vvysotskaya_a Анна Высоцкая]
|| [https://t.me/VishupHell Андраник Торосян]
|| [https://t.me/can4k Александр Яковлев]
|| [https://t.me/Vaneeva_N Наталья Ванеева]
|| [https://t.me/wakunder Алексей Солод]
|| [https://t.me/lixovian Кирилл Мендус]
|| [https://t.me/tatevikkkkkkkk Татевик Аракелян]
|-
|}
'''Ассистенты лектора:''' [https://t.me/artyy_l Валерия Чапурина], [https://t.me/bashmachyo Герман Альберштейн].

=== К кому обратиться? ===

По вопросам, касающимся содержательной стороны курса, лучше всего писать в [https://t.me/joinchat/U3mg-j0ibdH6SxJa общий чат] студентов в Телеграме, но можно также (например, когда вопрос содержит важное соображение по решению домашней задачи) написать лично ассистенту, преподавателю своей группы или лектору. В отношении математики лучше спросить  и узнать, чем не спрашивать и остаться в неведении. '''Не стесняйтесь!'''

Если вам нужна обстоятельная консультация по содержанию курса, то ассистенты проводят таковые с определенной периодичностью, а все преподаватели, включая лектора, имеют на них выделенные часы. На практике, лучше всего договориться о консультации заранее в личном сообщении.

По вопросам сдачи домашних заданий и проверки контрольных работ обращайтесь напрямую к ассистенту вашей группы. При возникновении разногласий --- к преподавателю группы, а затем, если нужно, к лектору.

По организационным вопросам следует писать ассистенту лектора и лишь в самых крайних случаях --- преподавателю своей группы или лектору. Вообще же, большинство организационных вопросов нужно решать в Учебном офисе и других уполномоченных подразделениях. '''Помните''': преподаватели высшей школы не являются "учительницей" и весьма затрудняются решать ваши '''организационные''' вопросы.

== Текущая успеваемость ==

[https://docs.google.com/spreadsheets/d/1Swx-9kby6fMhSt3YGlhD4RLXqCZ4V3BebuVZWN-nXLw/edit?usp=sharing Общая таблица].

== Наборы задач для семинаров ==


* [https://drive.google.com/file/d/19WyCIkbPZPN0_VA4ZBz6kIyU46b0A8Sy/view?usp=sharing Листок 1]
<!--
* [https://drive.google.com/file/d/14NheOt3B2JCwOkaaS25hLm569tVI0pX0/view?usp=drive_link Листок 1а]
-->

* [https://drive.google.com/file/d/1jHm9GSAlLz-vhs6yDZM4MBZ5xm0dTgSk/view?usp=drive_link Листок 2]

* [https://drive.google.com/file/d/1DyXwHak6eYG3OIk2_fhwhCeouHXJSD0g/view?usp=drive_link Листок 3]

* [https://drive.google.com/file/d/1Qu1_GTbkUk4wXS2ZTOzI_LxqjIq38rPO/view?usp=drive_link Листок 4]

* [https://drive.google.com/file/d/1vCcv09JTfWEqKF44VDqAarpgTEh64BZq/view?usp=drive_link Листок 5]

* [https://drive.google.com/file/d/1RRMfxKqPI0aeRPL8vrTafrVQsXh6Fgaj/view?usp=drive_link Листок 6]

* [https://drive.google.com/file/d/1g_JOH2C5W1JFtWjsWWqP0M91CP3rNn2Y/view?usp=drive_link Листок 7]

* [https://drive.google.com/file/d/1o9JLaCS4Md9qpOqtSVA0IrZGX54_H0AW/view?usp=drive_link Листок 8]

* [https://drive.google.com/file/d/1LOvCzvy26LvMJmItyBTet5K4ge0-R4op/view?usp=drive_link Листок 9]

* [https://drive.google.com/file/d/1_eeOvZ4nfF3MN1N9JNisD9th9f4Ncpjl/view?usp=drive_link Листок 10]

* [https://drive.google.com/file/d/1BE6frUTfQfdOF4wXgQApWxCLDdLIgha_/view?usp=drive_link Листок 11]

* [https://drive.google.com/file/d/1quTya5nBVmx82Rx_YTR5CFob1Rv4ki6n/view?usp=drive_link Листок 12]
<!--


* [https://drive.google.com/file/d/1PgDZSqT4XKRtAj1ye4VmtZuQS1tTghUm/view?usp=drive_link Листок 13]

-->

== Домашние задания ==

Домашнее задание выдается частями, каждую из которых следует сдавать в установленные
сроки. Преподаватель вправе потребовать от любого студента "защитить" (т.е. изложить устно,
отвечая на возникающие при этом вопросы) решение любой из зачтенных этому студенту задач ДЗ.
В случае неуспешной защиты, баллы за соответствующую часть ДЗ могут быть снижены, в т.ч. до нуля.
Некоторые задачи отмечены звездочкой* как задачи "повышенной сложности"; остальные считаются "обыкновенными".


{| class="wikitable"
|-
! Задание !! colspan="12" | Срок сдачи в группе
|-
| || 251 || 252 || 253 || 254 || 255 || 256 || 257 || 258 || 259 || 2510 
|-
| [https://drive.google.com/file/d/1MBgx-j_J_P1X85FYNqrhkim5n1Jd1S0Q/view?usp=drive_link ДЗ 1а ] ||  27.09 || 05.10 || 05.10 || 05.10 ||   || 27.09 || 05.10 ||25.09 || 11.10 ||  27.09
|-
| [https://drive.google.com/file/d/18g-6QRhwdt-zSCTbkVwHU5FMKAZb0MWx/view?usp=drive_link ДЗ 1b ] || 05.10 || 18.10 || 14.10 || 14.10 || || 11.10 || 17.10 || 09.10 || 18.10 || 08.10
|-
| [https://drive.google.com/file/d/11t8_j6Hu_gI--Nt6cqvP1GuCCNg3XlIV/view?usp=drive_link ДЗ 1c] || 19.10 || 25.10 || 26.10 || 26.10 || || 18.10 || 24.10 || 23.10 || 25.10 || 22.10
|-
| [https://drive.google.com/file/d/1OFYkx_ziIqczlHXfDjZqYhqlW8x045N5/view?usp=drive_link ДЗ 2a] || 14.11  || 21.11 || 26.11 || 26.11 ||  || 15.11 || 21.11 || 20.11 || 19.11 || 26.11
|-
| [https://drive.google.com/file/d/1upjIyX97vUwdRiWzkMGQDzBbsq4z_YPQ/view?usp=drive_link ДЗ 2b] || 30.11 || 05.12 || 10.12 || 10.12 ||  || 29.11 || 09.12 || 04.12 || 03.12 || 09.12
|-
| [https://drive.google.com/file/d/1ct2MtgE4XQrynozG7lmSYGL5kypsO7_C/view?usp=drive_link ДЗ 2c] || 14.12 || 17.12 || 19.12 || 19.12 ||  || 13.12 || 19.12 || 14.12  || 17.12 || 14.12
|-
| [https://drive.google.com/file/d/1CI6IdobWxjko4zaeGLdx5fSY4hZIKQJi/view?usp=drive_link ДЗ 3а] || 19.01  || 27.01 || 25.01 || 25.01 ||  || 24.01 || 23.01 ||  || 27.01 || 04.02
|-
| [https://drive.google.com/file/d/1C7WC1m5OJmiaG_j6MmA_3PA2Zl9OLGxW/view?usp=drive_link ДЗ 3б] || 07.02  || 13.02 || 11.02 || 09.02 ||  || 07.02 || 06.02 || || 11.02 || 11.02
|-
| [https://drive.google.com/file/d/1z6h65LDrQLmd-6tMQDHycdG-FjUWtp8V/view?usp=drive_link ДЗ 4а] || 27.02 || 04.03 || 27.02 || 28.02 || || 21.02 || 23.02 || || 03.03 || 22.02
|-
| [https://drive.google.com/file/d/1tHkombPE6qFFVflqXnkWRz3yVwSlALLB/view?usp=drive_link ДЗ 4б] || 10.04 || 13.03 || 11.03 || 10.03 ||  || 14.03 || 13.03 || || 15.03 || 01.04
|-
| [https://drive.google.com/file/d/16Q3xILERd53zIcOZjyuZ-6f_qTNoTd7u/view?usp=drive_link ДЗ 5а] || 10.04 || 10.04 || 12.04 || 12.04 || || 11.04 || 13.04 || || 19.04 || 19.04
|-
| [https://drive.google.com/file/d/1zFAC-Dvsr2mlWJiOn86OxU54IQokYGAa/view?usp=drive_link ДЗ 5б] || 17.04 || 21.04 || 22.04 || 22.04 ||  || 19.04 || 22.04 || || 30.04 || 26.04
|-
| [https://drive.google.com/file/d/1pWE0mT2cFrmJgfNUPWUn9bMYfPIGb4HW/view?usp=drive_link ДЗ 6а] || 30.04 || 30.04 || 27.05 || 28.05 ||  || 30.04 || 30.04 || || 30.04 || 30.04
|-
| [https://drive.google.com/file/d/1oWlcOHBsZnff4MhIZGIg4hbpgmLJwuSO/view?usp=drive_link ДЗ 6б] || 22.05 || 20.05 || 03.06 || 04.06 || || 23.05 || 25.05 || || 25.05 || 31.05
|-
| [https://drive.google.com/file/d/1FdJ29TZRgg-AiyVlb1vGW8QigKqToPZI/view?usp=drive_link ДЗ 7а] || 01.06 || || 07.06 || 07.06 ||  || 08.06 || 11.06 || ||  || 06.06
<!--
|-
| [https://drive.google.com/file/d/1T5yTCYe_kwn_b3qaYqk-fMODYy3S1xtm/view?usp=drive_link ДЗ 7б] || 05.06 || 08.06 || 08.06 || 15.06 ||  || 08.06 || 04.06 || || 09.06 || 15.06
|-
| [https://drive.google.com/file/d/1Go7JfalnFWToaubIElbhWr0I93UA-l69/view?usp=drive_link ДЗ 8а] || 15.06 || 19.06 || 15.06 || 19.06 ||  || 15.06 || 15.06 || || 15.06 || 19.06
|-
| [https://drive.google.com/file/d/1uSmZ0WxfTADJiecvTTGbXrXeO5a48dxz/view?usp=drive_link ДЗ 8б] || - || - || - || - || - || - || - || - || - || - 
|-
| [https://drive.google.com/file/d/19YJ9BUp8ARc6rRBF-cb4_mNfotMnQPPB/view?usp=drive_link ДЗ 9] || 18.06 ||  || 20.06 23:59 || 20.06 23:59 || || ||  || || 21.06 02:00 || 20.06 23:59 || 20.06 23:59
-->
|}

'''Срок сдачи задания устанавливается семинаристом группы.'''

== Экзамен ==

Письменные экзаменационные работы проводятся в сессию после второго и четвертого модулей. При наличии удовлетворительной накопленной оценки студент имеет право на "автомат", освобождающее его от написания экзаменационной работы (см. раздел "Аттестация и оценки"). На экзамене запрещается использовать какие-либо материалы или электронные устройства.

== Контрольные работы ==

Письменные контрольные работы проводятся в конце каждого модуля: обычно на последней учебной неделе в специально выделенное время, общее для всего потока. Посещение контрольных работ настоятельно рекомендуется. Об оценивании см. раздел "Аттестация и оценки". При написании контрольных работ разрешается использовать заранее подготовленный конспект на одном листе A4 (или двойном тетрадном). Любые иные материалы, а также электронные устройства использовать запрещается.

== Материалы курса ==

=== Группа для объявлений, вопросов и обсуждений по курсу ===

[https://t.me/joinchat/U3mg-j0ibdH6SxJa Обязательно вступайте!]

=== Материалы лектора ===

* [https://drive.google.com/drive/folders/1vJQkWLMxA-3_T9pb3EelOCd_3wsUvcXC?usp=sharing Наборы задач, конспекты и др.]

* [https://drive.google.com/file/d/1YFYHP3oHlv6zPI6d0k96Intjyu0qZpus/view?usp=drive_link Основной конспект (на англ. языке)]

* [https://drive.google.com/drive/folders/1cTCdJtVVtO9uDgIKE8HY0qhl285tzOo1?usp=drive_link Перевод основного конспекта] (работа студентов-добровольцев: берегитесь ошибок и [https://t.me/sigma_algebraa присоединяйтесь] к ней сами!)

* [https://drive.google.com/file/d/1rtKeAnBgLzSsakwIdXRAXlFao5-3AeGj/view?usp=drive_link Пособие по теории множеств]

* [https://rutube.ru/channel/32000946/ Канал лектора на RuTube] (видимо, будет приоритетным)

* [https://youtube.com/channel/UCp2EjaJEGS257bl6DVDyAqg Канал лектора на YouTube] (наследие прошлого)

* [https://meet.edashkov.net.ru Сервер лектора для удаленного общения] (включается по потребности)

<!-- === Записи лекций этого года === -->

=== Прочие материалы ===

* [https://www.youtube.com/playlist?list=PL1Uob8iPTHGTUM71KDYl7ZyBN01vykvLy Видеозаписи прошлых лет (Youtube)]

* [[Записи семинаров 212 группы | Записи семинаров 212 группы]]

* [https://disk.yandex.ru/d/grCjLzO3M4qvZg Записи семинаров 249 группы].

* [[Записи семинаров Козачинского| Записи семинаров Козачинского]]

* [https://disk.yandex.ru/d/4i7Gu93UrHYK4w Доски с лекций]

* [https://youtu.be/i7ubi4y-uxA Запись с доказательствами важных теорем арифметики производящих функций]

== Аттестация и оценки ==

=== Осенний семестр ===

Во втором модуле производится промежуточная аттестация за
осенний семестр. В осеннем семестре проводятся две письменные контрольные работы (КР1 и
КР2); выдается и проверяется письменное домашнее задание (ДЗ2). В оценку ДЗ2 входят домашние задания, сдаваемые в первом и втором модулях.

За каждую задачу домашнего задания ставится оценка от 0 до 1 балла (дробное значение) в зависимости от правильности и полноты представленного студентом решения. За все домашние задания модулей 1 и 2 выставляется оценка ДЗ2, (без округления) равная значению

ДЗ2 = 8 * обыкн + 2 * сложн, где

обыкн = #(баллов, полученных студентом за все обыкновенные задачи) / #(обыкновенных задач в домашнем задании),

сложн = #(баллов, полученных студентом за все задачи повышенной сложности) / #(задач повышенной сложности в домашнем задании).

За каждую задачу контрольной работы ставится оценка от 0 до 1 балла (дробное значение) в зависимости от правильности и полноты представленного студентом решения. За i-ю контрольную работу выставляется оценка КРi, (без округления) равная значению

КРi = 10 * #(баллов, полученных студентом за все задачи) / #(задач в контрольной работе).

Накопленная оценка НК2 за осенний семестр вычисляется по формулам:

НК2' = 0,35 * КР1 + 0,35 * КР2 + 0,3 * ДЗ2,

НК2 = ОКРУГЛ (НК2').

(Здесь и всюду ОКРУГЛение производится по обычным арифметическим правилам.)

Если НК2 >= 4, то студент имеет право "АВТОМАТОМ" получить оценку НК2 в качестве оценки промежуточной аттестации. По умолчанию мы предполагаем, что студент пользуется этим правом. Иначе студент должен заявить об отказе от "автомата". В случае если НК2 < 4 или студент отказывается от "автомата", студенту предлагается выполнить экзаменационное задание Э2, оцениваемое так:

Э2 = 10 * #(баллов, полученных студентом за все задачи) / #(задач в экзаменационной работе),

причем за каждую задачу экзаменационной работы ставится оценка от 0 до 1 балла (дробное значение) в зависимости от правильности и полноты представленного студентом решения.

В этом случае промежуточная оценка за осенний семестр равна

ОСЕНЬ = ОКРУГЛ (0,7 * Э2 + 0,3 * НК2').

=== Весенний семестр ===

В четвертом модуле производятся промежуточная аттестация за весенний семестр, а также итоговая аттестация. В весеннем семестре проводятся две письменные контрольные работы (КР3 и
КР4); выдается и проверяется письменное домашнее задание (ДЗ4). В оценку ДЗ4 входят домашние задания, сдаваемые в третьем и четвертом модулях.

Оценки за домашние задания, контрольные и экзаменационные работы выставляются так же, как и в осеннем семестре. 

Накопленная оценка НК4 за весенний семестр вычисляется по формулам:

НК4' = 0,35 * КР3 + 0,35 * КР4 + 0,3 * ДЗ4

НК4 = ОКРУГЛ (НК4').

Если НК4 >= 4, то студент имеет право "АВТОМАТОМ" получить оценку НК4 в качестве оценки промежуточной аттестации. По умолчанию мы предполагаем, что студент пользуется этим правом. Иначе студент должен заявить об отказе от "автомата". В случае если НК4 < 4 или студент отказывается от "автомата", студенту предлагается выполнить экзаменационное задание Э4. В этом случае промежуточная оценка за весенний семестр равна

ВЕСНА = ОКРУГЛ (0,7 * Э4 + 0,3 * НК4').

Итоговой оценкой по дисциплине является оценка ВЕСНА.

=== Пропуск контрольных работ по болезни ===

В случае пропуска одной контрольной работы КРi в семестре по уважительной причине (подтвержденной учебным офисом), студент имеет право прийти на экзамен и зачесть полученную там оценку Эj за оценку КРi в формуле НКj. О намерении воспользоваться таким правом следует заранее сообщить ассистенту лектора. Если при этом окажется HKj >= 4, применяются правила об "автомате". В противном случае считается, что студент писал экзамен, и расчет промежуточной оценки производится соответственно, причем в НКj значение КРi принимается равным нулю. Если обе контрольные работы в семестре пропущены по уважительной причине, вопрос решается в индивидуальном порядке. Также в индивидуальном порядке пропустившим по уважительной причине может быть разрешено писать контрольную работу в пределах краткого времени после того, как ее напишут большинство студентов.

== Пересдачи ==

В случае получения неудовлетворительных (т.е. < 4) оценок промежуточной аттестации ОСЕНЬ или ВЕСНА, студент отправляется на пересдачу. Эти оценки пересдаются отдельно --- в начале весеннего семестра и осенью следующего учебного года соответственно. При пересдаче применяются правила ПОПАТКУС. Согласно оным, при пересдаче каждой оценки студент имеет право на ПЕРВУЮ пересдачу, проводимую по всем правилам экзамена и выражающуюся в том, что ее результат заменяет собой оценку Эi в аттестационной формуле (т.е. накопленная НКi, по-прежнему, учитывается!). Если при этом опять получилась неудовлетворительная оценка, студент может выбрать ВТОРУЮ пересдачу, аналогичную ПЕРВОЙ (вновь с учетом того же значения НКi в аттестационной формуле!), или повторно изучить курс (вероятно, на платной основе), в ходе чего можно будет получить новую оценку НКi. При этом, однако, права на пересдачу уже не остается: нужно будет получить автомат или сдать экзамен по общим правилам с первой попытки.

== Литература ==

По вопросу подбора и, быть может, отыскания литературы можно обращаться не только в библиотеку, но и к лектору.

#      Верещагин Н. К., Шень А. Лекции по математической логике и теории алгоритмов. Части 1--3.  5-е изд., М: МЦНМО, 2017.
#      Виноградов И. М. Основы теории чисел. 9-е изд., М.: Наука, 1981.
#      [http://rubtsov.su/public/DM-HSE-Draft.pdf  Вялый М., Подольский В., Рубцов А., Шварц Д., Шень А. Лекции по дискретной математике.]
#      Гаврилов Г. П., Сапоженко А. А. Задачи и упражнения по дискретной математике. 3-е изд., М.: ФИЗМАТЛИТ, 2004.
#      [https://drive.google.com/file/d/1RM6KX_reBFwUXesWGUEu0sFn2NCaBgvz/view?usp=sharing Дашков Е. В. Введение в математическую логику. Множества и отношения. М.: МФТИ, 2019.]
#      Зубков А. М., Севастьянов Б. А., Чистяков В. П. Сборник задач по теории вероятностей. 2-е изд., М.: Наука, 1989.
#      Ландо С. К., Лекции о производящих функциях. 3-е изд, М.: МЦНМО, 2007.
#      Мельников О. И. Теория графов в занимательных задачах. 5-е изд., М.: Книжный дом "ЛИБРОКОМ", 2013.
#      [http://www.mccme.ru/free-books/shen/shen-induction.pdf Шень А., Математическая индукция. 5-е изд, М.: МЦНМО, 2016.]