Wiki - Факультет компьютерных наук - Вклад [ru]

Математическая логика

2021-10-10T13:19:28Z

Adlyamzin: Изменен срок ДЗ-2 для группы 2

== О курсе ==

Курс для студентов 2 курса в 1-2 модулях.

'''Лектор:''' [https://www.hse.ru/org/persons/104695093 Дашков Евгений Владимирович]

'''Семинаристы:'''
{| class="wikitable"
|-
! Группа !! Преподаватель !! Учебный ассистент || classroom || Чат в телеграм || Консультации
|-
| 1 || [https://www.hse.ru/staff/ansidiana Оноприенко Анастасия Александровна] [https://t.me/ansidiana Telegram] || Василевская Юлия [https://t.me/vslvskyy Telegram] || g6m5meu || https://t.me/joinchat/ZeOwa21ph4s4N2Q6 || онлайн, по договорённости в Telegram
|-
| 2 || Дашков Евгений Владимирович [https://t.me/edashkov Telegram] || Лямзин Алексей [https://t.me/almondflower Telegram] || x6nty3k || https://t.me/joinchat/SpWx9TdiD1E1MzVi || онлайн, по договорённости в Telegram
|-
| 3 || [https://www.hse.ru/staff/ansidiana Оноприенко Анастасия Александровна] [https://t.me/ansidiana Telegram] || Березовский Валерий || eijvv6i || https://t.me/joinchat/ZeOwa21ph4s4N2Q6 || онлайн, по договорённости в Telegram
|-
| 4 || [https://www.hse.ru/org/persons/218355200 Запрягаев Александр Александрович] [https://t.me/azapryagaev Telegram] || Шитов Александр [https://t.me/AtgshkaSan Telegram] || 3zbutmx || https://t.me/joinchat/OEXzV66uIoEwYjQy || онлайн, по договорённости в Telegram
|}

=== Полезные ссылки ===

Телеграм-чат курса: https://t.me/joinchat/M0dUGBBjmuJAEs3JmWbU2A

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

=== Лекции ===

[https://www.youtube.com/playlist?list=PLEwK9wdS5g0rCmFF5jX96XItpo7M7lR99 Лекции и семинары Е. Дашкова (записи текущего года)]

[https://drive.google.com/file/d/13QUtHNIkxE402as8tsJgCwewcZag78HV/view?usp=sharing Конспект по вычислимости]

=== Семинары ===
==== Листки с задачами для семинаров ====
* [https://drive.google.com/file/d/1zzgaHzo5gbRY2WOzVg33dXyoMWj6xzTD/view?usp=sharing Листок 1]

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

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

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

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

=== Домашние задания ===
{| class="wikitable"
|-
! Задание !! colspan="4" | Срок сдачи в группе
|-
| || 1 || 2 || 3 || 4
|-
| [https://drive.google.com/file/d/1tFxzOApeglNB3rwDdsH93_geX11_WQMb/view?usp=sharing ДЗ 1] || 24.09 || 24.09 || 24.09 || 24.09
|-
| [https://drive.google.com/file/d/199sk-E-y_Y5V8Bdrtmm3EHT4DLt1TB7Z/view?usp=sharing ДЗ 2] || 08.10 || 10.10 || 08.10 || 08.10
|}

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

=== Коллоквиум ===

=== Экзамен ===

== Оценки и аттестация ==

В течение семестра проводится устный коллоквиум (КОЛ), выдается и проверяется письменное домашнее задание (ДЗ).

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

Оценка КОЛ выставляется по десятибалльной системе без округления (т.е. с максимальной доступной используемым вычислительным
средствам точностью). Оценка ДЗ выставляется в долях единицы также без округления, причем она может превосходить единицу засчет
"бонусных баллов".

По курсу проводится экзамен, оцениваемый по десятибалльной системе оценкой ЭКЗ. Результирующая оценка Р по дисциплине вычисляется по формуле

Р = ОКРУГЛ ( min (10, 0.35 * ЭКЗ + 0.35 * КОЛ + 3 * ДЗ) ),

причем применяются обычные правила округления, но полуцелые числа округляются вверх

== Текущие оценки ==

* [https://docs.google.com/spreadsheets/d/1-_-ez6PqiszuYpDarfJQBJm3zXevvNCDkc59wWVC6po Оценки за ДЗ]

== Прочие ресурсы ==

* [https://t.me/joinchat/TSVJDOHaWwuZZtTY Группа для обсуждения всех вопросов по курсу.]

* [https://drive.google.com/drive/folders/10pGBoYJ8B544pL0WZlq3hWc9cxwGaAg-?usp=sharing Директория с материалами курса]

* [https://www.youtube.com/playlist?list=PL1Uob8iPTHGRZB9F2yjqXhGp75g1ZJFk- Видео лекций и некоторых семинаров 2020 г.]

* [http://wiki.cs.hse.ru/DM2-base2020/2021#.D0.9A.D0.BE.D0.BD.D1.81.D0.BF.D0.B5.D0.BA.D1.82.D1.8B_.D1.81.D0.B5.D0.BC.D0.B8.D0.BD.D0.B0.D1.80.D0.BE.D0.B2 Конспекты семинаров Оноприенко А.А. за 2020-2021 учебный год]

== Основная литература ==

1. Н.К. Верещагин, А. Шень. [https://www.mccme.ru/free-books/shen/shen-logic-part3-5ed.pdf Вычислимые функции]. М.:МЦНМО, 2017.

2. Н.К. Верещагин, А. Шень. [https://www.mccme.ru/free-books/shen/shen-logic-part2-5ed.pdf Языки и исчисления]. М.:МЦНМО, 2017.

Математическая логика

2021-09-07T15:23:49Z

Adlyamzin: /* О курсе */

Математическая логика

2021-09-07T15:21:22Z

Adlyamzin: /* О курсе */

DM2-base2020/2021

2020-10-27T13:49:12Z

Adlyamzin: дедлайн ДЗ3 дя БПМИ196

= Дискретная математика на 2-ом курсе ПМИ (основной поток)=

Лекции транслируются по субботам в 18:10 -- 19:30.

==Новости==

No news is good news.

==Лектор==

Евгений Владимирович Дашков. Почта: edashkov@gmail.com; ТГ: @edashkov; vk.com/evgeny.v.dashkov

==Семинаристы и ассистенты==

193 группа: Сысоева Любовь Николаевна, почта: lsysoeva@hse.ru, телеграмм: @lsysoeva. Ассистент: Залялов Александр

195 группа: Оноприенко Анастасия Александровна, почта ansidiana@yandex.ru. Для быстрой связи лучше писать в телеграм @ansidiana. Ассистент - Косакин Даниил, телеграм @nieto95.

196 группа: Евгений Дашков; ассистент – Лямзин Алексей, почта: adlyamzin@edu.hse.ru, телеграмм: @almondflower

197 группа: [https://www.hse.ru/org/persons/305069360 Антон Гнатенко], почта: [mailto:agnatenko@hse.ru agnatenko@hse.ru], телеграм: [https://t.me/antongnatenko @antongnatenko]. Ассистент: Мануйленко Никита, почта: nsmanuylenko@edu.hse.ru, телеграм: @WheelDeal

198 группа: Райко Илья Глебович (mailto://mylntsa.ilya.63@gmail.com).

199 группа: Сысоева Любовь Николаевна, почта lsysoeva@hse.ru, телеграмм: @lsysoeva.

1910 группа: Райко Илья Глебович (mailto://mylntsa.ilya.63@gmail.com), ассистент: Коваленко Влад (телеграмм: @ykeababy)

==Краткое описание==

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

==Отчётность по курсу и критерии оценки==

6 домашних заданий, коллоквиум и экзамен.

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

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

Коллоквиум (устный) и экзамен (письменный) оцениваются по десятибалльной системе. На коллоквиуме не разрешается пользоваться никакими записями. На экзамене можно пользоваться любыми бумажными источниками и нельзя никакими электронными. Коллоквиум состоит из двух теоретических вопросов (один по теории вычислимости, другой по логике) и одной задачи, которые оцениваются в 3, 3 и 4 баллов соответственно. Эти задачи берутся из заранее опубликованного списка задач (с точностью до выбора конкретных чисел), подобных тем, что были в домашних заданиях. Экзамен состоит из 8 задач и тоже оценивается по десятибалльной системе. Задачи нужно решить за две пары.

Оценки за коллоквиум и экзамен входят в итоговую оценку с коэффициентами 0.35, а оценка за домашние задания - с коэффициентом 0.3. Округление делается один раз --- при вычислении итоговой оценки. Применяются стандартные правила, но полуцелые числа округляются вверх.

Те, кто не смог прийти на коллоквиум по болезни, могут его сдать отдельно в день пересдачи (один раз). Это же относится и к тем, кто не смог прийти на экзамен или получил на нем менее 4 баллов. Те, кто после всех пересдач получил итоговую оценку менее 4 баллов, сдают устный экзамен комиссии, в этом случае все полученные ранее оценки аннулируются и оценка, полученная на экзамене, является окончательной.

==Сроки контрольных мероприятий==

===Сдача домашних заданий===

====Первое домашнее задание: срок сдачи====

группа 193: 25 сентября 13:00

группа 195: 21 сентября. (Сдавать [https://classroom.google.com/c/MTY0OTYzOTg2Nzk5?cjc=njl6gsd сюда])

группа 196: 25 сентября (защита до 16 октября).

группа 197: 25 сентября, 23:59 (Сдавать [https://docs.google.com/forms/d/e/1FAIpQLSdkkKR8H1GaF4sU36ZICf8ypRicgtfgdL8mWrGFPZJoyz87sw/viewform?usp=sf_link сюда]).

группа 199: 25 сентября 14:40

====Второе домашнее задание: срок сдачи====
группа 193: 9 октября до начала семинара.

группа 195: 9 октября. (Сдавать [https://classroom.google.com/c/MTY0OTYzOTg2Nzk5?cjc=njl6gsd сюда])

группа 196: 9 октября.

группа 197: 9 октября, 23:59 (Сдавать [https://docs.google.com/forms/d/e/1FAIpQLSdkkKR8H1GaF4sU36ZICf8ypRicgtfgdL8mWrGFPZJoyz87sw/viewform?usp=sf_link сюда]).

группа 198: 7 октября.

группа 199: 9 октября до начала семинара.

группа 1910: 7 октября.

====Третье домашнее задание: срок сдачи====
группа 193: 23:59 31го октября

группа 195: 31 октября. (Сдавать [https://classroom.google.com/c/MTY0OTYzOTg2Nzk5?cjc=njl6gsd сюда])

группа 196: 31 октября 16:20

группа 197: 2 ноября, 23:59 (Сдавать [https://docs.google.com/forms/d/e/1FAIpQLSdkkKR8H1GaF4sU36ZICf8ypRicgtfgdL8mWrGFPZJoyz87sw/viewform?usp=sf_link сюда]).

группа 198: 31 октября.

группа 199: 23:59 31го октября

группа 1910: 31 октября.

===Коллоквиум===

Коллоквиум пройдет в с

===Экзамен===

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

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

[https://drive.google.com/file/d/1fQbW9StntA6nbVv9Nreye0xqZMAtxK5Y/view?usp=sharing Домашнее задание № 1]

[https://drive.google.com/file/d/1TwCjnbwY9j2bhiB3MiYAW3s-XOtmDCJR/view?usp=sharing Домашнее задание № 2]

[https://drive.google.com/file/d/1L-iLQ_gmon36407q3b_bkVjHcmcid4Dm/view?usp=sharing Домашнее задание № 3]

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

[https://docs.google.com/spreadsheets/d/1gU2KPI5Rtxp3_c2OA7wbQG1YNxiaewkuTznY2wrEdi0/edit?usp=sharing Таблица] текущих результатов.

==Прочитанные лекции==

====Лекция 1 (5 сентября).====

Неформальное понятие и свойства алгоритма; вычислимые функции, перечислимые и разрешимые множества; теорема Поста; разрешимость и перечислимость под действием операций над множествами; теорема о графике; полуразрешимость; равносильные определения перечислимого множества.

[https://youtu.be/_xAoOF9_D6M Запись лекции].

====Лекция 2 (12 сентября).====

Универсальная вычислимая функция (у.в.ф.) и универсальный алгоритм, T-предикаты, невозможность универсальной вычислимой тотальной функции, проблемы самоприменимости и остановки, пример перечислимого неразрешимого множества, диагональ у.в.ф., вычислимые функции без вычислимого тотального продолжения, теорема о перечислимых рекурсивно неотделимых множествах, вычислимое кодирование пар, главная универсальная вычислимая функция.

[https://youtu.be/qu9DTOwE_sY Запись лекции].

====Лекция 3 (19 сентября).====

m-Сводимость и ее свойства; множество, полное в классе перечислимых; примеры применения; "программы" для нигде не определенной функции; пример неглавной у.в.ф.; теорема Клини о неподвижной точке.

[https://youtu.be/_MS9YL7hbtM Запись лекции].

====Лекция 4 (26 сентября).====

Теорема о рекурсии как следствие теоремы Клини; совместная рекурсия; решение "уравнений" на вычислимые функции и их систем; теорема Успенского-Райса и ее вывод из теоремы Клини; доказательство той же теоремы на основе сводимости.

[https://youtu.be/hxF6AuC-u4I Запись лекции].

====Лекция 5 (3 октября).====

Машины Тьюринга; неформальное и формальное определение; конфигурации; вычисление как преобразование конфигураций; вычислимые функции на словах конечного алфавита; вычислимость числовых функций, примеры; тезис Тьюринга; реализация "свойств алгоритмов" в модели машин Тьюринга; универсальная машина Тьюринга.

[https://youtu.be/SuVkmjBsRYk Запись лекции].

====Лекция 6 (10 октября).====

Формулы и термы языка первого порядка; сигнатуры; индуктивные определения; индукция по построению; параметры формулы.

[https://youtu.be/9qHMI2aN0pI Запись лекции].

====Лекция 7 (17 октября).====

Интерпретация сигнатуры \sigma; \sigma-стурктура; оценка переменных; значение терма и значение формулы в интерпретации при оценке; значение терма (формулы) в интерпретации зависит только от оценки (свободно) входящих туда переменных; значение формулы на наборе переменных; выразимость отношения формулой.

[https://youtu.be/jtrjpDBBrx4 Запись лекции].

== Семинары ==

=== Листки с задачами для семинаров ===
[https://drive.google.com/file/d/1i-2OA_pQcJ8c5Jbosb6UuFriDhcV0xVn/view?usp=sharing Листок 1]

[https://drive.google.com/file/d/10fdOStDqgzPbwx14iIMAbnpExhUIbmEW/view?usp=sharing Листок 2]

[https://drive.google.com/file/d/1M0Tq13q_UbkOE8IfxwCWo-SmM58a__7Q/view?usp=sharing Листок 3]

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

[https://drive.google.com/file/d/1DTEt-ZiHRi9tlD7XPH0m_wAuG2Cwylin/view?usp=sharing Листок 5]

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

== Консультации ==

Консультации А.А. Оноприенко: четверг 14-20 в дискорде https://discord.gg/v5DbugV (если меня там нет, пишите в телеграм @ansidiana).

Консультации И.Г. Райко: Очно или онлайн в соответствии с [[Участник:IRaiko#Расписание в сентябре – декабре 2020 года|таблицей]]. Для онлайн связи напишите в телеграм @ilya0x2dilya -- там поймём, как нам связаться.

Консультации Л.Н. Сысоевой: пятница после 16-00 (пишите в телеграм @lsysoeva, договоримся о точном времени и способе связи).

==Конспекты лекций==

[https://drive.google.com/file/d/13QUtHNIkxE402as8tsJgCwewcZag78HV/view?usp=sharing Конспект лектора по вычислимости]

[https://drive.google.com/file/d/1ocnXQXv1Y5yLeYZfHVYwU7Ek10L_-hKz/view?usp=sharing Конспект лектора по формулам первого порядка (не вполне соответствует лекциям!)]

[https://www.dropbox.com/s/nhdnt5d88zk14qv/res-lect-revised.pdf?dl=0 Конспект лекций профессора Н.К. Верещагина о методе резолюций]

==Конспекты семинаров==

Здесь выложены конспекты семинаров Оноприенко А.А., набранные Алисой Вернигор. Материалы будут обновляться по мере прочтения семинаров.

[https://drive.google.com/file/d/1UWvY-GiMT9MxhbV-nLhkCm-KogaLOyUz/view Семинар 2], 14.09.2020

[https://drive.google.com/file/d/1YuJOCbkVo4wLNELD1KvBmfeHZ-yiE9Ie/view Семинар 3], 21.09.2020

[https://drive.google.com/file/d/1UZOgOM4BF-OxSICj8ZuezZXbStGZ2R0t/view Семинары 4 и 5], 28.09.2020 и 05.10.2020

[https://drive.google.com/file/d/1B0mdBkrQJmQFjTwJ_RFh3HaUgua5bnS5/view Семинар 6], 12.10.2020

==Прочие ресурсы==
[https://drive.google.com/drive/folders/10pGBoYJ8B544pL0WZlq3hWc9cxwGaAg-?usp=sharing Директория с материалами курса.]

[https://t.me/joinchat/M0dUGBBjmuJAEs3JmWbU2A Группа в ТГ для обсуждения вопросов по курсу.]

[https://meet.edashkov.net/hse-amcs-dm2 Сервер телеконференций.] (Рекомендуется использовать Chrome.)

[https://docs.google.com/spreadsheets/d/1LaeCrFF7-iydLof_Lzu7s42t63FdA4Vcyng968ZmCS4/edit?usp=sharing Таблица распределения студентов по ассистентам]

==Рекомендуемая литература ==

1. Н.К.Верещагин, А. Шень. [https://www.mccme.ru/free-books/shen/shen-logic-part3-5ed.pdf Вычислимые функции]. М.:МЦНМО, 2008.

2. Н.К.Верещагин, А. Шень. [https://www.mccme.ru/free-books/shen/shen-logic-part2-5ed.pdf Языки и исчисления.] М.:МЦНМО, 2012. (Для курса будут наиболее важны главы 1, 3 и 4. Глава 1 содержит материал, который практически полностью входил в программу курса "Дискретная математика -1". Материал главы 4 в курсе будет затронут очень незначительно.)

3. Ч.Чень, Р.Ли. Математическая логика и автоматическое доказательство теорем. М.: Наука, 1983. (Для курса важен раздел про метод резолюций в главе 5.)

DM2-base2020/2021

2020-09-07T20:05:40Z

Adlyamzin:

DM2-base2020/2021

2020-09-07T20:05:08Z

Adlyamzin: Добавил себя в ассистенты