Сложность и логика — различия между версиями
Материал из Wiki - Факультет компьютерных наук
(Новая страница: «= Дискретная математика на 2-ом курсе ПМИ (основной поток)= Лекции проходят по вторникам в…») |
|||
| Строка 1: | Строка 1: | ||
| − | = | + | = Сложность вычислений и логика в теоретической информатике (3-ий курс ТИ) 2017 год = |
| − | Лекции проходят по вторникам в аудитории | + | Лекции проходят по вторникам в аудитории 306 в 15:10-16:30. Семинары по вторникам 16:40-18:00. Первая лекция и семинар 9 января. |
==Новости== | ==Новости== | ||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
==Лектор== | ==Лектор== | ||
| Строка 60: | Строка 9: | ||
Н.К. Верещагин nikolay.vereshchagin@gmail.com | Н.К. Верещагин nikolay.vereshchagin@gmail.com | ||
| − | == | + | ==Семинарист== |
| − | + | Козачинский Александр Николаевич, kozlach@mail.ru | |
| − | + | ||
| − | + | ||
| − | + | ||
| − | |||
| − | |||
==Краткое описание== | ==Краткое описание== | ||
| − | + | Теоремы Геделя о неполноте для формальной арифметики и теории множеств. | |
| − | + | Разрешимость элементарных теорий упорядоченного поля действительных чисел (теорема Тарского-Зайденберга и | |
| − | + | поля комплексных чисел. | |
| − | + | Экспандеры и теорема Рейнгольда о разрешимости связности для неориентированных графов на логарифмической памяти. | |
| − | + | Лемма Ловаса и быстрые алгоритмы для SAT. | |
| + | Сложность пропозициональных доказательств. | ||
| + | |||
==Отчётность по курсу и критерии оценки== | ==Отчётность по курсу и критерии оценки== | ||
| − | + | 4 домашних заданий, коллоквиум и экзамен. | |
| − | Оценка за каждое домашнее задание равна доле решенных задач, умноженной на 10. Общая оценка за домашние задания равна среднему арифметическому оценок за решение каждого из заданий. | + | Оценка за каждое домашнее задание равна доле решенных задач, умноженной на 10. Общая оценка за домашние задания равна среднему арифметическому оценок за решение каждого из заданий. На решение каждого ДЗ дается 14 дней, решение ДЗ нужно сдавать семинаристу до начала семинара. |
| − | На решение каждого ДЗ дается 14 дней, решение ДЗ нужно сдавать семинаристу до начала семинара. | + | |
Сдача домашних заданий после их срока невозможна. | Сдача домашних заданий после их срока невозможна. | ||
Каждое ДЗ будет проверено в течение 10 дней после дедлайна. Домашнее задание должно быть защищено в течение 3 недель после дедлайна. Для защиты студент должен прийти на консультацию и убедить преподавателя, что он понимает, что у него написано, и тем самым работа не списана. | Каждое ДЗ будет проверено в течение 10 дней после дедлайна. Домашнее задание должно быть защищено в течение 3 недель после дедлайна. Для защиты студент должен прийти на консультацию и убедить преподавателя, что он понимает, что у него написано, и тем самым работа не списана. | ||
| − | Коллоквиум (устный) и экзамен (письменный) оцениваются по десятибалльной системе. На коллоквиуме не разрешается пользоваться никакими записями. На экзамене можно пользоваться любыми бумажными источниками и нельзя никакими электронными | + | Коллоквиум (устный) и экзамен (письменный) оцениваются по десятибалльной системе. На коллоквиуме не разрешается пользоваться никакими записями. На экзамене можно пользоваться любыми бумажными источниками и нельзя никакими электронными. |
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
Сумма оценки за коллоквиум и оценки за домашние задания с коэффициентами 2/3 и 1/3, соответственно, составляют накопленную оценку. Накопленная оценка и оценка за экзамен с коэффициентами 3/5 и 2/5 дают итоговую оценку. Таким образом, оценки за коллоквиум и экзамен входят в итоговую оценку с коэффициентами 0.4, а оценка за домашние задания - с коэффициентом 0.2. | Сумма оценки за коллоквиум и оценки за домашние задания с коэффициентами 2/3 и 1/3, соответственно, составляют накопленную оценку. Накопленная оценка и оценка за экзамен с коэффициентами 3/5 и 2/5 дают итоговую оценку. Таким образом, оценки за коллоквиум и экзамен входят в итоговую оценку с коэффициентами 0.4, а оценка за домашние задания - с коэффициентом 0.2. | ||
| − | Те, кто не смог прийти на экзамен и коллоквиум по болезни, могут его | + | Те, кто не смог прийти на экзамен и коллоквиум по болезни, могут его сдать отдельно. Не набравшие в конце второго модуля нужное количество баллов (4) могут пересдать экзамен, а если и это не поможет, то сдавать экзамен комиссии. В последнем случае накопленная оценка аннулируется и оценка, полученная на экзамене, и является окончательной. |
| − | сдать отдельно. Не набравшие в конце второго модуля нужное количество баллов (4) могут пересдать экзамен, а если и это не поможет, то сдавать экзамен комиссии. В последнем случае накопленная оценка аннулируется и оценка, полученная на экзамене, и является окончательной. | + | |
====Правила округления==== | ====Правила округления==== | ||
| Строка 110: | Строка 50: | ||
====Экзамен==== | ====Экзамен==== | ||
| − | |||
| − | |||
==Сроки контрольных мероприятий== | ==Сроки контрольных мероприятий== | ||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
==Домашние задания == | ==Домашние задания == | ||
| − | |||
| − | |||
| − | + | ==Прочитанные лекции== | |
| − | + | ====Лекция 1 (9 января). ==== | |
| − | + | Формулировки первой и второй теоремы Гёделя для формальной арифметики и теории множеств. Понятие финитного и сугубо финитного доказательства. Программа Гильберта обоснования математики. | |
| − | + | ==Проведённые семинары (153 группа) == | |
| − | + | ===Семинар 1 (9 января)=== | |
| − | |||
| − | + | ==Конспекты лекций== | |
| − | [https://www.dropbox.com/s/ | + | '''[https://www.dropbox.com/s/q1xqbmlniw4u6an/main-ver.pdf?dl=0 Конспект лекций о линейном программировании.]''' |
| − | == | + | ==Консультации == |
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | == | + | ==Рекомендуемая литература == |
Версия 17:16, 9 января 2018
Содержание
- 1 Сложность вычислений и логика в теоретической информатике (3-ий курс ТИ) 2017 год
Сложность вычислений и логика в теоретической информатике (3-ий курс ТИ) 2017 год
Лекции проходят по вторникам в аудитории 306 в 15:10-16:30. Семинары по вторникам 16:40-18:00. Первая лекция и семинар 9 января.
Новости
Лектор
Н.К. Верещагин nikolay.vereshchagin@gmail.com
Семинарист
Козачинский Александр Николаевич, kozlach@mail.ru
Краткое описание
Теоремы Геделя о неполноте для формальной арифметики и теории множеств. Разрешимость элементарных теорий упорядоченного поля действительных чисел (теорема Тарского-Зайденберга и поля комплексных чисел. Экспандеры и теорема Рейнгольда о разрешимости связности для неориентированных графов на логарифмической памяти. Лемма Ловаса и быстрые алгоритмы для SAT. Сложность пропозициональных доказательств.
Отчётность по курсу и критерии оценки
4 домашних заданий, коллоквиум и экзамен.
Оценка за каждое домашнее задание равна доле решенных задач, умноженной на 10. Общая оценка за домашние задания равна среднему арифметическому оценок за решение каждого из заданий. На решение каждого ДЗ дается 14 дней, решение ДЗ нужно сдавать семинаристу до начала семинара. Сдача домашних заданий после их срока невозможна.
Каждое ДЗ будет проверено в течение 10 дней после дедлайна. Домашнее задание должно быть защищено в течение 3 недель после дедлайна. Для защиты студент должен прийти на консультацию и убедить преподавателя, что он понимает, что у него написано, и тем самым работа не списана.
Коллоквиум (устный) и экзамен (письменный) оцениваются по десятибалльной системе. На коллоквиуме не разрешается пользоваться никакими записями. На экзамене можно пользоваться любыми бумажными источниками и нельзя никакими электронными.
Сумма оценки за коллоквиум и оценки за домашние задания с коэффициентами 2/3 и 1/3, соответственно, составляют накопленную оценку. Накопленная оценка и оценка за экзамен с коэффициентами 3/5 и 2/5 дают итоговую оценку. Таким образом, оценки за коллоквиум и экзамен входят в итоговую оценку с коэффициентами 0.4, а оценка за домашние задания - с коэффициентом 0.2.
Те, кто не смог прийти на экзамен и коллоквиум по болезни, могут его сдать отдельно. Не набравшие в конце второго модуля нужное количество баллов (4) могут пересдать экзамен, а если и это не поможет, то сдавать экзамен комиссии. В последнем случае накопленная оценка аннулируется и оценка, полученная на экзамене, и является окончательной.
Правила округления
В вычислениях текущие оценки и промежуточные величины не округляются. Результат вычисляется точно и округляется только в момент выставления накопленной и итоговой оценок. Округление при выставлении итоговой оценки арифметическое, а при выставлении накопленной оценки используется следующее правило округления: между 1 и 5 округление вниз, между 5 и 6 округление арифметическое, а в остальных случаях округление вверх. Т.е. 3,92 округляется до 3, 5,48 – до 5, 5,54 – до 6, 7.12 – до 8.
Экзамен
Сроки контрольных мероприятий
Домашние задания
Прочитанные лекции
Лекция 1 (9 января).
Формулировки первой и второй теоремы Гёделя для формальной арифметики и теории множеств. Понятие финитного и сугубо финитного доказательства. Программа Гильберта обоснования математики.
Проведённые семинары (153 группа)
Семинар 1 (9 января)
Конспекты лекций
Конспект лекций о линейном программировании.
