Дискретная математика КНАД — различия между версиями

Материал из Wiki - Факультет компьютерных наук
Перейти к: навигация, поиск
(Преподаватели и учебные ассистенты)
(Контрольные Работы и Экзамены)
(не показано 87 промежуточных версии 2 участников)
Строка 3: Строка 3:
 
{| class="wikitable" style="text-align:center"
 
{| class="wikitable" style="text-align:center"
 
|-
 
|-
! Группа !! 201 !! 202
+
! Группа !! 211 !! 212
 
|-
 
|-
 
|| Лектор ||colspan="2"| [https://www.hse.ru/org/persons/224875083 Мажуга А.М.]
 
|| Лектор ||colspan="2"| [https://www.hse.ru/org/persons/224875083 Мажуга А.М.]
Строка 9: Строка 9:
 
|| Семинарист || Трушин Антон || [https://www.hse.ru/org/persons/224875083 Мажуга А.М.]   
 
|| Семинарист || Трушин Антон || [https://www.hse.ru/org/persons/224875083 Мажуга А.М.]   
 
|-
 
|-
|| Приемные часы || NBD || Среда, 18:00 -- 21:00, кабинет S808<br><span style="color:#DC143C">нужно предупредить за день</span>   
+
|| Приемные часы || TBD || Среда, 17:00 -- 21:00, через Zoom<br><span style="color:#DC143C">нужно предупредить за день</span>   
 
|-
 
|-
|| Ассистент || Никитин Артём <br> avnikitin_5@edu.hse.ru
+
|| Ассистент || Смородинов Александр <br> asmorodinov66@gmail.com
 
|| Копытов Даниил <br> daniil.copytow43@yandex.ru
 
|| Копытов Даниил <br> daniil.copytow43@yandex.ru
 
|}
 
|}
Строка 19: Строка 19:
  
 
== Конспект Лекций ==
 
== Конспект Лекций ==
 +
 +
''' <span style="color:#DC143C">Если вы заметили опечатку/ошибку в конспектах лекций, то, пожалуйста, опишите ее в [https://docs.google.com/spreadsheets/d/1UUkKlZ-QqewqHhs-PC1MFmF9IH9i8UGmxjq-Uz-jcLw/edit?usp=sharing '''этой''']</span> <span style="color:#DC143C">таблице.</span>'''
 +
 +
''' Модуль 2'''
 +
* [https://www.dropbox.com/s/js4k16xdt6nv1k4/%D0%94%D0%B8%D1%81%D0%BA%D1%80%D0%B0_%D0%9B%D0%B5%D0%BA_15.pdf?dl=0 '''Лекция 15'''] (15.12.2021). Начала теории чисел, Часть-IV; функция Эйлера; понятия мультипликативной и вполне мультипликативной функции; мультипликативность функции Эйлера; две замкнутые формы для выражения значения функции Эйлера; теорема Эйлера; некоторые дополнительные свойства функции Эйлера (без доказательства); китайская теорема об остатках.
 +
 +
* [https://www.dropbox.com/s/jqg1oemgfwon6jd/%D0%94%D0%B8%D1%81%D0%BA%D1%80%D0%B0_%D0%9B%D0%B5%D0%BA_14.pdf?dl=0 '''Лекция 14'''] (08.12.2021). Начала теории чисел, Часть-III; простые и составные натуральные числа; бесконечность множества простых чисел; факторизация натурального числа и основная теорема арифметики; теорема об изоморфизме порядков для отношения делимости; НОД и НОК в терминах факторизации; теорема Вильсона; малая теорема Ферма.
 +
 +
* [https://www.dropbox.com/s/srus7n3c2onf4wq/%D0%94%D0%B8%D1%81%D0%BA%D1%80%D0%B0_%D0%9B%D0%B5%D0%BA_13.pdf?dl=0 '''Лекция 13'''] (04.12.2021). Начала теории чисел, Часть-II; понятия сравнения по модулю, классы эквивалентности и вычеты; операции сложения и умножения вычетов, корректность определения и основные свойства; существование обратного вычета по умножению; описание множества решений сравнения 1-й степени.
 +
 +
* [https://www.dropbox.com/s/nqcu6wu79uh02vf/%D0%94%D0%B8%D1%81%D0%BA%D1%80%D0%B0_%D0%9B%D0%B5%D0%BA_12.pdf?dl=0 '''Лекция 12'''] (24.11.2021). Начала теории чисел, Часть-I; деление с остатком; корректность операции деления с остатком; наибольший общий делитель; основные свойства НОД (существование, единственность, au+bv формула); расширенный алгоритм Евклида.
 +
 +
* [https://www.dropbox.com/s/43kg2qt02l04fz3/%D0%94%D0%B8%D1%81%D0%BA%D1%80%D0%B0_%D0%9B%D0%B5%D0%BA_11.pdf?dl=0 '''Лекция 11'''] (17.11.2021). Отношения, Часть-III: Частичные порядки; понятие частичного порядка (строгий/нестрогий/линейный); теорема о взаимно однозначном соответствии между строгими и нестрогими порядками; понятие частично упорядоченного множества; минимальные/наименьшие/максимальные/наибольшие элементы; лексикографический порядок; изоморфизм порядков; сумма порядков.
 +
 +
* [https://www.dropbox.com/s/2bev18c9senfg64/%D0%94%D0%B8%D1%81%D0%BA%D1%80%D0%B0_%D0%9B%D0%B5%D0%BA_10.pdf?dl=0 '''Лекция 10'''] (10.11.2021). Отношения и функции, Часть-II; понятие обратной функции; теорема об обратной функции; примеры обратимых функций; теорема об обратной функции на конечном множестве; отношения эквивалентности; понятия клfсса эквивалентности и фактормножества; теорема об описании эквивалентностей; изоморфизмы графов.
 +
 +
* [https://www.dropbox.com/s/815hvuyvyyp6sc4/%D0%94%D0%B8%D1%81%D0%BA%D1%80%D0%B0_%D0%9B%D0%B5%D0%BA_9.pdf?dl=0 '''Лекция 9'''] (03.11.2021). Отношения и функции, Часть-I; понятие бинарного отношения и связанные с ним понятия; транспонирование и композиция бинарных отношений; ассоциативность композиции бинарных отношений; основные типы бинарных отношений (рефлексивные, симметричные и т.д.); понятие функции и связанные с ним понятия; инъективные, сюръективные, биективные функции и их основные свойства.
 +
 +
* [https://www.dropbox.com/s/8nrepdxabqe0zoi/%D0%94%D0%B8%D1%81%D0%BA%D1%80%D0%B0_%D0%9B%D0%B5%D0%BA_8.pdf?dl=0 '''Лекция 8'''] (27.10.2021). Комбинаторика, Часть-III; биномиальные коэффициенты и их основные свойства; треугольник Паскаля; мультиномиальные коэффициенты; явная формула для мультиномиальных коэффициентов; числа Каталана; явная формула для чисел Каталана.
  
 
''' Модуль 1'''
 
''' Модуль 1'''
 +
* [https://www.dropbox.com/s/vs36y1cq24kg9mt/%D0%94%D0%B8%D1%81%D0%BA%D1%80%D0%B0_%D0%9B%D0%B5%D0%BA_7.pdf?dl=0 '''Лекция 7'''] (13.10.2021). Комбинаторика, Часть-II; комбинаторный принцип деления; размещения, теорема о числе размещений; сочетания, теорема о числе сочетаний.
 +
 +
* [https://www.dropbox.com/s/29dcnac2h7tgkl3/%D0%94%D0%B8%D1%81%D0%BA%D1%80%D0%B0_%D0%9B%D0%B5%D0%BA_6.pdf?dl=0 '''Лекция 6'''] (06.10.2021). Графы, Часть-III: Ориентированные графы; понятие ориентированного графа, степени входа и выхода вершины орграфа; теорема о сумме степеней вершин орграфа; ориентированный путь и цикл в орграфе; понятие сильной связности; ациклические орграфы и их описание; задача о кенигсбергских мостах, эйлеровы циклы и эйлеровы графы; теорема об описании эйлеровых орграфов.
 +
 +
* [https://www.dropbox.com/s/78zycyx8cp5k6fu/%D0%94%D0%B8%D1%81%D0%BA%D1%80%D0%B0_%D0%9B%D0%B5%D0%BA_5.pdf?dl=0 '''Лекция 5'''] (29.09.2021). Графы, Часть-II: Деревья; понятия леса и дерева; теорема об описании лесов (эквивалентные определения леса); теорема об описании деревьев (эквивалентные определения дерева); размерность графа и ее основные комбинаторные свойства; теорема о размерности леса; теорема о размерности дерева (связь числа вершин и ребер в дереве); листья в девере; теорема об остовных деревьях; теорема Кэли о числе остовных деревьев в полном графе (без доказательства).
 +
 +
* [https://www.dropbox.com/s/lsk7n3ehdbvl9ec/%D0%94%D0%B8%D1%81%D0%BA%D1%80%D0%B0_%D0%9B%D0%B5%D0%BA_4.pdf?dl=0 '''Лекция 4'''] (22.09.2021). Графы, Часть-I: Введение; понятие графа, матрицы смежности и инцидентности; теорема о сумме степеней вершин графа; связность, области достижимости и компоненты связности графа.
 +
 +
* [https://www.dropbox.com/s/mb2zy4m57j9o8vv/%D0%94%D0%B8%D1%81%D0%BA%D1%80%D0%B0_%D0%9B%D0%B5%D0%BA_3.pdf?dl=0 '''Лекция 3'''] (17.09.2021). Комбинаторика, Часть-I; основные комбинаторные принципы: правило произведения и правило суммы; понятие последовательности; теорема о числе слов в конечном алфавите; формула включения-исключения.
 +
 +
* [https://www.dropbox.com/s/idul60ntayu8zb3/%D0%94%D0%B8%D1%81%D0%BA%D1%80%D0%B0_%D0%9B%D0%B5%D0%BA_2.pdf?dl=0 '''Лекция 2'''] (15.09.2021). Введение в теорию множеств; основные способы задания множества; основные операции над множествами; (полный) принцип математической индукции.
  
 
* [https://www.dropbox.com/s/dyjluf1xsnzfsk6/%D0%94%D0%B8%D1%81%D0%BA%D1%80%D0%B0_%D0%9B%D0%B5%D0%BA_1.pdf?dl=0 '''Лекция 1'''] (08.09.2021). Введение в алгебру логики; понятие высказывания, простые и сложные (= составные) высказывания; основные логические связки; логически эквивалентные высказывания; примеры эквивалентностей; тавтологии и противоречия; кванторы всеобщности и существования.
 
* [https://www.dropbox.com/s/dyjluf1xsnzfsk6/%D0%94%D0%B8%D1%81%D0%BA%D1%80%D0%B0_%D0%9B%D0%B5%D0%BA_1.pdf?dl=0 '''Лекция 1'''] (08.09.2021). Введение в алгебру логики; понятие высказывания, простые и сложные (= составные) высказывания; основные логические связки; логически эквивалентные высказывания; примеры эквивалентностей; тавтологии и противоречия; кванторы всеобщности и существования.
Строка 26: Строка 56:
 
== Семинары ==
 
== Семинары ==
  
'''Материал с семинаров 1-й группы:'''
+
'''Материал с семинаров 211-й группы:'''
  
 
'''Модуль 1'''
 
'''Модуль 1'''
  
[https://www.dropbox.com/s/4i438oauxrc1lk3/%D0%94%D0%B8%D1%81%D0%BA%D1%80%D0%B0_%D0%A1%D0%B5%D0%BC_1.pdf?dl=0   '''Семинар №1'''] (08.09.2021)
+
* [https://www.dropbox.com/s/uarny23vqfmcfko/%D0%A1%D0%B5%D0%BC%D0%B8%D0%BD%D0%B0%D1%8001.pdf?dl=0 '''Семинар №1'''] (09.09.2021)
  
 +
'''Материал с семинаров 212-й группы:'''
  
'''Материал с семинаров 2-й группы:'''
+
'''Модуль 2'''
 +
* [https://www.dropbox.com/s/hujrf5zs3qhv6tx/%D0%94%D0%B8%D1%81%D0%BA%D1%80%D0%B0_%D0%A1%D0%B5%D0%BC_14.pdf?dl=0  '''Семинар №14'''] (10.12.2021)
 +
 
 +
* [https://www.dropbox.com/s/edn7p74fnp348e0/%D0%94%D0%B8%D1%81%D0%BA%D1%80%D0%B0_%D0%A1%D0%B5%D0%BC_13.pdf?dl=0  '''Семинар №13'''] (03.12.2021)
 +
 
 +
* [https://www.dropbox.com/s/a5qrrk4vkiu9mox/%D0%94%D0%B8%D1%81%D0%BA%D1%80%D0%B0_%D0%A1%D0%B5%D0%BC_12.pdf?dl=0  '''Семинар №12'''] (26.11.2021)
 +
 
 +
* [https://www.dropbox.com/s/2krpibiezq7pbr3/%D0%94%D0%B8%D1%81%D0%BA%D1%80%D0%B0_%D0%A1%D0%B5%D0%BC_11.pdf?dl=0  '''Семинар №11'''] (25.11.2021)
 +
 
 +
* [https://www.dropbox.com/s/n0ki8y5y1xdr4gl/%D0%94%D0%B8%D1%81%D0%BA%D1%80%D0%B0_%D0%A1%D0%B5%D0%BC_10.pdf?dl=0  '''Семинар №10'''] (19.11.2021)
 +
 
 +
* [https://www.dropbox.com/s/vi40lgbb3alnetw/%D0%94%D0%B8%D1%81%D0%BA%D1%80%D0%B0_%D0%A1%D0%B5%D0%BC_9.pdf?dl=0  '''Семинар №9'''] (05.11.2021)
 +
 
 +
* [https://www.dropbox.com/s/ux8bzonhdows98j/%D0%94%D0%B8%D1%81%D0%BA%D1%80%D0%B0_%D0%A1%D0%B5%D0%BC_8.pdf?dl=0  '''Семинар №8'''] (03.11.2021)
  
 
'''Модуль 1'''
 
'''Модуль 1'''
 +
* [https://www.dropbox.com/s/pqnzhao3didrr7s/%D0%94%D0%B8%D1%81%D0%BA%D1%80%D0%B0_%D0%A1%D0%B5%D0%BC_7.pdf?dl=0  '''Семинар №7'''] (13.10.2021)
 +
 +
* [https://www.dropbox.com/s/qntjky0c8bod6oj/%D0%94%D0%B8%D1%81%D0%BA%D1%80%D0%B0_%D0%A1%D0%B5%D0%BC_6.pdf?dl=0  '''Семинар №6'''] (06.10.2021)
 +
 +
* [https://www.dropbox.com/s/1uocuf1chll3fm1/%D0%94%D0%B8%D1%81%D0%BA%D1%80%D0%B0_%D0%A1%D0%B5%D0%BC_5.pdf?dl=0  '''Семинар №5'''] (29.09.2021)
 +
 +
* [https://www.dropbox.com/s/k365j5anop7qqgi/%D0%94%D0%B8%D1%81%D0%BA%D1%80%D0%B0_%D0%A1%D0%B5%D0%BC_4.pdf?dl=0  '''Семинар №4'''] (24.09.2021)
 +
 +
* [https://www.dropbox.com/s/7r9jm8yqfwzzznw/%D0%94%D0%B8%D1%81%D0%BA%D1%80%D0%B0_%D0%A1%D0%B5%D0%BC_3.pdf?dl=0  '''Семинар №3'''] (22.09.2021)
 +
 +
* [https://www.dropbox.com/s/dbhxyb19jvc1vkw/%D0%94%D0%B8%D1%81%D0%BA%D1%80%D0%B0_%D0%A1%D0%B5%D0%BC_2.pdf?dl=0  '''Семинар №2'''] (15.09.2021)
 +
 +
* [https://www.dropbox.com/s/4i438oauxrc1lk3/%D0%94%D0%B8%D1%81%D0%BA%D1%80%D0%B0_%D0%A1%D0%B5%D0%BC_1.pdf?dl=0  '''Семинар №1'''] (08.09.2021)
  
 
== Домашние задания ==
 
== Домашние задания ==
  
'''Обязательные ДЗ для 1-й группы:'''
+
'''Обязательные ДЗ для 211-й группы:'''
  
 
'''Модуль 1'''
 
'''Модуль 1'''
  
[https://drive.google.com/file/d/1xrLEOs83SDLBnnoU1SO3NCBajrvWSOJp/view?usp=sharing  '''ДЗ №1'''] (выдача: 06.09.21, дедлайн: 19.09.21)
+
'''Обязательные ДЗ для 212-й группы:'''
  
 +
'''Модуль 2'''
 +
* [https://www.dropbox.com/s/6trwc813usscffp/%D0%94%D0%B8%D1%81%D0%BA%D1%80%D0%B0_%D0%94%D0%97_11%2C5.pdf?dl=0  '''ДЗ №11,5'''] (выдача: 29.11.21, дедлайн: 05.12.21)
  
'''Обязательные ДЗ для 2-й группы:'''
+
* [https://www.dropbox.com/s/curq6di3plyjijc/%D0%94%D0%B8%D1%81%D0%BA%D1%80%D0%B0_%D0%94%D0%97_10.pdf?dl=0  '''ДЗ №10'''] (выдача: 22.11.21, дедлайн: 28.11.21)
 +
 
 +
* [https://www.dropbox.com/s/fb84a78ae7hd17i/%D0%94%D0%B8%D1%81%D0%BA%D1%80%D0%B0_%D0%94%D0%97_9.pdf?dl=0  '''ДЗ №9'''] (выдача: 07.11.21, дедлайн: 19.11.21)
 +
 
 +
* [https://www.dropbox.com/s/aixw7whiuxuemmz/%D0%94%D0%B8%D1%81%D0%BA%D1%80%D0%B0_%D0%94%D0%97_8.pdf?dl=0  '''ДЗ №8'''] (выдача: 05.11.21, дедлайн: 12.11.21)
  
 
'''Модуль 1'''
 
'''Модуль 1'''
 +
* [https://www.dropbox.com/s/01ieck94gkvofy0/%D0%94%D0%B8%D1%81%D0%BA%D1%80%D0%B0_%D0%94%D0%97_7.pdf?dl=0  '''ДЗ №7'''] (выдача: 18.10.21, дедлайн: 31.10.21)
 +
 +
* [https://www.dropbox.com/s/p9q61g47ahjft8c/%D0%94%D0%B8%D1%81%D0%BA%D1%80%D0%B0_%D0%94%D0%97_6.pdf?dl=0  '''ДЗ №6'''] (выдача: 07.10.21, дедлайн: 15.10.21)
 +
 +
* [https://www.dropbox.com/s/obncdq60o1ggndb/%D0%94%D0%B8%D1%81%D0%BA%D1%80%D0%B0_%D0%94%D0%97_5.pdf?dl=0  '''ДЗ №5'''] (выдача: 30.09.21, дедлайн: 08.10.21)
 +
 +
* [https://www.dropbox.com/s/qcomucosx0l7icc/%D0%94%D0%B8%D1%81%D0%BA%D1%80%D0%B0_%D0%94%D0%97_4.pdf?dl=0  '''ДЗ №4'''] (выдача: 26.09.21, дедлайн: 03.10.21)
 +
 +
* [https://www.dropbox.com/s/xsxkcp67kmm6r1r/%D0%94%D0%B8%D1%81%D0%BA%D1%80%D0%B0_%D0%94%D0%97_3.pdf?dl=0  '''ДЗ №3'''] (выдача: 23.09.21, дедлайн: 01.10.21)
 +
 +
* [https://www.dropbox.com/s/rjira6lxrplxz50/%D0%94%D0%B8%D1%81%D0%BA%D1%80%D0%B0_%D0%94%D0%97_2.pdf?dl=0  '''ДЗ №2'''] (выдача: 16.09.21, дедлайн: 24.09.21)
 +
 +
* [https://www.dropbox.com/s/mzo22s3wo7vj7pf/%D0%94%D0%B8%D1%81%D0%BA%D1%80%D0%B0_%D0%94%D0%97_1.pdf?dl=0  '''ДЗ №1'''] (выдача: 08.09.21, дедлайн: 17.09.21)
  
 
== Ведомость с оценками и Контроль посещаемости ==
 
== Ведомость с оценками и Контроль посещаемости ==
  
 +
'''Оценки ДЗ:'''
 
{| class="wikitable" style="text-align:center"
 
{| class="wikitable" style="text-align:center"
 
|-
 
|-
! [https://docs.google.com/spreadsheets/d/13ud5o138uy_Y3dEfWtO83S0--QyEadquHFLUH6blo1g/edit?usp=sharing 191] !! [https://docs.google.com/spreadsheets/d/1Xkg-K2bCgHPqNOR-9iNpSRM8uu2rgvOWk7UWT0NwlgY/edit#gid=0 192] !! [https://docs.google.com/spreadsheets/d/1YilO_Lf0gruORTIBkmsckq6j6jQ2G8i61mhxcalDjiQ/edit?usp=sharing 194]
+
! [https://docs.google.com/spreadsheets/d/1Xkg-K2bCgHPqNOR-9iNpSRM8uu2rgvOWk7UWT0NwlgY/edit#gid=0 ???] !! [https://docs.google.com/spreadsheets/d/1YM_NPfRHux7gLDblkH_XkYGSk_V5-dMZPqJ6ANQj8P0/edit#gid=1636656391 212]
 
|}
 
|}
  
Строка 86: Строка 163:
  
 
== Контрольные Работы и Экзамены ==
 
== Контрольные Работы и Экзамены ==
 +
 +
'''Экзамен 1'''
 +
 +
ЭК 1 пройдет 22.12.2021 в формате Zoom конференции, начало в 13:00, ссылка на Zoom конференцию:
 +
 +
Тема: Дискретная_Мат_КНАД_ЭК_1
 +
 +
https://us02web.zoom.us/j/87860918377?pwd=SXp4WFQ5MlZMSko2NkNFMTVIZElBQT09
 +
 +
Идентификатор конференции: 878 6091 8377
 +
 +
Код доступа: 1234
 +
 +
Т.к. ЭК 1 --- это, по сути, контрольная работа, то правила его проведения такие же, как и у КР 1 (см. ниже).
 +
 +
Список задач для подготовки к ЭК 1 можно посмотреть в [https://www.dropbox.com/s/3ai7ou195gcd6wm/%D0%94%D0%B8%D1%81%D0%BA%D1%80_%D0%9C%D0%B0%D1%82_%D0%AD%D0%9A_1_%D0%A1%D0%BF%D0%B8%D1%81%D0%BE%D0%BA_%D0%97%D0%B0%D0%B4%D0%B0%D1%87_%D0%94%D0%BB%D1%8F_%D0%9F%D0%BE%D0%B4%D0%B3%D0%BE%D1%82%D0%BE%D0%B2%D0%BA%D0%B8.pdf?dl=0 '''этом файле''']. Если студенту нужен какой-то элементарный факт, прямо не относящийся к нашему курсу (например, формула для синуса тройного угла), то он может спросить этот факт у одного из преподавателей.
 +
 +
 +
'''Контрольная Работа 1'''
 +
 +
КР 1 пройдет 13.11.2021 в формате Zoom конференции, начало в 12:30 (но желательно подключиться к конференции в 12:20), ссылка на Zoom конференцию:
 +
 +
Тема: Дискретная_Мат_КНАД_КР_1
 +
 +
https://us02web.zoom.us/j/87860918377?pwd=SXp4WFQ5MlZMSko2NkNFMTVIZElBQT09
 +
 +
Идентификатор конференции: 878 6091 8377
 +
 +
Код доступа: 1234
 +
 +
На решение заданий КР 1 будет отведено 100-110 мин. В течение этого времени студенту запрещается пользоваться любыми записями (конспект лекций/семинаров, справочные таблицы, шпаргалки, ...) и любыми электронными устройствами (мобильными телефонами, часами, калькуляторами, наушниками, товарищем по несчастью...); решение заданий КР 1 записывается студентом на бумаге. После окончания этого времени будет выделено отдельное время для фотографирования/сканирования работы и загрузке ее в Google форму, в течение этого отдельного времени студент не может вносить изменения в работу (но, разумеется, может пользоваться телефоном/сканером/компьютером).
 +
 +
Описание КР 1 можно посмотреть в [https://www.dropbox.com/s/vjg0q6r2rg0v6wi/%D0%94%D0%B8%D1%81%D0%BA%D1%80_%D0%9C%D0%B0%D1%82_%D0%9A%D0%A0_1_%D0%A1%D0%BF%D0%B8%D1%81%D0%BE%D0%BA_%D0%97%D0%B0%D0%B4%D0%B0%D1%87_%D0%94%D0%BB%D1%8F_%D0%9F%D0%BE%D0%B4%D0%B3%D0%BE%D1%82%D0%BE%D0%B2%D0%BA%D0%B8.pdf?dl=0 '''этом файле''']. Если студенту нужен какой-то элементарный факт, прямо не относящийся к нашему курсу (например, формула для синуса тройного угла), то он может спросить этот факт у одного из преподавателей.
 +
 +
При написании КР 1 студент обязан включить в Zoom камеру и демонстрацию рабочего стола, рабочее место студента должно попадать в поле зрение камеры (при несоблюдении этих условий студент не допускается к написанию КР 1). Вопросы, касающиеся технических проблем на стороне студента (отключение Интернет, зависание компьютера, кот, разорвавший работу,...), будут решаться в индивидуальном порядке.
  
 
== Коллоквиумы ==
 
== Коллоквиумы ==
 +
 +
'''Коллоквиум 2'''
 +
 +
Кол. 2 запланирован на 14-е и 15-е декабря (но, при наличии возможности у принимающего, его можно сдать и в соседние даты) и пройдет в формате Zoom конференции.
 +
 +
Правила проведения и структура Кол. 2 такие же, как и у Кол. 1 (см. ниже).
 +
 +
Список вопросов на привести определение / формулировку можно посмотреть в [https://www.dropbox.com/s/j6acapjmh2hedew/%D0%94%D0%B8%D1%81%D0%BA%D1%80_%D0%9C%D0%B0%D1%82_%D0%9A%D0%BE%D0%BB_2_%D0%A1%D0%BF%D0%B8%D1%81%D0%BE%D0%BA_%D0%9E%D0%BF%D1%80%D0%B5%D0%B4%D0%B5%D0%BB%D0%B5%D0%BD%D0%B8%D0%B9_%D0%B8_%D0%A4%D0%BE%D1%80%D0%BC%D1%83%D0%BB%D0%B8%D1%80%D0%BE%D0%B2%D0%BE%D0%BA.pdf?dl=0 ''' этом файле. ''']
 +
 +
Список вопросов на привести доказательство можно посмотреть в [https://www.dropbox.com/s/tsgwxc3fn9ptg0b/%D0%94%D0%B8%D1%81%D0%BA%D1%80_%D0%9C%D0%B0%D1%82_%D0%9A%D0%BE%D0%BB_2_%D0%A1%D0%BF%D0%B8%D1%81%D0%BE%D0%BA_%D0%94%D0%BE%D0%BA%D0%B0%D0%B7%D0%B0%D1%82%D0%B5%D0%BB%D1%8C%D1%81%D1%82%D0%B2.pdf?dl=0 ''' этом файле. ''']
 +
 +
'''Коллоквиум 1'''
 +
 +
Кол. 1 запланирован на период с 27 по 29 октября (но еще есть небольшая вероятность, что пройдет на неделю позже) и пройдет в формате Zoom конференции.
 +
 +
Чтобы попасть на Кол. 1, вам нужно сначала на него записаться. У каждой из двух групп будет своя таблица для записи, для того, чтобы записаться на Кол. 1, в соответствующей таблице студент должен будет выбрать свободный временной слот и вписать в него свои Фамилия Имя. Обращаем ваше внимание на то, что за день до начала Кол. 1 запись в таблицу будет закрыта.
 +
 +
Кол. 1 будет проходить следующем образом: в указанное в таблице время, студент подключается к Zoom конференции (ссылки будут предоставлены позже), получает билет, готовится (примерно) 40 мин., фотографирует/сканирует свою работу, отправляет работу преподавателю, отвечает на вопросы по работе и доп. вопросы.
 +
 +
В билете будет:
 +
 +
1) четыре вопроса на привести определение / формулировку. Список этих вопросов приведен в [https://www.dropbox.com/s/gspjva3t642n1wj/%D0%94%D0%B8%D1%81%D0%BA%D1%80_%D0%9C%D0%B0%D1%82_%D0%9A%D0%BE%D0%BB_1_%D0%A1%D0%BF%D0%B8%D1%81%D0%BE%D0%BA_%D0%9E%D0%BF%D1%80%D0%B5%D0%B4%D0%B5%D0%BB%D0%B5%D0%BD%D0%B8%D0%B9_%D0%B8_%D0%A4%D0%BE%D1%80%D0%BC%D1%83%D0%BB%D0%B8%D1%80%D0%BE%D0%B2%D0%BE%D0%BA.pdf?dl=0 '''этом'''] файле, каждый вопрос оценивается в 1 балл (за вопрос можно получить 0 или 0,5 или 1 балл).
 +
 +
2) один вопрос на привести доказательство. Список этих вопросов приведен в [https://www.dropbox.com/s/9gxdc9bitwvsgzw/%D0%94%D0%B8%D1%81%D0%BA%D1%80_%D0%9C%D0%B0%D1%82_%D0%9A%D0%BE%D0%BB_1_%D0%A1%D0%BF%D0%B8%D1%81%D0%BE%D0%BA_%D0%94%D0%BE%D0%BA%D0%B0%D0%B7%D0%B0%D1%82%D0%B5%D0%BB%D1%8C%D1%81%D1%82%D0%B2.pdf?dl=0 '''этом'''] файле, этот вопрос оценивается в 4 балла (возможна оценка от 0 до 4 баллов с шагом 0,5 балла).
 +
 +
3) дополнительный вопрос(ы). Это может быть любой вопрос(ы), относящийся к курсу (например, не очень трудоемкая задача), но не доказательство из списка для второго вопроса. Этот вопрос(ы) оценивается в 2 балла (возможна оценка от 0 до 2 баллов с шагом 0,5 балла).
 +
 +
Во время подготовки студенту запрещается пользоваться любыми записями (конспект лекций/семинаров, справочные таблицы, шпаргалки, ...) и любыми электронными устройствами (мобильными телефонами, часами, калькуляторами, помощью лучшего друга,...). При сдачи Кол. 1 студент обязан включить в Zoom камеру и демонстрацию рабочего стола (в случает отсутствия камеры студент не допускается к сдачи Кол. 1). Вопросы, касающиеся технических проблем на стороне студента (отключение Интернет, зависание компьютера, кот, разорвавший работу,...), будут решаться в индивидуальном порядке.
  
 
== Список рекомендуемой литературы ==
 
== Список рекомендуемой литературы ==

Версия 03:22, 18 декабря 2021

Преподаватели и учебные ассистенты

Группа 211 212
Лектор Мажуга А.М.
Семинарист Трушин Антон Мажуга А.М.
Приемные часы TBD Среда, 17:00 -- 21:00, через Zoom
нужно предупредить за день
Ассистент Смородинов Александр
asmorodinov66@gmail.com
Копытов Даниил
daniil.copytow43@yandex.ru

О курсе

Эта страничка содержит ссылки на материалы по курсу Дискретная Математика в 2021/2022 учебном году на программе "Компьютерные науки и анализ данных" Факультета Компьютерных Наук НИУ ВШЭ.

Конспект Лекций

Если вы заметили опечатку/ошибку в конспектах лекций, то, пожалуйста, опишите ее в этой таблице.

Модуль 2

  • Лекция 15 (15.12.2021). Начала теории чисел, Часть-IV; функция Эйлера; понятия мультипликативной и вполне мультипликативной функции; мультипликативность функции Эйлера; две замкнутые формы для выражения значения функции Эйлера; теорема Эйлера; некоторые дополнительные свойства функции Эйлера (без доказательства); китайская теорема об остатках.
  • Лекция 14 (08.12.2021). Начала теории чисел, Часть-III; простые и составные натуральные числа; бесконечность множества простых чисел; факторизация натурального числа и основная теорема арифметики; теорема об изоморфизме порядков для отношения делимости; НОД и НОК в терминах факторизации; теорема Вильсона; малая теорема Ферма.
  • Лекция 13 (04.12.2021). Начала теории чисел, Часть-II; понятия сравнения по модулю, классы эквивалентности и вычеты; операции сложения и умножения вычетов, корректность определения и основные свойства; существование обратного вычета по умножению; описание множества решений сравнения 1-й степени.
  • Лекция 12 (24.11.2021). Начала теории чисел, Часть-I; деление с остатком; корректность операции деления с остатком; наибольший общий делитель; основные свойства НОД (существование, единственность, au+bv формула); расширенный алгоритм Евклида.
  • Лекция 11 (17.11.2021). Отношения, Часть-III: Частичные порядки; понятие частичного порядка (строгий/нестрогий/линейный); теорема о взаимно однозначном соответствии между строгими и нестрогими порядками; понятие частично упорядоченного множества; минимальные/наименьшие/максимальные/наибольшие элементы; лексикографический порядок; изоморфизм порядков; сумма порядков.
  • Лекция 10 (10.11.2021). Отношения и функции, Часть-II; понятие обратной функции; теорема об обратной функции; примеры обратимых функций; теорема об обратной функции на конечном множестве; отношения эквивалентности; понятия клfсса эквивалентности и фактормножества; теорема об описании эквивалентностей; изоморфизмы графов.
  • Лекция 9 (03.11.2021). Отношения и функции, Часть-I; понятие бинарного отношения и связанные с ним понятия; транспонирование и композиция бинарных отношений; ассоциативность композиции бинарных отношений; основные типы бинарных отношений (рефлексивные, симметричные и т.д.); понятие функции и связанные с ним понятия; инъективные, сюръективные, биективные функции и их основные свойства.
  • Лекция 8 (27.10.2021). Комбинаторика, Часть-III; биномиальные коэффициенты и их основные свойства; треугольник Паскаля; мультиномиальные коэффициенты; явная формула для мультиномиальных коэффициентов; числа Каталана; явная формула для чисел Каталана.

Модуль 1

  • Лекция 7 (13.10.2021). Комбинаторика, Часть-II; комбинаторный принцип деления; размещения, теорема о числе размещений; сочетания, теорема о числе сочетаний.
  • Лекция 6 (06.10.2021). Графы, Часть-III: Ориентированные графы; понятие ориентированного графа, степени входа и выхода вершины орграфа; теорема о сумме степеней вершин орграфа; ориентированный путь и цикл в орграфе; понятие сильной связности; ациклические орграфы и их описание; задача о кенигсбергских мостах, эйлеровы циклы и эйлеровы графы; теорема об описании эйлеровых орграфов.
  • Лекция 5 (29.09.2021). Графы, Часть-II: Деревья; понятия леса и дерева; теорема об описании лесов (эквивалентные определения леса); теорема об описании деревьев (эквивалентные определения дерева); размерность графа и ее основные комбинаторные свойства; теорема о размерности леса; теорема о размерности дерева (связь числа вершин и ребер в дереве); листья в девере; теорема об остовных деревьях; теорема Кэли о числе остовных деревьев в полном графе (без доказательства).
  • Лекция 4 (22.09.2021). Графы, Часть-I: Введение; понятие графа, матрицы смежности и инцидентности; теорема о сумме степеней вершин графа; связность, области достижимости и компоненты связности графа.
  • Лекция 3 (17.09.2021). Комбинаторика, Часть-I; основные комбинаторные принципы: правило произведения и правило суммы; понятие последовательности; теорема о числе слов в конечном алфавите; формула включения-исключения.
  • Лекция 2 (15.09.2021). Введение в теорию множеств; основные способы задания множества; основные операции над множествами; (полный) принцип математической индукции.
  • Лекция 1 (08.09.2021). Введение в алгебру логики; понятие высказывания, простые и сложные (= составные) высказывания; основные логические связки; логически эквивалентные высказывания; примеры эквивалентностей; тавтологии и противоречия; кванторы всеобщности и существования.

Семинары

Материал с семинаров 211-й группы:

Модуль 1

Материал с семинаров 212-й группы:

Модуль 2

Модуль 1

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

Обязательные ДЗ для 211-й группы:

Модуль 1

Обязательные ДЗ для 212-й группы:

Модуль 2

  • ДЗ №11,5 (выдача: 29.11.21, дедлайн: 05.12.21)
  • ДЗ №10 (выдача: 22.11.21, дедлайн: 28.11.21)
  • ДЗ №9 (выдача: 07.11.21, дедлайн: 19.11.21)
  • ДЗ №8 (выдача: 05.11.21, дедлайн: 12.11.21)

Модуль 1

  • ДЗ №7 (выдача: 18.10.21, дедлайн: 31.10.21)
  • ДЗ №6 (выдача: 07.10.21, дедлайн: 15.10.21)
  • ДЗ №5 (выдача: 30.09.21, дедлайн: 08.10.21)
  • ДЗ №4 (выдача: 26.09.21, дедлайн: 03.10.21)
  • ДЗ №3 (выдача: 23.09.21, дедлайн: 01.10.21)
  • ДЗ №2 (выдача: 16.09.21, дедлайн: 24.09.21)
  • ДЗ №1 (выдача: 08.09.21, дедлайн: 17.09.21)

Ведомость с оценками и Контроль посещаемости

Оценки ДЗ:

??? 212

Формы контроля и оценивание

Курс Дискретная Математика на КНАД читается в 1 и 2 модулях.


В течение курса установлены следующие формы контроля:

  • письменный экзамен (ЭК);
  • письменная контрольная работа (KР);
  • два коллоквиума (KЛ1, КЛ2);
  • несколько самостоятельных работ (СР, где СР --- есть среднее арифметическое оценок всех самостоятельных работ);
  • несколько домашних заданий (ДЗ, где ДЗ --- есть среднее арифметическое оценок всех домашних работ; обычно одно ДЗ соответствует одному семинару).

Блокирующих форм контроля нет.

Все оценки, а именно ЭК, KР, КЛ1, КЛ2, СР и ДЗ, являются вещественными числами, принадлежащими отрезку [0;10] и вычисляются без округления.

Итоговая Оценка за дисциплину, ИО, вычисляется по следующей формуле:

ИО = Округление(1/8*КЛ1+1/8*КЛ2+1/8*КР+7/40*ДЗ+3/20*СР+3/10*ЭК),

где функция Округление(r) определена следующим образом: если десятичная часть неотрицательного вещественного числа r лежит в полуинтервале [0;0,2), то r округляется до максимального целого числа, не превосходящего r (например, Округление(7,199)=7); если десятичная часть неотрицательного вещественного числа r лежит в интервале (0,7;1), то r округляется до наименьшего целого числа, большего r (например, Округление(7,701)=8); если десятичная часть неотрицательного вещественного числа r лежит в отрезке [0,2;0,7], то r округляется до максимального целого числа, не превосходящего r, если студент присутствовал менее чем на 66% семинаров, иначе r округляется до наименьшего целого числа, не меньшего r.

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

Без уважительной причины студент может сдать только одно ДЗ за семестр после дедлайна (оно оценивается без штрафа), это ДЗ нельзя сдавать в течение последней недели перед зимней сессией. В случае наличия уважительной причины ситуация с ДЗ решается индивидуально.

Контрольные Работы и Экзамены

Экзамен 1

ЭК 1 пройдет 22.12.2021 в формате Zoom конференции, начало в 13:00, ссылка на Zoom конференцию:

Тема: Дискретная_Мат_КНАД_ЭК_1

https://us02web.zoom.us/j/87860918377?pwd=SXp4WFQ5MlZMSko2NkNFMTVIZElBQT09

Идентификатор конференции: 878 6091 8377

Код доступа: 1234

Т.к. ЭК 1 --- это, по сути, контрольная работа, то правила его проведения такие же, как и у КР 1 (см. ниже).

Список задач для подготовки к ЭК 1 можно посмотреть в этом файле. Если студенту нужен какой-то элементарный факт, прямо не относящийся к нашему курсу (например, формула для синуса тройного угла), то он может спросить этот факт у одного из преподавателей.


Контрольная Работа 1

КР 1 пройдет 13.11.2021 в формате Zoom конференции, начало в 12:30 (но желательно подключиться к конференции в 12:20), ссылка на Zoom конференцию:

Тема: Дискретная_Мат_КНАД_КР_1

https://us02web.zoom.us/j/87860918377?pwd=SXp4WFQ5MlZMSko2NkNFMTVIZElBQT09

Идентификатор конференции: 878 6091 8377

Код доступа: 1234

На решение заданий КР 1 будет отведено 100-110 мин. В течение этого времени студенту запрещается пользоваться любыми записями (конспект лекций/семинаров, справочные таблицы, шпаргалки, ...) и любыми электронными устройствами (мобильными телефонами, часами, калькуляторами, наушниками, товарищем по несчастью...); решение заданий КР 1 записывается студентом на бумаге. После окончания этого времени будет выделено отдельное время для фотографирования/сканирования работы и загрузке ее в Google форму, в течение этого отдельного времени студент не может вносить изменения в работу (но, разумеется, может пользоваться телефоном/сканером/компьютером).

Описание КР 1 можно посмотреть в этом файле. Если студенту нужен какой-то элементарный факт, прямо не относящийся к нашему курсу (например, формула для синуса тройного угла), то он может спросить этот факт у одного из преподавателей.

При написании КР 1 студент обязан включить в Zoom камеру и демонстрацию рабочего стола, рабочее место студента должно попадать в поле зрение камеры (при несоблюдении этих условий студент не допускается к написанию КР 1). Вопросы, касающиеся технических проблем на стороне студента (отключение Интернет, зависание компьютера, кот, разорвавший работу,...), будут решаться в индивидуальном порядке.

Коллоквиумы

Коллоквиум 2

Кол. 2 запланирован на 14-е и 15-е декабря (но, при наличии возможности у принимающего, его можно сдать и в соседние даты) и пройдет в формате Zoom конференции.

Правила проведения и структура Кол. 2 такие же, как и у Кол. 1 (см. ниже).

Список вопросов на привести определение / формулировку можно посмотреть в этом файле.

Список вопросов на привести доказательство можно посмотреть в этом файле.

Коллоквиум 1

Кол. 1 запланирован на период с 27 по 29 октября (но еще есть небольшая вероятность, что пройдет на неделю позже) и пройдет в формате Zoom конференции.

Чтобы попасть на Кол. 1, вам нужно сначала на него записаться. У каждой из двух групп будет своя таблица для записи, для того, чтобы записаться на Кол. 1, в соответствующей таблице студент должен будет выбрать свободный временной слот и вписать в него свои Фамилия Имя. Обращаем ваше внимание на то, что за день до начала Кол. 1 запись в таблицу будет закрыта.

Кол. 1 будет проходить следующем образом: в указанное в таблице время, студент подключается к Zoom конференции (ссылки будут предоставлены позже), получает билет, готовится (примерно) 40 мин., фотографирует/сканирует свою работу, отправляет работу преподавателю, отвечает на вопросы по работе и доп. вопросы.

В билете будет:

1) четыре вопроса на привести определение / формулировку. Список этих вопросов приведен в этом файле, каждый вопрос оценивается в 1 балл (за вопрос можно получить 0 или 0,5 или 1 балл).

2) один вопрос на привести доказательство. Список этих вопросов приведен в этом файле, этот вопрос оценивается в 4 балла (возможна оценка от 0 до 4 баллов с шагом 0,5 балла).

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

Во время подготовки студенту запрещается пользоваться любыми записями (конспект лекций/семинаров, справочные таблицы, шпаргалки, ...) и любыми электронными устройствами (мобильными телефонами, часами, калькуляторами, помощью лучшего друга,...). При сдачи Кол. 1 студент обязан включить в Zoom камеру и демонстрацию рабочего стола (в случает отсутствия камеры студент не допускается к сдачи Кол. 1). Вопросы, касающиеся технических проблем на стороне студента (отключение Интернет, зависание компьютера, кот, разорвавший работу,...), будут решаться в индивидуальном порядке.

Список рекомендуемой литературы