DM2-pilot2020/2021 — различия между версиями
| (не показаны 202 промежуточные версии 6 участников) | |||
| Строка 1: | Строка 1: | ||
= Дискретная математика на 2-ом курсе ПМИ (пилотный поток)= | = Дискретная математика на 2-ом курсе ПМИ (пилотный поток)= | ||
| − | Лекции проходят по субботам в 13-14:20 онлайн. | + | Лекции проходят по субботам в 13-14:20 онлайн на платформе Zoom [https://zoom.us/j/99056983180?pwd=MkxkSjRWYm53b21oSXFOSVloS1dtZz09 по ссылке https://zoom.us/j/99056983180?pwd=MkxkSjRWYm53b21oSXFOSVloS1dtZz09]. При наличии технических проблем в Zoom лекции переносятся в Google meet: [https://meet.google.com/xoq-qtjo-pny meet.google.com/xoq-qtjo-pny] |
==Новости== | ==Новости== | ||
| − | + | === 1 февраля === | |
| − | + | ||
| − | + | Пересдача экзамена комиссии понедельник, 1 февраля, в 15:00: https://zoom.us/j/92864977568 | |
| − | + | ===23 января=== | |
| + | Пересдача 25 января в 15:00 по ссылке: https://zoom.us/j/92864977568 | ||
| + | ===16 января=== | ||
| + | Пересдачи назначены на 18 и 25 января в 15:00. Пересдача комиссии - 1 февраля в 15:00. | ||
| − | == | + | ===Итоговые ведомости=== |
| − | + | [https://docs.google.com/spreadsheets/d/1eqWW669ZdamECGHEwn2RY_x6kRrzmS03/edit#gid=1682879045 БПМИ 191], [https://docs.google.com/spreadsheets/d/1kV-AHGbbl4XhctjF6-Ufk9CR2PeVgTFd/edit#gid=218358711 Таблица со всеми оценками] | |
| − | + | ||
| − | + | ||
| − | + | [https://docs.google.com/spreadsheets/d/1CugeLWUkX48-mMPJ58eDRwEi1-R_NDdo/edit#gid=511315823 БПМИ 192], [https://docs.google.com/spreadsheets/d/14MTCwQBIGgQWI19RzK8dFXOxh5MNp5J-/edit#gid=979782108 Таблица со всеми оценками] | |
| − | + | ||
| − | + | ||
| − | + | [https://docs.google.com/spreadsheets/d/1icPlrTh-IfhW2YL1DEulzvkm_kr8Qf62/edit#gid=1216485817 БПМИ 194], [https://www.dropbox.com/home/hseDM2/2020-21/tables?preview=194.xlsx Таблица со всеми оценками] | |
| − | + | ||
| − | = | + | [https://docs.google.com/spreadsheets/d/1dskZpiU_GxbvijCipGpYLiLQjyKWn96_/edit#gid=1540717211 Не ФКН] |
| − | + | ===29 декабря=== | |
| + | Выложены [https://drive.google.com/file/d/1PB6uFwX5hl43aJlOVaWFBGA_N6GSwmrJ/view?usp=sharing решения экзаменационных задач] | ||
| − | = | + | Выложены [https://docs.google.com/spreadsheets/d/13j4KY-n3ZqkDRczudnL_w92v8AJybxHEVsGbo6eJ1EU/edit#gid=0 оценки и критерии выставления оценок экзаменационных работ] |
| − | + | Апелляция по поводу оценок за экзамен состоится 30 декабря в 18:00 в дискорде https://discord.gg/v5DbugV. | |
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ===27 декабря=== | |
| + | ====Инструкция к экзамену (письменному) 28 декабря.==== | ||
| + | Начало экзамена в 11 часов на платформе Zoom https://zoom.us/j/99884492481. Вариант состоит из 5 задач, которые нужно решить за полтора часа. | ||
| + | Экзамен проходит с прокторингом. Студенты загружают задание по ссылке https://www.dropbox.com/s/yroi37a7xz2mqzz/28.12.pdf?dl=0, решают на бумаге, в конце экзамена делают фотографии/сканы решений, сшивают в один PDF файл и загружают по следующей ссылке https://www.dropbox.com/request/f94hby1pjt00x5is0beh. Черновики отсылать не надо. Крайний срок посылки - 15 мин после конца экзамена. | ||
| − | + | Экзамен длится 90 минут. Во время экзамена студенты должны включить камеры. Во время экзамена разрешено смотреть на любые материалы, загруженные на компьютер до начала экзамена, писать на листах бумаги, а также смотреть на любые бумажные материалы на столе. Студенты могут пользоваться мышью и клавиатурой только для того, чтобы перелистывать загруженные материалы и условия задач. Если во время экзамена у студента возникнет вопрос по условию задачи, он может устно задать его и преподаватель даст на него ответ. | |
| − | + | ||
| − | + | Если у студента случился один или два обрыва связи продолжительностью менее пяти минут, он может продолжить написание экзамена (дополнительное время при этом не предоставляется). Если случился обрыв связи продолжительностью дольше 5 минут или более двух пятиминутных, то считается, что студент пропустил экзамен. В этом случае ему будет предложено без штрафов сдать экзамен устно в течение недели с момента данного экзамена. | |
| − | + | ===28 ноября=== | |
| + | Выложено пятое домашнее задание. | ||
| − | + | ===25 ноября=== | |
| + | В понедельник 30 ноября в 16:20-17:40 состоится дополнительная лекция взамен | ||
| + | одной из двух пропущенных лекций. Подключиться к конференции Zoom: | ||
| + | https://zoom.us/j/96230416179?pwd=UFNIbVkrRk5IWGRGcmxGODVXbHNHQT09 | ||
| + | ===19 ноября=== | ||
| + | Лектор болеет ковидом и не может принимать ДЗ в 192 группе. Сдавайте, пожалуйста, ассистенту. | ||
| + | ===31 октября=== | ||
| + | Выложено четвертое домашнее задание. | ||
| − | == | + | ===8 октября=== |
| + | Выложено третье домашнее задание. | ||
| − | + | ===21 сентября=== | |
| + | Выложено второе домашнее задание. | ||
| − | + | ===1 сентября=== | |
| − | + | Первая лекция будет 5 сентября. | |
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | == | + | |
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | Первая лекция будет 5 сентября. | + | |
==Лектор== | ==Лектор== | ||
| Строка 355: | Строка 67: | ||
Верещагин Николай Константинович nikolay.vereshchagin@gmail.com | Верещагин Николай Константинович nikolay.vereshchagin@gmail.com | ||
| − | == | + | ==Семинары и семинаристы== |
| − | 191 Райко Илья Глебович mylntsa.ilya.63@gmail.com | + | 191 Райко Илья Глебович mylntsa.ilya.63@gmail.com по понедельникам 9:30 - 10:50 |
| − | (учебный ассистент ) | + | (учебный ассистент Игорь Тараканов <79851126754@ya.ru>) |
| − | 192 Верещагин Николай Константинович nikolay.vereshchagin@gmail.com | + | 192 Верещагин Николай Константинович (e-mail: nikolay.vereshchagin@gmail.com, skype: vereshchagin, телеграмм @nikolay_vereshchagin) |
| − | (учебный ассистент ) | + | по субботам 14:40 - 16 онлайн на платформе Zoom [https://zoom.us/j/99063463658?pwd=bHdjZEtxNmtJTDBFcnVYUU8zSkkyUT09 по ссылке https://zoom.us/j/99063463658?pwd=bHdjZEtxNmtJTDBFcnVYUU8zSkkyUT09] |
| + | (учебный ассистент Шабалина Анастасия Владимировна shabalina.nasty@gmail.com) | ||
| − | 194 Оноприенко Анастасия Александровна ansidiana@yandex.ru (учебный ассистент ). | + | 194 Оноприенко Анастасия Александровна ansidiana@yandex.ru по понедельникам 11:10 - 12:30 (учебный ассистент Амашукели Игорь Михайлович imamashukeli@edu.hse.ru). Для быстрой связи лучше писать в телеграм @ansidiana. |
==Краткое описание== | ==Краткое описание== | ||
| Строка 371: | Строка 84: | ||
==Отчётность по курсу и критерии оценки== | ==Отчётность по курсу и критерии оценки== | ||
| − | + | === Тесты === | |
| + | В конце каждой лекции будет предлагаться десятиминутный тест с простыми задачами. Целью тестов является контроль за тем, чтобы студенты | ||
| + | внимательно слушали лекцию. К написанию теста допускаются только присутствовавшие на лекции (разрешается десятиминутное опоздание к началу лекции). За каждый тест | ||
| + | выставляется оценка, равная доле правильных ответов, умноженной на 10. | ||
| + | Общая оценка за тесты равняется среднему арифметическому оценок за все тесты. | ||
| − | Оценка за каждое домашнее задание равна доле решенных задач, умноженной на 10. Общая оценка за домашние задания равна среднему арифметическому оценок за решение каждого из заданий. | + | === 6 домашних заданий === |
| − | На решение каждого ДЗ дается 14 дней, решение ДЗ нужно сдавать семинаристу устно (очно или онлайн) или письменно. | + | В течение двух модулей студентам будет дано 6 домашних заданий. |
| − | Сдача домашних заданий после их срока невозможна. | + | Оценка за каждое домашнее задание равна доле решенных задач, умноженной на 10. Общая оценка за домашние задания равна среднему арифметическому оценок за решение каждого из заданий. На решение каждого ДЗ дается 14 дней, решение ДЗ нужно сдавать '''семинаристу или ассистенту''' устно (очно или онлайн) или письменно. Какой из двух видов сдачи ДЗ разрешен, решается семинаристом каждой группы. Сдача домашних заданий после их срока невозможна. |
| − | В случае письменной сдачи ДЗ, оно в будет проверено в течение 10 дней после дедлайна | + | В случае письменной сдачи ДЗ, оно в будет проверено в течение 10 дней после дедлайна и должно быть защищено студентом в течение 3 недель после дедлайна. Для защиты студент должен прийти на консультацию и убедить семинариста или ассистента, что он понимает, что у него написано, и тем самым работа не списана. В случае устной сдачи защиты не требуется. |
| − | Коллоквиум (устный) и экзамен (письменный) оцениваются по десятибалльной системе | + | ===Коллоквиум и письменный экзамен=== |
| − | + | Коллоквиум (устный) и экзамен (письменный) проводятся в конце второго модуля и оцениваются по десятибалльной системе. | |
| − | Оценки за коллоквиум и экзамен входят в итоговую оценку с коэффициентами 0. | + | ===Итоговая оценка=== |
| + | Оценки за коллоквиум и экзамен входят в итоговую оценку с коэффициентами 0.3, а оценки за домашние задания и тесты - с коэффициентом 0.2. | ||
| − | Те, кто не смог прийти на коллоквиум по болезни, могут его сдать отдельно в день пересдачи (один раз). Это же относится и к тем, кто не смог прийти на экзамен | + | Те, кто не смог прийти на коллоквиум по болезни, могут его сдать отдельно в день пересдачи (один раз). Это же относится и к тем, кто не смог прийти на экзамен. Те, кто после всех пересдач получил итоговую оценку менее 4 баллов, сдают устный экзамен комиссии, в этом случае все полученные ранее оценки аннулируются и оценка, полученная на экзамене, является окончательной. На экзамене комиссии будет выдан один билет из билетов коллоквиума (содержащий два теоретических вопроса и задачу), и при необходимости будет дана еще одна дополнительная задача. |
====Правила округления==== | ====Правила округления==== | ||
| − | |||
| − | |||
В оценках за домашние задания промежуточные величины не округляются. Результат | В оценках за домашние задания промежуточные величины не округляются. Результат | ||
| − | вычисляется точно и округляется только в момент выставления | + | вычисляется точно и округляется только в момент выставления итоговой оценки. |
| − | + | Используется арифметическое округление (то есть, 6.5 округляется до 7, а 6.49 - до 6). | |
| − | == | + | ==Сдача домашних заданий== |
| − | + | '''Группа 191:''' сдача домашних заданий проходит в устной форме ассистенту Игорю Тараканову (79851126754@ya.ru, тг @SetSplin) или семинаристу по четвергам (подробнее см. в разделе [[DM2-pilot2020/2021#Консультации|про консультации]]). | |
| − | + | '''Группа 192:''' | |
| + | Сдача домашних заданий семинаристу Н.К. Верещагину проходит только в устной форме по вторникам с 10 до 20, средам с 18 до 20, четвергам с 10 до 20 с помощью Google Meet https://meet.google.com/noy-cait-jph. Сдача домашних заданий ассистенту А. Шабалиной также проходит только в устной форме в понедельник с 14:30 до 17:00, в среду с 10:00 до 15:00, в четверг с 10:00 до 12:00, в пятницу с 10:00 до 17:00, в субботу с 10:00 до 14:00, cвязаться можно через телеграм (@nastyash08) или почту (shabalina.nasty@gmail.com). | ||
| − | + | '''Группа 194:''' сдача домашних заданий проходит в устной форме, задачи принимает преимущественно ассистент Игорь Амашукели (почта imamashukeli@edu.hse.ru, телеграм @iamashukeli) в [https://us04web.zoom.us/j/6780117923?pwd=QjF2ZXFjT2Fsc3JwazJlMHdJSVlOZz09 зуме]. Можно также сдавать семинаристке в [https://discord.gg/v5DbugV дискорде] по четвергам после 14:00 либо в другой день по предварительной договорённости. | |
| − | + | ==Сроки контрольных мероприятий== | |
| − | + | ====Первое домашнее задание: дедлайн для сдачи==== | |
| − | группа | + | группа 191: 21 сентября |
| − | группа | + | группа 192: 19 сентября |
| − | + | группа 194: 21 сентября | |
| − | + | ====Второе домашнее задание: дедлайн для сдачи==== | |
| − | + | группа 191: 7 откября | |
| − | группа | + | группа 192: 5 октября |
| − | группа | + | группа 194: 5 октября |
| − | + | ====Третье домашнее задание: дедлайн для сдачи==== | |
| − | + | группа 191: 26 октября | |
| − | группа | + | группа 192: 22 октября |
| − | + | группа 194: 23 октября | |
| − | + | ====Четвертое домашнее задание: дедлайн для сдачи==== | |
| − | группа | + | группа 191: 23 ноября |
| − | группа | + | группа 192: 24 ноября |
| − | + | группа 194: 22 ноября | |
| − | |||
| − | |||
| − | + | ====Пятое домашнее задание: дедлайн для сдачи==== | |
| − | группа | + | группа 191: |
| − | группа | + | группа 192: 12 декабря |
| − | + | группа 194: 13 декабря | |
| − | + | ====Шестое домашнее задание: дедлайн для сдачи==== | |
| − | группа | + | группа 191: |
| − | группа | + | группа 192: 26 декабря |
| − | группа | + | группа 194: 26 декабря |
| − | === | + | ===Коллоквиум=== |
| + | Коллоквиум пройдёт 14, 15 и 17 декабря в промежуток времени 15:00-19:00. | ||
| − | + | Коллоквиум проводится на платформе Зум, каждому будет назначено время, в которое нужно явиться. В случае неявки без уважительной причины (причина уважительная, если таковой её считает учебный офис) студент получает 0 баллов. | |
| − | + | В начале ответа Вы получите билет, в котором будет три вопроса. Первый | |
| + | вопрос: определение или формулировка теоремы (без доказательства). Во втором вопросе надо будет решить простую задачу на понимание определения. Третий вопрос: доказательство какой-нибудь теоремы. Отвечать надо будет без подготовки в режиме реального времени: рассуждать и вспоминать нужно будет устно в присутствии экзаменатора. При доказательстве теоремы можно расшарить свою запись или конспект и аннотировать их при необходимости. | ||
| − | + | Оценка за коллоквиум формируется следующим образом. Полный ответ на каждый из первых двух вопросов оценивается в 3 балла, | |
| + | а полный ответ на третий вопрос в 4 балла (всего 10 баллов). По правилам НИУ ВШЭ при обнаружении факта помощи извне за коллоквиум ставится 0 баллов. | ||
| − | + | [https://docs.google.com/spreadsheets/d/15tQKxVUkN5ujCjPJ7hja0ppgMs4GLYL2vDCNgjC8M6U/edit?usp=sharing Распределение студентов по дням и времени сдачи.] | |
| + | [https://www.dropbox.com/s/xwcgyj71u320xee/timetable.ods?dl=0 Альтернативная ссылка на Dropbox] | ||
| − | + | [https://www.dropbox.com/s/r4i5d9ip1gv138b/colloq2021.pdf?dl=0 Вопросы к коллоквиуму.] [https://www.dropbox.com/s/vhlm0dggpie37gp/colloq2021.tex?dl=0 Исходник TeX] | |
| − | === | + | ===Экзамен=== |
| + | Начало экзамена в 11 часов 28 декабря на платформе Zoom https://zoom.us/j/99884492481. Вариант состоит из 5 задач, которые нужно решить за полтора часа. | ||
| + | |||
| + | Экзамен письменный. Экзамен проходит с прокторингом. Студенты загружают задание по ссылке https://www.dropbox.com/s/yroi37a7xz2mqzz/28.12.pdf?dl=0, решают на бумаге, в конце экзамена делают фотографии/сканы решений, сшивают в один PDF файл и загружают по следующей ссылке https://www.dropbox.com/request/f94hby1pjt00x5is0beh. Черновики отсылать не надо. Крайний срок посылки - 15 мин после конца экзамена. | ||
| − | + | Экзамен длится 90 минут. Во время экзамена студенты должны включить камеры. Во время экзамена разрешено смотреть на любые материалы, загруженные на компьютер до начала экзамена, писать на листах бумаги, а также смотреть на любые бумажные материалы на столе. Студенты могут пользоваться мышью и клавиатурой только для того, чтобы перелистывать загруженные материалы и условия задач. Если во время экзамена у студента возникнет вопрос по условию задачи, он может устно задать его и преподаватель даст на него ответ. | |
| + | Если у студента случился один или два обрыва связи продолжительностью менее пяти минут, он может продолжить написание экзамена (дополнительное время при этом не предоставляется). Если случился обрыв связи продолжительностью дольше 5 минут или более двух пятиминутных, то считается, что студент пропустил экзамен. В этом случае ему будет предложено без штрафов сдать экзамен устно в течение недели с момента данного экзамена. | ||
| − | на | + | Ссылка на оценки за экзамен https://docs.google.com/spreadsheets/d/13j4KY-n3ZqkDRczudnL_w92v8AJybxHEVsGbo6eJ1EU/edit#gid=0 |
| − | + | Апелляция по поводу оценок за экзамен состоится 30 декабря в 18:00 в дискорде https://discord.gg/v5DbugV. | |
| − | + | ===Пересдачи=== | |
| − | + | Пересдачи состоятся 18 и 25 января в 15:00. Подключение по ссылке: | |
| + | https://zoom.us/j/92864977568 | ||
| − | на 15:00 | + | Комиссия назначена на 1 февраля 15:00 https://zoom.us/j/92864977568 |
| + | Сдача экзамена комиссии происходит устно. Все предыдущие оценки аннулируются. На экзамене будет выдан один билет из билетов коллоквиума (содержащий два теоретических вопроса и задачу), и при необходимости будет дана еще одна дополнительная задача. | ||
| + | ==Домашние задания == | ||
| + | [https://www.dropbox.com/s/r7lvqpre8tbh5t2/hw1.pdf?dl=0 Домашнее задание №1] | ||
| + | [https://www.dropbox.com/s/i7mlkccj2p07rht/hw2.pdf?dl=0 Домашнее задание №2] | ||
| + | [https://www.dropbox.com/s/f6qufic56sx3eme/hw3.pdf?dl=0 Домашнее задание №3] | ||
| − | + | [https://www.dropbox.com/s/6qk0m2ighsfr2j5/hw4.pdf?dl=0 Домашнее задание №4] | |
| − | [https://www.dropbox.com/s/ | + | [https://www.dropbox.com/s/c9w7ltfl1inb68o/hw5.pdf?dl=0 Домашнее задание №5] |
| − | + | [https://www.dropbox.com/s/r1phpwmjzlkni7o/hw6.pdf?dl=0 Домашнее задание №6] | |
| − | [https://www.dropbox.com/s/ | + | |
| − | == | + | ==Оценки за домашние задания и тесты== |
| + | |||
| + | [https://www.dropbox.com/s/4ke090dcla3ulgu/191.xls?dl=0 группа 191] | ||
| − | + | [https://www.dropbox.com/s/hd8a8y51gzyhjp9/192.xls?dl=0 группа 192] | |
| − | + | ||
| + | [https://www.dropbox.com/s/o87d5fgq53rc9ha/194.xls?dl=0 группа 194] | ||
| − | [https:// | + | ===[https://docs.google.com/spreadsheets/d/1EMypMXYQUYpbLqN3u7rrXJHunoUsELOxZBrHqvd-plc/edit#gid=301836361 Оценки за Tест 1]=== |
| + | ===[https://docs.google.com/spreadsheets/d/1uIG9rAvdzewmheivrHNijdrtKq2MxBiUgBEGaMs41V4/edit#gid=76635409 Оценка за Тест 2]=== | ||
| − | + | ===[https://docs.google.com/spreadsheets/d/1PBEsA9NFhTQjDXFn5NKxKnI-Xs7c58Cq67KZIplEPLk/ Оценки за Тест 3]=== | |
| − | + | ||
| − | == | + | ===[https://docs.google.com/spreadsheets/d/1ibKMA3IAWxXbFRbsrCp5OcUHhcsbSUwBPsxM_LpXnVY/edit#gid=2068781511 Оценки за Тест 4]=== |
| − | [https:// | + | ===[https://docs.google.com/spreadsheets/d/1bnLNrg864dD2dhQWmVh-4JTY_HUopTFb5Em_lf_HSgY/edit#gid=1479969798 Оценки за Тест 5]=== |
| − | + | ||
| − | + | ||
| − | + | ===[https://docs.google.com/spreadsheets/d/1I-WclFzpDtWRy8KCFqcQlIAbfu8elZFhpAy-upQpZcM/edit?usp=sharing Оценки за Тест 6]=== | |
| − | + | ||
| − | + | ||
| − | + | ||
| − | [https:// | + | |
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | [https:// | + | ===[https://docs.google.com/spreadsheets/d/1K1vi-vzkeCa1rpJsJ3VoYlL_lV21PnW8il4eumB0B_U/edit?usp=sharing Оценки за Тест 7]=== |
| − | [https:// | + | ===[https://docs.google.com/spreadsheets/d/17odAXShM2GLhQDIe1eoiNhQIqnzAupzPUnyVi5nJopA/ Оценки за Тест 8]=== |
| − | [https:// | + | ===[https://docs.google.com/spreadsheets/d/1yBZJsVYOelPzgvG7DzAVSnQuXvN4FaQPFQV6Pabekes/ Оценки за Тест 9]=== |
| − | [https:// | + | ===[https://docs.google.com/spreadsheets/d/1SDlVMR2cVtFE5lpKJRfI2LJwd4UU4GbAb67KH3yHa9w/edit?usp=sharing Оценки за Тест 10]=== |
| − | [https:// | + | ===[https://docs.google.com/spreadsheets/d/1SW1TMeeAXzmIQfxA9R7MFavAOIjVBN0LxUHN1YKKp0I/edit?usp=sharing Оценки за Тест 12]=== |
==Примерное содержание лекций== | ==Примерное содержание лекций== | ||
| Строка 558: | Строка 277: | ||
==Прочитанные лекции== | ==Прочитанные лекции== | ||
| − | ====Лекция 1 ( | + | ====Лекция 1 (5 сентября). ==== |
| − | + | ||
Общее неформальное понятие алгоритма и конструктивного объекта. Исходное данное и результат работы алгоритма. Пошаговая работа алгоритма. | Общее неформальное понятие алгоритма и конструктивного объекта. Исходное данное и результат работы алгоритма. Пошаговая работа алгоритма. | ||
Определение вычислимой частичной функции из N в N. Счетность семейства частичных вычислимых функций, и существование невычислимых функций. | Определение вычислимой частичной функции из N в N. Счетность семейства частичных вычислимых функций, и существование невычислимых функций. | ||
| − | Разрешимые подмножества N. Перечислимые подножества N. Счетность семейства перечислимых множеств, и существование неперечислимых. Эквивалентные определения перечислимости (полуразрешимость, область определения вычислимой функции, множество значений вычислимой функции - без подробного доказательства). Теорема Поста. Теорема о графике. | + | Разрешимые подмножества N. Перечислимые подножества N. Счетность семейства перечислимых множеств, и существование неперечислимых. Эквивалентные определения перечислимости (полуразрешимость, область определения вычислимой функции, множество значений вычислимой функции, проекции разрешимых множеств - без подробного доказательства). Теорема Поста. Теорема о графике. |
| − | + | [https://www.youtube.com/playlist?list=PLEwK9wdS5g0oT-ldgJejMd9gAKXZdJYHm Видеозапись лекции и семинара] | |
| − | Универсальные вычислимые функции (нумерации) для семейства частичных вычислимых функций натурального аргумента. Несуществование универсальной вычислимой функции для семейства тотальных вычислимых функций натурального аргумента (диагональное рассуждение) | + | ====Лекция 2 (12 сентября). ==== |
| + | |||
| + | Универсальные вычислимые функции (нумерации) для семейства частичных вычислимых функций натурального аргумента. Несуществование универсальной вычислимой функции для семейства тотальных вычислимых функций натурального аргумента (диагональное рассуждение). | ||
Вычислимая функция, не имеющая тотального вычислимого продолжения. Перечислимое неразрешимое множество. Неразрешимость проблемы применимости. | Вычислимая функция, не имеющая тотального вычислимого продолжения. Перечислимое неразрешимое множество. Неразрешимость проблемы применимости. | ||
| Строка 574: | Строка 294: | ||
Перечислимые неотделимые множества. | Перечислимые неотделимые множества. | ||
| − | ====Лекция 3 ( | + | ====Лекция 3 (19 сентября). ==== |
| + | Перечислимые неотделимые множества. | ||
| − | + | Главные универсальные функции. | |
| + | Теорема Райса-Успенского. | ||
| + | Теорема Клини о неподвижной точке. | ||
| − | + | ====Лекция 4 (26 сентября). ==== | |
| + | Еще раз о теореме Клини. | ||
| − | ====Лекция | + | Сводимости: m-сводимость и Тьюрингова сводимость. Их свойства. Полные перечислимые множества. Теорема Мучника - Фридберга (без доказательства). |
| + | |||
| + | Односторонние и двусторонние ассоциативные исчисления. Полугруппы, заданные порождающими и соотношениями. | ||
| + | |||
| + | ====Лекция 5 (3 октября). ==== | ||
Определение машин Тьюринга и вычислимых на машинах Тьюринга функций. Тезис Чёрча-Тьюринга. Неразрешимость проблемы остановки машины Тьюринга. | Определение машин Тьюринга и вычислимых на машинах Тьюринга функций. Тезис Чёрча-Тьюринга. Неразрешимость проблемы остановки машины Тьюринга. | ||
| − | Неразрешимость проблемы достижимости в односторонних | + | Неразрешимость проблемы достижимости в односторонних ассоциативных исчислениях (с доказательством). |
| − | + | ||
| − | ====Лекция | + | ====Лекция 6 (10 октября). ==== |
| + | Неразрешимость проблемы достижимости в двусторонних ассоциативных исчислениях (с доказательством). | ||
| + | Неразрешимость проблемы равенства слов в конечно определенных полугруппах. | ||
| − | Язык логики высказываний, формулы логики высказываний, связь со схемами. Тавтологии, выполнимые формулы. Связь между тавтологиями и выполнимыми формулами. КНФ и ДНФ (напоминание). | + | Язык логики высказываний, формулы логики высказываний, связь со схемами. Выбор набора связок. Тавтологии, выполнимые формулы. Связь между тавтологиями и выполнимыми формулами. КНФ и ДНФ (напоминание). |
| − | Эквивалентные формулы. Основные эквивалентности. | + | Эквивалентные формулы. |
| + | |||
| + | ====Лекция 7 (17 октября). ==== | ||
| + | |||
| + | Основные эквивалентности. | ||
Проблема проверки тавтологичности (выполнимости), ее NP полнота (без точных определений). | Проблема проверки тавтологичности (выполнимости), ее NP полнота (без точных определений). | ||
Исчисление высказываний, понятие вывода. | Исчисление высказываний, понятие вывода. | ||
| + | Теорема корректности исчисления высказываний. | ||
| + | Вывод из гипотез. Лемма о дедукции. | ||
| − | |||
| − | |||
| − | |||
| − | ====Лекция | + | ====Лекция 8 (31 октября). ==== |
| + | Полезные производные правила. Теорема полноты ИВ и ее доказательство. | ||
| + | |||
| + | Ссылка на видеозапись: https://www.youtube.com/playlist?list=PLo3cgfsnO72ctaL2aza8xQ0ZA2S9SqW-c | ||
| + | Ссылка на доску: https://jamboard.google.com/d/1HogjiZP2zrvEOTqOMYdRE10c4HDoQi-kd3p-oK6P-aY/viewer?f=0 | ||
| + | ====Лекция 9 (21 ноября). ==== | ||
Исчисление резолюций: дизъюнкты, правило резолюции, опровержение КНФ в исчислении резолюций, доказательство корректности. | Исчисление резолюций: дизъюнкты, правило резолюции, опровержение КНФ в исчислении резолюций, доказательство корректности. | ||
Теорема полноты (любое, даже бесконечное, непротиворечивое множество дизъюнктов совместно). | Теорема полноты (любое, даже бесконечное, непротиворечивое множество дизъюнктов совместно). | ||
| − | Опровержение пропозициональных формул общего вида в исчислении резолюций | + | Опровержение пропозициональных формул общего вида в исчислении резолюций (не было). |
| − | + | ||
| − | + | ||
Определение формулы первого порядка в данной сигнатуре. Запись утверждений формулами первого порядка. | Определение формулы первого порядка в данной сигнатуре. Запись утверждений формулами первого порядка. | ||
| − | |||
Модели (интепретации) сигнатуры. | Модели (интепретации) сигнатуры. | ||
| − | Нормальные модели | + | Нормальные модели. |
| − | |||
| − | ====Лекция | + | ====Лекция 10 (28 ноября). ==== |
| + | |||
| + | Общезначимые и выполнимые формулы. | ||
| + | Равносильные формулы. | ||
| + | Теории и их модели. Семантическое следование. | ||
Теорема Черча об алгоритмической неразрешимости отношения семантического следования, общезначимости и равносильности формул (с доказательством). | Теорема Черча об алгоритмической неразрешимости отношения семантического следования, общезначимости и равносильности формул (с доказательством). | ||
| Строка 624: | Строка 361: | ||
Дизъюнкты, универсальные дизъюнкты. Исчисление резолюций для доказательства несовместности множеств универсальных дизъюнктов. Теорема корректности ИР. | Дизъюнкты, универсальные дизъюнкты. Исчисление резолюций для доказательства несовместности множеств универсальных дизъюнктов. Теорема корректности ИР. | ||
| − | ====Лекция | + | ====Лекция 11 (30 ноября). ==== |
| − | + | Теорема полноты ИР (для множеств универсальных дизъюнктов). Исчисление резолюций для теорий, состоящих из формул общего вида (приведение к предваренной нормальной форме и сколемизация). | |
| − | Доказательства общезначимости с помощью ИР. Выводимость формулы в теории с помощью ИР. | + | Доказательства общезначимости с помощью ИР. Перечислимость множества общезначимых формул. Выводимость формулы в теории с помощью ИР. Эквивалентность выводимости и семантического следования. |
| − | |||
Теорема компактности. | Теорема компактности. | ||
| − | Гомоморфизмы, эпиморфизмы (сюръективные гомоморфизмы), изоморфизмы. Теорема о сохранении истинности при эпиморфизме (с доказательством). | + | Гомоморфизмы, эпиморфизмы (сюръективные гомоморфизмы), изоморфизмы. Изоморфные интерпретации. Теорема о сохранении истинности при эпиморфизме (с доказательством). |
| − | + | Элементарно эквивалентные модели, элементарная эквивалентность изоморфных моделей. | |
| + | |||
| + | ====Лекция 12 (5 декабря). ==== | ||
| + | |||
| + | Теорема о сохранении истинности при эпиморфизме (с доказательством). | ||
| + | Элементарно эквивалентные модели, элементарная эквивалентность изоморфных моделей. | ||
| − | Аксиомы равенства. | + | Аксиомы равенства. Семантическое следование для нормальных моделей и теорема полноты ИР для нормальных моделей (если теория не имеет нормальных моделей, то из |
её аксиом и аксиом равенства можно вывести пустой дизъюнкт). | её аксиом и аксиом равенства можно вывести пустой дизъюнкт). | ||
| − | |||
Игры Эренфойхта. Примеры: упорядоченные множества целых и рациональных чисел, | Игры Эренфойхта. Примеры: упорядоченные множества целых и рациональных чисел, | ||
| − | рациональных и действительных чисел | + | рациональных и действительных чисел. |
Доказательство элементарной эквивалентности с помощью игры Эренфойхта (доказательство в одну сторону: если Консерватор имеет выигрышную стратегию, то модели элементарно эквивалентны). | Доказательство элементарной эквивалентности с помощью игры Эренфойхта (доказательство в одну сторону: если Консерватор имеет выигрышную стратегию, то модели элементарно эквивалентны). | ||
| + | ====Лекция 13 (12 декабря). ==== | ||
Выразимые (определимые отношения). Сохранение выразимых отношений при автоморфизмах. Доказательства невыразимости. | Выразимые (определимые отношения). Сохранение выразимых отношений при автоморфизмах. Доказательства невыразимости. | ||
| − | + | Cемантически полные теории. Критерий семантической полноты в терминах элементарной эквивалентности моделей. | |
| − | + | ||
| − | + | ||
| − | Cемантически полные теории. | + | |
| − | Критерий семантической полноты в терминах элементарной эквивалентности моделей. | + | |
Задача аксиоматизации данной интерпретации. | Задача аксиоматизации данной интерпретации. | ||
| Строка 656: | Строка 393: | ||
Аксиоматизация элементарной теории упорядоченного множества целых чисел (доказательство элементарной эквивалентности моделей с помощью игры Эренфойхта). | Аксиоматизация элементарной теории упорядоченного множества целых чисел (доказательство элементарной эквивалентности моделей с помощью игры Эренфойхта). | ||
| − | Аксиоматизация элементарной теории упорядоченного множества действительных чисел. Аксиоматизация элементарной теории поля комплексных чисел. Обе теоремы без доказательства. | + | Этого не было: Аксиоматизация элементарной теории упорядоченного множества действительных чисел. Аксиоматизация элементарной теории поля комплексных чисел. Обе теоремы без доказательства. |
| + | |||
| + | ==Планируемые лекции== | ||
== Семинары == | == Семинары == | ||
| Строка 662: | Строка 401: | ||
=== Листки с задачами для семинаров === | === Листки с задачами для семинаров === | ||
| − | [https://www.dropbox.com/s/ | + | [https://www.dropbox.com/s/anig4e3h195kela/listok1.pdf?dl=0 Листок 1. Вычислимые функции, разрешимые, полуразрешимые и перечислимые множества.] |
| − | [https://www.dropbox.com/s/ | + | [https://www.dropbox.com/s/taiin7z49pwonj7/listok2.synctex.gz?dl=0 Листок 2. Универсальные функции, неразрешимые и неперечислимые множества.] |
| − | [https://www.dropbox.com/s/ | + | [https://www.dropbox.com/s/lgp1mcy6y5axr12/listok3.pdf?dl=0 Листок 3. Главные универсальные функции, теоремы Клини и Успенского - Райса.] |
| − | [https://www.dropbox.com/s/ | + | [https://www.dropbox.com/s/txvyki1ktwhwfbl/listok4.pdf?dl=0 Листок 4. Машины Тьюринга] |
| − | [https://www.dropbox.com/s/ | + | [https://www.dropbox.com/s/2yshtxt9xqzreq1/listok5.pdf?dl=0 Листок 5. Ассоциативные исчисления и проблемы разрешения] |
| − | [https://www.dropbox.com/s/ | + | [https://www.dropbox.com/s/i7yjbwycn0ffxf4/listok6.pdf?dl=0 Листок 6. Язык логики высказываний и выводы из гипотез в исчислении высказываний] |
| − | [https://www.dropbox.com/s/ | + | [https://www.dropbox.com/s/iq3hd1rcqogpv83/listok7.pdf?dl=0 Листок 7. Выводы в исчислении высказываний и исчислении резолюций] |
| − | [https://www.dropbox.com/s/ | + | [https://www.dropbox.com/s/oahd5byijhr3xgn/listok8.pdf?dl=0 Листок 8. Запись утверждений и выражение отношений формулами первого порядка; выполнимость, общезначимость и равносильность, теории и семантическое следование] |
| − | [https://www.dropbox.com/s/ | + | [https://www.dropbox.com/s/63hhlqvyjhswi9c/listok9.pdf?dl=0 Листок 9. Исчисление резолюций для формул первого порядка, изоморфность, элементарная эквивалентность и игры Эренфойхта] |
| − | = | + | [https://www.dropbox.com/s/wltz3ragmawjeu7/listok10.pdf?dl=0 Листок 10. Доказательства невыразимости, теории и их модели, аксиоматизация] |
| − | ==== | + | === Семинары в группе 192 === |
| − | + | ||
| − | ====Семинар | + | ====Семинар 1 (5 сентября)==== |
| + | Вычислимые функции, разрешимые и перечислимые множества (листок 1 задачи 1-14). | ||
| − | + | ====Семинар 2 (12 сентября)==== | |
| − | + | Закончили первый листок и сделали задачи 1-13 из второго листка. | |
| − | + | ====Семинар 3 (19 сентября)==== | |
| + | Закончили второй листок. Из третьего листка сделали задачи 1, 3,4,5 | ||
| − | ====Семинар 4 ( | + | ====Семинар 4 (26 сентября)==== |
| − | + | Закончили задачей 13 из листка 3. | |
| − | ====Семинар 5 ( | + | ====Семинар 5 (3 октября)==== |
| + | Закончили листок 3 и листок 4. | ||
| − | Листок 5 (кроме | + | ====Семинар 6 (10 октября)==== |
| + | Листок 5 (кроме последних двух задач). | ||
| − | ====Семинар | + | ====Семинар 7 (17 октября)==== |
| + | Листок 6 | ||
| − | + | ====Семинар 8 (31 октября)==== | |
| + | Сделали задачи 1-2 листка 7. | ||
| − | + | Ссылка на доску | |
| − | + | https://jamboard.google.com/d/1FpXbITvIBWpXz3gYKzPAHmqTBwovF_AtH-sMTqrymC0/viewer?f=0 | |
| − | = | + | Ссылка на видеозапись: https://www.youtube.com/playlist?list=PLo3cgfsnO72ctaL2aza8xQ0ZA2S9SqW-c |
| − | + | ====Семинар 9 (7 ноября)==== | |
| − | ====Семинар | + | ====Семинар 10 (14 ноября)==== |
| − | + | ||
| − | ====Семинар | + | ====Семинар 11 (21 ноября)==== |
| − | + | ====Семинар 12 (28 ноября)==== | |
| − | + | ||
| − | + | Закончили листок 8 и сделали те задачи листка 9, которые не требуют знания непрочитанного материала. | |
| − | ====Семинар | + | ====Семинар 13 (5 декабря)==== |
| − | + | Закончили в середине задачи 5 листка 9 | |
| − | + | ||
| − | ====Семинар | + | ====Семинар 14 (12 декабря)==== |
| + | Закончили задачей 5а из листка 10 | ||
| − | ====Семинар | + | ====Семинар 15 (19 декабря)==== |
| − | + | Закончили листок 10. | |
| − | + | ||
| − | + | ||
==Конспекты лекций== | ==Конспекты лекций== | ||
| − | [https://www.dropbox.com/s/nhdnt5d88zk14qv/res-lect-revised.pdf?dl=0 Конспект лекций о методе резолюций] | + | [https://www.dropbox.com/s/nhdnt5d88zk14qv/res-lect-revised.pdf?dl=0 Конспект лекций о методе резолюций] [https://www.dropbox.com/s/8p4knh6h1njs1yo/res-lect-revised.tex?dl=0 Исходник TeX] |
==Консультации == | ==Консультации == | ||
| − | + | Консультации Н.К. Верещагина: по вторникам с 10 до 20, средам с 18 до 20, четвергам с 10 до 20 с помощью skype (vereshchagin) или телеграмм (@nikolay_vereshchagin) или Google Meet https://meet.google.com/noy-cait-jph | |
| − | + | ||
| − | + | ||
| − | + | Консультации И.Г. Райко: Очно или онлайн в соответствии с [[Участник:IRaiko#Расписание в сентябре – декабре 2020 года|таблицей]]. Для онлайн связи напишите в телеграм @ilya0x2dilya -- там поймём, как нам связаться. | |
| − | + | Консультации А.А. Оноприенко: четверг 14-20 в дискорде https://discord.gg/v5DbugV (если меня там нет, пишите в телеграм @ansidiana). | |
==Рекомендуемая литература == | ==Рекомендуемая литература == | ||
Текущая версия на 14:57, 1 февраля 2021
Содержание
- 1 Дискретная математика на 2-ом курсе ПМИ (пилотный поток)
- 1.1 Новости
- 1.2 Лектор
- 1.3 Семинары и семинаристы
- 1.4 Краткое описание
- 1.5 Отчётность по курсу и критерии оценки
- 1.6 Сдача домашних заданий
- 1.7 Сроки контрольных мероприятий
- 1.7.1 Первое домашнее задание: дедлайн для сдачи
- 1.7.2 Второе домашнее задание: дедлайн для сдачи
- 1.7.3 Третье домашнее задание: дедлайн для сдачи
- 1.7.4 Четвертое домашнее задание: дедлайн для сдачи
- 1.7.5 Пятое домашнее задание: дедлайн для сдачи
- 1.7.6 Шестое домашнее задание: дедлайн для сдачи
- 1.7.7 Коллоквиум
- 1.7.8 Экзамен
- 1.7.9 Пересдачи
- 1.8 Домашние задания
- 1.9 Оценки за домашние задания и тесты
- 1.10 Примерное содержание лекций
- 1.11 Прочитанные лекции
- 1.11.1 Лекция 1 (5 сентября).
- 1.11.2 Лекция 2 (12 сентября).
- 1.11.3 Лекция 3 (19 сентября).
- 1.11.4 Лекция 4 (26 сентября).
- 1.11.5 Лекция 5 (3 октября).
- 1.11.6 Лекция 6 (10 октября).
- 1.11.7 Лекция 7 (17 октября).
- 1.11.8 Лекция 8 (31 октября).
- 1.11.9 Лекция 9 (21 ноября).
- 1.11.10 Лекция 10 (28 ноября).
- 1.11.11 Лекция 11 (30 ноября).
- 1.11.12 Лекция 12 (5 декабря).
- 1.11.13 Лекция 13 (12 декабря).
- 1.12 Планируемые лекции
- 1.13 Семинары
- 1.13.1 Листки с задачами для семинаров
- 1.13.2 Семинары в группе 192
- 1.13.2.1 Семинар 1 (5 сентября)
- 1.13.2.2 Семинар 2 (12 сентября)
- 1.13.2.3 Семинар 3 (19 сентября)
- 1.13.2.4 Семинар 4 (26 сентября)
- 1.13.2.5 Семинар 5 (3 октября)
- 1.13.2.6 Семинар 6 (10 октября)
- 1.13.2.7 Семинар 7 (17 октября)
- 1.13.2.8 Семинар 8 (31 октября)
- 1.13.2.9 Семинар 9 (7 ноября)
- 1.13.2.10 Семинар 10 (14 ноября)
- 1.13.2.11 Семинар 11 (21 ноября)
- 1.13.2.12 Семинар 12 (28 ноября)
- 1.13.2.13 Семинар 13 (5 декабря)
- 1.13.2.14 Семинар 14 (12 декабря)
- 1.13.2.15 Семинар 15 (19 декабря)
- 1.14 Конспекты лекций
- 1.15 Консультации
- 1.16 Рекомендуемая литература
Дискретная математика на 2-ом курсе ПМИ (пилотный поток)
Лекции проходят по субботам в 13-14:20 онлайн на платформе Zoom по ссылке https://zoom.us/j/99056983180?pwd=MkxkSjRWYm53b21oSXFOSVloS1dtZz09. При наличии технических проблем в Zoom лекции переносятся в Google meet: meet.google.com/xoq-qtjo-pny
Новости
1 февраля
Пересдача экзамена комиссии понедельник, 1 февраля, в 15:00: https://zoom.us/j/92864977568
23 января
Пересдача 25 января в 15:00 по ссылке: https://zoom.us/j/92864977568
16 января
Пересдачи назначены на 18 и 25 января в 15:00. Пересдача комиссии - 1 февраля в 15:00.
Итоговые ведомости
БПМИ 191, Таблица со всеми оценками
БПМИ 192, Таблица со всеми оценками
БПМИ 194, Таблица со всеми оценками
29 декабря
Выложены решения экзаменационных задач
Выложены оценки и критерии выставления оценок экзаменационных работ
Апелляция по поводу оценок за экзамен состоится 30 декабря в 18:00 в дискорде https://discord.gg/v5DbugV.
27 декабря
Инструкция к экзамену (письменному) 28 декабря.
Начало экзамена в 11 часов на платформе Zoom https://zoom.us/j/99884492481. Вариант состоит из 5 задач, которые нужно решить за полтора часа.
Экзамен проходит с прокторингом. Студенты загружают задание по ссылке https://www.dropbox.com/s/yroi37a7xz2mqzz/28.12.pdf?dl=0, решают на бумаге, в конце экзамена делают фотографии/сканы решений, сшивают в один PDF файл и загружают по следующей ссылке https://www.dropbox.com/request/f94hby1pjt00x5is0beh. Черновики отсылать не надо. Крайний срок посылки - 15 мин после конца экзамена.
Экзамен длится 90 минут. Во время экзамена студенты должны включить камеры. Во время экзамена разрешено смотреть на любые материалы, загруженные на компьютер до начала экзамена, писать на листах бумаги, а также смотреть на любые бумажные материалы на столе. Студенты могут пользоваться мышью и клавиатурой только для того, чтобы перелистывать загруженные материалы и условия задач. Если во время экзамена у студента возникнет вопрос по условию задачи, он может устно задать его и преподаватель даст на него ответ.
Если у студента случился один или два обрыва связи продолжительностью менее пяти минут, он может продолжить написание экзамена (дополнительное время при этом не предоставляется). Если случился обрыв связи продолжительностью дольше 5 минут или более двух пятиминутных, то считается, что студент пропустил экзамен. В этом случае ему будет предложено без штрафов сдать экзамен устно в течение недели с момента данного экзамена.
28 ноября
Выложено пятое домашнее задание.
25 ноября
В понедельник 30 ноября в 16:20-17:40 состоится дополнительная лекция взамен одной из двух пропущенных лекций. Подключиться к конференции Zoom: https://zoom.us/j/96230416179?pwd=UFNIbVkrRk5IWGRGcmxGODVXbHNHQT09
19 ноября
Лектор болеет ковидом и не может принимать ДЗ в 192 группе. Сдавайте, пожалуйста, ассистенту.
31 октября
Выложено четвертое домашнее задание.
8 октября
Выложено третье домашнее задание.
21 сентября
Выложено второе домашнее задание.
1 сентября
Первая лекция будет 5 сентября.
Лектор
Верещагин Николай Константинович nikolay.vereshchagin@gmail.com
Семинары и семинаристы
191 Райко Илья Глебович mylntsa.ilya.63@gmail.com по понедельникам 9:30 - 10:50 (учебный ассистент Игорь Тараканов <79851126754@ya.ru>)
192 Верещагин Николай Константинович (e-mail: nikolay.vereshchagin@gmail.com, skype: vereshchagin, телеграмм @nikolay_vereshchagin) по субботам 14:40 - 16 онлайн на платформе Zoom по ссылке https://zoom.us/j/99063463658?pwd=bHdjZEtxNmtJTDBFcnVYUU8zSkkyUT09 (учебный ассистент Шабалина Анастасия Владимировна shabalina.nasty@gmail.com)
194 Оноприенко Анастасия Александровна ansidiana@yandex.ru по понедельникам 11:10 - 12:30 (учебный ассистент Амашукели Игорь Михайлович imamashukeli@edu.hse.ru). Для быстрой связи лучше писать в телеграм @ansidiana.
Краткое описание
Курс состоит из двух частей. В первом модуле будет общая теория вычислимости, во втором модуле будет изучаться математическая логика: формулы логики высказываний и логики предикатов, определение истинности, выразимость средствами логики предикатов, исчисление резолюций.
Отчётность по курсу и критерии оценки
Тесты
В конце каждой лекции будет предлагаться десятиминутный тест с простыми задачами. Целью тестов является контроль за тем, чтобы студенты внимательно слушали лекцию. К написанию теста допускаются только присутствовавшие на лекции (разрешается десятиминутное опоздание к началу лекции). За каждый тест выставляется оценка, равная доле правильных ответов, умноженной на 10. Общая оценка за тесты равняется среднему арифметическому оценок за все тесты.
6 домашних заданий
В течение двух модулей студентам будет дано 6 домашних заданий. Оценка за каждое домашнее задание равна доле решенных задач, умноженной на 10. Общая оценка за домашние задания равна среднему арифметическому оценок за решение каждого из заданий. На решение каждого ДЗ дается 14 дней, решение ДЗ нужно сдавать семинаристу или ассистенту устно (очно или онлайн) или письменно. Какой из двух видов сдачи ДЗ разрешен, решается семинаристом каждой группы. Сдача домашних заданий после их срока невозможна.
В случае письменной сдачи ДЗ, оно в будет проверено в течение 10 дней после дедлайна и должно быть защищено студентом в течение 3 недель после дедлайна. Для защиты студент должен прийти на консультацию и убедить семинариста или ассистента, что он понимает, что у него написано, и тем самым работа не списана. В случае устной сдачи защиты не требуется.
Коллоквиум и письменный экзамен
Коллоквиум (устный) и экзамен (письменный) проводятся в конце второго модуля и оцениваются по десятибалльной системе.
Итоговая оценка
Оценки за коллоквиум и экзамен входят в итоговую оценку с коэффициентами 0.3, а оценки за домашние задания и тесты - с коэффициентом 0.2.
Те, кто не смог прийти на коллоквиум по болезни, могут его сдать отдельно в день пересдачи (один раз). Это же относится и к тем, кто не смог прийти на экзамен. Те, кто после всех пересдач получил итоговую оценку менее 4 баллов, сдают устный экзамен комиссии, в этом случае все полученные ранее оценки аннулируются и оценка, полученная на экзамене, является окончательной. На экзамене комиссии будет выдан один билет из билетов коллоквиума (содержащий два теоретических вопроса и задачу), и при необходимости будет дана еще одна дополнительная задача.
Правила округления
В оценках за домашние задания промежуточные величины не округляются. Результат вычисляется точно и округляется только в момент выставления итоговой оценки. Используется арифметическое округление (то есть, 6.5 округляется до 7, а 6.49 - до 6).
Сдача домашних заданий
Группа 191: сдача домашних заданий проходит в устной форме ассистенту Игорю Тараканову (79851126754@ya.ru, тг @SetSplin) или семинаристу по четвергам (подробнее см. в разделе про консультации).
Группа 192: Сдача домашних заданий семинаристу Н.К. Верещагину проходит только в устной форме по вторникам с 10 до 20, средам с 18 до 20, четвергам с 10 до 20 с помощью Google Meet https://meet.google.com/noy-cait-jph. Сдача домашних заданий ассистенту А. Шабалиной также проходит только в устной форме в понедельник с 14:30 до 17:00, в среду с 10:00 до 15:00, в четверг с 10:00 до 12:00, в пятницу с 10:00 до 17:00, в субботу с 10:00 до 14:00, cвязаться можно через телеграм (@nastyash08) или почту (shabalina.nasty@gmail.com).
Группа 194: сдача домашних заданий проходит в устной форме, задачи принимает преимущественно ассистент Игорь Амашукели (почта imamashukeli@edu.hse.ru, телеграм @iamashukeli) в зуме. Можно также сдавать семинаристке в дискорде по четвергам после 14:00 либо в другой день по предварительной договорённости.
Сроки контрольных мероприятий
Первое домашнее задание: дедлайн для сдачи
группа 191: 21 сентября
группа 192: 19 сентября
группа 194: 21 сентября
Второе домашнее задание: дедлайн для сдачи
группа 191: 7 откября
группа 192: 5 октября
группа 194: 5 октября
Третье домашнее задание: дедлайн для сдачи
группа 191: 26 октября
группа 192: 22 октября
группа 194: 23 октября
Четвертое домашнее задание: дедлайн для сдачи
группа 191: 23 ноября
группа 192: 24 ноября
группа 194: 22 ноября
Пятое домашнее задание: дедлайн для сдачи
группа 191:
группа 192: 12 декабря
группа 194: 13 декабря
Шестое домашнее задание: дедлайн для сдачи
группа 191:
группа 192: 26 декабря
группа 194: 26 декабря
Коллоквиум
Коллоквиум пройдёт 14, 15 и 17 декабря в промежуток времени 15:00-19:00.
Коллоквиум проводится на платформе Зум, каждому будет назначено время, в которое нужно явиться. В случае неявки без уважительной причины (причина уважительная, если таковой её считает учебный офис) студент получает 0 баллов.
В начале ответа Вы получите билет, в котором будет три вопроса. Первый вопрос: определение или формулировка теоремы (без доказательства). Во втором вопросе надо будет решить простую задачу на понимание определения. Третий вопрос: доказательство какой-нибудь теоремы. Отвечать надо будет без подготовки в режиме реального времени: рассуждать и вспоминать нужно будет устно в присутствии экзаменатора. При доказательстве теоремы можно расшарить свою запись или конспект и аннотировать их при необходимости.
Оценка за коллоквиум формируется следующим образом. Полный ответ на каждый из первых двух вопросов оценивается в 3 балла, а полный ответ на третий вопрос в 4 балла (всего 10 баллов). По правилам НИУ ВШЭ при обнаружении факта помощи извне за коллоквиум ставится 0 баллов.
Распределение студентов по дням и времени сдачи. Альтернативная ссылка на Dropbox
Вопросы к коллоквиуму. Исходник TeX
Экзамен
Начало экзамена в 11 часов 28 декабря на платформе Zoom https://zoom.us/j/99884492481. Вариант состоит из 5 задач, которые нужно решить за полтора часа.
Экзамен письменный. Экзамен проходит с прокторингом. Студенты загружают задание по ссылке https://www.dropbox.com/s/yroi37a7xz2mqzz/28.12.pdf?dl=0, решают на бумаге, в конце экзамена делают фотографии/сканы решений, сшивают в один PDF файл и загружают по следующей ссылке https://www.dropbox.com/request/f94hby1pjt00x5is0beh. Черновики отсылать не надо. Крайний срок посылки - 15 мин после конца экзамена.
Экзамен длится 90 минут. Во время экзамена студенты должны включить камеры. Во время экзамена разрешено смотреть на любые материалы, загруженные на компьютер до начала экзамена, писать на листах бумаги, а также смотреть на любые бумажные материалы на столе. Студенты могут пользоваться мышью и клавиатурой только для того, чтобы перелистывать загруженные материалы и условия задач. Если во время экзамена у студента возникнет вопрос по условию задачи, он может устно задать его и преподаватель даст на него ответ.
Если у студента случился один или два обрыва связи продолжительностью менее пяти минут, он может продолжить написание экзамена (дополнительное время при этом не предоставляется). Если случился обрыв связи продолжительностью дольше 5 минут или более двух пятиминутных, то считается, что студент пропустил экзамен. В этом случае ему будет предложено без штрафов сдать экзамен устно в течение недели с момента данного экзамена.
Ссылка на оценки за экзамен https://docs.google.com/spreadsheets/d/13j4KY-n3ZqkDRczudnL_w92v8AJybxHEVsGbo6eJ1EU/edit#gid=0
Апелляция по поводу оценок за экзамен состоится 30 декабря в 18:00 в дискорде https://discord.gg/v5DbugV.
Пересдачи
Пересдачи состоятся 18 и 25 января в 15:00. Подключение по ссылке: https://zoom.us/j/92864977568
Комиссия назначена на 1 февраля 15:00 https://zoom.us/j/92864977568 Сдача экзамена комиссии происходит устно. Все предыдущие оценки аннулируются. На экзамене будет выдан один билет из билетов коллоквиума (содержащий два теоретических вопроса и задачу), и при необходимости будет дана еще одна дополнительная задача.
Домашние задания
Оценки за домашние задания и тесты
Оценки за Tест 1
Оценка за Тест 2
Оценки за Тест 3
Оценки за Тест 4
Оценки за Тест 5
Оценки за Тест 6
Оценки за Тест 7
Оценки за Тест 8
Оценки за Тест 9
Оценки за Тест 10
Оценки за Тест 12
Примерное содержание лекций
- Вычислимые функции. Разрешимые и перечислимые множества.
- Универсальные функции. Перечислимые неразрешимые множества. Неразрешимость проблемы остановки. Неотделимые перечислимые множества.
- Теорема Клини о неподвижной точки. Теорема Райса-Успенского.
- Машины Тьюринга. Тезис Чёрча-Тьюринга.
- Алгоритмические проблемы. Примеры неразрешимых алгоритмических проблем.
- Пропозициональные формулы.
- Исчисление резолюций для пропозициональных формул.
- Языки первого порядка и их модели. Изоморфные и элементарно эквивалентные модели. Доказательства элементарной эквивалентности с помощью игр Эренфойхта
- Исчисление резолюций для формул первого порядка.
- Выразимые в данной модели отношения. Метод автоморфизмов доказательства невыразимости.
- Логическое следование и аксиоматические теории.
Прочитанные лекции
Лекция 1 (5 сентября).
Общее неформальное понятие алгоритма и конструктивного объекта. Исходное данное и результат работы алгоритма. Пошаговая работа алгоритма.
Определение вычислимой частичной функции из N в N. Счетность семейства частичных вычислимых функций, и существование невычислимых функций.
Разрешимые подмножества N. Перечислимые подножества N. Счетность семейства перечислимых множеств, и существование неперечислимых. Эквивалентные определения перечислимости (полуразрешимость, область определения вычислимой функции, множество значений вычислимой функции, проекции разрешимых множеств - без подробного доказательства). Теорема Поста. Теорема о графике.
Лекция 2 (12 сентября).
Универсальные вычислимые функции (нумерации) для семейства частичных вычислимых функций натурального аргумента. Несуществование универсальной вычислимой функции для семейства тотальных вычислимых функций натурального аргумента (диагональное рассуждение).
Вычислимая функция, не имеющая тотального вычислимого продолжения. Перечислимое неразрешимое множество. Неразрешимость проблемы применимости.
Перечислимые неотделимые множества.
Лекция 3 (19 сентября).
Перечислимые неотделимые множества.
Главные универсальные функции. Теорема Райса-Успенского. Теорема Клини о неподвижной точке.
Лекция 4 (26 сентября).
Еще раз о теореме Клини.
Сводимости: m-сводимость и Тьюрингова сводимость. Их свойства. Полные перечислимые множества. Теорема Мучника - Фридберга (без доказательства).
Односторонние и двусторонние ассоциативные исчисления. Полугруппы, заданные порождающими и соотношениями.
Лекция 5 (3 октября).
Определение машин Тьюринга и вычислимых на машинах Тьюринга функций. Тезис Чёрча-Тьюринга. Неразрешимость проблемы остановки машины Тьюринга.
Неразрешимость проблемы достижимости в односторонних ассоциативных исчислениях (с доказательством).
Лекция 6 (10 октября).
Неразрешимость проблемы достижимости в двусторонних ассоциативных исчислениях (с доказательством). Неразрешимость проблемы равенства слов в конечно определенных полугруппах.
Язык логики высказываний, формулы логики высказываний, связь со схемами. Выбор набора связок. Тавтологии, выполнимые формулы. Связь между тавтологиями и выполнимыми формулами. КНФ и ДНФ (напоминание). Эквивалентные формулы.
Лекция 7 (17 октября).
Основные эквивалентности.
Проблема проверки тавтологичности (выполнимости), ее NP полнота (без точных определений).
Исчисление высказываний, понятие вывода. Теорема корректности исчисления высказываний. Вывод из гипотез. Лемма о дедукции.
Лекция 8 (31 октября).
Полезные производные правила. Теорема полноты ИВ и ее доказательство.
Ссылка на видеозапись: https://www.youtube.com/playlist?list=PLo3cgfsnO72ctaL2aza8xQ0ZA2S9SqW-c Ссылка на доску: https://jamboard.google.com/d/1HogjiZP2zrvEOTqOMYdRE10c4HDoQi-kd3p-oK6P-aY/viewer?f=0
Лекция 9 (21 ноября).
Исчисление резолюций: дизъюнкты, правило резолюции, опровержение КНФ в исчислении резолюций, доказательство корректности. Теорема полноты (любое, даже бесконечное, непротиворечивое множество дизъюнктов совместно).
Опровержение пропозициональных формул общего вида в исчислении резолюций (не было).
Определение формулы первого порядка в данной сигнатуре. Запись утверждений формулами первого порядка. Модели (интепретации) сигнатуры. Нормальные модели.
Лекция 10 (28 ноября).
Общезначимые и выполнимые формулы. Равносильные формулы. Теории и их модели. Семантическое следование.
Теорема Черча об алгоритмической неразрешимости отношения семантического следования, общезначимости и равносильности формул (с доказательством).
Перечислимость множества общезначимых формул (пока без доказательства). Дизъюнкты, универсальные дизъюнкты. Исчисление резолюций для доказательства несовместности множеств универсальных дизъюнктов. Теорема корректности ИР.
Лекция 11 (30 ноября).
Теорема полноты ИР (для множеств универсальных дизъюнктов). Исчисление резолюций для теорий, состоящих из формул общего вида (приведение к предваренной нормальной форме и сколемизация). Доказательства общезначимости с помощью ИР. Перечислимость множества общезначимых формул. Выводимость формулы в теории с помощью ИР. Эквивалентность выводимости и семантического следования.
Теорема компактности.
Гомоморфизмы, эпиморфизмы (сюръективные гомоморфизмы), изоморфизмы. Изоморфные интерпретации. Теорема о сохранении истинности при эпиморфизме (с доказательством). Элементарно эквивалентные модели, элементарная эквивалентность изоморфных моделей.
Лекция 12 (5 декабря).
Теорема о сохранении истинности при эпиморфизме (с доказательством). Элементарно эквивалентные модели, элементарная эквивалентность изоморфных моделей.
Аксиомы равенства. Семантическое следование для нормальных моделей и теорема полноты ИР для нормальных моделей (если теория не имеет нормальных моделей, то из её аксиом и аксиом равенства можно вывести пустой дизъюнкт).
Игры Эренфойхта. Примеры: упорядоченные множества целых и рациональных чисел, рациональных и действительных чисел. Доказательство элементарной эквивалентности с помощью игры Эренфойхта (доказательство в одну сторону: если Консерватор имеет выигрышную стратегию, то модели элементарно эквивалентны).
Лекция 13 (12 декабря).
Выразимые (определимые отношения). Сохранение выразимых отношений при автоморфизмах. Доказательства невыразимости.
Cемантически полные теории. Критерий семантической полноты в терминах элементарной эквивалентности моделей.
Задача аксиоматизации данной интерпретации.
Аксиоматизация элементарной теории упорядоченного множества рациональных чисел (доказательство элементарной эквивалентности моделей с помощью игры Эренфойхта).
Аксиоматизация элементарной теории упорядоченного множества целых чисел (доказательство элементарной эквивалентности моделей с помощью игры Эренфойхта).
Этого не было: Аксиоматизация элементарной теории упорядоченного множества действительных чисел. Аксиоматизация элементарной теории поля комплексных чисел. Обе теоремы без доказательства.
Планируемые лекции
Семинары
Листки с задачами для семинаров
Листок 1. Вычислимые функции, разрешимые, полуразрешимые и перечислимые множества.
Листок 2. Универсальные функции, неразрешимые и неперечислимые множества.
Листок 3. Главные универсальные функции, теоремы Клини и Успенского - Райса.
Листок 5. Ассоциативные исчисления и проблемы разрешения
Листок 6. Язык логики высказываний и выводы из гипотез в исчислении высказываний
Листок 7. Выводы в исчислении высказываний и исчислении резолюций
Листок 10. Доказательства невыразимости, теории и их модели, аксиоматизация
Семинары в группе 192
Семинар 1 (5 сентября)
Вычислимые функции, разрешимые и перечислимые множества (листок 1 задачи 1-14).
Семинар 2 (12 сентября)
Закончили первый листок и сделали задачи 1-13 из второго листка.
Семинар 3 (19 сентября)
Закончили второй листок. Из третьего листка сделали задачи 1, 3,4,5
Семинар 4 (26 сентября)
Закончили задачей 13 из листка 3.
Семинар 5 (3 октября)
Закончили листок 3 и листок 4.
Семинар 6 (10 октября)
Листок 5 (кроме последних двух задач).
Семинар 7 (17 октября)
Листок 6
Семинар 8 (31 октября)
Сделали задачи 1-2 листка 7.
Ссылка на доску https://jamboard.google.com/d/1FpXbITvIBWpXz3gYKzPAHmqTBwovF_AtH-sMTqrymC0/viewer?f=0
Ссылка на видеозапись: https://www.youtube.com/playlist?list=PLo3cgfsnO72ctaL2aza8xQ0ZA2S9SqW-c
Семинар 9 (7 ноября)
Семинар 10 (14 ноября)
Семинар 11 (21 ноября)
Семинар 12 (28 ноября)
Закончили листок 8 и сделали те задачи листка 9, которые не требуют знания непрочитанного материала.
Семинар 13 (5 декабря)
Закончили в середине задачи 5 листка 9
Семинар 14 (12 декабря)
Закончили задачей 5а из листка 10
Семинар 15 (19 декабря)
Закончили листок 10.
Конспекты лекций
Конспект лекций о методе резолюций Исходник TeX
Консультации
Консультации Н.К. Верещагина: по вторникам с 10 до 20, средам с 18 до 20, четвергам с 10 до 20 с помощью skype (vereshchagin) или телеграмм (@nikolay_vereshchagin) или Google Meet https://meet.google.com/noy-cait-jph
Консультации И.Г. Райко: Очно или онлайн в соответствии с таблицей. Для онлайн связи напишите в телеграм @ilya0x2dilya -- там поймём, как нам связаться.
Консультации А.А. Оноприенко: четверг 14-20 в дискорде https://discord.gg/v5DbugV (если меня там нет, пишите в телеграм @ansidiana).
Рекомендуемая литература
1. Н.К.Верещагин, А. Шень. Вычислимые функции. М.:МЦНМО, 2008.
2. Н.К.Верещагин, А. Шень. Языки и исчисления. М.:МЦНМО, 2012. (Для курса будут наиболее важны главы 1, 3 и 4. Глава 1 содержит материал, который практически полностью входил в программу курса "Дискретная математика -1". Материал главы 4 в курсе будет затронут очень незначительно.)
3. Ч.Чень, Р.Ли. Математическая логика и автоматическое доказательство теорем. М.: Наука, 1983. (Для курса важен раздел про метод резолюций в главе 5.)
4. Черновик учебника "Лекции по дискретной математике" М.Вялый, В. Подольский, А. Рубцов, Д. Шварц, А Шень Главы 14-16 посвящены вычислимости.
